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.
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?