Rendering 3d From Scratch Chapter 6 - Coloring Screen Polygons

Let’s recap what we’ve accomplished so far:

  • Modelled 3d polyhedra

  • Created a “scene” with polyhedra in it

  • Created a “camera” object with a camera plane, and a point of interest

  • Projected faces from our polyhedra to our camera plane

And keep in mind, we’ve done this with very little prior knowledge and only a few new mathematical tools. Great work, take a bow!

Now, let’s figure out one of the last pieces: coloring in our projected faces. For each face on our polyhedra, we have a list of “screen points” (screen points are (x,y), points on our drawing canvas). Consecutive screen points represent edges.

We’ll use a process called scanline filling to accomplish our goal. Conceptually, scanline filling is pretty simple. We start by gathering all of our screen points, and determining the min and max values in our y coordinate. From there, we iterate from our min y point to our max y point and we fill in lines along the x axis. The borders of our lines are determined by intersections with our edges. If there are more than 2 intersections, sets of pairs are filled in.

linefill_algo.gif

The algorithm can be broken up into two parts:

  • One function whose sole responsibility is to figure out x intersections given a y value

  • Another function that loops through y values, uses the first function, and fills in pixels between x intersections.

Here’s the two functions. Our screenbuffer from the previous post is being used:

Renderer.prototype._getXIntersections = function (y, allPixels) {
  var xIntersections = [];

  var prev = allPixels[allPixels.length - 1];
  for (var i = 0; i < allPixels.length; i++) {
    var px = allPixels[i];
    if (px.y == y) {
      xIntersections.push(px);
    } else if ((prev.y < y && y < px.y) || (px.y < y && y < prev.y)) {
      var yDir = px.y - prev.y;
      var xDir = px.x - prev.x;

      var t = (y - prev.y) / yDir;
      var xIntersection = Math.round(prev.x + xDir * t);
      xIntersections.push(xIntersection);
    }
    prev = px;
  }

  xIntersections.sort(function (xi1, xi2) {
    return xi1 - xi2;
  });

  return xIntersections;
}

Renderer.prototype._fillScanlines = function (minY, maxY, pixels, rgb) {
  for (var y = Math.max(0, minY); y <= Math.min(this.screenBuffer.height - 1, maxY); y++) {
    var xIntersections = this._getXIntersections(y, pixels);

    for (var i = 1; i < xIntersections.length; i += 2) {
      var x1 = xIntersections[i - 1];
      var x2 = xIntersections[i];

      for (var x = Math.max(0, x1.x); x <= Math.min(x2.x, this.screenBuffer.width - 1); x++) {
        this.screenBuffer.setPixel(new Pixel(x, y), rgb);
      }
    }
  }
}

This algorithm is another puzzle piece slotted into place, and next time we’ll put all these pieces together and render some things to the screen!

Jon Bedard3d drawing