Real-time 3D Clipping (Sutherland-Hodgeman)
by (13 January 1999)
|Return to The Archives|
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:
Early Out Mechanism
Have a look at this code:|
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:
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.
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:
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.
Here are the last lines from my clipping code:|
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.
Jacco Bikker - a.k.a. "THE PHANTOM"