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”).
