Interpolate values on a triangle

Now that we can pass attribtues to shaders for lines, we will extend this to triangles.

We start again with the clipping (clip_polygon) and processing (process_triangle). These are basically exact equivalents to the line versions.

In clip_polygon, we add a block for the clipped attributes in addition to the positions. As the clipping only involves the intersection with the polygon edges, this is exactly the same as with the lines. In the code, the only difference is that we are in a loop over the edges and don't only have two points.

In process_triangle we incorporate the attributes and pass them to the rasterization along with the points when triangulating the clipped polygon.

As there isn't much new happening, you can look at the code below, but for brevity, it is folded in.

Show code

/**
 * Clips a polygon against the given clip-planes
 * @param {Array<AbstractMat>} points The input points
 * @param {Array<Object>} attribs The
 *  attributes per point
 * @param {Array<AbstractMat>} planes The
 *  clipping planes
 * @returns {[Array<AbstractMat>,Array<Object>]} The
 *  clipped points and interpolated attributes
 */
clip_polygon(points, planes, attribs) {
  // Implementation of the
  //  Sutherland-Hodgman algorithm
  for (let pi = 0; pi < planes.length; pi++) {
    const pl = planes[pi];
    const output = [];
    const output_block = [];
    const size = points.length;
    for (let i = 0; i < size; i++) {
      const cur = points[i];
      const ip = (i - 1 + points.length) % points.length;
      const prev = points[ip];

      // compute distance
      const dc = dot(pl, cur);
      const dp = dot(pl, prev);

      // cur inside
      if (dc >= 0.0) {
        // prev outside
        if (dp < 0.0) {
          // intersect prev -> cur

          const t = dp / (dp - dc);
          const p = add(prev, scale(sub(cur, prev), t));

          // interpolate attributes
          const p_attribs = {};

          for (let k in attribs[i]) {
            p_attribs[k] =
              this.interpolate_line(
                attribs[ip][k], attribs[i][k], t
              );
          }
          output.push(p);
          output_block.push(p_attribs);
        }

        output.push(cur);
        output_block.push(attribs[i]);
      } else if (dp >= 0.0) {
        // cur outside, prev inside
        // intersect prev->cur
        // intersect in homogeneous space

        const t = dp / (dp - dc);
        const p = add(prev, scale(sub(cur, prev), t));

        // interpolate attributes
        const p_attribs = {};

        for (let k in attribs[i]) {
          p_attribs[k] =
            this.interpolate_line(
              attribs[ip][k], attribs[i][k], t
            );
        }
        output.push(p);
        output_block.push(p_attribs);
      }
    }

    points = output;
    attribs = output_block;
  }
  return [points, attribs];
}

/**
 * Processes a single triangle
 * @param {Pipeline} pipeline The pipeline to use
 * @param {AbstractMat} v0 The first vertex
 * @param {AbstractMat} v1 The second vertex
 * @param {AbstractMat} v2 The third vertex
 * @param {Object<Number|AbstractMat>} attribs_v0 The
 *  attributes of the first vertex
 * @param {Object<Number|AbstractMat>} attribs_v1 The
 *  attributes of the second vertex
 * @param {Object<Number|AbstractMat>} attribs_v2 The
 *  attributes of the third vertex
 */
process_triangle(pipeline, v0, v1, v2,
    attribs_v0 = {}, attribs_v1 = {}, attribs_v2 = {}) {
  // prepare points and data for clipping
  let points = [v0, v1, v2];
  let attribs = [attribs_v0, attribs_v1, attribs_v2];
  // clip polygon
  [points, attribs] = this.clip_polygon(
    points, pipeline.clip_planes, attribs
  );

  // triangulate polygon (clipping the triangle may
  //  result in non triangles polygons) and rasterize
  for (let i = 0; i + 2 < points.length; i++) {
    this.rasterize_triangle(
      pipeline, points[0], points[i + 1], points[i + 2],
      attribs[0], attribs[i + 1], attribs[i + 2]
    );
  }
}

For the line rasterization, we had to calculate the interpolation parameter. Now for triangles, we have three points, so the singular parameter doesn't cut it.

But we already have a very similar mechanism: Barycentric coordinates. They do basically the same thing, being the weights of each vertex. On an edge of the triangle, they are actually equivalent to the linear interpolation (one weight is $0$ )!

So it makes sense, that we basically do the same thing with the barycentric coordinates as we did with the $t$ parameter. So instead of interpolating attributes as $d_{\mathbf{P}(t)} = (1-t)d_{\mathbf{A}} + t d_{\mathbf{B}}$ , we do the barycentric interpolation:

d_{\mathbf{P}(u,v,w)} = u d_{\mathbf{A}} + v d_{\mathbf{B}} + w d_{\mathbf{C}}

And we already computed the barycentric coordinates to check if a point is part of the triangle. So we will only implement a method interpolate_triangle that handles the interpolation, again for numbers and matrices seperately.

This will be called in the rasterize_triangle function, which looks basically the same as in the triangle rasterizer. Before calling the fragment shader, an object is filled with interpolations of vertex shader output attributes using the already computed barycentric coordinates. You can have a look at the changes here. Again, folded in, as there isn't too much new and to keep the page a bit leaner.

Show code

/**
 * 
 * @param {Pipeline} pipeline The pipeline to use
 * @param {AbstractMat} v0 The first vertex
 * @param {AbstractMat} v1 The second vertex
 * @param {AbstractMat} v2 The third vertex
 * @param {Object<Number|AbstractMat>} data_v0 The
 *  attributes for the first vertex
 * @param {Object<Number|AbstractMat>} data_v1 The
 *  attributes for the second vertex
 * @param {Object<Number|AbstractMat>} data_v2 The
 *  attributes for the third vertex
 * @returns 
 */
rasterize_triangle(pipeline, v0, v1, v2,
    data_v0 = {}, data_v1 = {}, data_v2 = {}) {
  // compute triangle screen bounds
  let points = [v0, v1, v2];
  let [bmin, bmax] = this.compute_screen_bounds(points);

  // pixel coordinates of bounds
  let ibmin = floor(bmin);
  let ibmax = ceil(bmax);

  const viewport = pipeline.viewport;

  const viewport_max = vec2(
    viewport.x + viewport.w - 1,
    viewport.y + viewport.h - 1
  );
  const viewport_min = vec2(viewport.x, viewport.y);
  // clamp bounds so they lie inside the image region
  cwiseMax(ibmin, viewport_min, ibmin);
  cwiseMin(ibmax, viewport_max, ibmax);

  // handle case where its fully outside
  if (isAny(ibmin, viewport_max, (a, b) => a > b) ||
      isAny(ibmax, viewport_min, (a, b) => a < b)) {
    return;
  }

  // interpolated data buffer
  const data = {};

  // gather attributes
  for (let i in data_v0) {
    if (!data_v1[i] || !data_v2[i]) {
      continue;
    }
    data[i] = null;
  }
  const program = pipeline.program;

  // compute the double triangle area only once
  const area_tri = this.signed_tri_area_doubled(v0, v1, v2);

  // check if any the triangle has zero area
  //  with some epsilon, if so, don't rasterize
  const epsilon = 1E-8;
  if (Math.abs(area_tri) < epsilon) {
    return;
  }

  // check all pixels in screen bounding box
  for (let y = ibmin.at(1); y <= ibmax.at(1); y++) {
    for (let x = ibmin.at(0); x <= ibmax.at(0); x++) {
      // sample point in center of pixel
      const p = add(vec2(x, y), vec2(0.5, 0.5));

      let v = this.signed_tri_area_doubled(v2, v0, p);
      v /= area_tri;
      if (v + epsilon < 0.0) {
        continue;
      }

      let w = this.signed_tri_area_doubled(v0, v1, p);
      w /= area_tri;
      if (w + epsilon < 0.0) {
        continue;
      }

      let u = 1.0 - v - w;
      if (u + epsilon < 0.0) {
        continue;
      }

      // barycentric coordinate
      const b = v32.from([u, v, w]);

      // interpolate values
      for (let i in data) {
        data[i] = this.interpolate_triangle(
          data_v0[i], data_v1[i],data_v2[i], b
        );
      }

      // run  fragment shader with data
      const frag_coord = vec4(x, y, 0.0, 1.0);
      // run  fragment shader with data
      const output_colors = {};

      const do_write_fragment =
          program.fragment_shader(
            frag_coord, data,
            pipeline.uniform_data,
            output_colors
          );

      if (do_write_fragment) {
        this.write_fragment(
          pipeline, frag_coord, output_colors
        );
      }
    }
  }
}

Before we get to implementing the function, a few words about what you will see.

One of the most important use cases for the attribute interpolation on triangles are texture coordinates. Basically, you have an image, the texture, that you want to draw on top of a triangle. To do that, you define for each vertex where that it would be on the image. These coordinates are then interpolated and you can use them to look up the color in the image.

Generally, these image/texture coordinates are normalized in $[0,1]^2$ , so they don't depend on resolution and we call them uv coordinates. The naming just comes from the fact, that surfaces are often parametrized by two variables, $u$ and $v$ . Sometimes, there are other names, for example GLSL provides the .st accessor.

We have included a function to sample an image with these coordinates.

/**
 * Samples an image at a given coordinate
 * @param {PixelImage} img The
 *  image to be sampled
 * @param {Abstractmat} uv The
 *  uv coordinate in [0,1]^2
 * @param {Object} param Additional
 *  parameters
 * @returns {AbstractMat} The color
 *  at the requested position
 */
function sample(img, uv, 
{ 
  interpolation_mode = Interpolation.NEAREST,
  wrap_s = Wrapping.CLAMP_TO_EDGE,
  wrap_t = Wrapping.CLAMP_TO_EDGE 
} = {}) {...}

There are some additional parameters after the uv to change how colors are interpolated and how edges are handled, but they don't matter too much for now.

We want to use that to put an image on our triangles!

For that we provide a field tex in the material of the objects and an attribute uv for the vertices.

For the attribute, we extend our define to:

const Attribute = {
    VERTEX: 0,
    UV: 1,
};

We want our shaders to do the following:

Vertex shader
1. Write the uv attribute into the output block
2. Return the Attribute.VERTEX transformed by the uniforms.M matrix
Fragment shader
1. Get the interpolated uv value from the data parameter
2. If the material has a tex field, sample that texture with the uv coordinate and put that color into the output. Otherweise use the materials color field

We can now implement our first texture-mapped triangles!

As usual, the solution to cross-check is below.

Exercise:

Implement the barycentric interpolation in interpolate_triangle in rasterizer.js
Go to the vertex_shader in shaders.js
- Store the attributes[Attribute.UV] with the name ´"uv"` in the outputs
Go to the fragment_shader in shaders.js
- Get the interpolated uv coordinate from data
- If the material has a texture (uniforms.material.tex), multiply the color with the sampled texture

Solution:

See the solution