1
$\begingroup$

This question is in the context of computer graphics. We have a scene with $n$ triangles and a ray. We want to find if the ray intersects any triangle and get the closest one.

There is a datastructure called Bounding Volume Hierachy (BVH) which groups triangles and fits a bounding volume (e.g. AABBs - axis-aligned bounding boxes) around it. The idea is that if the ray does not intersect the bounding volume, it does not intersect any of the contained triangles / other bounding volumes.

Now assume a BVH with AABB bounding volumes and a scene of $n$ triangles is given. You can spend arbitrary much time for constructing the BVH, but you don't know which rays will come.

What is the worst case time complexity for intersecting a ray with such a BVH? What would a worst case scene look like?

edit: What is the worst case time complexity if triangles may not cross each other?

I thought of something like the following, where the bounding volumes intersect with themselves a lot (think of a recursive definition where the scene is continued to the center).

enter image description here

$\endgroup$
2
$\begingroup$

Worst time complexity is $O(n)$: If all triangles are identical the bounding boxes are the same as well and every triangle needs to be intersected.

Btw.: The triangles do not need to be identical for the bounding boxes to be the same. The result is still $O(n)$ in that case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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