Allow me to describe the situation. I have a 3D triangular mesh with N triangles (approx. 1e5 triangles) and M lines (in the same order of magnitude as the triangles but not necessary the same number).
Now, the maths behind computing the intersection of a line and a triangle are no issue, they are pretty straight ahead and literature on such fast methods is wide. For the sake of this question, let's assume that the employed method consists on computing the intersection with the triangle plane (assuming it exists) and then checking if the intersection does actually lie on the triangle.
In this scenario, computing all line-triangle intersections will require MN computations of intersections and then MN checks of the intersections to be inside the triangles, where each of this steps involves at least 2 dot products. This is all just to express that brute forcing the intersections, then brute forcing the inside-the-triangle-checking might be very time consuming as the number of both triangles and lines increases.
I am quite sure there has to be some clever trick to select the best triangles to intersect with each line, perhaps something like a Bounding Box Hierarchy that selects the best candidates for each line, so that the number of intersections to be computed is severely reduced and hence the overall execution time is drastically reduced. Does anyone know about this? I am quite versed in geometry itself but not much in this topics.
Regarding what I have been using and such for this line-triangle intersection, I have been using both Trimesh and Open3d python libraries. Trimesh has actually been great in terms of returning data as I need it and with appropriate precision but it is really slow as the numbers rise, and Open3d, while being faster, does not return exactly the same values as Trimesh (meaning I have no real control over the precision) and seems to be returning the closest intersection that it finds, which is not exactly what I need. If anyone knows how to tune those, I'll be glad to listen!
In my particular case, the scene is static. Not sure if that helps with anything, but just to let you know. I am using macOS Sonoma 14.2.1 on an M1 Pro chip with 16GB of RAM.
Thank you in advance for your time!
PS: some more insight into my actual problem. I am working on a geometric processing task where I need to compute a bunch of line-triangle intersections. I do not need the first intersection or the closest one to the point on the line, but actually the one with the lowest parametric value, i.e., the lowest l such that P + l V is in a triangle. One could do a double loop running through lines and then through triangles to check all possible intersections but that is really slow, so I want, given a line, to discriminate triangles that would be unreasonable to test if we were to see the geometry, in order to minimice the number of intersections to compute. Does anyone know about literature on this topic?