[Intermediate] — Scan-converting a line: the naive algorithm, DDA, Bresenham (both slopes, derived in full), the midpoint view, building shapes and dashed lines from the line primitive, and how antialiasing softens the staircase.
Part 1 of the course, after note 01. This is the most-examined topic in SSG 511 — the Bresenham derivation for slope > 1 alone is worth 15 marks.
Before you start
You can use setpixel(x, y, colour) on a grid (note 01), find a line’s slope , and write a Python for loop.
After this note you will be able to:
- Explain why line algorithms matter and give three reasons Bresenham beats DDA.
- Derive Bresenham’s decision parameter for and , including .
- Trace a Bresenham table by hand for any line, and check it against code.
- Explain four antialiasing methods and their trade-off.
The kid version
You want to draw a diagonal line on squared paper, but you are only allowed to colour whole squares. Walk along the long direction one square at a time. At each step, ask one question: “is the true line closer to the square I’m level with, or to the one just above?” Colour the closer one. Bresenham’s trick is that you can answer that question by keeping a running score and only ever adding whole numbers to it.
Where the analogy stops working. On paper you can see which square is closer. The computer cannot; it needs the score (the decision parameter) precisely because comparing the real distances would need fractions.
Terms used in line drawing
- Scan conversion: This is the turning of a geometric line into the set of pixels that approximates it.
- Slope: This is also known as the gradient, written . This is how much changes for each unit change in : .
- Shallow line: This is a line with . It changes more in than in , so it is stepped along .
- Steep line: This is a line with . It changes more in than in , so it is stepped along .
- DDA: The letters stand for digital differential analyser. This is the line algorithm that steps one pixel along the longer axis and adds a constant fractional increment on the other.
- Decision parameter: This is the integer whose sign tells Bresenham which of two candidate pixels to colour next.
- Aliasing: This is the jagged, stair-step look of a smooth edge drawn on a pixel grid, caused by sampling a continuous shape at too few points.
- Antialiasing: This is any technique that reduces aliasing, usually by shading edge pixels with in-between intensities.
1. Why line and curve algorithms matter
Every picture on a raster screen is built from lines and curves, and the screen is a grid, so every line or curve must be scan-converted. It happens thousands to millions of times per picture, so the algorithm must be:
- Fast — to keep interaction smooth (the feedback loop).
- Accurate — the line looks straight and hits its end points.
- Simple — simple enough to build into hardware.
A good line should be straight and pass through both end points, be independent of point order (A→B lights the same pixels as B→A), and be uniformly bright whatever its slope.
2. The naive algorithm, and its three problems
The line equation says is the slope times the distance along , plus the starting height.
m = (y1 - y0) / (x1 - x0)
for (x = x0; x <= x1; ++x) {
y = m * (x - x0) + y0
setpixel(x, round(y), linecolor)
}
| Problem | Fix |
|---|---|
| If , nothing is drawn | Swap the points |
| For , too few pixels are lit — the line has gaps and looks dimmer | When loop over , with |
| Inefficient: a float multiply and a round per pixel | Bresenham |
Why stepping the wrong axis leaves gaps: for to , stepping gives 3 pixels for a line that spans 7 rows. Stepping gives steps = 6, , — no gaps.
3. DDA
Step one pixel along the longer axis, and add a constant increment on the other.
- , .
- .
- , .
- Start at and plot
(round(x), round(y)). - Repeat
stepstimes: , , plot.
The three cases fall out of step 2 automatically — you never need to find the slope first:
| Case | Condition | increment | increment |
|---|---|---|---|
| 1 | (more horizontal) | 1 | |
| 2 | (more vertical) | 1 | |
| 3 | 1 | 1 |
For a slope below 1, it is that increases by 1 every step — not . Getting this backwards is the most common DDA mistake. And write the update as , not "".
Good: simple, every slope, only additions per pixel. Bad: floating point, a rounding every step, and round-off error accumulates on long lines so pixels drift off the true line.
Worked — to : , , steps , , .
| i | x | y | pixel |
|---|---|---|---|
| 0 | 0 | 1 | (0, 1) |
| 1 | 1 | 1.8 | (1, 2) |
| 2 | 2 | 2.6 | (2, 3) |
| 3 | 3 | 3.4 | (3, 3) |
| 4 | 4 | 4.2 | (4, 4) |
| 5 | 5 | 5.0 | (5, 5) |
Worked — to : , . The values round to — the same pixels Bresenham gives below.
DDA program
# dda.py — run: python3 dda.py, then type: 1 1 6 4
import math
def dda(x0, y0, x1, y1):
dx, dy = x1 - x0, y1 - y0
steps = max(abs(dx), abs(dy))
if steps == 0:
return [(x0, y0)]
xinc, yinc = dx / steps, dy / steps
x, y = x0, y0
pixels = [(math.floor(x + 0.5), math.floor(y + 0.5))]
for _ in range(steps):
x += xinc
y += yinc
pixels.append((math.floor(x + 0.5), math.floor(y + 0.5)))
return pixels
x0, y0, x1, y1 = map(int, input("x0 y0 x1 y1: ").split())
print(dda(x0, y0, x1, y1))Expected: 1 1 6 4 → [(1, 1), (2, 2), (3, 2), (4, 3), (5, 3), (6, 4)].
Use
math.floor(x + 0.5), notround. Python’sroundrounds halves to the nearest even number (round(2.5) == 2), which can move a pixel.
4. Bresenham’s line algorithm
Bresenham uses only integers. At each step it picks whichever of two candidate pixels is closer to the true line, using the sign of a decision parameter .
Three reasons it is preferred over DDA:
- Integer arithmetic only — additions, subtractions and doubling; no floating point, no rounding.
- Faster and cheaper per pixel, and easy to build into hardware.
- More accurate — no accumulated round-off, and it always picks the pixel closest to the true line.
Derivation for (shallow, step in )
Let , , with . Suppose pixel has just been plotted. At column the true line has height , and the two candidates are the lower pixel and the upper pixel .
y_k+1 ┤ ·········□ upper d_upper = (y_k + 1) − y
│ ╱ ↕ d_upper
y ┤······● ← true line at x_k+1
│ ╱ ↕ d_lower
y_k ┤ ■ ········□ lower d_lower = y − y_k
└─┬─────────┬───
x_k x_k+1
Choose the lower pixel when it is closer, that is when :
This still contains the fraction . Multiply by — positive, so the sign is unchanged — and substitute . That product is the decision parameter:
- If , plot .
- If , plot .
The update. Subtract from ; the constant cancels:
Since always moves by 1, the update depends only on whether moved:
The start value. Put into with (the line passes through the start point). Everything cancels except:
Derivation for (steep, step in ) — the exam question
Swap the roles of and . Now . Step by 1 each time, and decide whether stays or increases by 1. Having plotted , at row the true line is at . The candidates are the left pixel and the right pixel .
row y_k+1: □ left ←d_left→ ● ←d_right→ □ right
x_k x x_k+1
row y_k: ■ (just plotted)
Multiply by (positive) and use :
Other cases. For negative slopes, work with and and step or by instead of (the sx, sy signs in the code below). Horizontal, vertical and 45° lines are special cases of the same rules.
Worked — steep line to
, , , so step . . Updates: ( stays) or ( goes up).
| k | Decision | Plot | ||
|---|---|---|---|---|
| start | (2, 1) | |||
| 0 | −1 | , stays | (2, 2) | −1 + 6 = 5 |
| 1 | 5 | , | (3, 3) | 5 − 8 = −3 |
| 2 | −3 | stays | (3, 4) | 3 |
| 3 | 3 | (4, 5) | −5 | |
| 4 | −5 | stays | (4, 6) | 1 |
| 5 | 1 | (5, 7) | −7 | |
| 6 | −7 | stays | (5, 8) | end |
There are pixels, one per row. To check, plot them on a grid and draw the true line over the top: no pixel is more than half a pixel away.
Worked — shallow line to
, , . Updates: ( stays) or ( up).
| k | Decision | Plot | ||
|---|---|---|---|---|
| start | (2, 3) | |||
| 0 | 3 | (3, 4) | −1 | |
| 1 | −1 | stays | (4, 4) | 9 |
| 2 | 9 | (5, 5) | 5 | |
| 3 | 5 | (6, 6) | 1 | |
| 4 | 1 | (7, 7) | −3 | |
| 5 | −3 | stays | (8, 7) | 7 |
| 6 | 7 | (9, 8) | end |
Worked — class example to
, , . Add when , add when .
| x | p | y moves? | pixel |
|---|---|---|---|
| 1 | 1 (≥ 0) | up | (1, 1) |
| 2 | −5 | stays | (2, 2) |
| 3 | 3 | up | (3, 2) |
| 4 | −3 | stays | (4, 3) |
| 5 | 5 | up | (5, 3) |
| 6 | −1 | stays | (6, 4) |
| 7 | 7 | up | (7, 4) |
| 8 | (done) | (8, 5) |
The end point is , so — not 8.
Worked — steep, going left: to
, : step ; moves left (). . If : , stays. If : , . Then .
| k | p | pixel | k | p | pixel |
|---|---|---|---|---|---|
| 0 | −2 | (12,3) | 9 | −4 | (8,12) |
| 1 | 12 | (12,4) | 10 | 10 | (8,13) |
| 2 | −6 | (11,5) | 11 | −8 | (7,14) |
| 3 | 8 | (11,6) | 12 | 6 | (7,15) |
| 4 | −10 | (10,7) | 13 | −12 | (6,16) |
| 5 | 4 | (10,8) | 14 | 2 | (6,17) |
| 6 | −14 | (9,9) | 15 | −16 | (5,18) |
| 7 | 0 | (9,10) | 16 | −2 | (5,19) |
| 8 | −18 | (8,11) |
17 pixels (), ending exactly at . At , counts as "", so steps.
5. The midpoint line algorithm
Same result, different way of seeing it. Write the line as . Points above the line give ; below give . Evaluate at the midpoint between the two candidates, :
- : the midpoint is above the line, so the line is nearer the lower pixel — plot .
- : plot .
With : , then (lower) or (upper). For lines it is exactly Bresenham. Its advantage is that it extends to circles and ellipses → note 03.
| Algorithm | Arithmetic | Main idea | Notes |
|---|---|---|---|
| DDA | Floating point | Step the long axis, add slope increments, round | Simple but slow; error builds up |
| Bresenham | Integers only | Decision parameter picks the closer pixel | Fast and exact |
| Midpoint | Integers only | Test the midpoint of the two candidates | Same as Bresenham for lines; generalises to circles |
Complexity
Both DDA and Bresenham are , where is the number of pixels drawn, because each does constant work per pixel. They do not differ in big-O. The difference is the work per pixel: DDA does two float additions and two roundings; Bresenham does integer additions and one comparison with 0. Integer operations are faster, exact, and simple in hardware — that is what makes Bresenham more efficient.
6. Worked example — an integer-only Bresenham for every slope
# bresenham.py — run: python3 bresenham.py, then type: 2 1 5 8
def bresenham(x0, y0, x1, y1):
"""Return the pixels of the line from (x0, y0) to (x1, y1), integers only."""
pixels = []
dx, dy = abs(x1 - x0), abs(y1 - y0)
sx = 1 if x1 > x0 else -1 # direction of travel in x
sy = 1 if y1 > y0 else -1 # direction of travel in y
x, y = x0, y0
if dy > dx: # steep line (|m| > 1): step in y
p = 2 * dx - dy
for _ in range(dy + 1):
pixels.append((x, y))
if p >= 0:
x += sx
p += 2 * (dx - dy)
else:
p += 2 * dx
y += sy
else: # shallow line (|m| <= 1): step in x
p = 2 * dy - dx
for _ in range(dx + 1):
pixels.append((x, y))
if p >= 0:
y += sy
p += 2 * (dy - dx)
else:
p += 2 * dy
x += sx
return pixels
x0, y0, x1, y1 = map(int, input("x0 y0 x1 y1: ").split())
print(bresenham(x0, y0, x1, y1))Test cases (all re-run and matching the hand tables):
| Use case | Input | Output |
|---|---|---|
| Shallow, | (2,3) to (9,8) | (2,3) (3,4) (4,4) (5,5) (6,6) (7,7) (8,7) (9,8) |
| Steep, | (2,1) to (5,8) | (2,1) (2,2) (3,3) (3,4) (4,5) (4,6) (5,7) (5,8) |
| Steep, negative slope | (1,8) to (6,2) | (1,8) (2,7) (3,6) (4,5) (4,4) (5,3) (6,2) |
| Horizontal | (1,4) to (6,4) | (1,4) (2,4) (3,4) (4,4) (5,4) (6,4) |
To justify results in an exam: plot the pixels and the true line together and show that no pixel is more than half a pixel from it. (The code was also checked on 28,392 random lines; every pixel was within half a pixel.)
7. From lines to shapes
A polygon is a set of lines. Call the line function for each pair of consecutive vertices, and for the last vertex back to the first — the % n closes the shape:
def draw_polygon(vertices, draw_line):
n = len(vertices)
for i in range(n):
x0, y0 = vertices[i]
x1, y1 = vertices[(i + 1) % n]
draw_line(x0, y0, x1, y1)A regular -gon’s vertices lie on a circle, spaced apart:
Round each vertex to integers before passing it to the line function. A hexagon has , so the vertices are 60° apart.
Dashed (styled) lines
Count pixels along the line, and plot one only when its position in the repeating pattern falls in the “on” part:
def dashed_pixels(pixels, on=4, off=3):
"""Keep `on` pixels, skip `off` pixels, and repeat."""
return [p for k, p in enumerate(pixels) if k % (on + off) < on]For a horizontal line of 14 pixels ( to ) with on = 4, off = 3, this keeps – and –. To toggle styles, add an option that either plots every pixel or applies this filter. For a rectangle, decide whether the pattern restarts at each corner or carries on around it — and say which.
8. Antialiasing
Antialiasing is a set of techniques that reduce the jagged, stair-step look of lines and edges that should be smooth.
Why jaggies happen. A line is continuous, but the screen is a grid with limited resolution. Scan conversion samples the shape at only a few points, so smooth edges become staircases. The same problem shows up as crawling or flickering edges in animation, and odd patterns on fine detail. The cause is the output device not having enough resolution to show the shape exactly — the raster weakness from note 01. → Rendering as sampling for the signal-processing view.
Four methods:
- Higher resolution. More, smaller pixels make smaller steps. It works, but costs memory and time.
- Area sampling (shading the in-between pixels). Set each pixel’s intensity in proportion to how much of it the line covers. A line covering 30% of a pixel gives it 30% of the line’s intensity — shades of grey on a monochrome screen, or shades of the line colour. Wu’s line algorithm is the well-known example.
- Supersampling. Compute the image at higher resolution (say 4 samples per pixel), then average each pixel’s samples. Simple and works for any shape, but cost multiplies with the sample count. MSAA is the cheaper hardware version that takes extra samples only near edges → note 10.
- Pixel phasing (smoothing). The output device shifts pixel positions by fractions of a pixel, adjusting dot size and horizontal alignment so lines and curves land more exactly.
Trade-off: antialiased lines look smoother but also softer (fuzzier), and need more computation.
Common pitfalls
- Testing the update instead of the parameter. The test is “if ”, not “if ” — is only the amount added.
- Using instead of for “move up”. At the step is taken.
- Calling the first value in the steps and in the example. Pick one name and keep it.
- Stepping the wrong axis in DDA — the long axis gets the step of 1.
- Spelling: it is Bresenham (not “Bresendham”).
- Forgetting the final pixel. Loop
dx + 1(ordy + 1) times, so both end points are drawn.
Check your understanding
- Without computing, how many pixels does Bresenham light for to , and which axis is stepped?
- Why is it safe to multiply by ?
- A friend’s DDA gives to as three pixels. What did they do wrong?
- DDA and Bresenham are both . In what sense is Bresenham “more efficient”, then?
Answers (after your attempt)
- , , steep, so step : pixels.
- , so multiplying does not change the sign, and the sign is all the decision uses. It also clears the fraction , leaving integers.
- They stepped along (the short axis). Steps should be .
- Constant factors: integer adds and a sign test per pixel versus float adds and rounding; and no accumulated error.
Practice — independent tasks
These are the SSG 511 Part A tasks; do them before reading anyone’s code.
- Rasterise to by hand with the derivation: table and plot. (Exam Q1b.) Done when you have pixels ending at and your code agrees.
- to by DDA by hand, then compare with your program. Done when both give 11 pixels, ending at .
- The cross: – and – with full-octant Bresenham. Done when both lines have 41 pixels and they cross at the centre.
- A regular hexagon centred at , radius 50, from six vertices you compute yourself.
- A dashed rectangle with vertices , , , and a toggle between solid and dashed.
- A DDA-versus-Bresenham viewer that draws the same line both ways in different colours (or offset), so you can compare end points and smoothness.
All of these are collected, with the rest of the paper, in the question bank.
Before moving on
You can derive both Bresenham cases from the distances, trace a table, and run your code against it. Next: Circles and Polygon Filling, where the midpoint idea earns its keep.
Related
- Rasterisation — the modern triangle version of the same problem
- Circles and Polygon Filling
- Formula sheet
- Computer graphics map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering