0
$\begingroup$

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,

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ StackOverflow would be a right place for computer science questions. $\endgroup$
    – Ilya Nikokoshev
    Dec 23, 2009 at 10:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Pete L. Clark
    Dec 23, 2009 at 11:38
  • 1
    $\begingroup$ 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? $\endgroup$
    – David E Speyer
    Dec 23, 2009 at 14:38
  • 1
    $\begingroup$ My vote is to ask at StackOverflow. $\endgroup$
    – Greg Kuperberg
    Dec 23, 2009 at 16:45
  • 1
    $\begingroup$ In general, you cannot do better, because there may be mn intersections. $\endgroup$
    – Reid Barton
    Dec 23, 2009 at 17:32

1 Answer 1

Reset to default
5
$\begingroup$

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)

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.