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,
Asked
Active
Viewed 445 times
3
-
@ET do you know there is mathoverflow.com – ACP Dec 23 '09 at 09:39
-
Are you doing raytracing? Are is it for something else? Do you really need all intersections, are only the intersection closest to the 'eye' for each specific ray? – Fortega Dec 23 '09 at 09:45
-
@Fortega I am not doing ray tracing. I just need get all intersections. It has nothing related to Graphic. Only in maths. – ET 0.618 Dec 23 '09 at 10:06
-
3This kind of question is perfect for Stack Overflow. It does not belong on mathoverflow.com. They would only direct you here. – Jason Orendorff Dec 23 '09 at 14:51
6 Answers
8
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
Adam Luchjenbroers
- 4,917
- 2
- 30
- 35
2
No. The reason is simple: there may actually be O(m * n) intersection points. just creating a list of them is O(n * m).
Ofri Raviv
- 24,375
- 3
- 55
- 55
-
This impies only the there can't be a better worst case complexity than O(nm). And if you allow the algorithm to output chunks of intersection points, even that doesn't hold true. – Gunther Piez Dec 23 '09 at 09:39
-
-
Because some rays and triangles have no intersection,I think the O(mn)is the worst. – ET 0.618 Dec 23 '09 at 09:58
-
It depends on what you mean by m and n. In raytracing, m would be the width of the viewpane, n the height. In that case, it can be optimized. – Fortega Dec 23 '09 at 10:09
-
2
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.
comingstorm
- 25,557
- 3
- 43
- 67
0
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.
Fortega
- 19,463
- 14
- 75
- 113
0
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).
PeterN
- 29
- 2