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.