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…


Motivation

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.

Most common algorithm

There are a few algorithms which solve the ray-AABB intersection problem…


Acceleration structure heat map visualization of the Stanford Dragon

Motivation

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. Plus, we’d like to render it in Full-HD (1920x1080 pixels). Without accelerators, we’d have to compute one million intersections for each ray. So if we’d shoot only one ray per pixel, we’d end up with…


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. Another acronym often appearing alongside SIMD is Streaming SIMD Extensions (SSE). You can read theoretical details about it in various publications and all over the internet, but I’ll try to frame it in a simplified, practical fashion: Basically for you as a coder, SIMD allows to perform four operations (reading/writing/calculating) for the price of one instruction. The cost…

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