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

11 min readJul 21, 2019

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. Usually, these volumes offer a trade-off between tight volumes and fast computation. Weghorst et al. define this simple relationship as:

where T is the total cost, b the number of times that the bounding volume is tested for intersection, B the cost of testing the bounding volume, i the number of times that the enclosed item is tested for intersection, and I the cost of testing the enclosed item for an intersection.

At the beginning of BVH research for ray tracing, few works were mentioning BVHs built upon volumes like OBBs. However, today, the AABB is the de-facto standard for BVHs in the context of ray tracing, and I’m not aware of any recent works questioning that. But is it the best fit for BVHs?

In this article, let us together wonder ‘what-if’ and have a look at two other, possibly competitive, bounding volumes: the Axis-Aligned-Bounding-Tetrahedron (AABT) and Axis-Aligned-Bounding-Octahedron (AABO).

AABT and AABO

This article is heavily inspired by the work from Bryan McNett. He wrote an excellent and inspiring article about AABT and AABO recently, presenting their possible use in real-time collision detection systems. So I thought hey, why not try this for ray tracing too? In the following, I’ll give a quick summary of what I think is important for this article, but I highly recommend checking out the source for it and where these original ideas are coming from.

Let us illustrate and work through the topics in 2D for better understanding. Later on, we’ll see that it’s trivial to extend this into 3D (I always wanted to say that!)

When we take a look at an AABB in 2D (an ‘axis-aligned bounding rectangle’), we see that it consists of four planes, axis-aligned to some coordinate system:

Utah teapot enclosed by an ‘axis-aligned bounding rectangle’ in 2D which requires four planes

The question is: Is there any way to enclose our object with less than four planes? If we could, this could mean a saving in space and maybe computation, too. And indeed, we can use three planes as an ‘axis-aligned bounding triangle’ to enclose our object:

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.

We could use arbitrary oriented axes, but using the coordinate systems main axes x, y, and a simple combination of -(x+y) allows for easy conversion between coordinate systems.

So it’s great we saved in 25% of space, however, at the same time, we most likely ended up with a more loose bounding volume (except for maybe an axis-aligned triangle object). To achieve a tighter bounding volume, we can extend the bounding volume with another triangle oriented in the opposite direction, essentially ending up with an ‘axis-aligned bounding hexagon’:

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’.

With this bounding volume, we can see that we’ll always be as tight as with an axis-aligned bounding rectangle in the worst-case, but may additionally have the chance to shrink the bounding volume further down with the two triangle hypotenuses.

But what was the point of decreasing the number of enclosing planes, just to increase them again, and ending up with six planes instead of rectangle’s four? Here is the deal: Assume we assemble the hexagon test from the two triangle tests. Then, if the ray does not intersect the first triangle, we can ignore the second triangle alltogether, and don’t even need to load it from memory. Just if the ray hits the first triangle, we need to test the second one, and even though this is arguably more expensive overall, we have a (most likely) tighter bounding volume. Wow.

Let us end this section by recognizing that the previous remarks extend into all higher dimensions. This means we need at least n+1 hyperplanes in the nth dimension (in 2D three hyperplanes, in 3D four hyperplanes) to enclose objects. Thus, our ‘axis-aligned bounding triangle’ and ‘axis-aligned bounding hexagon’ transform into a tetrahedron/AABT and octahedron/AABO in 3D, respectively.

New Ray-AABT Intersection Algorithm

We saw that we can save some space with AABT in contrast to AABB. Our hope now is to find a sufficiently fast Ray-AABT intersection algorithm to make up for the more loose bounding volume. This way, we might end up with a faster overall hierarchy.

Unfortunately for us, a quick google search shows us that there is not much on the table here. The best general ray-tetrahedra test I could find is the one from Christer Ericson. However, since the axis-aligned restriction may give us new possibilities, let’s see if we can come up with something ourselves.

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]

Since we’re dealing with a BVH traversal, we’re not only interested in a boolean hit result. Instead, we’d like to receive a hit range of our ray where the ray is intersecting an AABT (that is, the parametric distance tmin and tmax). This gives us more flexibility during the traversal (e.g., for culling nodes).

We already know how to compute the parametric distance of a ray to an axis-aligned plane. This is exactly what we do during a Ray-AABB intersection. Therefore, let’s start the algorithm off by computing the parametric distance of the ray to the four axis-aligned planes of the tetrahedron. This is very convenient because it fits in one float4 vector and we can compute it with just one vectorized subtraction and multiplication. The prerequisite here is that we have prepared a float4 ray origin and direction so that the w-component represents the -(x+y+z) axis. We can easily compute this sum of vector components by taking the dot product with a one-vector. So far, we got:

First Iteration to the final Ray-AABT algorithm

Now we already know that we have to extract tmin and tmax from two components in the vector t4, but we don’t know which ones yet. From what I got so far when drawing different cases of rays intersecting tetrahedra, it appears to me that it’s not as easy to select them as within the AABB test. Whereas in the AABB test you can choose between the min and max of one axis (where you can be certain that one is certainly the min and one is certainly the max), we can’t easily tell this for the tetrahedron from what I can see.

To get a better grasp which parametric distance might be a tmin and a tmax candidate, let’s take the location of the ray origin into consideration. One interesting thing to note is that with the AABT, all plane normals either point inside or outside of the tetrahedron. Say we have a tetrahedron where each axis-aligned plane normal points towards the inside. Then, if our ray is originating on the side of a plane normal, this plane is a tmax candidate. Otherwise, it is a tmin candidate, because the ray has to intersect the backside of the plane at some point if it is to enter the tetrahedron. If all plane normals point outside of the tetrahedron, the opposite holds:

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.

The only exception which needs more special handling is a ray originating exactly on a plane, which also requires to check the direction.

We use this knowledge to create an int4 mask which will store if the corresponding vector component is a tmin/tmax candidate. By multiplying this mask with all our candidates, we receive one vector containing the candidates for tmin/tmax. Finally, just like in the AABB test, we must select the min/max components of the vectors.

The only thing left to check is if any of the tmin candidates are negative. Then, we don’t hit the tetrahedron. Translating all these things into code:

Final Ray-AABT Intersection Algorithm

The selection of tmin and tmax plus the mask handling is more involved than I’d like, but hey, this is the best I can come up with right now. Certainly, there is something better out there. Although the whole algorithm looks more tangled than the AABB test due to all the conditional moves, we shouldn’t forget that it has the advantage of just using one vector register input representing the tetrahedron’s planes compared to AABB’s two.

New Ray-AABO Intersection Algorithm

Regarding the Ray-AABO test, I generally see two ways going forward:

Assemble the Ray-AABO test from two Ray-AABT tests as explained in the previous sections. Since we already have a working Ray-AABT test, this is straight-forward, and I won’t describe this path any further (just mind the correct update of tmin and tmax and cull if required).
Come up with a new ‘atomic’ Ray-AABO test which tests the AABO ‘at-once’. Let’s see how we could do that.

The state-of-the-art Ray-AABB algorithm which is also used by NVIDIA OptiX and Intel Embree is described by Majercik et al. I’ve also written a blog post about it. For convenience, here is the listing again:

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

If we take a closer look at it, we can see pretty quickly that it is very easy to extend this to a Ray-AABO test. Like in the Ray-AABT test, we achieve this by using the fourth w-component of the ray and plane vectors to compute the parametric distance for the two additional planes on the -(x+y+z) axis. Then, we end up with:

Ray-AABB test extended to a Ray-AABO test

Besides one additional min/max operation in selecting the min/max component of tmin/tmax in line 7, it is pretty much the same algorithm just using vec4 instead of vec3. So we got two additional restricting planes, without any substantial cost. The prerequisite here is that we transformed the ray origin’s and direction’s w-component correctly once before, like in the Ray-AABT test.

Preliminary Results

Let’s find out how all these things we’ve been going through translate into a ray tracing system.

First, we have to update our way of building the BVH, and for the beginning, we will do this very naively. When building the bounding volumes, we not only have to compute the min and max but also -min(x+y+z) and -max(x+y+z) for our additional axis, so that we can use it in our node planes later on. This will take a bit of extra time when building the hierarchy, but if we’re dealing with static BVHs it shouldn’t bother us too much. There are a lot more possibilities for improvement (more on this at the end), but for now, let’s leave it like that to not overcomplicate things.

Second, it is important that we save a float4 origin and direction within a ray instead of float3 (if that is not already the case). Then, after the last transform operation on the ray (e.g., after it’s transformed into local space of an object), we have to compute the w-component of the origin and direction one time as two dot products, that is -dot(orig, 1) and -dot(dir, 1), respectively.

Now that we’re done with this arrangement, we can trace our rays through BVHs built from AABBs, AABTs, and AABOs. We will create some renderings with each BVH variant and profile them against various test meshes from Morgan McGuire’s Computer Graphics Archive. Here are the numbers and some heatmap rendering eye-candy:

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?

Good question. What I can say is this:

Yes, in my specific ray tracing system and setup, AABOs and AABBs match pretty much. Which one wins in which situation seems to depend on the scene and viewpoint. AABOs can shrink the volume further down, but I didn’t manage to pack pointers to next nodes / leaf node information into AABO nodes compared to AABBs, so there was some additional reading cost.
The ‘atomic’ AABO test is to prefer against the assembled version from two AABT tests (though this might change with a better AABT intersection).
When using a naive approach to replace AABBs with AABTs, they definitely perform worse (which is not specifically surprising, but still worth mentioning).
How these results translate into different layouts of BVHs, variations, hardware, and other systems, I don’t have a clue to be honest. After all, I called this section preliminary results for a reason, and this is not an all encompassing scientific paper, but a blog post. Still, I think it is fair to say that AABOs are definitely noteworthy alternatives to AABBs.

To get a better grasp of what AABTs might be capable of when using a more intelligent BVH construction, there should be a focus on:

Taking the fourth axis into cutting consideration
Being able to switch between (possibly) four diagonal axes to get differently oriented tetrahedrons on each hierarchy level
An alternative or extension to the Surface Area Heuristic, since we will deal with bounding volumes which do not enclose each other completely anymore, but rather child volumes which ‘carve’ volumes out of the parent volume. My dear colleague David Kuri and I already talked about this general idea some time ago and called it the ‘Bounding Volume Carving Hierarchy’. The following illustrations show the potential behind this concept:

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.

Now call me crazy (rightfully so), but I think that with these additions, the AABT is the most interesting route to investigate further. This will be super exciting and may very well be a part 2 article.

Besides a second part, there is also a lot to look forward to from Bryan McNett. In addition to his work on AABT and AABO, he wrote another interesting article on HexPrism.

We’re living in exciting times.

Cheers, Broman

References

(in order of appearance)