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

1、消隐(xio yn)算法 主要(zhyo)内容: 一、概述二、消隐的基本技术三、凸多面体消除隐藏线四、消除隐藏面 共六十二页 用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息(xnx)作某种投影变换，在二维显示表面上绘制出来。 由于投影变换失去了深度信息，往往导致图形的二义性：要消除二义性，必须在绘制时消隐实际不可见得线和面，即消隐。经过(jnggu)消隐的投影图称为物体的真实图形。一、概述共六十二页消隐(xio yn)不仅与消隐(xio yn)对象有关，还与观察者的位置有关。如图所示，由于视点的位置不同，物体的可见部分也不同：消隐

2、与观察者的位置(wi zhi)关系共六十二页按消隐的对象分类线消隐（Hidden-line）面消隐（Hidden-surface）按消隐空间分类物体空间消隐算法(sun f)图像空间消隐算法共六十二页线消隐（Hidden-line） 消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或其它画线设备绘制图形(txng)时，主要使用这种算法。面消隐（Hidden-surface） 消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示器绘制图形时，主要使用这种算法。 早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续变化的色调(s dio)来描述，消

3、隐算法的研究渐渐转向消隐面的问题。 共六十二页第一种是物空间算法。它以三维场景中的物体对像作为(zuwi)处理单元的，在所有的对像之间进行比较，除去完全不可见的的物体和物体上不可见的部分。常用于线框表示立体的线隐藏，也用于面隐藏。for (场景中的每一个(y )物体) 将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分； 隐藏线（面）的消除的两种基本算法特点是：算法可以达到相当高的精度。 共六十二页第二种是像空间算法。 它以构成(guchng)图形的每一个像素为处理单元的，确定场景中哪些表面的像素相对于观察点而言是可见的，用该表面的颜色填充该像素。常用于隐藏面。特点是：

4、算法精度低，只能达到屏幕精度为止，但速度往往更高。 其算法是对每一个像素:在和投影点到像素的连线相交的表面中找到离观察点最近的表面用该表面上交点处的颜色填充该像素。 for (窗口内的每一个(y )像素) 确定距视点最近的物体，以该物体表 面的颜色来显示像素共六十二页算法(sun f)复杂度 假设场景中有k个物体(wt)，平均每个物体表面由h个多边形构成，显示区域中有m x n个像素，则： 第一种算法的复杂度为： O(kh)(kh) 第二种算法的复杂度为：O(mnkh)共六十二页9物空间消隐算法: 需对物体表面的h个多边形中的每个面与其余h-1个面进行比较，精确地求出物体上每个棱边(ln bi

5、n)或每个面的遮挡关系。算法的计算量正比于h2，即算法复杂度为：O(h)2) 。 则：k个物体的算法复杂度为：O(kh)2) 。共六十二页10象空间消隐算法： 这类算法对屏幕上的每个象素进行判断(pndun)，以决定物体上哪个多边形在该象素 点上是可见的。若屏幕上有mn个象素点，每个物体表面上有h个多边形，则该类消隐算法计算量正比于mnh。 则： k个物体的算法复杂度为： O(mnkh) 。共六十二页 各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序(cx)。排序

6、次序(cx)影响算法的效率。 算法(sun f)排序共六十二页二、 消隐基本(jbn)技术 为了提高(t go)消隐算法的效率，各种消隐算法常采用一些有效的消隐基本算法。利用连贯性将透视投影转换成平行投影包围盒技术背面剔除空间分割技术物体分层表示共六十二页 物体(wt)连贯性面的连贯性 区域连贯性 扫描线的连贯性 深度连贯性 利用(lyng)连贯性 连贯性是指从一个事物到另一个事物，其属性值(如颜色值、空间位置)通常是平缓过渡的性质。例如： 棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换； 面的连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。共六十二页物体连贯性

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

8、比如，2D的矩形，3D的立方块、长方体、球等。目的： 避免盲目的求交测试； 各物体间的比较等。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。例：矩形包围盒及长方体包围盒提高算法效率共六十二页包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。可推广到面与面的遮挡快速判断。例如：两个空间多边形A、B在投影(tuyng)平面上的投影(tuyng)分别为A，B ，因为A 、B的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试。右图：包围盒相交，投影也相交；包围盒相交，投影不相交。AABB共六十二页 背面(bimin)剔除 外法

9、向 外法向与投影方向(fngxing)（观察方向(fngxing)）的夹角判断：前向面与后向面（背面）剔除依据： 物体表面是封闭的，背面总是被前向面所遮挡，从而始终是 不可见的。共六十二页法向向量N 视线向量V法向向量N 法向向量N 90 90共六十二页 视线-法线夹角法N 面的法向量(xingling)V 面上一点指向观察点的向量 = cos-1( )0= 时 可见 = 0N . V02共六十二页、空间(kngjin)分割技术依据：场景中的物体，它们的投影在投影平面上 是否有相互(xingh)遮挡的重叠部分？ 对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。方法：将投影平面上的窗

10、口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体可见时，只要对本区域的相关物体表中的物体进行比较即可。共六十二页复杂度比较： 假定每个小区域的相关物体表中平均有h个物体，场景中有k个物体，由于物体在场景中的分布是分散(fnsn)的，显然h远小于k。 根据物空间消隐方法所述，其算法复杂度为O(h2),远小于O(k2)。共六十二页 物体(wt)分层表示表示形式：模型(mxng)变换中的树形表示方式原理：减少场景中物体的个数，降低算法复杂度。方法： 将父节点所代表的物体看成子节点物体的包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点

11、做进一步测试。 父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。共六十二页 将透视(tush)投影转换成平行投影 消隐与透视关系较密切，体现在： 1）消隐必须在投影之前完成；因为消隐需要物体三维信息，投影后只有二维信息； 2）物体之间的遮挡关系与投影中心（视点(sh din)） 的选取有关； 3）物体之间的遮挡关系与投影方式有关，在平行投影时，其遮挡关系可通过深度值来确定。共六十二页 凸多面体的每个面要么(yo me)可见，要么(yo me)不可见；不可能出现一个面部分可见，部分不可见。xyz三、凸多面体隐藏(yncng)线的消除 凸多面体是由若干个平面围成的物体。假设这些平面方程为：

12、ai x+bi y+ci z+di=0 (i=1,2,n)调整系数的符号，使每个平面的法向量（ai,bi,ci）指向多面体内部。 如果投影方向为（Xp,Yp,Zp）,那么（ai,bi,ci）(Xp,Yp,Zp）0时，此平面为不可见面，在作图时，此面不绘制。共六十二页凸多面体消隐的基本原理表面外法线与其可见性的关系 设平面Pi上任一点(y din)的外法矢ni与该点的视线矢量vi的数量积： 从而有 其中i为ni与vi之间的夹角，i=1，2，m，这里m为平面数。共六十二页当 cosi0 ，即 0i /2 时，Pi为朝前面，为可见的，应该画出；当 cosi0 ，即 /2 face_zmax(i) T

13、hen face_zmax(i) = zz(line_p(j) Next jNext i 求各面最大Z坐标 XYZ0123456750共六十二页 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): fac

14、e_zmax(i) = face_zmax(L): face_zmax(L) = k End If Next i 对面表根据(gnj)最大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)共六十二

15、页For i = 0 To 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 计算(j sun)面多边形顶点的最大最小值 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 - yy(line_p(j)

16、 - 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两个面正轴测投影(tuyng)-消隐 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. 深度(shnd)缓冲

17、器算法(Z-buffer算法）Z缓冲器算法的基本思想是： 将投影平面每个像素所对应(duyng)的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。见图。 Z缓冲器算法基本思想S3S2S1(x,y)XvZvYv一种典型的、也是最简单的像空间消隐算法共六十二页帧缓存来存放每个象素的颜色值初值可放对应背景(bijng)颜色的值深度缓存来存放每个象素的深度值。初值取成z的极小值。Z缓冲器每个单元存放对应象素当前最近面的深度值帧缓冲器每个单元存放对应象素的颜色值屏幕(pngm)共六十二页深度(shnd)缓冲器算法算法描述深度(shnd)缓冲器所有单元均置为最小z值，

18、帧缓冲器各单元均置为背景色，然后逐个处理多边形表中的各面片。每扫描一行，计算该行各像素点（x，y）所对应的深度值z（x，y），并将结果与深度缓冲器中该像素单元所存储的深度值ZB（x，y）进行比较。若zZB（x，y）,则ZB（x，y）= z，同时将该像素的属性值I（x，y）写入帧缓冲器，即FB（x，y）= I（x，y）；否则不变。共六十二页算法(sun f)描述：for ( v= 0;vvmax;v+) for (u= 0; u Z缓冲器的第(u,v)单元的值) 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d; 共六十二页深度(shnd)缓冲器算法深度值的计

19、算若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面(pngmin)方程为：则多边形面上的点（x，y）所对应的深度值为： C0 共六十二页由于所有(suyu)扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。 深度计算共六十二页若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算： 沿多边形左边界递归计算边界上各点的坐标： m为该边的斜率(xil)，沿该边的深度也可以递归计算出来，即： 共六十二页如果该边是一条(y tio)垂直边界，则计算公式简化为： 对于每条扫描线，首先根据公式计算出与其相交的多边形最左边的交点所对应的深度值，然后，利用图形