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(mn) time complexity.Is there any way to low the time complexity fronm O(mn) to O(m* logn) or O(logm*n)?
Best Regards,
Thousands of rays intersections with Triangles in 3D space
482 Views Asked by ET 0.618 At
6
There are 6 best solutions below
5
On
No. The reason is simple: there may actually be O(m * n) intersection points. just creating a list of them is O(n * m).
0
On
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.
0
On
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
0
On
Obviously, if you must iterate and compute intersection between a ray and each triangle then the complexity is O(mn). However, if you are interested in only those triangles that may potentially intersect with particular ray, you can try a variant of a space partitioning grid, for example a Hierarchical Quadtree Grid (http://graphics.stanford.edu/courses/cs468-06-fall/Slides/steve.pdf).
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.