Hi
There are thousands of rays and triangles. We need get all the intersection points. If we use the normal two level loops,we need O(m*n) time complexity.Is there any way to low the time complexity fronm O(m*n) to O(m* logn) or O(logm*n)?
Best Regards,
No. The reason is simple: there may actually be O(m * n) intersection points. just creating a list of them is O(n * m).
You could group the triangles close to each other in cubes. Then for each ray: if it does not hit the cube, you are sure it does not hit one of the triangles inside the cube, so you can skip all the intersection calculations with those triangles for this specific ray.
What you probably want to look at is some kind of space partitioning technique. This allows you to quickly rule out collections of triangles.
I'd probably consider some approach using spherical Bounding Volume Hierarchies. But other techniques you may also want to look into are BSP (Binary Space Partitioning) Trees/ KD Trees or using an Octree
The classic solution to this problem is to build a KD tree based on the triangles, and query it for each ray. You can optimize the tree for the kind of queries you expect; if your rays are randomly distributed, the probability of a hit is proportional to the surface area in question.
Even if you aren't actually doing ray tracing, this problem is currently the main performance bottleneck for ray tracing, so you should probably check out the literature on it.