《计算机图形学》08消隐技术

第八章消隐技术8.1基本概念一.为什么要消隐因为计算机图形处理的过程中，不会自动消去隐藏部分，相反会将所有的线和面都显示出来。问题：①对于线画图形会出现多义性。对于光栅扫描着色的面图形则会导致图形错误。②要增强图形的真实感必须进行消隐处理。二.消隐的分类

1.消除隐藏线对于采用物体的棱线或轮廓线表示的线画图形，应消去物体本身看不见的棱线和轮廓线部分，以及因物体间的互相遮挡而被隐藏的棱线和轮廓线。2.消除隐藏面对于采用光栅扫描着色方法（即采用物体表面不同的明暗度）绘制的图形，应消除物体上看不见的面以及因物体间的互相遮挡而被隐藏的面。与此相对应，消隐的算法也可分为两种：

第一种方法是以场景中的物体为处理单元，将一个物体与其余的k－1个物体逐一比较，仅显示它可见的表面以达到消隐的目的。此类算法通常用于消除隐藏线。假定场景中有k个物体，平均每个物体的表面由h个多边形构成，其计算复杂度为O((kh)2)。

算法描述如下：for(场景中的每一个物体){将该物体与场景中的其它物体进行比较，确定其表面的可见部分；显示该物体表面的可见部分；}

第二种方法是以窗口内的每个像素为处理单元，确定在每一个像素处，场景中的物体哪一个距离观察点最近（可见的），从而用它的颜色来显示该像素。此类算法通常用于消除隐藏面。若显示区域中有m×n个像素，则其计算复杂度为O(mnkh)。算法描述如下：for(窗口内的每一个像素){确定距观察点最近的物体，以该物体表面的颜色来显示像素；}三.消隐算法中常用的处理技术1.排序确定物体间遮挡关系的要素：视点位置视线方向按观察方向上离视点（投影参考点）的远近（通常用z值来表示）排序。2.测试用以判断点与面、线与面、面与面之间的关系。u(x)v(y)n(z)视点z值包含测试：测试空间点的投影是否在某个空间多边形的投影内，若在，则可能存在遮挡关系；若不在，则不存在遮挡关系。测试方法：从空间点的投影开始向与－y轴平行的方向作射线，计算该射线与空间多边形的投影的交点个数，若为奇数，则点的投影在多边形的投影内；若为偶数，则点的投影不在多边形的投影内。xy特殊情况左闭右开重叠测试：测试两个空间多边形的投影是否重叠，若重叠，则可能存在遮挡关系；若不重叠，则不存在遮挡关系。测试方法：四.提高消隐算法效率的常用方法利用连贯性包围盒技术背面剔除将透视投影转换成平行投影空间分割技术

复杂度比较物体分层表示

1.利用相关性（连贯性）

物体的相关性：若物体A与物体B是完全相互分离的，消隐时只需比较A、B两物体之间的遮挡关系，而不需对其表面多边形逐一进行测试。

面的相关性：一个面内的各种属性值（坐标值、灰度值等）一般都是缓慢变化的，可采用简单增量方式进行计算。

区域相关性：一个区域是指屏幕上一组相邻的像素，它们通常属于同一个可见面。区域相关性表现在一条扫描线上时,即为扫描线上的每个区间内只有一个面可见。扫描线相关性：在相邻的两条扫描线上，可见面的分布情况相似。

深度相关性：物体的同一表面上的相邻部分深度是相近的。

2.包围盒技术用于对物体间的某些关系进行比较和测试，从而可避免盲目的求交运算，减少计算量，提高效率。一个好的包围盒要具有两个条件：（1）包围盒充分紧密包围着形体；（2）对其的测试比较简单。二维图形-----包围框（重叠测试）；三维物体-----包围盒、包围球。3.背面剔除一个平面多面体的表面由若干个平面多边形构成，若一个多边形表面的外法线方向与投影方向（观察方向）的夹角为钝角，则该面为前向面；若其夹角为锐角，则为后向面或背面。剔除依据：物体表面是封闭的，背面总是被前向面所遮挡，从而始终是不可见的。投影方向ABCD4.将透视投影转换成平行投影消隐与透视关系密切,体现有： 1）消隐必须在投影之前完成； 2）物体之间的遮挡关系与投影中心（视点）的选取有关； 3）物体之间的遮挡关系与投影方式有关5.空间分割技术

依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？（是否存在相互遮挡的可能？）对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较即可。6.复杂度比较：不妨假定每个小区域的相关物体表中平均有h个物体，场景中有k个物体，由于物体在场景中的分布是分散的，显然h远小于k。根据第二种消隐方法所述，其算法复杂度为O(h*h),远小于O(k*k)。7.物体分层表示

表示形式：模型变换中的树形表示方式

原理：减少场景中物体的个数，从而降低算法复杂度。

方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。8.2深度缓存算法(Z—buffer算法)1.Z—Buffer用于存放与屏幕上像素点对应的物体上点的深度值。xyz视线方向视点位置屏幕像素F—BufferZ—Buffer投影面可见点不可见点2.算法初始化：ZB(i,j)=机器最大值；FB(i,j)=背景色。for(j=1;j<=n;j++)/*共有n根扫描线*/for(i=1;i<=m;i++)/*每根扫描线上有m个像素点*/for(k=1;k<=p;k++)/*共有p个多边形*/{判断像素点(i,j)是否在多边形Fk在投影面上的投影内;若(i,j)在多边形Fk的投影内，计算多边形Fk上对应于像素点(i,j)处的深度值Zi,j;if(Zi,j<ZB(i,j)){ZB(i,j)=Zi,j;FB(i,j)=多边形Fk的颜色}else不作处理}3.算法实现中的关键问题①判断点(i,j)是否在多边形Fk在投影面上的投影内解决办法：采用包含测试。②计算多边形Fk在点(i,j)处的深度值Zi,j

若多边形Fk的平面方程为：ax+by+cz+d=0若c≠0，则ai+bj+dc若c=0，则多边形Fk的法线方向与Z轴垂直，Fk在投影面上的投影为一条直线，可不予考虑。Zi,j=—4.算法的特点①简单不需要将所有的多边形按离视点的远近排序，其算法的复杂度只与多边形的个数成正比。②需要有一个较大容量的Z—Buffer。5.算法的改进①采用包围框技术，提高算法的效率。②采用硬件Z—Buffer来实现。

6.算法的进一步改进①采用分区处理方法。②利用相关性。8.3列表优先算法（画家算法）

基本思路：根据物体上各个面（多边形）距离视点的远近进行排序，建立一张优先级表。约定距离视点近的优先级高，距离视点远的优先级低。生成图象时，优先级低的多边形先画，优先级高的多边形后画。

关键问题：在深度方向上对多边形进行正确的排序。ABC分离面PDExyzo空中小三角形面片xyo

8.4光线投射算法算法思路将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点，用深度值最大的交点（最近的）所属的多边形的颜色显示相应的像素；