If you compiled and ran the line-drawing program to make a line between two specified points, you may have noticed that the line is not always completely solid-looking; Because only one pixel is drawn per row, lines which are more horizontal than vertical end up being broken, more of a dotted line than a solid line. Although this can be fixed, it's probably more trouble than it's worth to do so, and so we'll skip directly to something much more interesting and useful: Making a polygon and filling it.
A triangle is the simplest polygon because it has the minimum required number of sides: Three. (You cannot make a polygon with two sides or less.) Even in the realm of 3D, triangles are popular for one very simple reason: A triangle is always flat. No matter how you twist them around, any three points (even in three-dimensional space) always form a triangle that is a flat plane. The same is not always true for figures with more than three points, and so three-pointed figures are much easier to draw in 3D than shapes with more points.
For now, we'll work on making a triangle in 2D because it's a little simpler. In actuality, however, once you understand how to make a 2D triangle, it's not much harder to make it 3D.
The tricky part of making a filled polygon isn't drawing the sides; We already know a simple way to make a line between two points by just calculating the slope, so you can draw the outline of a triangle by simply making three lines that connect three points. Tricker than this is the act of filling in the triangle; How do you draw every pixel within the boundaries of the triangle?
Once again, we'll do this on a line-by-line basis, turning the triangle into a stack of rows of pixels. If you envision the triangle this way, then it becomes nothing more than a bunch of horizontal lines. The question, then, becomes: How do we know where the left side of each line is, and where the right side is?
The answer, again, is fairly simple: Use an array. For each side of the lines (the left and the right side), make an array that records the horizontal value for each row of pixels. For this example, we'll use arrays called lefts and rights. lefts will hold the left sides for all the rows, and rights will hold the right sides for all the rows. The subscript of the array represents the row; For example, lefts[5] will contain the left-most x coordinate for row 5 on the screen. How do we fill these arrays with the required values? By returning to the slope-using, line-drawing method we used when making a line.
If all this sounds like we're going to be using a lot of variables, you are correct. Let's take a look at the initial variable declarations we might want to use. I used the following lines to declare most of my variables:
double x, y;
double pqxdiff, pqydiff, prxdiff, prydiff, qrxdiff, qrydiff;
double pqm, prm, qrm;
int lefts[400], rights[400];
//Create a structure type called Point, containing an x and a y variable
typedef struct {double x; double y;} Point;
Point p1, p2, p3, p, q, r, temppoint;
As you can see, to make the concept of working with a "point" easier, I created a structure called Point, which cuts down on variable declarations, since a point really has two properties (its X value and its Y value). Then I made seven Point objects.
p1, p2, and p3 are the user-supplied coordinates for each of the three points that make up the triangle. p, q, and r are going to be these same coordinates once they've been sorted; To keep things orderly, I decided to sort the three points by height and name them P, Q, and R respectively, with P being the highest and R being the lowest. This way the user can enter whatever points they want and the program will automatically sort them by height. (What if two of the user-supplied points have the same height? Then this program will crash; So make sure you give different x and y coordinates to each of the points.) X and Y simply represent the point where a pixel is being drawn right now (this changes constantly as the triangle is being drawn). The six "diff" variables represent the distances between each of the points; For example, pqxdiff is the horizontal distance between P and Q. The three "m" variables will be the slope of the three lines of the triangle. Finally, as mentioned, the two arrays "lefts" and "rights" will contain the left and right sides for each of the horizontal lines that will make up our triangle. (The "temppoint" object is just a temporary Point object used for swapping points, as we'll see later.)
Let's initialize each element in both arrays to zero before we begin:
for (int i = 0; i < 400; i++)
{lefts[i] = 0; rights[i] = 0;}
Let's begin the actual program action by prompting the user for the three points:
printf("x1? ");
scanf("%lf", &p1.x);
printf("y1? ");
scanf("%lf", &p1.y);
printf("x2? ");
scanf("%lf", &p2.x);
printf("y2? ");
scanf("%lf", &p2.y);
printf("x3? ");
scanf("%lf", &p3.x);
printf("y3? ");
scanf("%lf", &p3.y);
This is the end of the user's interaction with the program; Once these points have been entered, all that's left is for the program to calculate and draw.
Now let's sort these points by height and put them into P, Q, and R. For this, I first sorted p1, p2, and p3 by height, using the following relatively simple pseudo-algorithm:
If p1 is lower than p2, swap p1 with p2.
If p1 is lower than p3, swap p1 with p3.
If p2 is lower than p3, swap p2 with p3.
These three steps will ensure that p1, p2, and p3 are sorted by height. To accomplish this algorithm, I used the following code:
if (p1.y > p2.y) {temppoint = p1; p1 = p2; p2 = temppoint;}
if (p1.y > p3.y) {temppoint = p1; p1 = p3; p3 = temppoint;}
if (p2.y > p3.y) {temppoint = p2; p2 = p3; p3 = temppoint;}
This may get a little confusing if you don't bear in mind that the HIGHER the value of a point on the screen, the LOWER it will appear on the screen. Y values (vertical values) on a computer screen are numbered starting from 1, which is the top row of pixels, through 2, which is the second-highest row of pixels, etc. So the first line of this code, for example, checks if p1 has a higher Y value than p2, which would mean that p1 is LOWER than p2.
Once p1, p2, and p3 were sorted, you can transfer them all into the points p, q, and r like this:
p = p1; q = p2; r = p3;
Now we can start doing our slope calculations. Remember, to calculate the slope of each of the three lines, we first find the distance between the points, then we divide the horizontal length of the line by the vertical height. For example, here's how we get pqm (the slope of PQ, which is the line from point P to point Q):
if (p.x < q.x) {pqxdiff = q.x - p.x;}
if (p.x > q.x) {pqxdiff = p.x - q.x;}
if (p.x == q.x) {pqxdiff = 0;}
if (p.y < q.y) {pqydiff = q.y - p.y;}
if (p.y > q.y) {pqydiff = p.y - q.y;}
if (p.y == q.y) {pqydiff = 0.01;}
double pqm = pqxdiff / pqydiff;
This code is pretty straightforward: You find out which value is greater, and then subtract the lesser from the greater value to find the difference. If the values are the same, then their difference is zero. The only trip-up is that since the slope is calculated by a division, the divisor can't be zero, or else we get the old classic divide-by-zero error. To avoid this, if the Y values of the points are exactly the same, I set the difference to be 0.01, pretty close to zero, instead of exactly zero. This is probably a pretty stupid way to do this, and I'm sure there's a better and more precise way to deal with the problem, but I'm too lazy to do it right now. :)
Now we have all the locations of the points and the slopes of the lines. So far, so good. Now all that's left is to calculate the leftmost and the rightmost points at each value of Y in the entire polygon. Let's start with PQ, and update our arrays so that they contain the X values for each Y value.
for (y = q.y + 1; y != p.y; y = y - 1)
{
if (p.x > q.x)
{x = x + pqm; lefts[y] = x; rights[y] = x;}
if (p.x < q.x)
{x = x - pqm; lefts[y] = x; rights[y] = x;}
if (p.x == q.x)
{x = x; lefts[y] = x; rights[y] = x;}
}
This for loop gets a little tricky, but all it really does is calculate the X value for each Y value of the line PQ. This should be fairly clear. More involved is the procedure for keeping the arrays meaningful as we check out the other two lines. This for loop looks something like this (here we're doing the line PR):
for (y = p.y + 1; y != r.y; y = y + 1)
{
if (p.x < r.x)
{x = x + prm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (p.x > r.x)
{x = x - prm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (p.x == r.x)
{x = x;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
}
This might look a little hairy, but bear with me, this is as bad as it's going to get. What this for loop does is, again, calculate the X value for each value of Y along the line (only this time the line is PR). If PX is less than RX (which would mean that P is to the left of R), the slope is added to X as we go from P to R (since X must increase to go from P to R). By the same token, if PX is more than RX, then P is to the right of R and we subtract the slope from X as we go from P to R (since X must decrease to go from P to R).
Still with me? Then all that's left are those two long-ish if lines. They're easier to understand than they look, though. Take a look at the first one:
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
If the X value for this point on this line is less than the currently-stored value for this Y point in lefts (that is, if X is left of the point stored previously for this height in lefts), then the value in lefts is not really the left-most value for Y. Remember, lefts is supposed to contain the absolute left-most X value for each value of Y. Get it? So if our current X is farther left than what's in lefts, then lefts doesn't really have the left-most value of X, and we should replace it with the current value of X. That's exactly what this code does. Also, if the value in lefts is 0, then it hasn't been set yet, and we should just set it to the current X value. In English, what this line of code says is:
If x is less than the value stored in lefts for the current value of Y, or if the value stored in lefts for the current value of Y is zero, then set lefts to the current value of X for the current value of Y.
Got it? Good.
Once we have our lefts and rights arrays all created, it's almost amazingly simple to actually draw our triangle. All it takes is a for loop nested inside another for loop:
for (y = p.y + 1; y != r.y - 1; y = y + 1)
{
for (x = lefts[y]; x <= rights[y]; x = x + 1)
{putpixel (x, y, 9);}
}
This means: At each line, start at the leftmost point of the polygon on that pixel row, and just keep drawing pixels until you hit the rightmost point on that row.
Our program's concept is now complete. A complete program which actually works fairly well is given below. This code is not perfect, but it works most of the time.
#include <stdio.h>
#include <graphics.h>
main()
{
double x, y;
double pqxdiff, pqydiff, prxdiff, prydiff, qrxdiff, qrydiff;
double pqm, prm, qrm;
int lefts[400], rights[400];
//Create a structure type called Point, containing an x and a y variable
typedef struct {double x; double y;} Point;
Point p1, p2, p3, p, q, r, temppoint;
//The two lines below initialize lefts and rights so that all elements
//in the arrays are zero.
for (int i = 0; i < 400; i++)
{lefts[i] = 0; rights[i] = 0;}
//Now we prompt the user for the x,y coordinates of the three points.
printf("x1? ");
scanf("%lf", &p1.x);
printf("y1? ");
scanf("%lf", &p1.y);
printf("x2? ");
scanf("%lf", &p2.x);
printf("y2? ");
scanf("%lf", &p2.y);
printf("x3? ");
scanf("%lf", &p3.x);
printf("y3? ");
scanf("%lf", &p3.y);
/* The two lines below just init the graphics mode. */
int gdriver=VGA, gmode=2;
initgraph(&gdriver, &gmode, "C:\\TC\\BGI");
/* Now that we have the three x,y coordinates, we sort them by y value. */
if (p1.y > p2.y) {temppoint = p1; p1 = p2; p2 = temppoint;}
if (p1.y > p3.y) {temppoint = p1; p1 = p3; p3 = temppoint;}
if (p2.y > p3.y) {temppoint = p2; p2 = p3; p3 = temppoint;}
/* ...And now, we assign the three sorted points to be P, Q, and R. */
p = p1; q = p2; r = p3;
//Now let's calculate pqm
//m is the slope, how much x changes when you ++ y
if (p.x < q.x) {pqxdiff = q.x - p.x;}
if (p.x > q.x) {pqxdiff = p.x - q.x;}
if (p.x == q.x) {pqxdiff = 0;}
if (p.y < q.y) {pqydiff = q.y - p.y;}
if (p.y > q.y) {pqydiff = p.y - q.y;}
if (p.y == q.y) {pqydiff = 0.01;}
pqm = pqxdiff / pqydiff;
//pqm (PQ slope) has been calculated.
//Now let's do the arrays from P to Q.
lefts[q.y] = q.x;
x = q.x;
for (y = q.y + 1; y != p.y; y = y - 1)
{
//putpixel (x, y, 9);
if (p.x > q.x)
{x = x + pqm; lefts[y] = x; rights[y] = x;}
if (p.x < q.x)
{x = x - pqm; lefts[y] = x; rights[y] = x;}
if (p.x == q.x)
{x = x; lefts[y] = x; rights[y] = x;}
}
//Arrays from p to q have been calculated
//Now we do the arrays from p to r
//Let's calculate prm
//m is the slope, how much x changes when you ++ y
if (p.x < r.x) {prxdiff = r.x - p.x;}
if (p.x > r.x) {prxdiff = p.x - r.x;}
if (p.x == r.x) {prxdiff = 0;}
if (p.y < r.y) {prydiff = r.y - p.y;}
if (p.y > r.y) {prydiff = p.y - r.y;}
if (p.y == r.y) {prydiff = 0.01;}
prm = prxdiff / prydiff;
//prm (PR slope) has been calculated.
//Now let's do the arrays from P to R.
rights[p.y] = p.x;
x = p.x;
for (y = p.y + 1; y != r.y; y = y + 1)
{
//putpixel (x, y, 9);
if (p.x < r.x)
{x = x + prm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (p.x > r.x)
{x = x - prm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (p.x == r.x)
{x = x;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
}
//Arrays from p to r have been calculated
//Now we do the arrays from q to r
//Let's calculate qrm
//m is the slope, how much x changes when you ++ y
if (q.x < r.x) {qrxdiff = r.x - q.x;}
if (q.x > r.x) {qrxdiff = q.x - r.x;}
if (q.x == r.x) {qrxdiff = 0;}
if (q.y < r.y) {qrydiff = r.y - q.y;}
if (q.y > r.y) {qrydiff = q.y - r.y;}
if (q.y == r.y) {qrydiff = 0.01;}
qrm = qrxdiff / qrydiff;
//qrm (QR slope) has been calculated.
//Now let's do the arrays from Q to R.
x = q.x;
for (y = q.y + 1; y != r.y; y = y + 1)
{
//putpixel (x, y, 9);
if (q.x < r.x)
{x = x + qrm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (q.x > r.x)
{x = x - qrm;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
if (q.x == r.x)
{x = x;
if (x < lefts[y] || lefts[y] == 0) {lefts[y] = x;}
if (x > rights[y] || rights[y] == 0) {rights[y] = x;}}
}
//Arrays from q to r have been calculated
//Time to actually draw the polygon!
for (y = p.y + 1; y != r.y - 1; y = y + 1)
{
for (x = lefts[y]; x <= rights[y]; x = x + 1)
{putpixel (x, y, 9);}
}
//Let's return a nice value just to appease our compiler
return(0);
}