• 07/16/99 05:58 PM
    Sign in to follow this  
    Followers 0

    Gouraud Shaded Polygons

    Graphics and GPU Programming

    Myopic Rhino
                          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 for
    
    3.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 = -16000;     /* Set up our impossible values */
       endx = -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 != -16000)  /* Indicates there is a line on this row */
        {
         if (endx == -16000)
             endx = startx; /* In case there was only one
                                     point found on this row */
           shadedline (startx, startcol, endx, endcol, 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:
     1. The left edge is less than 0
     2. 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!).
    
    
    
    
    
    
    
    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    There are no reviews to display.