How to Sample 3D Points Outside and Inside the Mesh Surface

Question

I have a mesh of an object enclosed in unit volume cube and I would like to sample points inside and outside the mesh surface. What are the different ways of doing it? Is there any sample code available?

Answer 1

What you want is something that can perform the inside-outside test for meshes. The simplest solution would be to use Trimesh's implementation which can be ran with Embree to accelerate ray queries.

I recommend you check out recent literature on neural implicit representations if you want more alternatives. Your problem arises when one wants to learn 3D shapes using small neural networks; it is then necessary to sample points and their groundtruth attributes with respect to the mesh (signed distances or occupancies of points). Here's one example for SDFs written in CUDA. NVIDIA's Kaolin also has a CUDA kernel for this IIRC.

For more troublesome meshes, you can also use the generalized winding number, which has an implementation in libigl but I think their code is CPU-only.

Answer 2

I have a few suggestions:

1. Partition the volume by using tetrahedra within the mesh, and outside of it (in the cube). Set the probability to sample each tetrahedron to its volume divided by the inside/outside volume of the mesh. Sample a tetrahedron based on the above probability, then sample a point (uniformly) within the chosen tetrahedron.

2. Discretize your mesh to a grid, and then use a filling algorithm for the inside/outside. Keep arrays of the inside/outside cells and sample those randomly. Compared to (1) this introduces discretization error.

3. Pick a point uniformly in the cube, then shoot a ray in any direction and if it intersect the mesh an even number of times then it is outside, otherwise it is inside.

If the mesh is convex (or can be decomposed in convex pieces) then you can check plane half-space membership which allows an early out.

Answer 3

For a mesh that is not closed then, by definition, there is no interior or exterior, only points on the surface and points that are not on the surface.

So your first step is to make the hand a "Closed Concave Polyhedron" by closing any openings it has. This can be done relatively simply by defining a plane where the hand is open. (such as at the wrist)

With that done your first test is to determine if a point is on the hand side of the plane or the non hand side of the plane. ( A more generic solution would be to require the polyhedron to be closed and solve the closure part as a separate problem). It sounds like this has already been done for you with the bounding box that the hand lies inside. If that is the case then your first step is to determine if the point is inside the bound box or outside the bounding box. If it is outside the bounding box you are done. If it is inside then you must now check to see if it is inside the hand.

Note: If you don't close the polyhedron in some way, then there is no algorithm that can reliably determine interior/exterior. This is one of the things that lightxbulb was eluding to with the first suggestion. For example, I have taken biology classes that consider your entire digestive track to be "outside" your body.

A very common and fast method to determine if a point is inside a concave polyhedron is called ray casting. (suggestion 3 from lightxbulb) Using this technique you pick a random point usually outside the enclosed area, I would recommend picking a point outside the unit cube since you know for certain that your are starting outside the mesh.

The point your are testing and the random point you picked can be used to form a line. Do not use a line that is infinitely long, instead your line has a start (the point outside the mesh) and an end (the point you are testing)

Now you just brute force test every triangle in the mesh to see if they intersect with the line. Along the way you are counting the number of intersections that occur. If your point is inside the mesh then the line will pass through an odd number of triangles if your point is outside the mesh then your line will pass through an even number of points.

I recommend drawing simple hand shape on a piece of paper, picking the two points, draw the line then count the intersections with the hand. This should make it much more clear why this works.

If you do not close the polyhedron then you can get unlucky and there will be a line that can get inside the mesh without passing through it and this algorithm will fail. So one of the "triangles" you must test against is the plane that closes the mesh and it must be counted as a pass through a triangle or you could end up with false positive/negative.