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

<b>7.6、Beam树
</b>　　尽管使用前一节提及的BSP树能够有效地创建可用于画家隐面消除算法的多边形从后到前的顺序，但它仍然有某些缺点。当我们要绘制纹理或明暗处理多边形的时候，存在着画家算法的基本问题 — 透支，其开销很大，不能够忽视。早先也注意到，在沿着所有其它的多边形执行裁剪的时候，看起来也是个低效率的解决方案，实际上，分析并抛弃遮住的部分可能对继续下去更有吸引力，因为它避免了透支。非常有趣的是，BSP树可能同样对后者有极大的帮助。我们即将讨论的Beam树方法，可以同BSP树一同用于这两个方面：对多边形的排序和追踪屏幕上哪个区域被绘制。
　　在前一节中，我们已经讨论了使我们能够使用BSP树获得多边形从后到前的顺序的算法。也可以用同样的方式获得从前到后的顺序，只需逆转BSP遍历算法中的调用顺序。因此，更靠近观察者的半空间将首先被遍历，然后是根多边形和较远的半空间遍历，产生需要的从前到后的顺序。
　　获得的顺序中，第一个多边形最靠近观察者。既然没什么东西能遮挡它，这个多边形完整地在屏幕上可见，由此被光栅处理。所有其它的多边形可能完全或部分被第一个遮挡。如果我们沿着第一个多边形的边界裁剪剩余多边形在屏幕上的投影，并抛除被遮挡的部分，我们实际上把原始问题的大小减小了一个。在列表开头的新多边形也是能被完整地看到的（因为它已经被沿着原来第一个多边形裁剪过了），而且，剩下的多边形如前面一样可能完全或部分被顺序列表中新的第一个多边形遮挡。
　　必须承认，我们必须做大量的裁剪，这相当大地恶化了这种算法。为了更有效地管理裁剪，引入了平面BSP树，用来追踪屏幕上哪个区域剩了下来可用于绘制。不象在前面考虑的树， 在这个BSP树中附加的叶节点将描述最终的凸多边形区域，其结果形成了细分区域，且没有相关联的多边形。该区域被标记为占用或空。由于2D屏幕边界裁剪的基本目的基本是一样的 — 寻找可被光栅处理的图元部分，这两个处理过程实际上是统一的。因此我们从描述屏幕区域为空（可绘制）的BSP树开始，相对应的，在屏幕外的空间被标记为占用。图7.27演示了初始化的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/Image760.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.27 用于空屏幕的Beam树</B></FONT></TD></TR></TABLE>
　　当一个多边形必须被绘制的时候，它向下过滤BSP树。在某些节点可能被分割， 这样该部分可以在正确的子树内被明确地检查。当某一块到达树叶，且该叶被标记为占用，我们就知道了这个多边形实际上被遮挡可以被抛除。另一方面，当多边形某块到达标记为空的叶时，该块被光栅处理，由于多边形所在的区域现在被占用了，必须更新BSP树来反映这一点。
　　考虑图7.28中的例子。在这个例子中， 要绘制包含E、G、H边的多边形。首先沿着追踪当前屏幕上可见区域的BSP树根检验。在BSP树根，A边分割了指定的多边形。A左侧的较小部分要沿着左侧子树检验，剩余部分沿着右侧子树检验。在前者的情形下，该小块到达被占用的节点，因此被抛弃。对后者来说，多边形沿着B边检验，被上边分割的要被抛弃。低处的部分进一步到描述屏幕矩形的节点进行检验（参见图7.27，标记为F的节点）。在该点上，我们能够安全地光栅处理多边形剩余的部分，并更新树，使用多边形边进行进一步的分割，同时标记多边形区域为占用，剩下的标记为空。显然，当多边形小块到达叶节点的时候，该块整个在叶描述的区域内。因此，任何必要的树的替换方案都位于子树的这个区域，并以该叶作为根节点。(参见图 7.28)


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

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


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

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


<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/Image764.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图7.31 使用Z-buffer隐面消除的光栅处理</B></FONT></TD></TR></TABLE>
　　从图7.31中，我们能够看出，每个屏幕像素，除了一些图像位图的存储单元之外，还必须分配空间存储z值。所有z值的数组被存在“Z-buffer”中。
　　在帧渲染的开始，我们必须在Z-buffer中以选定的精度用最远的z值初始化所有的位置。作为结果，在任意位置获得的第一个像素将有必要通过算法逻辑的比较允许其被绘制。
　　在多边形情形中，z坐标的判定可以通过线性插值来完成。我们使用与光栅化明暗强度相同的算法来判定，该方法在光栅处理中内插明暗以及在线性纹理映射中内插纹理坐标。因此，我们将在保留每个像素上的z直到光栅处理阶段，沿着边内插它然后沿着扫描线在边上使用该值。
　　必须注意到，如果我们应用了透视投影变换，在可用空间中的z坐标不是线性地变化的。比较有吸引力的是使用<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image765.gif">来代替深度标准，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/7.1/Image765.gif">在这样的空间中是线性变化的。


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

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