The clipping procedure can be inserted in many placed in the pipeline. We'll speak of it being placed before the projection transform. That is, we have points in view coordinates, and we want to clip away all of those that don't fall within the view volume.
Since we're doing this before the projection transform, note that we can assume that all our points have a homogeneous coordinate of 1.
The view volume will have six planes. To identify whether a line lies on a plane, we have only to make sure that it lies on the ``inside'' of each plane. (As you can see, I'm actually talking about a half-space rather than a plane, but I'll continue mixing the terms, since the boundary of the half-space (which is a plane) is the essential feature in question.)
We need some algebraic way of testing whether a point lies ``inside'' a plane. Each plane has some values A, B, C, and D such that
To talk about which side a point lies on, we'll talk about the sign of H * P.
If H * P > 0, then we say P is ``inside'' the plane defined by H.Note that we can negate H, and it will still define the same plane. But we will have reversed the ``inside'' of the plane to the other side.
We have only to find H for the planes that surround the frustum view volume.
Given a point P in homogenous coordinates, we clip it out if H * P < 0 for any of these H's.
near plane Hnear = (0, 0, -1, near) far plane Hfar = (0, 0, 1, far) left plane Hleft = (left, near, 0, 0) right plane Hright = (-right, -near, 0, 0) top plane Htop = (0, -near, top, 0) bottom plane Hbottom = (0, near, bottom, 0)
Suppose our line segment is defined by the points P and Q. To clip the segment to the view volume, we can clip it to the inside of each plane in succession. To clip the segment to a plane, we compute H * P and H * Q.
We only need a way to shift an endpoint outside a plane along the line segment until it reaches the plane. The points along the segment can be written in parametric form as follows, for t varying from 0 to 1:
If H * P >= 0, H * Q >= 0: Do nothing. If H * P < 0, H * Q < 0: Clip entire line. If H * P < 0, H * Q >= 0: Shift P to plane. If H * P >= 0, H * Q < 0: Shift Q to plane.
The above procedure is somewhat wasteful, as it can mean clipping segments to be inside one plane, even if the segment will later be clipped away completely. A slightly more efficient technique is to compute a bitmap for each endpoint.
Once we have the two endpoints' codes codeP and codeQ, we check their bitwise AND and bitwise OR.
bit 0: Hnear * P < 0 bit 1: Hfar * P < 0 bit 2: Hleft * P < 0 bit 3: Hright * P < 0 bit 4: Htop * P < 0 bit 5: Hbottom * P < 0
If codeP & codeQ != 0: Reject line altogether. If codeP | codeQ == 0: Accept line as is. Otherwise: Shift P or Q according to one of their 1-bits;
recompute the code for that endpoint;
and repeat this test.
The advantage of the above bitmaps is that we can apply the same technique to polygons. In particular, we can computer codei for each vertex Pi of the polygon. Then we can take the bitwise AND of all the polygons; if it turns out to be non-zero, then the polygon lies entirely outside the view volume, and we can discard the polygon.
Intersecting an arbitrary polygon with the view volume is rather tedious. The good news is that it's also unnecessary: We can defer the intersection calculation to the scan-conversion stage of the pipeline. Suppose we use brute-force scan-conversion of the polygon; then we never need to find the intersection of the polygon with the screen. We simply intersect the polygon's bounding box with the screen's bounding box (which is easy), and check whether each of those pixels lies within the polygon.
There is one plane that is important, though: Points whose z-value is 0 will result in division by zero when we perform homogeneous normalization after the projection transform. Moreover, points with positive z values (points behind the eye) can map to valid screen coordinates if we pass them down the pipeline. To avoid this, we'll clip the polygon against the near plane before passing it down the pipeline. (Intersecting a polygon with a half-space is six times easier than intersecting with the view volume.)