Graphics Reference
In-Depth Information
more generally in
Z
n
. Although we are only interested in the case n = 2 in this chapter,
there is nothing special about that case (except for the terminology), and it is useful
to see what one can do in general. In fact, the case n = 3 will be needed to define dis-
crete lines for volume rendering in Chapter 10. This topic will not delve into the
concept of curve rasterization in dimensions larger than 3, but the subject has been
studied. See, for example, [Wüth98] or [Herm98].
Definition.
In
Z
2
, the
4-neighbors
of (i,j) are the four large grid points adjacent to
(i,j) shown in Figure 2.1(a). The
8-neighbors
of (i,j) are the eight large grid points adja-
cent to (i,j) in Figure 2.1(b). More precisely, the 4-neighbors of (i,j) are the points (i,j
+ 1), (i - 1,j), (i,j - 1), and (i + 1,j). The 8-neighbors can be listed in a similar way.
In order to generalize this definition to higher dimensions, think of the plane as
tiled with 1 ¥ 1 squares that are centered on the grid points of
Z
2
and whose sides are
parallel to the coordinate axes (see Figure 2.1 again). Then, another way to define the
neighbors of a point (i,j) is to say that the 4-neighbors are the centers of those squares
in the tiling that share an edge with the square centered on (i,j) and the 8-neighbors
are the centers of those squares in the tiling that share
either
an edge
or
a vertex with
that square. Now think of
R
n
as tiled with n-dimensional unit cubes whose centers
are the points of
Z
n
and whose faces are parallel to coordinate planes.
Definition.
In
Z
3
, the
6-neighbors
of (i,j,k) are the grid points whose cubes meet the
cube centered at (i,j,k) in a face. The
18-neighbors
of (i,j,k) are the grid points whose
cubes meet that cube in either a face
or
an edge. The
26-neighbors
of (i,j,k) are the
grid points whose cubes meet that cube in either a face
or
an edge
or
a point.
Figure 2.2(a) shows the cubes of the 6-neighbors of the center point. Figure 2.2(b)
shows those of the 18-neighbors and Figure 2.2(c), those of the 26-neighbors. More
generally,
Figure 2.1.
The 4- and 8-neighbors of a point.
Figure 2.2.
The 6-, 18-, and 26-neighbors of a point.
