CG消隐计算.ppt

* * * 1999年7月07/16/96 * *## * * * * * * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * * * * 1999年7月07/16/96 * *## * * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * * * * * * * * * * * * * * 1999年7月07/16/96 * *## * * 1999年7月07/16/96 * *## * 计算机图形学 * 区域扫描线算法 多边形发生相互贯穿 在多边形发生相互贯穿的情况下，仍可以使用扫描线消隐算法。如图所示，多边形GHI和JKL发生相互贯穿。此时，可将多边形GHI分为两个多边形GHH‘G’和H‘G’I，引入了虚边G‘H’。 G’ L J G H K I H’ 计算机图形学 * 区域扫描线算法 扫描线消隐算法特点 扫描线消隐算法不仅用于多边形的消隐，还可扩展应用到任意曲面体的消隐。 在任意曲面体的消隐中，需要将多边形表PT改为曲面表ST，活动边表改为活动曲面表。 扫描转换时，当进入下一条扫描线，需删除那些已脱离扫描线的多边形结点，并增加一些新加入的多边形结点。 计算机图形学 * 8.4 深度排序算法（画家算法） 算法原理：算法约定距视点近的优先级高，距视点远的优先级低。生成图像时，优先级低的多边形先画，优先级高的多边形后画。这样，后画的多边形就会将先画的多边形遮挡住，从而达到消隐的效果。 算法的关键是多边形排序。 计算机图形学 * 三维物体的深度排序算法 将场景中的多边形序列按其z坐标的最小值zmin (物体上离视点最远的点)进行排序。 当物体间的z值范围不重叠时：假设多边形P的zmin在上述排序中最小，如果多边形P的z值范围与Q的z值范围不重叠，即Pzmax Qzmin，此时可以断定多边形P的优先级最低。 计算机图形学 * 三维物体的深度排序算法 z x P Q Pzmax Qzmin 物体间的z值范围不重叠 计算机图形学 * 三维物体的深度排序算法 当物体间的z值范围重叠时：判断多边形P是否遮挡场景中多边形Q，需作如下5个判别步骤： (1). 多边形P和Q的x坐标范围是否不重叠 (2). 多边形P和Q的y坐标范围是否不重叠 (3). 从视点看去，多边形P是否完全位于Q的背面 (4). 从视点看去，多边形Q是否完全位于P的同一侧 (5). 多边形P和Q在xy平面上的投影是否不重叠 计算机图形学 * 三维物体的深度排序算法 z x P Q (1). 多边形P和多边形Q的x坐标范围不重叠 计算机图形学 * 三维物体的深度排序算法 y x P Q (2). 多边形P和多边形Q的y坐标范围不重叠 计算机图形学 * 三维物体的深度排序算法 z x P Q (3). 从视点看去，多边形P完全位于Q的背面 计算机图形学 * 三维物体的深度排序算法 z x P Q (4). 从视点看去，多边形Q完全位于P的同一侧 计算机图形学 * 三维物体的深度排序算法 y x P Q (5). 多边形P和Q在xy平面上的投影不重叠 计算机图形学 * 三维物体的深度排序算法 如果上述五种情况中只要有一种成立，就表明多边形P和Q是互不遮挡的，即多边形P的绘制优先级低于Q。 如果上述判断都不成立，说明多边形P有可能遮挡Q，此时把多边形P和Q进行互换重新进行判断，而重新判断只要对上述条件(3)和(4)进行即可。 计算机图形学 * 三维物体的深度排序算法 P和Q交换顺序后，仍不能判断其优先级顺序，可以按如下方法处理：将其中一个多边形沿另一个物体剖分： 避免循环判断：P做标记 多边形剖分：将P沿Q剖分 计算机图形学 * 三维物体的深度排序算法 相互遮挡时，将其中一个多边形沿另一个多边形进行剖分。 x y Q P x y R P Q 计算机图形学 * 深度排序算法 三维物体的深度排序算法适合于固定视点的消隐。 通过多边形的剖分，总是可以实现多边形物体在三维空间中的深度排序 深度排序算法可以有效地实现透明效果 在视点变化的场合中(如飞行模拟)，深度排序算法难以满足实时性的要求。 算法复杂度O(nlogn) 计算机图形学 * 8.5