3D图形编程指南 8续- 隐面消除

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3>
<TABLE cellSpacing=0 cellPadding=0 width="100%" bgColor=#ffffff border=0>

<TR>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image736.gif"></TD></TR></TABLE></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图 7.15 高度场遍历（Height-field traversal）</B></FONT></TD></TR></TABLE>
　　由于这种表达方法的规律性，这四个子地形在观察者屏幕上的投影几乎没有交叉。少数由于透视变换可能出现的交叉点可通过按从小到大渲染子地形很容易地得到修复。
　　在每个分割域内，我们通过从最远的多边形开始能够得到多边形从后到前的顺序，一行一行或一列一列地朝向观察者所在的单元进行处理。包含观察者所在的单元的多边形最后进行光栅处理。举例来说，在图7.15中的地形单元光栅处理顺序如下：

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

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image738.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.17 四叉树遍历的四种顺序</B></FONT></TD></TR></TABLE>
　　如图7.17所示，为了遍历任意子树，我们使用相同的顺序，轮到它的时候，可能会导致在很低的细分层次上遍历，但即便如此，我们仍然在高层次上对其使用同样的顺序。
　　非常类似的策略可以用在八叉树的情形中。通过把上面的方法扩展到三维，我们将有8个不同的遍历顺序，每个应用于方位角度的特定范围。

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image739.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.18 室内空间布局</B></FONT></TD></TR></TABLE>
　　恰到好处地描述上面这种策略的语言使人想起递归。让我们考虑一下观察者所处的房间的相邻房间。我们能够构建一个图表，其中的节点代表房间，线条代表入口。（参见图7.19）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image740.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.19 室内域图表</B></FONT></TD></TR></TABLE>
　　首先绘制房间中入口导向的多边形，然后绘制当前房间中确保可见性正确的所有多边形。这个转化到图表（房间）的递归上，首先对连接到当前节点的节点应用递归，然后对当前节点本身应用可见性处理算法。
　　必须注意到，在任意图表递归中，对这种算法来说，应该小心地注意不要发生可能的循环。如果算法应用到某个节点上，则不应在对该节点重复应用第二次。在图7.19这个特别的例子中，工作过程如下：我们从顶点A开始，接下来是顶点B，在经过顶点C到达顶点D。在这个过程中，我们不会跑到别的地方去，因为B已经被用过了。既然再没地方可去，同D联系在一起的房间被绘制；我们再返回C，从这里第一次到达E，绘制其多边形，返回并绘制C房间的所有多边形。在该点上，我们返回B，绘制它并最终返回并绘制A房间。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image743.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.21 一个二叉空间分割</B></FONT></TD></TR></TABLE>
　　多边形B所在的平面将空间分割为两个部分，使得多边形D和E位于同一个半空间中，多边形C在另一个半空间中。在这个例子中， 多边形A穿越了两个半空间，这样，它就不能十分明确的被分配到任何一个半空间中。但是，如果我们将这个多边形从它与分割平面相交的地方分为两个部分一个命名为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image744.gif">，另一个命名为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image745.gif">，这样，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image744.gif">就和D、E在同一个半空间中，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image745.gif">和C在同一个半空间中。下图表述了这一过程。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image746.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.22 建立BSP树的一个阶段</B></FONT></TD></TR></TABLE>
　　我们现在已经将问题分成了两个子问题。我们可以在子树中再次使用上述算法。例如，我们在左边子树中选择E作为分割多边形，在右边子树中选择<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image747.gif">作为分割多边形。这样，我们将建立下面的结构树。(见图7.23)


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image748.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.23 建立BSP树</B></FONT></TD></TR></TABLE>
　　必须注意，任何给定的BSP树都不是唯一的。我们可以对同样的多边形找到多个有效的二叉分割。依靠我们选择来进行分割的多边形的顺序，可以得到不同的树。例如，在图7.24中，我们可以看到另一个树，它也建立在前面我们讨论的多边形上。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image749.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.24 另一种结构</B></FONT></TD></TR></TABLE>
　　尽管所有适合这种算法的正确的树都可以用来得到多边形从后向前的顺序，但是总有一些要比其他一些更加有效。我们首先检查树遍历算法，然后检查确认特殊树结构的原因。
　　我们考虑一个包含了一系列多边形的场景， 场景带有一个预先计算好的BSP树和一个位于场景中某个位置的观察者。(见图7.25)


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image751.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.26 使用BSP树渲染的一个场景，左边是不同的多边形</B></FONT></TD></TR></TABLE>
　　对于垂直边的裁剪情况，我们使用二分搜索技术，根据边的中点的位置抛除掉边的一部分。既然这样，我们可以使用类似的方法来进行处理，区别只是改变一下判据。我们可以将同样的方法用于多边形的裁剪。
　　应该强调的是，由于一个BSP树的结构是预先确定的，因此我们不必担心建立树时算法的效率问题。
　　一旦创建了树，要得到多边形从后向前的顺序，就要采取下面的步骤：我们取位于树顶的一个多边形。计算这个多边形的平边方程式。将观察者当前的位置坐标代入方程式中，观察结果的正负号。接着对子树运用相同的方法
进行处理。
　　我们回忆一下平面方程式的形式：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image752.gif"></TD></TR></TABLE>
　　式中，<I>P</I>表示平面中的点，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image753.gif">时平面的法向量。它还可以表示成下面的形式：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image754.gif"></TD></TR></TABLE>
　　后一种形式是通过对原始形式进行标量相乘得到的，使得<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image755.gif">、<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image756.gif">、<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image757.gif">、<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image758.gif">。当我们在视空间中遍历整个树时，观察者的位置为<I>(0,0,0)</I>，我们提到的代换结果等于平面方程式中的系数<I>D</I>。这样，BSP树遍历可以很方便的在透视变换之前来进行。
　　表7.1显示了一个树遍历的结构。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

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