Triangle Fill by Edge Walking

Why Triangles Are the Universal Primitive

A triangle is the fundamental primitive in computer graphics. Unlike arbitrary polygons, triangles are always convex, always planar, and produce unambiguous interior points. Every 3D model decomposes into triangles before rendering.

Rasterizing a triangle means determining which pixels lie inside it. The scanline edge-walk algorithm is the classic CPU approach and the conceptual ancestor of hardware rasterizers.

The Scanline Algorithm

Sort vertices by y-coordinate (top, middle, bottom)
For each scanline between top and bottom y:
- Compute x-intersections with left and right edges
- Fill all pixels between those x values

As you move down one scanline, each edge's x-intersection advances by a constant dx/dy (inverse slope). The triangle splits into a top half and bottom half at the middle vertex.

c
Loading…

For example, a triangle with vertices (2,1), (8,1), (5,7) fills scanline y=4 between x=3 and x=7. GPUs parallelize this across tile rasterization units, but the geometry is identical.

For This Exercise

You will implement scanline edge-walking and output the pixel coordinates that would be filled. This task does not require a framebuffer display. Getting edge interpolation correct here is the direct prerequisite for barycentric tests and z-buffering later in this subtrack.

Write a C program that fills a triangle using the scanline edge-walk algorithm.

Requirements:

Define three vertices: (2, 2), (8, 3), (5, 8)
Sort vertices by y-coordinate to identify top, middle, and bottom
For each scanline from top_y to bottom_y:
- Calculate the x-intersections of the scanline with the triangle's left and right edges
- Use linear interpolation: for an edge from (x0, y0) to (x1, y1), x at scanline y is x0 + (y - y0) * (x1 - x0) / (y1 - y0)
- Print each filled pixel as "(x, y)"
Track and print the total number of interior pixels
Handle the split at middle_y: above it, one pair of edges bounds the scanline; below it, a different pair does
Print a bounding box summary: min/max x and y of the triangle
Include a note explaining why triangles (not quads or polygons) are the standard rasterization primitive

Why Triangles Are the Universal Primitive

Rasterizing a triangle means determining which pixels lie inside it. The scanline edge-walk algorithm is the classic CPU approach and the conceptual ancestor of hardware rasterizers.

The Scanline Algorithm

Sort vertices by y-coordinate (top, middle, bottom)
For each scanline between top and bottom y:
- Compute x-intersections with left and right edges
- Fill all pixels between those x values

As you move down one scanline, each edge's x-intersection advances by a constant dx/dy (inverse slope). The triangle splits into a top half and bottom half at the middle vertex.

c
Loading…

For example, a triangle with vertices (2,1), (8,1), (5,7) fills scanline y=4 between x=3 and x=7. GPUs parallelize this across tile rasterization units, but the geometry is identical.

For This Exercise

Write a C program that fills a triangle using the scanline edge-walk algorithm.

Requirements:

Define three vertices: (2, 2), (8, 3), (5, 8)
Sort vertices by y-coordinate to identify top, middle, and bottom
For each scanline from top_y to bottom_y:
- Calculate the x-intersections of the scanline with the triangle's left and right edges
- Use linear interpolation: for an edge from (x0, y0) to (x1, y1), x at scanline y is x0 + (y - y0) * (x1 - x0) / (y1 - y0)
- Print each filled pixel as "(x, y)"
Track and print the total number of interior pixels
Handle the split at middle_y: above it, one pair of edges bounds the scanline; below it, a different pair does
Print a bounding box summary: min/max x and y of the triangle
Include a note explaining why triangles (not quads or polygons) are the standard rasterization primitive

Topic Overview

Why Triangles Are the Universal Primitive

The Scanline Algorithm

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source

Triangle Fill by Edge Walking

Topic Overview

Why Triangles Are the Universal Primitive

The Scanline Algorithm

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source