Randomly generating points within a sphere

[elias4444]

Ok, my math just isn't so great (I think I'm gonna go buy a book)...

I'm trying to generate x number of random points, all within a sphere. Big problem though, I can't seem to figure out the math.  :?

I know the radius of the sphere, and it's origin (let's just say it's 0,0,0 for simplicity's sake). I've tried several methods, but I always end up with the points being distributed too far within the sphere, or going outside of it.  Anyone know the math for this? It would be greatly appreciated.

[WiESi]

The formula for a sphere is:
(x - xm)² + (y - ym)² + (z - zm)² = r²
where (xm, ym, zm) is the coordinate of the center. r is the radius and (x, y, z) is the coordinate. This formula would be true if the point is on the surface of the sphere. So if the point should be within (or on the surface) then use this formula:
(x - xm)² + (y - ym)² + (z - zm)² <= r²

WiESi

[elias4444]

Where does the Z coordinate factor into this? Is it x^2 + y^2 + z^2 = r^2 ?

[elias4444]

Of course, now that I'm thinking about it, I'm not even sure how to code it up using the sphere equation...

I tried generating random vectors for dx, dy, and dz, but I wasn't sure how to plug them into the radius to find the point x,y,z. Any ideas? The vector method seems easier to code... I think.  :?

[jam007]

An alternative method:
1 radom radius r (0 to sphere radius)
2 random longitude l (0 to 2*PI)
3 random latitude h (0 to PI) Edit: should be -PI/2 to PI/2

(x,y,z)=(r*cos(l)*cos(h), r*sin(h), r*sin(l)*cos(h))

More math instead of using the previous method and only randomizing x, y, z and discarding those outside the sphere but math is fun :wink:

Anders

Edit:
Trial and error method like this:
do {
dx=random()*2*R-R;
dy=random()*2*R-R;
dz=random()*2*R-R;
while(dx*dx+dy*dy+dz*dz>R*R);
position.set(xorigin+dx, yorigin+dy,zorigin+dz);

[elias4444]

Thanks Anders... It's working really well. I get an interesting plotting of points (they like gravitating more towards the center and axis of the sphere), but I think I can work with it.  

Edit: Oh, and one more thing for those trying it, I had to make the random "h" =  (Math.random()*Math.PI*2) - Math.PI), in order to get values below the top half of the sphere as well.

[jam007]

Ah, sorry, should have been r*cos(h) for the y coord to work with 0 to PI.
Edit: and then x and y should use sin (h)

Yes that would be an effect that they seems to be "gravitating" towards the middle since the sphere is smaller there and r is lineary randomized.
this should not happend with the discard method that WEiSi suggested

Anders

[elias4444]

I'm still curious about the vector method... my vector math is really weak, but I seem to remember, if you have a dx, dy, and dz, and a radius (or random number from 0 to radius), you can generate a point. I'm just not sure who to properly calculate the vector/average the vector for that.

[elias4444]

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.

[tomb]

That is way to complex. I would go with WEiSis method. Generate randomers inside the sphere bounding box. Discard points outisde sphere.
if dx, dy, dz is distance from center of the sphere to the test point, then the is inside if:

boolean isInsideSphere = ((dx*dx + dy*dy + dz*dz) < (r*r));

Easy, fast and no mucking around with trig functions.

[jam007]

Your helpful physics professor and I suggest the same method. The difference is only a matter of what axis you call x, y, and z. (And the mistake I made in sin(h) writing 0 to PI instead of -PI/2 to PI/2 :oops: )
(Not very surpricing since IÃ,´m a physics teatcher...)

I agree with tomb that for just generating random points itÃ,´s probably easier to do the trial and error method.

Anders

[elias4444]

I guess my problem is wanting to actually understand the math better (does that make me crazy?). Unfortunately, my physics professor friend informed me that he didn't learn a lot of the sphere mathematics until he was a senior in his major.  :?  I guess that doesn't bode well for someone who graduated in English.  

[tomb]

In this case the math is very easy. It's been a while since I learned it in school, but I think it is call phytagoras (no idee how it is spelled, but it's the greak guy how discovered it). When you got a triangle with one angle that is 90 deg, then the distance of the longest side is the square root of the sum of the square shortest side. Ok, I know my description sucks, and I might just be rambeling, but this must be basic highschool math that everyone learns, right?

[jam007]

Correct!
Draw a circle at the origin of a x,y coordinate system. Draw a line from the origin to a point on the circle and then straight down to the x-axis. You then got a right-angled triangle. Then x^2+y^2=r^2 (Pythagoras theorem) for all points on the circle.
For a sphere you then imagines a paper standing in the z-direction and going through the origin and a point of your original circle. You will find that  you have to use pythagoras theorem twice (first on the xy-surface and then for the radius) and you end up with x^2+y^2+z^2=r^2

cos and sin is slightly more advanced but the reason physicist in general donÃ,´t read a lot of spherical trigonometry is that they dont need it not that it complicated. The only physicists who reads a lot about spheres are astronomers, you can all guess why  

Anders

[weston]

I actually did this last weekend, using vectors. The steps were as follows:

1:generate point a point within a range much higher than your actual sphere radius, store that point in a vector.

2: normalize the vector

3: multiply the individual components of the normalized vector by the (+/-)radius of the sphere.

4: repeat for the number of points you want your sphere to be made up of.


that will put all the points on the edge of a sphere though, not sure if thats what you want. It would be easy to change it so they filled the sphere though. In step 3 where you multiply by the radius of the sphere, instead multiply by a random number between zero and the radius.