i
i
i
i
i
i
i
i
5.6. Aliasing and Antialiasing 119
Figure 5.21. The solid blue line is the original signal, the red circles indicate uniformly
spaced sample points, and the green dashed line is the reconstructed signal. The top
figure shows a too low sample rate. Therefore, the reconstructed signal appears to be
of lower frequency. The bottom shows a sampling rate of exactly twice the frequency
of the original signal, and the reconstructed signal is here a horizontal line. It can be
proven that if the sampling rate is increased ever so slightly, perfect reconstruction is
possible.
a movie camera [404]. Because the wheel spins much faster than the camera
records images, the wheel may appear to be spinning slowly (backwards or
forwards), or may even look like it is not rotating at all. This can be seen
in Figure 5.20. The effect occurs because the images of the wheel are taken
in a series of time steps, and is called temporal aliasing.
Common examples of aliasing in computer graphics are the “jaggies” of
a rasterized line or polygon edge, flickering highlights, and when a texture
with a checker pattern is minified (see Section 6.2.2).
Aliasing occurs when a signal is being sampled at too low a frequency.
The sampled signal then appears to be a signal of lower frequency than the
original. This is illustrated in Figure 5.21. For a signal to be sampled prop-
erly (i.e., so that it is possible to reconstruct the original signal from the
samples), the sampling frequency has to be more than twice the maximum
frequency of the signal to be sampled. This is often called the sampling
theorem, and the sampling frequency is called the Nyquist
7
rate [1035, 1367]
or Nyquist limit [1332]. The Nyquist limit is also illustrated in Figure 5.20.
The fact that the theorem uses the term “maximum frequency” implies
that the signal has to be bandlimited, which just means that there are not
any frequencies above a certain limit. Put another way, the signal has to
be smooth enough relative to the spacing between neighboring samples.
A three-dimensional scene is normally never bandlimited when rendered
with point samples. Edges of polygons, shadow boundaries, and other
phenomena produce a signal that changes discontinuously and so produces
frequencies that are essentially infinite [170]. Also, no matter how closely
7
After Harry Nyquist [1889-1976], Swedish scientist, who discovered this in 1928.
i
i
i
i
i
i
i
i
120 5. Visual Appearance
packed the samples are, objects can still be small enough that they do
not get sampled at all. Thus, it is impossible to entirely avoid aliasing
problems when using point samples to render a scene. However, at times
it is possible to know when a signal is bandlimited. One example is when
a texture is applied to a surface. It is possible to compute the frequency
of the texture samples compared to the sampling rate of the pixel. If this
frequency is lower than the Nyquist limit, then no special action is needed
to properly sample the texture. If the frequency is too high, then schemes
to bandlimit the texture are used (see Section 6.2.2).
Reconstruction
Given a bandlimited sampled signal, we will now discuss how the original
signal can be reconstructed from the sampled signal. To do this, a filter
must be used. Three commonly used filters are shown in Figure 5.22. Note
that the area of the filter should always be one, otherwise the reconstructed
signal can appear to grow or shrink.
In Figure 5.23, the box filter (nearest neighbor) is used to reconstruct
a sampled signal. This is the worst filter to use, as the resulting signal
is a noncontinuous stair case. Still, it is often used in computer graphics
because of its simplicity. As can be seen in the illustration, the box filter is
placed over each sample point, and then scaled so that the topmost point
of the filter coincides with the sample point. The sum of all these scaled
and translated box functions is the reconstructed signal shown to the right.
The box filter can be replaced with any other filter. In Figure 5.24,
the tent filter, also called the triangle filter, is used to reconstruct a sam-
pled signal. Note that this filter implements linear interpolation between
Figure 5.22. The top left shows the box filter, and the top right the tent filter. The
bottom shows the sinc filter (which has been clamped on the x-axis here).
i
i
i
i
i
i
i
i
5.6. Aliasing and Antialiasing 121
Figure 5.23. The sampled signal (left) is reconstructed using the box filter. This is done
by placing the box filter (see Figure 5.22) over each sample point, and scaling it in the
y-direction so that the height of the filter is the same as the sample point. The sum is
the reconstruction signal (right).
Figure 5.24. The sampled signal (left) is reconstructed using the tent filter. The recon-
structed signal is shown to the right.
neighboring sample points, and so it is better than the box filter, as the
reconstructed signal now is continuous.
However, the smoothness of the reconstructed signal using a tent filter
is not very good; there are sudden slope changes at the sample points. This
has to do with the fact that the tent filter is not a perfect reconstruction
filter. To get perfect reconstruction the ideal lowpass filter has to be used.
A frequency component of a signal is a sine wave: sin(2πf), where f is
the frequency of that component. Given this, a lowpass filter removes all
frequency components with frequencies higher than a certain frequency
defined by the filter. Intuitively, the lowpass filter removes sharp features
i
i
i
i
i
i
i
i
122 5. Visual Appearance
Figure 5.25. Here, the sinc filter is used to reconstruct the signal. The sinc filter is the
ideal lowpass filter.
of the signal, i.e., the filter blurs it. The ideal lowpass filter is the sinc filter
(Figure 5.22 bottom):
sinc(x)=
sin(πx)
πx
. (5.15)
Using the sinc filter to reconstruct the signal gives a smoother result, as
shown in Figure 5.25.
8
What can be seen is that the sampling process introduces high fre-
quency components (abrupt changes) in the signal, and the task of the
lowpass filter is to remove these. In fact, the sinc filter eliminates all sine
waves with frequencies higher than 1/2 the sampling rate. The sinc func-
tion, as presented in Equation 5.15, is the perfect reconstruction filter when
the sampling frequency is 1.0 (i.e., the maximum frequency of the sampled
signal must be smaller than 1/2). More generally, assume the sampling fre-
quency is f
s
, that is, the interval between neighboring samples is 1/f
s
.For
such a case, the perfect reconstruction filter is sinc(f
s
x), and it eliminates
all frequencies higher than f
s
/2. This is useful when resampling the signal
(next section). However, the filter width of the sinc is infinite and also is
negative at times, so it is rarely useful in practice.
There is a useful middle ground between the low-quality box and tent
filters on one hand, and the impractical sinc filter on the other. Most widely
used filter functions [872, 941, 1276, 1367] are between these extremes. All
8
The theory of Fourier analysis [1035] explains why the sinc filter is the ideal lowpass
filter. Briefly, the reasoning is as follows. The ideal lowpass filter is a box filter in
the frequency domain, which removes all frequencies above the filter width when it is
multiplied with the signal. Transforming the box filter from the frequency domain to
the spatial domain gives a sinc function. At the same time, the multiplication operation
is transformed into the convolution function, which is what we have been using in this
section, without actually describing the term.
i
i
i
i
i
i
i
i
5.6. Aliasing and Antialiasing 123
of these filter functions have some approximation to the sinc function, but
with a limit on how many pixels they influence. The filters that most
closely approximate the sinc function have negative values over part of
their domain. For applications where negative filter values are undesirable
or impractical, filters with no negative lobes (often referred to generically
as Gaussian filters, since they either derive from or resemble a Gaussian
curve) are typically used. Section 10.9 discusses filter functions and their
use in more detail.
After using any filter, a continuous signal is obtained. However, in
computer graphics we cannot display continuous signals directly, but we
can use them to resample the continuous signal to another size, i.e., either
enlarging the signal, or diminishing it. This is discussed next.
Resampling
Resampling is used to magnify or minify a sampled signal. Assume that the
original sample points are located at integer coordinates (0, 1, 2,...), that
is, with unit intervals between samples. Furthermore, assume that after
resampling we want the new sample points to be located uniformly with an
interval a between samples. For a>1, minification (downsampling) takes
place, and for a<1, magnification (upsampling) occurs.
Magnification is the simpler case of the two, so let us start with that.
Assume the sampled signal is reconstructed as shown in the previous sec-
tion. Intuitively, since the signal now is perfectly reconstructed and con-
tinuous, all that is needed is to resample the reconstructed signal at the
desired intervals. This process can be seen in Figure 5.26.
However, this technique does not work when minification occurs. The
frequency of the original signal is too high for the sampling rate to avoid
Figure 5.26. On the left is the sampled signal, and the reconstructed signal. On the
right, the reconstructed signal has been resampled at double the sample rate, that is,
magnification has taken place.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.