Efficient line segment-triangle intersection

Question

I have a collection of triangles that compose an arbitrary geometry (read from an OFF file). Each triangle is defined by three vertexes, which are 3D points. I have an observation point, and I want to remove from the object all those vertexes that are not visible, meaning that the segment line that joins the observation point and the vertex does not intersect with any triangle.

It is important to note that the number of vertexes and triangles in a single object is in the other of 10^4. A simple approach will be to follow [1] accepted answer, which uses the signed volumes. I have implemented it, but it includes two nested for loops: for each vertex, I need to check if the line to the observation point intersects with ANY of the triangles. Of course, I break the look when it intersects with one, but it still leads to 192M calls to the signed volume function.

Some efficient algorithms [2] assume an infinite line, not a line segment, which leads to the deletion of the vertex even if the intersection is with a further away triangle. Any ideas on how to solve this efficiently?

[1] Intersection between line and triangle in 3D

[2] Möller and Trumbore, « Fast, Minimum Storage Ray-Triangle Intersection », Journal of Graphics Tools, vol. 2,‎ 1997, p. 21–28

Answer 1

Your problem statement is literally a ray-tracing problem: find if a bunch of points are occluded by the geometry or not. Therefore you can apply any ray-tracing tricks to make it fast; i.e. build some spacial index over your model and trace the rays using that spacial index. Some of the most common spacial indexes are BVH, BSP trees, or kd-trees.

If an approximate solution is good-enough, you can rasterize the geometry from the vantage point, and then test all your vertices against the generated Z-buffer.

Notice that either of these methods will filter the vertices (which is what you asked for). However, some triangles may be visible even if all their vertices are occluded. Those triangles will be removed too, even though they are visible. The rasterization method is easy to modify to filter triangles instead of vertices.

Answer 2

There are two question in one:

• efficiency
• segment-triangle intersection instead of ray-triangle intersection

efficiency

You can use a Bounding Volume Hierarchy (BVH)

The idea is to construct a hierarchy of boxes. Each box contains either other boxes or a bunch of triangles. The boxes are organized as a tree, and the root of the tree corresponds to a box that contains everything.

The function that computes an intersection works like that:

Compute the intersection between the ray and the box. If there is an intersection, open the box and recursively compute the intersections between the ray and what's in the box.

In more formal terms:

   Intersect_Ray_Node(Ray, node)
      if(Intersect_Ray_Box(Ray, node.box)) {
           if(node.is_leaf) {
              for each triangle t in node
                 Intersect_Ray_Triangle(Ray, t)
           } else {
              for each child in children(node)
                 Intersect_Ray_Node(Ray,child) 
           }
      }

Now, the "boxes" can be different things. The simplest thing to use is an AABB (Axis Aligned Bounding Box), that is, simply the minimum and maximum values of the coordinates of what's in the box.

There are several ways of implementing the tree. The most efficient implementations use no data structure and simply reorder the facets in the mesh, in such a way that facets that are in the same node have contiguous indices. Then you just need a couple of additional arrays, one that stores for each node the bounds of the boxes, and another one that indicate for each node how many triangles there are in the left child (then the number of triangles in the right child is implicit).

An implementation is available here, in my geogram library. Constructing the AABB is just a matter of sorting the triangles geometrically here and constructing the bouding box recursively.

I made also a ShaderToy implementation here (and a big comment at the end of BufferA contains the C++ source of my "MeshCompiler" that creates the AABB).

Note that if you want to be even more compact in memory, Pierre Terdiman proposed the Zero Byte AABB-tree (see here and here). The idea is to encode everything in the order of the triangles and the order of the vertices, based on the interesting remark that the bounds of the boxes are always coordinates of existing points in the mesh.

line segment versus ray

If what you want to intersect is a segment (with two vertices) instead of a ray (line that starts from a point and that extends towards infinity in a direction), you can do that with a simple modification of my answer here. Replace the last line of the intersect_triangle() function with:

return (det >= 1e-6 && t >= 0.0 && t <= 1.0 && u >= 0.0 && v >= 0.0 && (u+v) <= 1.0);

(test that t is between 0 and 1, which means that the point is inside the segment)