Graphics Reference
In-Depth Information
2.8
Choosing the Coordinates of a Pixel
Before going on to discuss another scan conversion algorithm we pause to take up a
subject that probably did not occur to the reader as being an issue. However, since
pixels should be treated as having area, if we consider our image as corresponding to
a grid as we have, where should the pixels be placed? Should they be at the intersec-
tion of the grid lines or in the center of the grid squares? Equivalently, when we con-
sider scan lines, do their y-coordinates fall on integers or half-integers? Whatever
choice one makes, it
does
matter. We summarize the conclusions of the excellent
article by Heckbert [Heck90a].
The real issue here is how one maps reals to integers. Should one round or trun-
cate? Rounding corresponds to placing pixels at the integers because the whole inter-
val [n - 0.5,n + 0.5) will map to n. Truncating corresponds to placing the pixels at
half-integers because the whole interval [n,n + 1) will map to n. To use an example,
if one rounds, then the interval [-.5,2.5) maps to {0,1,2}, whereas if one truncates,
then [0,3) maps to {0,1,2}. The second approach is a cleaner choice because there are
no .5's to worry about. By truncating one simplifies some mathematics. We shall there-
fore use the following correspondence if we need to map back and forth between the
continuous and discrete world:
real
c
Æ
integer
n = Floor (c)
integer
n
Æ
real
(n + 0.5)
(Mathematically it is the Floor function that returns an integer whereas the Trunc
function returns a real.) In two dimensions this means that when we have a pixel with
coordinates (x,y), its center will be at continuous coordinates (x + 0.5,y + 0.5). Note
that this was the choice we made when discussing antialiasing. Now we know why.
In the future, whenever we scan a
continuous
object the scan lines will fall on
half-integers.
2.9
More Drawing Algorithms
2.9.1
Scan Converting Polygons
The Bresenham line-drawing algorithm discussed in Section 2.5.2 dealt with scan con-
verting a
single
segment. There may be several segments we want to scan convert
such as the boundary of a polygon. In that case one can use the
coherence
inherent
in that problem and use an algorithm that is more efficient that simply scan con-
verting each bounding edge separately.
Consider the edges in Figure 2.16. As we move down from the top of the picture
one scan line at a time we do not need to compute the intersections of the edges
with the scan line each time. These can be computed incrementally. Since not every
edge will intersect current scan line, by using an
active edge list
(AEL), we do not
have to look at every edge each time. Here are the steps to scan convert these edges
efficiently:
