Recursive Subdivision of AABBs in AirplaneMode
This project was inspired by Wrighter on the GP discord. He does all sorts of cool stuff that I really dig, but when he described the concept of this algorithm to me and showed off some results, I decided that I wanted to try to do something with it myself. The results can be really impressive for as simple as you will see that it is. I implemented this between Christmas and New Years, in my CPU pathtracer, AirplaneMode ( so named because is an easy project to work on pretty much anywhere, all it requires is a computer with a C++ compiler ).
AirplaneMode operates using explicit ray-primitive tests, and has a simple multithreaded structure which renders a pathtraced image in tiles. I added some code to do intersection with axis-aligned bounding box primitives, so that I could use this as the basis for setting up the recursive subdivision. This is a cool primitive, very easy to use, because you specify it as a set of three minimums and a set of three maximums, which define a range on each axis where it exists.
The Recursive Subdivision Algorithm
If you're familiar with recursion, the algorithm is very simple. There is a function, which spawns more calls to itself, until it reaches some termination condition. In this case, it is a random number which controls this termination, and each recursive step is used to split up the AABB under consideration. In pseudocode:
// Initialize the parent AABB - this is the bounding volume for all AABBs that follow
vec3 minsInitial( -0.5, -0.5, -0.5 ), maxsInitial( 0.5, 0.5, 0.5 );
void recursiveSplit ( vec3 min, vec3 max ) {
if ( rng() < threshold ) {
// create an AABB primitive for the renderer to use, with bounds min and max
} else {
// pick an axis - split the AABB on that axis, and recurse with each piece
recursiveSplit( min, middle );
recursiveSplit( middle, max );
}
}
// the initial call to the recursive function
recursiveSplit( minsInitial, maxsInitial );
The first step is to define the outer bounds of your recusively subdivided structure. This set of mins and maxs define the bounds of the structure that contains all of the further split primitives, a sort of 'parent node', if you think about it in BVH terms. Entering the function for the first time, some random number is generated, which is compared against a threshold to determine the exit condition. You might add in this branch another RNG check to see if you draw or don't draw, so that some of the cubes show up as empty and the bounding volume doesn't show up as 100% full. Assuming that this action is not taken on the first call, you enter the recursive call part of the function. This can do a number of things - in the simplest implementation, you could just have it split the AABB in half on some axis, x, y or z, and call the function again on either half. I experimented with splitting it irregularly, instead of evenly half and half, and with using more than one split, where there would be more than two branching recursive calls.
It really ends up being remarkably simple - there is a little bit more to the split logic, as you have to split the selected axis and maintain the min and max property of the two arguments. You probably want to include some logic in the threshold check to also see if the AABB is below some minimum size, and terminate under that condition as well.
I messed around with passing an object containing a stateful RNG as an argument as part of the recursive call, so that you could do deterministic subtress, creating the same behavior in multiple splits downstream, but had limited success with this - I want to revisit this, because I think that having some repeats inside of the pattern would be cool. I have since thought more about this, and it may make more sense to produce it once and then manually repeat it by creating the primitves in translated locations along some axis.
I tried a number of different scene layouts, some that held just the subdivided AABB, some that had some mirrored spheres sprinkled around or put in the shape of a tetrahedron surrounding the box. These are completely arbitrary, just some logic to create a scene to test rays against.
Due to the airflow in my apartment being so poor, I've got to leave the windows open - during the winter it gets a little chilly, but this comes with some positives, as well. I left my desktop near the window, with 16 threads under full load I was maintaining mid 20's to low 30's C core temperatures. I let it run for several days, and generated a few hundred outputs - some of which are shown on this page.
At some point, I'll probably come back to this project and add more primitives. It's been a good justification for writing my own templated vector library, which is a good exersize, to make sure you understand all the constituent pieces of the math required to perform these pathtracing calculations. I think this further reinforces the purpose of the project, as a learning exercise, to help internalize the pathtracing algorithm.
I've been thinking more about doing postprocessing on projects, things like dithering, or ways to make use of the font glyph collection that I've amassed. This renderer is 100% CPU based, with no interaction with the GPU, so all aspects of the process from end to end can be fiddled with as much as you want, structured however you feel makes sense. Keeping depth and normal buffers would be potentially useful for denoising efforts or else some cool effects like depth-dependent blur-based fake DoF.