目 录
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.2)
 |
| 图7.2 凸多面体与凹多面体 |
如果我们对一个多边形模型执行背面剔除，并且这个模型是一个凸多面体，那么经过这样的处理之后，我们就已经消除了所有的隐藏表面。由于这些模型的形状，所有隐藏的多边形就是组成背面的多边形。但是，在消除凹多面体的隐藏面时，这一通用的技术就会出现一些问题。有可能某些对象的正面被其他多边形中同样是正面的面遮挡(见图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
