Clipping 剪辑

In the last few chapters, we developed equations and algorithms to transform a 3D definition of a scene into 2D shapes we can draw on the canvas; we developed a scene structure that lets us define 3D models and place instances of those models in the scene; and we developed an algorithm that lets us render the scene from any point of view.
在过去的几章中，我们开发了方程和算法，将场景的三维定义转化为我们可以在画布上绘制的二维图形；我们开发了一个场景结构，让我们定义三维模型并将这些模型的实例放置在场景中；我们还开发了一个算法，让我们从任何视角渲染场景。

However, doing this exposes one of the limitations we’ve been working with: the perspective projection equations only work as expected for points that are in front of the camera. Since we can now move and rotate the camera around the scene, this poses a problem.
然而，这样做暴露了我们一直以来的一个局限性：透视投影方程只对位于摄像机前面的点起作用。由于我们现在可以在场景中移动和旋转摄像机，这就造成了一个问题。

In this chapter, we’ll develop the techniques necessary to lift this limitation: we’ll explore how to identify points, triangles, and entire objects that are behind the camera and develop techniques to deal with them.
在这一章中，我们将开发必要的技术来解除这一限制：我们将探讨如何识别摄像机后面的点、三角形和整个物体，并开发处理它们的技术。

An Overview of the Clipping Process
剪辑过程概述

Back in Chapter 9 (Perspective Projection), we arrived at the following equations:
早在第9章（透视投影）中，我们就得出了以下公式。

$$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. Moreover, points behind the camera have negative $Z$ values, which we currently can’t handle properly. Even points in front of the camera but very close to it will cause trouble in the form of severely distorted objects.
除以P z 𝑃 𝑧是有问题的；它可能导致除以零。此外，摄像机后面的点有负的Z𝑍值，我们目前无法正确处理。即使是在摄影机前面但非常接近摄影机的点也会造成麻烦，会出现严重扭曲的物体。

To avoid these problematic cases, we’ll choose not to render anything behind the projection plane $Z = d$. This clipping plane lets us classify any point as being inside or outside of the clipping volume—that is, the subset of space that is actually visible from the camera. In this case, the clipping volume is “whatever is in front of $Z = d$.” We’ll only render the parts of the scene that are inside the clipping volume.
为了避免这些问题，我们将选择不渲染投影平面Z=d 𝑍 = 𝑑后面的任何东西。这个剪裁平面让我们可以将任何一个点划分为剪裁体积内或剪裁体积外--也就是说，从相机中实际可见的空间子集。在这种情况下，剪裁范围是 "Z=d 𝑍 = 𝑑前面的东西"。我们将只渲染场景中位于剪裁体积内的部分。

The Clipping Volume 剪切量

Using a single clipping plane to make sure no objects behind the camera are rendered will produce correct results, but 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 be projected outside of the viewport and therefore won’t be visible, as shown in Figure 11-1.
使用单一的剪贴面来确保摄像机后面的物体不被渲染，会产生正确的结果，但这并不完全有效。有些物体可能在摄像机前面，但仍然不可见；例如，靠近投影平面但在右边很远很远的物体的投影将被投影到视口之外，因此不可见，如图11-1所示。

Any computational resources we use to project such an object, plus all the per-triangle and per-vertex computations done to render it, would be wasted. It would be more efficient to ignore these objects altogether.
我们用来投射这样一个对象的任何计算资源，加上为渲染它而进行的所有每三角形和每顶点的计算，都会被浪费掉。完全忽略这些对象会更有效率。

To do this, we can define additional planes to clip the scene to exactly what should be visible on the viewport; these planes are defined by the camera and each of the four sides of the viewport (Figure 11-2).
要做到这一点，我们可以定义额外的平面，将场景准确地夹在视口上应该看到的地方；这些平面由摄像机和视口的四边分别定义（图11-2）。

Each of the clipping planes splits space in two parts we call half-spaces. The “inside” half-space is everything that’s in front of the plane; the “outside” half-space is everything that’s behind it. The “inside” of the clipping volume we’re defining is the intersection of the “inside” half-spaces defined by each clipping plane. In this case, the clipping volume looks like an infinitely tall pyramid with the top chopped off.
每个剪裁平面将空间分成两部分，我们称之为半空间。内部 "半空间是指平面前面的一切；"外部 "半空间是指它后面的一切。我们所定义的剪裁体积的 "内部 "是每个剪裁平面所定义的 "内部 "半空间的交点。在这种情况下，剪裁体积看起来像一个顶部被砍掉的无限高的金字塔。

This means that to clip the scene against a clipping volume, we just need to clip it in succession against each of the planes that define the clipping volume. Whatever geometry remains inside after clipping against one plane is then clipped against the remaining planes. After the scene has been clipped against all the planes, the geometry that remains is the result of clipping the scene against the clipping volume.
这意味着，要在一个剪裁体上剪裁场景，我们只需要在定义剪裁体的每个平面上连续剪裁。在对一个平面进行剪裁后，里面的几何图形将被剪裁到其余的平面上。当场景在所有的平面上被剪切后，剩下的几何体就是针对剪切体剪切场景的结果。

Next we’ll take a look at how to clip the scene against each clipping plane.
接下来我们将看看如何根据每个剪贴面来剪贴场景。

Clipping the Scene Against a Plane
对着飞机的场景进行剪辑

Consider a scene with multiple objects, each made of four triangles (Figure 11-3).
考虑一个有多个物体的场景，每个物体由四个三角形组成（图11-3）。

The fewer operations we execute, the faster our renderer will be. We will clip the scene against a clipping plane as a sequence of stages. Each stage will attempt to classify as much geometry as possible as either accepted or discarded, depending on whether it’s inside or outside the half-space defined by the clipping plane (that is, the clipping volume of this plane). Whatever geometry can’t be classified moves on to the next stage, which will take a more detailed look at it.
我们执行的操作越少，我们的渲染器就越快。我们将以一连串的阶段对场景进行剪裁。每个阶段都会尝试将尽可能多的几何体分类为可接受或可抛弃，这取决于它是在剪裁平面所定义的半空间（也就是这个平面的剪裁体积）之内还是之外。任何不能被分类的几何体都会进入下一个阶段，它将对其进行更详细的检查。

The first stage attempts to classify entire objects at once. If an object is completely inside the clipping volume, it’s accepted (green in Figure 11-4); if it’s completely outside, it’s discarded (red in Figure 11-4).
第一阶段试图一次对整个物体进行分类。如果一个物体完全在剪裁体积内，它就被接受（图11-4中的绿色）；如果它完全在剪裁体积外，它就被丢弃（图11-4中的红色）。

If an object can’t be fully accepted or discarded, we move on to the next stage and classify each of its triangles independently. If a triangle is completely inside the clipping volume, it’s accepted; if it’s completely outside, it’s discarded (see Figure 11-5).
如果一个物体不能被完全接受或丢弃，我们就进入下一个阶段，对其每个三角形进行独立分类。如果一个三角形完全在剪裁体积内，它就被接受；如果它完全在剪裁体积外，它就被丢弃（见图11-5）。

Finally, for each triangle that isn’t either accepted or discarded, we need to clip the triangle itself. The original triangle is removed, and either one or two new triangles are added to cover the part of the triangle that is inside the clipping volume (see Figure 11-6).
最后，对于每个没有被接受或丢弃的三角形，我们需要对三角形本身进行剪切。原有的三角形被移除，然后添加一个或两个新的三角形来覆盖三角形在剪裁体积内的部分（见图11-6）。

Now that we have a clear conceptual understanding of how clipping works, we’ll develop the math and algorithms to create a working implementation.
现在我们对剪裁的工作原理有了清晰的概念性理解，我们将开发数学和算法来创建一个工作实现。

Defining the Clipping Planes
定义剪裁平面

Let’s start with the equation of the projection plane $Z = d$, which we’ll use as a clipping plane. This equation is simple to visualize, but it’s not in the most convenient or general form for our purposes.
让我们从投影平面Z=d 𝑍 = 𝑑的方程开始，我们将把它作为一个剪裁平面。这个方程很简单，但对于我们的目的来说，它不是最方便或最一般的形式。

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 on the plane. If we group the coefficients $(A, B, C)$ in a vector $\vec{N}$, we can rewrite the equation as $\langle \vec{N}, P \rangle + D = 0$.
三维平面的一般方程是Ax+By+Cz+D=0 𝐴 𝑥 + 𝐵 𝑦 + 𝐶 𝑧 + 𝐷=0，这意味着当且仅当P𝑃位于平面上时，点P=（x,y,z） 𝑃=（𝑥 , 𝑦 , 𝑧 ）将满足该方程。如果我们将系数（A,B,C） ( 𝐴 , 𝐵 , 𝐶 ) 分成一个向量 N ⃗ 𝑁 →，我们可以将方程改写为 ⟨ N ⃗ ,P⟩+D=0 ⟨ 𝑁 → , 𝑃 ⟩ + 𝐷 = 0。

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 / |\vec{N}|}$, multiply the original equation, and get a new equation $\langle \vec{N}\, ', P \rangle + D\, ' = 0$ where $\vec{N}\, '$ is a unit vector. So any given plane can be represented by an equation $\langle \vec{N}, P \rangle + D = 0$, where $\vec{N}$ is a unit vector and $D$ is a real number.
请注意，如果⟨ N ⃗ ,P⟩+D=0 ⟨ 𝑁 → , 𝑃 ⟩ + 𝐷 = 0，那么k⟨ N ⃗ ,P⟩+kD=0 𝑘 ⟨ 𝑁 → , 𝑃 ⟩ + 𝑘 𝐷 = 0 对于任何k值𝑘。特别是，我们可以选择k=1/| N ⃗ | 𝑘 = 1 / | 𝑁 → |，与原方程相乘，得到一个新方程 ⟨ N ⃗ ′ ,P⟩+D ′ =0 ⟨ 𝑁 → ′ , 𝑃 ⟩ + 𝐷′ =0 其中N ⃗ ′ 𝑁 → ′是一个单位向量。所以任何给定的平面都可以用一个方程来表示 ⟨ N ⃗ ,P⟩+D=0 𝑁 → , 𝑃 ⟩ + 𝐷 = 0, 其中 N ⃗ 𝑁 → 是一个单位向量，D 𝐷 是一个实际数。

This is a very convenient formulation: $\vec{N}$ happens to be 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 the plane to $P$ ; $distance = 0$ is just the special case where $P$ is contained in the plane.
这是一个非常方便的表述。N ⃗ 𝑁 → 恰好是平面的法线，-D - 𝐷 是从原点到平面的有符号距离。事实上，对于任何一个点P 𝑃，⟨ N ⃗ ,P⟩+D ⟨ 𝑁 → ，𝑃 ⟩ + 𝐷是平面到P 𝑃的符号距离；距离=0 𝑑 𝑖 𝑠 𝑡 𝑛 𝑐𝑒 = 0，只是P 𝑃包含在平面内的特殊情况。

If $\vec{N}$ is the normal of a plane, 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” with 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$:
如果N ⃗ 𝑁 →是一个平面的法线，那么-N → - 𝑁 →也是，所以我们选择N ⃗ 𝑁 →，使其指向剪裁体积的 "内部"。对于平面Z=d 𝑍 = 𝑑，我们选择法线(0,0,1) ( 0 , 0 , 1 ) ，它指向相对于相机的 "前方"。由于点(0,0,d)( 0 , 0 , 𝑑)包含在平面内，它必须满足平面方程，我们可以解决D 𝐷。

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

and from this we immediately get $D = -d$.
由此我们立即得到D=-𝐷 = - 𝑑。

We could have gotten $D = -d$ directly from the original plane equation $Z = d$ by rewriting it as $Z - d = 0$. However, we can apply this general method to derive the equations of the rest of the clipping planes.
我们本可以从原平面方程Z=d 𝑍 = 𝑑中直接得到D=d 𝑍 = 𝑑，将其改写为Z-d=0 𝑍 - 𝑑 = 0。然而，我们可以应用这种通用方法来推导其余剪接平面的方程。

We know all these additional planes have $D = 0$ (because they all go through the origin), so all we need to do is determine their normals. To make the math simple, we’ll choose a $90^\circ$ field of view (FOV), meaning the planes are at $45^\circ$.
我们知道所有这些额外的平面都有D=0 𝐷=0（因为它们都经过原点），所以我们需要做的就是确定它们的法线。为了使计算简单，我们将选择一个90∘的视场（FOV），也就是说，这些平面在45∘的位置。

Consider the left clipping plane. The direction of its normal is $(1, 0, 1)$ (that is, $45^\circ$ right and forward). The length of that vector is $\sqrt{2}$, so if we normalize it we get $({1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}})$. Therefore the equation of the left clipping plane is
考虑一下左边的剪裁平面。它的法线方向是（1,0,1）（1 , 0 , 1）（也就是说，45 ∘45 ∘右方和前方）。这个向量的长度是2-√2，所以如果我们把它归一化，就会得到 ( 1 2 √ ,0, 1 2 √ ) ( 1 2 , 0 , 1 2 ) 。因此，左侧剪裁平面的方程为

$$\langle N, P \rangle + D = \langle ({1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}}), P \rangle = 0$$

Similarly, the normals for the right, bottom, and top clipping planes are $({-1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}})$, $(0, {1 \over \sqrt{2}}, {1 \over \sqrt{2}})$, and $(0, {-1 \over \sqrt{2}}, {1 \over \sqrt{2}})$ respectively. Computing the clipping planes for any arbitrary FOV would involve just a little bit of trigonometry.
同样地，右侧、底部和顶部剪裁平面的法线分别是（-1 2 √ ,0, 1 2 √ ）（ - 1 2 , 0 , 1 2 ），（0, 1 2 √ , 1 2 √ ）（ 0 , 1 2 , 1 2 ），以及（0, -1 2 √ , 1 2 √ ）（ 0 , - 1 2 , 1 2 ）。计算任意FOV的剪裁平面只需要一点三角函数。

In summary, our clipping volume is defined by the following five planes:
综上所述，我们的剪裁量由以下五个平面定义。

$$(near) \langle (0, 0, 1), P \rangle - d = 0$$ $$(left) \langle ({1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}}), P \rangle = 0$$ $$(right) \langle ({-1 \over \sqrt{2}}, 0, {1 \over \sqrt{2}}), P \rangle = 0$$ $$(bottom) \langle (0, {1 \over \sqrt{2}}, {1 \over \sqrt{2}}), P \rangle = 0$$ $$(top) \langle (0, {-1 \over \sqrt{2}}, {1 \over \sqrt{2}}), P \rangle = 0$$

Let’s now take a detailed look at how to clip geometry against a plane.
现在让我们来详细了解一下如何针对一个平面来剪辑几何体。

Clipping Whole Objects 截取整个物体

Suppose we put each model inside the smallest sphere that can contain it; we call that sphere the bounding sphere of the object. Computing this sphere is surprisingly more difficult than it seems, and it falls outside the scope of this book. But a rough approximation can be obtained by first computing the center of the sphere by averaging the coordinates of all the vertices in the model, and then defining the radius to be the distance from the center to the vertex that it’s farthest away from.
假设我们把每个模型放在可以包含它的最小的球体里；我们把这个球体称为物体的边界球体。计算这个球体比它看起来要困难得多，而且它不属于本书的范围。但是可以得到一个粗略的近似值，首先通过平均模型中所有顶点的坐标来计算球体的中心，然后将半径定义为从中心到它最远的顶点的距离。

In any case, let’s assume we know the center $C$ and the radius $r$ of a sphere that completely contains each model. Figure 11-7 shows a scene with a few objects and their bounding spheres.
在任何情况下，让我们假设我们知道一个完全包含每个模型的球体的中心C𝐶和半径r𝑟。图11-7显示了一个有几个物体和它们的边界球体的场景。

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 entire object is accepted; no further clipping is necessary against this plane (but it may still be clipped by a different plane). See Figure 11-8 for an example.
在这种情况下，整个物体被接受；不需要针对这个平面进一步剪裁（但它仍然可能被不同的平面剪裁）。见图11-8的例子。

The sphere is completely behind the plane.
球体完全在平面后面。

In this case, the entire object is discarded; no further clipping is necessary (no matter what the other planes are, no part of the object will ever be inside the clipping volume). See Figure 11-9 for an example.
在这种情况下，整个物体被丢弃；没有必要进一步剪裁（无论其他平面是什么，物体的任何部分都不会在剪裁体积内）。请看图11-9的例子。

The plane intersects the sphere. 平面与球体相交。

This doesn’t give us enough information to know whether any part of the object is 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. See Figure 11-10 for an example.
这并没有给我们足够的信息来知道物体的任何部分是否在剪裁体积内；它可能完全在里面，完全在外面，或者部分在里面。有必要进入下一步，逐个三角形地剪裁模型。请看图11-10的例子。

How does this categorization actually work? The way we’ve chosen to express the clipping planes is such that plugging any point into 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; otherwise $|d| < r$, which means the plane intersects the sphere. Figure 11-11 illustrates all three cases.
这种分类实际上是如何进行的呢？我们选择的表达剪裁平面的方式是这样的：将任何点插入平面方程，就可以得到该点到平面的有符号距离；特别是，我们可以计算出从边界球体中心到平面的有符号距离d 𝑑。因此，如果d>r 𝑑 > 𝑟，球体就在平面前面；如果d<-r 𝑑 < - 𝑟，球体就在平面后面；否则|d|<r | 𝑑 | < 𝑟，这意味着平面与球体相交。图11-11说明了这三种情况。

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, we have to clip each triangle against it.
如果球面测试不足以确定一个物体是完全在剪裁平面的前面还是后面，我们就必须对照它来剪裁每个三角形。

We can classify each vertex of the triangle against the clipping plane by looking at its signed distance to the plane. If the distance is zero or positive, the vertex is in front of the clipping plane; otherwise, it’s behind. Figure 11-12 illustrates this idea.
我们可以通过观察三角形的每个顶点与剪裁平面的有符号距离来对其进行分类。如果这个距离是零或正的，那么这个顶点就在剪裁平面的前面；否则，它就在后面。图11-12说明了这个想法。

For each triangle, there are four possible classifications:
对于每个三角形，有四种可能的分类。

Three vertices in front. 前面有三个顶点。

In this case, the whole triangle is in front of the clipping plane, so we accept it and no further clipping against this plane is needed.
在这种情况下，整个三角形都在剪裁平面的前面，所以我们接受它，不需要针对这个平面进一步剪裁。

Three vertices behind. 后面有三个顶点。

In this case, the whole triangle is behind the clipping plane, so we discard it and no further clipping is 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, we discard $ABC$, and add a new triangle $AB\, 'C\, '$, where $B\, '$ and $C\, '$ are the intersections of $AB$ and $AC$ with the clipping plane (Figure 11-13).
让A𝐴是三角形ABC𝐴𝐵 𝐶的顶点，它位于平面的前面。在这种情况下，我们舍弃ABC 𝐴 𝐵 𝐶，并添加一个新的三角形AB ′ C ′ 𝐴 𝐵 ′ 𝐶，其中B ′ 𝐵 ′ 和C ′ ′ 是AB 𝐴 𝐵 和AC 𝐴 𝐶与剪裁平面的交点（图11-13）。

Two vertices in front. 两个顶点在前面。

Let $A$ and $B$ be the vertices of the triangle $ABC$ that are in front of the plane. In this case, we discard ABC and add two new triangles: $ABA\, '$ and $A\, 'BB\, '$, where $A\, '$ and $B\, '$ are the intersections of $AC$ and $BC$ with the clipping plane (Figure 11-14).
让A𝐴和B𝐵是三角形ABC𝐴𝐵𝐶的顶点，这些顶点在平面前面。在这种情况下，我们舍弃ABC，增加两个新的三角形。ABA ′ 𝐴 𝐵 𝐴 ′和A ′ BB ′ 𝐴 ′ 𝐵 ′，其中A ′ 𝐴 ′和B ′ 𝐵 ′是AC 𝐴 𝐶和BC 𝐵 𝐶与剪切平面的交点（图11-14）。

Segment-Plane Intersection 分段-平面交叉点

To clip triangles as discussed above, we need to compute the intersection of the sides of the triangle with the clipping plane.
要像上面讨论的那样剪辑三角形，我们需要计算三角形的边与剪辑平面的交点。

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:
我们有一个由方程⟨N,P⟩+D=0 ⟨ 𝑁 , 𝑃 ⟩ + 𝐷 = 0.三角形边AB𝐴𝐵可以用参数方程表示为P=A+t（B-A） 𝑃 = 𝐴 + 𝑡 ( 𝐵 - 𝐴 ) 为0≤t≤1 0 ≤ 𝑡 ≤ 1。为了计算发生交点的参数t𝑡的值，我们将平面方程中的P𝑃替换为线段的参数方程。

$$\langle N, P \rangle + D = 0$$ $$P = A + t(B - A)$$ $$\implies {\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 𝑡。

$$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 that the segment and the normal are perpendicular, which in turn would imply that the segment and the plane don’t intersect.
我们知道一个解决方案总是存在的，因为我们知道AB𝐴𝐵与平面相交；在数学上，⟨N,B-A⟩ ⟨ 𝑁 ，𝐵 - 𝐴⟩不可能是零，因为这意味着线段和法线是垂直的，这又意味着线段和平面没有相交。

Having computed $t$, the intersection $Q$ is simply
在计算了t 𝑡之后，交集Q 𝑄简单地说就是

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

Note that if the original vertices carry additional attributes (for example, the $h$ intensity value we were using in Chapter 7 (Filled Triangles)), we need to compute the values of these attributes for the new vertices.
注意，如果原始顶点带有额外的属性（例如，我们在第7章（填充三角形）中使用的hℎ强度值），我们需要为新顶点计算这些属性值。

In the equation above, $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 computed as
在上式中，t 𝑡是发生交集的AB 𝐴 𝐵段的分数。假设α A 𝛼 𝐴和α B 𝐵是某个属性α 𝛼在A𝐴和B 𝐵两点的值；如果我们假设该属性在AB 𝐴 𝐵中呈线性变化，那么α Q 𝛼 𝑄可以被计算为

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

We now have all the algorithms and equations to implement our clipping pipeline.
我们现在有了所有的算法和方程式来实现我们的剪裁管道。

Clipping Pseudocode 剪切伪代码

Let’s write some high-level pseudocode for the clipping pipeline. We’ll follow the top-down approach we developed before.
让我们为剪裁管道写一些高级伪代码。我们将遵循我们之前开发的自上而下的方法。

To clip a scene, we clip each of its instances (Listing 11-1).
要剪辑一个场景，我们要剪辑它的每个实例（清单11-1）。

ClipScene(scene, planes) {
    clipped_instances = []
    for I in scene.instances {
        clipped_instance = ClipInstance(I, planes)
        if clipped_instance != NULL {
            clipped_instances.append(clipped_instance)
        }
    }
    clipped_scene = Copy(scene)
    clipped_scene.instances = clipped_instances
    return clipped_scene
}

To clip an instance, we either accept it, reject it, or clip each of its triangles, depending on its bounding sphere (Listing 11-2).
为了剪辑一个实例，我们要么接受它，要么拒绝它，要么根据它的边界球体剪辑它的每个三角形（清单11-2）。

ClipInstance(instance, planes) {
    for P in planes {
        instance = ClipInstanceAgainstPlane(instance, plane)
        if instance == NULL {
            return NULL
        }
    }
    return instance
}

ClipInstanceAgainstPlane(instance, plane) {
    d = SignedDistance(plane, instance.bounding_sphere.center)
    if d > r {
        return instance
    } else if d < -r {
        return NULL
    } else {
        clipped_instance = Copy(instance)
        clipped_instance.triangles =
            ClipTrianglesAgainstPlane(instance.triangles, plane)

        return clipped_instance
    }
}

Finally, to clip a triangle, we either accept it, reject it, or decompose it into up to two triangles, depending on how many of its vertices are in front of the clipping plane (Listing 11-3).
最后，为了剪辑一个三角形，我们要么接受它，要么拒绝它，要么把它分解成最多两个三角形，这取决于它有多少个顶点在剪辑平面的前面（清单11-3）。

ClipTrianglesAgainstPlane(triangles, plane) {
    clipped_triangles = []
    for T in triangles {
        clipped_triangles.append(ClipTriangle(T, plane))
    }
    return clipped_triangles
}

ClipTriangle(triangle, plane) {
    d0 = SignedDistance(plane, triangle.v0)
    d1 = SignedDistance(plane, triangle.v1)
    d2 = SignedDistance(plane, triangle.v2)

    if {d0, d1, d2} are all positive {
        return [triangle]
    } else if {d0, d1, d2} are all negative {
        return []
    } else if only one of {d0, d1, d2} is positive {
        let A be the vertex with a positive distance
        compute B' = Intersection(AB, plane)
        compute C' = Intersection(AC, plane)
        return [Triangle(A, B', C')]
    } else /* only one of {d0, d1, d2} is negative */ {
        let C be the vertex with a negative distance
        compute A' = Intersection(AC, plane)
        compute B' = Intersection(BC, plane)
        return [Triangle(A, B, A'), Triangle(A', B, B')]
    }
}

The helper function SignedDistance just plugs the coordinates of a point into the equation of a plane (Listing 11-4).
辅助函数 SignedDistance 只是将一个点的坐标插入一个平面的方程中（清单11-4）。

SignedDistance(plane, vertex) {
    normal = plane.normal
    return (vertex.x * normal.x)
         + (vertex.y * normal.y)
         + (vertex.z * normal.z)
         + plane.D
}

Source code and live demo >>
源代码和现场演示 >>

Clipping in the Rendering Pipeline
渲染管线中的剪裁

The order of the chapters in the book is not the order of operations 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 or, more precisely, it computes the intersection of the scene and the clipping volume. For this reason, clipping must happen after objects have been placed in the scene (that is, using the vertices 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 pre-process their levels by 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 pre-processing time and a more rigid scene. If you’re interested in this topic, read about BSP partitioning and portal systems.
本章介绍的技术可以可靠地工作，但非常通用。你对你的场景有越多的先验知识，你的剪裁就会越有效。例如，许多游戏通过向它们添加可见性信息来预处理它们的关卡；如果你能将一个场景划分为 "房间"，你就可以制作一个表格，列出从任何给定的房间都能看到哪些房间。当以后渲染场景时，你只需要弄清楚摄像机在哪个房间，你就可以安全地忽略所有被标记为 "不可见 "的房间，从而在渲染时节省大量资源。当然，其代价是更多的预处理时间和更僵硬的场景。如果你对这个话题感兴趣，可以阅读BSP分区和门户系统的内容。

Summary

In this chapter, we finally lifted one of the main limitations caused by the perspective projection equation. We’ve overcome the limitation that only vertices in front of the camera can be meaningfully projected. In order to do this, we came up with a precise definition of what “being in front of the camera” means: whatever is inside a clipping volume we define with five planes.
在这一章中，我们终于解除了由透视投影方程引起的一个主要限制。我们克服了只有在摄像机前面的顶点才能被有意义地投影的限制。为了做到这一点，我们为 "在摄像机前面 "的含义提出了一个精确的定义：凡是在我们用五个平面定义的剪切体积内的东西。

Then we developed the equations and algorithms to compute the geometrical intersection between the scene and the clipping volume. As a consequence, we can take an entire scene and remove everything that can’t possibly be projected onto the viewport. This not only avoids the cases that can’t be handled by the perspective projection equations, it also saves computation resources by removing geometry that would be projected outside of the viewport.
然后我们开发了方程式和算法来计算场景和剪裁体积之间的几何交集。因此，我们可以取一个完整的场景，并删除所有不可能投射到视口上的东西。这不仅避免了透视投影方程无法处理的情况，而且还通过移除将被投影到视口之外的几何体来节省计算资源。

However, after clipping a scene, we might still end up with geometry that could be visible in the final canvas, but which will not, most likely because there’s something else in front of it! We’ll find ways to deal with this in the next chapter.