Octrees are your friends
After some painstaking debugging (I guess every programmer can start a post like this), I got my Sparse Voxel Octree-based raycaster working. It’s still all CPU-based, to keep things simple for now. As you can see from the following false color images, the efficient skipping of empty space results in a massive reduction of traversal steps which need to be taken, with the most steps concentrating around the model edges (the just missed-rays).
These images were generated with a full octree (so every leaf node maps to exactly one voxel). Note that the blocky structures on the right part of the images are not compression artifacts, but a result of the division into octree nodes – these will be smaller on higher voxel grid resolutions. I plan on doing some resolution-based statistics during the next week, so I can compare ray hits / execution time / etc.
Unfortunately, there’s still some nasty performance bugs plaguing me from taking this to the next level: When you’re working with massive datasets like these, the way you store. refer to and access data is important. Shifting some variables between loops or storing them in a different way can make a day/night difference on execution time. It’s time for me to dive deeper into some profiling tools and get a good statistics framework in place, so I can easily compare implementations and techniques in the future – and get to know more of the ins and outs when dealing with voxel structures along the way.
Got some good tips for basic code profiling and rooting out performance issues? Feel free to leave them in the comments. I’ll be publishing the code for my iterative octree traversal strategy soon.