Sutherland-Hodgman Clipping

@DrWatson

Published in

atari

· 11 months ago

Fourth part of The 3D Coding Blackhole tutorial series

Overview
Z-Clipping
Clipping against the screen

Overview

Some chineese proverb says that drawing polygons elsewhere than on the screen is bad, so you're better clip your polygons. You must clip against the edges of the screen, but also against the front of the view volumes (you must not draw things behind the viewer, when the z coordinate is too small). When we clip a polygon, we don't check if every point is inside the limits, but we rather add necessary vertices. So we will need a third polygon structure:

typedef struct 
{ 
    int Count; 
   _3D Vertex[20]; 
}CPolygon_t;

And since we can have additional vertices to project, we can no longer project vertices, we will rather project clipped 3D polygons onto 2D polygons:

void M3D_Project(CPolygon_t *Polygon,Polygon2D_t *Clipped,int focaldistance) 
{ 
   int v; 
    for(v=0; v<Polygon->Count; v++) 
   { 
      if(!Polygon->Vertex[v].z)Polygon->Vertex[v].z++; 
         Clipped->Points[v].x=Polygon->Vertex[v].x*focaldistance/ 
            Polygon->Vertex[v].z+Origin.x; 
         Clipped->Points[v].y=Polygon->Vertex[v].y*focaldistance/ 
            Polygon->Vertex[v].z+Origin.y; 
   } 
   Clipped->PointsCount=Polygon->Count; 
}

Z-Clipping

We will start our Z-Clipping (or clipping against the front of the view volume) by defining macros to compute the z deltas between the first point and the second (dold) and between the first point and the minimum z value. Then we will compute the proportion, and make sure we don't get a divide by zero.

WORD ZMin=20; 
#define INIT_ZDELTAS dold=V2.z-V1.z;  dnew=ZMin-V1.z; 
#define INIT_ZCLIP INIT_ZDELTAS if(dold)m=dnew/dold;

Then we will create a function that will take as parameter a clipped polygon pointer (where it will write the resulting clipped vertices), a first vertex (the beginning of the edge we're clipping) and a second one (the end):

void CLIP_Front(CPolygon_t *Polygon,_3D V1,_3D V2) 
{ 
   float dold,dnew, m=1; 
   INIT_ZCLIP

Now we must check if the edge is either totally inside the viewport, leaving it or entering it. If the edge isn't totally inside, we compute the intersection of the edge and the viewport, with our m value, computed with INIT_ZCLIP.

If it's inside:

   if ( (V1.z>=ZMin) && (V2.z>=ZMin) ) 
      Polygon->Vertex[Polygon->Count++]=V2;

If it's leaving the viewport:

   if ( (V1.z>=ZMin) && (V2.z<ZMin) ) 
   { 
      Polygon->Vertex[Polygon->Count   ].x=V1.x + (V2.x-V1.x)*m; 
      Polygon->Vertex[Polygon->Count   ].y=V1.y + (V2.y-V1.y)*m; 
      Polygon->Vertex[Polygon->Count++ ].z=ZMin; 
   }

If it's entering the viewport:

   if ( (V1.z<ZMin) && (V2.z>=ZMin) ) 
   { 
      Polygon->Vertex[Polygon->Count   ].x=V1.x + (V2.x-V1.x)*m; 
      Polygon->Vertex[Polygon->Count   ].y=V1.y + (V2.y-V1.y)*m; 
      Polygon->Vertex[Polygon->Count++ ].z=ZMin; 
      Polygon->Vertex[Polygon->Count++ ]=V2; 
   }

And that's it with this edge Z-Clipping function:

Now we must write an entire polygon Z-Clipping procedure. And for the occasion, we will define a macro searching for the appropriate polygon vertex in an object structure:

#define Vert(x) Object->Vertex[Polygon->Vertex[x]]

And here is the function:

void CLIP_Z(Polygon_t *Polygon,Object_t *Object,CPolygon_t *ZClipped) 
{ 
   int d,v; 
   ZClipped->Count=0; 
   for (v=0; v<Polygon->Count; v++) 
   { 
      d=v+1; 
      if(d==Polygon->Count)d=0; 
      CLIP_Front(ZClipped, Vert(v).Aligned,Vert(d).Aligned); 
   } 
}

This one is pretty straightforward: it simply calls FrontClip, doing a vertex wrap-around.

Clipping against the screen

Clipping against the edges of the screen is the same as Z-Clipping, but you have 4 edges instead of one, so we will need 4 different functions. But they will all use the same delta initialization:

#define INIT_DELTAS dx=V2.x-V1.x;  dy=V2.y-V1.y; 
#define INIT_CLIP INIT_DELTAS if(dx)m=dy/dx;

And the edges will be:

_2D TopLeft, DownRight;

And to simplify further use of the types _2D and _3D, we'll define two useful functions:

_2D P2D(short xshort y) 
{ 
   _2D Temp; 
   Temp.x=x; 
   Temp.y=y; 
   return Temp; 
} 
_3D P3D(float x,float y,float z) 
{ 
   _3D Temp; 
   Temp.x=x; 
   Temp.y=y; 
   Temp.z=z; 
   return Temp; 
}

then use them to specify the viewport:

TopLeft=P2D(0, 0); 
DownRight=P2D(319, 199);

And here comes the 4 edge clipping functions:

void CLIP_Left(Polygon2D_t *Polygon,_2D V1,_2D V2) 
{ 
   float   dx,dy, m=1; 
   INIT_CLIP 

   // ************OK************ 
   if ( (V1.x>=TopLeft.x) && (V2.x>=TopLeft.x) ) 
   Polygon->Points[Polygon->PointsCount++]=V2; 
   // *********LEAVING********** 
   if ( (V1.x>=TopLeft.x) && (V2.x<TopLeft.x) ) 
   { 
      Polygon->Points[Polygon->PointsCount].x=TopLeft.x; 
      Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(TopLeft.x-V1.x); 
   } 
   // ********ENTERING********* 
   if ( (V1.x<TopLeft.x) && (V2.x>=TopLeft.x) ) 
   { 
      Polygon->Points[Polygon->PointsCount].x=TopLeft.x; 
      Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(TopLeft.x-V1.x); 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   } 
} 
void CLIP_Right(Polygon2D_t *Polygon,_2D V1,_2D V2) 
{ 
   float dx,dy, m=1; 
   INIT_CLIP 
   // ************OK************ 
   if ( (V1.x<=DownRight.x) && (V2.x<=DownRight.x) ) 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   // *********LEAVING********** 
   if ( (V1.x<=DownRight.x) && (V2.x>DownRight.x) ) 
   { 
      Polygon->Points[Polygon->PointsCount].x=DownRight.x; 
      Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(DownRight.x-V1.x); 
   } 
   // ********ENTERING********* 
   if ( (V1.x>DownRight.x) && (V2.x<=DownRight.x) ) 
   { 
      Polygon->Points[Polygon->PointsCount].x=DownRight.x; 
      Polygon->Points[Polygon->PointsCount++].y=V1.y+m*(DownRight.x-V1.x); 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   } 
} 
/* 
================= 
CLIP_Top 
================= 
*/ 
void CLIP_Top(Polygon2D_t *Polygon,_2D V1,_2D V2) 
{ 
   float   dx,dy, m=1; 
   INIT_CLIP 
   // ************OK************ 
   if ( (V1.y>=TopLeft.y) && (V2.y>=TopLeft.y) ) 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   // *********LEAVING********** 
   if ( (V1.y>=TopLeft.y) && (V2.y<TopLeft.y) ) 
   { 
      if(dx) 
         Polygon->Points[Polygon->PointsCount].x=V1.x+(TopLeft.y-V1.y)/m; 
      else 
         Polygon->Points[Polygon->PointsCount].x=V1.x; 
      Polygon->Points[Polygon->PointsCount++].y=TopLeft.y; 
   } 
   // ********ENTERING********* 
   if ( (V1.y<TopLeft.y) && (V2.y>=TopLeft.y) ) 
   { 
      if(dx) 
         Polygon->Points[Polygon->PointsCount].x=V1.x+(TopLeft.y-V1.y)/m; 
      else 
         Polygon->Points[Polygon->PointsCount].x=V1.x; 
      Polygon->Points[Polygon->PointsCount++].y=TopLeft.y; 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   } 
} 
void CLIP_Bottom(Polygon2D_t *Polygon,_2D V1,_2D V2) 
{ 
   float dx,dy, m=1; 
   INIT_CLIP 
   // ************OK************ 
   if ( (V1.y<=DownRight.y) && (V2.y<=DownRight.y) ) 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   // *********LEAVING********** 
   if ( (V1.y<=DownRight.y) && (V2.y>DownRight.y) ) 
   { 
      if(dx) 
         Polygon->Points[Polygon->PointsCount].x=V1.x+(DownRight.y-V1.y)/m; 
      else 
         Polygon->Points[Polygon->PointsCount].x=V1.x; 
      Polygon->Points[Polygon->PointsCount++].y=DownRight.y; 
   } 
   // ********ENTERING********* 
   if ( (V1.y>DownRight.y) && (V2.y<=DownRight.y) ) 
   { 
      if(dx) 
         Polygon->Points[Polygon->PointsCount].x=V1.x+(DownRight.y-V1.y)/m; 
      else 
         Polygon->Points[Polygon->PointsCount].x=V1.x; 
      Polygon->Points[Polygon->PointsCount++].y=DownRight.y; 
      Polygon->Points[Polygon->PointsCount++]=V2; 
   } 
}

And now we must do the entire polygon clipping function, but for that we will need an additional global variable:

polygon2D_t TmpPoly; 

void CLIP_Polygon(Polygon2D_t *Polygon,Polygon2D_t *Clipped) 
{ 
   int v,d; 

   Clipped->PointsCount=0; 
   TmpPoly.PointsCount=0; 

   for (v=0; v<Polygon->PointsCount; v++) 
   { 
      d=v+1; 
      if(d==Polygon->PointsCount)d=0; 
      CLIP_Left(&TmpPoly, Polygon->Points[v],Polygon->Points[d]); 
   } 
   for (v=0; v<TmpPoly.PointsCount; v++) 
   { 
      d=v+1; 
      if(d==TmpPoly.PointsCount)d=0; 
      CLIP_Right(Clipped, TmpPoly.Points[v],TmpPoly.Points[d]); 
   } 
   TmpPoly.PointsCount=0; 
   for (v=0; v<Clipped->PointsCount; v++) 
   { 
      d=v+1; 
      if(d==Clipped->PointsCount)d=0; 
      CLIP_Top(&TmpPoly, Clipped->Points[v],Clipped->Points[d]); 
   } 
   Clipped->PointsCount=0; 
   for (v=0; v<TmpPoly.PointsCount; v++) 
   { 
      d=v+1; 
      if(d==TmpPoly.PointsCount)d=0; 
      CLIP_Bottom(Clipped, TmpPoly.Points[v],TmpPoly.Points[d]); 
   } 
}