第5讲 计算机图形学消隐算法

1、消隐算法消隐算法 用计算机生成三维形体的真实图形，是计算机图形学研究用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种投影变换，在二维显示表面上绘制出来。维信息作某种投影变换，在二维显示表面上绘制出来。 由于投影变换失去了深度信息，往往导致图形的二义性：由于投影变换失去了深度信息，往往导致图形的二义性：要消除二义性，必须在绘制时消隐实际不可见得线和面，要消除二义性，必须在绘制时消隐实际不可见得线和面，即消隐。经过消隐的投影图称为物体的真实图形。即消隐。经过消隐的投影图称为物体

2、的真实图形。一、概述一、概述 消隐不仅与消隐对象有关，还与观察者消隐不仅与消隐对象有关，还与观察者的位置有关。如图所示，由于视点的位的位置有关。如图所示，由于视点的位置不同，物体的可见部分也不同：置不同，物体的可见部分也不同：消隐与观察者的位置关系消隐与观察者的位置关系按消隐的对象分类按消隐的对象分类线消隐（线消隐（Hidden-lineHidden-line）面消隐（面消隐（Hidden-surfaceHidden-surface）按消隐空间分类按消隐空间分类物体空间消隐算法物体空间消隐算法图像空间消隐算法图像空间消隐算法p线消隐（线消隐（Hidden-lineHidden-line） 消隐

3、对象是物体上不可见的线，一般用于消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或其它画线设备绘制线框图。当用笔式绘图仪或其它画线设备绘制图形时，主要使用这种算法。图形时，主要使用这种算法。p面消隐面消隐（Hidden-surfaceHidden-surface） 消隐对象是物体上不可见的面，一般用于消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示器绘制图形时，主填色图。当用光栅扫描显示器绘制图形时，主要使用这种算法。要使用这种算法。 早期图形显示器是用线条表示图形，消隐主要是消隐线早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续变化的

4、色调来描问题。使用光栅显示器后，物体可用连续变化的色调来描述，消隐算法的研究渐渐转向消隐面的问题。述，消隐算法的研究渐渐转向消隐面的问题。 p第一种是物空间算法。第一种是物空间算法。它以三维场景中的物体对像作为处理单元的，在所它以三维场景中的物体对像作为处理单元的，在所有的对像之间进行比较，除去完全不可见的的物体有的对像之间进行比较，除去完全不可见的的物体和物体上不可见的部分。常用于线框表示立体的线和物体上不可见的部分。常用于线框表示立体的线隐藏，也用于面隐藏。隐藏，也用于面隐藏。for (for (场景中的每一个物体场景中的每一个物体) ) 将其与场景中的其它物体比较，确定其将其与场景中的其

5、它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；表面的可见部分；显示该物体表面的可见部分； 隐藏线（面）的消除的两种基本算法隐藏线（面）的消除的两种基本算法特点是：算法可以达到相当高的精度。特点是：算法可以达到相当高的精度。 p第二种是像空间算法。第二种是像空间算法。 它以构成图形的每一个像素为处理单元的，确定场景它以构成图形的每一个像素为处理单元的，确定场景中哪些表面的像素相对于观察点而言是可见的，用该表面中哪些表面的像素相对于观察点而言是可见的，用该表面的颜色填充该像素。常用于隐藏面。的颜色填充该像素。常用于隐藏面。特点是：算法精度低，只能达到屏幕精度为止，但速度往特点是：算法

6、精度低，只能达到屏幕精度为止，但速度往往更高。往更高。 其算法是对每一个像素其算法是对每一个像素:l在和投影点到像素的连线相交的表面中找到离观察点最近在和投影点到像素的连线相交的表面中找到离观察点最近的表面的表面l用该表面上交点处的颜色填充该像素。用该表面上交点处的颜色填充该像素。 for (for (窗口内的每一个像素窗口内的每一个像素) ) 确定距视点最近的物体，以该物体表确定距视点最近的物体，以该物体表 面的颜色来显示像素面的颜色来显示像素 算法复杂度算法复杂度 假设场景中有假设场景中有k k个物体个物体，平均每个物体表面，平均每个物体表面由由h h个多边形个多边形构成，显示区域中有构成

7、，显示区域中有m x nm x n个像素个像素，则：则： 第一种算法的复杂度为：第一种算法的复杂度为： O(kh)O(kh)(kh)(kh) 第二种算法的复杂度为：第二种算法的复杂度为：O(mnkh)O(mnkh)9物空间消隐算法物空间消隐算法: : 需对物体表面的需对物体表面的h h个多边形个多边形中的每个面与其余中的每个面与其余h-1h-1个面进行比较，精确地求出物体上每个棱边或个面进行比较，精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正比于每个面的遮挡关系。算法的计算量正比于h h2 2，即算即算法复杂度为：法复杂度为：O(h)O(h)2 2) ) 。 则：则：k k个物体个

8、物体的算法复杂度为：的算法复杂度为：O(kh)O(kh)2 2) ) 。10象空间消隐算法象空间消隐算法： 这类算法对屏幕上的每个象素进行判断，以决这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边形在该象素定物体上哪个多边形在该象素 点上是可见的。若屏点上是可见的。若屏幕上有幕上有m mn n个象素个象素点，每个物体表面上有点，每个物体表面上有h h个多边形个多边形，则该类消隐算法计算量正比于，则该类消隐算法计算量正比于mnhmnh。 则：则： k k个物体个物体的算法复杂度为：的算法复杂度为： O(mnkh)O(mnkh) 。 各种消隐算法均采用一定形式的几何排序。通过排各种消隐算法

9、均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何元素，确定几何序，可搜查出位置上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次题。各种算法都有各自的排序方法和排序次序。排序次序影响算法的效率。序影响算法的效率。 算法排序算法排序二、二、 消隐基本技术消隐基本技术 为了提高消隐算法的效率，为了提高消隐算法的效率，各种消隐算法各种消隐算法常常采用一些有效的采用一些有效的消隐消隐基本基本算法。算法。利用连贯性利用连贯性将透视投影转换成平行投影将透视投影转换

10、成平行投影包围盒技术包围盒技术背面剔除背面剔除空间分割技术空间分割技术物体分层表示物体分层表示 物体连贯性物体连贯性面的连贯性面的连贯性 区域连贯性区域连贯性 扫描线的连贯性扫描线的连贯性 深度连贯性深度连贯性p 利用连贯性利用连贯性 连贯性是指从一个事物到另一个事物，其连贯性是指从一个事物到另一个事物，其属性值属性值( (如颜色值、空间位置如颜色值、空间位置) )通常是平缓过渡通常是平缓过渡的性质。的性质。例如：例如： 棱边的连贯性棱边的连贯性是指：是指：棱边的可见性在它与其他棱边相交棱边的可见性在它与其他棱边相交时才发生变换时才发生变换； 面的连贯性面的连贯性是指：是指：如果面的一部分是可

11、见的，则一般情如果面的一部分是可见的，则一般情况下整个面都是可见的况下整个面都是可见的。 物体连贯性 若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需要对它们的表面多边形逐一进行测试； 面的连贯性一张面内的各种属性值一般是缓慢变化的，可采用增量的形式对其进行计算； 区域连贯性一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相同； 扫描线的连贯性在相邻两条扫描线上，可见面的分布情况相似； 深度连贯性同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同，这样只需取其上一点计算出深度值，比较该深度值便能得出结果； p 包围盒技

12、术包围盒技术 一个形体的包围盒指的是包围它的简单形体。一个形体的包围盒指的是包围它的简单形体。比如，比如，2 2D D的矩形，的矩形，3 3D D的的立方块、长方体、球等。立方块、长方体、球等。目的：目的： 避免盲目的求交测试；避免盲目的求交测试； 各物体间的比较等。各物体间的比较等。一个好的包围盒要具有两个条件：一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；包围和充分紧密包围着形体；对其的测试比较简单。对其的测试比较简单。例：例：矩形包围盒及长方体包围矩形包围盒及长方体包围盒提高算法效率盒提高算法效率 包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进

13、行进一步判断。可推广到面与面的遮挡快速判断。 例如：两个空间多边形A、B在投影平面上的投影分别为A，B ，因为A 、B的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试。右图：包围盒相交，投影也相交；包围盒相交，投影不相交。AABBp 背面剔除背面剔除 外法向外法向 外法向与投影方向（观察方向）的夹角判断：外法向与投影方向（观察方向）的夹角判断：前向面与后向面（背面）前向面与后向面（背面）剔除依据：剔除依据： 物体表面是封闭的，背面总是被前物体表面是封闭的，背面总是被前向面所遮挡，从而始终是向面所遮挡，从而始终是 不可见的。不可见的。法向向量法向向量N 视线向量视线向量V法向向量法向向量N

14、法向向量法向向量N 90 90V VN N cos 视线视线- -法线夹角法法线夹角法N N 面的法向量面的法向量V V 面上一点指向观察点的向量面上一点指向观察点的向量 = = coscos-1-1( )( )0= 0= 时时 可见可见 = = = 00N N . . V V00 2 2p、空间分割技术、空间分割技术依据：依据：场景中的物体，它们的投影在投影平面上场景中的物体，它们的投影在投影平面上 是否有相互遮挡的重叠部分？是否有相互遮挡的重叠部分？ 对于根本不存在相互遮挡关系的物体，应对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。避免这种不必要的测试。方法：方法：将投影平面

15、上的窗口分成若干小区域；为将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体该区域有相交部分；则在小区域中判断哪个物体可见时，可见时，只要对本区域的相关物体表中的物体进只要对本区域的相关物体表中的物体进行比较即可行比较即可。复杂度比较：复杂度比较： 假定每个小区域的相关物体表中平均假定每个小区域的相关物体表中平均有有h h个个物体，场景中有物体，场景中有k k个物体，由于物体在场景中的分个物体，由于物体在场景中的分布是分散的，显然布是分散的，显然h h远小于远小于k k。 根据物空间

16、消隐方法所述，其算法复杂根据物空间消隐方法所述，其算法复杂度为度为O(hO(h2 2),),远小于远小于O(kO(k2 2) )。p 物体分层表示物体分层表示表示形式表示形式：模型变换中的树形表示方式：模型变换中的树形表示方式原理：原理：减少场景中物体的个数，降低算法复杂度减少场景中物体的个数，降低算法复杂度。方法方法： 将父节点所代表的物体看成子节点物体的将父节点所代表的物体看成子节点物体的包围盒，当两个父节点之间不存在遮挡关系时，包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点做进一步测试。就勿对两者的子节点做进一步测试。 父节点之间的遮挡关系可以用它们之间的包父节点之间的遮挡

17、关系可以用它们之间的包围盒进行预测试。围盒进行预测试。p 将透视投影转换成平行投影将透视投影转换成平行投影 消隐与透视关系较密切，体现在消隐与透视关系较密切，体现在： 1 1）消隐必须在投影之前完成；）消隐必须在投影之前完成；因为消隐需要物体三维信息，投影后只有二维信息； 2 2）物体之间的遮挡关系与投影中心（视点）物体之间的遮挡关系与投影中心（视点） 的选取有关；的选取有关； 3 3）物体之间的遮挡关系与投影方式有关，）物体之间的遮挡关系与投影方式有关，在平行投影时，其遮挡关系可通过深度值来确定。l 凸多面体的每个面要么可见，要么凸多面体的每个面要么可见，要么不可见；不可能出现一个面部分可不

18、可见；不可能出现一个面部分可见，部分不可见。见，部分不可见。xyz三、凸多面体隐藏线的消除三、凸多面体隐藏线的消除l 凸多面体是由若干个平面围成的物体。凸多面体是由若干个平面围成的物体。假设这些平面方程为：假设这些平面方程为： ai x+bi y+ci z+di=0 (i=1,2,n)调整系数的符号，使每个平面的法向调整系数的符号，使每个平面的法向量（量（ai,bi,ci）指向多面体内部。指向多面体内部。l 如果投影方向为（如果投影方向为（Xp,Yp,Zp）,那么那么（ai,bi,ci）( (Xp,Yp,Zp）0时，时，此平面为不可见面，在作图时，此平面为不可见面，在作图时，此面不绘制。此面不

19、绘制。 凸多面体消隐的基本原理凸多面体消隐的基本原理 表面外法线与其可见性的关系表面外法线与其可见性的关系 设平面设平面Pi上任一点的外法矢上任一点的外法矢ni与该点的视线矢量与该点的视线矢量vi的数的数量积：量积： 从而有从而有 其中其中i为为ni与与vi之间的夹角，之间的夹角，i=1，2，m，这里，这里m为平面数。为平面数。iiiiivnvncos 当当 cos i i0 0 ，即，即 0 i i /2 时，时，Pi为朝前面，为可见的，应为朝前面，为可见的，应该画出；该画出； 当当 cos i i00 ，即，即 /2 face_zmax(i) Then face_zmax(i) = zz(

20、line_p(j) Next jNext i 求各面最大求各面最大Z坐标坐标 XYZ012345675050 For i = 0 To 5 L = i For m = i + 1 To 5 If (face_zmax(m) face_zmax(L) Then L = m Next m If (L i) Then k = face_s(i): face_s(i) = face_s(L): face_s(L) = k k = face_e(i): face_e(i) = face_e(L): face_e(L) = k k = face_zmax(i): face_zmax(i) = face_z

21、max(L): face_zmax(L) = k End If Next i 对面表根据最大对面表根据最大Z坐标从小到大排序坐标从小到大排序 face_s = Array(0, 5, 10, 15, 20, 25) face_e = Array(4, 9, 14, 19, 24, 29) face_zmax=Array(68,90,54,90,90,22) face_s = Array(25, 10, 0, 5, 15, 20) face_e = Array(29, 14, 4, 9, 19, 24) face_zmax=Array(22,54,68,90,90,90)For i = 0 To

22、 5 多边形面多边形面循环循环 ymin = 10000: ymax = 0 For j = face_s(i) To face_e(i) - 1 If (yy(line_p(j) ymax) Then ymax = yy(line_p(j) Next 计算面多边形顶点的最大最小值计算面多边形顶点的最大最小值 For h = ymin To ymax 扫描线循环扫描线循环 k = 0 For j = face_s(i) To face_e(i) - 1 面多边形的边循环面多边形的边循环 If Int(yy(line_p(j + 1) Int(yy(line_p(j) Then t = (h -

23、 yy(line_p(j) - 0.5) / (yy(line_p(j + 1) - yy(line_p(j) If (t = 0 And t 0)then for i=fs(j) to fe(j)-1 picture1.line(xx(i),yy(i)-(xx(i+1),yy(i+1) next endifendif两个面正轴测投影两个面正轴测投影-消隐消隐 a=(y2- y1)(z3 - z1)- (y3- y1)(z2 - z1) b=(z2- z1)(x3 - x1)- (z3- z1)(x2 - x1) c=(x2- x1)(y3 - y1)- (x3- x1)(y2 - y1)2.

24、 深度缓冲器算法深度缓冲器算法(Z-buffer算法）算法） Z缓冲器算法的基本思想是缓冲器算法的基本思想是： 将投影平面每个像素所对应的所有面片（平面或曲面）将投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。见图。素的属性值。见图。 Z缓冲器算法基本思想缓冲器算法基本思想S3S2S1(x,y)XvZvYv一种典型的、也是最简单的像空间消隐算法一种典型的、也是最简单的像空间消隐算法Z缓缓冲器冲器每个单元存放对应象素每个单元存放对应象素当前最近面的深度值当前最近面的深度值帧缓帧缓冲器

25、冲器每个单元存放对应象素每个单元存放对应象素的颜色值的颜色值深度缓冲器算法深度缓冲器算法 算法描述算法描述深度缓冲器所有单元均置为最小深度缓冲器所有单元均置为最小z值，帧缓冲值，帧缓冲器各单元均置为背景色，然后逐个处理多边形器各单元均置为背景色，然后逐个处理多边形表中的各面片。表中的各面片。每扫描一行，计算该行各像素点（每扫描一行，计算该行各像素点（x，y）所对）所对应的深度值应的深度值z（x，y），并将结果与深度缓冲），并将结果与深度缓冲器中该像素单元所存储的深度值器中该像素单元所存储的深度值ZB（x，y）进行比较。进行比较。若若zZB（x，y）,则则ZB（x，y）= z，同时将，同时将该像

26、素的属性值该像素的属性值I（x，y）写入帧缓冲器，即）写入帧缓冲器，即FB（x，y）= I（x，y）；否则不变。）；否则不变。算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u Z缓冲器的第缓冲器的第(u,v)单元的值单元的值) 置帧缓冲器的第置帧缓冲器的第(u,v)单元值为当前多边形颜色；单元值为当前多边形颜色； 置置Z缓冲器的第缓冲器的第(u,v)单元值为单元值为d; 深度缓冲器算法深度缓冲器算法 深度值的计算深度值的计算若已知多边形的方程，则可用增量法计若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方算扫描线每一个像素的深度。设平面

27、方程为：程为：则多边形面上的点（则多边形面上的点（x，y）所对应的深）所对应的深度值为：度值为： CDByAxz)(C0C0 0DCzByAx 由于所有扫描线上相邻点间的水平间距由于所有扫描线上相邻点间的水平间距为为1个像素单位，扫描线行与行之间的垂个像素单位，扫描线行与行之间的垂直间距也为直间距也为1。因此可以利用这种连贯性。因此可以利用这种连贯性来简化计算过程，如图所示。来简化计算过程，如图所示。 深度计算深度计算 若已计算出（若已计算出（x，y）点的深度值为）点的深度值为zi，沿，沿x方向相邻连贯点（方向相邻连贯点（x+1，y）的深度值）的深度值zi+1可可由下式计算：由下式计算： 沿多边形左边界递归计算边界上各点的坐标：沿多边形左边界递归计算边界上各点的坐标： m为该边的斜率，沿该边的