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

消隐算法主要内容:

一、概述二、消隐的基本技术三、凸多面体消除隐藏线四、消除隐藏面

用计算机生成三维形体的真实图形，是计算机图形学研究的重要内容之一。在使用显示设备描绘三维图形时，必须把三维信息作某种投影变换，在二维显示表面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性：

要消除二义性，必须在绘制时消隐实际不可见得线和面，即消隐。经过消隐的投影图称为物体的真实图形。一、概述消隐不仅与消隐对象有关，还与观察者的位置有关。如图所示，由于视点的位置不同，物体的可见部分也不同：消隐与观察者的位置关系按消隐的对象分类线消隐（Hidden-line）面消隐（Hidden-surface）按消隐空间分类物体空间消隐算法图像空间消隐算法线消隐（Hidden-line）消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或其它画线设备绘制图形时，主要使用这种算法。面消隐（Hidden-surface）消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示器绘制图形时，主要使用这种算法。

早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续变化的色调来描述，消隐算法的研究渐渐转向消隐面的问题。

第一种是物空间算法。它以三维场景中的物体对像作为处理单元的，在所有的对像之间进行比较，除去完全不可见的的物体和物体上不可见的部分。常用于线框表示立体的线隐藏，也用于面隐藏。for(场景中的每一个物体){将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；}隐藏线（面）的消除的两种基本算法特点是：算法可以达到相当高的精度。

第二种是像空间算法。它以构成图形的每一个像素为处理单元的，确定场景中哪些表面的像素相对于观察点而言是可见的，用该表面的颜色填充该像素。常用于隐藏面。特点是：算法精度低，只能达到屏幕精度为止，但速度往往更高。

其算法是对每一个像素:在和投影点到像素的连线相交的表面中找到离观察点最近的表面用该表面上交点处的颜色填充该像素。

for(窗口内的每一个像素) {确定距视点最近的物体，以该物体表面的颜色来显示像素}算法复杂度假设场景中有k个物体，平均每个物体表面由h个多边形构成，显示区域中有mxn个像素，则：第一种算法的复杂度为：O((kh)×(kh))

第二种算法的复杂度为：O(mnkh)9物空间消隐算法:需对物体表面的h个多边形中的每个面与其余h-1个面进行比较，精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正比于h2，即算法复杂度为：O((h)2)

。则：k个物体的算法复杂度为：O((kh)2)

。10象空间消隐算法：这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边形在该象素点上是可见的。若屏幕上有m×n个象素点，每个物体表面上有h个多边形，则该类消隐算法计算量正比于mnh。则：k个物体的算法复杂度为：O(mnkh)

。各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次序影响算法的效率。算法排序二、消隐基本技术为了提高消隐算法的效率，各种消隐算法常采用一些有效的消隐基本算法。利用连贯性将透视投影转换成平行投影包围盒技术背面剔除空间分割技术物体分层表示物体连贯性 面的连贯性区域连贯性扫描线的连贯性 深度连贯性利用连贯性连贯性是指从一个事物到另一个事物，其属性值(如颜色值、空间位置)通常是平缓过渡的性质。例如：

棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换；

面的连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。物体连贯性若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需要对它们的表面多边形逐一进行测试；

面的连贯性一张面内的各种属性值一般是缓慢变化的，可采用增量的形式对其进行计算；

区域连贯性一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相同；

扫描线的连贯性在相邻两条扫描线上，可见面的分布情况相似；

深度连贯性同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同，这样只需取其上一点计算出深度值，比较该深度值便能得出结果；

包围盒技术一个形体的包围盒指的是包围它的简单形体。比如，2D的矩形，3D的立方块、长方体、球等。目的：避免盲目的求交测试； 各物体间的比较等。一个好的包围盒要具有两个条件：包围和充分紧密包围着形体；对其的测试比较简单。例：矩形包围盒及长方体包围盒提高算法效率包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。可推广到面与面的遮挡快速判断。例如：两个空间多边形A、B在投影平面上的投影分别为A’，B’

，因为A’

、B’的矩形包围盒不相交，则A’、B’不相交，无须进行遮挡测试。右图：包围盒相交，投影也相交；包围盒相交，投影不相交。AA’BB’背面剔除

外法向 外法向与投影方向（观察方向）的夹角判断：前向面与后向面（背面）剔除依据：物体表面是封闭的，背面总是被前向面所遮挡，从而始终是不可见的。法向向量N

视线向量V法向向量N

法向向量N<90°<90°可见可见

不可见>90°视线-法线夹角法N

面的法向量V

面上一点指向观察点的向量=cos-1()0<=<时可见<=<=时不可见2N.V|N||V|N.V>0N.V<02、空间分割技术依据：场景中的物体，它们的投影在投影平面上是否有相互遮挡的重叠部分？对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试。方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体可见时，只要对本区域的相关物体表中的物体进行比较即可。复杂度比较：假定每个小区域的相关物体表中平均有h个物体，场景中有k个物体，由于物体在场景中的分布是分散的，显然h远小于k。根据物空间消隐方法所述，其算法复杂度为O(h2),远小于O(k2)。物体分层表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，降低算法复杂度。方法：将父节点所代表的物体看成子节点物体的包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。将透视投影转换成平行投影消隐与透视关系较密切，体现在：

1）消隐必须在投影之前完成；因为消隐需要物体三维信息，投影后只有二维信息；2）物体之间的遮挡关系与投影中心（视点）的选取有关；3）物体之间的遮挡关系与投影方式有关，在平行投影时，其遮挡关系可通过深度值来确定。凸多面体的每个面要么可见，要么不可见；不可能出现一个面部分可见，部分不可见。xyz三、凸多面体隐藏线的消除凸多面体是由若干个平面围成的物体。假设这些平面方程为：

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上任一点的外法矢ni与该点的视线矢量vi的数量积：

从而有

其中θi为ni与vi之间的夹角，i=1，2，…，m，这里m为平面数。当

cosθi≥0

，即0≤θi≤π/2时，Pi为朝前面，为可见的，应该画出；当cosθi<0，即π/2

<θi≤π时，Pi为朝后面，不可见，不画出或用虚线表示。视线方向与外法线的关系如图7-7。视线方向与外法线的关系

视线矢量平行于某一基本坐标轴时夹角的计算：

当视线矢量vi平行于某一基本坐标轴时，那么平面的外法矢量n{A，B，C}与视线矢量的夹角就是外法矢量n与某一基本坐标轴的夹角，分别用α、β、γ表示，视线矢量平行X、Y、Z轴时平面的外法矢量n{A，B，C}与坐标轴的夹角。当视线矢量平行Z轴时，有同理，若视线矢量平行X轴时，某平面的可见性由该平面外法矢量n在X轴的方向分量A所决定。若视线矢量平行y轴时，某平面的可见性由该平面外法矢量n在Y轴的方向分量B所决定。平面多边形的外法矢量的计算为了判别物体上各表面是朝前面还是朝后面，需求出各表面（平面多边形）指向物体外侧的法矢量。如图所示。物体表面外法矢量在图中，平面P1P2P3的外法矢量·任意多边形法矢量的算法方法如下：设法矢量，三个方向分量为：

式中：m为顶点号，若i≠n，则j=i+1；否则i=m，j=1。为避免在程序中出现两种计算外法矢量的方法，建议凸多边形也采用该算法进行计算。多边形所在的平面方程可写成：

其中：，为平面上任意一点。算法实现的一般步骤根据表面的数据结构，取顶点数据，计算表面的外法线矢量。计算外法线在投影方向上的分量的值。根据分量的值判断表面的可见性。若表面可见画出该表面，否则处理下一个表面。计算平面法向量已知平面上三个点的坐标为（x1,y1,z1)、（x2,y2,z2)、（x3,y3,z3)，其顺序符合右手规则，其大姆指所指方向为该平面的法向量（a,b,c),则：

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)如：投影面为XOY面，投影方向从（0，0，10）到（10，-10，0），即（10，-10，-10）（斜投影）0123面：（0，0，1）·(10，-10，-10）=-10不可见4567面：（0，0，-1）·(10，-10，-10）=10可见0145面：（0，1，0）·(10，-10，-10）=-10不可见2367面：（0，-1，0）·(10，-10，-10）=10可见0374面：（1，0，0）·(10，-10，-10）=10可见1256面：（-1，0，0）·(10，-10，-10）=-10不可见XZ01234567Y实体模型数据结构之一000100001002000020000030010003001002003000200300

xyz01234567045910141519202425290123450123076547...0123456789..XZ01234567Yx=array(0,100,100,0,0,100,100,0)y=array(0,0,200,200,0,0,200,200)z=array(0,0,0,0,300,300,300,300)line_p=array(0,1,2,3,0,7,6,5,4,7,1,5,6,2,1,0,3,7,4,0,6,7,3,2,6,4,5,1,0,4)face_s=array(0,5,10,15,20,25)face_e=array(4,9,14,19,24,29)面表线表顶点表1.画家算法(深度排序算法）是同时运用物空间与像空间算法的操作，在物空间和像空间中完成排序，在像空间中完成扫描转换。画家的作画时，先涂背景色，然后由远及近的将景物画上，顺序暗示出所画物体之间的相互遮挡关系。所以称为画家算法。算法基本原理：1）先把屏幕置成背景色；2）将场景中的物体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾）该表称为深度优先级表。3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。也称：表优先级算法四、消除隐藏面深度优先级表的建立、多边形优先级的考虑首先对一个简单的画面，可以直接建立一个确定的深度优先表如图（a）所示。深度方向上无重叠。当画面略微复杂一点，却无法按简单的Z向排序建立确定的深度优先表，以确定每一个多边形的优先级，如图（b）所示。深度方向上有重叠QXZPRQXZP（a）（b）二、投影重叠判断：测试按照难度递增顺序排列：1.P和Q在oxy平面上投影的包围盒在x方向上不相交；2.P和Q在oxy平面上投影的包围盒在y方向上不相交；3.P在Q之后。P的各顶点均在Q的远离视点的一侧；4.Q在P之前。Q的各顶点均在P的靠近视点的一侧；5.P和Q在观察平面oxy上的投影不相交；上面5项只要有一项成立，P就不遮挡Q，不需要重新排序yyy对于1、2两种情况，可利用包围盒技术测试。对于3、4两种情况，可根据“内外法”测试。即将S面的顶点坐标代入R面的方程：AX+BY+CZ+D，检查结果值的符号。一般使建立的平面方程的外法线方向正对着视点，如果结果值小于零，则表示S面在R面的内侧，即S面位于R面的后面‘结果值大于零，则表示S面在R面的外侧，即S面位于R面的前面。测试1至4均为假，则需执行测试5。在XY平面上利用直线方程计算两表面边界的交点。但两表面在坐标范围x、y、z方向上均重叠，也有可能不相交。如图所示。对于某一重叠表面，上述五项测试均不成立，则需在有序表中调换两个面的位置。S,S,S

S,S,SSSSzS,S

S,S有重叠SS调换两个面的位置后，需要对调换过顺序的表面重复上述5项测试。。对于两个或多个表面循环遮挡，该算法可能导致无限循环。此时，算法反复将重叠表面的位置进行组合。为避免死循环。可对调至更远处的表面进行标识。执行重排序后，若某个面的位置需再次交换，则表明存在交叉覆盖的情况，如图所示，将P沿Q所在平面分割成两部分P1和P2，从表中去掉原多边形P，而将P的这两个新的部分插入原表中的适当位置，使其仍保持按Zmin排序的性质。对新形成的表，重新执行第二步。无法直接建立正确的深度优先表。解决方法是沿多边形所在平面间的交线循环分割这些多边形。排序计算量大；多边形相交或循环重叠时，必须分割多边形。画家算法的不足：x=Array(0,80,80,0,0,80,80,0)y=Array(0,0,80,80,0,0,80,80)8个顶点的X。、Y、Z坐标z=Array(0,0,0,0,80,80,80,80)line_p=Array(0,1,2,3,0,7,6,5,4,7,1,5,6,2,1,0,3,7,4,0,6,7,3,2,6,4,5,1,0,4)face_s=Array(0,5,10,15,20,25)face_e=Array(4,9,14,19,24,29)Fori=0To7

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)Nexti‘各顶点绕X轴和Y轴的旋转变换Fori=0To5face_zmax(i)=0Forj=face_s(i)Toface_e(i)-1Ifzz(line_p(j))>face_zmax(i)Thenface_zmax(i)=zz(line_p(j))NextjNexti‘求各面最大Z坐标

XYZ0123456750Fori=0To5L=iForm=i+1To5If(face_zmax(m)<face_zmax(L))ThenL=mNextmIf(L<>i)Thenk=face_s(i):face_s(i)=face_s(L):face_s(L)=kk=face_e(i):face_e(i)=face_e(L):face_e(L)=kk=face_zmax(i):face_zmax(i)=face_zmax(L):face_zmax(L)=kEndIfNexti

‘对面表根据最大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)Fori=0To5‘多边形面循环

ymin=10000:ymax=0

Forj=face_s(i)Toface_e(i)-1If(yy(line_p(j))<ymin)Thenymin=yy(line_p(j))If(yy(line_p(j))>ymax)Thenymax=yy(line_p(j))

Next

‘计算面多边形顶点的最大最小值

Forh=yminToymax

‘扫描线循环

k=0

Forj=face_s(i)Toface_e(i)-1‘面多边形的边循环

IfInt(yy(line_p(j+1)))<>Int(yy(line_p(j)))Thent=(h-yy(line_p(j))-0.5)/(yy(line_p(j+1))-yy(line_p(j)))If(t>=0Andt<=1)Then

xjd(k)=xx(line_p(j))+(xx(line_p(j+1))-xx(line_p(j)))*tyjd(k)=h：k=k+1

‘计算扫描线与边的交点

EndIfEndIf

Next

Picture1.Line(xjd(0),yjd(0))-(xjd(1),yjd(1)),RGB(face_s(i)*10,50,100)

NextNext正轴测投影(一个面正投影）XYZ0123456750x=Array(0,50,50,0,0)y=Array(0,0,50,50,0)z=Array(50,50,50,50,50)fori=0to3picture1.line(x(i),y(i))-(x(i+1),y(i+1))nextxx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)x=Array(0,50,50,0,0)y=Array(0,0,50,50,0)z=Array(50,50,50,50,50)fori=0to4

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextfori=0to3picture1.line(xx(i),yy(i))-(xx(i+1),yy(i+1))next一个面正轴测投影XYZ0123456750x=Array(0,0,50,50,0,0,0,0,0,0)y=Array(0,50,50,0,0,0,50,50,0,0)z=Array(50,50,50,50,50,0,0,50,50,0)fs=Array(0,5)fe=Array(4,9)fori=0to9

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextforj=0to1fori=fs(j)tofe(j)-1picture1.line(xx(i),yy(i))-(xx(i+1),yy(i+1))nextendif两个面正轴测投影x=Array(0,0,50,50,0,0,0,0,0,0)y=Array(0,50,50,0,0,0,50,50,0,0)z=Array(50,50,50,50,50,0,0,50,50,0)fs=Array(0,5)：fe=Array(4,9)fori=0to9

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextforj=0to1

c=(xx(fs(j)+1)-xx(fs(j)))*(yy(fs(j)+2)-yy(fs(j)))-(xx(fs(j)+2)-xx(fs(j)))*(yy(fs(j)+1)-yy(fs(j)))

if(-c>0)thenfori=fs(j)tofe(j)-1picture1.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.深度缓冲器算法(Z-buffer算法）Z缓冲器算法的基本思想是：

将投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。见图。

Z缓冲器算法基本思想S3S2S1(x,y)XvZvYv一种典型的、也是最简单的像空间消隐算法帧缓存来存放每个象素的颜色值初值可放对应背景颜色的值深度缓存来存放每个象素的深度值。初值取成z的极小值。Z缓冲器每个单元存放对应象素当前最近面的深度值帧缓冲器每个单元存放对应象素的颜色值屏幕深度缓冲器算法算法描述深度缓冲器所有单元均置为最小z值，帧缓冲器各单元均置为背景色，然后逐个处理多边形表中的各面片。每扫描一行，计算该行各像素点（x，y）所对应的深度值z（x，y），并将结果与深度缓冲器中该像素单元所存储的深度值ZB（x，y）进行比较。若z＞ZB（x，y）,则ZB（x，y）=z，同时将该像素的属性值I（x，y）写入帧缓冲器，即FB（x，y）