图形编程指南chapter7new

《图形编程指南chapter7new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、25第七章隐面消除目录：7.1背面剔除(backculling)算法7.2从后到前排序7.3顺序列表和八叉树7.4入口（Portals）7.5二叉空间分割树7.6Beam树7.7扫描线算法7.8Z-buffer算法引言到目前为止，我们完全忽略了一些问题：很明显，它们是由于屏幕上的一些图元被另一些图元挡住所造成的。例如，当我们要描绘一个由多边形面组成的三维物体时，那么它的一部分必然要被挡住。我们要在屏幕上显示的必须是可见的东西。打个比方，对于一个立方体，无论从哪个方向进行透视处理，我们最多只能看到其中的三个面。这样，我们就要想出一种方法来决定哪些面是我们所能看到

2、的。如果我们使用从屏幕到世界的视处理方法，那么很自然的就能保证只有图元上正确的部分才显示在屏幕上。在这种视处理中，可见性在屏幕的每一个像素上进行判断。我们从人眼发出一条射线，穿过一个给定的像素，那么首先与这条射线相交的表面在这一个像素上就是可见的。从这个表面反射的光线能够进入我们的眼睛。在这一章中，我们将讨论用于隐面消除的一些方法。由于最普通的图元就是多边形，所以我们将要讨论的许多技术都是只针对多边形模型的。我们也将重点讨论用于多边形地形、体素模型的一些技术，最后将讨论一种适用于任何图元的一般性的算法。尽管隐面消除对于光线投射方法是本身就具备的，但是它的计算量

3、是很大的。这样，我们还将使用一些用于从世界到屏幕视处理方法的隐面消除算法，它们将与光线投射算法结合使用，从而减少计算量。7.1背面剔除(backculling)算法许多三维物体，它们所占据的空间都被一些连续的表面所包围。当我们观察这些物体时，只能看到这些包围表面中正面部分，而对背面就无法看到了。背面剔除算法就是将这些我们看不到的背面多边形去除掉。(见图7.1)25图7.1：包围表面的可见与不可见部分在前面的章节中，我们已经遇到过凸多边形的概念。这一概念也可以引申到多面体上。如果位于表面上的任意两个点的连线都没有超出边界的话，那么这个多面体就是一个凸多面体。凹多

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

5、面消除要归功于这种算法的自然本性，但背面剔除算法可以减少场景的复杂度，使我们不用再同那些复杂的隐藏面一起进行考虑，这样就加快了视处理的过程。让我们来设计一种技术，来决定一个多边形是位于物体表面的正面还是背面。我们已经看到了法向量在描述一个多边形的朝向时所起到的作用。这样，当一个多边形的法向量与观察方向之间的夹角大于90°时，就表示这个多边形位于物体的背面。25我们已经讨论过矢量积和标量积，它们对于解决上面的问题很有帮助。首先，我们计算位于一个给定多边形平面上的某两个向量的矢量积，得到这个多边形的法向量。这两个向量可以通过多边形顶点的差分来得到。接下来，计算观察

6、方向与法向量之间标量积的符号，由此决定它们之间是否形成了大于90°的角。如果真的大于90°，这个多边形就要被剔除掉，也就不用再考虑进行视处理过程了。我们要注意，根据定义，两个向量的矢量积的结果也是一个向量，它与两个做向量乘法的向量组成的平面正交。这也就是说，根据多边形平面上形成这两个向量的方式的不同，我们可以得到两种可能的法向量，它们的方向正好相反。(见图7.4)图7.4：顶点顺序与方向量方向的关系如图7.4所示，如果我们在连续顶点和建立两个向量，那么法向量的方向将会依赖于这两个向量的顺序。我们可以很方便的将多边形表面的正面与顶点的反时针顺序联系起来(见图7.

7、4(a))，这也正是定义表面法向量的基础。我们已经见到了两种不同的视处理过程，并且还有两种不同的投影变换。使用这些技术，我们可以在渲染管道中的某一特定阶段完成背面剔除算法。对于平行投影方式，投影线都具有相同的方向，并且与观察方向一致。就在投影阶段之前，观察方向向量指向Z方向，可以用(0,0,1)来进行描述。这样当然也就减少了标量积的计算量，其结果就等于法向量的z分量。这样，我们就只需要计算法向量的z分量值就可以了。对于透视投影，投影线相交在观察者的眼中，它们的方向是不同的。我们可以在世界或观察空间中的任一点上构造一个指向观察者眼睛的向量，并使它指向该点方向，这

8、样就得到了这一点的观察方向。(见图7.