A Convex Polygon Drawing Technique

code last updated: 5-3-97
last updated: 5-11-97

As a continuation of my WWW pages that discuss how to draw shapes, I have decided to show how the line algorithm can be modified and used to draw convex polygons. I'm not going to optimize this because I haven't the time, but if you want to optimize it for your own purposes, that would be great.

Converting the line algorithm to only follow edges.

When drawing a polygon, you can either make it an outline or filled. I'm going to discuss how to make a filled convex polygon because the outline would be basically just connecting the dots with the line algorithm. To fill a polygon takes more planning and modifications.
For filling a polygon using horizontal lines, it is good to realize that the outer x coordinates of the polygon at a given y coordinate are the only points that are needed. These outer points mark the edge of the polygon and are the points we wish to fill between. Our line algorithm right now draws lines, but it only moves one x coordinate at a time. We need to modify it so that it can jump more than one x coordinate at a time.
This is done easily enough. All we need to do is find out how many whole x amounts are moved for every one y. This makes the normal step equal to x_step = (md / mn). To make the sign the same as the movement value (which is either a positive one or a negative one), we just multiply it by the movement value. Now the slope that the line routine needs to follow has changed because we are skipping all x within the step region. This also means that the y coordinate is moved in every loop. To calculate the new md value, we use the remainder which is md = (md % mn). The new code is: 

void DrawEdge(int x1, int y1, int x2, int y2)
   {
   int mn, md;
   int x_move, y_move;
   int x_position, y_position;
   int balance;

   md = x2 - x1;   // Find md.
   if (md < 0)     // If it is negative,
      {
      md = -md;    // Make mn positive.
      x_move = -1; // Make x move in a negative direction.
      }
   else            // else
      {
      x_move = 1;  // Make x move in a positive direction.
      }

   mn = y2 - y1;   // Find mn.
   if (mn < 0)     // If it is negative,
      {
      mn = -mn;    // Make mn positive.
      y_move = -1; // Make y move in a negative direction.
      }
   else
      {
      y_move = 1;  // Make y move in a positive direction.
      } 

   // ======================= NEW CODE =======================
   if (mn == 0)
      {
      // The line is flat, so only one edge point exists.
      DrawPointAt(x2, y2);   // Draw the point.
      return;
      }

   x_step = (md/mn) * x_move;  // Find the x value always to step by.
   md = (md % mn);      // Find the new slope for finding the singular
                        //    x movements.
   // ========================================================

   x_position = x1;  // Set the starting x position.
   y_position = y1;  // Set the starting y position.

   if (mn < md)          // If the x grows faster than y.
      {
      balance = md;      // Set the balance as positive md.
      }
   else                  // Else
      {
      balance = -(mn);   // Set the balance as negative mn.
      }

   mn = 2 * mn;   // Double mn and md which is the equivalent
   md = 2 * md;   //     of halving balance.

   // While not at the last x and y position, go...
   while ((x_position != x2) || (y_position != y2))
      {
      DrawPointAt(x_position, y_position);   // Draw the point.

      // ======================= NEW CODE =======================
      x_position = x_position + x_step;   // Always step by this amount.
      
      y_position = y_position + y_move;   // Always move forward y.
      balance = balance + md;             // Balance x with y.
      // ========================================================

      // =================== CODE REMOVED HERE ==================
      // ========================================================

      // Putting this here insures x gets a chance to move each time.
      if (balance >= 0)  // If the balance leans toward y...
         {
         balance = balance - mn;           // Balance y with x.
         x_position = x_position + x_move; // Move x in the correct direction.
         }
      }
   DrawPointAt(x_position, y_position);   // Draw the last point.
   }

So you can see where I made changes, I've marked the code by surrounding the new code with comments, and by surrounding the position where old, removed code was found at one time. You should compare this with the normal line drawing routine and see how it was changed. I've tested it, so I don't think the code will over shoot the end point, but if it does, that may cause some problems.

The edge structure (to make things easier).

The rest of the code will have C++ data constructs in it, so if you don't know C++ and can't understand what the code is doing, just read and see if you learn anything that way.
To make things easier to keep track of, I've decided to use a C construct, called a structure. It'll hold much of the edge information that is required to follow the edge of the polygon. It looks as follows: 

// The structure to hold edge information.
struct EdgeInfo
   {
   long balance;  // The balance value.
   long mn;       // The x balancing factor.
   long md;       // The y balancing factor.
   long x_step;   // The amount x moves every step down or up y.
   long x_move;   // The amount x moves every time it needs to rebalance.
   long y_move;   // The amount y moves down (usually 1 for drawing polygon).
   long x_start;  // The x position the edge starts at.
   long y_start;  // The y position the edge starts at.
   long height;   // The height of the edge.
   };

Everything should look familiar to those elements found in the edge drawing algorithm, except for height which is just how far there is still to travel.

Storing points.

Our points will also need to be stored someplace. A circular link list? A fixed or dynamic array? Where? I've chosen to store each point in a structure, and make an array of structures to equal the points in the polygon. I've fixed the array size just for simplicity. Notice how I have a place to put the address of the first point in the array, and a place to put the address of the second point in the array. The type "real" is defined so that it can be any number type you want (even integer, if you wish). 

typedef double real;

struct Point
   {
   real x, y;
   }

struct Polygon
   {
   Point points[20];
   Point *start;
   Point *end;
   };

Setting up the edge structure.

Our edge structure needs to be set up so that it looks similar to the algorithm that draws edges. Because my algorithm to draw convex polygons sets up edges multiple times, it would be nice to put it into a procedure instead of making sloppy code using cut and paste.
The procedure shares all of the same concepts as those in the edge drawing algorithm, so I won't discuss them here. Instead, I suggest you see what it shares and doesn't share with the edge drawing algorithm. Notice that it contains basically everything outside of the loop. The starting part of the procedure is made so that it doesn't get edges that have heights of zero, since those would have no area to draw. It also converts the "real" numbers to integers since the screen is defined by integer points and positions. NOTE: To those who don't know what the '&' (ampersand) means in C++, it makes it so that the variable in the calling function has the final value of the variable in this function. I used this to change the values in edge and update points to point at the next point in the edge. 

void next_edge(int offset, Point *end, Point *start,
	       Point *&points, EdgeInfo &edge)
   {
   Point *points_temp;
   long y_end, x_end;

   // Save the initial point position.
   points_temp = points;

   // Get the y coordinate that will be started at.
   edge.y_start = (long)points->y;
   if (points->y < 0.0) edge.y_start--;

   // Find the position where the height changes.
   for (edge.height = 0; edge.height == 0; )
      {
      // Get the x coordinate that will be started at.
      edge.x_start = (long)points->x;
      if (points->x < 0.0) edge.x_start--;

      // Move to the next point.
      points += offset;

      // Loop if the point went beyond the bounds of the point array.
      if (points < start) points = end;
      else if (points > end) points = start;

      // Make sure this is not looping endlessly.
      if (points == points_temp)
	 {
	 edge.height = 0;
	 return;
	 }

      y_end = (int)points->y;
      if (points->y < 0.0) y_end--;
      edge.height = edge.y_start - y_end;
      }

   // Find md (the slope's denominator).
   x_end = (int)points->x;
   if (points->x < 0.0) x_end--;
   edge.md = x_end - edge.x_start;
   if (edge.md > 0)        // If it is positive,
      {
      edge.x_move = 1;     // Make x move in a positive direction.
      }
   else                    // else
      {
      edge.md = -edge.md;  // Make md positive.
      edge.x_move = -1;    // Make x move in a negative direction.
      }

   // Find mn (the slope's numerator).
   edge.mn = y_end - edge.y_start;
   if (edge.mn > 0)        // If it is positive,
      {
      edge.y_move = 1;     // Make y move in a positive direction.
      }
   else                    // else
      {
      edge.mn = -edge.mn;  // Make mn positive.
      edge.y_move = -1;    // Make y move in a negative direction.
      }

   // Find out the minimum x_step per move in y.
   edge.x_step = (edge.md/edge.mn) * edge.x_move;
   edge.md = (edge.md % edge.mn);  // Make the denominator reflect the change.

   if (edge.mn < edge.md)          // If the x grows faster than y,
      {
      edge.balance = edge.md;      // Set the balance as positive md.
      }
   else                            // Else,
      {
      edge.balance = -(edge.mn);   // Set the balance as negative mn.
      }

   edge.mn = 2 * edge.mn;   // Double mn and md which is the equivalent
   edge.md = 2 * edge.md;   //     of halving balance.
   }

Specifics of drawing the polygon.

I haven't the time to draw any pictures, although pictures would help in the visualization of how polygons should be drawn. Polygons shouldn't overlap, and they need to be drawn correctly so that edges meet. If these criteria aren't met, then shapes can overlap, which means you draw more than you have to, or shapes may not meet, which means you draw less than you should and leave holes in your picture (not a pretty sight). When you are writing more complex polygon drawing algorithms, you might want to anti-alias (blend) polygons together where they meet at one point. That would be another topic however, and would make it more complex, so I'll leave that for another WWW page.
To make visulization easier, I'm going to make the assumption that all points are restricted to integer positions (which is what happens anyway when you deal with pixels on the screen). Now, let's say a line seperating two polygons runs through a point on our integer grid. The common question is, "If we don't want the polygons to overlap, who lays claims to the point?" Which polygon draws a point there? The upper polygon or the lower polygon? The left polygon or the right polygon?
The answer is that you must make a scheme to decide who gets it. The scheme I'm going to choose says, the polygon that is to the right draws the pixel if you can move right and move a little bit up (in fact as long as the small amount up is greater than zero, even though it may approach zero, it should be drawn).
When I find the time, I'll have some graphics to demonstrate this. Meanwhile, see if you can guess what I mean by scribbling on a piece of paper. :-)

Finally drawing the polygon.

Now putting the pieces together, we can finish our convex polygon drawing algorithm. If you wish to look ahead and refer to the procedure as I discuss the individual pieces, that would probably be the best way to understand this algorithm.

The first part of the algorithm just looks for the highest point in the polygon. There may be more than one, but we just care about finding one of those highest points. First it searches from the start to end for the highest point, and then from end to start for the highest point. Because we have confined this polygon to being convex, you can prove to yourself that the highest y value found is the end result of the searching. One of the sides will travel upward toward the top, while the other may travel downward. The side traveling downward will stop quickly, but the side traveling upward will continue until it reaches the top. Notice that I have chosen a large negative value for the starting highest_y. This value must be chosen so that it is lower than or equal to the lowest possible point.
Now if you look at the for loops carefully, you can see that they would overshoot the highest_y position, so I back them up and check to see if they are at the highest_y position. The one not pointing at the highest_y position is set to point at the one pointing at the highest_y position. The reason why we should start at the top is so that all of the polygons will have the same edges if they have the same sides. If you look at the next_edge procedure, you'll see that you get different edges if you go up instead of down. We want to only go either up or down, and I've chosen to go down.

Now using the next_edge, we calculate the starting edge information for the left and right edges. The offset value tells next_edge which way the edges travel in the array. In my case, the edges go clockwise, so I travel backward to get the left edge and forward to get the right edge.

Before we move on, let me explain how I'm handling the case to keep polygons from overlapping. We know that the edge structure moves along the edges. This solves the problem with only drawing something that is inside to the left because if I'm at the right edge, then I'm definitely out, so traveling (redge.x_start - ledge.x_start) from x_start of the left edge will only include the left edge up to the right edge. The little bit up is solved by making sure the height of the edge is non-zero and by not including the bottom of an edge. Traveling only the distance given by height solves this.
Moving on, you should recognize the rest of the polygon drawing algorithm as just the addition of what we left out of DrawEdge when we made next_edge, with the exception of testing to see when we get to the end of an edge to start on a new one. The final product is show below:

void draw_polygon(const Polygon &polygon, unsigned char *screen,
		  const long &screen_height, const long &screen_width,
		  unsigned char color)
   {
   int i;
   real highest_y;
   Point *start, *end;
   Point *left, *right;
   EdgeInfo ledge, redge;

   // Get the beginning and end of the point array for later reference.
   start = polygon.start;
   end = polygon.end;

   // Find the highest point and set the left and right point to start at it.
   for (right = start, highest_y = start->y; right <= end; right++)
      {
      if (right->y >= highest_y)
         {
         left = right;
         highest_y = right->y;
         }
      }
   right = left;   

   // Choose the highest point.
   left += 1;
   if (left->y == highest_y)
      {
      right = left;
      }
   else
      {
      right -= 1;
      left = right;
      }

   // *** Find the initial slopes and destinations. ***

   // First do the left edge.
   next_edge(-1, end, start, left, ledge);

   // Second do the right edge.
   next_edge(1, end, start, right, redge);

   // Go until there is no height to go on the left (or right) side.
   while (ledge.height > 0)
      {
      // Set the pixels.
      for (i = ledge.x_start; i < redge.x_start; i++)
         {
         DrawPointAt(i, ledge.y_start);   // Draw the point.
         }

      // Move down one y.
      ledge.y_start += ledge.y_move;
      redge.y_start += redge.y_move;
      ledge.balance += ledge.md;  // Balance x with y since we moved down one.
      redge.balance += redge.md;  // Balance x with y since we moved down one.

      // *** Update the left edge. ***
      // First move the point in the x direction.
      ledge.x_start += ledge.x_step;
      if (ledge.balance >= 0)        // If the balance leans toward y ...
	 {
	 ledge.balance -= ledge.mn;  // Balance y with x.
	 ledge.x_start += ledge.x_move;    // Move x in the correct direction.
	 }

      // Check to see if we are starting a new edge.
      if (--ledge.height <= 0)
	 {
	 // Moving to a new edge.
	 next_edge(-1, end, start, left, ledge);
	 }

      // *** Update the right edge. ***
      // First move the point in the x direction.
      redge.x_start += redge.x_step;
      if (redge.balance >= 0)        // If the balance leans toward y ...
	 {
	 redge.balance -= redge.mn;     // Balance y with x.
	 redge.x_start += redge.x_move; // Move x in the correct direction.
	 }

      // Check to see if we are starting a new edge.
      if (--redge.height <= 0)
	 {
	 // Moving to a new edge.
	 next_edge(1, end, start, right, redge);
	 }
      }
   }

I've tested this and it worked for me. If you find that it doesn't work, don't be afraid to let me know, so I can either help you make it work or fix it.

Improvements to drawing the polygon.

A few days after writing the first edition of this, I thought of some problems that may be encountred while using this polygon algorithm. Most specifically, if the polygons don't share the verticies of an adjacent edge, then holes may show up where they are supposed to meet. This problem is quickly identified as being a bi-product of the starting value that is placed in balance (this is calculated in the next_edge procedure). In the normal version, a value equal in magnitude of the most dominant (largest in magnitude) of mn and md is used in balancing the procedures. The factors mn and md are then multiplied by two to make the line more pleasing to look at. If you start the line at a different y position, it will look the same. This means two adjacent lines with the same slope may have some overlapping and some points that don't meet. Apparently we aren't getting what we want.

To make the balancing factor more position dependant, some more math will be necessary to choose a correct value. We know the end value has to be less than or equal to the most dominant of mn or md, so the answer will envolve a modulus. It also must be dependant on the slope of the line, so that depending on where the line is, the starting position will be different. The answer to our problem is (x_start*mn)%md, when x_start >= 0, or -((y_start*md)%mn), when y_start >= 0, depending on the size md or mn. You also must handle the case where the used coordinate (x_start or y_start) is negative. The updated code shows an example of how this can be handled (actually, it is only partial and doesn't quite work yet).

Another improvement is to realize that mn > md at all times in our drawing polygon algorithm, so we can ignore the first case and only use the second case. The updated code is show below: 

void next_edge(int offset, Point *end, Point *start,
	       Point *&points, EdgeInfo &edge)
   {
   Point *points_temp;
   long y_end, x_end;

   // Save the initial point position.
   points_temp = points;

   // Get the y coordinate that will be started at.
   edge.y_start = (long)points->y;
   if (points->y < 0.0) edge.y_start--;

   // Find the position where the height changes.
   for (edge.height = 0; edge.height == 0; )
      {
      // Get the x coordinate that will be started at.
      edge.x_start = (long)points->x;
      if (points->x < 0.0) edge.x_start--;

      // Move to the next point.
      points += offset;

      // Loop if the point went beyond the bounds of the point array.
      if (points < start) points = end;
      else if (points > end) points = start;

      // Make sure this is not looping endlessly.
      if (points == points_temp)
	 {
	 edge.height = 0;
	 return;
	 }

      y_end = (int)points->y;
      if (points->y < 0.0) y_end--;
      edge.height = edge.y_start - y_end;
      }

   // Find md (the slope's denominator).
   x_end = (int)points->x;
   if (points->x < 0.0) x_end--;
   edge.md = ((int)points->x) - edge.x_start;
   if (edge.md > 0)        // If it is positive,
      {
      edge.x_move = 1;     // Make x move in a positive direction.
      }
   else                    // else
      {
      edge.md = -edge.md;  // Make md positive.
      edge.x_move = -1;    // Make x move in a negative direction.
      }

   // Find mn (the slope's numerator).
   edge.mn = y_end - edge.y_start;
   if (edge.mn > 0)        // If it is positive,
      {
      edge.y_move = 1;     // Make y move in a positive direction.
      }
   else                    // else
      {
      edge.mn = -edge.mn;  // Make mn positive.
      edge.y_move = -1;    // Make y move in a negative direction.
      }

   // Find out the minimum x_step per move in y.
   edge.x_step = (edge.md/edge.mn) * edge.x_move;
   edge.md = (edge.md % edge.mn);  // Make the denominator reflect the change.

   // ======================= CODE CHANGED =======================
   // The y position changes faster than the x, so set the balance as a
   //    portion of mn.

   // Set the balance as a portion of negative mn.
   if (edge.y_start >= 0)
      edge.balance = -((edge.y_start*edge.md)%edge.mn);
   else
      edge.balance = -(edge.mn - ((edge.y_start*edge.md)%edge.mn));
   // ============================================================
   }

Problems with imperfect polygons.

Through the process of actually putting my polygon drawing algorithm to the real test (in a 3D application), I have found that it lacks the constructs necessary to combat imperfections in floating point math. Every once in awhile, a floating point number has a chance to become minutely off, just enough to leave a crack between two polygons. The easiest method to combat this problem is to update the polygon drawing algorithms to draw everything that could possibly be contained within the polygon's edges, instead of the ideal method of only drawing enough. This can cause overlap between polygons, but it is a simple way of removing those pesky cracks that appear otherwise. (In fact, this is the method I prefer at the moment. I will be searching for better ways of confronting this problem when I have time.)

Special thanks to:

Professor Forsyth, for teaching CS184 where much of what I learned during lecture helped me to understand this technique better. Without the increased understanding, I may not have been able to do as well with writing this WWW page.

joshuacantrell@yahoo.com
(My Home Page) - (My Personal Page) - (My Computer Science Page) - (My Resume)