<p>If your triangles are all aligned to CW or CCW, the following algorithm works very quickly:</p>
<p>When rendering the entire mesh with an orthographic projection from one direction (e.g., in the X direction) with the depth test disabled, each triangle that spans an area is rasterized. Inside the fragment shader, the depth value and the triangle direction ('bool gl_FrontFacing') are obtained.
These two information can be stored as a node in a linked list in a SHADER_STORAGE_BUFFER per pixel.</p>
<p>After rendering, one has to sort the linked lists by the depth values of the pixels.</p>
<p>When iterating a single pixel list, one should get a frontface node immediately followed by a backface node.This is not only the case, it can appear, that two following face directions are same. This usually occurs at edges were two triangles share the same edge. This need to be corrected by deleting the following one:
For two consecutive frontface nodes, keep only the node that is closer to the camera. For two consecutive backface nodes, keep the node which is farther away and delete the other.</p>
<p>Now you can check your 3D point by first calculating the pixel position of the point. Now find out between which nodes of the pixel the point is located. (the depth value)</p>
<p>If the point is closer to the camera than the first node, it is outside.</p>
<p>If the point is further away than the last node, it is outside.</p>
<p>If the point is between a front and a back node, it is inside.</p>
<p>If the point is between a back node and a front node, it is outside.</p>
<p>Now that we understand how the algorithm works, I have to say that you have to do this three times: in the X direction, in the Y direction, and in the Z direction.</p>
<p>If the point is outside in all 3 direction tests, it is outside. Otherwise it is inside.</p>
<p><strong>Why do you have to do this three times?</strong> If a triangle is aligned in the X direction, it will not be rendered. If you do it in all (X, Y, Z) directions, each triangle will span an area in at least one of the three frames.</p>
<p>Additional positive effects:
After creating the three images (each with resolution_x * rosolution_y linked lists) as preprocessing step, you can check very fast if 3d Points are inside the mesh. The size of a single linked list within the image is very small (depends on the complexity of your mesh), so finding the correct position within the nodes can be very fast.</p>

CC BY-SA 4.0
2023-05-24T16:48:45.097Z
With this algorithm you don't need an acceleration technique. The viewport of the rendering should be large to be more precise...
Thomas
CC BY-SA 4.0
2023-05-25T02:50:14.537Z
If I understand correctly, this algorithm involves modification of shaders right?
veggieg
CC BY-SA 4.0
2023-05-25T05:46:55.367Z
To use shaders is the easiest way... But you can implement it without using the rendering pipeline. So for each triangle you would render, you can calculate the 3 vertex points on screen and use barycentric coordinates to interpolate the depth value for each pixel... The face direction can be calculated by the cross product
Thomas
CC BY-SA 4.0
2023-05-24T16:39:54.473Z
2023-05-24T21:02:02.787Z
2023-05-24T21:02:02.787Z
Thomas
<p>A very fast method is to convert the mesh to a signed distance field by computing a tight fighting bounding box for the mesh. Then subdividing that box into evenly sized &quot;voxels&quot; in the x,y,z direction. Finally compute the distance from the center of each voxel to the nearest point on the mesh. Points outside the mesh have values of 0 and points inside have values of 1.</p>
<p>To check a point, first check the point against the AABB, if it is inside, simply read the corresponding point from the SDF. It's value tells if the point is inside our outside the mesh.</p>
<p>Since a zero or a one is all we need the SDF can be reduced to a bit field which allows for fine grained SDF fields.</p>
<p>The biggest downside of this method is that generating the SDF can be slow. But a basic implementation is easy to write. (there are some nice compute shader techniques to speed this up considerably) And a very fine grained field can consume a lot of memory even if we are only using 1 bit for each voxel.</p>

CC BY-SA 4.0
2023-05-25T02:26:35.290Z
I tried this and it ran much faster than ray casting. The downsides are already mentioned above. Regards the precision problem, I tested and on my input mesh it's actually much better than I thought. If precision is important, maybe consider giving it a threshold.
veggieg
CC BY-SA 4.0
2023-05-24T21:51:18.110Z
2023-05-24T21:51:18.110Z
pmw1234
<p>Usually a ray casting algorithm is used to determine whether a point is indide or outside a mesh. But this algorithm is slow.
Is there any fast algorithm to do this check?
My input mesh is a triangular closed mesh.
This question has been previously asked here: <a href="https://stackoverflow.com/questions/6554313/algorithm-for-determining-whether-a-point-is-inside-a-3d-mesh">https://stackoverflow.com/questions/6554313/algorithm-for-determining-whether-a-point-is-inside-a-3d-mesh</a>
.
The author solved the problem, but I don't understand the solution he/she provided.</p>
<p>Update:
there's another method mentioned in <a href="https://www.reddit.com/r/Houdini/comments/u2co9i/the_most_efficient_way_to_test_if_a_point_is/" rel="nofollow noreferrer">https://www.reddit.com/r/Houdini/comments/u2co9i/the_most_efficient_way_to_test_if_a_point_is/</a>. The algorithm is to find a nearest point on mesh, let's call this nearest point B, and the point to test A. The algorithm simply tests the dot product of AB and the normal of B. However, this seems to only work with convex mesh. The algorithm should handle all different kinds of meshes.</p>

CC BY-SA 4.0
2023-05-24T23:46:09.883Z
@YvesDaoust I understand that  it's a projection.But what is the direction of the ray?(as far as I understand, if I wanna know whether point A is inside/outside, the origin of the ray is A, but the answer didn't mention the direction of the ray)
veggieg
<computational-geometry>
fast algorithm to check if a point is inside/outside mesh
veggieg
# fast algorithm to check if a point is inside/outside mesh

(Asked by: username_0 on 2023-05-24)

Usually a ray casting algorithm is used to determine whether a point is indide or outside a mesh. But this algorithm is slow.
Is there any fast algorithm to do this check?
My input mesh is a triangular closed mesh.
This question has been previously asked here: <https://stackoverflow.com/questions/6554313/algorithm-for-determining-whether-a-point-is-inside-a-3d-mesh>
.
The author solved the problem, but I don't understand the solution he/she provided.

Update:
there's another method mentioned in <https://www.reddit.com/r/Houdini/comments/u2co9i/the_most_efficient_way_to_test_if_a_point_is/>. The algorithm is to find a nearest point on mesh, let's call this nearest point B, and the point to test A. The algorithm simply tests the dot product of AB and the normal of B. However, this seems to only work with convex mesh. The algorithm should handle all different kinds of meshes.

**Tags:** computational-geometry

> **Comments:**
> **username_0**: @YvesDaoust I understand that  it's a projection.But what is the direction of the ray?(as far as I understand, if I wanna know whether point A is inside/outside, the origin of the ray is A, but the answer didn't mention the direction of the ray)  

---

## 2 answers

### Answer by username_2 on 2023-05-24. Score: 2

A very fast method is to convert the mesh to a signed distance field by computing a tight fighting bounding box for the mesh. Then subdividing that box into evenly sized "voxels" in the x,y,z direction. Finally compute the distance from the center of each voxel to the nearest point on the mesh. Points outside the mesh have values of 0 and points inside have values of 1.

To check a point, first check the point against the AABB, if it is inside, simply read the corresponding point from the SDF. It's value tells if the point is inside our outside the mesh.

Since a zero or a one is all we need the SDF can be reduced to a bit field which allows for fine grained SDF fields.

The biggest downside of this method is that generating the SDF can be slow. But a basic implementation is easy to write. (there are some nice compute shader techniques to speed this up considerably) And a very fine grained field can consume a lot of memory even if we are only using 1 bit for each voxel.

> **Comments:**
> **username_0**: I tried this and it ran much faster than ray casting. The downsides are already mentioned above. Regards the precision problem, I tested and on my input mesh it's actually much better than I thought. If precision is important, maybe consider giving it a threshold.  

---

### Answer by username_1 on 2023-05-24. Score: 1

If your triangles are all aligned to CW or CCW, the following algorithm works very quickly:

When rendering the entire mesh with an orthographic projection from one direction (e.g., in the X direction) with the depth test disabled, each triangle that spans an area is rasterized. Inside the fragment shader, the depth value and the triangle direction ('bool gl\_FrontFacing') are obtained.
These two information can be stored as a node in a linked list in a SHADER\_STORAGE\_BUFFER per pixel.

After rendering, one has to sort the linked lists by the depth values of the pixels.

When iterating a single pixel list, one should get a frontface node immediately followed by a backface node.This is not only the case, it can appear, that two following face directions are same. This usually occurs at edges were two triangles share the same edge. This need to be corrected by deleting the following one:
For two consecutive frontface nodes, keep only the node that is closer to the camera. For two consecutive backface nodes, keep the node which is farther away and delete the other.

Now you can check your 3D point by first calculating the pixel position of the point. Now find out between which nodes of the pixel the point is located. (the depth value)

If the point is closer to the camera than the first node, it is outside.

If the point is further away than the last node, it is outside.

If the point is between a front and a back node, it is inside.

If the point is between a back node and a front node, it is outside.

Now that we understand how the algorithm works, I have to say that you have to do this three times: in the X direction, in the Y direction, and in the Z direction.

If the point is outside in all 3 direction tests, it is outside. Otherwise it is inside.

**Why do you have to do this three times?** If a triangle is aligned in the X direction, it will not be rendered. If you do it in all (X, Y, Z) directions, each triangle will span an area in at least one of the three frames.

Additional positive effects:
After creating the three images (each with resolution\_x \* rosolution\_y linked lists) as preprocessing step, you can check very fast if 3d Points are inside the mesh. The size of a single linked list within the image is very small (depends on the complexity of your mesh), so finding the correct position within the nodes can be very fast.

> **Comments:**
> **username_1**: With this algorithm you don't need an acceleration technique. The viewport of the rendering should be large to be more precise...  
> **username_0**: If I understand correctly, this algorithm involves modification of shaders right?  
> **username_1**: To use shaders is the easiest way... But you can implement it without using the rendering pipeline. So for each triangle you would render, you can calculate the 3 vertex points on screen and use barycentric coordinates to interpolate the depth value for each pixel... The face direction can be calculated by the cross product  

---

