Introduction
As pointed out in our introductory topic, the only real implementation constraint that the hardware places on us is that all geometric objects eventually need to be represented by a collection of points in a two-dimensional grid (a raster). The subject matter of this topic is to analyze the geometry of discrete sets and to describe some important algorithms that map continuous planar objects to discrete ones. Insofar as it is possible, one would like the discrete world to be a mirror image of the continuous one.
Section 2.2 starts the topic by introducing some discrete world terminology. Sections 2.3, 2.4, and 2.9.1 describe a border-following algorithm and several region-filling algorithms. Sections 2.5 and 2.9 deal with discrete curves – how to generate them and work with them efficiently. Sections 2.6-2.8 discuss some problems caused by discretization and some ways to deal with them. Hardware issues that are involved in the optimization of low-level graphics primitives are ignored in this topic, but Section 2.10 does briefly discuss how the existence of certain bit map operations helps out. We finish with a brief discussion in Section 2.11 of a few basic techniques in 2d animation.
Discrete Topology
This section defines the discrete analogs of a number of important continuous concepts. Probably the most basic of these is the idea of continuity itself, and central to that is the idea of a neighborhood of a point. Neighborhoods define the "topology" of a space. Now a raster can be modeled in an obvious way as a subset of Z2 and so this leads us to describe some possible definitions of a neighborhood of a point in Z2, or more generally in Zn. Although we are only interested in the case n = 2 in this topic, there is nothing special about that case (except for the terminology), and it is useful to see what one can do in general.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, [Wuth98] or [Herm98].
Definition. In Z2, 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 adjacent 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 x 1 squares that are centered on the grid points of Z2 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 Rn as tiled with n-dimensional unit cubes whose centers are the points of Zn and whose faces are parallel to coordinate planes.
Definition. In Z3, 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.
Definition. Let _
and let d be a fixed integer satisfying 0 < d < n – 1. Suppose that k is the number of points of Zn that are the centers of cubes that meet the cube with center p in a face of dimension larger than or equal to d. Each of those points will be called a k-neighbor of p in Zn.
Note: The general definition for k-neighbor is not very satisfying because it is relatively complicated. It would have made more sense to call the point a “d-neighbor.” Unfortunately, the terminology as stated is too well established for the two- and threedimensional case to be able to change it now.
Definition. Two points in Zn are said to be k-adjacent if they are k-neighbors.
k-adjacency is the key topological concept in the discrete world. All the terms defined below have an implicit “k-” prefix. However, to simplify the notation this prefix will be dropped. For example, we shall simply refer to “adjacent” points rather than “k-adjacent” points. It must be emphasized though that everything depends on the notion of adjacency that is chosen, that is, for example, whether the intended k is 4 or 8, in the case of Z2, or 6, 18, or 26, in the case of Z3. To make this dependency explicit, one only needs to restore the missing “k-” prefix.
There is a nice alternate characterization of k-adjacency in two special cases that could have been used as the definition in those cases.
Alternate Definition. Let
The points p
and q are 2n-adjacent in
if and only if 
They are (3n – 1)-adjacent in Zn if and only if
Properties of 2n- and (3n – 1)-adjacency are studied extensively in [Herm98].
Definition. A (discrete or digital) curve from point p to point q in Zn is a sequence 
of points such that
is adjacent to
Furthermore, with this notation, we define the length of the curve to be k – 1.
For example, the points pi, p2, p3, and p4 in Figure 2.3 form a discrete curve of length 3 with respect to 8-adjacency but not with respect to 4-adjacency because p1 and p2 are not 4-adjacent.
Definition. A set S is connected if for any two points p and q in S there is a curve from p to q that lies entirely in S. A maximal connected subset of S is called a component.
Figure 2.3. An 8-connected discrete curve.
Because of the difference between 4- and 8-connected, note the difference between a 4-component and an 8-component. It is easy to show that every 8-component is the union of 4-components (Exercise 2.2.2). A similar comment holds for the components of sets in Z3.
Some Definitions. We assume that the sets S below are subsets of some fixed set P in Zn. In practice, P is usually a large but finite solid rectangular set representing the whole picture for a scene, but it could be all of Zn.
The complement of S in P, denoted by Sc, is, P – S.
The border of S, B(S), consists of those points of S that have neighbors belonging to Sc if S π P or neighbors in Zn – P if S = P.
The background of S is the union of those components of Sc that are either unbounded in Zn or that contain a point of the border of the picture P.
The holes of S are all the components of Sc that are not contained in the background of S.
S is said to be simply connected if S is connected and has no holes.
The interior of S, iS, is the set S – B(S).
An isolated point of S is a point of S that has no neighbors in S.
If S is a finite set, then the area of S is the number of points in S.
Definition. There are several ways to define the distance d between two points (i,j) and (k,l) in Z2, or, more generally, between points p and q in Zn:
This distance function gets its name from the fact that a taxi driving from one location to another along orthogonal streets would drive that distance.
Figure 2.4. Examples of discrete concepts.
All three of these distance functions define a metric on Zn, called the Euclidean, taxicab, and max metric, respectively. (They actually also define a metric on Rn.) For example, consider the points p = (2,1) and q = (5,3). Then the distances between these two points are:
The points that are a distance of 1 from a given point are its 4-neighbors when we use the taxicab distance and the 8-neighbors when we use the max distance.
Finally, the rest of this topic deals with two-dimensional sets and, unless stated otherwise, all our sets will be (discrete) subsets of some given picture P in Z2. We shall use the terminology above.
Border-Following Algorithms
Algorithms that can compute the borders of regions in a picture are important in a variety of places, in particular in animation. We describe one such algorithm here to give the reader a flavor of what they are like. See [RosK76] for more details. Other contour-following algorithms are described in [Pavl82]. See also [Herm98].
Assume that each point of a picture has a value associated to it and that in our case this is either 0 or 1, with the region of interest in it being the points with value 1. We shall show pictures by showing the values at their points and, to simplify the discussion, we often identify the point with its value. (“Setting a point to 3” will mean setting its value to 3.)
Definition. If C is a component of S, D a component of Sc, then the D-border of C is the set of points of C that are adjacent to a point of D.
For example, consider the connected set S of 1′s below:
Let D1 and D2 be the components of Sc that contain the left and right “0,” respectively. Then
are the D1-border and D2-border of S, respectively.
Algorithm 2.3.1. A border-following algorithm.
Example. We show the various stages of Algorithm 2.3.1 for a set S. The values of points in the pictures below are shown in boldface and S starts off as the points marked with 1′s. The current c and d are shown in parentheses to the left of the point to which they refer. The numbering of the 8-neighbors of c is shown in parentheses to the right of the point. We also show the value of k that we get in step (2) of the algorithm.
Finally, the configuration
shows that the choice of adjacency is important. The algorithm fails if C is a 4-component and must be changed. See [RosK76].
Algorithm 2.3.1 can be used to find all border points of a set S. It provides a way of marking its border points so that one can then fill the interior of S using a fill algorithm of the type discussed in the next section.
