View Full Version : Move an object to a random point inside a volume

 KielFiggins10 October 2008, 02:20 AMHey, I'm trying to figure out a way to move an object to a random point inside another objects volume (not bounding box/area). I can already to this with a bounding box (taking the mins'maxs') and randomizing the location. Works fine, the tool is helpful, but i'd like more control. Say I had a sphere or some other closed object (single mesh, nothing overly complex). How would I go about getting the locational values that are inside the mesh? Much appreciated.
Keilun
10 October 2008, 03:21 AM
For standard geometric shapes, like a sphere, you can go back to the mathematical definition:

eg. For a sphere:

x^2 + y^2 + z^2 = r^2

To get a random point inside that volume, you want to choose a random (x, y, z) such that:

x^2 + y^2 + z^2 <= r^2

You know that the following statements must hold true:

-r <= x <= r
-r <= y <= r
-r <= z <= r

So that limits your random choices, but that doesn't guarantee it's in the sphere yet. So then, we can do this step by step:

1. Randomly select one of the 3 axes (X,Y,Z) to begin with.
2. Say we choose X.
3. Randomly select a value between [-r:r].
4. Say we choose X=0.5*r.
5. Next randomly select one of the remaining 2 axes (Y,Z).
6. Say it chose Z.
7. Randomly select a value between [-Q:Q]

2D Trig tells us that given X and R, we can compute the max value of Z that will coincide with the sphere.

theta = arccos( X / r )
Q = r * sin( theta )

8. Say it chose Z = 0.2*r.
9. That leaves us with:

(0.5r)^2 + Y^2 + (0.2r)^2 = r^2

Solve for Y in terms of r:

0.25r^2 + Y^2 + 0.04r^2 <= r^2
Y^2 <= (0.71)r^2
Y <= 0.842*r

I think my math is right there. Doing this off the top of my head. That will do your basic sphere. You can extend this to spherical derivatives (ellipses) and such. For more generic arbitrary meshes, this approach is not going to work. Not really sure how to approach arbitrary meshes. My first stab would be exploring ray intersection methods with randomized penetration depths - pretty computation expensive though.

Derek Wolfe
10 October 2008, 06:24 PM
Find a random position in the bounding box.
Find the closest face on the mesh to that position.
Get the normal, and position, of the face.
Compare the normal vector, with the vector derived from the position minus the face position.
If the angle between the vectors is less than 90 degrees, the point is inside the mesh.

Something like this would work.

YourDaftPunk
10 October 2008, 06:16 AM
Derek, I don't know if that would work. Simple objects it's probably fine (and fast).

KielFiggins, I think you could start with a point on a face, then in a random direction opposite of the face normal (so it is facing inward), trace a ray. When you find that ray intersection, you now have a line inside the model between two faces. Pick a random point along that line. Instance your object.

You could do checks to make sure that the points are not being placed too closely together. This stuff won't be fast on a medium to large model without an acceleration structure like a kd-tree or octree- too many ray polygon tests. Still, there is lots of info and example code online.

I did a quick search for papers on the subject, but I seem to have been using the wrong terms because I came up with nil. Good luck.

-shawn

YourDaftPunk
10 October 2008, 06:40 AM
I found this, and it is similar to what I was describing, but in two dimensions.

Polygon filling:
http://alienryderflex.com/polygon_fill/

sj_bee
10 October 2008, 10:10 AM
For standard geometric shapes, like a sphere, you can go back to the mathematical definition:

eg. For a sphere:

x^2 + y^2 + z^2 = r^2

Also, maya has a built in function to do this

sphrand <float>
sphrand <vector>

"This command generates random vectors evenly distributed inside a sphere of the specified radius. If a vector argument is given, sphrand scales the output by the components of the vector argument."

check the MEL help on how to use this command

Derek Wolfe
10 October 2008, 08:50 PM
Here's a fun way to find a point inside an arbitrary mesh:
Emit particles from the mesh towards the inside of the object, using a surface emitter.
Have the particles collide with the mesh.
run for a few frames.
Choose a particle and use it's position.

YourDaftPunk
10 October 2008, 10:39 PM
Here's a fun way to find a point inside an arbitrary mesh:
Emit particles from the mesh towards the inside of the object, using a surface emitter.
Have the particles collide with the mesh.
run for a few frames.
Choose a particle and use it's position.

Best way I think unless you really want to code a lot :)

CGTalk Moderation
10 October 2008, 10:39 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1