c提高消隐算法效率的常见方法3 应用一避免盲目求交 例如:两个空间多边形A、B在投影平面上的 投影分别为A,B′,因为A、B'的矩形包 围盒不相交,则A、B不相交,无须进行遮 挡测试。右下图:包围盒相交,投影也相交; 包围盒相交,投影不相交。 B 包围盒 包围盒
浙江大学信息学院 计算机图形学 提高消隐算法效率的常见方法3 应用—避免盲目求交 例如：两个空间多边形A、B在投影平面上的 投影分别为A’ ，B’ ，因为A’ 、B’的矩形包 围盒不相交，则A’ 、B’不相交，无须进行遮 挡测试。右下图：包围盒相交，投影也相交； 包围盒相交，投影不相交
提高消隐算法效率的常见方法4 背面剔除 外法向:规定每个多边形的外法向都是指向物 体外部的 前向面:若多边形的外法向与投影方向(观察 方向)的夹角为钝角,称为前向面。 后向面:若多边形的外法向与投影方向(观察 方向)的夹角为锐角,称为后向面(背面)。 剔除依据:背面总是被前向面所遮挡,从而不 可见。 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 提高消隐算法效率的常见方法4 • 背面剔除 外法向：规定每个多边形的外法向都是指向物 体外部的。 前向面：若多边形的外法向与投影方向（观察 方向）的夹角为钝角，称为前向面。 后向面：若多边形的外法向与投影方向（观察 方向）的夹角为锐角，称为后向面（背面） 。 剔除依据：背面总是被前向面所遮挡，从而不 可见
提高消隐算法效率的常见方法4 前向面 后向面 多面体的隐藏线消除 图中的JEAF、HCBG和 DEABC所在的面均为后向面 其它为前向面 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 提高消隐算法效率的常见方法4 前向面 后向面 多面体的隐藏线消除 图中的JEAF、HCBG和DEABC所在的面均为后向面。 其它为前向面。 V A B C D E F G H I J N V n V n
Y提高消隐算法效率的常见方法5 ·空间分割技术 依据:场景中的物体,它们的投影在投影 平面上是否有重叠部分?(是否存在相互遮挡 的可能?)对于根本不存在相互遮挡关系的物 体,应避免这种不必要的测试。 方法:将投影平面上的窗口分成若干小区 域;为每个小区域建立相关物体表,表中物体 的投影于该区域有相交部分;则在小区域中判 断那个物体可见时,只要对该区域的相关物体 表中的物体进行比较即可。 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 提高消隐算法效率的常见方法5 • 空间分割技术 依据：场景中的物体，它们的投影在投影 平面上是否有重叠部分？（是否存在相互遮挡 的可能？）对于根本不存在相互遮挡关系的物 体，应避免这种不必要的测试。 方法：将投影平面上的窗口分成若干小区 域；为每个小区域建立相关物体表，表中物体 的投影于该区域有相交部分；则在小区域中判 断那个物体可见时，只要对该区域的相关物体 表中的物体进行比较即可
提高消隐算法效率的常见方法5 复杂度比较: 不妨假定每个小区域的相关物体表中平均有h个物 体,场景中有k个物体,由于物体在场景中的分布是分 散的,显然h远小于k。根据第二种消隐方法所述,其 算法复杂度为0(h*h),远小于0(k*k) 第二类消隐方法(物体空间的消隐算法):以场景中的 物体为处理单元; for(场景中的每一个物体) {将其与场景中的其它物体比较,确定其表面的可见部 假设场景中有k个物体,平均每个物体表面由h个多边形 构成,则:算法的复杂度为:0((kh)*(kh) 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 提高消隐算法效率的常见方法5 复杂度比较： 不妨假定每个小区域的相关物体表中平均有h个物 体，场景中有k个物体，由于物体在场景中的分布是分 散的，显然h远小于k。根据第二种消隐方法所述，其 算法复杂度为O(h*h),远小于O(k*k)。 第二类消隐方法（物体空间的消隐算法）：以场景中的 物体为处理单元； for (场景中的每一个物体) { 将其与场景中的其它物体比较，确定其表面的可见部 分 } 假设场景中有k个物体，平均每个物体表面由h个多边形 构成，则：算法的复杂度为：O((kh)*(kh))