Graphics Reference
In-Depth Information
though is that the time spent in line drawing algorithms is often dominated by the
operation of setting pixels in the frame buffer, so that software improvements alone
may be less important.
2.6
The Aliasing Problem
No matter how good a line drawing algorithm is, it is impossible to avoid giving most
discrete lines a staircase effect (the “jaggies”). They just will not look “straight.”
Increasing the resolution of the raster helps but does not resolve the problem entirely.
In order to draw the best looking straight lines one has to first understand the “real”
underlying problem which is one of
sampling
.
The geometric curves and surfaces one is typically trying to display are continu-
ous and consist of an infinite number of points. Since a computer can only show a
finite (discrete) set of points, how one chooses this finite set that is to represent the
object is clearly important. Consider the sinusoidal curve in Figure 2.11. If we sample
such a sine wave badly, say at the points
A
,
B
,
C
, and
D
, then it will look like a straight
line. If we had sampled at the points
A
,
E
,
F
, and
D
, then we would think that it has
a different frequency.
The basic problem in sampling theory:
How many samples does one have to take so
that no information is lost?
This is a question that is studied in the field of signal processing. The theory of
the
Fourier transform
plays a big role in the analysis. Chapter 21, in particular Section
21.6, gives an overview of some of the relevant mathematics. For more details of the
mathematics involved in answering the sampling problem see [GonW87], [RosK76],
or [Glas95]. We shall only summarize a few of the main findings here and indicate
some practical solutions that are consequences of the theory.
Definition.
A function whose Fourier transform vanishes outside a finite interval is
called a
band-limited
function.
One of the basic theorems in sampling theory is the following:
The Whittaker-Shannon Sampling Theorem.
Let f(x) be a band-limited function
and assume that its Fourier transform vanishes outside [-w,w]. Then f(x) can be
reconstructed exactly from its samples provided that the sampling interval is no bigger
than 1/(2w).
Figure 2.11.
Aliasing caused by bad sampling.
