Intersection test for ray tracing

[Negatron]

I know that intersection tests can typically (for hit detection in games) be computed in log n time with reasonable accuracy, but there is a problem that I see with using hierarchical bounding volumes in ray tracing.

For example, a ray may intersect a bounding volume however due to the shape of the contained object it may turn out that the object has not been intersected. For hit detection in games this typically doesn't matter and a hit can be assumed, but a ray needs to actually intersect a low level primitive to draw a pixel.

When the test is performed in a bounding volume and it turns out no intersection took place the algorithm would have to back-track, and I'm not sure this complication would still retain log n properties.

So how are intersection tests performed where such precision is required and is log n still achieved? I know I have to do my own homework on the implementation but I'm just interested in the vague idea and maybe the name of the algorithm, thanks.

 

[lofgran]

Thank you for bringing up this interesting point about using hierarchical bounding volumes in ray tracing. You are correct in your observation that there can be cases where a ray may intersect a bounding volume, but not the actual object contained within it. This can lead to complications in the algorithm and potentially affect its overall efficiency.

In cases where precision is required, such as in scientific simulations or medical imaging, a different approach is often used for intersection tests. One commonly used method is called the "ray-primitive intersection" algorithm, which involves testing the ray against each individual primitive in the scene rather than just the bounding volumes.

This approach does not rely on hierarchical bounding volumes, but instead uses a data structure known as a bounding volume hierarchy (BVH) to organize the primitives in the scene. This data structure allows for efficient traversal and testing of the ray against the individual primitives, while still achieving a logarithmic time complexity.

There are also other algorithms and techniques used for intersection testing, such as the "ray-box intersection" and "ray-triangle intersection" methods, which are optimized for specific types of primitives. These can also be combined with BVHs for even better performance.

In summary, while hierarchical bounding volumes are a useful tool for hit detection in games, they may not be suitable for cases where precision is crucial. In these situations, other algorithms and data structures are used to ensure accurate and efficient intersection testing. I hope this helps answer your question and provides some insight into the broader topic of intersection testing.