Filling a triangle with edge tests

A triangle is the basic shape of computer graphics. Games, films and design tools build every surface out of thousands of them, and each one must be filled with pixels.

In this lesson you learn how a program decides whether a pixel is inside a triangle, using three simple tests.

Walk from one corner of a triangle to the next. Everything on your left is on one side of that edge, and everything on your right is on the other.

The edge test gives a number for a point p and an edge from a to b. Let dx and dy be the edge's run and rise, and px and py the point's offset from a. The number is dx times py, minus dy times px. Zero means p is exactly on the line.

docker exec jupyter python3 -c "e = lambda a, b, p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]); a, b, c = (0, 0), (8, 0), (0, 8); print([e(a, b, (2, 2)), e(b, c, (2, 2)), e(c, a, (2, 2))])"

The Run prints [16, 32, 16], the first row of the table. A point is inside the triangle when the three edge values are all positive, or all negative, or zero.

Which sign it is depends on whether the corners go clockwise or anticlockwise. Accepting either direction makes the test work for any triangle.

To fill the triangle, test pixels one at a time and colour the ones that pass. Testing the whole picture is wasteful, so we loop only over the bounding box, the smallest rectangle around the three corners.

Real graphics chips do exactly this, testing thousands of pixels at once.

docker exec jupyter python3 -c "e = lambda a, b, p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]); a, b, c = (0, 0), (8, 0), (0, 8); print(sum(1 for x in range(9) for y in range(9) if min(e(a, b, (x, y)), e(b, c, (x, y)), e(c, a, (x, y))) >= 0))"

def edge(a, b, p):
    return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])

corners = [[1, 1], [9, 2], [3, 6]]
a = corners[0]
b = corners[1]
c = corners[2]

for y in range(8):
    line = ""
    for x in range(11):
        p = [x, y]
        first = edge(a, b, p)
        second = edge(b, c, p)
        third = edge(c, a, p)
        if first >= 0 and second >= 0 and third >= 0:
            line = line + "#"
        elif first <= 0 and second <= 0 and third <= 0:
            line = line + "#"
        else:
            line = line + "."
    print(line)
# Change the corner [3, 6] to [3, 7] and press Run.

The same three numbers also say where a point sits. Divide each edge value by the number for the whole triangle, which is the edge test of the third corner. The three results are the barycentric weights.

They add up to 1. Each is large when the point is near its corner. A negative weight means the point is outside.

Weights let us interpolate. Say the corners are red, green and blue. A pixel takes red times its first weight, plus green times its second, plus blue times its third.

Pixels near the red corner come out mostly red, and in the middle all three mix. This is how a graphics chip smooths colour across a surface.

docker exec jupyter python3 -c "from PIL import Image, ImageDraw; p = Image.new('L', (40, 40), 0); ImageDraw.Draw(p).polygon([(2, 2), (34, 2), (2, 34)], fill=200); p.save('triangle.png'); print(p.getpixel((10, 10)), p.getpixel((30, 30)))"

The Run prints 200 0 and saves triangle.png. Open it from the file list.

You see a black square with a light grey right-angled triangle in it. The right angle is at the top left, and the long slanting edge runs from the top right to the bottom left.