Randomly generating points within a sphere

[tomb]

weston: that will result in a higher consentration of points near the center of the sphere, and not a random distribution.

[Anonymous]

Hmm, I see what you mean. The first method I described works correctly (http://www.cyntaks.com/projects/spherescreen.png), that last part I just thought of off the top of my head cause I thought elias may have been asking for something else. Why is it that there are more points toward the center anyway?

[tomb]

Why is it that there are more points toward the center anyway?

You randomly distrubute the points from the center to the edge of the sphere. Since the volume of a slice of the sphere increases as you move away from the center, the consentration decreases. The volume of of range [1, 2] from the center is much less than the range [9, 10].

[andrewc]

Well, I got ahold of a physics professor friend of mine... he shot down the vector method.

Instead he gave me this method (I converted it to code):

float r = (float)Math.random()*(sphereradius);
float phi = (float)(Math.random()*Math.PI);
float theta = (float)(Math.random()*Math.PI*2f);
float tempsetX = (float)(r * Math.cos(theta) * Math.sin(phi));
float tempsetY = (float)(r * Math.sin(theta) * Math.sin(phi));
float tempsetZ = (float)(r * Math.cos(phi));
pointlocation = new Vector3f(tempsetX,tempsetY,tempsetZ);

Basically, using spherical points and converting to cartesian. It's very similar to Anders' method.

I would have thought that this produced a clustering of points near to the poles. Phi and Theta are latitude and longitude - generating them like this will give an even distribution when you flatten the sphere into a 2d map, but on a sphere the lines of longitude get closer together towards the poles. You could take this into account when choosing the latitude:

float phi = (float)(Math.asin(1 - 2 * Math.random()) + Math.PI / 2)

but I haven't actually checked this in 3d.

[elias4444]

Wow! That new phi calculation was amazing!

Back to math classes for me I guess.  :?

[andrewc]

Did it work then?
Actually, a little thought suggests that this slightly shorter one does the same:

float phi = (float)(Math.acos(1 - 2 * Math.random()))

[elias4444]

The following worked PERFECTLY:

float r = (float)Math.random()*(mainsphereradius - mainsphereradius/10f) + mainsphereradius/10f;
float phi = (float)(Math.acos(1 - 2 * Math.random()));
float theta = (float)(Math.random()*Math.PI*2f);
float tempsetX = (float)(r * Math.cos(theta) * Math.sin(phi));
float tempsetY = (float)(r * Math.sin(theta) * Math.sin(phi));
float tempsetZ = (float)(r * Math.cos(phi));
pointlocation = new Vector3f(tempsetX,tempsetY,tempsetZ);

Thank you for your help. This math just amazes me honestly.

P.S. The funny stuff for "r" is just to keep the points from existing near the center of the sphere.

[andrewc]

Hmm. It didn't occur to me before, but you must be getting a higher density of points near the centre. I don't know whether you want this effect but you can distribute the points evenly with a better choice of radius. Assuming you want the same gap in the middle:

double radiusOfGap = 0.1;
double temp = Math.random() * (1 - radiusOfGap) + radiusOfGap;
float r = (float) (mainsphereradius * Math.sqrt(temp));

[Mokosha]

I'm replying to this thread only to provide a little insight into the discussion that came up on the front page after googling the problem:

Wolfram alpha presents a very nice method for generating points on the unit sphere:
http://mathworld.wolfram.com/SpherePointPicking.html

Now, in order to generate points within the sphere, one cannot simply choose a random radius, as that will bunch the points towards the center. It seems that a few people here have come up with a method for generating a hacked version that unclumps them from the center. Arguably, computer graphics is one giant hack, so this might be acceptable to most for finding a "good enough" solution.

Mathematically, if you have a point x on an n-dimensional sphere of radius R and a value u which is uniformly chosen over the interval [0, R], then a uniformly random point within the sphere would simply be:

(u ^ (1/n)) * x

What this means is that in order to find a truly uniformly distributed point within a sphere of radius R one method is to first find a point on the sphere and then scale it by the cube root of a value chosen from the interval [0, R].

The ramifications of this are that not many computers can do a cube root in a reasonably fast manner when compared to the "close enough" solutions presented in this thread.

I hope I didn't break any forum rules by digging up this thread from the grave, I was hoping to shed some light on whatever googler may come across it as I did.

[szoltomi]

Okay, a little bit more grave-digging by me because I believe you all overthink it.

Generate a set of points in the bounding box of the sphere, then simply cull out the ones where the distance ( Sqrt(x²+y²+z²) ) is larger than 1.

And if you need a fixed number of points, just put it in a counting loop, testing for every point. There is a drawback here, that this has a potential infinite maximum execution time, if you are terribly unlucky. 

[amarzo]

I would try to avoid all methods of generating random points until one of them lies into the sphere, polygon, torus, ... at least if there is a more proper method.

Cartesian/Polar transform is cool but as you have tried it produces a not desired concetracion of points near the center.

If you have an sphere of radious sphereRadious located at (sphereX, sphereY, sphereZ) I think a good method of generating random points inside the sphere would be ([x,y] refers to an uniform distribution between x and y):

t = [0,2pi]
u = [0,1]
z = [-1,1]
auxr = sqrt(1-z*z)
auxu = u^(1/3) * sphereRadious
x  = auxr * cos(t) * auxu + sphereX
y  = auxr * sin(t) * auxu + sphereY
z  = z * auxu + sphereZ

[tomb]

I would try to avoid all methods of generating random points until one of them lies into the sphere, polygon, torus, ... at least if there is a more proper method.

Why? It is much easier to understand and the code will be more readable. I bet it is also faster since trig functions are slow. I will argue that it IS the proper method of solving this kind of problem. It was one of the suggestions on the first page, but the discussion got hung up on solving it the complex way.