<p>I have a few suggestions:</p>
<ol>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ol>
<p>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.</p>

CC BY-SA 4.0
2020-08-29T07:46:21.940Z
2020-08-29T08:17:48.747Z
2020-08-29T08:17:48.747Z
lightxbulb
<p>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.</p>
<p>So your first step is to make the hand a &quot;Closed Concave Polyhedron&quot; 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)</p>
<p>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.</p>
<p>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 &quot;outside&quot; your body.</p>
<p>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.</p>
<p>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)</p>
<p>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.</p>
<p>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.</p>
<p>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 &quot;triangles&quot; 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.</p>

CC BY-SA 4.0
2020-09-10T13:33:43.793Z
2020-09-10T13:33:43.793Z
pmw1234
<p>What you want is something that can perform the <a href="https://en.wikipedia.org/wiki/Point_in_polygon" rel="nofollow noreferrer">inside-outside test</a> for meshes. The simplest solution would be to use <a href="https://github.com/mikedh/trimesh" rel="nofollow noreferrer">Trimesh</a>'s implementation which can be ran with Embree to accelerate ray queries.</p>
<p>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). <a href="https://github.com/zekunhao1995/DualSDF/blob/master/extensions/mesh2sdf2_cuda/mesh2sdf_kernel.cu" rel="nofollow noreferrer">Here</a>'s one example for SDFs written in CUDA. NVIDIA's <a href="https://github.com/NVIDIAGameWorks/kaolin" rel="nofollow noreferrer">Kaolin</a> also has a CUDA kernel for this IIRC.</p>
<p>For more troublesome meshes, you can also use the <a href="https://www.dgp.toronto.edu/projects/fast-winding-numbers/" rel="nofollow noreferrer">generalized winding number</a>, which has an implementation in <a href="https://github.com/libigl/libigl" rel="nofollow noreferrer">libigl</a> but I think their code is CPU-only.</p>

CC BY-SA 4.0
2020-09-09T10:17:47.090Z
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?
akes
CC BY-SA 4.0
2020-08-28T22:54:12.950Z
2020-08-28T22:54:12.950Z
Hubble
<p>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?</p>

CC BY-SA 4.0
2020-08-31T16:08:25.747Z
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"?
pmw1234
CC BY-SA 4.0
2020-09-09T10:14:33.293Z
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).
akes
<3d><mesh><sampling>
How to Sample 3D Points Outside and Inside the Mesh Surface
akes
# How to Sample 3D Points Outside and Inside the Mesh Surface

(Asked by: username_0 on 2020-08-28)

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?

**Tags:** 3d, mesh, sampling

> **Comments:**
> **username_1**: 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"?  
> **username_0**: 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).  

---

## 3 answers

### Answer by username_3 on 2020-08-28. Score: 4 | Accepted answer

What you want is something that can perform the [inside-outside test](https://en.wikipedia.org/wiki/Point_in_polygon) for meshes. The simplest solution would be to use [Trimesh](https://github.com/mikedh/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](https://github.com/zekunhao1995/DualSDF/blob/master/extensions/mesh2sdf2_cuda/mesh2sdf_kernel.cu)'s one example for SDFs written in CUDA. NVIDIA's [Kaolin](https://github.com/NVIDIAGameWorks/kaolin) also has a CUDA kernel for this IIRC.

For more troublesome meshes, you can also use the [generalized winding number](https://www.dgp.toronto.edu/projects/fast-winding-numbers/), which has an implementation in [libigl](https://github.com/libigl/libigl) but I think their code is CPU-only.

> **Comments:**
> **username_0**: Sorry for the late reply! Thank you @username_3 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?  

---

### Answer by username_2 on 2020-08-29. Score: 4

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 by username_1 on 2020-09-10. Score: 1

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 username_2 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 username_2) 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.


---

