Triangles are rasterized by finding all of the integer-coordinate points inside the three edges of the triangle1. For each such point, we also wish to interpolate an arbitrary number of other values to that point. We can both find these points and interpolate to them very efficiently using either the DDA algorithm or its rational-number cousin the Bresenham algorithm. As both are similar and you’re likely more familiar with working in real numbers than in rational numbers, we’ll discuss DDA here.
The DDA algorithm takes an n-dimensional line segment, specified by its two the n-vector end points, and finds all points on that line segment that have an integer coordinate in one particular dimension.
DDA
Officially, DDA stands for digital differential analyzer
but
I’ve never heard that name used except in explanatory texts like this
one. It’s always called DDA
, the DDA algorithm,
or the
DDA line-drawing algorithm.
Setup:
Find the first potential point:
Find all points:
Working backwards,
Given a point \vec p on the line segment with integer p_d, \vec p + \vec s is the next point on the line segment with integer p_d as long as both \vec s is aligned with the segment and s_d = 1. So once we have one \vec p and \vec s, we just loop through adding \vec s to \vec p until we leave the segment (8).
To get \vec s we start with a vector aligned with the line segment by simple subtraction (3) and then get s_d = 1 by dividing the entire vector by whatever it’s d coordinate is (4).
Any time we have division, we have to consider division by zero. In this case division by zero would happen if the line has no extent in the d direction, meaning there are either 0 or \infty points on the line with integer d; in either case, we can simply return the empty set: no meaningful points (1).
To get the initial \vec p we need to figure out how far the starting end of the segment is from an integer d coordinate (e, 5) make a vector offset that will move us to that point (\vec o with o_d = e, 6) and add that offset to the starting end of the segment (7).
All of this assumed we were stepping in the positive d direction, so we swap the order of the segment endpoints if needed to make sure that’s the case (2).
The scanline algorithm uses DDA to find the pixels in a triangle by first using DDA in y (i.e., finding points with integer y values) on the three edge line segments; then using DDA in x between pairs of points found this way that share the same y value.
Bresenham’s line algorithm achieves the same results as DDA, but using only integer values. Because it uses only integers, it is both faster (integer arithmetic requires less hardware than floating-point hardware) and more precise (no rounding error) than DDA. It works on integer, rational, and fixed-point endpoints and outputs. Because of its efficiency and precision, it is commonly used in graphics hardware.
Bresenham’s line algorithm can be derived by writing out DDA using rational numbers and tracking the integral and fractional parts of each number separately. The result is less intuitive and more complicated code than DDA, but simpler and smaller hardware because the individual components require many fewer transistors.
Jack Elton Bresenham derived this algorithm not as a form of DDA, but rather by considering the implicit equation for a line, and also showed how it could draw other polygonal curves such as circles. Those generalizations are suitable for hardware implementation, but are not commonly implemented in hardware.
A naive implementation of DDA or Bresenham performs linear interpolation of values across a line or triangle. That means in particular that if one end of a line is at x=0 and has a red value of r=0 and the other end is at x=100 and has r=1 then at x=50 the interpolated r will be 0.5.
While linear interpolation may seem intuitive, it is incorrect when paired with projection. To see this, consider the following two images:
If we use linear interpolation in 2D screen space, everything looking 2D and flat. This can be fixed by interpolating in hyperbolic coordinates instead.
In 1992 Jim Blinn wrote a paper explaining how interpolation could be made perspective-correct using something called hyperbolic interpolation; all graphics hardware now uses his approach.
Hyperbolic interpolation assumes that three components of the vector of values at each vertex of a triangle are special. x and y are special because they correspond to pixel locations; and w is special because in homogeneous coordinates they are used to create frustums and perspective projection. It is traditional to also treat z as special because it gives better [depth buffer] precision for up-close objects where errors would be more visible.
Suppose we have a supplied vertex coordinate (x,y,z,w,r,g,b,s,t). We first perform perspective projection in x and y by dividing by w; we also divide everyithing else by w while we’re at it, getting \left(\dfrac{x}{w},\dfrac{y}{w},\dfrac{z}{w},\dfrac{1}{w},\dfrac{r}{w},\dfrac{g}{w},\dfrac{b}{w},\dfrac{s}{w},\dfrac{t}{w}\right). Note that w is replaced by 1 \div w not w \div w. We use these divided coordinates in DDA to get a pixel coordinate (x',y',z',w',r',g',b',s',t'). The x' and y' are the correct pixel x and y and the z' is the depth we use in the depth buffer, but the rest of the coordinates had a spurious division by w which we now undo to get \left(x',y',z',\dfrac{1}{w'},\dfrac{r'}{w'},\dfrac{g'}{w'},\dfrac{b'}{w'},\dfrac{s'}{w'},\dfrac{t'}{w'}\right).
Hyperbolic interpolation
Consider the two points (12,0,6,3, 150, 30, 0) and (2,0,-6,1, 0, 30, 150).
Division by w gives (4,0,2,\frac{1}{3}, 50, 10, 0) and (2,0,-6,1, 0, 30, 150).
Interpolation to the midpoint gives (3,0,-2,\frac{2}{3}, 25, 20, 75).
Multiplication by the interpolated \frac{1}{w} gives (3,0,-2,1.5,37.5,30,112.5).
It is common to wish to provide color and other material properties
at a different resolution than geometry. The usual way to realize this
is by (a) interpolating texture coordinates
to each fragment and
(b) at each fragment looking up the color and so on at those coordinates
in an image or array called a texture
. We have a separate page on using Textures in WebGL and
one on various applications of textures;
this section covers only basic texture lookups.
decal, adjusting the color only for a part of the triangle, and the alpha is composited on top of the interpolated object color.