第九章 3D基本算法 数字媒体技术知识专业学科课程 计算机游戏概论ppt .ppt

现在的二元空间分割树看起来就如下图： 再继续分割上述二元树结构的话，二元树结构就会变成如下图所示： 当映射多边形时，我们可以利用camera的位置与每个平面比较，然后再以距离为基本顺序原则。 一开始，基本节点是B多边形，接着执行下面步骤： (1)求出平面与camera之间的距离。 (2)如果距离大于0： ¤移向后面节点并回到步骤（1）。 ¤显示目前节点内的多边形。 ¤移向前面节点并回到步骤（1） (3)如果（2）是错误的： ¤移向前面节点并回到步骤（1） ¤显示目前节点内的多边形。 ¤移向后面节点并回到步骤（1） 完成上面步骤，绘制节点的顺序： Node A、Node Cb、Node Fb、Node Fa、Node Gab、Node Gaa、Node E、Node Gb、Node Ca、Node D 9.5.5 细节层次 在real time图形中。需要绘制3D场景的复杂度非常高（包含几十个甚至上百万个多边形），所以要实现这种复杂场景的绘制是非常困难的。 解决方法：利用减少场景的复杂度来提高图像的绘制速度，而“细节层次”（Level of Detail——LOD）这一门用来显示和简化场景的技术就是在这种背景下产生的。 细节层次绘制简化的技术是在不影响画面视觉效果的条件下，逐步简化景物的表面细节来减少场景的几何图形所产生之复杂性，并且它又可以提高绘制算法的效率。 对于原始网格模型不同细节层次的模型建立，我们可以假设场景的模型都是以三角形的网格呈现（在实际应用中，为了绘制方便，3D场景一般都被转化为三角形网格状），因此可以 从网格的几何特性着手，而这种技术可以归纳为3种不同的基本演算，分别是：“顶点删除”，“边界压缩”及“面的收缩”。 网格简化（real time rendering） 顶点删除 删除网格中的一个顶点，然后再对它的相邻三角形做出一个空洞，这个空洞就当作是三角的剖分，以保持网格的一致性。 边界压缩（Edge Collapse边塌陷） 将网格上的一条边压缩成一个顶点，这个顶点与该边相邻的两个三角形一起退化掉，而再把它的两个顶点融合成一个新的顶点。 面的收缩 将网格上的一个面收缩成一个顶点，让该三角形本身的和与其相邻的三个三角形一起退化掉，而它的三个顶点则收缩成另一个新的顶点。 细节层次简化是实时3D图形学应用比较多的一种技术，通过这种技术，我们可以简化场景的复杂度，同时也可以采用不同分辨率的模型来显示复杂场景的不同物体，以满足实时3D的要求。 本章结束 3D裁剪 9-5 隐藏面消除 背面剔除(back culling)算法 许多三维物体中，它们所占据的空间都被一些连续的表面所包围着。当我们观察这些物体的时候，只能看到这些包围表面中的正面部分，背面则无法看到。「背面剔除算法」就是将这些我们看不到的背面多边形去除掉。如下图所示： 我们只能看见三为物体中的其中一面而已 凸面体 凹面体 这个面被其它面挡住了 对于透视投影而言，投影线会相交在观察者的眼中，它们的方向是不同的。我们可以在世界或观察空间中的任意一点上构造一个指向观察者眼睛的向量，并且使它指向该点的方向，如此一来，我们就得到了这一点的观察方向了。如下图所示： 9.5.2 排序 另一种方法也可以用来剔除这些看不到的顶点，其方法可以充分的利用图形硬件的缓冲储存结构来加速其运算。不管场景中的多边形有没有挡住其它的多边形，只要按照从后面到前面的顺序光栅化图形就可以正确的显示所有可见的图形了，也就是将离观察者最近的一个多边形最后进行光栅化处理。这种方法就是我们称它为「画家算法」。 从前边节已经看到，一般多边形模型隐藏面消除的代价极高，然而在大多数情况下，我们要处理的对象有一些特殊的属性，利用这些属性可以减轻隐藏面的消除工作量。例如在以“高度值运算“来处理表面的地形曲面时。就很容易地获得多边形视点从前到后的顶点顺序。 由于这种表面方法具有矩形自然的属性，地形就可以被分割成许多正方形的单元格。 9.5.3 八叉树 当观察者在一些单元边界内位于虚拟地形表面上或表面的上方。我们能够把整个的地形分割为四个规则的子地形，如下图。 我们可以将地形单元的光栅处理顺序编列成如下所示： 第一次：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。 光栅处理的顺序将会依据观察者在场景中角度的不同而有所改变。如下图所示： 有这种规律的特性，我们可以将它作为由后到前寻找地形顺序的依据，而这种特性就可以使用“八叉树”的存储规则，或者也可以用在空间占有的矩形来描述映射。 在这种情况下，我们利用类似高度场的方法，扩展成为处理三维