Triangle Filling and the Depth Buffer

Goal

Fill a triangle with barycentric coordinates, interpolate vertex values, decide front from back with a depth buffer, and filter out back faces. When this lab is done, you hold the core of a complete rasterizer in your hands.

Why it matters

The screen is a grid of pixels, and the edges of a triangle do not fit the grid. You need a rule that decides which pixels belong to this triangle, and barycentric coordinates solve that rule and value interpolation at once. If all three coefficients are 0 or greater, the point is inside, and you can blend color, normal, texture coordinates and depth with the same coefficients.

The depth buffer gives something even bigger. If you remember the minimum depth so far for every pixel, you get the same picture regardless of the drawing order. You no longer need to sort triangles, and objects that pierce each other are handled naturally. This is why hardware chose this over the painter's algorithm.

Steps

Put the toolbox in /root/raster.
Make barycentric coordinates in /root/raster/bary.py.
Fill a triangle to /root/raster/out/tri.png.
Draw with interpolated vertex colors to /root/raster/out/tri_rgb.png.
Draw two triangles with a depth buffer to /root/raster/out/zbuffer.png.
Swap only the depths to make /root/raster/out/zswap.png.
Read /root/raster/tris.txt, discard back faces, and make /root/raster/out/cull.png and /root/raster/out/07-cull.txt.

Notes

To see the pictures, start a server with nohup python3 -m http.server 8080 -d /root/raster/out & and then open http://localhost:8080/ in the Web preview. Looking at zbuffer.png and zswap.png side by side is the key scene of this lab.
The pixel center is (x+0.5, y+0.5). If you decide with integer coordinates, the boundary shifts by one line.
Common mistake 1: doing the depth comparison but not updating the depth buffer. Then whatever is drawn later always wins.
Common mistake 2: going over the whole screen instead of taking a bounding box. The result is the same, but in Python it is several times slower.

Put the drawing toolbox in place

Save /root/raster/gfxlib.py exactly as in the example, and use /root/raster/check.py to draw a test pattern and make /root/raster/out/00-check.png. The pattern is a 64x64 black background with a white (255,255,255) diagonal line from (0,0) to (63,63), and over it a red (255,0,0) horizontal line from (0,32) to (63,32).

From this lab on, you do not rebuild the PNG encoder. We hand you the same code you built by hand in the first lab as a tool — because file formats are not what you learn here.

The lab Pod has no volume, so the files you made in the previous lab are not kept. That is why each lab starts by putting the toolbox in place again.

Create Canvas(w, h, bg), draw the two lines with line(x0, y0, x1, y1, rgb), and then save with write_png(path). Draw the horizontal line later, so that the intersection (32,32) becomes red.

Barycentric coordinates

In /root/raster/bary.py, make barycentric(a, b, c, p). a, b, c and p are 2D points, and it returns three real numbers (u, v, w) such that p = u*a + v*b + w*c.

The denominator is twice the triangle's area (signed).

d = (b1-c1)*(a0-c0) + (c0-b0)*(a1-c1)
u = ((b1-c1)*(p0-c0) + (c0-b0)*(p1-c1)) / d
v = ((c1-a1)*(p0-c0) + (a0-c0)*(p1-c1)) / d
w = 1 - u - v

Check with the vertices. If p is a, it must be (1,0,0), if b then (0,1,0), and if c then (0,0,1). And the sum of the three values is always 1 everywhere.

If all three values are 0 or greater, the point is inside the triangle. This one property solves the inside-outside test and value interpolation at once.

Paint the triangle

Use /root/raster/fill.py to fill, on /root/raster/out/tri.png (256x256, black background), the triangle with vertices (30,30), (220,60), (120,230) in red (255,60,60). Treat the center of pixel (x, y) as (x+0.5, y+0.5), and paint when all three barycentric coordinates are 0 or greater.

Do not scan the whole screen; go over only inside the bounding box. Take the box from the minimum and maximum x and the minimum and maximum y of the three vertices. GPUs do the same thing in units of tiles.

It is important to set the pixel center to (x+0.5, y+0.5). If you decide with integer coordinates, one line shifts at the boundary.

The number of painted pixels should be close to the triangle's area. Find the area with the shoelace formula and compare.

Blend the vertex colors

Use /root/raster/interp.py to draw the same triangle to /root/raster/out/tri_rgb.png, but set vertex A(30,30) to red (255,0,0), B(220,60) to green (0,255,0) and C(120,230) to blue (0,0,255), and blend the pixel color as u*A색 + v*B색 + w*C색 (the placeholders are the three vertex colors).

Barycentric coordinates are not only for the inside-outside test. You can blend any value attached to the vertices with the same coefficients. Color, texture coordinates, normals and depth all work the same way.

Blend each channel separately, like r = u*255 + v*0 + w*0.

Where the three barycentric coordinates are each 1/3 (the triangle's centroid), all three channels come to about 85 and it looks gray. Check it.

Decide front from back with a depth buffer

Use /root/raster/zbuf.py to make /root/raster/out/zbuffer.png (256x256, black background). Triangle A is at (30,30),(200,30),(30,200) in blue (60,60,255) with depth 0.2, and triangle B is at (60,60),(230,60),(60,230) in yellow (255,220,60) with depth 0.8. Keep a depth buffer per pixel, and the smaller depth wins.

The depth buffer is an array of real numbers the same size as the screen. Fill it at first with a very large value (for example, float("inf")).

Before painting a pixel, check whether z < zbuf[y][x], and write the color and the depth together only then. If you do not update the depth, whatever is drawn later wins unconditionally.

Here depth is constant per triangle, but a real renderer interpolates depth with barycentric coordinates too. The point of this step is that the same picture comes out regardless of the drawing order.

Swap only the depths

Leave the positions and colors of the triangles as they are, swap only the depths (A to 0.8, B to 0.2), and make /root/raster/out/zswap.png.

The code is almost the same. Just swap the two depth values with each other.

Put the two pictures side by side. Only the color of the overlapping region changes and the rest is identical. That is exactly what the depth buffer does — it decides front from back per pixel.

Test whether the result is the same if you change the order in which you draw the triangles. It should be the same. That order independence is the real reason to use a z-buffer.

Pick out and discard the back faces

Read the six triangles in /root/raster/tris.txt, fill only those whose signed screen-coordinate area is negative with their own color on /root/raster/out/cull.png (256x256, black background), and write nine lines to /root/raster/out/07-cull.txt: total=, drawn=, culled=, and t1=front|back through t6=.

You compute the signed area like this.

signed_area = ((Bx-Ax)*(Cy-Ay) - (Cx-Ax)*(By-Ay)) / 2

If it is negative, treat it as a front face, and if positive, as a back face. Screen coordinates have y growing downward, so the sign reads opposite to the convention from math class.

Each line of tris.txt has nine integers, x0 y0 x1 y1 x2 y2 r g b. You can cut it up with split().

For a closed object, the back faces are hidden behind the front faces anyway, so this one sign lets you discard half of the triangles before rasterization.