Graphics Reference
In-Depth Information
CHAPTER 2
Raster Algorithms
Prerequisites:
Sections 4.2, 5.2 in [AgoM05] (to define and motivate concepts in
Section 2.2), Section 21.8 (for Section 2.6)
2.1
Introduction
As pointed out in our introductory chapter, the only real implementation constraint
that the hardware places on us is that all geometric objects eventually need to be rep-
resented by a collection of points in a two-dimensional grid (a raster). The subject
matter of this chapter 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 continu-
ous one.
Section 2.2 starts the chapter 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.
2.2
Discrete Topology
This section defines the discrete analogs of a number of important continuous con-
cepts. 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
Z
2
and so this
leads us to describe some possible definitions of a neighborhood of a point in
Z
2
, or
