A Cheater's Form of Z Clipping By Ian Romanick, idr@cs.pdx.edu In the 3D graphics realm, it is neccessary to perform clipping to the Z plane. This operation is computationally expensive, not only because it typically involes a number of multiplies and divides and must be performed on a polygon to polygon basis, but also because it can degenerated triangles in to quadrilaterals. In systems that are based solely around triangles, the degeneration into quadrilaterals can cause an incredible increase in complexity and computation time. A very simple solution to this problem exists, that is perfectly acceptable in many cases. This paper will present concepts applicable to any Z clipping algorithm, a typical Z clipping algorithm, and a cheater's method for Z clipping. ---------------------------------------------------------------------------- Trivial Rejection The most important case in Z clipping is the trivial reject. A number of methods exist to perform a trivial rejection, but the method that I prefer can also be used to solve other 3D graphics problems. This method is based around the knowledge of the minimal bounding sphere for each object in the environment. Once an object has been transformed into view space, this sphere should be tested agains the view plane. If the sphere is totally in front of the view plane, no clipping need be performed and the object should be rendered. If the sphere is totally behind the view plane, the object is totally invisible and should be skipped. If the sphere intersects the view plane, there is a good chance that clipping will need to be performed on any given polygon in the object. Once it is established that some portion of the object needs to be clipped, a second trivial rejection pass needs to be made. This second step is functionally much like the first, with the exception that it works on at a polygon level. If all of the points of a given triangle are on the same side of the view plane, a trivial accept/reject decision can be made. If fixed point integers and two's complement math are used, this can be done using just a few logic operations. ---------------------------------------------------------------------------- Nontrivial Cases This is the point at which the task of Z clipping becomes complex. There are typically two stages to this phase. The first stage clips each individual line to Z = 0. The out codes of each clip must also be stored. There are three possible out codes for a given line, as shown in the folloing table. Out code Condition -1 Both points are in 0 Both points are in 1 One point is in With this information, the second stage may begin. This stage involes building the real triangle data from the clipped points. A level of complexity is added to this stage due to the fact that the clipped polygon might be a quadrilateral. Determining weather a quadrilateral resulted is actually quite simple. The following table shows how the line out codes relate to the shape of the polygon. Sum of triples Cases Notes -3 (0,0,0) All three are in. -2 - Error. -1 - Error. 0 (2,2,2) All three are out. 1 (1,1,0), (1,0,1), (0,1,1) Two clips, one in. 2 (1,1,2), (1,2,1), (2,1,1) Two clips, one out. 3 - Error. Technically the cases for -3 and 0 should also be errors, since they should have been filtered out by the trivial rejection tests. The case for 1 results in a quadrilateral, and the case for 2 results in a triangle. By examining the clip cases with a bit more scrutiny, an exact picture of the resultant polygons is painted. If the out code sum is 1, there are three cases to look at, and the following diagrams show all three cases. The deciding factor between each of these cases is the line that is totally in. 1 /\ / \ /\ 1 /\ 1 /XX/ \XX\ / \ /XX/ \ / \XX\ __/____\__ /XX/ \ / \XX\ /XXXXXX\ 3 --/----- 2 3 -----\-- 2 3 -------- 2 / \ Case (1,1,0) Case (0,1,1) Case (1,0,1) A similar approach is taken if the out code sum is 2. As in the last case, there are only three possible polygon orientations. In this case, however, the deciding factor is the line that is totally out. 1 /\ / \ /\ 1 /\ 1 / / \ \ /XX\ / /X\ /X\ \ __/XXXX\__ / /XXX\ /XXX\ \ / \ 3 --/----- 2 3 -----\-- 2 3 -------- 2 / \ Case (1,1,2) Case (2,1,1) Case (1,2,1) One additional factor that has gone as yet unmentioned, is how texture mapping and shading are handled. These values must also be clipped, just as the X and Y values are. This can result in a routine that effectivly must clip in seven dimensions for a texture mapped and Gouraud shaeded display. There are methods to reduce the computational compexity during the clip operation, but the result is added computation later in the rendering pipe line. ---------------------------------------------------------------------------- Cheaters Can Win It should be obvious at this point that Z clipping is not a shallow subject. The level of complexity and the amount computation time involved are extreemly high, in some cases even higher than actually rendering the objects! There is an obvious need for something better. The largest stumbling block surrounding Z clipping is the fact that it must be performed before perspective projection. Since perspective projection must be performed before scan conversion, a modified Z-buffer algorithm can't be used. A very simple method, that is perfectly acceptable in many cases does exist. The need for non-trivial clipping can be prevented by simply bounding the Z value to zero after the trivial rejection tests are completed. On some CPUs this operation can be performed with one instruction, which should execute significanly faster than the algorithm detailed above. This method is obviously far from perfect. When an object penetrates the view plane at a point that is on the screen, the object will appear to squish. However, in situations where 3D collsion algorithms are in use, this case will not occur. If an object penetrates the view plane at a point that is off the screen, the offending polygons will usually be removed by the 2D clipping routine. In any case, mutations that occur will be minor in most situations. These factors make this method a good choice for 3D games. ---------------------------------------------------------------------------- Bibliography Computer Graphics: Principles and Practice (2nd Ed.), J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley 1990, ISBN 0-201-12110-7 Computer Graphics Handbook: Geometry and Mathematics, Michael E. Mortenson, Industrial Press, Inc., 1990, ISBN 0-8311-1002-3 ---------------------------------------------------------------------------- Return to the Epsilon Graphics Page.