I’ve implemented a stable version of the Amanatides and Woo algorithm for fast traversal of voxel grids and added some optimisations and support for non-square voxels.
After reading up on OpenMP, I couldn’t stand having a renderer which ran an inherently parallel algorithm on just one CPU. Every ray shot (we shoot rays to ‘pierce’ the data grid) is independent: the only thing the threads need is read access to the data structure which holds the grid information. Notice that I’ve just scratched the surface of parallel programming – lots of other optimisations are possible, more efficient data structures, etc … I’m sure my colleague Ares Lagae can advise me on that, since he’s a real C++ mastermind.
In the following tests I rendered images on a “first found” basis: we render the first nonempty voxel the ray encounters. This is a field of 256x256x256 colorfield / randomly-colored, slightly rectangular voxels. Thats a bit more than 16 million data points. Pretty impressive how a software-mode ray caster just burns through all that at a decent speed on such a high resolution (2000×2000) If you only work with dense objects, on a more human resolution (800×600) the rates can be considered real time – can’t wait for my GPU implementation!
Now that I have Amanatides/Woo(and thus a list of voxels the ray pierces), the need for marching is gone. Other interesting problems arise however:
- Our Amanatides/Woo algorithm should be incremental. We don’t want a huge list of voxels the ray pierces only to find out that we only need the first dozen of them.
- Empty space (sparseness) in the data set still has the biggest impact on performance. This is to be expected, since we don’t have a hierarchical data structure yet: every empty space is built out of thousands of empty voxels.
- The Amanatides/Woo algorithm also gives us the intersection points: we have to use these and trilinear interpolation to get the correct value for a point, and calculate the weights. Lots of manual tweaking here, depending on data set.
- Which brings us to my next point: I should get working on some drag/rotate UI.
Next step is to write an importer that can import some obj files, perform sampling on them to transform them into a voxel field. Let’s get rid of these stupid cubes!
Oh, and since I love publishing bloopers, this is what happens when you mess up your inner loop variables/invariables with OpenMP: