1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The solution in the link is to cast rays in a predefined viewing direction. That makes the problem 2D by projection. When you find which faces are hit, you return to 3D. (But you still need some acceleration technique such as a hierarchy of bounding boxes or gridding to speed-up the 2D search.) $\endgroup$
    – user1703
    May 24, 2023 at 14:47
  • $\begingroup$ @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) $\endgroup$
    – veggieg
    May 24, 2023 at 23:46
  • $\begingroup$ Any direction ! $\endgroup$
    – user1703
    May 25, 2023 at 7:26

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – veggieg
    May 25, 2023 at 2:26
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ With this algorithm you don't need an acceleration technique. The viewport of the rendering should be large to be more precise... $\endgroup$
    – Thomas
    May 24, 2023 at 16:48
  • $\begingroup$ If I understand correctly, this algorithm involves modification of shaders right? $\endgroup$
    – veggieg
    May 25, 2023 at 2:50
  • $\begingroup$ 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 $\endgroup$
    – Thomas
    May 25, 2023 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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