Axis-Aligned Bounding Tetrahedra and Octahedra for Ray Tracing Bounding Volume Hierarchies

Roman Wiche
Jul 21 · 11 min read

Motivation

AABT and AABO

Utah teapot enclosed by an ‘axis-aligned bounding rectangle’ in 2D which requires four planes
Utah teapot enclosed by an ‘axis-aligned bounding triangle’ in 2D which requires only three planes. Note the additional definition of the -(x+y) axis.
Utah teapot enclosed by an ‘axis-aligned bounding hexagon’, two overlapping axis-aligned bounding triangles, in 2D. The violet area visualizes the hexagon’s intersection area between both triangles. Note how the -min(x+y) and -max(x+y) allow decreasing the area of an ‘axis-aligned bounding rectangle’.

New Ray-AABT Intersection Algorithm

ALL RIGHT, BRAIN. IT’S ALL UP TO YOU. YOU HAVE TO COME UP WITH AN ALGORITHM. #THINKING RAPIDLY# EAT THE PUDDING, EAT THE PUDDING, EAT THE PUDDING. [https://frinkiac.com/img/S05E22/1096795.jpg]
First Iteration to the final Ray-AABT algorithm
Various cases of rays intersecting AABTs. Violet circles indicate parametric distance to the planes. Top-left: Rays originating outside of the AABT. Plane normals pointing toward the origin are max-candidates / pointing away from the origin are min-candidates. Top-right: Ray is originating inside the AABT. All planes are possible max-candidates, but we ignore negative values, and intersections in the origin (if a ray lies exactly on a plane) if the ray points into the tetrahedron. Note that tmin is 0. Bottom-left: AABT planes all point outside instead of inside. Our previous rules for min/max-candidates are inverted. Bottom-right: If any tmin candidate is negative, there is no way the ray can intersect the AABT.
Final Ray-AABT Intersection Algorithm

New Ray-AABO Intersection Algorithm

Listing 1 from Majercik et al. — State-of-the-art Ray-AABB algorithm used for BVH traversal by NVIDIA OptiX and Intel Embree
Ray-AABB test extended to a Ray-AABO test

Preliminary Results

Performance numbers of the previously discussed four BVH variants. For these measurements, three viewpoints were averaged for each mesh. I used Full-HD resolution and shot only primary rays with 16 samples per pixel for Teapot and Bunny, and four samples per pixel for Bedroom and Sibenik (my GPU couldn’t take so much more). Tests were conducted on NVIDIA GeForce GTX 970M with one thread per ray and thread group size 16x8x1.
Heatmap images rendered for the three bounding volume types. Top-Left: AABB. Top-Right: AABT. Bottom: AABO. Note how the AABO uses its diagonals to shrink the intersection area compared to AABB. Also, this shows perfectly that building AABTs naively into the previous AABB scheme definitely needs more refinement.

What to make out of all this?

Using a more versatile and intelligent BVH construction for AABT. Note the additional (-x+y) axis to allow for another diagonal split. While the root node bounding volume is most likely more loose than an AABB, we see tighter child volumes compared to AABB on the first level already. Also, note how the child volumes are not completely enclosed by the parent, but just ‘carve’ a volume out of the parent.

References

Roman Wiche

Written by

Passionate and mindful Software Engineer, explorer, and Broman

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade