Rasterization

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.

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.

<!-- {{c_container_comment}} -->
<div class="controls">
  <button id="btn-play" type="button">{{btn_play}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <label class="speed-label">{{label_speed}}
    <input id="speed" type="range" min="1" max="10" value="4">
  </label>
</div>
<canvas id="canvas" width="320" height="280" title="{{canvas_title}}"></canvas>
<div id="info" class="info">{{info_init}}</div>

/* {{c_style_comment}} */
* { 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; }

// Code not found

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 \cdot w)$ time where $h$ is the triangle height in pixels and $w$ is the average width — proportional to the area, nothing wasted.

How hard is rasterization, algorithmically?

• Lower bound: any algorithm must write at least one value per covered pixel, so the work is $\Omega(A)$ where $A$ is the triangle's area in pixels. Rasterization hits this bound — it is output-optimal.
• Scanline algorithm: sort the three vertices by $y$, split into at most two trapezoids at the middle vertex, then for each scanline compute left/right $x$ intersections with the edges and fill the span. Total work: $O(A)$.
• Edge-function test: an equivalent formulation evaluates the sign of three half-plane inequalities $(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 $(\lambda_0, \lambda_1, \lambda_2)$ with $\lambda_0 + \lambda_1 + \lambda_2 = 1$. These interpolate vertex attributes (color, texture coordinates, depth) across the triangle surface in $O(1)$ per pixel after a three-multiply setup.
• Hierarchical tiling: real GPUs subdivide the screen into $8 \times 8$ or $16 \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)$ empty work when the triangle is small relative to its bounding box.
• Depth buffering: a depth value $z$ is interpolated barycentrically per pixel and compared to a stored $z$-buffer. If the new pixel is farther away, it is discarded — the whole fill remains $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.

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.

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 $A$ pixels in fewer than $A$ 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.