Preparations

We will need to add the attribute data in a few places, though it will look mostly the same everywhere. Basically, we want to keep it pretty flexible, but not make the code too complicated. So we will just add add an additional parameter to the vertex shader. This parameter will be called output and it is just an empty object.

A vertex shader can then just add any field to that object. These "output blocks" will be stored along with the transformed vertex positions and passed on to the rasterization, where they will be handled and then passed to the fragment shader.

The fragment shader previously had a data parameter, which was left empty. We will fill it now, as it will be the result of the attribute interpolation implemented in the next step.

As this setup is a choice for this framework (and very likely not the fastest), we will show you the new setup code, with some of the mostly unchanged part left out. There is one part missing, namely the processing and clipping functions. These will be changed in the next step as well.

class Rasterizer {
  /**
   * Draw the given geometry
   * @param {Pipeline} pipeline The pipeline to use
   * @param {Object} geom Geometry object
   *  specifying all information
   */
  draw(pipeline, geom) {
    // no vertex shader
    if (!pipeline.program) {
      return;
    }
    const program = pipeline.program;
    // no vertices
    // we could also take a parameter specifying
    //  the number of vertices to be
    // drawn and not rely on vertex data
    if (!geom.attributes[Attribute.VERTEX]) {
      return;
    }

    const vertices = geom.attributes[Attribute.VERTEX];
    const n = vertices.length;
    // process vertices
    const transformed_points = new Array(n);
    // Buffer variable to prevent having to create a
    //  new map for each vertex, as
    // they share the same attributes
    let vertex_attributes = [];
    // storage for vertex outputs
    // each vertex has a number of outputs, that are
    //  filled by the vertex shader
    const vertex_outputs = new Array(n);

    for (let i = 0; i < n; i++) {
      vertex_outputs[i] = {};
    }

    for (let i = 0; i < n; i++) {
      // copy attributes in buffer
      for (const [key, values] of Object.entries(geom.attributes)) {
        vertex_attributes[key] = values[i];
      }
      // call vertex shader
      transformed_points[i] =
        program.vertex_shader(
          vertex_attributes, 
          pipeline.uniform_data, 
          vertex_outputs[i]
        );
    }

    // go through objects
    if (geom.topology === Topology.LINES) {
      // handles lines
      // handle two vertices per step
      for (let i = 0; i < n; i += 2) {
        this.process_line(
          pipeline, 
          transformed_points[i], transformed_points[i + 1],
          vertex_outputs[i], vertex_outputs[i + 1]
        );
      }
    } else if (geom.topology === Topology.TRIANGLES) {
      // handle triangles
      // handle three vertices per step
      for (let i = 0; i < n; i += 3) {
        this.process_triangle(pipeline, 
          transformed_points[i], transformed_points[i + 1],
          transformed_points[i + 2], vertex_outputs[i],
          vertex_outputs[i + 1], vertex_outputs[i + 2]);
      }
    }
  }

  /**
   * 
   * @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];

    ...

    // interpolated data buffer
    const data = {};

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

    ...

    // 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++) {
        ...

        // TODO
        // Interpolate the data and store it in the
        //  "data" variable

        ...

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

        ...
      }
    }
  }

  /**
   * Rasterize a line
   * @param {AbstractMat} a 
   * @param {AbstractMat} b 
   * @param {Object<Number|AbstractMat>} data_a 
   * @param {Object<Number|AbstractMat>} data_b 
   */
  rasterize_line(pipeline, a, b,
    data_a = {}, data_b = {}) {
    ...

    // interpolated data buffer
    const data = {};

    // gather attributes
    for (let i in data_a) {
      if (!data_b[i]) {
        continue;
      }
      data[i] = null;
    }

    ...

    for (let x = x0; x <= x1; x++) {
      ...
      
      // TODO
      // Interpolate the data and store it in the
      //  "data" variable

      ...

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

      ...
    }
  }
}

Interpolate values on a line

We have defined a line between two points $\mathbf{A}$ and $\mathbf{B}$ as $\mathbf{P}(t) = \mathbf{A} + t(\mathbf{B} - \mathbf{A})$ .

We can rewrite this as $(1-t)\mathbf{A} + t \mathbf{B}$ .

As before, we get $\mathbf{A}$ for $t=0$ and $\mathbf{B}$ for $t=1$ . Every value of $t$ between $0$ and $1$ produces a point on the line between the two points. That is why we call this linear interpolaton.

Now, we can just apply the same idea to not only the points but any kind of data on the line. So let's say, we have a data attribute for each endpoint $d_{\mathbf{A}}$ and $d_{\mathbf{B}}$ . For the point $\mathbf{P}(t)$ , we calculate the interpolated attribute $d_{\mathbf{P}(t)}$ as:

d_{\mathbf{P}(t)} = (1-t)d_{\mathbf{A}} + t d_{\mathbf{B}}

As long as we can multiply the attribute with a scalar and add two attributes, the above formula is defined, especially for numbers and vectors/matrices!

In our system, we will allow attributes to be numbers and matrices (which includes vectors).

Let's implement this function and see how it looks like. Due to the missing operator overloading, we will have to implement the formula twice, once for numbers and once for matrices. Luckily, the formula is pretty short.

The solution is below to compare your result.

Exercise:

Implement the interpolation formula in interpolate_line in interpolate.js

Solution:

See the solution

Now, when rasterizing, we will just need to calculate the $t$ parameter for the current fragment and interpolate all attributes! The interpolated values will then be passed to the fragment shader.

That is not the only place though. We also need the line interpolation when clipping! When we cut away a part of a polygon edge or line, we need to get the attribute at that newly created vertex!

In that case we already know the $t$ value, since we computed it for the clipping, but how do we get it in general and during line rasterization?

The answer is projection!

For a point $\mathbf{P}$ , we compute the vector from $\mathbf{A}$ to $\mathbf{P}$ . We then compute its projection onto the line direction $\mathbf{B} - \mathbf{A}$ .

The projection is given by the dot product with the normalized direciton vector: $(\mathbf{P} - \mathbf{A}) \cdot \frac{\mathbf{B}-\mathbf{A}}{||\mathbf{B}-\mathbf{A}||}$ .

What we really want though are value between $0$ and $1$ . To get that, we simply divide by the length of the direction vector.

\begin{align*} t &= ((\mathbf{P} - \mathbf{A}) \cdot \frac{\mathbf{B}-\mathbf{A}}{||\mathbf{B}-\mathbf{A}||})\frac{1}{||\mathbf{B}-\mathbf{A}||} \\ &= (\mathbf{P} - \mathbf{A}) \cdot \frac{\mathbf{B}-\mathbf{A}}{||\mathbf{B}-\mathbf{A}||^2} \\ &= \frac{(\mathbf{P} - \mathbf{A}) \cdot(\mathbf{B}-\mathbf{A})}{(\mathbf{B}-\mathbf{A})\cdot (\mathbf{B}-\mathbf{A})} \end{align*}

You can easily verify that you get $0$ and $1$ at the endpoints, by plugging them in.

Now the only thing left to do is to implement it.

We will start with lines and while we are at it also adjust the process_line and clip_line methods. As we already implemented the interpolation method, both of these don't require any special understanding and are shown with their implementation.

clip_line produces clipped attributes in addition to the clipped points. We clip by finding the point on the line that intersects the line with a parameter $t\in[0,1]$ . That is exactly the linear interpolation, so we just call the interpolate_line method for each attribute, when we need to intersect a plane. Note: We could also call the interpolate_line function to get the intersection itself!

As the code basically looks the same as before, we just add the attribute arrays and interpolation call, we opted to just show this.

/**
 * Clips a line 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_line(points, planes, attribs) {
  // successive clipping at each plane
  // clpping a line at a plane is more or less
  //  one step of the
  // Sutherland-Hodgman algorithm, but without 
  //  the polygon wrap-around
  for (let pi = 0; pi < planes.length; pi++) {
      const pl = planes[pi];
      if (points.length === 0) {
        return [[], []];
      }

      // simplified sutherland-hodgman
      const p0 = points[0];
      const p1 = points[1];
      // compute projective distance

      const d0 = dot(pl, p0);
      const d1 = dot(pl, p1);

      // the four cases
      // the actual implementation will combine
      //  them a bit, as there is a bit of overlap

      if (d1 < 0.0 && d0 < 0.0) {
        // case 1 - both outside -> finished
        return [[], []];
      }
      else if (d1 >= 0.0 && d0 >= 0.0) {
        // case 2 - both inside -> continue
        //  with the next plane
        continue;
      }
      else if (d0 >= 0.0 && d1 < 0.0) {
        // case 3 - start inside, end outside
        // compute intersection
        const t = d0 / (d0 - d1);
        const p = add(p0, scale(sub(p1, p0), t));

        //  return startpoint and intersection
        // In this case we will just replace the
        //  points and continue with the next plane;
        points = [p0, p];

        // interpolate attributes
        const p_attribs = {};

        for (let k in attribs[0]) {
          p_attribs[k] =
            this.interpolate_line(attribs[0][k], attribs[1][k], t);
        }
        attribs = [attribs[0], p_attribs];
        continue;
      } else {
        // case 4 - start outside, end inside
        // compute intersection
        const t = d0 / (d0 - d1);
        const p = add(p0, scale(sub(p1, p0), t));


        // return intersection and endpoint
        points = [p, p1];

        // interpolate attributes
        const p_attribs = {};

        for (let k in attribs[0]) {
          p_attribs[k] =
            this.interpolate_line(attribs[0][k], attribs[1][k], t);
        }
        attribs = [p_attribs, attribs[1]];
        continue;
      }
  }
  return [points, attribs];
}

The process_line is only changed such that it passes along the attributes and clipped attributes.

/**
 * Processes a single line
 * @param {Pipeline} pipeline The pipeline to use
 * @param {AbstractMat} v0 The first vertex
 * @param {AbstractMat} v1 The second 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
 */
process_line(pipeline, v0, v1,
  attribs_v0 = {},
  attribs_v1 = {}) {
  // prepare points and data for clipping
  let points = [v0, v1];
  let attribs = [attribs_v0, attribs_v1];
  // clip line
  [points, attribs] = this.clip_line(
    points, pipeline.clip_planes, attribs
  );

  // finally rasterize line
  if (points.length === 2) {
    this.rasterize_line(
      pipeline, points[0], points[1],
       attribs[0], attribs[1]
    );
  }
}

The only missing part of interest is computing the $t$ parameter for the rasterized line. We show lines in a circle with additional clipping planes.

The solutions is below.

Exercise:

Go to the rasterize_line method in interpolate.js
- Compute the interpolation parameter according to $\frac{(\mathbf{P} - \mathbf{A}) \cdot(\mathbf{B}-\mathbf{A})}{(\mathbf{B}-\mathbf{A})\cdot (\mathbf{B}-\mathbf{A})}$

Solution:

See the solution