Fustrum 3D Clipping

3 D . F u s t r u m . C l i p p i n g

Clipping is a very important part of a 3d-rendering pipeline. It keeps your scanline drawing routines from trashing memory outside of the screen boundaries, and thus from crashing. It also helps you to speed up your engine because you simply neglect polygons that are not on the screen on which you would otherwise have wasted time.

Over time, people have developed a number of different approaches to clipping polygons. The first, most logical solution was to implement a conditional jump in the innermost loop of the drawing routines to check whether the pixel it is at is on the screen or not.

The second, a bit more abstract, but better, approach, was the Sutherland-Hodgman 2D algorithm, which involves inserting vertices at the points where the polygon intersects with the screen boundaries in two-dimensional space (top, bottom, left and right of your monitor), by clipping all vertices' screen-coordinates to each boundary, deleting vertices outside of screen space, and finally drawing the resulting vertices.

Another method is the one I'll be describing here. Personally I believe that this algorithm is the best one I know of, because it not only provides you with more information on the clipped polygons, it also implements a standard clipping on the z-axis, that is, polygons are also clipped as if they were coming out of your monitor.

Basically, fustrum clipping is an extension of the Sutherland-Hodgman algorithm. The only difference is that not each screen-coordinate is clipped against each boundary in turn, but that each 3D vertex is clipped against each plane of the fustrum in turn.

I hear you cry "What the hell is this fustrum thing?". Well, a fustrum is nothing more than the mathematical definition of the volume of space which the camera can see. You could describe it as a regular square-based pyramid with the top cut off. You place the camera instead of that top, looking down at the base of the pyramid, and take out the bottom square of the pyramid. That's your basic fustrum. The expelled bottom of the pyramid represents your screen, and the intersection plane from the cut represents the camera lens.
Of course your screen is not square, but that's a minor detail we'll deal with later on.

From a mathematical point of view, you would describe the viewing fustrum as 5 infinite planes (left, right, top, bottom, and near z plane, and if you want, a 6th far z plane for distance clipping). Let's set them up.

First we need to define a vector, but I take it for granted you have already done that. If you really haven't yet, you should go and read some basic tutorials first.

  struct Vector3D {

    float x,y,z;

  };

Now we need to know how to handle a plane. Since we look from the mathematical point of view, you ought to know about the plane equation: ax+by+cz=d.
So, to determine a plane all we need to do is put a,b,c and d in a structure (x,y and z are given by the vertex). Since (a,b,c) form the normal of the plane, we can use a Vector3D for that.

  struct Plane3D {

    Vector3D normal;

    float distance;

  };

Finally we can define the fustrum:

  struct Fustrum3D {

    Plane left, right, top, bottom, nearZ;

    Plane farZ; // this one isn't really necessary

};

Furthermore to set up the viewing fustrum, we'll need to know the value with which all vertices are scaled, the perspective projection distort. You'll probably do something like

  Vertex.ScreenX = Vertex.RotatedX * PerspectiveX / Vertex.RotatedZ;

  Vertex.ScreenY = Vertex.RotatedY * PerspectiveY / Vertex.RotatedZ;

somewhere in your systems. Now, just store the PerspectiveX and PerspectiveY globally, so the clipping module can access them. (PerspectiveX and PerspectiveY might be one variable with the same value for both)

Hmm. All we know are the screen width and height and the scaling values on X and Y axes. That's not much. But it can be done!
With a little sine/cosine stuff we can calculate the angle between left and right sides, and top and bottom sides of the fustrum:

  LeftRight_angle = atan2 ( XRes/2 , PerspectiveX );

  TopBottom_angle = atan2 ( YRes/2 , PerspectiveY );

Now we have these, we can calculate the normals of all the planes! (Except for the near and far Z planes, which always have the same normal)

  Fustrum.left.normal.x = cos ( LeftRight_angle );

  Fustrum.left.normal.y = 0;

  Fustrum.left.normal.z = sin ( LeftRight_angle );



  Fustrum.right.normal.x = - cos ( LeftRight_angle );

  Fustrum.right.normal.y = 0;

  Fustrum.right.normal.z = sin ( LeftRight_angle );



  Fustrum.top.normal.x = 0;

  Fustrum.top.normal.y = cos ( TopBottom_angle );

  Fustrum.top.normal.z = sin ( TopBottom_angle );



  Fustrum.bottom.normal.x = 0;

  Fustrum.bottom.normal.y = - cos ( TopBottom_angle );

  Fustrum.bottom.normal.z = sin ( TopBottom_angle );



  Fustrum.nearZ.normal.x = 0;

  Fustrum.nearZ.normal.y = 0;

  Fustrum.nearZ.normal.z = 1;



  Fustrum.farZ.normal.x = 0;

  Fustrum.farZ.normal.y = 0;

  Fustrum.farZ.normal.z = -1;

Yippee! We have all the normals. Now with a little logical thought, you can figure out that the distance of all the side planes are zero! (They all run through the camera!) The only thing left to define is the distance of the near and far Z planes, which I'll leave up to you. (I don't use a far Z plane, and I find 10 to be a good distance for the near Z plane).

"Hmm", you say, "So you have your fustrum. Good for you. What's the use of it?"
I'll tell you what it's use is: now we can start clipping, you dummy! :)
We do that by clipping the polygon to every plane in turn. We use the output from one plane-clipping pass as input for the next.
Then, we'll have to consider every line of our polygon seperately. So we start with the line from vertex 0 to vertex 1, then line 1-2, etc ... and the last line will be 3-0 if you're dealing with quads, 2-0 if triangles, etc.
We check for both points whether they are inside the fustrum or not. This is done by an easy dotproduct.

  Vector3D CurVertex;

  Vector3D PNormal = Fustrum.left.normal; // or right, or top, etc...

  float InsideCheck = PNormal.x*CurVertex.x + PNormal.y*CurVertex.y + PNormal.z*CurVertex.z - PlaneDistance;

Now, if (InsideCheck<0) the point is outside the polygon, and otherwise is in it.

With this we can make out three different cases for each line:
1. Both points are inside the fustrum
2. Both points are outside the fustrum
3. One point is inside, the other outside the fustrum.

Obviously, in case 1 we insert both points into the final polygon and in case 2 we insert none. Case 3 is a little trickier. We'll have to calculate the point of intersection, and insert that one along with the point inside the fustrum.

If you ever had a mathematics course, you know there is a simple formula for calculating the intersection of a line and a plane, so I won't go into that. Just use this, or go find some math book. Let's define the first point as A and the second as B;

  float scale = (DotProduct(A,Plane)-Plane.distance)/(DotProduct(A,Plane)-DotProduct(B,Plane)-2*Plane.distance); 

  Vector IntersectionPoint;

  IntersectionPoint.x = A.x + (B.x - A.x) * scale;

  IntersectionPoint.y = A.y + (B.y - A.y) * scale;

  IntersectionPoint.z = A.z + (B.z - A.z) * scale;

If you need to clip more values, like texture coordinates for example, you should do it like this:

  IntersectionPoint.value = A.value + (B.value - A.value) * scale;

That's it! You did it! The final polygon is now inside the screen space when you perspective project it (which you still have to do after this of course). Now you can eradicate all those tests in your scanline drawer!
You can of course take it further.

With 3D-fustrum clipping you have a number of other advantages:
- you get the clipped Z coordinate for free, which comes in very handy when you use perspectively corrected texture mapping. Also 3D hardware needs the Z coordinate, and doesn't do clipping of it's own.
- you save calculation time of the perspective projection of vertices which aren't visible.
- you can now have smaller and easier to maintain polygon drawers.
- you could even backtransform your camera into object space, and clip there. This would save you the entire transformation process for all the invisible vertices.
- if you use bounding boxes, you can quickly discard entire objects which are outside of the viewing fustrum (just a matter of checking the 8 vertices of the box to the fustrum).

Well, that's about it I suppose. I sure learned a lot from coding my 3d clipping routines, and I hope you do too. It is a great algorithm, which gains you some speed and flexibility.

If you have any comments or whatever, tell me about them on fatalv@hotmail.com.

Chris Heunen aka Fatal Vision