# Fast method of detecting whether point is inside mesh

I'm trying to construct a 3d object from a large number of particles. I think this is called BVH (Bounding volume hierarchy). I figured the best way is to draw the particles inside the mesh, then let them drop down. Repeat as often as produces suitable results.

For this, I need to check for each point whether they lie inside the 3d model. I might be using something in the order of 1 million particles, so the point-in-mesh code needs to be fast. I have some clues about creating a 2d stencil projection first, and checking against that. But I'm not really sure what's the smart way to go about this.

-
To clarify: do you have a given polygon mesh and you want to spawn particles on the surface or in the interior? Or do you have a given collection of particles and you want to generate a polygon mesh to more or less match the shape of the particle cloud? Either way, how does the BVH come into it - how are you trying to use a BVH? – Nathan Reed Apr 12 '13 at 18:23
Yes, I have a given polygon mesh... Actually an amazing character design sculpted by a professional 3d artist just hours ago for this project, I got lucky :) I'm gonna also animate the mesh interactively with skeleton movement info captured from human bodies using Kinect, and display this live. Gonna be awesome. – Eero Heikkinen Apr 12 '13 at 18:26
It doesn't really matter whether the particles are spawned on the surface or in the interior, as long as the result looks good. I'm looking into just spawning particles along the surface of the mesh if the goal outlined by this question proves to be too difficult, but it's going to create a hollow particle cloud. Don't know whether that really affects the visual output though. – Eero Heikkinen Apr 12 '13 at 18:27
BVH was an algorithm I was suggested I should look into to do the particle generation. Didn't really understand it though, and I'm running on a very strict timeline here and can't allow to waste time. – Eero Heikkinen Apr 12 '13 at 18:30

As the link suggests, a BVH is a data structure that is used to quickly compute collision queries for a set of polygons. It doesn't usually provide information about the underlying geometry itself other than possibly maintaining references to triangles in the leaves of the tree.

In terms of your problem of finding out whether or not a point is within a set of geometry, a BVH is a good way to go. How to construct a BVH from a set of particles is a bit more tricky. In general, your BVH won't be a tight fit, and might result in some false positives for points that are extremely close to your point set.

In order to reconstruct a 3D surface from your points you will likely need to use some implicit representation to generate triangles. This work was done back in 2001 with a very famous model:

http://vgc.poly.edu/~csilva/papers/vis2001c.pdf

Once you get the idea for how to think about these kinds of problems, solutions are available via the Computational Geometry Algorithms Library. More specifically, they have a solution to the problem of generating surfaces from 3D point sets:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Surface_reconstruction_points_3/Chapter_main.html

-

If you want to spawn particles on the surface of a mesh, it's relatively easy: pick a random triangle, then pick a random point on it. The choice of triangle should be weighted by area so that the particles don't clump into the denser areas of the mesh (unless that is a desirable effect).

To spawn particles within the volume enclosed by a mesh is harder. Rejection sampling - generating random points in the bounding box of the model, then checking if they're inside and throwing away the ones that aren't - will work, but I suspect it isn't very efficient, as you'll generate many points you won't use. Still might be worth a try. To test whether a point is inside the mesh, see this StackOverflow question, which points out that you only need a 2D acceleration structure, not full 3D, to make this work. But you're still going to be doing a bunch of ray-triangle tests to determine whether a point is inside or outside the volume.

If you did build a full 3D acceleration structure, such as a BSP or BVH, there's probably a way to use it to focus the generation of points. For instance, you could pre-calculate the volume of each BSP leaf node, then generate a point by picking a random leaf node weighted by volume and generating a random point within it. That sounds difficult, though - both calculating the volume of a BSP node and picking a random point within it sound nontrivial.

-
Yeah - actually my deadline for this is by tomorrow evening. So building a complex 3d acceleration structure is out of question I think :) I probably will end up just spawning particles on the surface of the mesh. It would be cool to be able to focus on different areas of the mesh with more detail, like the face of this creature needs to have a lot more detail than the rest of it's body. – Eero Heikkinen Apr 12 '13 at 19:12

I think the easiest method is to pre-build a skeleton. If your moving the object, then the skeleton can be composed of grid point means. The skeleton needs just enough articulation that the skeleton never leaves the grid. Each "bone" will have numerical ranges of gridpoints that are close to it.

To check a particle find the closest bone. Then find 2 grid points near the particle, then check if a solution exists where particle is in the plane point1 point2, arbitrary point on bone. The grid points must be chosen with care, to be left and right of the bone, and close enough that they don't leave an arc where the particle could hide.

-