title: Implementing a scanline algorithm
body: <p>I've been tasked with implementing a version of the scanline algorithm for an assignment.  This program works by reading in a list of vertices and colors from a text file.  Three vertices and three colors are popped from a queue at a time, then the triangle's edges are drawn.  So far, my program does this pretty much perfectly.  Prior to doing this, we were tasked with an assignment that drew rectangles, and it immediately became clear after running tests that the program needed to flip the y coordinates in order for the image to be drawn correctly.</p>
  
  <p>Therein lies the problem.  I found some algorithms for scanline triangle fill functions <a href="http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html" rel="nofollow noreferrer">here</a>, but I noticed that I'd have to modify them in order to account for the fact that the image is flipped.  In a computer graphics grid, higher y values are toward the bottom.  When organizing the three vertices of a given triangle, the normal thing to do is designate the vertex with the lowest y value as the top, and the vertex with the highest y value as the bottom.  I inverted this in order to account for the image flip.</p>
  
  <p>No matter what I do, I can't get my image to fill correctly.  It'll work with these functions as is, so long as I don't flip the y values when individual pixels are drawn and the vertices are sorted in the expected manner where lower y values are toward the top.  However, the resulting image is flipped vertically.</p>
  
  <p>The following functions are pretty much the entirety of the program, aside from the line drawing one which I don't think needs any correction.</p>
  
  <pre><code>void FrameBuffer::drawTriangle(const Vertex&amp; v0, const Vertex&amp; v1, const Vertex&amp; v2, const Color&amp; c0, const Color&amp; c1, const Color&amp; c2, Functional status) {
      //Start by organizing vertices from top to botttom (need to rearrange colors as well)
      Vertex vTop, vMid, vLow;
      Color cTop, cMid, cLow;
  
      vTop = v0;  cTop = c0;
      if (v1[Y] &gt; vTop[Y]) {
          vMid = vTop;    cMid = cTop;
          vTop = v1;      cTop = c1;
      }
      else {
          vMid = v1;      cMid = c1;
      }
  
      if (v2[Y] &gt; vTop[Y]) {
          vLow = vMid;    cLow = cMid;
          vMid = vTop;    cMid = cTop;
          vTop = v2;      cTop = c2;
      }
      else if (v2[Y] &gt; vMid[Y]) {
          vLow = vMid;    cLow = cMid;
          vMid = v2;      cMid = c2;
      }
      else {
          vLow = v2;      cLow = c2;
      }
  
      //Draw the edges of the triangle
      drawLine(vTop, vMid, cTop, cMid, status);
      drawLine(vTop, vLow, cTop, cLow, status);
      drawLine(vMid, vLow, cMid, cLow, status);
  
      //Fill the triangle; first case is flat bottom
      if (vMid[Y] == vLow[Y]) {
          fillFlatBottom(vTop, vMid, vLow, status);
      }
      //Second case is flat top
      else if (vTop[Y] == vMid[Y]) {
          fillFlatTop(vTop, vMid, vLow, status);
      }
      //General case; triangle can be split into flat bottom above a flat top
      else {
          Vertex vNew;        //This represents the point on the triangle across from the "midpoint"
          vNew[Y] = vMid[Y];
          vNew[X] = vTop[X] + ((vMid[Y] - vTop[Y]) / (vLow[Y] - vTop[Y])) * (vLow[X] - vTop[X]);
          vNew[Z] = (vLow[Z] * (vNew[X] - vTop[X]) * (vNew[Y] - vMid[Y]) + vTop[Z] * (vNew[X] - vMid[X]) * (vNew[Y] - vLow[Y]) + vMid[Z] * (vNew[X] - vLow[X]) * (vNew[Y] - vTop[Y]) - vMid[Z] * (vNew[X] - vTop[X]) * (vNew[Y] - vLow[Y]) - vLow[Z] * (vNew[X] - vMid[X]) * (vNew[Y] - vTop[Y]) - vTop[Z] * (vNew[X] - vLow[X]) * (vNew[Y] - vMid[Y])) / ((vNew[X] - vTop[X]) * (vNew[Y] - vMid[Y]) + (vNew[X] - vMid[X]) * (vNew[Y] - vLow[Y]) + (vNew[X] - vLow[X]) * (vNew[Y] - vTop[Y]) - (vNew[X] - vTop[X]) * (vNew[Y] - vLow[Y]) - (vNew[X] - vMid[X]) * (vNew[Y] - vTop[Y]) - (vNew[X] - vLow[X]) * (vNew[Y] - vMid[Y]));
  
          fillFlatBottom(vTop, vMid, vNew, status);
          fillFlatTop(vMid, vNew, vLow, status);
      }
  }
  
  //Draw from bottom up (something is happening here that causes errors)
  void FrameBuffer::fillFlatTop(const Vertex&amp; v0, const Vertex&amp; v1, const Vertex&amp; v2, Functional status) {
      double xSlope1 = -(v2[X] - v0[X]) / (v2[Y] - v0[Y]);
      double xSlope2 = -(v2[X] - v1[X]) / (v2[Y] - v1[Y]);
  
      Vertex curV0 = v2;
      Vertex curV1 = v2;
  
      //v0 is the highest point with the highest y value and v2 is the lowest (for this case) with the lowest y value
      while (curV0[Y] &lt; v0[Y] &amp;&amp; curV1[Y] &lt; v0[Y]) {
          Color curC0 = image.get(curV0[X], curV0[Y]);
          Color curC1 = image.get(curV1[X], curV1[Y]);
  
          drawLine(curV0, curV1, curC0, curC1, status);
  
          curV0[Y] += 1;  curV0[X] -= xSlope1;
          curV1[Y] += 1;  curV1[X] -= xSlope2;
      }
  }
  
  //Draw from top down (something is happening here that causes errors)
  void FrameBuffer::fillFlatBottom(const Vertex&amp; v0, const Vertex&amp; v1, const Vertex&amp; v2, Functional status) {
      double xSlope1 = -(v1[X] - v0[X]) / (v1[Y] - v0[Y]);
      double xSlope2 = -(v2[X] - v0[X]) / (v2[Y] - v0[Y]);
  
      Vertex curV0 = v0;
      Vertex curV1 = v0;
  
      //v0 is the highest point with the highest y value and v1 (for this case) is the lowest with the lowest y value
      while (curV0[Y] &gt;= v1[Y] &amp;&amp; curV1[Y] &gt;= v1[Y]) {
          Color curC0 = image.get(curV0[X], curV0[Y]);
          Color curC1 = image.get(curV1[X], curV1[Y]);
  
          drawLine(curV0, curV1, curC0, curC1, status);
  
          curV0[Y] -= 1;  curV0[X] += xSlope1;
          curV1[Y] -= 1;  curV1[X] += xSlope2;
      }
  }
  </code></pre>
  
  <p>To provide some perspective, this is the resulting image when nothing is filled: <a href="https://imgur.com/a/VOpWJ" rel="nofollow noreferrer">http://imgur.com/a/VOpWJ</a></p>
  
  <p>This occurs when only fillFlatBottom runs: <a href="https://imgur.com/a/nexR9" rel="nofollow noreferrer">http://imgur.com/a/nexR9</a></p>
  
  <p>This occurs when only fillFlatTop runs: <a href="https://imgur.com/a/flRCK" rel="nofollow noreferrer">http://imgur.com/a/flRCK</a></p>
  
  <p>What exactly am I doing wrong?  It's apparent that the line algorithm is not causing this problem.  I'm either calculating the point across from the midpoint (that being vNew) incorrectly or I've messed up the fill algorithms somehow.</p>