2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by sample points inside and outside the mesh? Just random points and determine if they are inside/outside? And by "mesh" are you referring to a closed manifold that has a well defined "interior"? $\endgroup$ – pmw1234 Aug 31 at 16:08
  • $\begingroup$ Sorry for the late response. Yes, sample points uniformly or randomly outside and inside the mesh surface. By mesh I mean, surface(for eg. hand mesh, which is not watertight or not closed). $\endgroup$ – akes Sep 9 at 10:14
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for the late reply! Thank you @Hubble for your input. SDFs example helped me. But in my case meshes are not watertight or not closed. So, would you have any suggestions to convert them into watertight or closed meshes? $\endgroup$ – akes Sep 9 at 10:17
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I followed a similar approach. $\endgroup$ – akes Sep 9 at 10:18
  • $\begingroup$ Please accept the answer so that others don't spend a bunch of time writing a more explicit response only to discover a "thank you" $\endgroup$ – pmw1234 Sep 10 at 14:37
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.