Graphics Reference
In-Depth Information
Figure 10.17.
Rays tunneling through objects.
dx
=-
x
x
,
dy
=-
y
y
,
and dz
=-
z
z
.
1
0
1
0
1
0
We shall describe an algorithm for generating 26-connected lines first.
Assume that dx ≥ dy ≥ dz ≥ 0. Let
L
xy
and
L
xz
be the projections of
L
on the xy-
and xz-plane, respectively. We shall build our discrete line from the midpoint line
drawing algorithm applied to the lines
L
xy
and
L
xz
. Now the line
L
xy
goes from (x
0
,y
0
,0)
to (x
1
,y
1
,0) and
L
xz
goes from (x
0
,0,z
0
) to (x
1
,0,z
1
). Using the notation of Algorithm
2.5.3.1 in Section 2.5.3, let d
xy
be the decision variable for the line
L
xy
and posInc
xy
and negInc
xy
the increments of this variable. Similarly, let d
xz
, posInc
xz
, and negInc
xz
be the corresponding variables for the line
L
xz
. Since the metric associated to 26-
connected curves is the max metric, our assumptions on the relative sizes of dx, dy,
and dz mean that the x-coordinate of the discrete points we generate will increase by
one each time, so that the curve will have length dx. Furthermore, we can determine
how the y-coordinate and z-coordinate change by looking at the midpoint algorithm
applied to the lines
L
xy
and
L
xz
, respectively. If we fill in the details we get Algorithm
10.4.1.1. Finally, for a complete algorithm that generates 26-connected discrete lines,
one that handles lines between any two points, we need two more versions of Algo-
rithm 10.4.1.1 to handle the case of nonnegative dx, dy, and dz, namely, one where dy
is the largest increment and one where dz is the largest. The rest of the cases where
one or more of the dx, dy, or dz are negative are handled by symmetry.
Next, we look at the case of 6-connected lines. We shall describe the algorithm
presented in [CohK97]. This time we only need to assume that dx, dy, dz ≥ 0. In addi-
tion to the projections
L
xy
and
L
xz
we also consider the projection
L
yz
of the line
L
onto the yz-plane. Define functions f
i
(x,y) by
(
)
=
()
-
()
+
fxy
,
dyx dxy c
1
1
(
)
=
()
-
()
+
fxz
,
dzx dxz c
2
2
(
)
=
()
-
()
+
fyz
,
dzy dyz c
.
3
3
Then the lines
L
xy
,
L
xz
, and
L
yz
are defined by f
1
(x,y) = 0, f
2
(x,z) = 0, and f
3
(y,z) = 0,
respectively. Assume that pixels are centered on points with integer coordinates. If the
line crosses a pixel centered at (x,y,z), then it will leave the pixel via one of the three
faces adjacent to the point
O
= (x + 0.5,y + 0.5,z + 0.5). See Figure 10.18(a). We shall
