Clipping the Star Streak Polygon Against A HI Pixel

Anti-aliasing is a technique that is used to soften a computer generated image to make it look more like a picture. Non anti-aliased static images often result in lines and edges having a stair step quality to them and non-aliased moving images result in lines and edges having a "crawling" characteristic to them as the move around the screen.

Input to the anti-aliasing algorithm consists of the HI (X,Y) pixel coordinate and the star streak polygon that is to be clipped against the pixel. The first thing that I will do before anti-aliasing begins is to translate the star streak polygon to the origin. The amount we translate the polygon in the X and Y directions is the negative amount of the row and column numbers of the pixel the polygon is being clipped to. Doing this results in our clip window being bounded by the two diagonal points (0,0) and (1,0).

The method I used to do the polygon clipping is based on the Sutherland-Hodgman basic clip and the C code for implementing the polygon clipping is presented below. I am including this source code since all of it was given to me in a very nice computer graphics book that I own so there is no reason not to also give it to you. For those of you who are interested, I can photocopy and snail mail the algorithmic description of the below code, as it's description is to extensive for me to put on this website.

/*structure to hold all information related to a hyperspace star*/

/*Structure to hold one of the star streak polygon's vertices*/

typedef struct {
    double x, y;
   } Vertex;

typedef struct {
    float starting_point_x;
    float starting_point_y;
    float ending_point_x;
    float ending_point_y;
    double endpoint_distance;
    Vertex vertex[4]; /*verts for poly defined counter-clockwise*/
    int size;
    int x_low, x_high;   /*x extent of current range*/
    int y_low, y_high;   /*y extent of current range*/
    int number_white_pixels;
    int quadrant;
   } Star_points;

/*variables used in support of polygon clipping*/

typedef struct
    {
    int    vertex_used[10];
    Vertex vertex_out[10];
    } Polygon_clip;

Polygon_clip poly_clip;
Vertex last_left, last_right, last_bottom, last_top;
int number_out_vertices;

void vertex_store(double x, double y)
   {
   poly_clip.vertex_out[number_out_vertices].x = x;
   poly_clip.vertex_out[number_out_vertices].y = y;
   poly_clip.vertex_used[number_out_vertices]  = 0;

   number_out_vertices++;
   }

void clip_top(double x, double y)
   {
   if (((y <= 1.0) && (1.0 < last_top.y)) ||
       ((last_top.y < 1.0) && (1.0 <= y)))
      vertex_store((x-last_top.x)*(1.0-y)/(y-last_top.y)+x, 1.0);

   last_top.x = x;
   last_top.y = y;

   if (y < 1.0) vertex_store(x,y);
   }

void clip_bottom(double x, double y)
   {
   if (((last_bottom.y < 0.0) && (0.0 <= y)) ||
       ((y <= 0.0) && (0.0 < last_bottom.y)))
      clip_top((x-last_bottom.x)*(0.0-y)/(y-last_bottom.y)+x, 0.0);

   last_bottom.x = x;
   last_bottom.y = y;

   if (0.0 < y) clip_top(x,y);
   }

void clip_right(double x, double y)
   {
   if (((x <= 1.0) && (1.0 < last_right.x)) ||
       ((last_right.x < 1.0) && (1.0 <= x)))
   clip_bottom(1.0, (y-last_right.y)*(1.0-x)/(x-last_right.x)+y);

   last_right.x = x;
   last_right.y = y;

   if (x < 1.0) clip_bottom(x,y);
   }

void clip_left(double x, double y)
   {
   if (((last_left.x < 0.0) && (0.0 <= x)) ||
       ((x <= 0.0) && (0.0 < last_left.x)))
   clip_right(0.0, (y-last_left.y)*(0.0-x)/(x-last_left.x)+y);

   last_left.x = x;
   last_left.y = y;

   if (0.0 < x) clip_right(x,y);
   }


/**************************************************************************
   anti_alias_polygon()
**************************************************************************/

void anti_alias_polygon(int curr_star, int row, int col)
   {
   int i, j;

   /*set the last points for the clipping algorithm.*/

   last_left.x = stars[curr_star].vertex[3].x - col;
   last_left.y = stars[curr_star].vertex[3].y - row;
   last_right.x = 0.0;
   last_right.y = 0.0;
   last_bottom.x = 0.0;
   last_bottom.y = 0.0;
   last_top.x = 0.0;
   last_top.y = 0.0;

   /*lets go through the clipping routines twice, the first time 
     is a fake clip used to set the last_xxxx points 
     variables correctly. The second run is used to actually 
     clip the star streak polygon against the clip window, which
     is denoted by the two coords (0,0) and (1,1).*/

   for (i=0; i <= 1; i++)
      {
      number_out_vertices = 0;

      for (j=0; j <= 3; j++)
         {
         clip_left(stars[curr_star].vertex[j].x - col, 
         stars[curr_star].vertex[j].y - row);
         }
      }

   /*now that we have the star streak polygon clipped against
     the unit window we need to decompose that resulting polygon
     into triangles so that we can find the polygon's area.*/

   if (number_out_vertices >= 3)
      determine_clipped_polygon_area(row, col);
   }

Last Updated: April 25, 2000
HTML URL: http://geocities.datacellar.net/~special_effect/hyperspace_cp.html
E-Mail: special_effect@geocities.com or click here
1