1 DDA (Obsolete)

Triangles are rasterized by finding all of the integer-coordinate points inside the three edges of the triangle¹. 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.

Input

Two $n$ -dimensional endpoints, $\vec a$ and $\vec b$
The dimension $d$ that should have integer coordinates

Output

A set of points $\vec p$ where each $p_d$ is an integer

Process

Setup:

If $a_d = b_d$ , return the empty set
If $a_d > b_d$ , swap $\vec a$ and $\vec b$
Let $\vec \Delta = \vec b - \vec a$
Let $\vec s = \vec \Delta \div \Delta_d$

Find the first potential point:

Let $e = \lceil a_d \rceil - a_d$
Let $\vec o = e \vec s$
Initialize $\vec p$ as $\vec a + \vec o$

Find all points:

While $p_d < b_d$ repeat:
1. add $\vec p$ to the set to be returned
2. add $\vec s$ to $\vec p$

Discussion

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.

Rasterization of a triangle by first DDA-stepping the edges in

y

, then DDA-stepping between points on the edges in

x

. Using the notation in the DDA algorithm above: blue lines are

\vec o

y

and green lines are

\vec s

y

; red lines are

\vec o

x

and purple lines are

\vec s

x

2 Bresenham (Current)

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.

3 Linear (Obsolete)

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:

On the left is a trapezoid divided at equally-spaced points in

x

using linear interpolation. On the right is a rectangle seen in perspective, divided at equally-spaced points along its length using hyperbolic interpolation.

If we use linear interpolation in 2D screen space, everything looking 2D and flat. This can be fixed by interpolating in hyperbolic coordinates instead.

4 Hyperbolic (Current)

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)$ .

5 Textures

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.

Normalized texture coordinates: Most applications of textures assume texture coordinates are normalized to a 0–1 range regardless of texture size. Thus, if a texture coordinate is $(0.2, 0.5)$ and the texture image is 300×500 texels² in size then we look up the texel with coordinates $(60, 250)$ .
Wrapping: There are various options for what to do with a texture coordinate outside the 0–1 range; the most common is to wrap them, treating 1.2 as 0.2 and -0.3 as 0.7.
Interpolation and mipmaps: Naive texture lookups have a whole range of aliasing problems. Full implementations will store multiple sizes of the texture, called mipmaps, selecting the size to approximately achieve one texel per fragment, and will interpolate between texture sizes and surrounding texels to minimize that aliasing. The full details are outside the scope of this page.
Replace or combine: There are many values that could be stored in a texture, but simple texture mapping stores object color. If the texture contains an alpha channel, using that alpha for the fragment can allow parts of a triangle to be transparent and other parts opaque, increasing the apparent complexity of the geometry. Sometimes instead the texture is treated as a decal, adjusting the color only for a part of the triangle, and the alpha is composited on top of the interpolated object color.

Because abutting triangles are often used to represent more complicated shapes, special care is taken to insure abutting triangles draw each pixel exactly once. In particular, if an edge passes through an integer coordinate point $(x,y)$ , the point is considered inside the triangle if either $(x+\epsilon,y)$ is inside and not on an edge or if $(x+\epsilon,y)$ is inside on an edge and $(x+\epsilon,y+\epsilon)$ is inside and not on an edge, for infinitesimally small positive $\epsilon$ .

In the DDA algorithm, this abutment-handling rule informs the $<$ (instead of $\le$ ) condition of the loop, the ordering of $\vec a$ and $\vec b$ and the resulting use of $s_d = 1$ (instead of $-1$ ), and the computation of $e$ using ceiling (instead of floor).↩︎
pixels in a texture are usually called texels instead↩︎