home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / GPOLY.TXT < prev    next >
Text File  |  1996-07-23  |  17KB  |  523 lines

  1.               WGT Graphics Tutorial #2
  2.            Topic: Gouraud Shaded Polygons
  3.               By Chris Egerter
  4.               October 13, 1994
  5.              Contact me at: chris.egerter@homebase.com
  6.  
  7. Introduction
  8. ------------
  9.    This series of tutorials describes a method of drawing filled polygons
  10. using 3 rendering techniques: Solid, Gouraud shading, and texture mapping.
  11.  
  12. The code in this tutorial was written in Turbo C++ but can be ported to
  13. other graphics libraries and operating systems.  I did not use the
  14. WGT functions in this one, so the wgtgfx.c file contains a few routines
  15. which are needed for the demos.  I have decided to explain the method
  16. used for these routines since I had to discover them on my own, and
  17. think you can learn from the code.
  18.  
  19.  
  20. 1.0 - Shading Along a Line
  21. --------------------------
  22. The idea behind shading is we want different shades of color along a surface.
  23. The simplest application of shading is along a horizontal line.  Imagine
  24. the line is black at the left end, and white at the right end.  A pixel in
  25. the middle will be a shade of grey.   As the line is drawn from left to
  26. right, the color value starts at black and increases by a constant amount
  27. towards white.  This constant value is determined by the number of colors
  28. between the endpoints and the length of the line.  Specifically, the
  29. constant is equal to the number of colors divided by the number of pixels
  30. along the line.  If the number of colors equals the number of pixels,
  31. the constant is 1, which makes perfect sense.  Since we cannot deal with
  32. fractions of a color in computer graphics, we will only deal with the integer
  33. portion of the color value.
  34.  
  35. 2.0 - Pseudo-code
  36. -----------------
  37. Our basic shaded line routine looks like this:
  38.   Calculate the step value
  39.   Make a color variable equal to the left endpoint color.
  40.   For x = x1 to x2
  41.     Put pixel on screen
  42.     Add step value to the color
  43.   End for
  44.  
  45. 3.0 - Assembly Language Benefits
  46. --------------------------------
  47. When dealing with 256 colors, you can fit the color value in one byte.
  48. We will use fixed point math to store the step value, that is, 1 byte to
  49. store the whole number, and 1 byte to store the fractional portion.
  50. By using 1 byte for the fraction, we can store the whole and fractional
  51. parts in one integer.  This makes it easy in assembly language since we
  52. can put these values in a register, say AX, and access each portion
  53. individually with AH and AL.  In C language you would need to shift the
  54. value right 8 times in order to get the whole value.  This works out
  55. perfectly since we can add a step value to AX, and AH will always contain
  56. the color we want to put on the screen.  You don't have to worry about
  57. the fractional portion carrying over 256 since it will already be added
  58. to the whole portion.
  59.  
  60. 4.0 - Calculating the step value in 8.8 fixed point
  61. ---------------------------------------------------
  62. 8.8 means we are using 8 bits for the number before the decimal, and
  63. 8 bits for the fraction.   You have to think of the fraction in hexadecimal
  64. since it will carry at 256 instead of the usual decimal system most people
  65. relate to (base 10).
  66.  
  67. To make a step value with the whole portion in the upper byte, first we
  68. need to shift the colors to the left by 8 bits.  This will put the
  69. color value in the high byte and leave the fraction as 0.  Now to calculate
  70. the step value, divide it by the length.
  71.  
  72. eg:  step = (numcolors << 8) / length;
  73.  
  74.  
  75. 5.0 - Code segment 1
  76. --------------------
  77. We can write a more specific routine now:
  78.  
  79. void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
  80. {
  81. int length;
  82. int numcolors;
  83. int colorvalue;
  84. int step;
  85. int x;
  86.  
  87.  length = x2 - x1 + 1;
  88.  if (length > 0)
  89.  {
  90.   numcolors = lastcolor - firstcolor + 1;
  91.  
  92.   colorvalue = firstcolor << 8;
  93.   step = ((long)numcolors << 8) / (long)length;
  94.   for (x = x1; x <= x2; x++)
  95.     {
  96.      drawpixel (x, y, colorvalue >> 8);
  97.      colorvalue += step;
  98.     }
  99.  }
  100. }
  101.  
  102.  
  103. x1 is the left coordinate of the line, with firstcolor being the color
  104. of this point.
  105.  
  106. x2 is the right coordinate of the line, with lastcolor being the color
  107. of this point.
  108.  
  109. y is the y coordinate of the horizontal line (you only need one).
  110.  
  111. drawpixel is a simple function which sets a single pixel to a color.
  112. It is defined as:
  113.  
  114. void drawpixel (int x, int y, unsigned char col)
  115. {
  116.  abuf [y * 320 + x] = col;
  117. }
  118.  
  119. The above code is demonstrated in gshade1.c.
  120.  
  121.  
  122.  
  123. 6.0 - Optimization Number 1
  124. ---------------------------
  125. Calling drawpixel for each pixel is not very efficient.  We know the
  126. pixels are one after the other, so it is useless to multiply the y
  127. coordinate by 320 every time when we can just move over one pixel.
  128.  
  129. The following code shows how the drawpixel code has been simplified and
  130. put directly into the shadedline routine.
  131.  
  132. void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
  133. {
  134. int length;
  135. int numcolors;
  136. int colorvalue;
  137. int step;
  138. int x;
  139. unsigned char far * dest;   /* Ptr to the screen */
  140.  
  141.  length = x2 - x1 + 1;
  142.  if (length > 0)
  143.  {
  144.   numcolors = lastcolor - firstcolor + 1;
  145.  
  146.   colorvalue = firstcolor << 8;
  147.   step = ((long)numcolors << 8) / (long)length;
  148.  
  149.   dest = abuf + y * 320 + x1;
  150.   /* Make a pointer to the first pixel */
  151.  
  152.   for (x = x1; x <= x2; x++)
  153.     {
  154.      *dest++ = colorvalue >> 8;
  155.      /* Draw the pixel and move to the next location in memory */
  156.  
  157.      colorvalue += step;
  158.     }
  159.  }
  160. }
  161.  
  162. The above code is demonstrated in gshade2.c.
  163.  
  164.  
  165. 7.0 - Optimization Number 2 (ASM)
  166. ---------------------------------
  167. The other bottleneck in the routine is the colorvalue being shifted
  168. right by 8 for every pixel.  By using the assembly language registers
  169. mentioned earlier, we can take the high byte of colorvalue without
  170. shifting.
  171.  
  172. The code below shows how inline assembly is used to speed up the
  173. routine:
  174.  
  175. void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
  176. {
  177. int length;
  178. int numcolors;
  179. int colorvalue;
  180. int step;
  181. int x;
  182. unsigned char far * dest;   /* Ptr to the screen */
  183.  
  184.  length = x2 - x1 + 1;
  185.  if (length > 0)
  186.  {
  187.   numcolors = lastcolor - firstcolor + 1;
  188.  
  189.   colorvalue = firstcolor << 8;
  190.   step = ((long)numcolors << 8) / (long)length;
  191.  
  192.   dest = abuf + y * 320 + x1;
  193.   /* Make a pointer to the first pixel */
  194.  
  195.   /* Begin assembly optimization */
  196.   if (length > 0)
  197.    {
  198.     asm {
  199.     mov cx, word ptr length        /* Set length */
  200.     les di, dest            /* Set destination ptr */
  201.     mov ax, word ptr colorvalue    /* Set color */
  202.        }
  203.     shadedlineloop:
  204.     ;
  205.     asm {
  206.     mov es:di, ah            /* Move color to screen */
  207.     add ax, word ptr step          /* Add to color */
  208.     inc di                /* Move to next pixel */
  209.     dec cx                /* Decrease length */
  210.     jnz shadedlineloop        /* Repeat for all pixels */
  211.     }
  212.    }
  213.  }
  214. }
  215.  
  216. The above code is demonstrated in gshade3.c.
  217.  
  218.  
  219.  
  220. 8.0 - Combining The Shaded Line and Polygon Routines
  221. ----------------------------------------------------
  222. The next question you may be asking is, "How do I know what colors to
  223. use at the endpoints when drawing a polygon?".  In order to do this, we
  224. have to modify our polygon scan conversion routines I developed in
  225. tutorial #1.
  226.  
  227. The point structure is defined as:
  228.  
  229. typedef struct
  230.     {
  231.      int x,y;
  232.     } point;
  233.  
  234. Since each vertex now has a color associated with it, we will add another
  235. variable to this structure, called col.  The point structure becomes the
  236. gpoint structure, which looks like this:
  237.  
  238. typedef struct
  239.     {
  240.      int x,y;
  241.      unsigned char col;
  242.     } gpoint;
  243.  
  244. When we converted the polygon into a list of x coordinates, we stored them
  245. into two arrays, startx and endx.  Now we also need to store the color
  246. at both of these coordinates.
  247.  
  248. Let's make two new arrays:
  249.  
  250. int startcol[200];
  251. int endcol[200];
  252.  
  253. When the list is created, we will have 2 x coordinates and a color value
  254. associated with each of them.  This is all the information we need to call
  255. the shadedline routine.
  256.  
  257. The polyline routine becomes the gpolyline routine, which also calculates
  258. the colors at the ends of each horizontal line.  To do this, we use fixed
  259. point math, similar to the way we calculated the colors along the length
  260. of the line.  This time we are adding the step value to the color
  261. for every pixel we move down, instead of across.
  262.  
  263.  
  264. void gpolyline (int x1, int y1, int col1, int x2, int y2, int col2)
  265. /* Calculates the coordinates of a line given two
  266.    vertices (x1,y1) with color col1, and (x2,y2) with color col2.
  267.  
  268.    We will use fixed point math to speed things up.
  269.    The x coordinate is multiplied by 256 and for each row,
  270.    a constant m is added to x.  This is a simplified version
  271.    of a line algorithm because we only have to store 1 x coordinate
  272.    for every y coordinate.
  273.  
  274.    The color value is increase by a step value based on the
  275.    number of colors between the vertices and the distance between the
  276.    y coordinates.
  277.  
  278. */
  279. {
  280.  int tmp,y;
  281.  long x,m;
  282.  long col, colstep; /* First color, and the step value */
  283.  
  284.  if (y2 != y1)      /* This isn't a horizontal line */
  285.  {
  286.    if (y2 < y1)     /* Make sure y2 is greater than y1 */
  287.    {
  288.     tmp = y1;       /* Swap the y coordinate */
  289.     y1 = y2;
  290.     y2 = tmp;
  291.  
  292.     tmp = x1;       /* Swap the corresponding x coordinates */
  293.     x1 = x2;
  294.     x2 = tmp;
  295.  
  296.     tmp = col1;     /* Swap the corresponding color values */
  297.     col1 = col2;
  298.     col2 = tmp;
  299.    }
  300.  
  301.  x = (long)x1<<8;   /* Multiply be 256 */
  302.  
  303.  m = ((long)(x2 - x1)<<8) / ((long)(y2 - y1));
  304.  /* m is the fractional amount to add to the x coordinate every row.
  305.     m is equal to (delta x) / (delta y).  In other words, the x coordinate
  306.     has to change by (x2 - x1) columns in (y2 - y1) rows. */
  307.  
  308.  col = (long)col1 << 8;     /* Initial color in 8.8 fixed point format */
  309.  colstep = ((long)(col2 - col1) << 8) / ((long)(y2 - y1));
  310.  /* Calculate the color step value similar to the method in the
  311.     shadedline routine, only we're dividing by the delta y value. */
  312.  
  313.  
  314.  x += m; /* We ALWAYS skip the first point in every line. This is done */
  315.  y1++; /* because we do not want to store the point where two lines
  316.       meet, twice.  This would result in a single point being drawn. */
  317.  
  318.  for (y = y1; y <= y2; y++) /* Go through each row */
  319.   {
  320.    if ((y >= 0) & (y < 200)) /* If the coordinate is on the screen */
  321.     if (startx[y] == -16000) /* Store the first coordinate */
  322.       {
  323.        startx[y] = x>>8;
  324.        startcol[y] = col >> 8;    /* store the color */
  325.       }
  326.     else
  327.       {
  328.        endx[y] = x>>8;        /* Store the last coordinate */
  329.        endcol[y] = col >> 8;
  330.       }
  331.    x += m;             /* Add our constant to x */
  332.    col += colstep;
  333.    }
  334.  }
  335. }
  336.  
  337.  
  338.  
  339. The fillpoly routine becomes the shadedpoly routine, which calls gpolyline
  340. with the correct coordinates and color of each vertex, and finally the
  341. shadedline routine.
  342.  
  343.  
  344. void shadedpoly (gpoint *vertexlist, int numvertex)
  345. /* Draws a shaded polygon given an array of vertices. */
  346. {
  347. int i;
  348. gpoint *curpt,*nextpt;
  349.   /* Two pointers to a vertex. These are used to connect to vertices
  350.      together in when calling the gpolyline routine. */
  351.  
  352.  curpt = vertexlist;      /* Set to the first vertex in the array */
  353.  nextpt = vertexlist + 1; /* and to the second vertex */
  354.  
  355.  for (i = 0; i < 200; i++)
  356.   {
  357.    startx[i] = -16000;     /* Set up our impossible values */
  358.    endx[i] = -16000;
  359.   }
  360.  
  361.  for (i = 1; i < numvertex; i++)
  362.   {
  363.    gpolyline (curpt->x,  curpt->y,  curpt->col,
  364.           nextpt->x, nextpt->y, nextpt->col);
  365.    /* Calculate the edge of this line. */
  366.  
  367.    curpt += 1;  /* Go to the next line */
  368.    nextpt += 1;
  369.   }
  370.  
  371.   nextpt = vertexlist;  /* Now close the polygon by doing a line between
  372.                the first and last vertex. */
  373.   gpolyline (curpt->x,  curpt->y,  curpt->col,
  374.          nextpt->x, nextpt->y, nextpt->col);
  375.  
  376.   for (i = 0; i < 200; i++)   /* Now draw the horizontal line list */
  377.     if (startx[i] != -16000)  /* Indicates there is a line on this row */
  378.     {
  379.      if (endx[i] == -16000)
  380.      endx[i] = startx[i]; /* In case there was only one
  381.                  point found on this row */
  382.        shadedline (startx[i], startcol[i], endx[i], endcol[i], i);
  383.        /* Draw a shaded line between the two x coordinates, on the row i. */
  384.     }
  385. }
  386.  
  387.  
  388. 9.0 - What About Clipping?
  389. --------------------------
  390. So far we assumed the x coordinates of the shaded line would fall between
  391. 0 and 319 inclusively.  What happens if one of the x coordinates does not?
  392. The line will wrap around to the other side of the screen.  You can
  393. try this with any of the first 4 example programs.  It will probably cause
  394. the system to crash since you are able to write to memory outside the
  395. video display memory.
  396.  
  397. We have already clipped the y coordinate in the shadedpoly routine, so we
  398. do not have to worry about that.
  399.  
  400. There are two possible cases that need clipping:
  401.  1. The left edge is less than 0
  402.  2. The right edge is greater than 319
  403.  
  404. The second case is easy to solve, since you can just decrease the length
  405. of the line.  In other words, chop off the pixels past 319.   Note that
  406. you should clip the line AFTER you calculate the step value since
  407. changing the length will change the step value as well.
  408.  
  409. The code for clipping the right side would look something like this:
  410.  if (x2 > 319)    /* Set right coordinate to right clipping coordinate */
  411.    x2 = 319;
  412.  
  413. No other math is required.
  414.  
  415.  
  416. The first case is a tricky one.  We cannot simply set x1 to 0, since the
  417. first color would be wrong.  We have to increase the colorvalue to skip
  418. over the pixels past the left edge.  We know that for each pixel the
  419. colorvalue is increased by the step value, so we can multiply the
  420. step value by the number of pixels past the left edge and add the
  421. result to the colorvalue.  This will advance the color to the correct
  422. value.
  423.  
  424. The code for clipping the right edge would look like this:
  425.  
  426.  if (x1 < 0)            /* Clip the left edge */
  427.   {
  428.    dist = 0 - x1;        /* Find number of pixels to be clipped */
  429.    colorvalue += dist * step;
  430.     /* Add dist color steps onto the starting value */
  431.    x1 = 0;
  432.     /* Set left coordinate to the left clippin coordinate*/
  433.   }
  434.  
  435.  
  436. After the clipping is performed, the length of the line should be
  437. recalculated.  The shadedline routine now looks like this:
  438.  
  439. void shadedline (int x1, int firstcolor, int x2, int lastcolor, int y)
  440. {
  441. int length;
  442. int numcolors;
  443. int colorvalue;
  444. int step;
  445. int x;
  446. unsigned char far * dest;   /* Ptr to the screen */
  447. int dist;
  448.  
  449.  length = x2 - x1 + 1;
  450.  if (length > 0)
  451.  {
  452.   numcolors = lastcolor - firstcolor + 1;
  453.  
  454.   colorvalue = firstcolor << 8;
  455.   step = ((long)numcolors << 8) / (long)length;
  456.  
  457.   if (x2 > 319)    /* Set right coordinate to right clipping coordinate */
  458.     x2 = 319;
  459.  
  460.   if (x1 < 0)            /* Clip the left edge */
  461.    {
  462.     dist = 0 - x1;        /* Find number of pixels to be clipped */
  463.     colorvalue += dist * step;
  464.      /* Add dist color steps onto the starting value */
  465.     x1 = 0;
  466.      /* Set left coordinate to the left clippin coordinate*/
  467.    }
  468.  
  469.   dest = abuf + y * 320 + x1;
  470.   /* Make a pointer to the first pixel */
  471.  
  472.   length = x2 - x1 + 1;
  473.  
  474.   /* Begin assembly optimization */
  475.   if (length > 0)
  476.    {
  477.     asm {
  478.     mov cx, word ptr length        /* Set length */
  479.     les di, dest            /* Set destination ptr */
  480.     mov ax, word ptr colorvalue    /* Set color */
  481.        }
  482.     shadedlineloop:
  483.     ;
  484.     asm {
  485.     mov es:di, ah            /* Move color to screen */
  486.     add ax, word ptr step          /* Add to color */
  487.     inc di                /* Move to next pixel */
  488.     dec cx                /* Decrease length */
  489.     jnz shadedlineloop        /* Repeat for all pixels */
  490.     }
  491.    }
  492.  }
  493. }
  494.  
  495.  
  496.  
  497. 10.0 - Other Issues
  498. -------------------
  499. The example programs included use the default palette.  This does not
  500. produce a very nicely shaded polygon.  You should define your palette with
  501. shades of colors. For example, colors 0 to 63 may contain shades of red,
  502. while colors 64 to 127 contain shades of blue.  The more shades of colors
  503. you use, the more realistic the shading will look, and less banding will
  504. occur.  Banding occurs when you see distinct edges along each color in the
  505. polygon.  This is caused by the colors being too different.
  506.  
  507. Gouraud shading also involves calculating the normal of the polygon and
  508. comparing it with the direction of the lightsource in order to find
  509. realistic values of colors at each vertex.  Since this deals with 3D
  510. graphics, it is out of the scope of this tutorial.  You don't always need
  511. to take this into account however.  You can base the color on the z value
  512. of the vertex, or leave this out completely if you are strictly dealing
  513. with 2D graphics.  As well, you may want to set the colors of the vertices
  514. once and leave them the same throughout the rest of the program.
  515.  
  516. I hope you enjoyed this tutorial.  The next topic is texture mapping, which
  517. is only a small change on the code presented here (believe it or not!).
  518.  
  519.  
  520.  
  521.  
  522.  
  523.