Graphics Reference
In-Depth Information
dx
dx
2
+ dy
2
tx
=
(maxx - x
1
)
dx
dx
2
+ dy
2
tx
=
(x
1
-
minx)
maxx = M x
1
/M
+
M
tx
minx = M x
1
/M
minx = M x
1
/M
(
x
1
,
y
1
)
(
x
1
,
y
1
)
tx
maxx = M x
1
/M
+
M
x
1
-
minx
maxx - x
1
(a)
(b)
Figure 7.18
Computing the initial value of
tx
(done analogously for
ty
) (a) for a ray directed
to the left and (b) for a ray directed to the right.
If instead the ray is directed to the left, the corresponding expression is
minx
)
dx
2
+
dy
2
=
−
tx
(
x
1
.
dx
These derivations are illustrated in Figure 7.18. The initial value of
ty
is computed in
an analogous fashion.
To keep track of which cell is currently visited, first the cell (
i
,
j
) that the ray or
directed line segment originates in is found. A direction (
di
,
dj
) is then computed for
the ray. For a ray directed up and to the right, the direction would be (1, 1). For a ray
going to the left, it would be (
1, 0), and so on. Each time the ray passes through a cell
boundary, a step of
di
or
dj
is made along the
x
axis or
y
axis respectively, depending on
whether the boundary was vertical or horizontal. For a line segment, the coordinates
of the ending cell are computed in advance to minimize the traversal cost.
The follo
wing code implements the full grid traversal. Note that because the term
−
dx
2
+
dy
2
is constant and occurs in all four of the
tx
,
ty
,
tx
, and
ty
terms it can
be dropped, greatly simplifying the initialization calculations.
void VisitCellsOverlapped(float x1, float y1, float x2, float y2)
{
// Side dimensions of the square cell
const float CELL_SIDE = 30.0f;
// Determine start grid cell coordinates (i, j)
int i = (int)(x1 / CELL_SIDE);
int j = (int)(y1 / CELL_SIDE);
