Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!texbell!texsun!newstop!sun!peregrine!falk
From: falk@peregrine.Sun.COM (Ed Falk)
Newsgroups: comp.graphics
Subject: Re: Random points on a sphere
Message-ID: <135454@sun.Eng.Sun.COM>
Date: 10 May 90 02:04:19 GMT
References: <150632@<1990May4> <4400066@m.cs.uiuc.edu> <271@paralogics.UUCP>
Sender: news@sun.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 63

In article <271@paralogics.UUCP> shaw@paralogics.UUCP (Guy Shaw) writes:
>In article <4400066@m.cs.uiuc.edu>, cwg@m.cs.uiuc.edu writes a good
>summary of many postings:

[generate random points on a sphere by generating random points in
a unit cube; reject points outside the sphere, project points inside
the sphere]

>The thing that bothers me about using any method that involves
>generating random numbers and rejecting those that fail some test
>is that, even though an average rejection rate is known, there is
>no guarantee that I won't generate a _long_ series of rejected numbers.
>
> ...
>
>Am I just being paranoid?  Is this just a theoretical nit, or does this
>count "for all practical purposes", as well?  Does anyone have some pointers
>to literature on the subject?

It's always a good idea to be paranoid when looking at algorithms.

In this case, though I wouldn't worry.  Statisticly speaking, the
fraction of rejected points will be

	volume(cube) - volume(sphere)
	-----------------------------  =  1 - volume(unit sphere) =~ 48%
		volume(cube)


Of course, it *is* possible to get a long string of random points
outside of the sphere, but with random numbers it's possible to get
long strings of anything.  That's the risk you take with random
numbers, otherwise they wouldn't be random.

Here's something else to be paranoid about though; make sure that
this algorithm doesn't divide by zero.  In general, if I'm testing
a number to see if it's zero before dividing, a flag goes up in
my head to tell me to be careful of very small nonzero numbers.
In the points on the sphere case, random points very close to the
origin might cluster when projected to the sphere because of low
precision, or they might be significantly off the surface of the
sphere because of round-off error.  For these reasons, my own
version of the algorithm is

	x = rand[-1 1] ;
	y = rand[-1 1] ;
	z = rand[-1 1] ;
	r = sqrt(x*x + y*y + z*z)
	if ( r > 1  ||  r < .01 )
	  reject ;
	else
	{
	  x = x/r ;
	  y = y/r ;
	  z = z/r ;
	}

Finally, as a general note, the sqrt() operation can be saved until
you accept the point, thus reducing the work.

		-ed falk, sun microsystems
		 sun!falk, falk@sun.com
		 card-carrying ACLU member.