Noteworthy Alternatives to Axis-Aligned Bounding Boxes?

Motivation

Today, the Bounding Volume Hierarchy (BVH) and it’s variations are the most common acceleration structures for ray tracing. During the last decades, the BVH often proved superior to the likes of uniform grids, kd-trees, BSP-trees, etc. Consequently, it is employed in the world’s most sophisticated ray tracers, like NVIDIA OptiX and Intel Embree.

In all cases that I’m aware of, the BVH is built upon Axis-Aligned Bounding Boxes (AABBs) as bounding volumes. The reasoning behind this is the simplicity to build the hierarchy, fast intersection testing with rays, and an often sufficiently tight enough bounding volume around objects. Besides AABBs, there are many other bounding volumes, like bounding spheres, Oriented-Bounding-Boxes (OBBs), and more.


Rendering, physics, and AI applications benefit from fast ray-box intersection tests. For me, ray-axis-aligned-bounding-box (AABB) intersection tests are of particular interest, because Bounding Volume Hierarchies (BVHs) are commonly built with AABBs. BVHs, in turn, are the most common acceleration structures for ray tracing. To traverse BVHs efficiently, a fast algorithm to judge whether a ray is piercing an AABB is essential. This way, the algorithm determines whether primitives or child nodes need to be tested or discarded because the ray does or does not hit the parent AABB.

There are a few algorithms which solve the ray-AABB intersection problem. Majercik et al. give an excellent overview of existing ray-box tests. Which algorithm to choose amongst these, is usually dependent on a few…


Image for post
Image for post
Acceleration structure heat map visualization of the Stanford Dragon

We use acceleration data structures for various computer science topics. For example, we use a kd-tree to perform nearest neighbor searches or multidimensional key queries. Accelerators for ray tracing applications enable the fast selection of potential ray-triangle intersections. But why is this necessary? What about a brute-force solution?

Let’s consider the following example: We’d like to render a high polygon mesh with one million triangles. …


Motivation
First of all, what does SIMD actually mean? I certainly haven’t heard of it until some years into my computer science studies. It is an acronym for Single instruction, multiple data (SIMD) and is related to the architecture of CPU’s and GPU’s. …

About

Roman Wiche

Passionate and mindful Software Engineer, explorer, and Broman

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store