Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!cwg
From: cwg@m.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: Random points on a sphere
Message-ID: <4400066@m.cs.uiuc.edu>
Date: 5 May 90 14:21:00 GMT
References: <150632@<1990May4>
Lines: 33
Nf-ID: #R:<1990May4:150632:m.cs.uiuc.edu:4400066:000:1253
Nf-From: m.cs.uiuc.edu!cwg    May  5 09:21:00 1990


Re: Random points on surface of sphere (or in its interior).

There are essentially two choices:

(1) choose a region over which it is simple to generate random points and
which contains the sphere, and then reject those points outside.
Hence, since uniform [0,1] are usually computationlly inexpensive, generating
on a cube is good.  The additional cost, as has been pointed out, is
the 48% of the points that have to be discarded, and the cost
of computing the "discard" function.  (Also, if only the surface points
are needed, the cost of projecting interior points back to the
surface.)  Thus the cost is

(3R + 3M + 2A + C)/0.52

for each point, where R, M, A, and C are costs of random number,
multiply, Add, and comparison.  Projection costs an additional

Q + 3D

per point, where Q and D are costs of square root and divide.

(2) Choose a parameterization of the space, and then generate points
with a probability distribution appropriate to the parametarization.
This has also been proposed, using polar coordinates.  If only the
surface is needed, only two parameters are needed, say lattitude and
longitude.  The cost is now

2R + T

where T is the cost of computing a trigonometric function, typically
about 6(M+A).  It is probably faster.