Shaded triangles

In the previous chapter we developed an algorithm to draw a triangle and fill it with some color. Our next goal will be to draw a shaded triangle - something that looks like it has been filled with a gradient.

Although shaded triangles look nicer than uniformly colored triangles, that is not the main goal of this chapter; it’s just a special application of the technique we will develop, which as it turns out, it’s probably the most important one in this section of the book; almost everything else is built on top of this.

But let’s start simple. Instead of filling the triangle with a solid color, we want to fill it with shades of the solid color. It will look like this:

Source code and live demo >>

The first step is to formally define what we want to draw. To do this, we’ll assign a real value \(h\) to each vertex, denoting the intensity of the color at the vertex. \(h\) is in the \([0.0, 1.0]\) range.

To obtain the exact color of a pixel given the color \(C\) and the intensity \(h\), we’ll just multiply channel-wise: \(C_h = (R_C*h, G_C*h, B_C*h)\). Therefore \(h = 0.0\) yields black and \(h = 1.0\) yields the original color \(C\).

Computing edge shading

So in order to draw a shaded triangle, all we need to do is to compute a value of \(h\) for each pixel of the triangle, obtain the corresponding shade of the color, and paint the pixel. Easy!

At this point, however, we only know the values of \(h\) for the vertexes - these are given. How do we compute values of \(h\) for the rest of the triangle?

Let’s focus on the edges first. Consider the edge \(AB\). We know \(h_A\) and \(h_B\). What happens at \(M\), the midpoint of \(AB\)? Since we want the intensity to vary smoothly from \(A\) to \(B\), \(h_M\) has to be some value between \(h_A\) and \(h_B\). Since \(M\) is the midpoint of \(AB\), why not choose \(h_M\) to be the average value of \(h_A\) and \(h_B\)?

More formally, we have a function \(h = f(P)\) for which we know the extreme values \(h(A)\) and \(h(B)\), and we want to make it smooth. Since we know nothing else about \(h = f(P)\), we can choose any function that fits these criteria, for example a linear function:

The basis for our shaded triangle code will be, of course, the solid triangle code developed in the previous chapter. One of the first steps involved computing the endpoints of each horizontal segment, that is, x_left and x_right, for the sides \(P_0P_1\), \(P_0P_2\), and \(P_1P_2\); we used Interpolate() to compute values of \(x = f(y)\) given \(x(y_0)\) and \(x(y_1)\)… which is exactly what we’re trying to do here, if you replace \(x\) with \(h\)!

So we can compute intermediate values of \(h\) in the exact same way we computed values of \(x\):

x01 = Interpolate(y0, x0, y1, x1)
h01 = Interpolate(y0, h0, y1, h1)

x12 = Interpolate(y1, x1, y2, x2)
h12 = Interpolate(y1, h1, y2, h2)

x02 = Interpolate(y0, x0, y2, x2)
h02 = Interpolate(y0, h0, y2, h2)

The next step was turning these three vectors into two vectors, and determining which one represented left-side values and which represented right-side values. Note that the values of \(h\) play no role whatsoever in which is which; this is entirely determined by the values of \(x\). The values of \(h\) “stick” to the values of \(x\), since they are different attributes of the same physical pixels. That is, if x012 has values for the right side of the triangle, then h012 also has values for the right side of the triangle:

  # Concatenate the short sides
  remove_last(x01)
  x012 = x01 + x12

  remove_last(h01)
  h012 = h01 + h12

  # Determine which is left and which is right
  m = x012.length / 2
  if x02[m] < x012[m] {
      x_left = x02
      x_right = x012

      h_left = h02
      h_right = h012
  } else {
      x_left = x012
      x_right = x02

      h_left = h012
      h_right = h02
  }

Computing interior shading

The only step remaining is to draw the actual horizontal segments. For each segment, we know \(x_{left}\) and \(x_{right}\), and now we also know \(h_{left}\) and \(h_{right}\). However, instead of iterating from left to right and drawing each pixel with the base color, we need to compute values of \(h\) for each pixel of the segment.

Again, we can assume \(h\) varies linearly with \(x\), and use Interpolate() to compute these values:

h_segment = Interpolate(x_left[y-y0], h_left[y-y0], x_right[y-y0], h_right[y-y0])

And then it’s just a matter of computing the color for each pixel and painting it.

Here’s the complete code for DrawShadedTriangle:

DrawShadedTriangle (P0, P1, P2, color) {
    # Sort the points so that y0 <= y1 <= y2
    if y1 < y0 { swap(P1, P0) }
    if y2 < y0 { swap(P2, P0) }
    if y2 < y1 { swap(P2, P1) }

    # Compute the x coordinates and h values of the triangle edges
    x01 = Interpolate(y0, x0, y1, x1)
    h01 = Interpolate(y0, h0, y1, h1)

    x12 = Interpolate(y1, x1, y2, x2)
    h12 = Interpolate(y1, h1, y2, h2)

    x02 = Interpolate(y0, x0, y2, x2)
    h02 = Interpolate(y0, h0, y2, h2)

    # Concatenate the short sides
    remove_last(x01)
    x012 = x01 + x12

    remove_last(h01)
    h012 = h01 + h12

    # Determine which is left and which is right
    m = x012.length / 2
    if x02[m] < x012[m] {
        x_left = x02
        x_right = x012

        h_left = h02
        h_right = h012
    } else {
        x_left = x012
        x_right = x02

        h_left = h012
        h_right = h02
    }

    # Draw the horizontal segments
    for y = y0 to y2 {
        x_l = x_left[y - y0]
        x_r = x_right[y - y0]

        h_segment = Interpolate(x_l, h_left[y - y0], x_r, h_right[y - y0])
        for x = x_l to x_r {
            shaded_color = color*h_segment[x - xl]
            canvas.PutPixel(x, y, shaded_color)
        }
    }
}

This algorithm is actually much more general than it looks: up to the point where \(h\) is multiplied by the color, the fact that \(h\) represents a color intensity doesn’t play any role. This means we can use this technique to compute the value of anything that can be represented as a real number for every pixel of the triangle, starting from the values of this property at the vertexes of the triangle, and assuming the property varies linearly on the screen.

As such, it will prove invaluable in later chapters; you should make sure you really understand how this works before proceeding.

<< Filled triangles · Perspective projection >>
Computer Graphics from scratch · Introduction · Table of contents · Common concepts
Part I: Raytracing · Basic ray tracing · Light · Shadows · Reflection · Arbitrary camera · Beyond the basics · Raytracer pseudocode
Part II: Rasterization · Lines · Filled triangles · Shaded triangles · Perspective projection · Scene setup · Clipping · Hidden surface removal · Shading · Textures
Found an error? Everything is in Github.