Amanatides and Wu's “A Fast Voxel Traversal..” http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf​ is great for stepping through a grid along a ray, however it only works for infinitely thin rays – I'm trying to sweep a circle through a grid, and I can't find any similar algorithm for swept-circles.

AFAICT there should be some way to adapt Amanatides+Wu so that it visits all the grid cells touched by a “fat ray”. On paper it seems like it should be sufficient to cast two rays and then visit all cells between them, however I'm unable to get this to work nicely.

If anyone knows of an algorithm for this, or what search terms I should be using, please let me know! Thanks. : )

(I'm also trying to figure out a related problem: imagine a set of squares arranged in a grid, where the grid spacing is less than the square size (ie so that each square overlaps the squares in the 3x3 neighbourhood around it). I'd like to cast a ray through this grid and visit the squares in the order that the ray hits them: this should be similar to Amanatides+Wu (ie the ray intersects the squares at a regular interval based on the ray slope), except with an offset. However I'm unable to get this working either! A related problem might be “given a line segment in a grid, find all grid nodes which are within some radius r of the line segment”).

Update: I found what I was looking for, it's called “Coherent Grid Traversal”, from Wald et al “Ray Tracing Animated Scenes using Coherent Grid Traversal”.

If anyone has any insight into casting a ray vs a set of objects placed on a grid (where the objects are of uniform size but larger than the grid spacing, so that they overlap), please let me know. Thanks!