Clipping

Back in the Perspective Projection chapter, we arrived at the following equations:

$P'_X = {P_X \cdot d \over P_Z}$

$P'_Y = {P_Y \cdot d \over P_Z}$

The division by $$P_Z$$ is problematic; it can cause a division by zero. It can also yield negative values, which represent points behind the camera, and which aren’t handled properly. Even points which are in front of the camera but very close to it will cause trouble, in the form of severely distorted objects.

To avoid all these problematic cases, we choose not to render anything behind the projection plane $$Z = d$$. This clipping plane lets us classify any point as being inside or outside the clipping volume, that is, the subset of space which is actually visible from the camera. In this case, the clipping volume is “the half-space in front of $$Z = d$$”. We’ll only render the parts of the scene which are inside the clipping volume.

The fewer operations we make, the faster our renderer will be, so we’ll follow a top-down approach. Consider a scene with multiple objects, each made of four triangles:

Each step tries to determine as cheaply as possible whether we can stop clipping at that point, or if further and more detailed clipping is needed:

• If an object is completely inside the clipping volume, it’s accepted (green); if it’s completely outside, it’s discarded (red):
• Otherwise, we repeat the process on a per-triangle basis. If a triangle is completely inside the clipping volume, it’s accepted; if it’s completely outside, it’s discarded:
• Otherwise, we need to clip the triangle itself. The original triangle is discarded, and either one or two triangles are added to cover the part of the triangle that is inside the clipping volume:

We’ll now take a more detailed look at each step in the process.

Defining the clipping planes

The first thing we need to do is to find an equation for the clipping plane. There’s nothing wrong with $$Z = d$$, but it’s not the most convenient format for our purposes; and because later in this chapter we’ll generalize this approach to other clipping planes, we’ll develop a generic approach instead of one for this particular case.

The general equation for a 3D plane is $$Ax + By + Cz + D = 0$$, meaning a point $$P = (x, y, z)$$ will satisfy that equation if and only if $$P$$ is in the plane. We can rewrite the equation as $$\langle \vec{N}, P \rangle + D = 0$$, where $$\vec{N} = (A, B, C)$$.

Note that if $$\langle \vec{N}, P \rangle + D = 0$$, then $$k\langle \vec{N}, P \rangle + kD = 0$$ for any value of $$k$$. In particular, we can choose $$k = { 1 \over |\vec{N}| }$$ and get a new equation $$\langle \vec{N}', P \rangle + D' = 0$$ where $$\vec{N}'$$ is an unit vector. So for any given plane we can always assume there exists $$\vec{N}$$, an unit vector, and $$D$$, a real number, such that $$\langle \vec{N}, P \rangle + D = 0$$ is the equation of that plane.

This is a very convenient formulation: $$\vec{N}$$ is actually the normal of the plane, and $$-D$$ is the signed distance from the origin to the plane. In fact, for any point $$P$$, $$\langle \vec{N}, P \rangle + D$$ is the signed distance from $$P$$ to the plane; it’s easy to see that $$0$$ is the special case where $$P$$ is contained in the plane.

As we’ve seen before, if $$\vec{N}$$ is a plane normal so is $$\vec{-N}$$, so we choose $$\vec{N}$$ such that it points to “inside” the clipping volume. For the plane $$Z = d$$ we choose the normal $$(0, 0, 1)$$, which points “forward” respect to the camera. Since the point $$(0, 0, d)$$ is contained in the plane, it must satisfy the plane equation, and we can solve for $$D$$:

$\langle \vec{N}, P \rangle + D = \langle (0, 0, 1), (0, 0, d) \rangle + D = d + D = 0$

so $$D = -d$$1.

The clipping volume

Although using a single clipping plane to make sure no objects behind the camera are rendered does produce correct results, it’s not entirely efficient. Some objects may be in front of the camera but still not visible; for example, the projection of an object near the projection plane but far, far to the right will fall outside of the viewport and therefore won’t be visible:

Any resources we use to compute the projection of such an object, plus all the per-triangle and per-vertex computations done to render it, would be wasted. It would be nice to ignore these objects altogether.

Fortunately, this is not difficult at all. We can define additional planes to clip the scene to exactly what can be visible on the viewport; these planes are defined by the camera and each of the sides of the viewport:

All these planes have $$D = 0$$ (since the origin is contained in all the planes), so all is left is to determine the normals. The easiest case is a $$90^\circ$$ FOV, where the planes are at $$45^\circ$$, so their normals are $$({1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}})$$ for the left plane, $$({-1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}})$$ for the right plane, and $$(0, {1 \over \sqrt{2}}, {1 \over \sqrt{2}})$$ and $$(0, {-1 \over \sqrt{2}}, {1 \over \sqrt{2}})$$ for the bottom and top planes respectively. Computing the clipping planes for any arbitrary FOV involves just a little bit of trigonometry.

To clip objects or triangles against a clipping volume, we just clip them against each plane in sequence. Whatever survives the clipping against one plane is clipped against the rest of the planes; this works because the clipping volume is the intersection of the half-spaces defined by each clipping plane.

Clipping whole objects

Having the clipping volume fully defined by its clipping planes, we can start by determining whether an object is completely inside or outside the half-space determined by each of these planes.

Suppose we put each model inside the smallest sphere that can contain it. How to get this sphere is outside the scope of the book; it can be computed from the set of its vertexes by one of several algorithms, or an approximation can be defined by the designer of the model. In any case, let’s assume we have the center $$C$$ and the radius $$r$$ of a sphere that completely contains each object:

We can categorize the spatial relationship between this sphere and a plane as follows:

• The sphere is completely in front of the plane. In this case the model is accepted; no further clipping is necessary against this plane (it may still be clipped by a different plane, though):
• The sphere is completely behind the plane. In this case the model is discarded; no further clipping is necessary at all (no matter what the other planes are, no part of the model will ever be inside the clipping volume):
• The plane intersects the sphere. This doesn’t give us enough information to know whether parts of the object are inside the clipping volume; it may be completely inside, completely outside, or partially inside. It is necessary to proceed to the next step and clip the model triangle by triangle.

How does this categorization actually work? We’ve chosen a way to express the clipping planes in such a way that plugging any point in the plane equation gives us the signed distance from the point to the plane; in particular, we can compute the signed distance $$d$$ from the center of the bounding sphere to the plane. So if $$d > r$$, the sphere is in front of the plane; if $$d < -r$$, the sphere is behind the plane; and otherwise $$|d| < r$$, which means the plane intersects the sphere.

Clipping triangles

If the sphere-plane test isn’t enough to determine whether an object is fully in front or fully behind the clipping plane, it’s necessary to clip each triangle against it.

We can classify each vertex of the triangle against the clipping plane by taking the sign of its signed distance to the plane. If the distance is zero or positive, the vertex is in front of the clipping plane, and otherwise it’s behind:

There are four possible cases:

• Three vertexes in front. In this case the whole triangle is in front of the clipping plane, so it’s accepted with no further clipping against this plane needed.

• Three vertexes behind. In this case the whole triangle is behind the clipping plane, so it’s discarded with no further clipping necessary at all.

• One vertex in front. Let $$A$$ be the vertex of the triangle $$ABC$$ that is in front of the plane. In this case, $$ABC$$ is discarded, and a new triangle $$AB'C'$$ is added, where $$B'$$ and $$C'$$ are the intersections of $$AB$$ and $$AC$$ with the clipping plane.

• Two vertexes in front. Let $$A$$ and $$B$$ the vertexes of the triangle $$ABC$$ that are in front of the plane. In this case, ABC is discarded, and two new triangles are added: $$ABA'$$ and $$A'BB'$$, where $$A'$$ and $$B'$$ are the intersections of $$AC$$ and $$BC$$ with the clipping plane.

Segment-Plane intersection

To do per-triangle clipping we need to compute the intersection of triangle sides with the clipping plane. Note that it’s not enough to compute the coordinates of the intersection: it’s also necessary to compute the appropriate value of any attribute that was associated to the vertexes, such as shading as seen in the Drawing shaded triangles chapter, or one of the attributes described in the following chapters.

We have a clipping plane given by the equation $$\langle N, P \rangle + D = 0$$. The triangle side $$AB$$ can be expressed with a parametric equation as $$P = A + t(B - A)$$ for $$0 \le t \le 1$$. To compute the value of the parameter $$t$$ where the intersection occurs, we replace $$P$$ in the plane equation with the parametric equation of the segment:

$\langle N, A + t(B - A) \rangle + D = 0$

Using the linear properties of the dot product:

$\langle N, A \rangle + t\langle N, B - A \rangle + D = 0$

Solving for $$t$$:

$t = {-D - \langle N, A \rangle \over \langle N, B - A \rangle}$

We know a solution always exists because we know $$AB$$ intersects the plane; mathematically, $$\langle N, B - A \rangle$$ can’t be zero because that would imply the segment and the normal are perpendicular, which in turn would imply the segment and the plane don’t intersect.

Having computed $$t$$, the intersection $$Q$$ is simply

$Q = A + t(B - A)$

Note that $$t$$ is the fraction of the segment $$AB$$ where the intersection occurs. Let $$\alpha_A$$ and $$\alpha_B$$ be the values of some attribute $$\alpha$$ at the points $$A$$ and $$B$$; if we assume the attribute varies linearly across $$AB$$, then $$\alpha_Q$$ can be easily computed as

$\alpha_Q = \alpha_A + t(\alpha_B - \alpha_A)$

Clipping in the pipeline

The order of the chapters in the book is not the order in which operations need to be done in the rendering pipeline; as explained in the introduction, the chapters are ordered in such a way that visible progress is reached as quickly as possible.

Clipping is a 3D operation; it takes 3D objects in the scene and generates a new set of 3D objects in the scene, more precisely, the intersection of the scene and the clipping volume. It should be clear that clipping must happen after objects have been placed on the scene (that is, using the vertexes after the model and camera transforms) but before perspective projection.

The techniques presented in this chapter work reliably, but are very generic. The more prior knowledge you have about your scene, the more efficient your clipping can be. For example, many games preprocess their game maps adding visibility information to them; if you can divide a scene into “rooms”, you can make a table listing what rooms are visible from any given room. When rendering the scene later, you just need to figure out what room the camera is in, and you can safely ignore all the rooms marked as “non-visible” from there, saving considerable resources during rendering. The trade-off is, of course, more preprocessing time and a more rigid scene.

Found an error? Everything is in Github.

1. It would have been trivial to get here from $$Z = d$$ by rewriting it as $$Z - d = 0$$. However, the reasoning presented here applies to the rest of the planes we’ll be dealing with, and helps us deal with the fact that $$-Z + d = 0$$ is equally valid, but with the normal pointing in the wrong direction.