i
i
i
i
i
i
i
i
164 8. The Graphics Pipeline
line possible that has no gaps. A diagonal connection between two pixels is not
considered a gap.
As the line progresses from the left endpoint to the right, there are only two
possibilities: draw a pixel at the same height as the pixel drawn to its left, or draw
a pixel one higher. There will always be exactly one pixel in each column of pixels
Figure 8.2. Three
“reasonable” lines that go
seven pixels horizontally
and three pixels vertically.
between the endpoints. Zero would imply a gap, and two would be too thick a line.
There may be two pixels in the same row for the case we are considering; the line
is more horizontal than vertical so sometimes it will go right, and sometimes up.
This concept is shown in Figure 8.2, where three “reasonable” lines are shown,
each advancing more in the horizontal direction than in the vertical direction.
The midpoint algorithm for m ∈ (0, 1] first establishes the leftmost pixel and
the column number (x-value) of the rightmost pixel and then loops horizontally
establishing the row (y-value) of each pixel. The basic form of the algorithm is:
y = y
0
for x = x
0
to x
1
do
draw(x, y)
if (some condition) then
y = y +1
Note that x and y are integers. In words this says, “keep drawing pixels from left
to right and sometimes move upwards in the y-direction while doing so.” The key
is to establish efficient ways to make the decision in the if statement.
An effective way to make the choice is to look at the midpoint of the line
between the two potential pixel centers. More specifically, the pixel just drawn
is pixel (x, y) whose center in real screen coordinates is at (x, y). The candidate
pixels to be drawn to the right are pixels (x+1,y) and (x+1,y+1).The midpoint
between the centers of the two candidate pixels is (x +1,y +0.5). If the line
passes below this midpoint we draw the bottom pixel, and otherwise we draw the
top pixel (Figure 8.3).
To decide whether the line passes above or below (x+1,y+0.5),weevaluate
f(x, y +0.5) in Equation (8.1). Recall from Section 2.5.1 that f (x, y)=0for
points (x, y) on the line, f (x, y) > 0 for points on one side of the line, and
f(x, y) < 0 for
points on the other side of the line. Because −f(x, y)=0and
Figure 8.3. Top: the line
goes above the midpoint so
the top pixel is drawn. Bot-
tom: the line goes below
the midpoint so the bottom
pixel is drawn.
f(x, y)=0are both perfectly good equations for the line, it is not immediately
clear whether f(x, y) being positive indicates that (x, y) is above the line, or
whether it is below. However, we can figure it out; the key term in Equation (8.1)
is the y term (x
1
− x
0
)y. Note that (x
1
− x
0
) is definitely positive because
x
1
>x
0
. This means that as y increases, the term (x
1
−x
0
)y gets larger (i.e., more
positive or less negative). Thus, the case f(x, +∞) is definitely positive, and
definitely above the line, implying points above the line are all positive. Another