Graphics /Discover / Filling a triangle

Filling a triangle

scenario

From Edges to a Filled Surface

You can already rasterise individual line segments. But rendered objects are not usually just collections of visible edges. Complex surfaces are commonly represented as meshes made from many triangles: a coarse mesh may reveal the triangular structure clearly, while a dense mesh can approximate a smooth-looking shape.

Now focus on one triangle. Its three edges tell you the boundary, but drawing only those edges leaves the interior empty. To draw the triangle as a solid primitive, you must decide which pixels inside that boundary are covered.

You could test every pixel on the screen against the triangle, but that ignores structure provided by the shape and the grid. A triangle has boundary edges, and a display is arranged into rows. The problem is to turn those facts into a systematic way to find the covered pixels without searching everywhere.

A y-down grid shows a triangle outline with its interior raster cells filled row by row, while zero-width top and bottom rows contain no filled pixel.
A filled triangle is represented by the raster pixels covered by its area, not only by pixels along its three edges.

Given only the three triangle vertices and a pixel grid, how would you organise the work so that you visit the triangle row by row and know where filling should begin and end on each row?