Introduction

Every image on a screen is a rectangular grid of colored pixels. The 3D world inside a game or animation is made of triangles. Rasterization is the step that bridges the two: it converts each triangle, defined by three floating-point vertices in screen space, into the exact set of pixels it covers.

The idea dates to the early 1970s and is deceptively simple. For each triangle, scan from its topmost point to its bottommost, one horizontal row (scanline) at a time. On each scanline, compute where the left and right edges of the triangle cross that row, then fill every pixel between those two crossing points. Repeat for every triangle, and you have an image.

What makes rasterization remarkable is not its cleverness but its raw throughput. A modern game renders tens of millions of triangles per frame at sixty frames per second. The GPU achieves this by running thousands of tiny fill units in parallel, each handling a small tile of pixels simultaneously — the same scanline logic, just massively replicated. No smarter algorithm is needed: sheer parallelism wins.

Rasterization contrasts with ray tracing, where a ray is cast from each pixel into the scene to find what it hits. Ray tracing is more physically accurate but far more expensive per pixel; rasterization goes the other way — from triangles out to pixels — and is orders of magnitude faster for real-time work.

Try It: Scanline Fill

Below is a triangle spinning slowly on a pixel grid. Each frame, the algorithm scans from the topmost vertex to the bottommost, one row at a time, and fills the pixels between the left and right edge crossings.

<!-- Main layout — controls above the pixel canvas -->
<div class="controls">
  <button id="btn-play" type="button">Play</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <label class="speed-label">Speed:
    <input id="speed" type="range" min="1" max="10" value="4">
  </label>
</div>
<canvas id="canvas" width="320" height="280" title="Scanline rasterization of a spinning triangle"></canvas>
<div id="info" class="info">Press Step or Play to start filling.</div>

/* Minimal style for the scanline rasterization demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; display: flex; flex-direction: column; align-items: center; gap: .5rem; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; justify-content: center; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.speed-label { font-size: .82rem; color: #555; display: flex; align-items: center; gap: .35rem; }
#speed { width: 80px; cursor: pointer; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; display: block; background: #f5f8fb; }
.info { font-size: .85rem; color: #444; min-height: 1.3em; text-align: center; }

// Scanline rasterization demo: spin a triangle and fill it row by row
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const btnPlay = document.getElementById('btn-play');
const btnStep = document.getElementById('btn-step');
const btnReset = document.getElementById('btn-reset');
const speedSlider = document.getElementById('speed');
const info = document.getElementById('info');

// Grid dimensions — each cell is one logical pixel
const COLS = 16, ROWS = 14;
const CW = canvas.width / COLS, CH = canvas.height / ROWS;

// Animation state
let angle = 0;
let scanY = null;   // current scanline row being filled (null = show full fill)
let filled = [];    // filled pixel cells for this frame
let playing = false;
let animId = null;
let lastTime = 0;
let tickAcc = 0;

// Equilateral triangle centered on the canvas, rotating with angle a
function triVertices(a) {
  const cx = canvas.width / 2, cy = canvas.height / 2;
  const rx = 100, ry = 90;
  const offsets = [0, 2.094, 4.189]; // 0, 2π/3, 4π/3 — vertices of equilateral triangle
  return offsets.map(d => ({
    x: cx + rx * Math.cos(a + d),
    y: cy + ry * Math.sin(a + d)
  }));
}

// Rasterize triangle verts → array of {row, col} pixel cells
function rasterize(verts) {
  // Sort vertices top-to-bottom
  const v = [...verts].sort((a, b) => a.y - b.y);
  const [v0, v1, v2] = v;
  const result = [];

  // Interpolate x on edge (ya,xa)→(yb,xb) at row y
  function edgeX(ya, yb, xa, xb, y) {
    if (yb === ya) return xa;
    return xa + (xb - xa) * (y - ya) / (yb - ya);
  }

  const yMin = Math.ceil(v0.y / CH), yMax = Math.floor(v2.y / CH);
  for (let row = yMin; row <= yMax; row++) {
    const py = row * CH + CH / 2; // pixel center y
    let xLeft, xRight;
    if (py <= v1.y) {
      // Upper half: long edge left vs short top edge right
      xLeft  = edgeX(v0.y, v2.y, v0.x, v2.x, py);
      xRight = edgeX(v0.y, v1.y, v0.x, v1.x, py);
    } else {
      // Lower half: long edge left vs short bottom edge right
      xLeft  = edgeX(v0.y, v2.y, v0.x, v2.x, py);
      xRight = edgeX(v1.y, v2.y, v1.x, v2.x, py);
    }
    if (xLeft > xRight) { const t = xLeft; xLeft = xRight; xRight = t; }
    const colMin = Math.ceil(xLeft / CW), colMax = Math.floor(xRight / CW);
    for (let col = colMin; col <= colMax; col++) {
      result.push({ row, col });
    }
  }
  return result;
}

// Render the canvas
function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  const verts = triVertices(angle);
  const allPixels = rasterize(verts);

  // Filled pixels (blue)
  const visiblePixels = scanY === null ? allPixels : allPixels.filter(p => p.row < scanY);
  ctx.fillStyle = '#4a90d9';
  for (const { row, col } of visiblePixels) {
    ctx.fillRect(col * CW + 1, row * CH + 1, CW - 2, CH - 2);
  }

  // Current scanline pixels (red)
  if (scanY !== null && scanY <= Math.floor(triVertices(angle)[2].y / CH)) {
    ctx.fillStyle = '#e63946';
    const rowPixels = allPixels.filter(p => p.row === scanY);
    for (const { col } of rowPixels) {
      ctx.fillRect(col * CW + 1, scanY * CH + 1, CW - 2, CH - 2);
    }
  }

  // Pixel grid
  ctx.strokeStyle = '#dde4ec';
  ctx.lineWidth = 0.5;
  for (let r = 0; r <= ROWS; r++) { ctx.beginPath(); ctx.moveTo(0, r * CH); ctx.lineTo(canvas.width, r * CH); ctx.stroke(); }
  for (let c = 0; c <= COLS; c++) { ctx.beginPath(); ctx.moveTo(c * CW, 0); ctx.lineTo(c * CW, canvas.height); ctx.stroke(); }

  // Triangle outline
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.moveTo(verts[0].x, verts[0].y);
  ctx.lineTo(verts[1].x, verts[1].y);
  ctx.lineTo(verts[2].x, verts[2].y);
  ctx.closePath();
  ctx.stroke();

  // Active scanline indicator (red dashed)
  if (scanY !== null) {
    const sy = scanY * CH + CH / 2;
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 1;
    ctx.setLineDash([4, 3]);
    ctx.beginPath(); ctx.moveTo(0, sy); ctx.lineTo(canvas.width, sy); ctx.stroke();
    ctx.setLineDash([]);
  }
}

// Reset scan to the first row of the current triangle
function resetScan() {
  const verts = triVertices(angle);
  const sorted = [...verts].sort((a, b) => a.y - b.y);
  scanY = Math.ceil(sorted[0].y / CH);
  filled = [];
}

function getMaxScanY() {
  const verts = triVertices(angle);
  return Math.floor([...verts].sort((a, b) => a.y - b.y)[2].y / CH);
}

// Advance one scanline
function step() {
  if (scanY === null) resetScan();
  const maxY = getMaxScanY();
  if (scanY > maxY) {
    info.textContent = fmt('Done — %rows% scanlines filled.', { rows: maxY - Math.ceil(triVertices(angle).sort((a,b)=>a.y-b.y)[0].y/CH) + 1 });
    scanY = null;
    return;
  }
  info.textContent = fmt('Filling scanline %row% of %maxRow%…', { row: scanY, maxRow: maxY });
  scanY++;
  draw();
}

// Animation loop — rotate and re-rasterize
function tick(ts) {
  if (!playing) return;
  const dt = ts - lastTime; lastTime = ts;
  const speed = parseInt(speedSlider.value, 10);
  tickAcc += dt;
  const interval = 300 / speed; // ms between frames at this speed setting
  if (tickAcc >= interval) {
    tickAcc -= interval;
    // Advance rotation angle
    angle += 0.03 * speed;
    resetScan();
    draw();
  }
  animId = requestAnimationFrame(tick);
}

btnPlay.addEventListener('click', () => {
  playing = !playing;
  btnPlay.textContent = playing ? 'Pause' : 'Play';
  if (playing) {
    lastTime = performance.now(); tickAcc = 0;
    animId = requestAnimationFrame(tick);
  } else {
    cancelAnimationFrame(animId);
  }
});

btnStep.addEventListener('click', () => {
  if (playing) { playing = false; btnPlay.textContent = 'Play'; cancelAnimationFrame(animId); }
  step();
});

btnReset.addEventListener('click', () => {
  playing = false; btnPlay.textContent = 'Play'; cancelAnimationFrame(animId);
  angle = 0; scanY = null; filled = [];
  info.textContent = 'Press Step or Play to start filling.';
  draw();
});

// Initial draw
draw();
info.textContent = 'Press Step or Play to start filling.';
Result
Console

Press Step to advance one scanline at a time and watch the fill progress row by row. Press Play / Pause to let the triangle spin continuously. Use the speed slider to slow it down or speed it up. Notice how the fill is always completed in O(h⋅w)O(h \cdot w) time where hh is the triangle height in pixels and ww is the average width — proportional to the area, nothing wasted.

The Real Complexity

How hard is rasterization, algorithmically?

  • Lower bound: any algorithm must write at least one value per covered pixel, so the work is Ω(A)\Omega(A) where AA is the triangle's area in pixels. Rasterization hits this bound — it is output-optimal.
  • Scanline algorithm: sort the three vertices by yy, split into at most two trapezoids at the middle vertex, then for each scanline compute left/right xx intersections with the edges and fill the span. Total work: O(A)O(A).
  • Edge-function test: an equivalent formulation evaluates the sign of three half-plane inequalities (e0,e1,e2)(e_0, e_1, e_2) per candidate pixel. If all three are non-negative, the pixel is inside. This form is trivially parallelizable — thousands of pixels can be tested simultaneously with no dependencies between them.
  • Barycentric interpolation: the same edge values give barycentric coordinates (λ0,λ1,λ2)(\lambda_0, \lambda_1, \lambda_2) with λ0+λ1+λ2=1\lambda_0 + \lambda_1 + \lambda_2 = 1. These interpolate vertex attributes (color, texture coordinates, depth) across the triangle surface in O(1)O(1) per pixel after a three-multiply setup.
  • Hierarchical tiling: real GPUs subdivide the screen into 8×88 \times 8 or 16×1616 \times 16 pixel tiles and use a fast bounding-box test to skip tiles that don't overlap the triangle at all. Only tiles that partially overlap require per-pixel edge tests. This prunes O(P−A)O(P - A) empty work when the triangle is small relative to its bounding box.
  • Depth buffering: a depth value zz is interpolated barycentrically per pixel and compared to a stored zz-buffer. If the new pixel is farther away, it is discarded — the whole fill remains O(A)O(A).

The punchline: rasterization is not just fast in practice; it is theoretically optimal for the task it solves. The only way to go faster is to draw fewer or smaller triangles — which is why level-of-detail systems and culling algorithms matter.

Where It Matters

Rasterization is the single most executed algorithm on consumer hardware — it runs billions of times per second on every device with a screen:

  • Video games: the entire visible scene is rasterized every frame. A modern title submits millions of triangles; the GPU's rasterizers fill tens of billions of pixels per second.
  • Film VFX previews: while final frames use path tracing, artists work in rasterized viewports that give instant feedback on geometry, lighting rigs and animation.
  • CAD and 3D modeling: real-time viewport rendering in tools like Blender or AutoCAD relies on rasterization to let designers manipulate models fluidly.
  • 2D UI and vector graphics: every browser <canvas>, SVG shape and HTML element is ultimately rasterized to the screen. The GPU's 2D rasterizer fills rounded rectangles and Bézier curves with the same scanline logic.
  • Font rendering: scalable fonts (TrueType, OpenType) store glyph outlines as quadratic Bézier curves. At display time those curves are rasterized to a pixel grid, with sub-pixel anti-aliasing blending partial coverage at edges.

Understanding rasterization is the entry point to the whole graphics pipeline, and it connects directly to deeper topics in computational geometry — including visibility, clipping, and the interplay between discrete and continuous geometry.

Conclusion

Rasterization is one of those rare algorithms where the naive approach — scan each row, fill between the edges — turns out to be provably optimal. You cannot fill AA pixels in fewer than AA steps, and that is exactly what the scanline algorithm does. Everything else is engineering: tile hierarchies, parallel fill units, depth buffers and attribute interpolation, all stacked on top of the same simple loop.

The next time a game renders a frame in sixteen milliseconds, remember that each of those milliseconds contains millions of tiny triangles scanned row by row, their pixels tested and filled in parallel across thousands of shader cores. Simple math, massive scale — that is rasterization.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rasterization/Content licensed under CC BY-NC 4.0.