Voxel Iteration

2 minute read

Given my poor 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.

grid iteration

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.