D Clipping

Last in the fixes to Simple3DTest1 is to add 3D clipping. You might remember that the tree polygon looked very strange when it was close to the camera, and the tree appeared upside down when it was behind the camera. To fix this, you're going to clip the polygons to the view frustum. The view frustum is a pyramid formed by four planes. You could clip a polygon to each of the planes. Alternatively, you could clip a polygon to a front clip plane and let 2D clipping handle the rest. This works well and is the method you'll use. Three situations arise when clipping a polygon to a plane: Either the polygon is completely in front of the plane, completely behind it, or intersecting the plane. If it's behind the plane, you can ignore the polygon. If it intersects the plane, you need to clip the polygon to the plane so that you draw only the portion of the polygon in front of the plane. Clipping a convex polygon to a plane creates another convex polygon, so you're not creating any concave polygons in this process. Let's start with Screenshot. Here, a polygon intersects the clip plane. In the figure, the front of the plane is on top of the dotted line.

Screenshot Clipping, step 1: A polygon intersects the clip plane.

In the next step, in Screenshot, you add vertices to the polygon where the polygon's edges and the clip plane intersect.

Screenshot Clipping, step 2: Add vertices at the intersection of the clip plane and the polygon's edges.

At this stage, every edge of the polygon is either completely in front of or completely behind the clip plane. The last step is to just remove the edges behind the clip plane, or to simply remove all vertices that are behind the clip plane, as shown in Screenshot.

Screenshot Clipping, step 3: Remove all vertices behind the clip plane.

Because the front clip plane is parallel to the view window, all that's left is to pick a location of the clip plane. You might first pick z=0, but this can lead to some divide-by-zero problems. In the demos in this tutorial, we use z=-1. To find the intersection of a polygon edge with the clip plane, again you use the equation of the line. Knowing the location of the clip plane z, you get the equations to find the point of intersection:

x = (z-z1)(x2-x1)/(z2-z1)+x1
y = (z-z1)(y2-y1)/(z2-z1)+y1
z = z

The clipping algorithms is implemented in the clip() method, shown here and added to the Polygon3D class:

/**
 Clips this polygon so that all vertices are in front of
 the clip plane, clipZ (in other words, all vertices
 have z <= clipZ).
 The value of clipZ should not be 0, as this causes
 divide-by-zero problems.
 Returns true if the polygon is at least partially in
 front of the clip plane.
*/
public boolean clip(float clipZ) {
 ensureCapacity(numVertices * 3);
 boolean isCompletelyHidden = true;
 // insert vertices so all edges are either completely
 // in front of or behind the clip plane
 for (int i=0; i<numVertices; i++) {
 int next = (i + 1) % numVertices;
 Vector3D v1 = v[i];
 Vector3D v2 = v[next];
 if (v1.z < clipZ) {
 isCompletelyHidden = false;
 }
 // ensure v1.z < v2.z
 if (v1.z > v2.z) {
 Vector3D temp = v1;
 v1 = v2;
 v2 = temp;
 }
 if (v1.z < clipZ && v2.z > clipZ) {
 float scale = (clipZ-v1.z) / (v2.z - v1.z);
 insertVertex(next,
 v1.x + scale * (v2.x - v1.x) ,
 v1.y + scale * (v2.y - v1.y),
 clipZ);
 // skip the vertex we just created
 i++;
 }
 }
 if (isCompletelyHidden) {
 return false;
 }
 // delete all vertices that have z > clipZ
 for (int i=numVertices-1; i>=0; i--) {
 if (v[i].z > clipZ) {
 deleteVertex(i);
 }
 }
 return (numVertices >= 3);
}
/**
 Inserts a new vertex at the specified index.
*/
protected void insertVertex(int index, float x, float y,
 float z)
{
 Vector3D newVertex = v[v.length-1];
 newVertex.x = x;
 newVertex.y = y;
 newVertex.z = z;
 for (int i=v.length-1; i>index; i--) {
 v[i] = v[i-1];
 }
 v[index] = newVertex;
 numVertices++;
}
/**
 Delete the vertex at the specified index.
*/
protected void deleteVertex(int index) {
 Vector3D deleted = v[index];
 for (int i=index; i<v.length-1; i++) {
 v[i] = v[i+1];
 }
 v[v.length-1] = deleted;
 numVertices--;
}

The clipping technique implemented is relatively simple, considering that you're clipping to only a vertical, front clip plane. Optionally, you might also want to clip to a vertical back clip plane (so polygons very far away aren't drawn). Of course, clipping to the left, right, top, and bottom planes of the view frustum relieves the scan converter of some work, but just clipping to the front clip plane provides the correct results.