Line segment with grid intersection test ?

[Alejo Hausner]

On Wed, 2 Jun 2004, Skybuck Flying wrote:

> A line segment intersects with a grid. The cells in the grid have the same
> dimensions.
>
> The objective is to mark all cells that are intersected by the line segment.
>
> I am looking for a description of an algorithm that will work in 2D.


(I didn't invent the stuff below)


The problem arises in acceleration of ray tracing.
A simple solution will treat the line segment as a
ray, and will march accross the grid.  It must keep
track of the distance t along the ray, where the ray
enters the current grid cell (i,j).

1. Find which side of the grid the ray hits first,
   determine the initial t, and identify the initial
   grid cell (i,j).

2. Consider the two lines on the "other" side of cell
   (i,j) : the ray intersects the x-parallel line at
   tx, and the y-parallel line at ty.

3. The smaller of tx and ty determines the next cell
   visited:
   if (tx < ty) {
     t = tx;
     i++;
   }
   else {
     t = ty;
     j++;
   }

4. Repeat until ray exits whole grid.

Note: for step 2, you can pre-compute a decision
flag which can be used in the loop to quickly decide
which exit lines you should test.

The algorithm extends very naturally to 3 and higher
dimensions.

------------------------------+-------------------------------
Alejo Hausner (ah at cs.unh.edu) | Mailing address:
  phone: (603) 862-1237       |   Dept. of Computer Science
  fax:   (603) 862-3493       |   131 Main St.
  Office: Nesmith 303         |   Durham, NH 03824

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.