The Scanline Polygonfill algorithm in Cocoa (Objective C)

The Scanline Polygonfill algorithm draws a filled polygon into our custom framebuffer MYDraw. The algorithm is used to draw individual filled polygons of your 3D objects. It replaces Cocoa's [NSBezierPath fill].

Scanlines

The Scanline Polygonfill algorithm is named after the fact that it uses "scanlines" to draw filled polygons. Scanlines are horiziontal lines within a polygon. Think of a scanner reading in the polygon from top to bottom, one horizontal line after the other — or even better, think of a plotter printing the image of a polygon, one horizontal line after the other. You probably could call it Polygonfill Plotter algorithm instead, but you couldn't google for that.

In short, our goal is to fill up the polygon's shape from top to bottom with horizontal lines. I'm going to use images to describe how it works.

	You start by determining the top vertex. It's the vertex with the smallest y value — remember the framebuffer is up-side-down.
	We defined all polygons anti-clockwise, so we can certainly identify the next two vertices A1 and B1 to the "left" and "right" of the top vertex. Thanks to the Bresenham algorithm we can easily calculate the individual pixels on both edges Start-A1 and Start-B1. We start at the first pixels and draw the wireframe portion of both edges. Then we fill the horizontal line (scanline) in between. And so on, pixel by pixel "downward".
	The scanline reached A1: The first edge on the "left" side is finished! We identify the next vertex A2 to the "left" and mark it as our new goal. Our goal on the "right" side, B1, remains the same.
	We draw the wireframe portions of the edges between the A1-A2 and Start-B1, and fill up the scanlines in between.
	The scanline reached B1: The first edge on the "right" side is finished! We identify the next vertex to the "right", B2, and mark it as our new goal. Our goal on the "left" side, A2, remains the same.
	We again draw the wireframe portions of the edges between A1-A2 and B1-B2, and fill up the scanlines in between.
	We reached A2: The second edge on the "left" side is finished! We identify the next vertex to the "left", A3, and mark it as our new goal. A3 happens to be the same vertex which is our goal on the "right" side, B2.
	We again draw the wireframe portions of the edges between the A2-A3 and B1-B2, and fill up the scanlines in between. When we reach the last vertex A3=B2, the vertexcounter is zero, and the loop ends.

This algorithm also works for cubes — filling in the first scanline immediately completes the first horizontal edge, and the next vertex is selected as goal. Then the algorithm fills in the cube's main area between the two next vertical edges. The last scanline also completes the last horizontal edge, and the algorithm finishes.

Implementation

I implemented the Scanline Polygonfill algorithm as a method in my MYDraw framebuffer object. It directly relies on the following of MYDraw's instance variables:

• vertexNum — (the number of vertices of the polygon to draw),
• ppr — the number of pixels per row in the framebuffer
• two NSMutableArrays, vertexListX and vertexListY, containing the vertices' x and y values respectively (this is instead of an array of structs).
• an NSBitmapImageRepresentation named bitmap, containing byte which represent the framebuffer's individual pixels.

- (void) drawFilledPolygon
{
    /* ---- Draw a polygon with a solid color ---------------------
    *  Scanline-Algorithm: Start at the Polygon's top vertex and calculate
    *  the pixels of the edges to the left (anti-clockwise) and right (clockwise).
    *  Go from top to bottom, filling up all the space between two edges
    *  with horizontal scanlines. Edges between which scanlines are drawn
    *  can be (but do not have to be) connected. 
    *  E.g. if one of the edges is horizontal, draw it, and immediately continue
    *  with the next edge in that direction, either clockwise or anti-clockwise.
    */
  long    i;                         /* top vertex loop counter */
  short   dx1, dx2;                  /* x length of sides in pixels */
  short   dy1, dy2;                  /* y length of sides in pixels*/
  short   topVertex;                 /* Index of top vertex */
  int     edgeCounter=vertexNum-1;   /* Number of vertices in this polygon
                                     (last vertex = first, can be skipped) */
  
  /* These variables define which two edges (1 & 2) we're drawing 
   * horizontal scanlines between. start1 and end1 are the starting and
   * ending array indices of edge #1; xStart1, yStart1, xEnd1,
   * and yEnd1 are the screen coordinates of line #1. Each of these
   * has a counterpart for line #2. 
   */
  int    start1, end1;     // edge1 Vertex index
  int    xStart1, yStart1; // edge1 coordinates in pixels
  int    xEnd1, yEnd1;     // edge1 coordinates in pixels
  int    start2, end2;     // edge2 Vertex index
  int    xStart2, yStart2; // edge2 coordinates in pixels  
  int    xEnd2, yEnd2;     // edge2 coordinates in pixels
  int    pixelOffset1, pixelOffset2; // index of pixel in framebuffer

  /* Figure out which vertex is at the top of the polygon */
  {
    short  topVertexY;     
    /* Start by assuming the first vertex is on top */
    topVertex = 0;      // (result variable)
    topVertexY = [[vertexListY objectAtIndex:0] intValue]; // y-coordinate
    /* loop through all of the following vertices */
    for (i = 1; i < vertexNum-1; i++) {
      /* Compare to see if the stored vertex is higher
       * than the current one.
       */
      if ([[vertexListY objectAtIndex:i] intValue] < topVertexY) { 
        /* It is higher. Remember it for later */
        topVertex = i;
        topVertexY = [[vertexListY objectAtIndex:i] intValue];
      }
    }
  }
  
  /* Find the starting and ending vertices for the first
   * two edges to the left and right of the top vertex.
   */
  start1 = topVertex;
  start2 = topVertex;  /* They both start from the same vertex */
  xStart1 = [[vertexListX objectAtIndex:start1] intValue];
  yStart1 = [[vertexListY objectAtIndex:start1] intValue];
  xStart2 = [[vertexListX objectAtIndex:start2] intValue];
  yStart2 = [[vertexListY objectAtIndex:start2] intValue];
  
  /* Get the end of edge 1 - check for wrap-over */
  end1 = start1 - 1;
  if (end1 < 0)
      end1 = vertexNum-2;
  xEnd1 = [[vertexListX objectAtIndex:end1] intValue];
  yEnd1 = [[vertexListY objectAtIndex:end1] intValue];
  
  /* Get the end of edge 2 - check for wrap-over */
  end2 = start2 + 1;
  if (end2 >= vertexNum-1) 
    end2 = 0;
  xEnd2 = [[vertexListX objectAtIndex:end2] intValue];
  yEnd2 = [[vertexListY objectAtIndex:end2] intValue];
  
  /* Our setup is done. Start the drawing */
  
  /* Set up the offsets for both edges */ 
  pixelOffset1 = (ppr * yStart1) + (xStart1);
  pixelOffset2 = (ppr * yStart2) + (xStart2);

  while (edgeCounter > 0) {  /* Draw until we're out of edges */
    int    errorTerm1, errorTerm2;
    int    xUnit1, yUnit1;
    int    xUnit2, yUnit2;
    int    count1, count2;
    int    length;
    int    linePixelPtr;

    /* Initialize error terms */
    errorTerm1 = errorTerm2 = 0;
    
    /* Find the x length of edges */
    dx1 = xEnd1 - xStart1;
    /* If the line is going to the left, set the
     * xUnit to -1 and make dx positive
     */
    if (dx1 < 0) {
      dx1 = -dx1;
        xUnit1 = -1;
    } else {
      xUnit1 = 1;
    }
    /* Do the same for edge 2 */
    dx2 = xEnd2 - xStart2;
    if (dx2 < 0) {
      dx2 = -dx2;
      xUnit2 = -1;
    } else {
      xUnit2 = 1;
    }
    
    /* Find the y length of the edges */
    dy1 = yEnd1 - yStart1;
    yUnit1 = ppr;
    
    dy2 = yEnd2 - yStart2;
    yUnit2 = ppr; 
    
    /* Use one of four different methods for drawing between
     * differently sloped edges */
    /* Case 1 */
    if (dx1 > dy1) {     /* Edge 1 slope is < 1 */
      if (dx2 > dy2) {   /* Edge 2 slope is < 1 */
        /* Figure out how many pixels to draw in each edge */
        count1 = dx1;
        count2 = dx2;
        
        /* Draw until one of the edges is done */
        while (count1 && count2) {
          /* Draw the wireframe portion of the line
           * until we're ready to jump down a pixel */
          while ((errorTerm1 < dx1) && (count1 > 0)) {
            count1--;            /* Count off this pixel */
            pixelOffset1 += xUnit1;  /* Point to next pixel */
            xStart1 += xUnit1;

            /* Increase the error term */
            errorTerm1 += dy1;
            
            /* Check to see if we're ready to move in y */
            if (errorTerm1 < dx1) {
              /* Nope, we're not ready yet. Plot a pixel for
               * this line
               */
                [self setPixel:pixelOffset1 to:color]; // draw wireframe
            }
          }
          /* Reset the error term */
          errorTerm1 -= dx1;
          
          /* Now do the same thing to edge 2 */
          
          while ((errorTerm2 < dx2) && (count2 > 0)) {
            count2--;     /* Count off this pixel */
            pixelOffset2 += xUnit2;   /* Point to next pixel */
            xStart2 += xUnit2;

            /* Increase the error term */
            errorTerm2 += dy2;
            
            /* Are we ready to move in y? */
            if (errorTerm2 < dx2) {
                /* We're not ready yet. Plot a pixel */
                [self setPixel:pixelOffset2 to:color]; // draw wireframe
            }
          }
          
          /* Reset the error term */
          errorTerm2 -= dx2;

          /* FILLING: Draw the line from edge 1 to edge 2.
           * Find the length of the line:
           */
          length = (pixelOffset2 - pixelOffset1); 
          if (length < 0) {  /* If negative... */
              length = -length;  /* make it positive */
              linePixelPtr = pixelOffset2;
          } else {
              linePixelPtr = pixelOffset1;
          }
          while (length--)
          {
              [self setPixel:linePixelPtr to:color]; // fill a scanline
              linePixelPtr++;
          }
          
          /* Advance to next line */
          pixelOffset1 += yUnit1;
          yStart1++;
          pixelOffset2 += yUnit2;
          yStart2++;
        }
      } else {
              /* Case 2 */
        /* Edge 2 slope is >= 1 */

        /* Increment edge 1 on x and edge 2 on y */
        count1 = dx1;
        count2 = dy2;

        /* Draw until one of the edges is done */
        while (count1 && count2) {
          /* Draw the wireframe portion of the line
           * until we're ready to jump down a pixel  */
          
          while ((errorTerm1 < dx1) && (count1 > 0)) {
            count1--;           /* Count off this pixel */
            pixelOffset1 += xUnit1;  /* Point to next pixel */
            xStart1 += xUnit1;
            
            /* Increase the error term */
            errorTerm1 += dy1;
            
            /* Check to see if we're ready to move in y */
            if (errorTerm1 < dx1) {
                /* Nope, we're not ready yet. Plot a pixel for
                * this line */
                [self setPixel:pixelOffset1 to:color]; // draw wireframe
            }
          }
          /* Reset the error term */
          errorTerm1 -= dx1;
          
          /* Now handle edge 2 */
          errorTerm2 += dx2;  // Increment error term
          
          /* Check to see if it's time to move in the x
           * direction. If so, reset the error term
           * and increment the pixelOffset */
          if (errorTerm2 >= dy2) {
            errorTerm2 -= dy2;
            pixelOffset2 += xUnit2;
            xStart2 += xUnit2;
          }
          count2--;

          /* Draw the line from edge 1 to edge 2.
           * Find the length of the line:
           */
          length = (pixelOffset2 - pixelOffset1); 
          if (length < 0) {  /* If negative... */
              length = -length;  /* make it positive */
              linePixelPtr = pixelOffset2;
          } else {
              linePixelPtr = pixelOffset1;
          }
          while (length--)
          {
              [self setPixel:linePixelPtr to:color]; // fill a scanline
              linePixelPtr++;
          }
          
          /* Advance to next line */
          pixelOffset1 += yUnit1;
          yStart1++;
          pixelOffset2 += yUnit2;
          yStart2++;
        }
      }
    } else{
      /* Edge 1 slope is >= 1 */
      if (dx2 > dy2) {  /* Case 3 */
        /* Edge 2 slope is < 1 */

        /* Increment edge 1 on y and edge 2 on x */
        count1 = dy1;
        count2 = dx2;
        
        /* Draw until one edge is done */
        while (count1 && count2) {
          /* Process edge 1 */
          
          /* Initialize edge 1 errorterm */
          errorTerm1 += dx1;
          
          /* If it's time to move in the x dimension, reset
           * error term and move offset to the next pixel
           */
          if (errorTerm1 >= dy1) {
            errorTerm1 -= dy1;
            pixelOffset1 += xUnit1;
            xStart1 += xUnit1;
          }
          count1--;
          
          /* Handle the second edge */
          
          while ((errorTerm2 < dx2) && (count2 > 0)) {
            count2--;     /* Count off this pixel */
            pixelOffset2 += xUnit2;  /* Point to next pixel */
            xStart2 += xUnit2;
          
            /* Increase the error term */
            errorTerm2 += dy2;
            
            /* Are we ready to move in y? */
            if (errorTerm2 <= dx2) {
              /* We're not ready yet. Plot a pixel */
                [self setPixel:pixelOffset2 to:color];  // draw wireframe
            }
          }
          
          /* Reset the error term */
          errorTerm2 -= dx2;
          
          /* Draw the line from edge 1 to edge 2.
           * Find the length of the line:
           */
          length = (pixelOffset2 - pixelOffset1); 
          if (length < 0) {  /* If negative... */
              length = -length;  /* make it positive */
              linePixelPtr = pixelOffset2;
          } else {
              linePixelPtr = pixelOffset1;
          }
          while (length--)
          {
              [self setPixel:linePixelPtr to:color]; // fill a scanline
              linePixelPtr++;
          }
          
          /* Advance to next line */
          pixelOffset1 += yUnit1;
          yStart1++;
          pixelOffset2 += yUnit2;
          yStart2++;
        }
      } else {  /* Case 4 */
        /* Edge 2 slope >= 1. Increment edge 1 and edge 2 on y
         */

        count1 = dy1;
        count2 = dy2;

        /* Draw until one edge is done */
        
        while (count1 && count2) {
          /* Handle edge 1 */
          
          /* Initialize edge 1 errorterm */
          errorTerm1 += dx1;
          
          /* If it's time to move in the x dimension, reset
           * error term and move offset to the next pixel
           */
          if (errorTerm1 >= dy1) {
            errorTerm1 -= dy1;
            pixelOffset1 += xUnit1;
            xStart1 += xUnit1;
          }
          count1--;

          /* Now handle edge 2 */
          
          errorTerm2 += dx2;  /* Increment error term */
          
          /* Check to see if it's time to move in the x
           * direction. If so, reset the error term
           * and increment the pixelOffset
           */
          if (errorTerm2 >= dy2) {
            errorTerm2 -= dy2;
            pixelOffset2 += xUnit2;
            xStart2 += xUnit2;
          }
          count2--;

          /* Draw the line from edge 1 to edge 2.
           * Find the length of the line:
           */
          length = (pixelOffset2 - pixelOffset1);
          if (length < 0) {  /* If negative... */
              length = -length;  /* make it positive */
              linePixelPtr = pixelOffset2;
          } else {
              linePixelPtr = pixelOffset1;
                                        }
              while (length--)
                                        {
              [self setPixel:linePixelPtr to:color];// fill
              linePixelPtr++;
          }
          
          /* Advance to next line */
          pixelOffset1 += yUnit1;
          yStart1++;
          pixelOffset2 += yUnit2;
          yStart2++;
        }
      }
    }

    /* An edge is done. Start another edge, if there are any remaining */
    if (count1 == 0) {
      /* Edge 1 is complete. Decrement the edgeCounter */
      edgeCounter--;

      /* Make the ending vertex into the starting vertex */
      start1 = end1;
      
      /* Get a new ending vertex */
      end1 -= 1;
      
      /* Check to see if this vertex wraps to the beginning */
      if (end1 < 0) {
        end1 = vertexNum-2;
      }

      /* Get the x & y of the new ending vertex */
      xEnd1 = [[vertexListX objectAtIndex:end1] intValue];
      yEnd1 = [[vertexListY objectAtIndex:end1] intValue];
    }

    if (count2 == 0) {
      /* Edge 2 is complete. Decrement the edge count */
      edgeCounter--;

      /* Make ending vertex 2 into starting vertex 2 */
      start2 = end2;
      
      /* Get a new ending vertex */
      end2++;
      
      /* Check to see if this vertex wraps to the beginning */
      if (end2 >= vertexNum-1) {
        end2 = 0;
      }

      /* Get the x & y of new ending vertex */
      xEnd2 = [[vertexListX objectAtIndex:end2] intValue];
      yEnd2 = [[vertexListY objectAtIndex:end2] intValue];
    }

  }
}