3D图形编程指南(back culling)

隐面消除(back culling)

　　目 录
　　7.1 背面剔除算法
　　7.2 从后到前排序
　　7.3 顺序列表和八叉树
　　7.4 入口
　　7.5 二叉空间分割树
　　7.6 Beam树
　　7.7 扫描线算法
　　7.8 Z-Buffer算法

---

　　引言
　　到目前为止，我们完全忽略了一些问题：很明显，它们是由于屏幕上的一些图元被另一些图元挡住所造成的。例如，当我们要描绘一个由多边形面组成的三维物体时，那么它的一部分必然要被挡住。我们要在屏幕上显示的必须是可见的东西。打个比方，对于一个立方体，无论从哪个方向进行透视处理，我们最多只能看到其中的三个面。这样，我们就要想出一种方法来决定哪些面是我们所能看到的。
　　如果我们使用从屏幕到世界的视处理方法，那么很自然的就能保证只有图元上正确的部分才显示在屏幕上。在这种视处理中，可见性在屏幕的每一个像素上进行判断。我们从人眼发出一条射线，穿过一个给定的像素，那么首先与这条射线相交的表面在这一个像素上就是可见的。从这个表面反射的光线能够进入我们的眼睛。
　　在这一章中，我们将讨论用于隐面消除的一些方法。由于最普通的图元就是多边形，所以我们将要讨论的许多技术都是只针对多边形模型的。我们也将重点讨论用于多边形地形、体素模型的一些技术，最后将讨论一种适用于任何图元的一般性的算法。
　　尽管隐面消除对于光线投射方法是本身就具备的，但是它的计算量是很大的。这样，我们还将使用一些用于从世界到屏幕视处理方法的隐面消除算法，它们将与光线投射算法结合使用，从而减少计算量。

7.1、背面剔除(back culling)算法
　　许多三维物体，它们所占据的空间都被一些连续的表面所包围。当我们观察这些物体时，只能看到这些包围表
面中正面部分，而对背面就无法看到了。背面剔除算法就是将这些我们看不到的背面多边形去除掉(见图7.1)

图7.1 包围表面的可见与不可见部分

　　在前面的章节中，我们已经遇到过凸多边形的概念。这一概念也可以引申到多面体上。如果位于表面上的任意两个点的连线都没有超出边界的话，那么这个多面体就是一个凸多面体。凹多面体没有这样的特性。(见图7.2)

图7.2 凸多面体与凹多面体

　　如果我们对一个多边形模型执行背面剔除，并且这个模型是一个凸多面体，那么经过这样的处理之后，我们就已经消除了所有的隐藏表面。由于这些模型的形状，所有隐藏的多边形就是组成背面的多边形。但是，在消除凹多面体的隐藏面时，这一通用的技术就会出现一些问题。有可能某些对象的正面被其他多边形中同样是正面的面遮挡(见图7.3)。这时，位于背面的多边形仍然是不可见的，明确地消除它们将对此有帮助， 即便不能解决这一问题，那么至少减小了其复杂性。

图7.3 向前的多边形被遮挡的情况

　　同样的推理也应用于光线投射算法。尽管我们完成隐面消除要归功于这种算法的自然本性，但背面剔除算法可以减少场景的复杂度，使我们不用再同那些复杂的隐藏面一起进行考虑，这样就加快了视处理的过程。
　　让我们来设计一种技术，来决定一个多边形是位于物体表面的正面还是背面。我们已经看到了法向量在描述一个多边形的朝向时所起到的作用。这样，当一个多边形的法向量与观察方向之间的夹角大于90°时，就表示这个多边形位于物体的背面。
　　我们已经讨论过矢量积和标量积，它们对于解决上面的问题很有帮助。首先，我们计算位于一个给定多边形平面上的某两个向量的矢量积，得到这个多边形的法向量。这两个向量可以通过多边形顶点的差分来得到。接下来，计算观察方向与法向量之间标量积的符号，由此决定它们之间是否形成了大于90°的角。如果真的大于90°，这个多边形就要被剔除掉，也就不用再考虑进行视处理过程了。
　　我们要注意，根据定义，两个向量的矢量积的结果也是一个向量，它与两个做向量乘法的向量组成的平面正交。这也就是说，根据多边形平面上形成这两个向量的方式的不同，我们可以得到两种可能的法向量，它们的方向正好相反。(见图7.4)

图7.4 顶点顺序与方向量方向的关系

　　如图7.4所示，如果我们在连续顶点和建立两个向量，那么法向量的方向将会依赖于这两个向量的顺序。我们可以很方便的将多边形表面的正面与顶点的反时针顺序联系起来(见图7.4 (a))，这也正是定义表面法向量的基础。
　　我们已经见到了两种不同的视处理过程，并且还有两种不同的投影变换。使用这些技术，我们可以在渲染管道中的某一特定阶段完成背面剔除算法。
　　对于平行投影方式，投影线都具有相同的方向，并且与观察方向一致。就在投影阶段之前，观察方向向量指向Z方向，可以用(0,0,1)来进行描述。这样当然也就减少了标量积的计算量，其结果就等于法向量的z分量。这样，我们就只需要计算法向量的z分量值就可以了。
　　对于透视投影，投影线相交在观察者的眼中，它们的方向是不同的。我们可以在世界或观察空间中的任一点上构造一个指向观察者眼睛的向量，并使它指向该点方向，这样就得到了这一点的观察方向。(见图7.5)

图7.5 寻找背面多边形

　　然而，一旦模型经过透视变换从观察空间映射到屏幕空间之后，用来执行背面剔除的观察方向恒定，使我们只需要对法向量的z分量来进行简单的计算就可以了。
　　背面剔除可以在渲染管道的开始阶段执行，也可以在世界空间甚至对象空间中来进行。我们越早剔除掉背面多边形，那么要执行的多余的操作就会也少。我们还要考虑对顶点进行的3-D变换，这样，如果我们可以剔除掉不属于任何前表面的顶点的话，在对象空间执行背面剔除运算将会很有好处。我们可以对每一个顶点设置一个布尔变量，当包含某个顶点的多边形位于前表面时，就将该顶点的布尔变量值设为“true”。检查完所有多边形之后，我们就可以将任何情况下都没有被设置为“true”的顶点剔除掉。这样就可以避免对被剔除的顶点执行3-D变换，从而减少了计算量。如果我们不选择执行上述操作，那我们同样可以在世界空间中来进行背面剔除运算。在世界空间中执行剔除运算，可以避免对一些多边形进行计算量很大的裁剪计算。但是剔除运算本身的计算量将比在光栅化之前执行大一些。
　　除了在运行时计算多边形表面的法向量之外，我们还可以在程序的渲染循环之前预先计算好这些向量，并将它们与每一个多边形表面联系起来。为了在世界空间中得到法向量，我们可以应用变换将顶点变换到世界空间中。应该注意到，为了达到对一个向量的变化目的，我们只能应用变换的线性部分（也就是旋转和非归一化缩放变换）。平移变换没有必要使用，因为它对向量没有影响。将一个法向量从一个空间变换到另一个空间中的计算量往往要比直接在目标空间中建立该法向量还要大。但是，由于光线处理过程也要使用到单位法向量，这样我们就可以将两种运算目的合并起来。然而，在一个空间中建立一个单位法向量的计算量又要比从另一个空间中变换过来的计算量大的多。因此，我们还是要对法向量进行变换。
　　同样的推理最可能应用在从屏幕到世界的视处理情形中，正如我们注意到的，我们可以对这种方式进行一些修改，避免计算光线和背面多边形的交叉点。由于在这种视处理方法中，我们没有明确地把坐标变换到视空间中，它留下的只是用于可能的剔除应用的世界和对象空间。将在下一章中，我们可能会使用递归射线来追踪环境反射。由于这种光线的方向很难被提前预见，因此它们可能正好与观察者不可见的多边形相交。作为结果，在对象空间中剔除没有太多的意义。

7.2、从后到前排序
　　如我们在前一节看到的，背面剔除对多边形模型中的隐面消除来说是不够的。一般情况下，在使用从世界到屏幕方法时，要找到所有被遮挡起来的多边形部分是比较困难的。要解决这一问题，我们可以对每一个多边形相对于所有其它的多边形进行反复的裁剪，并检查得到的面片的深度信息。如果面片沿着观察方向比裁剪多边形更远的话，那么它就一定被遮挡住了，就要被剔除掉。在这一处理过程结束时，我们会得到一系列新的多边形，它们都是可见的。
　　毫无疑问，这种方法的计算量将会很大，并不一定实用。我们还有一种方法，它充分利用了图形硬件的帧缓存结构。不管场景中的多边形挡没挡住其它的多边形，我们只要按照从后向前顺序光栅化图元，就可以正确的显示所有的图元。离观察者最近的一个多边形最后进行光栅化处理。这种方法就是我们常说的画家算法。
　　我们必须注意，当多边形光栅化处理的计算量太大时，例如我们使用比较复杂的纹理映射和光线，再使用从后到前顺序就不太好了，因为许多多边形会被遮挡住，白白浪费了大量的工作。这时，使用我们前面所说的一些方法可能会比较适合。
　　为了得到从后向前的顺序，沿着观察方向按照多边形的深度信息对它们进行排序是一种比较好的方法。如果使用了透视变换，我们在视空间中就不能使用排序方法了，因为观察方法相对于不同的多边形会发生变化。观察方向只在光栅化处理阶段前才是一个常量，这时就可以使用排序方法了。
　　为了沿着观察方向进行排序，必须找到一个多边形比较的判据。最简单的方法就是比较一个多边形上所有顶点中最大z坐标（离观察者最远）。也可以比较多边形顶点z坐标的平均值。
　　还有其它许多的排序算法。最直截了当的方法复杂度为。也就是说为了产生一个排序列表，这些算法中使用的大量的基本运算都与成比例。这种算法的一个例子就是气泡排序法（bubble-sort）。在这种算法中，我们在列表中将一个物体与它前面的物体进行比较，如果不满足排序判据，就将它们的位置进行交换。如果我们从列表中的第一个物体开始对每一个物体进行比较，那么对于单个物体来说，它就会逐渐被交换到正确的位置，就像一个气泡被逐渐推到水面一样。我们将一个物体移动到正确的位置只需要进行n-1比较。(见图7.6)

图7.6 气泡排序法

　　具有平方复杂度的算法的计算量仍然是很大的。还有一类排序算法，它们的复杂度为。这类算法都使用了各种不同的细分和克服策略。例如快速排序算法（quicksort），它将一个列表分为两部分，并预先选出一个重心值，这样，列表一部分中的所有对象都比重心小，而另一部分中的所有对象都大于或等于重心。如果我们递归地进行快速排序，那么最终就会得到排序的原始列表。这种算法的复杂度大约是。(见图7.7)

图7.7 快速排序算法

　　的复杂程度已经很有效了，但我们还有一类排序算法，它们利用了这样的一个事实，那就是我们的排序总有一定的范围，这样它的复杂度就更小。例如，我们经常用32位来存储一个整型数，这也是我们能够表示一个整型数的界限。基数排序算法（Radix sort）就是这类算法中的一种，它的复杂度大约只有，但是它往往要求比较大的空间，有时又对基本操作或存储单元又不同的要求。这样，我们还是经常使用复杂度为的一些算法。
　　基数排序（Radix sort）算法基于这么一个事实，即对来自一定范围的数进行排序比较容易。例如，如果允许的排序索引表（sorting key）的范围为[0,3]，那么我们就可以按照下面的步骤来放置标有这些索引表数值的对象。计算标有每个索引表数值的元素的总的序号。这些序号定义了一些偏移量，根据偏移量每一组的元素必须放置在最终的列表中。比如说，标有1的对象必须跟在标有0的对象后面，并由此放置在最终的列表中。我们再一次遍历原始列表， 这次根据已知的偏移量将对象放置在最终的列表中。这一算法就是计数排序算法（counting sort），当排序索引的范围较小时，它是比较适合的。基数排序算法需要一个有限的但不必非常小的范围，并且它通过多次引用一个与计数算法类似的过程来进行工作， 每一次排序都按照不同的位来安排索引表数值。(见图7.8，左图用低2位进行遍历排序，右图则再用高2位排序)

图7.8 基数排序

　　从图7.8的例子可以看到，这种算法的复杂度也为，但是，它需要多次的穿越列表，这样它的执行效率就会降低。通常，快速排序算法在列表较小时执行的比较好。基数排序算法只有在列表较长，要表示的值的范围较窄时，它的优点才会显现出来。
　　我们使用上述算法的目的就为了将多边形按照从后向前的顺序放置。但是，所讨论的算法的性能依赖于要被排序的列表的混乱程度。许多级的算法在整个列表都被进行排序时工作得较好，这时，只需要很少的操作就可以完成工作。当列表比较混乱时，快速排序算法工作的较好。只有在列表比较大、数值范围比较窄时，基数排序算法才比较适用。在三维图形程序中，我们经常希望慢慢的旋转多边形物体。这时，多边形的顺序在帧与帧之间变化不大，我们使用通常看起来效率不太高的算法就可以达到很好的性能了。另一方面，如果要确保通常情况下的比较平均的性能，那么快速排序算法比较适合。
　　还应该强调，我们进行排序算法是基于这样的一个假设的，就是我们已经具有一些排序判据来将多边形按照从后向前的顺序放置。不幸的是，并不完全是这样。有时按照最大z坐标来进行比较并不正确。(见图7.9)

图7.9 最大z坐标判据实效的情况

　　在图7.9中，基于最大z坐标判据，多边形A应该首先被绘制，但是实际上它挡住了多边形B的一部分。类似的情况也会发生在使用平均z坐标判据的情况。
　　在某些情况下，我们可以容忍上述的问题。当我们保证场景中的多边形的大小都相同时，基于最大或平均z坐标的排序算法是可以接受的。例如，当我们将某种解析形状如球、或双三次面片镶嵌成多边形时，上述这种情况就会发生。这时，简单的排序通常是比较有效的。有时，我们不能保证多边形的大小完全相等，我们可以尝试使用更复杂的排序判据。如果我们可以找到一个点，它属于两个多边形的屏幕投影的交集，我们就可以进一步计算这一点的深度，并用结果作为判据来进行比较。为了定位这样一个点，我们不得不找到一个多边形的每个边与其他多边形的每个边的交集，还要检查一个多边形的屏幕投影被包含在其他多边形的屏幕投影中的情况。这样的一种方法可能在每个多边形的边较少时比较有效。当这一情况不能保证时，我们将不得不进行一定的条件放宽，并使用一些更经典的方法。例如，如果我们假设多边形是凸多边形，我们可以首先找到它们的公共切线，也就是一条将多边形的顶点都留在一侧的线（见图7.10），接下来，将会得到帆状或沙漏多边形来找到一个交点或显示不存在这种现象。(见图7.11)
　　为了找到公共切线，我们可以首先检查两个多边形的边延长线，例如可以从具有最小y坐标的顶点开始。既然在一个凸多边形中，一条边的延长线将所有的顶点都置于同一侧，这条线就可以称为一条切线。我们可以检查两个多边形的这些切线的关系。例如，在图7.10中的边d，它位于边a延长线的右侧。我们处理下面的边，得到同样的情况：属于第二个多边形的边e位于b的右侧。但是，当我们考虑相邻的边时，情况发生了变化，第一个多边形中的边c位于第二个多边形中的边f的右侧。由于有切线相互交叉，换句话说当我们从一个多边形中的方向b变化到方向c，并且从另一个多边形中的方向e到方向f时，它们的关系会发生变化，因此，存在一条公共的切线，使得两个多边形的所有顶点都位于它的同一侧，这条切线就是图中点A和D的连线。(见图7.10)

图7.10 找到两个多边形之间的桥梁

　　必须注意，切线从不相交的情况是并不是不可能的。如果我们遇到一个多边形包含在另一个多边形内的情况，那么前者的所有点都可以被用来进行深度比较。
　　一条公共切线就象一座桥一样将两个多边形联系在一起。它同样定义了一个类似帆的形状，它由两个交叉的凸多边形链组成，每一个都来自于一个多边形 。(见图7.11)

图7.11 寻找交点

　　为了找到两个链的交点， 我们可以反复减小问题的大小直到找到交点为止。我们来看一下上图中的三角形ABI和IJA。很明显，每一个都是一个ear，也就是一个不包含在任何其他凸多边形的内部的三角形。为了验证这一点，可以检查B是否在AJ上，同样，也要检查J是否在IB上。确定了ABI是一个凸状体之后，我们可以将它去除掉，并继续进行最初的子问题 — 一个BI位于顶部的帆。最后，CK成为帆当前的顶，在这一点处，D不在CL上，L也不在DK上。这就意味着，我们已经找到了CD和KL的交点，并且可以进一步使用第五章中的技术来找到两个多边形在交点处的z坐标。
　　应该注意，这两个多边形可能不会相交，这时，代替帆状多边形，我们将得到一个沙漏多边形。调整暗示的方法来找到合适发生这种情况并不困难。
　　这种方法的另一个加速的办法，就是使用约束体，并且在多边形的关系很明显时避免大量的计算。例如，如果一个多边形最小的z值比另一个多边形最大的z值还要大，那么，我们就可以确定它们的顺序了。(见图7.12)

图7.12 多边形比较的扩展

　　当z值出现重叠时，我们再使用计算量较大的比较方法。除了计算量较大之外，上述的比较多边形进行排序的方法还有它内在的问题。我们不能真正找到一个能够建立很好的顺序的判据。本质上，一个建立得很好的顺序就需要在任何的一系列的元素中都有最小的一个。(见图7.13)

图7.13 多边形比较的困难所在

　　在图7.13中，多边形A、B和C应该按照先A再B然后C的顺序排列，这是由于B挡住了A的一部分，而C又挡住了B的一部分。但是，如果在排序处理过程中，我们要对A和C进行比较，那我们就不能这么说了。这些多边形具有相同的最大和平均z坐标值，它们在屏幕上的投影也并不相交。我们将尝试着认为它们“相等”，并且对我们来说，应该按照什么顺序进行渲染并不重要。但这并不是真的：多边形B确实在A和C之间， 并且它们的顺序也是很重要的。这种情况在有多重交叠存在是将更加严重(见图7.14)。这些多边形中没有一个明确的最小者。

图7.14 多边形的多重交叠

　　在这个例子中，A<C并且C<B，但同时又有B<A。
　　我们可以看到，当一个多边形穿刺过其他多边形时，排序方法就不能进行处理了，还有其他一些情况，例如多
重交叠等。但是，这种方法在一定的限制内还是有用的。

7.3、顺序列表和八叉树
　　我们在前一节已经看到，一般多边形模型的隐面消除代价极其昂贵。然而，在大多数情形中，我们要处理的对象有一些特殊的属性，利用这些属性可以减轻隐面消除工作量。举例来说，在以高度场（Height-field）进行表度的地形处理的情形中，我们可以很容易地获得多边形从前到后的顺序。这是由于这种表度方法具有的矩形自然本性，据此，地形可以被分割为正方形的单元格。
　　让我们考虑一种情况，观察者在一些单元边界内位于虚拟地形表面上或表面的上方。我们能够把整个的地形分割为四个规则的子地形，如图7.15所示。

图 7.15 高度场遍历（Height-field traversal）

　　由于这种表达方法的规律性，这四个子地形在观察者屏幕上的投影几乎没有交叉。少数由于透视变换可能出现的交叉点可通过按从小到大渲染子地形很容易地得到修复。
　　在每个分割域内，我们通过从最远的多边形开始能够得到多边形从后到前的顺序，一行一行或一列一列地朝向观察者所在的单元进行处理。包含观察者所在的单元的多边形最后进行光栅处理。举例来说，在图7.15中的地形单元光栅处理顺序如下：

　　首先： 1,2,3,4;
　　其次： 5,6,7,8,9,10;
　　再次： 11,12,13,14,15,16;
　　然后： 17,18,19,20,21,22,23,24,25;

　　这种遍历有效地保证了在任意投影中的可见性。然而，每个单元，正如我们在前一章所看到的，可能由两个三角形组成。光栅处理的顺序将依据看向场景的角度而不同。（参见图7.16）

图7.16 在高度场单元中的三角形顺序

　　从图7.16中，很清楚，当观察方向在范围45°～225°的时候，多边形B在A之后被渲染，否则，当观察方向不同的时候，我们以相反的顺序渲染多边形：A在B之后。在正好是45°或者225°的时候， 渲染的顺序无所谓，因为多边形的投影在屏幕上没有交叉。
　　极为类似的规律特性也用于寻找体素从后到前的顺序，这使用八叉树存储，或者也用于空间占用的矩形表达方式，这两点在前一章中我们都已经看过了。在这两种情形中，我们能够使用同讨论过的高度场非常类似的方法，扩展为处理三维而不是两维。
　　八叉树是递归结构，在每个细分的层次上有着同样规则的属性。因此，在每个层次上可以应用同样的遍历顺序，以获得整个结构元素从后到前的顺序。
　　四叉树是八叉树在一个平面上的特例。为了简化的缘故，让我们考虑一下如图7.17遍历一个四叉树。取决于观察的方位，共有四种不同的遍历顺序，每种用于方位的特定范围。（参见图7.17）

图7.17 四叉树遍历的四种顺序

　　如图7.17所示，为了遍历任意子树，我们使用相同的顺序，轮到它的时候，可能会导致在很低的细分层次上遍历，但即便如此，我们仍然在高层次上对其使用同样的顺序。
　　非常类似的策略可以用在八叉树的情形中。通过把上面的方法扩展到三维，我们将有8个不同的遍历顺序，每个应用于方位角度的特定范围。

7.4、入口(Portals)
　　如何处理可见性的另一个例子是，在一种特别的情形下，模型在室内场景中演示。考虑到域的集合 — 房间，通过入口（门、窗等）连接。在这种简化的例子中，房间是凸多面体，这通过背面剔除就可以正确地绘制出可见物体。
　　在图7.18中，观察者位于房间A。显然，组成房间A的多边形是可见的。为了正确地绘制入口在屏幕上的投影，房间入口导向的地方必须被绘制；为了正确地绘制其他房间可见部分，组成该处的多边形和入口同样也要被绘制。

图7.18 室内空间布局

　　恰到好处地描述上面这种策略的语言使人想起递归。让我们考虑一下观察者所处的房间的相邻房间。我们能够构建一个图表，其中的节点代表房间，线条代表入口。（参见图7.19）

图7.19 室内域图表

　　首先绘制房间中入口导向的多边形，然后绘制当前房间中确保可见性正确的所有多边形。这个转化到图表（房间）的递归上，首先对连接到当前节点的节点应用递归，然后对当前节点本身应用可见性处理算法。
　　必须注意到，在任意图表递归中，对这种算法来说，应该小心地注意不要发生可能的循环。如果算法应用到某个节点上，则不应在对该节点重复应用第二次。在图7.19这个特别的例子中，工作过程如下：我们从顶点A开始，接下来是顶点B，在经过顶点C到达顶点D。在这个过程中，我们不会跑到别的地方去，因为B已经被用过了。既然再没地方可去，同D联系在一起的房间被绘制；我们再返回C，从这里第一次到达E，绘制其多边形，返回并绘制C房间的所有多边形。在该点上，我们返回B，绘制它并最终返回并绘制A房间。

图7.20 带有入口的内部场景

　　这种方案可得到成倍的改良。显然，图表可能极大，而实际上遍历到某个深度就停止比较有意义，举例来说，当遍历到远离当前所在房间三到四个房间的时候就停止。比这些房间还要深的房间用不着被看到。
　　除了我们所在的房间外，也有可能通过入口看到所有的房间，入口在屏幕上投影之外的不可能被看到。因此，当绘制我们通过门看到的房间的时候，我们实际上沿着入口屏幕投影裁剪多边形，极大地减轻了过负荷的问题。然而，既然入口的投影是任意导向的多边形，这类裁剪可能是非常昂贵的。我们通过沿着矩形约束裁剪来解决这个问题，矩形约束是入口屏幕投影的扩展。尽管仍然要出现某些透支现象，沿着矩形裁剪要比沿着任意多边形裁剪快得多。特别在纹理映射多边形伴随着复杂的光线模式的情形下，从此改进中我们将节省相当大的开销。应该注意到，如果我们沿着入口边界应用裁剪，必须改变房间遍历算法，这样在通过不同的入口到达同一个房间的时候，我们能够多次绘制它。
　　进一步，我们将要看到某个通用的方法，在我们用到后面提到的beam树的时候，利用它来减轻开销。

7.5、二叉空间分割（BSP）树
　　BSP （Binary Space Partition）表示二叉空间分割。使用这种方法可以使我们在运行时使用一个预先计算好的树来得到多边形从后向前的列表，它的复杂度为。它是由Fuch和Kedem在1980年首先提出的。它的基本思想是基于这样一个事实，任何平面都可以将空间分割成两个半空间。所有位于这个平面的一侧的点定义了一个半空间，位于另一侧的点定义了另一个半空间。此外，如果我们在任何半空间中有一个平面，它会进一步将此半空间分割为更小的两个子空间。我们可以使用多边形列表将这一过程一直进行下去，将子空间分割得越来越小，直到构造成一个二叉树。在这个树中，一个进行分割的多边形被存储在树的节点，所有位于子空间中的多边形都在相应的子树上。当然，这一规则使用于树中每一个节点。
　　我们来看一下图7.21种的多边形。为了简单起见，我们选择一个这样一个平面投影，在它上面，所有多边形都能映射为直线段。让我们由多边形B开始构造一个BSP树。(见图7.21)

图7.21 一个二叉空间分割

　　多边形B所在的平面将空间分割为两个部分，使得多边形D和E位于同一个半空间中，多边形C在另一个半空间中。在这个例子中， 多边形A穿越了两个半空间，这样，它就不能十分明确的被分配到任何一个半空间中。但是，如果我们将这个多边形从它与分割平面相交的地方分为两个部分一个命名为，另一个命名为，这样，就和D、E在同一个半空间中，和C在同一个半空间中。下图表述了这一过程。

图7.22 建立BSP树的一个阶段

　　我们现在已经将问题分成了两个子问题。我们可以在子树中再次使用上述算法。例如，我们在左边子树中选择E作为分割多边形，在右边子树中选择作为分割多边形。这样，我们将建立下面的结构树。(见图7.23)

图7.23 建立BSP树

　　必须注意，任何给定的BSP树都不是唯一的。我们可以对同样的多边形找到多个有效的二叉分割。依靠我们选择来进行分割的多边形的顺序，可以得到不同的树。例如，在图7.24中，我们可以看到另一个树，它也建立在前面我们讨论的多边形上。

图7.24 另一种结构

　　尽管所有适合这种算法的正确的树都可以用来得到多边形从后向前的顺序，但是总有一些要比其他一些更加有效。我们首先检查树遍历算法，然后检查确认特殊树结构的原因。
　　我们考虑一个包含了一系列多边形的场景， 场景带有一个预先计算好的BSP树和一个位于场景中某个位置的观察者。(见图7.25)

图7.25 用BSP树来得到从后向前的顺序

　　我们检查观察者的位置和位于树顶部的多边形之间的关系。很明显，当这个多边形将空间分割为两个部分时，观察者必须位于其中的一个半空间中。当然，位于同一半空间中的多边形要比另一半空间中的多边形离观察者更近。基于这样的事实，如果我们首先将较远处半空间中的多边形放置在最终的列表中，然后放置根多边形，再放置与观察者在同一半空间中的多边形，这样就很容易得到多边形从后向前的顺序了。我们对每一个子树都重复同样的过程，在每一个级别中选择相应的顺序，最终，就会得到正确的多边型的顺序。
　　这一算法的一个优点就是无论观察者位于场景中的什么位置，无论观察者的朝向如何，它都可以很好的进行工作。例如，在图7.25 (a)中产生的列表就与(b)中产生的不同。但是他们对于各自的情况都是正确的。这样，如果我们预先为一个多边形模型计算一个BSP树，那么在运行时，我们只需要根据观察者的位置调用这个树，执行树遍历过程，就可以产生用于隐面消除的画家算法所需的从后向前的多边形顺序。
　　在这个算法中，在树的每一个节点处所作的判定，都依赖于观察者位于该节点多边形所产生的哪一个半空间中。在第五章中，分析平面方程式时我们已经遇到过要使用这种计算的情况。利用我们所讨论过的事实，我们可以看到，如果将观察者位置的坐标代入给定多边形的平面方程式中，结果数值的符号如果是正号，就表示观察者位于该多边形的法向量所指向的半空间中，负号表示位于另一个半空间中， 0值表示他位于这个多边形所在的平面上。最后一种情况，对于遍历整个BSP树的意图来说，意味着半空间在屏幕上的投影不相交， 并且我们可以在这一阶段的遍历过程中选择任何子树的顺序。
　　相同的计算也要在预先计算一个BSP树时使用到。我们需要决定不同的多边形应该被放置在哪个子树中。从可实现性的观点出发，预先计算一个BSP树的过程可以被描述成下面的形式：对多边形集合，我们选择一个多边形。进一步计算该多边形的平面方程式。对剩余的多边形，我们用所说的方程式检查它们的所有顶点。如果所有顶点都是负值，那么多边形就放置在一个子树中；如果都是正值，那么多边形就放置在另一个子树中；如果结果有正有负，那么多边形就被分为两部分，分别放置在两个子树中。一旦我们将所有多边形分配到了正确的半空间中，我们就可以对子树进一步调用同样的方法来进行处理，直到当前的子表只包含一个多边形为止。
　　一个多边形被任何平面所分割的问题可以当作一个裁剪问题来处理。解决这一问题的算法只与我们在裁剪问题时所讨论的算法又很小的差别。唯一明显的差别就是在二进制搜索边缘裁剪过程中，我们将使用分割多边形的平面方程式来找到边的中点的位置。

图7.26 使用BSP树渲染的一个场景，左边是不同的多边形

　　对于垂直边的裁剪情况，我们使用二分搜索技术，根据边的中点的位置抛除掉边的一部分。既然这样，我们可以使用类似的方法来进行处理，区别只是改变一下判据。我们可以将同样的方法用于多边形的裁剪。
　　应该强调的是，由于一个BSP树的结构是预先确定的，因此我们不必担心建立树时算法的效率问题。
　　一旦创建了树，要得到多边形从后向前的顺序，就要采取下面的步骤：我们取位于树顶的一个多边形。计算这个多边形的平边方程式。将观察者当前的位置坐标代入方程式中，观察结果的正负号。接着对子树运用相同的方法
进行处理。
　　我们回忆一下平面方程式的形式：


　　式中，P表示平面中的点，时平面的法向量。它还可以表示成下面的形式：


　　后一种形式是通过对原始形式进行标量相乘得到的，使得、、、。当我们在视空间中遍历整个树时，观察者的位置为(0,0,0)，我们提到的代换结果等于平面方程式中的系数D。这样，BSP树遍历可以很方便的在透视变换之前来进行。
　　表7.1显示了一个树遍历的结构。

表7.1 遍历一个BSP树

　　我们考查了树的创建和遍历之后，仍然有一些问题需要解决。当我们构建一个树时，我们可以选择剩余多边形中的任何一个来分割空间。选择不同的多边形会导致不同的树的结构。因此，我们就应该考虑选择哪个多边形有助于算法的效率。
　　有些多边形会导致剩余多边形更多的分割(见图7.21、7.23和7.24)。每一个多边形在通过渲染管道时都有一定的系统消耗，因此多边形越少，性能就越好。我们可以利用判据来选择有较少分割的多边形。
　　使用判据来平衡BSP树，并不需要每一级中的子树中的多边形的数量都相同， 因为它不会影响运行时间。树的遍历总是假设至少每次都取一个多边形，因此平衡不会影响性能——我们仍然不得不每次取每一个多边形。另一方面，一个平衡的树可以以较少的迭代调用来执行遍历。我们可以将平衡作为第二判据来使用。
　　总之，使用BSP树来进行从后向前排序的最大优点就是算法运行的复杂性较低 。这种方法也解决了多边形的多重交叠和多边形穿越问题。但是，通过使用一个预计算结构，我们已经失去了一定的灵活性。如果多边形的排列在运行时发生了改变， BSP树就必须发生相应的改变。由于计算量非常巨大，我们不能这样做，因此，这种算法对于场景在运行时发生改变的情况就不能使用了。
　　应该注意，只有当多边形经历不同的变换设置时树才会受到影响。如果所有的多边形都使用同样的变换，那么分割仍然是正确的，树也将不会受到影响。这样，场景中的一个动态物体，它在世界中移动或者是旋转，仍然可以使用同样的BSP树。如果物体中的一部分相对于其他物体发生了移动，那我们就要使用其它的算法了。

7.6、Beam树
　　尽管使用前一节提及的BSP树能够有效地创建可用于画家隐面消除算法的多边形从后到前的顺序，但它仍然有某些缺点。当我们要绘制纹理或明暗处理多边形的时候，存在着画家算法的基本问题 — 透支，其开销很大，不能够忽视。早先也注意到，在沿着所有其它的多边形执行裁剪的时候，看起来也是个低效率的解决方案，实际上，分析并抛弃遮住的部分可能对继续下去更有吸引力，因为它避免了透支。非常有趣的是，BSP树可能同样对后者有极大的帮助。我们即将讨论的Beam树方法，可以同BSP树一同用于这两个方面：对多边形的排序和追踪屏幕上哪个区域被绘制。
　　在前一节中，我们已经讨论了使我们能够使用BSP树获得多边形从后到前的顺序的算法。也可以用同样的方式获得从前到后的顺序，只需逆转BSP遍历算法中的调用顺序。因此，更靠近观察者的半空间将首先被遍历，然后是根多边形和较远的半空间遍历，产生需要的从前到后的顺序。
　　获得的顺序中，第一个多边形最靠近观察者。既然没什么东西能遮挡它，这个多边形完整地在屏幕上可见，由此被光栅处理。所有其它的多边形可能完全或部分被第一个遮挡。如果我们沿着第一个多边形的边界裁剪剩余多边形在屏幕上的投影，并抛除被遮挡的部分，我们实际上把原始问题的大小减小了一个。在列表开头的新多边形也是能被完整地看到的（因为它已经被沿着原来第一个多边形裁剪过了），而且，剩下的多边形如前面一样可能完全或部分被顺序列表中新的第一个多边形遮挡。
　　必须承认，我们必须做大量的裁剪，这相当大地恶化了这种算法。为了更有效地管理裁剪，引入了平面BSP树，用来追踪屏幕上哪个区域剩了下来可用于绘制。不象在前面考虑的树， 在这个BSP树中附加的叶节点将描述最终的凸多边形区域，其结果形成了细分区域，且没有相关联的多边形。该区域被标记为占用或空。由于2D屏幕边界裁剪的基本目的基本是一样的 — 寻找可被光栅处理的图元部分，这两个处理过程实际上是统一的。因此我们从描述屏幕区域为空（可绘制）的BSP树开始，相对应的，在屏幕外的空间被标记为占用。图7.27演示了初始化的BSP树和导致的分割部分。

图7.27 用于空屏幕的Beam树

　　当一个多边形必须被绘制的时候，它向下过滤BSP树。在某些节点可能被分割， 这样该部分可以在正确的子树内被明确地检查。当某一块到达树叶，且该叶被标记为占用，我们就知道了这个多边形实际上被遮挡可以被抛除。另一方面，当多边形某块到达标记为空的叶时，该块被光栅处理，由于多边形所在的区域现在被占用了，必须更新BSP树来反映这一点。
　　考虑图7.28中的例子。在这个例子中， 要绘制包含E、G、H边的多边形。首先沿着追踪当前屏幕上可见区域的BSP树根检验。在BSP树根，A边分割了指定的多边形。A左侧的较小部分要沿着左侧子树检验，剩余部分沿着右侧子树检验。在前者的情形下，该小块到达被占用的节点，因此被抛弃。对后者来说，多边形沿着B边检验，被上边分割的要被抛弃。低处的部分进一步到描述屏幕矩形的节点进行检验（参见图7.27，标记为F的节点）。在该点上，我们能够安全地光栅处理多边形剩余的部分，并更新树，使用多边形边进行进一步的分割，同时标记多边形区域为占用，剩下的标记为空。显然，当多边形小块到达叶节点的时候，该块整个在叶描述的区域内。因此，任何必要的树的替换方案都位于子树的这个区域，并以该叶作为根节点。(参见图 7.28)

图7.28 在多边形被绘制之后的Beam树

　　在屏幕平面创建的BSP树追踪没有被遮挡的视线（beam of view），这也是它的名称的由来。总的来说，在这种算法中，我们从前到后地拾取多边形，一次只拾取一个，并在BSP树中向下进行过滤，同时关联着屏幕。当多边形的一部分或多个部分被光栅处理的时候，树就被更新，以追踪剩余的自由空间，这样，每个连续的多边性能一致的被检验。这样，透支问题被极大地避免了，尽管如此，这种算法的裁剪数量较大以及实现起来要更复杂。
　　我们在下一章中讨论到阴影产生的时候，还要遇到一个使用BSP树的例子。显然，这个和其他的分割方案在解决计算机图形处理的许多问题的时候具有极大的重要性。

7.7、扫描线算法
　　在第六章中我们已经讨论过多边形模型的另一种表度方式，其中的多边形以边的形式来描述而不是用顶点的形式。这类表度方式能避免多余的裁剪且对隐面消除来说也相当地实用，在这一节中，我们对这种方法作一下分析。扫描线隐面消除的思路是把可见性确定从多边形层次转变到单个的多边形像素线（参见图7.29）。这种算法可以被认为是通用多边形光栅处理的扩展，这种方法我们曾与凹多边形一起讨论过。我们应该看到，这两种算法的许多思想是一致的。

图7.29 在每条扫描线上确定隐藏面

　　在这种算法中，场景中的所有多边形同时被光栅处理，可见性判定在平面内执行，该平面与当前屏幕上的扫描线正交，我们将要在屏幕上判定交叉的多边形的关系。图7.30演示了一个例子，三个多边形被使用这种算法进行光栅处理。能够看出，多边形中与扫描线相交的边的顺序的信息对这个算法来说是最至关紧要的。我们能够在每条扫描线上使用与对凹多边形光栅处理应用该算法时相同的方法得到这样的边顺序。有了这个顺序后，可见性的判定可以通过相当直截了当的方式完成，假定我们也有多边形平面方程。让我们分析一下在图7.30中的扫描线1。

图7.30 不同扫描线上的活动边

　　在图7.30中的扫描线1只与多边形ABC相交，因此，我们在这些边中光栅化该多边形。扫描线2交叉了两个多边形， 但交叉边的顺序是这样的：在遇到多边形DEF之前我们结束了多边形ABC的光栅处理。此情形对扫描线3来说不是这样的。我们开始渲染多边形ABC，在结束之前，遇到了属于多边形EDF的边DE。在此阶段，我们必须在该点上比较这两个多边形的深度以判定可见性。如果在此位置对两个多边形求平面方程的值，就可以完成判定。在这个特别的情形下，多边形DEF的深度较小，因此我们先渲染它。当我们进一步遇到AC边的时候，我们可以忽略它，因为多边形DEF的光栅处理还没有结束，且AC边属于早就被判定为较远的多边形。
　　在某种意义上，每条边在端点间定义了一个范围，在其中的被光栅处理。如果在某些点上多边形被遮挡，我们仍然必须稍后对其进行光栅处理。这种情形就是扫描线4所演示的（参见图7.30）。因此，在交叉DF边之后，我们必须分析多边形ABC和IJK的深度，在此情形中，光栅处理多边形ABC。当我们越过AC边的时候，我们仍然在一个多边形的范围内，对此多边形仍然要进行处理。
　　正如我们看到的，这种分割算法相当容易被实现。我们也取决于这么一个事实，即在每条扫描线上，我们都有多边形的排序。如我们所讨论的，这种顺序可以通过以最小垂直顶点坐标预排序所有的多边形来获得，在两条边相同的情形中，使用第二个评判标准，比较具有最大垂直坐标的端点的水平坐标。有了这个顺序后，我们能够以增量方式为每条扫描线更新当前边。一旦我们找到了当前边，也必须根据当前水平坐标排列。
　　必须强调的是这种算法的优点在于它能够忽略被遮挡的扫描线的光栅处理。正如我们看到的，如果在场景中使用了复杂的纹理映射或照明的时候，这变得极其重要。这种算法也正确地处理了多边形相互重叠的情形，但是在形式不变的时候，它不能处理多边形穿越的情形。使用这种算法也暗示了对已存在的多边形管道的修改，因为全部多边形同时被光栅处理有时候并不合算。

7.8、Z-Buffer算法
　　迄今为止的大多数算法都有一个很大的限制，它们处理的对象都模拟为多边形集。有时候这不是问题。我们光栅处理的内容可能表示为其它各种各样的图元形式。即便是在多边形模型的情形中，当多边形数量增加的时候，大多数隐面消除方法的性能出现了不成比例的退化。
　　在本节我们要考虑的算法适合以任何一种方法光栅化任何一种图元，并且在本质上其工作时间是线性的，这就是说，复杂性与场景中的图元数量成比例。
　　Z-buffer算法的思路是，它把寻找哪些是可见的，哪些是被遮挡的处理过程从图元层次或扫描线层次上进一步转变到了单个的像素层次上。换句话说，每次我们要判定某些图元的一个像素在图元光栅处理前是否应该被绘制时， 我们把该像素的颜色同z（深度）坐标存储在一起。如果某个属于另一个甚至是同一个图元的像素必须被绘制在同一个位置上，必须比较z值，且如果新像素实际上更靠近观察者，则它将替代前面被绘制上的像素。如果新像素被判定距离更远，我们在该位置上保留原先的像素。图7.31演示了两个被光栅化的图元位置，使用Z-buffer算法用于隐面消除。

图7.31 使用Z-buffer隐面消除的光栅处理

　　从图7.31中，我们能够看出，每个屏幕像素，除了一些图像位图的存储单元之外，还必须分配空间存储z值。所有z值的数组被存在“Z-buffer”中。
　　在帧渲染的开始，我们必须在Z-buffer中以选定的精度用最远的z值初始化所有的位置。作为结果，在任意位置获得的第一个像素将有必要通过算法逻辑的比较允许其被绘制。
　　在多边形情形中，z坐标的判定可以通过线性插值来完成。我们使用与光栅化明暗强度相同的算法来判定，该方法在光栅处理中内插明暗以及在线性纹理映射中内插纹理坐标。因此，我们将在保留每个像素上的z直到光栅处理阶段，沿着边内插它然后沿着扫描线在边上使用该值。
　　必须注意到，如果我们应用了透视投影变换，在可用空间中的z坐标不是线性地变化的。比较有吸引力的是使用来代替深度标准，在这样的空间中是线性变化的。

图7.32 使用Z-buffer算法处理对象的交叉

　　在Z-buffer算法的众多优点中，可能它的简单性是最大的一个优点。由于这种简单性，它成为了最可能通过硬件实现的算法。它的通用性和本质上的线性运行时间使它对最高级的应用充满了吸引力。Z-buffer算法的问题可能来自这么一个事实，即我们只有极为有限的位数来表度屏幕上像素的z坐标。在某些场合下，我们对z值可能的舍入或截尾引起了对像素的人为干扰，位数的减少可能引起可见性的错误判定。当然，对实现来说，我们必须在光栅处理例程内循环中加入一定数量的代码。这也导致了某些性能上的恶化，使这种算法对有中等数量图元的应用没什么吸引力。我们必须也要注意到，Z-buffer数组也是相当大的，虽然随着时间的推移，内存的限制越来越小，但对某些应用来说，用初始值填充Z-buffer可能导致相当可观的花费。这个算法也很容易受到透支问题的困扰，因为被遮挡的图元仍然必须被光栅处理。

　　小结
　　总的说来，当我们将图元从世界投影到屏幕上而获得虚拟世界的图像的时候，隐藏面带来的问题就会出现在从世界到屏幕的视处理过程中。一些图元可能会遮挡住屏幕投影中的其他图元，这样我们就需要一些方法来将隐藏面去除掉。对于我们已经讨论过的几种消除隐藏面的方法，许多都只能应用于使用多边形表示的模型。一种比较普通的方法就是按照从后向前的顺序对多边形进行光栅化处理，使得靠近观察者的多边形能够覆盖掉远离的观察者的多边形。我们有很多方法来将多边形按照从后向前的顺序进行排列。具体的算法包括排序、空间分割等。但是，这种方法在执行光栅化处理的时候系统开销会很大，因为它要光栅化所有的多边形，包括被遮挡住的。这时，我们就要考虑采取其它一些看起来效率低下的方法，例如使用Beam树对多边形进行反复的裁剪，以避免对不必要的多边形进行光栅化。
　　Z-buffer方法对图元的形状没有任何的要求，并且它也是最简单的隐面消除算法，还经常通过硬件来执行。这种算法同样要我们对无用的多边形进行处理。扫描线隐面消除算法使我们避免了这种情况，但是它只适用于多边形模型，同时还要求对多边形管道进行相当大的改变。
　　隐面消除算法的运行时间是很难进行比较的，因为它们都有一个基本的不同复杂性的步骤。这样，具有线性运行时间的算法执行起来可能比具有指数性运行时间的算法执行起来更糟糕。前一种形式的优点通常只在多边形的数量非常巨大的时候才能显现出来。只有基于一些特殊的情况和对条件进行适当的放宽，才能够确定选择哪一种策略。