Take the 2-minute tour ×


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,

share|improve this question

closed as off topic by Greg Kuperberg, Reid Barton, Anton Geraschenko Dec 23 '09 at 19:08


StackOverflow would be a right place for computer science questions. –  Ilya Nikokoshev Dec 23 '09 at 10:39
I don't know -- algorithmic geometry seems to have one foot in mathematics. I have a different issue with the question: I feel that it is very vaguely worded. –  Pete L. Clark Dec 23 '09 at 11:38
I think the subject matter is OK and, piecing together all the clues, I think I know what the question must be. That said, I shouldn't have to piece together clues. ET, can you confirm that the following is correct: we have m triangles and n rays in three dimensional space. I am not sure whether or not the rays all pass through the origin. We wish to find every pair (ray, triangle), so that the ray and triangle meet. There is an obvious O(mn) algorithm -- check each pair. Can we do better? –  David Speyer Dec 23 '09 at 14:38
My vote is to ask at StackOverflow. –  Greg Kuperberg Dec 23 '09 at 16:45
In general, you cannot do better, because there may be mn intersections. –  Reid Barton Dec 23 '09 at 17:32

1 Answer 1

This is a basic question in ray tracing. Do a Google search on "ray tracing acceleration data structures," or pick up a copy of the PBRT book by Pharr & Humphreys. Classic examples of acceleration structures include the kd-tree and bounding volume hierarchy (BVH). Although kd-trees are theoretically optimal in many situations, actual performance depends largely on the distribution of triangle sizes and locations. You also need to take into account the complexity of building the structure -- building a kd-tree nominally takes O(n log n) time in the number of triangles, but it is difficult to make incremental updates (e.g., for dynamic geometry). A more modern acceleration structure is the BIH (bounding interval hierarchy), which is useful for dynamic scenes.

(Also, a resource more specific to your problem than stackoverflow.net are the forums on ompf.org)

share|improve this answer
