Spherical Asteroid Distribution

Remember, "random" on a computer is really only psuedo-random, so you can't really be sure that it's a uniform distribution.

There are ways to fix that though. At any rate, you have several ways of accomplishing this. The first way is to general three random XYZ coordinates within a cube distribution and see if the point is within the sphere. Keep it if it is, or reject it if it isn't. That would work, but I don't like the "hit or miss" nature of it. Feels sloppy.

The second method is to generate three XYZ coordinates again, but use them as a direction vector. Normalize it, find a third random uniform value between 0 and the radius of the circle (or -radius and radius, it doesn't matter), and multiply the unit vector by the scalar value to get the position.

Here's the deal. The first method is hit-or-miss, but you can avoid the square-root required to normalize the vector in the second method. The second method however is guaranteed to generate valid asteroid positions within linear time, while the first one just "keeps going" until all your asteroids are there.

And about the uniform distribution, I'm pretty sure (rand()/RAND_MAX)*maxValueInclusive will do the trick.

EDIT: Just realized the asteroids have size too Simply subtract the bounding radius of the asteroid from the radius of the field for an effective placement radius.

[edited by - Zipster on May 31, 2003 1:09:10 AM]

quote:

---

Original post by Zipster
The second method is to generate three XYZ coordinates again, but use them as a direction vector. Normalize it, find a third random uniform value between 0 and the radius of the circle (or -radius and radius, it doesn''t matter), and multiply the unit vector by the scalar value to get the position.

---

This is not uniform because the density of the asteriods will be higher near the center. To get uniform distribution, generate a direction vector and a value from 0 to 1. Then use the cube root of the value times the radius of the sphere.

Hey jambolo... is that easy to prove (the cube root thing)? I''ve always wondered how to generate uniform volume distribution with a direction vector and a radius, but that seems too simple.

Ok the problem with the ideas I''ve seen so far is that they only work for infinitissimal points - my points are asteroids of no more then 110.0f units in radius. I need to ensure a placement such that no two asteroids will be within each other.

quote:

---

Original post by vanillacoke
Hey jambolo... is that easy to prove (the cube root thing)? I''ve always wondered how to generate uniform volume distribution with a direction vector and a radius, but that seems too simple.

---

I''m too lazy to prove it, so I don''t know for sure if it is really true. But I can demonstrate the reasoning pretty easily.

The volume of a sphere is 4/3 * pi * r³, so a unit sphere has the volume 4/3 * pi * 1³ = 4/3 * pi. Half the numbers generated in the range [0,1] will be < 1/2 and half will be > 1/2. A sphere of radius 1/2 has the volume 4/3 * pi * (1/2)³ = 4/3 * pi * 1/8. Using the generated value for the radius means 1/2 of the points will be in the inner 1/8 of the volume, and half will be in the outer 7/8. That is obviously not uniform.

The volume of a sphere with a radius of the cube root of 1/2 is 4/3 * pi * ((1/2)^1/3)³ = 4/3 * pi * 1/2. Using this value for the radius means 1/2 of the points will be in the inner 1/2 of the volume, and half will be in the outer 1/2. That seems pretty uniform.

quote:

---

Original post by Zipster
The second method is to generate three XYZ coordinates again, but use them as a direction vector. Normalize it, find a third random uniform value between 0 and the radius of the circle (or -radius and radius, it doesn''t matter), and multiply the unit vector by the scalar value to get the position.

---

Since the coordinates were generated inside a cube, once normalized, there will be more vectors in the directions pointing toward a cube vertex.

That, and the non-uniform problem that Jambolo pointed out. But it could be fixed by taking r = (random_number) ^ (1/3). At least, that''s what intuition tells me right now. I''m late!

Cédric