fast algorithm to check if a point is inside/outside mesh

Question

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.

Answer 1

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.

Answer 2

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.