Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 50 ยท Polygons and Filling

Triangle Rasterization and Barycentric Coordinates

Learn how GPUs fill triangles: bounding boxes, edge functions, barycentric weights, the top-left rule and color interpolation, with live demos.

Scanline filling and flood fill can handle any polygon, but modern graphics hardware does something simpler and much more powerful. It breaks every shape into triangles and fills each triangle with one small, uniform test that runs for every pixel independently. Because the test needs no shared state, thousands of pixels can be checked at the same time, which is exactly what a GPU is good at.

The same test also produces three numbers called barycentric coordinates. They tell you how close a pixel is to each corner, and they are the key to smooth colors, textures and depth across a triangle. In this lesson you build a complete triangle renderer in plain JavaScript.

Why triangles?

A triangle is the simplest polygon that has an area. It has three important properties:

  • It is always convex, so there are no concave pitfalls like those in scanline polygon filling.
  • It is always planar. Any three points lie in one plane, while four points in 3D usually do not.
  • Any other polygon can be triangulated, that is, cut into triangles that share edges.

So a renderer only has to be perfect at one primitive. Everything else (a character model, a terrain, a text glyph) is converted to triangles first.

The edge function

Take two points a and b that form an edge, and a third point p. The edge function is the 2D cross product of the vector from a to b with the vector from a to p:

TEXT
E(a, b, p) = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)

Its sign tells you which side of the infinite line through a and b the point p lies on. It is zero when p is exactly on the line. Its magnitude is twice the area of the triangle a, b, p, so it grows the farther p is from the line.

A point is inside a triangle v0, v1, v2 when it is on the same side of all three edges. If you walk the edges in a consistent order, "same side" means all three values have the same sign. For a triangle with one orientation they are all positive, for the other orientation all negative. The value E(v0, v1, v2) is twice the signed area of the whole triangle, so its sign gives you the orientation.

flowchart LR
  A["For each pixel in the<br/>bounding box"] --> B["Evaluate 3 edge functions<br/>at the pixel center"]
  B --> C{"All three on the<br/>same side?"}
  C -->|"yes"| D["Pixel is covered:<br/>compute weights, shade it"]
  C -->|"no"| E["Skip the pixel"]

The whole rasterizer is this loop. Every pixel is tested on its own.

Bounding box

Testing every pixel of the screen for every triangle would be wasteful. You only need the pixels that could possibly be inside, which are the pixels in the triangle's axis-aligned bounding box: the smallest rectangle containing all three vertices. Compute the minimum and maximum of the vertex x and y values, round outwards, and clamp to the framebuffer so you never write outside it.

For a long thin triangle on a diagonal, the box is much larger than the triangle, so many tests fail. That is acceptable: the test is cheap, and hardware rasterizers use smarter tiles to skip empty areas. For learning, the plain box is perfect.

Barycentric coordinates

Every point p inside a triangle can be written as a weighted average of the three corners:

TEXT
p = w0 * v0 + w1 * v1 + w2 * v2      with  w0 + w1 + w2 = 1

The numbers w0, w1, w2 are the barycentric coordinates of p. At corner v0 the weights are (1, 0, 0). At the middle of the triangle they are (1/3, 1/3, 1/3). On the edge opposite v0 the weight w0 is zero. Inside the triangle all three weights are between 0 and 1. If any weight is negative, the point is outside.

You already computed what you need. The weight of a vertex is the area of the sub-triangle opposite that vertex divided by the whole area, and areas are what the edge functions measure:

TEXT
area = E(v0, v1, v2)
w0 = E(v1, v2, p) / area
w1 = E(v2, v0, p) / area
w2 = E(v0, v1, p) / area

Dividing by the signed area also normalizes the orientation: inside the triangle all three weights are positive whichever way the vertices are listed. The inside test becomes simply w0 >= 0 && w1 >= 0 && w2 >= 0.

Interpolation

Once you have the weights, you can blend any per-vertex value across the triangle. Give each vertex a color, and the color of a pixel is w0 * c0 + w1 * c1 + w2 * c2. This is how smooth gradients, Gouraud shading, texture coordinates and depth values are all produced. A vertex attribute becomes a smooth function over the surface because the weights change linearly across the triangle.

Here is a complete rasterizer. It samples each pixel at its center (the pixel at column x and row y is sampled at x + 0.5, y + 0.5), computes the weights and writes the interpolated color into an ImageData buffer, just as you learned in pixels and framebuffers. The canvas is only 64 by 48 pixels and scaled up with image-rendering: pixelated, so you can see individual pixels. Move the mouse over the triangle to read the weights, and use the checkbox to show the bounding box.

A triangle renderer with interpolated colors

Notice that near each corner the color is almost pure, and in the middle all three mix. The weights always sum to 1, and outside the triangle at least one of them is negative.

The shared-edge problem and the top-left rule

Two triangles in a mesh often share an edge. A pixel center that lies exactly on that edge makes the edge function equal to zero for both triangles. If your test is >= 0, both triangles claim the pixel: it is drawn twice. That is wasteful, and with transparency it leaves a visible seam where the color is blended twice. If your test is > 0, neither triangle claims it and you get a hole. Neither is acceptable.

The fix is a tie-breaking convention: a pixel exactly on an edge belongs to the triangle only if the edge is a top edge or a left edge. Because the shared edge is the left or top edge of exactly one of the two neighbours (and a right or bottom edge of the other), every pixel on it is drawn exactly once. This is the top-left rule used by Direct3D, OpenGL and Vulkan.

An edge is top if it is horizontal and the triangle lies below it, and left if the triangle lies to its right. Which direction of edge that means depends on the winding order. With the sign convention used above (inside values are positive, with y pointing down the screen), the edge from a to b is:

  • a top edge when b.y == a.y and b.x > a.x,
  • a left edge when b.y < a.y.

The rule then becomes: for each edge, accept the pixel when E > 0, or when E == 0 and the edge is top or left. The next demo draws a square made of two triangles that share a diagonal, with integer vertices so many pixel centers fall exactly on the diagonal. It counts how many pixels each triangle claims, first with the naive >= 0 test and then with the top-left rule.

Why the top-left rule matters

The red pixels along the diagonal are the ones both triangles drew. With the top-left rule the red line disappears and the writes add up to exactly the 100 pixels of the square.

Practical details

  • Sampling position. Sampling at pixel centers (+ 0.5) is what graphics APIs specify. Sampling at the corner shifts every triangle by half a pixel.
  • Degenerate triangles. If area is zero, the three points lie on a line. Skip the triangle, otherwise you divide by zero.
  • Incremental evaluation. Each edge function is linear in x and y. Stepping one pixel right changes E by the constant -(b.y - a.y), and one row down by (b.x - a.x). Real rasterizers add these constants instead of recomputing the products.
  • Anti-aliasing. Testing only the pixel center produces jagged edges. Testing several sub-samples per pixel gives the smoother result covered in aliasing and antialiasing.
  • Perspective. In 3D, plain linear weights are not correct for colors or textures. They must be corrected by depth, as discussed in texture mapping.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the sign of the edge function E(a, b, p) tell you?

    The edge function is a 2D cross product. Its sign says on which side of the infinite line the point lies, and it is zero exactly on the line.
  2. 2. A pixel has barycentric weights (0.5, 0.5, 0.0). Where is it?

    w2 = 0 puts the point on the edge opposite v2, which runs from v0 to v1, and equal weights put it halfway along that edge.
  3. 3. Why do renderers use a top-left rule?

    Without a tie-break, a pixel exactly on a shared edge is drawn twice or not at all. The rule gives it to exactly one of the two triangles.
  4. 4. How is a per-vertex color turned into a smooth color across the triangle?

    The weights change linearly across the triangle, so blending the vertex colors with them produces a smooth gradient.

Summary

  • Graphics hardware fills triangles because they are convex, planar and independent per pixel.
  • The edge function E(a, b, p) gives the side of an edge and twice a sub-triangle's area; a pixel is inside when all three edge functions agree.
  • Loop only over the bounding box, clamped to the framebuffer, and sample at pixel centers.
  • Barycentric weights w0 + w1 + w2 = 1 come from dividing each edge function by the total area, and they interpolate any vertex attribute.
  • The top-left rule decides ownership of pixels exactly on a shared edge, so there are no double draws or gaps.

Next, we start moving shapes around: Translation, Scaling and Rotation.