Efficient line segment-triangle intersection-CodePudding

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

CodePudding user response：

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.