i
i
i
i
i
i
i
i
168 8. The Graphics Pipeline
and get the third from that relation, but it is not clear that this saves computation
once the algorithm is made incremental, which is possible as in the line drawing
algorithms; each of the computations of α, β,andγ does an evaluation of the
form f(x, y)=Ax + By + C. In the inner loop, only x changes, and it changes
by one. Note that f(x +1,y)=f(x, y)+A. This is the basis of the incremental
algorithm. In the outer loop, the evaluation changes for f (x, y) to f(x, y +1),
so a similar efficiency can be achieved. Because α, β,andγ change by constant
increments in the loop, so does the color c. So this can be made incremental as
well. For example, the red value for pixel (x +1,y) differs from the red value
for pixel (x, y) by a constant amount that can be precomputed. An example of a
triangle with color interpolation is shown in Figure 8.5.
Dealing with Pixels on Triangle Edges
We have still not discussed what to do for pixels whose centers are exactly on
the edge of a triangle. If a pixel is exactly on the edge of a triangle, then it is
also on the edge of the adjacent triangle if there is one. There is no obvious way
to award the pixel to one triangle or the other. The worst decision would be to
not draw the pixel because a hole would result between the two triangles. Better,
but still not good, would be to have both triangles draw the pixel. If the triangles
are transparent, this will result in a double-coloring. We would really like to
award the pixel to exactly one of the triangles, and we would like this process
to be simple; which triangle is chosen does not matter as long as the choice is
well defined.
Figure 8.6. The off-
screen point will be on one
side of the triangle edge
or the other. Exactly one
of the non-shared vertices
a and b will be on the
same side.
One approach is to note that any off-screen point is definitely on exactly one
side of the shared edge and that is the edge we will draw. For two non-overlapping
triangles, the vertices not on the edge are on opposite sides of the edge from each
other. Exactly one of these vertices will be on the same side of the edge as the
off-screen point (Figure 8.6). This is the basis of the test. The test if numbers p
and q have the same sign can be implemented as the test pq > 0,whichisvery
efficient in most environments.
Note that the test is not perfect because the line through the edge may also
go through the offscreen point, but we have at least greatly reduced the number
of problematic cases. Which off-screen point is used is arbitrary, and (x, y)=
(−1, −1) is as good a choice as any. We will need to add a check for the case of a
point exactly on an edge. We would like this check not to be reached for common
cases, which are the completely inside or outside tests. This suggests:
x
min
= floor (x
i
)
x
max
= ceiling (x
i
)