i
i
i
i
i
i
i
i
166 8. The Graphics Pipeline
8.1.2 Triangle Rasterization
We often want to draw a 2D triangle with 2D points p
0
=(x
0
,y
0
), p
1
=(x
1
,y
1
),
and p
2
=(x
2
,y
2
) in screen coordinates. This is similar to the line drawing
problem, but it has some of its own subtleties. As with line drawing, we may
wish to interpolate color or other properties from values at the vertices. This is
straightforward if we have the barycentric coordinates(Section 2.7). For example,
if the vertices have colors c
0
, c
1
,andc
2
, the color at a point in the triangle with
barycentric coordinates (α, β, γ) is
c = αc
0
+ βc
1
+ γc
2
.
This type of interpolation of color is known in graphics as Gouraud interpolation
after its inventor (Gouraud, 1971).
Another subtlety of rasterizing triangles is that we are usually rasterizing tri-
angles that share vertices and edges. This means we would like to rasterize ad-
jacent triangles so there are no holes. We could do this by using the midpoint
algorithm to draw the outline of each triangle and then fill in the interior pixels.
This would mean adjacent triangles both draw the same pixels along each edge.
If the adjacent triangles have different colors, the image will depend on the order
in which the two triangles are drawn. The most common way to rasterize trian-
gles that avoids the order problem and eliminates holes is to use the convention
that pixels are drawn if and only if their centers are inside the triangle, i.e., the
barycentric coordinates of the pixel center are all in the interval (0, 1).Thisraises
the issue of what to do if the center is exactly on the edge of the triangle. There
are several ways to handle this as will be discussed later in this section. The key
observation is that barycentric coordinates allow us to decide whether to draw a
pixel and what color that pixel should be if we are interpolating colors from the
vertices. So our problem of rasterizing the triangle boils down to efficiently find-
ing the barycentric coordinates of pixel centers (Pineda, 1988). The brute-force
rasterization algorithm is:
for all x do
for all y do
compute (α, β, γ) for (x, y)
if (α ∈ [0, 1] and β ∈ [0, 1] and γ ∈ [0, 1]) then
c = αc
0
+ βc
1
+ γc
2
drawpixel (x, y) with color c
The rest of the algorithm limits the outer loops to a smaller set of candidate pixels
and makes the barycentric computation efficient.
i
i
i
i
i
i
i
i
8.1. Rasterization 167
We can add a simple efficiency by finding the bounding rectangle of the
three vertices and only looping over this rectangle for candidate pixels to draw.
We can compute barycentric coordinates using Equation (2.33). This yields the
algorithm:
x
min
= floor (x
i
)
x
max
= ceiling (x
i
)
y
min
= floor (y
i
)
y
max
= ceiling (y
i
)
for y = y
min
to y
max
do
for x = x
min
to x
max
do
α = f
12
(x, y)/f
12
(x
0
,y
0
)
β = f
20
(x, y)/f
20
(x
1
,y
1
)
γ = f
01
(x, y)/f
01
(x
2
,y
2
)
if (α>0 and β>0 and γ>0) then
c = αc
0
+ βc
1
+ γc
2
drawpixel (x, y) with color c
Here f
ij
is the line given by Equation (8.1) with the appropriate vertices:
f
01
(x, y)=(y
0
− y
1
)x +(x
1
− x
0
)y + x
0
y
1
− x
1
y
0
,
f
12
(x, y)=(y
1
− y
2
)x +(x
2
− x
1
)y + x
1
y
2
− x
2
y
1
,
f
20
(x, y)=(y
2
− y
0
)x +(x
0
− x
2
)y + x
2
y
0
− x
0
y
2
.
Note that we have exchanged the test α ∈ (0, 1) with α>0 etc., because if
all of α, β, γ are positive, then we know they are all less than one because α +
β + γ =1. We could also compute only two of the three barycentric variables
Figure 8.5. A colored triangle with barycentric interpolation. Note that the changes in color
components are linear in each row and column as well as along each edge. In fact it is
constant along every line, such as the diagonals, as well. (See also Plate II.)
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
)
i
i
i
i
i
i
i
i
8.1. Rasterization 169
y
min
= floor (y
i
)
y
max
= ceiling (y
i
)
f
α
= f
12
(x
0
,y
0
)
f
β
= f
20
(x
1
,y
1
)
f
γ
= f
01
(x
2
,y
2
)
for y = y
min
to y
max
do
for x = x
min
to x
max
do
α = f
12
(x, y)/f
α
β = f
20
(x, y)/f
β
γ = f
01
(x, y)/f
γ
if (α ≥ 0 and β ≥ 0 and γ ≥ 0) then
if (α>0 or f
α
f
12
(−1, −1) > 0) and (β>0 or f
β
f
20
(−1, −1) > 0)
and (γ>0 or f
γ
f
01
(−1, −1) > 0) then
c = αc
0
+ βc
1
+ γc
2
drawpixel (x, y) with color c
We might expect that the above code would work to eliminate holes and double-
draws only if we use exactly the same line equation for both triangles. In fact,
the line equation is the same only if the two shared vertices have the same order
in the draw call for each triangle. Otherwise the equation might flip in sign. This
could be a problem depending on whether the compiler changes the order of op-
erations. So if a robust implementation is needed, the details of the compiler and
arithmetic unit may need to be examined. The first four lines in the pseudocode
above must be coded carefully to handle cases where the edge exactly hits the
pixel center.
In addition to being amenable to an incremental implementation, there are
several potential early exit points. For example, if α is negative, there is no need
to compute β or γ. While this may well result in a speed improvement, profiling is
always a good idea; the extra branchescould reduce pipeliningor concurrencyand
might slow down the code. So as always, test any attractive-looking optimizations
if the code is a critical section.
Another detail of the above code is that the divisions could be divisions by
zero for degenerate triangles, i.e., if f
γ
=0. Either the floating point error condi-
tions should be accounted for properly, or another test will be needed.
8.1.3 Clipping
Simply transforming primitives into screen space and rasterizing them does not
quite work by itself. This is because primitives that are outside the view volume—
i
i
i
i
i
i
i
i
170 8. The Graphics Pipeline
z=f
z=n
z'
z
n
f
n+f
eye
gaze
direction
eye
gaze
direction
a
b
c
a’
b’
c’
Figure 8.7. The depth
z
is transformed to the depth
z
by the perspective transform. Note
that when
z
moves from positive to negative,
z
switches from negative to positive. Thus
vertices behind the eye are moved in front of the eye beyond
z
=
n
+
f
. This will lead to
wrong results, which is why the triangle is first clipped to ensure all vertices are in front of the
eye.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.