Jason Gedge

Voxel Iteration

Posted on January 20, 2014

Given my poor man’s implementation of intersection testing, I realized it was time to do a proper implementation of a grid-based iterator. I’m not going to dive into great detail about this algorithm because this post exists to point to the GitHub repository with my code, so I’ll summarize the idea of the algorithm.

Given a ray, source + t\*direction, you initialize the iterator with the value of t required to get to the next voxel along each axis. For every iteration, you take the smallest t value and iterate the voxel index along that axis. For example, if we’re at <5, -2, 4> and the smallest value for t is along the y-axis, we’ll move to <5, -1, 4> or <5, -3, 4>, based on which direction the ray is moving along the y-axis. We then update the value of t to move to the next voxel along the y-axis.


Iterating over a 2D grid.

For a better description of this algorithm, check out this paper. I’ve created a GitHub repository to show what this looks like in code. This repository contains the iterator itself, along with a small Qt program to visualize the iteration.

comments powered by Disqus