Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 50 ยท Line and Circle Algorithms

Aliasing and Antialiasing

See why raster lines show jaggies, learn the sampling idea behind them, and fix them with supersampling, pixel coverage and Wu's line algorithm.

Plot a diagonal line with Bresenham's algorithm and look closely. The line is a staircase. Every pixel is either fully on or fully off, so the edge steps from one row to the next. These stairs are called jaggies, and the general effect is called aliasing. Moving shapes make it worse: edges crawl, thin lines flicker, and small objects blink in and out.

Antialiasing is the family of techniques that reduce it. Instead of asking "is this pixel on or off?", we ask "how much of this pixel does the shape cover?" and use partial coverage to blend the pixel between the shape color and the background. The staircase becomes a soft edge that the eye reads as a smooth line. This lesson explains where aliasing comes from and builds two classic fixes: supersampling and Wu's line algorithm.

Where aliasing comes from

A pixel represents a whole little square of the picture, but a basic rasterizer evaluates the shape at one sample point, usually the pixel center, and records the answer. This is point sampling. A shape has sharp edges, and a sharp edge changes from "inside" to "outside" in zero distance. Sampling that on a regular grid inevitably produces a stair pattern.

The cleanest way to see the problem is with a smooth signal. Imagine a wave and a row of sample points. If the wave oscillates faster than half the sampling rate, there are too few samples per cycle to describe it, and the samples look like a slower wave. The fast wave is "aliased" into a false, slow one. The Nyquist limit states the rule: to capture a signal you must sample at more than twice its highest frequency.

The following console example samples two different cosines at one sample per unit step. The 0.9 cycles-per-sample wave is far above the limit of 0.5, and its samples are identical to those of a 0.1 wave.

JS Two waves, the same samples

Press Run (or Ctrl + Enter) to see the console output here.

No output.

In an image, the "waves" are repeating details: fine stripes, a distant brick wall, a checkerboard. Past the limit they produce wrong patterns called moire. A sharp edge is worse: it contains frequencies of every size, so no sample rate captures it. The usual remedy is to remove what we cannot represent before sampling (blur it slightly), or to estimate the average color of each pixel's area instead of one point.

Coverage: the idea behind every fix

Both techniques below estimate coverage: the fraction of the pixel square that the shape occupies, a number from 0 to 1. A pixel with coverage 0.3 is shown as 30 percent shape color and 70 percent background:

TEXT
color = coverage * shapeColor + (1 - coverage) * backgroundColor

For black on white, a coverage of 0.3 gives gray level 255 * (1 - 0.3).

flowchart LR
  A["Shape edge crosses<br/>a pixel square"] --> B["Estimate<br/>coverage 0..1"]
  B --> C["Blend shape and<br/>background by coverage"]
  C --> D["Soft edge,<br/>no hard stair step"]

Antialiasing replaces the on/off decision with a coverage estimate and a blend.

Supersampling

Supersampling (SSAA, super-sample antialiasing) estimates coverage by brute force. Split each pixel into an n x n grid of sub-samples, test each sub-sample against the shape, and average the results. With 4 x 4 samples the coverage can take 17 values (0/16 to 16/16) instead of just 2.

Where do you place the samples? A regular grid inside the pixel is the simplest choice. Jittered or rotated patterns work better against some artifacts, but the principle is the same. The cost is the weak point: n x n samples means n^2 times the work. This is why real renderers prefer smarter variants such as MSAA, which runs the expensive shading once per pixel and only tests geometry coverage more often.

The next example draws a 1-pixel-wide line and a ring on a tiny grid, magnified so each cell is one pixel. The left canvas uses one sample per pixel; the right one uses the number you pick. The shape test measures the distance from the sample to the line segment or to the circle's center.

Point sampling vs supersampling

Set the menu to 2 x 2 and then to 8 x 8. The gain is large at first and small later: going from 1 to 4 samples per axis removes most of the visible stair, while 8 x 8 looks only slightly smoother yet costs four times as much as 4 x 4.

Wu's line algorithm

Supersampling works for any shape but wastes effort on a line, whose coverage can be derived directly. Xiaolin Wu's line algorithm (1991) is the standard answer for lines. It walks along the major axis like DDA, but at each step the exact y lies between two pixel rows. Wu lights both pixels, splitting the brightness according to how close the line is to each.

Suppose the line is gentle (more horizontal than vertical). At integer x the line's true height is y. Let yi = floor(y) and f = y - yi, the fractional part. Then:

  • pixel (x, yi) gets brightness 1 - f;
  • pixel (x, yi + 1) gets brightness f.

If the line passes exactly through a pixel center, f = 0 and only one pixel is lit. If it passes halfway between two rows, both get 0.5. The two values always add up to 1, so the line keeps a constant visual weight along its length.

flowchart TB
  A["Steep line?<br/>(|dy| > |dx|)"] -->|yes| B["Swap x and y<br/>(remember to swap back when plotting)"]
  A -->|no| C["Keep"]
  B --> D["Make x0 <= x1"]
  C --> D
  D --> E["For each x: y = y0 + slope * (x - x0)"]
  E --> F["Plot (x, floor(y)) with 1 - f<br/>Plot (x, floor(y)+1) with f"]

Steep lines are handled by swapping the axes, so one loop covers all slopes.

Here is a compact version. It rounds the end points to the nearest pixel, which keeps the code short. The full published algorithm also fades the end caps by their partial coverage.

JavaScript
function wuLine(plot, x0, y0, x1, y1) {
  const steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
  if (steep) { [x0, y0] = [y0, x0]; [x1, y1] = [y1, x1]; }
  if (x0 > x1) { [x0, x1] = [x1, x0]; [y0, y1] = [y1, y0]; }

  const slope = x1 === x0 ? 0 : (y1 - y0) / (x1 - x0);
  const start = Math.round(x0), end = Math.round(x1);
  let y = y0 + slope * (start - x0);

  for (let x = start; x <= end; x++) {
    const yi = Math.floor(y);
    const f = y - yi;
    if (steep) {            // swap back when plotting
      plot(yi, x, 1 - f);
      plot(yi + 1, x, f);
    } else {
      plot(x, yi, 1 - f);
      plot(x, yi + 1, f);
    }
    y += slope;
  }
}

The example compares it with a plain rounding line. Both canvases show the same three lines, including one steep line.

Wu's line algorithm vs plain rounding

Wu's algorithm needs a drawing surface that can blend: each pixel must be mixed with what is already there. On a bare black-and-white display it is useless. With gray levels or color, it is cheap and effective.

Gamma and other practical details

  • Gamma. Screens do not respond linearly to pixel values, so 50 percent coverage drawn as value 128 can look too dark or too light. Careful renderers blend in linear light and convert afterwards. Gamma and sRGB are covered in the color chapter.
  • Filters. Averaging the samples equally is a box filter. Weighting samples nearer the pixel center more strongly (a tent or Gaussian filter) gives softer edges with less pixel crawl.
  • Prefiltering vs postfiltering. Wu computes coverage analytically (prefiltering). Supersampling renders more than needed and then reduces the image (postfiltering).
  • Screen-space methods. FXAA and similar techniques detect edges in the finished image and smooth them. They are cheap but cannot recover detail that was never sampled. Temporal methods (TAA) jitter the samples each frame and accumulate them over time.
  • Text. Font rendering uses the same ideas, often with extra tricks that exploit the red, green and blue stripes of an LCD.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the root cause of jaggies in a basic rasterizer?

    Point sampling produces binary results along a sharp edge, which creates a stair pattern. Partial coverage is what smooths it.
  2. 2. In Wu's algorithm, a line passes exactly halfway between two pixel rows at some x. What brightness do the two pixels get?

    The fractional part f is 0.5, so one pixel gets 1 - f = 0.5 and the other gets f = 0.5. The two always sum to 1.
  3. 3. A 4 x 4 supersampled pixel has 11 sample points inside the shape. What is its coverage?

    Coverage is the fraction of samples that hit the shape: 11 out of 16.
  4. 4. Why is 8 x 8 supersampling often not worth the cost compared with 4 x 4?

    The sample count grows with n squared (64 versus 16), while the visible improvement shrinks as the stair steps are already tiny.
  5. 5. What does the Nyquist limit say?

    Below that rate, fast detail shows up as false slower patterns (aliasing, moire).

Summary

  • Aliasing comes from point sampling a shape with sharp edges on a regular pixel grid.
  • Signals sampled below twice their highest frequency appear as false, slower patterns (Nyquist limit).
  • Antialiasing estimates each pixel's coverage and blends shape and background by that fraction.
  • Supersampling averages n x n sub-samples per pixel: it works for any shape but costs n^2 times more.
  • Wu's algorithm lights the two pixels nearest the line with brightness 1 - f and f, using one loop and swapped axes for steep lines.
  • Blending, gamma handling and the choice of filter all affect how smooth the result looks.

Next: Thick Lines, Dashes and Pen Styles.