Graphics Reference
In-Depth Information
// Determine end grid cell coordinates (iend, jend)
int iend = (int)(x2 / CELL_SIDE);
int jend = (int)(y2 / CELL_SIDE);
// Determine in which primary direction to step
intdi=((x1<x2)?1:((x1 > x2) ? -1 : 0));
intdj=((y1<y2)?1:((y1 > y2) ? -1 : 0));
// Determine tx and ty, the values of t at which the directed segment
// (x1,y1)-(x2,y2) crosses the first horizontal and vertical cell
// boundaries, respectively. Min(tx, ty) indicates how far one can
// travel along the segment and still remain in the current cell
float minx = CELL_SIDE * floorf(x1/CELL_SIDE), maxx = minx + CELL_SIDE;
float tx = ((x1 < x2) ? (x1 - minx) : (maxx - x1)) / Abs(x2 - x1);
float miny = CELL_SIDE * floorf(y1/CELL_SIDE), maxy = miny + CELL_SIDE;
float ty = ((y1 < y2) ? (y1 - miny) : (maxy - y1)) / Abs(y2 - y1);
// Determine deltax/deltay, how far (in units of t) one must step
// along the directed line segment for the horizontal/vertical
// movement (respectively) to equal the width/height of a cell
float deltatx = CELL_SIDE / Abs(x2 - x1);
float deltaty = CELL_SIDE / Abs(y2 - y1);
// Main loop. Visits cells until last cell reached
for (;;) {
VisitCell(i, j);
if (tx <= ty) {
// tx smallest, step in x
if (i == iend) break;
tx += deltatx;
i+=di;
} else {
// ty smallest, step in y
if (j == jend) break;
ty += deltaty;
j+=dj;
}
}
}
Instead of using the
i
and
j
coordinates to index into some array
grid[i][j]
,it
is possible to maintain a pointer to the current cell and step the pointer directly by
adding appropriate values to the pointer instead of adding
di
and
dj
to a set of index
variables.
