Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Generating random points in a sphere


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Relfos   Members   -  Reputation: 331

Like
0Likes
Like

Posted 27 January 2014 - 09:42 AM

I am implementing volumetric cloud rendering.

So I need to generate a lot of particles in shape of a cloud.

Right now I am using this formula:

 

for I:=1 To ParticleCount Do

Points [I] := VectorCreate( Random(-Radius, Radius), Random(-Radius, Radius), Random(-Radius, Radius));

 

Basically, it picks 3 random coords inside the defined Cloud radius range,

The problem is, clouds generated with this formula look like cubes instead of spheres.


I tried looking in google for ways to generate points in a sphere, but I could only find ways to generate points in the surface of a sphere, not in the full volume.

Any suggestions for how to change the formula to produce spheres instead of cubes?

 

Once I can generate spheres I can approximate a cloud shape by using many spheres.

But if there is a better method to generate a cloud shape, tell me :)



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13933

Like
4Likes
Like

Posted 27 January 2014 - 09:52 AM

Two options:

(1) Write a do-while loop around your random point picking, so you keep generating random points until one inside the sphere is generated.

(2) Pick a random point on the surface of the sphere and then pick a random number between 0 and 1 which will be used to interpolate between the center of the sphere and your point at the surface. In order to get an even distribution of points, your random number should be the cubic root of a uniformly-distributed number.


Edited by Álvaro, 27 January 2014 - 09:53 AM.


#3 Relfos   Members   -  Reputation: 331

Like
0Likes
Like

Posted 27 January 2014 - 10:04 AM

Thanks, that seems a good idea, I'll try it :)



#4 morbik   Members   -  Reputation: 363

Like
0Likes
Like

Posted 27 January 2014 - 11:42 AM

Might also make sense to switch over to a spherical coordinate system.  Pick a random value from 0 - 360 for X, 0 - 360 for y, and a random value from 0 - radius for z. Then convert that to the cartesian coordinates.

 

http://en.wikipedia.org/wiki/Spherical_coordinate_system

It's just what I would do, you don't necessarily have to.



#5 Álvaro   Crossbones+   -  Reputation: 13933

Like
1Likes
Like

Posted 27 January 2014 - 12:30 PM

Might also make sense to switch over to a spherical coordinate system.  Pick a random value from 0 - 360 for X, 0 - 360 for y, and a random value from 0 - radius for z. Then convert that to the cartesian coordinates.

 

http://en.wikipedia.org/wiki/Spherical_coordinate_system

It's just what I would do, you don't necessarily have to.

 

How do you pick those random values so the resulting distribution of points in the sphere is uniform? That's precisely what this thread is about. If you do the naive thing you just described, you'll end up with too many points near the center of the sphere and too many points near the poles, or something like that (not sure what "x" and "y" are in your post to know for sure).



#6 Relfos   Members   -  Reputation: 331

Like
0Likes
Like

Posted 27 January 2014 - 12:40 PM

I tested his approach now, well, it seems to work fine, the distribution might not be uniform but is enough for this case.

Also tested the do/while approach, but using spherical coordinates seems faster



#7 samoth   Crossbones+   -  Reputation: 5036

Like
1Likes
Like

Posted 27 January 2014 - 12:47 PM

Note that spherical coordinates will cause clustering at poles, which is most probably not what you want. A slightly more complicated approach is needed to properly pick points on a sphere (which, if the radius is also random, will give points inside the sphere).

 

On the other hand, the solution of generating points in the unit cube (or in the "radius cube", does that word exist?)  and discarding points for which dot(point, point) > distance_squared is much easier and works well, too.


Edited by samoth, 27 January 2014 - 12:48 PM.


#8 Aressera   Members   -  Reputation: 1487

Like
2Likes
Like

Posted 27 January 2014 - 01:30 PM

Here is the code that I use to generate uniform random points on a sphere (which is derived from the wolfram link posted above):

float u1 = randomRange( -1.0f, 1.0f );
float u2 = randomRange( 0.0f, 1.0f );
float r = sqrt( 1.0f - u1*u1 );
float theta = 2.0f*math::pi<float>()*u2;

return Vector3( r*cos( theta ), r*sin( theta ), u1 );


#9 Relfos   Members   -  Reputation: 331

Like
1Likes
Like

Posted 27 January 2014 - 07:01 PM

 

Here is the code that I use to generate uniform random points on a sphere (which is derived from the wolfram link posted above):

float u1 = randomRange( -1.0f, 1.0f );
float u2 = randomRange( 0.0f, 1.0f );
float r = sqrt( 1.0f - u1*u1 );
float theta = 2.0f*math::pi<float>()*u2;

return Vector3( r*cos( theta ), r*sin( theta ), u1 );

Thanks, it seems to work great :)



#10 iMalc   Crossbones+   -  Reputation: 2314

Like
1Likes
Like

Posted 29 January 2014 - 02:49 AM

 

Might also make sense to switch over to a spherical coordinate system.  Pick a random value from 0 - 360 for X, 0 - 360 for y, and a random value from 0 - radius for z. Then convert that to the cartesian coordinates.

 

http://en.wikipedia.org/wiki/Spherical_coordinate_system

It's just what I would do, you don't necessarily have to.

 

How do you pick those random values so the resulting distribution of points in the sphere is uniform? That's precisely what this thread is about. If you do the naive thing you just described, you'll end up with too many points near the center of the sphere and too many points near the poles, or something like that (not sure what "x" and "y" are in your post to know for sure).

 

Indeed, a spherical coordinate system would create clustering due to the effects of gimbal lock. The same solutions to that problem can be used to overcome this (vector algebra / quaternions)

 

But yes ultimately the simplest, and quite efficient solution is the rejection method where you try again if the point is outside of the radius. Do a squared-radius check of course, to avoid square roots inside the loop.


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS