Gouraud Shaded Polygons
WGT Graphics Tutorial #2
Topic: Gouraud Shaded Polygons
By Chris Egerter
October 13, 1994
Contact me at: chris.egerter@homebase.com
Introduction
This series of tutorials describes a method of drawing filled polygons using 3 rendering techniques: Solid, Gouraud shading, and texture mapping.
The code in this tutorial was written in Turbo C++ but can be ported to other graphics libraries and operating systems. I did not use the WGT functions in this one, so the wgtgfx.c file contains a few routines which are needed for the demos. I have decided to explain the method used for these routines since I had to discover them on my own, and think you can learn from the code.
1.0 - Shading Along a Line
The idea behind shading is we want different shades of color along a surface. The simplest application of shading is along a horizontal line. Imagine the line is black at the left end, and white at the right end. A pixel in the middle will be a shade of grey. As the line is drawn from left to right, the color value starts at black and increases by a constant amount towards white. This constant value is determined by the number of colors between the endpoints and the length of the line. Specifically, the constant is equal to the number of colors divided by the number of pixels along the line. If the number of colors equals the number of pixels, the constant is 1, which makes perfect sense. Since we cannot deal with fractions of a color in computer graphics, we will only deal with the integer portion of the color value.
2.0 - Pseudo-code
Our basic shaded line routine looks like this:
Calculate the step value
Make a color variable equal to the left endpoint color.
For x = x1 to x2
Put pixel on screen
Add step value to the color
End for3.0 - Assembly Language Benefits
When dealing with 256 colors, you can fit the color value in one byte. We will use fixed point math to store the step value, that is, 1 byte to store the whole number, and 1 byte to store the fractional portion. By using 1 byte for the fraction, we can store the whole and fractional parts in one integer. This makes it easy in assembly language since we can put these values in a register, say AX, and access each portion individually with AH and AL. In C language you would need to shift the value right 8 times in order to get the whole value. This works out perfectly since we can add a step value to AX, and AH will always contain the color we want to put on the screen. You don't have to worry about the fractional portion carrying over 256 since it will already be added to the whole portion.
4.0 - Calculating the step value in 8.8 fixed point
8.8 means we are using 8 bits for the number before the decimal, and 8 bits for the fraction. You have to think of the fraction in hexadecimal since it will carry at 256 instead of the usual decimal system most people relate to (base 10).
To make a step value with the whole portion in the upper byte, first we need to shift the colors to the left by 8 bits. This will put the color value in the high byte and leave the fraction as 0. Now to calculate the step value, divide it by the length.
eg:
step = (numcolors << 8) / length;5.0 - Code segment 1
We can write a more specific routine now:
void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
{
int length;
int numcolors;
int colorvalue;
int step;
int x;
length = x2 - x1 + 1;
if (length > 0)
{
numcolors = lastcolor - firstcolor + 1;
colorvalue = firstcolor << 8;
step = ((long)numcolors << 8) / (long)length;
for (x = x1; x <= x2; x++)
{
drawpixel (x, y, colorvalue >> 8);
colorvalue += step;
}
}
}x1 is the left coordinate of the line, with firstcolor being the color of this point.
x2 is the right coordinate of the line, with lastcolor being the color of this point.
y is the y coordinate of the horizontal line (you only need one).
drawpixel is a simple function which sets a single pixel to a color.
It is defined as:
void drawpixel (int x, int y, unsigned char col)
{
abuf [y * 320 + x] = col;
}The above code is demonstrated in gshade1.c.
6.0 - Optimization Number 1
Calling drawpixel for each pixel is not very efficient. We know the pixels are one after the other, so it is useless to multiply the y coordinate by 320 every time when we can just move over one pixel.
The following code shows how the drawpixel code has been simplified and put directly into the shadedline routine.
void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
{
int length;
int numcolors;
int colorvalue;
int step;
int x;
unsigned char far * dest; /* Ptr to the screen */
length = x2 - x1 + 1;
if (length > 0)
{
numcolors = lastcolor - firstcolor + 1;
colorvalue = firstcolor << 8;
step = ((long)numcolors << 8) / (long)length;
dest = abuf + y * 320 + x1;
/* Make a pointer to the first pixel */
for (x = x1; x <= x2; x++)
{
*dest++ = colorvalue >> 8;
/* Draw the pixel and move to the next location in memory */
colorvalue += step;
}
}
}The above code is demonstrated in gshade2.c.
7.0 - Optimization Number 2 (ASM)
The other bottleneck in the routine is the colorvalue being shifted right by 8 for every pixel. By using the assembly language registers mentioned earlier, we can take the high byte of colorvalue without shifting.
The code below shows how inline assembly is used to speed up the routine:
void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
{
int length;
int numcolors;
int colorvalue;
int step;
int x;
unsigned char far * dest; /* Ptr to the screen */
length = x2 - x1 + 1;
if (length > 0)
{
numcolors = lastcolor - firstcolor + 1;
colorvalue = firstcolor << 8;
step = ((long)numcolors << 8) / (long)length;
dest = abuf + y * 320 + x1;
/* Make a pointer to the first pixel */
/* Begin assembly optimization */
if (length > 0)
{
asm {
mov cx, word ptr length /* Set length */
les di, dest /* Set destination ptr */
mov ax, word ptr colorvalue /* Set color */
}
shadedlineloop:
;
asm {
mov es:di, ah /* Move color to screen */
add ax, word ptr step /* Add to color */
inc di /* Move to next pixel */
dec cx /* Decrease length */
jnz shadedlineloop /* Repeat for all pixels */
}
}
}
}The above code is demonstrated in gshade3.c.
8.0 - Combining The Shaded Line and Polygon Routines
The next question you may be asking is, "How do I know what colors to use at the endpoints when drawing a polygon?". In order to do this, we have to modify our polygon scan conversion routines I developed in tutorial #1.
The point structure is defined as:
typedef struct
{
int x,y;
} point;Since each vertex now has a color associated with it, we will add another variable to this structure, called col. The point structure becomes the gpoint structure, which looks like this:
typedef struct
{
int x,y;
unsigned char col;
} gpoint;When we converted the polygon into a list of x coordinates, we stored them into two arrays, startx and endx. Now we also need to store the color at both of these coordinates.
Let's make two new arrays:
int startcol[200];
int endcol[200];When the list is created, we will have 2 x coordinates and a color value associated with each of them. This is all the information we need to call the shadedline routine.
The polyline routine becomes the gpolyline routine, which also calculates the colors at the ends of each horizontal line. To do this, we use fixed point math, similar to the way we calculated the colors along the length of the line. This time we are adding the step value to the color for every pixel we move down, instead of across.
void gpolyline (int x1, int y1, int col1, int x2, int y2, int col2)
/* Calculates the coordinates of a line given two
vertices (x1,y1) with color col1, and (x2,y2) with color col2.
We will use fixed point math to speed things up.
The x coordinate is multiplied by 256 and for each row,
a constant m is added to x. This is a simplified version
of a line algorithm because we only have to store 1 x coordinate
for every y coordinate.
The color value is increase by a step value based on the
number of colors between the vertices and the distance between the
y coordinates.
*/
{
int tmp,y;
long x,m;
long col, colstep; /* First color, and the step value */
if (y2 != y1) /* This isn't a horizontal line */
{
if (y2 < y1) /* Make sure y2 is greater than y1 */
{
tmp = y1; /* Swap the y coordinate */
y1 = y2;
y2 = tmp;
tmp = x1; /* Swap the corresponding x coordinates */
x1 = x2;
x2 = tmp;
tmp = col1; /* Swap the corresponding color values */
col1 = col2;
col2 = tmp;
}
x = (long)x1<<8; /* Multiply be 256 */
m = ((long)(x2 - x1)<<8) / ((long)(y2 - y1));
/* m is the fractional amount to add to the x coordinate every row.
m is equal to (delta x) / (delta y). In other words, the x coordinate
has to change by (x2 - x1) columns in (y2 - y1) rows. */
col = (long)col1 << 8; /* Initial color in 8.8 fixed point format */
colstep = ((long)(col2 - col1) << 8) / ((long)(y2 - y1));
/* Calculate the color step value similar to the method in the
shadedline routine, only we're dividing by the delta y value. */
x += m; /* We ALWAYS skip the first point in every line. This is done */
y1++; /* because we do not want to store the point where two lines
meet, twice. This would result in a single point being drawn. */
for (y = y1; y <= y2; y++) /* Go through each row */
{
if ((y >= 0) & (y < 200)) /* If the coordinate is on the screen */
if (startx[y] == -16000) /* Store the first coordinate */
{
startx[y] = x>>8;
startcol[y] = col >> 8; /* store the color */
}
else
{
endx[y] = x>>8; /* Store the last coordinate */
endcol[y] = col >> 8;
}
x += m; /* Add our constant to x */
col += colstep;
}
}
}The fillpoly routine becomes the shadedpoly routine, which calls gpolyline with the correct coordinates and color of each vertex, and finally the shadedline routine.
void shadedpoly (gpoint *vertexlist, int numvertex)
/* Draws a shaded polygon given an array of vertices. */
{
int i;
gpoint *curpt,*nextpt;
/* Two pointers to a vertex. These are used to connect to vertices
together in when calling the gpolyline routine. */
curpt = vertexlist; /* Set to the first vertex in the array */
nextpt = vertexlist + 1; /* and to the second vertex */
for (i = 0; i < 200; i++)
{
startx[i] = -16000; /* Set up our impossible values */
endx[i] = -16000;
}
for (i = 1; i < numvertex; i++)
{
gpolyline (curpt->x, curpt->y, curpt->col,
nextpt->x, nextpt->y, nextpt->col);
/* Calculate the edge of this line. */
curpt += 1; /* Go to the next line */
nextpt += 1;
}
nextpt = vertexlist; /* Now close the polygon by doing a line between
the first and last vertex. */
gpolyline (curpt->x, curpt->y, curpt->col,
nextpt->x, nextpt->y, nextpt->col);
for (i = 0; i < 200; i++) /* Now draw the horizontal line list */
if (startx[i] != -16000) /* Indicates there is a line on this row */
{
if (endx[i] == -16000)
endx[i] = startx[i]; /* In case there was only one
point found on this row */
shadedline (startx[i], startcol[i], endx[i], endcol[i], i);
/* Draw a shaded line between the two x coordinates, on the row i. */
}
}9.0 - What About Clipping?
So far we assumed the x coordinates of the shaded line would fall between 0 and 319 inclusively. What happens if one of the x coordinates does not? The line will wrap around to the other side of the screen. You can try this with any of the first 4 example programs. It will probably cause the system to crash since you are able to write to memory outside the video display memory.
We have already clipped the y coordinate in the shadedpoly routine, so we do not have to worry about that.
There are two possible cases that need clipping:
- The left edge is less than 0
- The right edge is greater than 319
The second case is easy to solve, since you can just decrease the length of the line. In other words, chop off the pixels past 319. Note that you should clip the line AFTER you calculate the step value since changing the length will change the step value as well.
The code for clipping the right side would look something like this:
if (x2 > 319) /* Set right coordinate to right clipping coordinate */
x2 = 319;No other math is required.
The first case is a tricky one. We cannot simply set x1 to 0, since the first color would be wrong. We have to increase the colorvalue to skip over the pixels past the left edge. We know that for each pixel the colorvalue is increased by the step value, so we can multiply the step value by the number of pixels past the left edge and add the result to the colorvalue. This will advance the color to the correct value.
The code for clipping the right edge would look like this:
if (x1 < 0) /* Clip the left edge */
{
dist = 0 - x1; /* Find number of pixels to be clipped */
colorvalue += dist * step;
/* Add dist color steps onto the starting value */
x1 = 0;
/* Set left coordinate to the left clippin coordinate*/
}After the clipping is performed, the length of the line should be recalculated. The shadedline routine now looks like this:
void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
{
int length;
int numcolors;
int colorvalue;
int step;
int x;
unsigned char far * dest; /* Ptr to the screen */
int dist;
length = x2 - x1 + 1;
if (length > 0)
{
numcolors = lastcolor - firstcolor + 1;
colorvalue = firstcolor << 8;
step = ((long)numcolors << 8) / (long)length;
if (x2 > 319) /* Set right coordinate to right clipping coordinate */
x2 = 319;
if (x1 < 0) /* Clip the left edge */
{
dist = 0 - x1; /* Find number of pixels to be clipped */
colorvalue += dist * step;
/* Add dist color steps onto the starting value */
x1 = 0;
/* Set left coordinate to the left clippin coordinate*/
}
dest = abuf + y * 320 + x1;
/* Make a pointer to the first pixel */
length = x2 - x1 + 1;
/* Begin assembly optimization */
if (length > 0)
{
asm {
mov cx, word ptr length /* Set length */
les di, dest /* Set destination ptr */
mov ax, word ptr colorvalue /* Set color */
}
shadedlineloop:
;
asm {
mov es:di, ah /* Move color to screen */
add ax, word ptr step /* Add to color */
inc di /* Move to next pixel */
dec cx /* Decrease length */
jnz shadedlineloop /* Repeat for all pixels */
}
}
}
}10.0 - Other Issues
The example programs included use the default palette. This does not produce a very nicely shaded polygon. You should define your palette with shades of colors. For example, colors 0 to 63 may contain shades of red, while colors 64 to 127 contain shades of blue. The more shades of colors you use, the more realistic the shading will look, and less banding will occur. Banding occurs when you see distinct edges along each color in the polygon. This is caused by the colors being too different.
Gouraud shading also involves calculating the normal of the polygon and comparing it with the direction of the lightsource in order to find realistic values of colors at each vertex. Since this deals with 3D graphics, it is out of the scope of this tutorial. You don't always need to take this into account however. You can base the color on the z value of the vertex, or leave this out completely if you are strictly dealing with 2D graphics. As well, you may want to set the colors of the vertices once and leave them the same throughout the rest of the program.
I hope you enjoyed this tutorial. The next topic is texture mapping, which is only a small change on the code presented here (believe it or not!).
