A geometric line, circle or ellipse is made up of infinitely many points, but a screen can only turn on pixels sitting at integer coordinates. Converting a continuous shape into the discrete set of pixels that best approximates it is called rasterization, or - specifically for a line segment - vector generation. A good rasterization algorithm has to satisfy three practical requirements: the shape must start and end exactly at the given coordinates, it must appear with constant, direction-independent brightness along its whole length, and it must be fast enough to run once for every pixel of every shape on the screen.
The last requirement rules out anything involving square roots, trigonometric functions or even division inside the per-pixel loop. Every algorithm in this chapter is built around the same trick to get there: instead of evaluating the true, continuous equation of the shape at every pixel, an integer-valued decision variable is updated incrementally from one pixel to the next, so that only its sign needs to be checked.
Horizontal and vertical lines rasterize perfectly: every pixel touches exactly one neighbor along the line, so the line has constant width. A 45° line is almost as good, since consecutive pixels touch diagonally. Any other slope, however, forces some pixels to repeat a row or column before the next one starts (as in the third plot above), which is why an arbitrary line looks slightly thicker or fainter than a horizontal, vertical or 45° line of the same length - an effect no rasterization algorithm can fully remove, only manage.
The Line Through Two Points
Two distinct points \(P_1=(x_1,y_1)\) and \(P_2=(x_2,y_2)\) determine a unique line. Writing \(\Delta x=x_2-x_1\) and \(\Delta y=y_2-y_1\) for the horizontal and vertical distance between them, any third point \((x,y)\) lies on that line iff the triangle it forms with \(P_1\) has the same ratio of vertical to horizontal side as the triangle formed by \(P_2\):
\[ \frac{y-y_1}{x-x_1}=\frac{\Delta y}{\Delta x}=:m\qquad(x_1\neq x_2). \]
The ratio \(m\) is the slope of the line: how much \(y\) changes per unit of \(x\). Multiplying through by \(x-x_1\) gives the point-slope form
\[ y=y_1+m(x-x_1), \]
and expanding the product and collecting the constant terms into \(b=y_1-mx_1\) gives the familiar slope-intercept form
\[ \boxed{y=mx+b}. \]
If \(x_1=x_2\), the slope is undefined - the line is vertical and has the much simpler equation \(x=x_1\), which cannot be written as \(y=mx+b\) for any finite \(m\). This edge case reappears throughout the chapter and always needs a small amount of special handling.
Intersection of Two Lines
Given two non-vertical lines \(y=m_1x+b_1\) and \(y=m_2x+b_2\), a shared point \((x_S,y_S)\) must satisfy both equations at once, so their right-hand sides must be equal at \(x=x_S\):
\[ m_1x_S+b_1=m_2x_S+b_2 \;\Longrightarrow\; x_S(m_1-m_2)=b_2-b_1. \]
As long as \(m_1\neq m_2\), dividing by \(m_1-m_2\) and substituting back into either line's equation gives the intersection point in closed form:
\[ \boxed{ x_S=\frac{b_2-b_1}{m_1-m_2}, \qquad y_S=m_1x_S+b_1=\frac{m_1b_2-m_2b_1}{m_1-m_2}. } \]
If \(m_1=m_2\), the two lines rise at the same rate and never meet unless they are the exact same line (\(b_1=b_2\), in which case every point is shared) - otherwise they are parallel and the division by \(m_1-m_2=0\) correctly signals that no solution exists. If either line is vertical, its slope is undefined rather than merely equal to the other line's, so this slope-based formula does not apply directly; substituting \(x=x_1\) into the other line's equation gives \(y_S\) just as easily in that case.
From Equation to Pixels
The equation \(y=mx+b\) describes infinitely many real-valued points, while a screen only has pixels at integer coordinates \((x,y)\in\mathbb{Z}^2\). The most direct rasterization strategy computes \(y=mx+b\) for every integer \(x\) between the endpoints and rounds the result - but every evaluation needs a multiplication, and every result needs a rounding step, both of which were historically expensive relative to a simple addition or comparison. The rest of this section removes first the multiplication, then the rounding, one algorithm at a time.
The Digital Differential Analyzer (DDA)
The DDA algorithm avoids re-evaluating \(y=mx+b\) from scratch at every pixel by stepping both coordinates by a small constant amount instead. The number of pixels needed is the larger of the horizontal and vertical spans,
\[ \text{length}=\max(|\Delta x|,|\Delta y|), \]
since a line can never need more steps than its longest coordinate span without skipping or repeating a pixel. Dividing the full displacement by that many steps gives the per-step increment in both directions,
\[ \delta x=\frac{\Delta x}{\text{length}}, \qquad \delta y=\frac{\Delta y}{\text{length}}, \]
so that exactly one of \(\delta x,\delta y\) is \(\pm 1\) and the other is a fraction with magnitude at most \(1\). Starting at \((x_1,y_1)\) and repeatedly adding \((\delta x,\delta y)\) for \(\text{length}\) steps, then rounding each intermediate point to the nearest pixel, produces the rasterized line:
function rasterizeDDA(x1, y1, x2, y2) {
const dx = x2 - x1;
const dy = y2 - y1;
const length = Math.max(Math.abs(dx), Math.abs(dy));
const stepX = dx / length;
const stepY = dy / length;
const points = [];
let x = x1;
let y = y1;
for (let i = 0; i <= length; i++) {
points.push([Math.round(x), Math.round(y)]);
x += stepX;
y += stepY;
}
return points;
} For the line from \((0,0)\) to \((6,6)\), \(\Delta x=\Delta y=6\), so \(\text{length}=6\) and \(\delta x=\delta y=1\): the algorithm visits \((0,0),(1,1),\dots,(6,6)\), exactly the diagonal pixels drawn in the second plot above.
The DDA algorithm is simple, but it still runs on floating-point coordinates and rounds every single point, which is both comparatively slow and prone to accumulating rounding error over a long line. Bresenham's algorithm below reaches the same pixels using only integers.
Bresenham's Line Algorithm
Consider first a line with \(x_1<x_2\) and a slope between \(0\) and \(1\), i.e. \(0\leq\Delta y\leq\Delta x\). Since the slope cannot exceed \(1\), moving from one pixel to the next always increases \(x\) by exactly \(1\), while \(y\) either stays the same or also increases by \(1\) - there is never a reason to skip a row. So from a current pixel \(P_k=(x_k,y_k)\), only two candidates are possible for the next pixel:
\[ E=(x_k+1,\,y_k) \qquad\text{and}\qquad NE=(x_k+1,\,y_k+1). \]
Whichever of the two lies closer to the true line is the better pixel. Both share the same \(x\)-coordinate, so comparing their distance to the line reduces to comparing their \(y\)-coordinate to the line's exact height at \(x_k+1\). The implicit form of the line, obtained by clearing denominators in \(\frac{y-y_1}{x-x_1}=\frac{\Delta y}{\Delta x}\), makes that comparison possible without ever computing that height explicitly:
\[ F(x,y):=\Delta y\,(x-x_1)-\Delta x\,(y-y_1). \]
\(F(x,y)=0\) exactly on the line, and since \(F\) decreases as \(y\) grows (its \(y\)-coefficient \(-\Delta x\) is negative), \(F\) is positive below the line and negative above it. Evaluating \(F\) at the midpoint \(M=(x_k+1,\,y_k+\tfrac12)\) between \(E\) and \(NE\) therefore decides which one is closer: if \(F(M)>0\), the line passes above \(M\), so \(NE\) is the better choice; if \(F(M)<0\), \(E\) is.
To keep every quantity an integer, the decision variable is defined as twice this value,
\[ p_k:=2F(x_k+1,\,y_k+\tfrac12)=2\Delta y\,(x_k-x_1+1)-\Delta x\,(2y_k-2y_1+1), \]
which is always a whole number because \(\Delta x,\Delta y,x_1,y_1\) are integers and the \(\tfrac12\) cancels against the factor \(2\) multiplying \(\Delta x\). At the very first pixel, \(x_k=x_1\) and \(y_k=y_1\), so
\[ \boxed{p_0=2\Delta y-\Delta x}. \]
Substituting \(x_{k+1}=x_k+1\) into \(p_k\)'s definition shows how the decision variable changes from one step to the next without recomputing it from scratch. If \(E\) was chosen (\(y\) unchanged),
\[ p_{k+1}=p_k+2\Delta y, \]
and if \(NE\) was chosen (\(y_{k+1}=y_k+1\)), the extra \(-\Delta x\cdot 2\) term from the shift in \(y\) gives
\[ p_{k+1}=p_k+2\Delta y-2\Delta x. \]
Restricted to \(0\leq\Delta y\leq\Delta x\) and \(x_1<x_2\), the algorithm is therefore:
dx = x2 - x1
dy = y2 - y1
x = x1
y = y1
p = 2 * dy - dx
plot(x, y)
while (x < x2) {
x = x + 1
if (p >= 0) {
y = y + 1
p = p + 2 * dy - 2 * dx
} else {
p = p + 2 * dy
}
plot(x, y)
} Worked Example
Rasterize the line from \((5,5)\) to \((13,9)\): \(\Delta x=8\), \(\Delta y=4\), so \(p_0=2\cdot4-8=0\). Since \(p_0\geq0\), the very first step already picks \(NE\):
| \(k\) | pixel | \(p_k\) | choice |
|---|---|---|---|
| 0 | (5, 5) | 0 | NE |
| 1 | (6, 6) | -8 | E |
| 2 | (7, 6) | 0 | NE |
| 3 | (8, 7) | -8 | E |
| 4 | (9, 7) | 0 | NE |
| 5 | (10, 8) | -8 | E |
| 6 | (11, 8) | 0 | NE |
| 7 | (12, 9) | -8 | E |
| 8 | (13, 9) | - | done |
The decision variable alternates between \(0\) and \(-8\) because the slope \(\tfrac12\) is exact: every other candidate midpoint lands precisely between two lattice rows, and the algorithm's tie-breaking rule (\(p_k\geq0\Rightarrow NE\)) consistently rounds those ties up.
All Eight Octants
A line can point in any of eight directions depending on the signs of \(\Delta x,\Delta y\) and whether \(|\Delta y|\leq|\Delta x|\) or not. Every octant reduces to the case above by the same kind of symmetry argument used for the circle and ellipse later in this chapter: swapping the roles of \(x\) and \(y\) handles the steep octants (\(|\Delta y|>|\Delta x|\)), and stepping by \(-1\) instead of \(+1\) handles a line whose second point lies to the left of or below the first. Working with \(|\Delta x|,|\Delta y|\) and a per-axis step direction folds all eight cases into one implementation:
function rasterizeLine(x1, y1, x2, y2) {
const dx = Math.abs(x2 - x1);
const dy = Math.abs(y2 - y1);
const sx = x2 > x1 ? 1 : -1;
const sy = y2 > y1 ? 1 : -1;
const steep = dy > dx;
let x = x1, y = y1;
let p = steep ? 2 * dx - dy : 2 * dy - dx;
const points = [[x, y]];
const length = steep ? dy : dx;
for (let i = 0; i < length; i++) {
if (steep) {
y += sy;
if (p >= 0) { x += sx; p += 2 * dx - 2 * dy; }
else { p += 2 * dx; }
} else {
x += sx;
if (p >= 0) { y += sy; p += 2 * dy - 2 * dx; }
else { p += 2 * dy; }
}
points.push([x, y]);
}
return points;
} Circle Rasterization
A circle of radius \(r\) centered at the origin is the set of points satisfying
\[ x^2+y^2=r^2. \]
Solving for \(y=\pm\sqrt{r^2-x^2}\) and stepping \(x\) from \(-r\) to \(r\) works, but it needs a square root at every pixel, and near \(x=\pm r\) the tangent is nearly vertical, so consecutive integer values of \(x\) jump over several rows of \(y\) at once, leaving visible gaps.
Eight-Way Symmetry
A circle centered at the origin is unchanged by reflecting across either axis or the line \(y=x\). Consequently, if \((x,y)\) lies on the circle, so do all of
\[ (\pm x,\pm y) \qquad\text{and}\qquad (\pm y,\pm x), \]
eight points in total (fewer if \(x=0\), \(y=0\) or \(x=y\)). It is enough to rasterize the single \(45°\) octant from \((0,r)\) to where \(x=y\), and mirror every plotted pixel into the other seven positions:
The Midpoint Circle Algorithm
Within that octant (\(0\leq x\leq y\)), moving from a pixel \((x,y)\) with \(x\) incremented by \(1\) again leaves only two candidates for the next pixel, exactly as with the line:
\[ E=(x+1,\,y) \qquad\text{and}\qquad SE=(x+1,\,y-1). \]
Instead of testing a fractional midpoint as with the line, both candidates' squared distances to the center are compared directly against \(r^2\):
\[ D_E:=(x+1)^2+y^2-r^2, \qquad D_{SE}:=(x+1)^2+(y-1)^2-r^2. \]
Throughout this octant, \(E\) lies on or outside the circle (\(D_E\geq0\)) and \(SE\) lies on or inside it (\(D_{SE}\leq0\)), because moving right without moving down can only increase the distance to the center, while moving down without moving right can only decrease it. \(E\) is therefore the closer pixel exactly when its (non-negative) error is smaller than \(SE\)'s (non-positive) error's absolute value, i.e. when \(D_E<-D_{SE}\), or equivalently when their sum is negative. That sum is the decision variable:
\[ d:=D_E+D_{SE}=2(x+1)^2+2y^2-2y+1-2r^2. \]
At the starting pixel \((x,y)=(0,r)\), this evaluates to
\[ \boxed{d_0=3-2r}. \]
Expanding \(d\) at \((x+1,y)\) - i.e. after choosing \(E\), where \(y\) is unchanged - against its value at \((x,y)\) leaves only linear terms in \(x\):
\[ d_{\text{new}}=d+4x+6\qquad(\text{if }d<0,\text{ i.e. }E\text{ chosen}). \]
Doing the same after choosing \(SE\) (both \(x\) and \(y\) change) gives
\[ d_{\text{new}}=d+4(x-y)+10\qquad(\text{if }d\geq0,\text{ i.e. }SE\text{ chosen, and }y=y-1). \]
Both updates only ever touch \(x\), \(y\) and \(d\) with additions, so the whole algorithm runs without a single multiplication, division or square root once \(d_0\) is known:
function rasterizeCircleOctant(r) {
let x = 0, y = r;
let d = 3 - 2 * r;
const points = [];
while (x <= y) {
points.push([x, y]);
if (d < 0) {
d += 4 * x + 6;
} else {
d += 4 * (x - y) + 10;
y -= 1;
}
x += 1;
}
return points;
}
function rasterizeCircle(cx, cy, r) {
const points = [];
for (const [x, y] of rasterizeCircleOctant(r)) {
points.push(
[cx + x, cy + y], [cx + y, cy + x],
[cx - x, cy + y], [cx - y, cy + x],
[cx + x, cy - y], [cx + y, cy - x],
[cx - x, cy - y], [cx - y, cy - x],
);
}
return points;
} As a check, \(r=5\) gives \(d_0=3-2\cdot5=-7\), and tracing the loop plots \((0,5),(1,5),(2,5),(3,4)\) before \(x>y\) stops it - matching \(\sqrt{25}=5\), \(\sqrt{24}\approx4.90\), \(\sqrt{21}\approx4.58\) (closer to \(5\) than to \(4\)) and \(\sqrt{16}=4\) exactly, confirming that every plotted \(y\) really is the nearest integer to the true circle at that \(x\).
Ellipse Rasterization
An axis-aligned ellipse centered at the origin with horizontal semi-axis \(r_x\) and vertical semi-axis \(r_y\) satisfies
\[ \frac{x^2}{r_x^2}+\frac{y^2}{r_y^2}=1, \]
or, after clearing denominators, the implicit form
\[ F(x,y):=r_y^2x^2+r_x^2y^2-r_x^2r_y^2. \]
Unlike a circle, an ellipse only has two-fold symmetry across each axis (four points \((\pm x,\pm y)\) per computed pixel), since \(r_x\neq r_y\) breaks the extra diagonal symmetry a circle has. It also has two visually different regions instead of one octant: the curve is nearly flat close to \((0,r_y)\) and nearly vertical close to \((r_x,0)\), so a single stepping rule cannot cover the whole quarter without either wasting pixels or leaving gaps.
The two regions are separated by the point where the tangent has slope \(-1\). Implicit differentiation of \(F(x,y)=0\) gives \(\frac{dy}{dx}=-\frac{r_y^2x}{r_x^2y}\), so the boundary sits where \(r_y^2x=r_x^2y\):
- Region 1 (\(r_y^2x<r_x^2y\), near the top): the curve is flatter than \(45°\), so \(x\) is incremented every step, choosing between \(E=(x+1,y)\) and \(SE=(x+1,y-1)\) exactly as for the circle, using \(F\) at the midpoint \((x+1,\,y-\tfrac12)\).
- Region 2 (\(r_y^2x\geq r_x^2y\), near the right): the curve is steeper than \(45°\), so the roles of \(x\) and \(y\) swap - \(y\) is decremented every step, choosing between \(S=(x,y-1)\) and \(SW=(x-1,y-1)\), using \(F\) at the midpoint \((x-\tfrac12,\,y-1)\).
Starting at \((0,r_y)\), the region 1 decision variable is \(p_1=F(1,\,r_y-\tfrac12)\), which expands to
\[ \boxed{p_1=r_y^2-r_x^2r_y+\tfrac14r_x^2}. \]
The same incremental-difference technique used for the line and the circle - substituting the updated \(x\) or \(y\) back into \(F\) at the shifted midpoint and cancelling the terms shared with the previous step - gives an \(O(1)\) update in both regions, and the region switches exactly once the midpoint test crosses the \(r_y^2x=r_x^2y\) boundary:
function rasterizeEllipseQuadrant(rx, ry) {
const rx2 = rx * rx;
const ry2 = ry * ry;
const points = [];
let x = 0, y = ry;
let p1 = ry2 - rx2 * ry + 0.25 * rx2;
// Region 1: flatter than 45 degrees
while (rx2 * y > ry2 * x) {
points.push([x, y]);
if (p1 < 0) {
x += 1;
p1 += 2 * ry2 * x + ry2;
} else {
x += 1;
y -= 1;
p1 += 2 * ry2 * x - 2 * rx2 * y + ry2;
}
}
// Region 2: steeper than 45 degrees
let p2 = ry2 * (x + 0.5) * (x + 0.5) + rx2 * (y - 1) * (y - 1) - rx2 * ry2;
while (y >= 0) {
points.push([x, y]);
if (p2 > 0) {
y -= 1;
p2 += rx2 - 2 * rx2 * y;
} else {
y -= 1;
x += 1;
p2 += 2 * ry2 * x - 2 * rx2 * y + rx2;
}
}
return points;
} The Common Principle
Every algorithm in this chapter follows the same four-step pattern:
- Write the shape as an implicit equation \(F(x,y)=0\).
- At each step, exactly two neighboring pixels are candidates for the next point.
- Evaluate \(F\) at the point exactly between the two candidates; its sign decides which one is closer to the true shape.
- Instead of recomputing \(F\) from scratch, update the previous value using only the difference introduced by the single pixel step just taken.
This turns a per-pixel computation that would otherwise need a division (line), a square root (circle) or both plus a trigonometric function (ellipse) into a handful of integer additions, which is exactly why these decision-variable algorithms, and not the direct equations they are derived from, are what actual rasterizers use.
References
- Bresenham65J. E. Bresenham (1965) Algorithm for Computer Control of a Digital Plotter, IBM Systems Journal, 4(1), 25-30
- FoleyVanDamJ. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes (1990) Computer Graphics: Principles and Practice, 2nd edition, Addison-Wesley
- VanAken84J. R. Van Aken (1984) An Efficient Ellipse-Drawing Algorithm, IEEE Computer Graphics and Applications, 4(9), 24-35