Loading page…
Master the fundamental concepts of software rasterizer through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksA 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.
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.
cLoading…
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.
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.
Fill triangles the classic way, by scanline edge walking: for every row of pixel centres, find where the triangle's edges cross that row, and fill the span between the crossings. Do it exactly, with rational arithmetic instead of floats, and with fill conventions that make adjacent triangles tile perfectly. Then cross-check every pixel against the edge-function test with the top-left rule. The two methods must agree.
# starts a comment line.
cLoading…
Each tri is filled on a fresh, empty canvas.
Work on a doubled grid: a vertex (x, y) becomes (2x, 2y), and pixel (px, py) has its centre at (2px+1, 2py+1).
ay ≤ Yc < by. Horizontal edges never cross. The crossing is X = (ax·(by-ay) + (Yc-ay)·(bx-ax)) / (by-ay), kept as a fraction.L ≤ 2px+1 < R. Only pixels with 0 ≤ px < W count.: degenerate, nothing to fill after the header.E(a→b) = (bx-ax)(Py-ay) - (by-ay)(Px-ax) are ≥ 0 (after ordering the triangle to positive area), where an edge with E = 0 counts only if it is top (ay == by && bx > ax) or left (by < ay).cLoading…
#/..N pixel(s) filled; edge-function test agrees, or DISAGREES if any pixel differs.canvas: W (1-64) H (1-32), tri: X0 Y0 X1 Y1 X2 Y2, tri: coordinates within +-1000, unknown command X.Input:
cLoading…
Output:
cLoading…
[top, bottom), span [L, R)) are what make two triangles sharing an edge cover each pixel exactly once. The edge-function cross-check proves it.Hidden tests cover two triangles sharing a diagonal (together covering the canvas exactly), a flat-top and a flat-bottom triangle, a degenerate triangle, a triangle larger than the canvas, and input errors.