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.
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
Where does the Z coordinate factor into this? Is it x^2 + y^2 + z^2 = r^2 ?
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. :?
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);
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. :D
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.
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
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.
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.
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.
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
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. :P
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?
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 :D
Anders
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.
weston: that will result in a higher consentration of points near the center of the sphere, and not a random distribution.
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?
QuoteWhy 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].
Quote from: "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.
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.
Wow! That new phi calculation was amazing!
Back to math classes for me I guess. :?
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()))
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.
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));
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.
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(x2+y2+z2) ) 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. :P
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
Quote from: amarzo on August 05, 2011, 10:23:27
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.