Real-time 3D Clipping (Sutherland-Hodgeman)
by (13 January 1999)


Return to The Archives
Introduction


For those who are interested, here's a brief explanation of the 3D plane clipping used in Focus. The plane clipper is used for the lighting model (world polygons are clipped against light 'beams') and for 'frustum clipping' (making sure that anything outside the screen is not drawn). Frustum clipping is used only for the left side of the screen in Focus. In case you wondered why I did that: Focus renders its polygons using an s-buffer. That means that every polygon is split in horizontal spans, these spans are stored in a structure, and when all the spans are processed, the structure is drawn on the screen. Each span that is partially outside the screen boundaries needs clipping. On the right side of the screen this can be achieved by simply making the span shorter, this does not affect starting values for U and V, nor delta values for U and V. The left side of the screen on the other hand requires recalculation of the start values. If this happens for all 50 spans of a polygon, a lot of time is lost. In that case, plane clipping is faster. Since simply testing whether a polygon needs to be clipped against a plane is already expensive, I use this kind of clipping ony for a quarter of the cases, and that is the most expensive one using other clipping methods, the left side of the screen.

Lets cut-and-paste the clipping code, and then discuss it block- by-block:


 fPolygon* fPolygon::clip (fPlane* p, bool rotated)
 {	// Early out: All points on one side of plane 
	 double dist[25];
	 bool allin=true, allout=true;
	 for (int i=0; i<vertices(); i++)
	 {	 fCoord* c=vertex(i)->coord();
		 if (rotated) dist[i]=p->A()*c->rx()+p->B()*c->ry()+p->C()*c->rz()-p->D();
				 else dist[i]=p->A()*c->x()+p->B()*c->y()+p->C()*c->z()-p->D();
		 if (dist[i]<-EPSILON) allin=false;
		 if (dist[i]>=EPSILON) allout=false;
	 }	
	 if (allin) return this; else if (allout) return 0;
	 // Clip a polygon against a plane
	 fVertex *cv[10], *v1=vertex(0);
	 double dist2, dist1=dist[0];
	 bool clipped=false, inside=(dist1>=0);
	 int curv=0;
	 for (i=1; i<=vertices(); i++)
	 {	 fVertex* v2=vertex(i % vertices());
		 dist2=dist[i % vertices()];
		 // Sutherland-hodgeman clipping
		 if (inside && (dist2>=0.0f)) cv[curv++]=v2;	// Both in
		 else if ((!inside) && (dist2>=EPSILON))		// Coming in
		 {	 clipped=inside=true;
			 fVertex* t=tempv[tempverts++]=newVert ();
			 double d=dist1/(dist1-dist2);
			 if (rotated)
			 {	 t->rx((float)(v1->rx()+(v2->rx()-v1->rx())*d));
				 t->ry((float)(v1->ry()+(v2->ry()-v1->ry())*d));
				 t->rz((float)(v1->rz()+(v2->rz()-v1->rz())*d));
				 t->coord ()->processed (1);
			 } else
			 {	 t->x((float)(v1->x()+(v2->x()-v1->x())*d));
				 t->y((float)(v1->y()+(v2->y()-v1->y())*d));
				 t->z((float)(v1->z()+(v2->z()-v1->z())*d));
				 t->coord ()->processed (0);
			 }
			 t->u((float)(v1->u()+(v2->u()-v1->u())*d));
			 t->v((float)(v1->v()+(v2->v()-v1->v())*d));
			 cv[curv++]=t;
			 cv[curv++]=v2;
		 } else if (inside && (dist2<-EPSILON))		// Going out
		 {	 clipped=true;
			 inside=false;
			 fVertex* t=tempv[tempverts++]=newVert ();
			 double d=dist1/(dist1-dist2);
			 if (rotated)
			 {	 t->rx((float)(v1->rx()+(v2->rx()-v1->rx())*d));
				 t->ry((float)(v1->ry()+(v2->ry()-v1->ry())*d));
				 t->rz((float)(v1->rz()+(v2->rz()-v1->rz())*d));
				 t->coord ()->processed (1);
			 } else
			 {	 t->x((float)(v1->x()+(v2->x()-v1->x())*d));
				 t->y((float)(v1->y()+(v2->y()-v1->y())*d));
				 t->z((float)(v1->z()+(v2->z()-v1->z())*d));
				 t->coord ()->processed (0);
			 }
			 t->u((float)(v1->u()+(v2->u()-v1->u())*d));
			 t->v((float)(v1->v()+(v2->v()-v1->v())*d));
			 cv[curv++]=t;
		 } clipped=true;		// Both out
		 v1=v2;
		 dist1=dist2;
	 }
	 if (!clipped) return this;
	 // Construct clipped polygon
	 if (curv<3) return 0;
	 fPolygon* poly=newPoly (curv);
	 poly->type (m_type|TEMP);
	 poly->m_plane=m_plane;
	 poly->texture (m_text);
	 for (i=0; i<curv; i++) 
	 {	 poly->vertex(i, cv[i]);
		 if (rotated) cv[i]->coord()->perspective();
	 }
	 return poly;
 }


Early Out Mechanism


Have a look at this code:


 // Early out: All points on one side of plane

 double dist[25];
 bool allin=true, allout=true;
 for (int i=0; i<vertices(); i++)
 {	 fCoord* c=vertex(i)->coord();
	 if (rotated) dist[i]=p->A()*c->rx()+p->B()*c->ry()+p->C()*c->rz()-p->D();
			 else dist[i]=p->A()*c->x()+p->B()*c->y()+p->C()*c->z()-p->D();
	 if (dist[i]<-EPSILON) allin=false;
	 if (dist[i]>=EPSILON) allout=false;
 }	
 if (allin) return this; else if (allout) return 0;


This code quickly determines if a polygon is completely 'out' or 'in'. As you can see, determining this for a single vertex requires three multiplications. That's quite expensive still, so the results of the calculations are stored for later usage.

The 'rotated' flag is used to be able to clip both rotated and original polygons. The idea is the same, so I will ignore it in the rest of this document. At the end of this piece of code, the distance of every vertex to the plane is known, and it is also known wheter the polygon is completely 'in' or 'out'. If it's 'in', a pointer to the original polygon is returned, if it's 'out', a NULL pointer is returned. One last note: With this clipping function you cannot clip polygons that consist of more than 25 vertices since there is only room for 25 vertex-to-plane distances in the 'dist' array. 25 should be enough, I guess.

Next piece of code:


 // Clip a polygon against a plane

 fVertex *cv[10], *v1=vertex(0);
 double dist2, dist1=dist[0];
 bool clipped=false, inside=(dist1>=0);
 int curv=0;
 for (i=1; i<=vertices(); i++)


The array 'cv' is going to contain the vertices of the clipped polygon (so 'cv' stands for: 'clipped vertex'). The 'v1' pointer points to the first vertex of each edge. Likewise, 'dist2' points to the distance of the vertex at the end of the edge, and so on. The flag 'clipped' is used at the end of the routine to detect polygons that where completely 'in', but missed by the early-out code (shit happens). The 'inside' flag is a small enhancement to the Sutherland-Hodgeman clipping.


Sutherland-Hodgeman Clipping


The algorithm to perform sutherland-hodgeman clipping is very simple and easy to implement. Grab a piece of paper, and draw a convex polygon on it. Then draw a rectangular 'screen' area, so that parts of the polygon are outside this area. Number the vertices of your polygon, 0...n. Now start with the first edge. The startpoint of this edge is called 'v1', the endpoint of the edge is 'v2'. Make a table, called 'cv'.

Now use the following algorithm:

1. If v1 is 'in' and v2 is 'out', the edge is apparently 'going out'. Determine the point where the edge leaves the 'screen'. Call this point 'clipped coord'. Note this in your 'cv' table.

2. If v1 is 'out' and v2 is 'in', the edge is apparently 'coming in'. Determine the point of entrance. Write this point in your 'cv' table. Also write 'v2' in your 'cv' table. Lines that are entering the area always cause two entries in the 'cv' table.

3. If both v1 and v2 are 'in', write only v2 to your 'cv' table.

4. If neither v1 nor v2 are 'in', don't do anything.

Note that if each of these cases would have occured, exactly four vertices where written in 'cv'.

When you have done this for your first edge, rename 'v2' to 'v1', 'dist2' to 'dist1' and so on, and get 'v2', 'dist2' for the second edge. Then choose one of the four steps mentioned above again. When all four edges are processed, your 'cv' table contains the clipped polygon.


The Actual Clipping


Here's how you determine exactly where the clipped coord is. First, calculate where the point is relative to the two distances of the vertices of the plane:

double d = dist1 / (dist1 - dist2);

This is always a number between 0 and 1. Then, create a new vertex and store the adjusted coordinates in it:


t->x((float)(v1->x()+(v2->x()-v1->x())*d));
t->y((float)(v1->y()+(v2->y()-v1->y())*d));
t->z((float)(v1->z()+(v2->z()-v1->z())*d));


If this formulas give you bad results, you probably have your planes pointing in the wrong direction.

In the code from Focus I also clip the U and V coordinates for textures, this is done in exactly the same way.

Note that I use an 'EPSILON' value: This is handy for polygons that are just a tiny bit on the other side of the plane. In these cases, it's a shame to construct a really tiny polygon for that. Because normal Sutherland-Hodgeman doesn't know where the last vertex was, I added the 'inside' flag. Now it is possible to consider a coordinate 'out' if it was 'out' for the last edge, and only a very little 'in' for the current edge.


Closing


Here are the last lines from my clipping code:


 if (!clipped) return this;

 // Construct clipped polygon

 if (curv<3) return 0;
 fPolygon* poly=newPoly (curv);
 poly->type (m_type|TEMP);
 poly->m_plane=m_plane;
 poly->texture (m_text);
 for (i=0; i<curv; i++) 
 {	 poly->vertex(i, cv[i]);
	 if (rotated) cv[i]->coord()->perspective();
 }
 return poly;


The first line takes care of polygons that weren't clipped after all. In that case, the complete polygon is returned. Note that the 'cv' table does contain all the information needed to construct this polygon, but that is ignored.

The third line checks for invalid polygons. It is possible that a polygon contains zero vertices (if the early-out code failed), but it should be impossible that 'cv' contains only one or two vertices. I checked for it anyway, just to be sure.

In my code, a new polygon is now constructed, it is marked as 'temporary' so that it can be thrown away after being drawn, it is texturized with the texture of the original polygon (I am sooo lousy at copy constructors:) and finally the correct vertices are copied to the polygon.

That's it - I hope it is clear how this stuff works. Don't copy this stuff - I mean, I don't care, but it's important to be able to do this yourself if you want to do more complex 3D stuff.

Greets
Jacco Bikker - a.k.a. "THE PHANTOM"
 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.