《第5讲-计算机图形学消隐算法PPT课件.ppt》由会员分享，可在线阅读，更多相关《第5讲-计算机图形学消隐算法PPT课件.ppt（61页珍藏版）》请在三一文库上搜索。
1、1,消隐算法,主要内容:,一、概述 二、消隐的基本技术 三、凸多面体消除隐藏线 四、消除隐藏面,2,用计算机生成三维形体的真实图形，是计算机图形学研究 的重要内容之一。在使用显示设备描绘三维图形时，必须把三 维信息作某种投影变换，在二维显示表面上绘制出来。 由于投影变换失去了深度信息，往往导致图形的二义性：,要消除二义性，必须在绘制时消隐实际不可见得线和面， 即消隐。经过消隐的投影图称为物体的真实图形。,一、概述,3,消隐不仅与消隐对象有关，还与观察者的位置有关。如图所示，由于视点的位置不同，物体的可见部分也不同：,消隐与观察者的位置关系,4,按消隐的对象分类 线消隐（Hidden-line）
2、 面消隐（Hidden-surface） 按消隐空间分类 物体空间消隐算法 图像空间消隐算法,5,线消隐（Hidden-line） 消隐对象是物体上不可见的线，一般用于线框图。当用笔式绘图仪或其它画线设备绘制图形时，主要使用这种算法。 面消隐（Hidden-surface） 消隐对象是物体上不可见的面，一般用于填色图。当用光栅扫描显示器绘制图形时，主要使用这种算法。,早期图形显示器是用线条表示图形，消隐主要是消隐线问题。使用光栅显示器后，物体可用连续变化的色调来描述，消隐算法的研究渐渐转向消隐面的问题。,6,第一种是物空间算法。 它以三维场景中的物体对像作为处理单元的，在所有的对像之间进行比较
3、，除去完全不可见的的物体和物体上不可见的部分。常用于线框表示立体的线隐藏，也用于面隐藏。,for (场景中的每一个物体) 将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分； ,隐藏线（面）的消除的两种基本算法,特点是：算法可以达到相当高的精度。,7,第二种是像空间算法。 它以构成图形的每一个像素为处理单元的，确定场景中哪些表面的像素相对于观察点而言是可见的，用该表面的颜色填充该像素。常用于隐藏面。 特点是：算法精度低，只能达到屏幕精度为止，但速度往 往更高。 其算法是对每一个像素: 在和投影点到像素的连线相交的表面中找到离观察点最近的表面 用该表面上交点处的颜色填充该
4、像素。,for (窗口内的每一个像素) 确定距视点最近的物体，以该物体表 面的颜色来显示像素,8,算法复杂度,假设场景中有k个物体，平均每个物体表面 由h个多边形构成，显示区域中有m x n个像素， 则： 第一种算法的复杂度为： O(kh)(kh) 第二种算法的复杂度为：O(mnkh),9,物空间消隐算法: 需对物体表面的h个多边形中的每个面与其余h-1个面进行比较，精确地求出物体上每个棱边或每个面的遮挡关系。算法的计算量正比于h2，即算法复杂度为：O(h)2) 。 则：k个物体的算法复杂度为：O(kh)2) 。,10,象空间消隐算法： 这类算法对屏幕上的每个象素进行判断，以决定物体上哪个多边
5、形在该象素 点上是可见的。若屏幕上有mn个象素点，每个物体表面上有h个多边形，则该类消隐算法计算量正比于mnh。 则： k个物体的算法复杂度为： O(mnkh) 。,11,各种消隐算法均采用一定形式的几何排序。通过排序，可搜查出位置上靠近观察者的几何元素，确定几何元素之间在位置上的遮挡关系，解决消隐计算的主要问题。各种算法都有各自的排序方法和排序次序。排序次序影响算法的效率。,算法排序,12,二、 消隐基本技术,为了提高消隐算法的效率，各种消隐算法常 采用一些有效的消隐基本算法。,利用连贯性 将透视投影转换成平行投影 包围盒技术 背面剔除 空间分割技术 物体分层表示,13,物体连贯性 面的连贯
6、性 区域连贯性 扫描线的连贯性 深度连贯性,利用连贯性,连贯性是指从一个事物到另一个事物，其属性值(如颜色值、空间位置)通常是平缓过渡的性质。,例如： 棱边的连贯性是指：棱边的可见性在它与其他棱边相交时才发生变换； 面的连贯性是指：如果面的一部分是可见的，则一般情况下整个面都是可见的。,14,物体连贯性 若物体A与物体B是完全分离的，消隐时只需要比较两物体之间的遮挡关系即可，不需要对它们的表面多边形逐一进行测试； 面的连贯性 一张面内的各种属性值一般是缓慢变化的，可采用增量的形式对其进行计算； 区域连贯性 一个区域一般指屏幕上一组相邻的象素，他们通常为同一个可见面所占据，可见性相同； 扫描线的
7、连贯性 在相邻两条扫描线上，可见面的分布情况相似； 深度连贯性 同一表面上的相邻部分深度是相近的，而占据屏幕上同一区域的不同表面的深度不同，这样只需取其上一点计算出深度值，比较该深度值便能得出结果；,15,包围盒技术,一个形体的包围盒指的是包围它的简单形体。 比如，2D的矩形，3D的立方块、长方体、球等。,目的： 避免盲目的求交测试； 各物体间的比较等。,一个好的包围盒要具有两个条件： 包围和充分紧密包围着形体； 对其的测试比较简单。,例：矩形包围盒及长方体包围盒提高算法效率,16,包围盒不相交，线段和多边形也不相交，线段完全可见，无需就线段和多边形的遮挡关系进行进一步判断。可推广到面与面的遮
8、挡快速判断。 例如：两个空间多边形A、B在投影平面上的投影分别为A，B ，因为A 、B的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试。右图：包围盒相交，投影也相交；包围盒相交，投影不相交。,17,背面剔除,外法向 外法向与投影方向（观察方向）的夹角判断：前向面与后向面（背面）,剔除依据： 物体表面是封闭的，背面总是被前向面所遮挡，从而始终是 不可见的。,19,视线-法线夹角法 N 面的法向量 V 面上一点指向观察点的向量 = cos-1( ) 0= 时 可见 = = 时 不可见,N.V,|N|V|,20,、空间分割技术,依据：场景中的物体，它们的投影在投影平面上 是否有相互遮挡的重叠部分
9、？ 对于根本不存在相互遮挡关系的物体，应 避免这种不必要的测试。,方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影于该区域有相交部分；则在小区域中判断哪个物体可见时，只要对本区域的相关物体表中的物体进行比较即可。,21,复杂度比较： 假定每个小区域的相关物体表中平均有h个 物体，场景中有k个物体，由于物体在场景中的分 布是分散的，显然h远小于k。 根据物空间消隐方法所述，其算法复杂度为O(h2),远小于O(k2)。,22,物体分层表示,表示形式：模型变换中的树形表示方式 原理：减少场景中物体的个数，降低算法复杂度。,方法： 将父节点所代表的物体看成子节点物体的
10、包围盒，当两个父节点之间不存在遮挡关系时，就勿对两者的子节点做进一步测试。 父节点之间的遮挡关系可以用它们之间的包围盒进行预测试。,23,将透视投影转换成平行投影,消隐与透视关系较密切，体现在： 1）消隐必须在投影之前完成；因为消隐需要物体三维信息，投影后只有二维信息； 2）物体之间的遮挡关系与投影中心（视点） 的选取有关； 3）物体之间的遮挡关系与投影方式有关，在平行投影时，其遮挡关系可通过深度值来确定。,24,凸多面体的每个面要么可见，要么 不可见；不可能出现一个面部分可 见，部分不可见。,三、凸多面体隐藏线的消除,凸多面体是由若干个平面围成的物体。 假设这些平面方程为： ai x+bi
11、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为平面数。,26,当 cosi0 ，即 0i /2 时，Pi为朝前面，为可见的，应该画出； 当 cosi0 ，即 /2 i 时，Pi为朝后面，不可见，不画出或用虚线表示。 视
12、线方向与外法线的关系如图7-7。,视线方向与外法线的关系,27,视线矢量平行于某一基本坐标轴时夹角的计算： 当视线矢量vi平行于某一基本坐标轴时，那么平面的外法矢量nA，B，C与视线矢量的夹角就是外法矢量n与某一基本坐标轴的夹角，分别用、表示，视线矢量平行X、Y、Z轴时平面的外法矢量nA，B，C与坐标轴的夹角。,28,当视线矢量平行Z轴时，有 同理，若视线矢量平行X轴时，某平面的可见性由该平面外法矢量n在X轴的方向分量A所决定。 若视线矢量平行y轴时，某平面的可见性由该平面外法矢量n在Y轴的方向分量B所决定。,29,平面多边形的外法矢量的计算 为了判别物体上各表面是朝前面还是朝后面，需求出各表
13、面（平面多边形）指向物体外侧的法矢量。如图所示 。,物体表面外法矢量,30,在图中，平面P1P2P3的外法矢量 任意多边形法矢量的算法方法如下： 设法矢量 ，三个方向分量为： 式中：m为顶点号，若in，则j=i+1；否则i=m，j=1。,31,为避免在程序中出现两种计算外法矢量的方法，建议凸多边形也采用该算法进行计算。多边形所在的平面方程可写成： 其中： ， 为平面上任意一点。,32,算法实现的一般步骤 根据表面的数据结构，取顶点数据，计算表面的外法线矢量。 计算外法线在投影方向上的分量的值。 根据分量的值判断表面的可见性。 若表面可见画出该表面，否则处理下一个表面。,33,计算平面法向量,已
14、知平面上三个点的坐标为（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),34,如：投影面为XOY面，投影方向从 （0，0，10）到（10，-10，0）， 即（10，-10，-10）（斜投影）,0123面：（0，0，1）(10，-10，-10）=-10 不可见 4567
15、面：（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 不可见,35,实体模型数据结构之一,x=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,
16、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),面表,线表,顶点表,36,1. 画家算法(深度排序算法）,是同时运用物空间与像空间算法的操作，在物空间和像空间中完成排序，在像空间中完成扫描转换。 画家的作画时，先涂背景色，然后由远及近的将景物画上，顺序暗示出所画物体之间的相互遮挡关系。所以称为画家算法。 算法基本原理： 1）先把屏幕置成背景色； 2）将场景中的物体的各个面按其距观察点的远近进行排序，结果放在一张线性表中；（
17、线性表构造：距观察点远的优先级低，放在表头；距观察点近的优先级高，放在表尾 ）该表称为深度优先级表。 3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体表面。 也称：表优先级算法,四、消除隐藏面,37,深度优先级表的建立 、多边形优先级的考虑 首先对一个简单的画面，可以直接建立一个确定的深度优先表如图（a）所示。深度方向上无重叠。 当画面略微复杂一点，却无法按简单的Z向排序建立确定的深度优先表，以确定每一个多边形的优先级，如图（b）所示 。深度方向上有重叠,38,二、投影重叠判断： 测试按照难度递增顺序排列： 1. P和Q在oxy平面上投影的包围盒在x方向上不相交； 2. P和Q在oxy平
18、面上投影的包围盒在y方向上不相交； 3. P在Q之后。P的各顶点均在Q的远离视点的一侧； 4.Q在P之前。Q的各顶点均在P的靠近视点的一侧； 5. P和Q在观察平面oxy上的投影不相交； 上面5项只要有一项成立，P就不遮挡Q，不需要重新排序,39,对于1、2两种情况，可利用包围盒技术测试。 对于3、4两种情况，可根据“内外法”测试。即将S面的顶点坐标代入R面的方程：AX+BY+CZ+D，检查结果值的符号。一般使建立的平面方程的外法线方向正对着视点，如果结果值小于零，则表示S面在R面的内侧，即S面位于R面的后面结果值大于零，则表示S面在R面的外侧，即S面位于R面的前面。 测试1至4均为假，则需执
19、行测试5。 在XY平面上利用直线方程计算两表面边界的交点。但两表面在坐标范围x、y、z方向上均重叠，也有可能不相交。如图所示。,40,对于某一重叠表面，上述五项测试均不成立，则需在有序表中调换两个面的位置。,调换两个面的位置后，需要对调换过顺序的表面重复上述5项测试。,41,对于两个或多个表面循环遮挡，该算法可能导致无限循环。此时，算法反复将重叠表面的位置进行组合。为避免死循环。可对调至更远处的表面进行标识。 执行重排序后，若某个面的位置需再次交换，则表明存在交叉覆盖的情况，如图所示，将P沿Q所在平面分割成两部分P1和P2，从表中去掉原多边形P，而将P的这两个新的部分插入原表中的适当位置，使其
20、仍保持按Zmin排序的性质。对新形成的表，重新执行第二步。,42,无法直接建立正确的深度优先表。,解决方法是沿多边形所在平面间的交线循环分割这些多边形。,43,排序计算量大； 多边形相交或循环重叠时，必须分割多边形。,画家算法的不足：,44,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,
21、 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) For i = 0 To 7 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(
22、rx) Next i 各顶点绕X轴和Y轴的旋转变换 For i = 0 To 5 face_zmax(i) = 0 For j = face_s(i) To face_e(i) - 1 If zz(line_p(j) face_zmax(i) Then face_zmax(i) = zz(line_p(j) Next j Next i 求各面最大Z坐标,45,For i = 0 To 5 L = i For m = i + 1 To 5 If (face_zmax(m) i) Then k = face_s(i): face_s(i) = face_s(L): face_s(L) = k k
23、= face_e(i): face_e(i) = face_e(L): face_e(L) = k k = face_zmax(i): face_zmax(i) = face_zmax(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
24、= Array(29, 14, 4, 9, 19, 24) face_zmax=Array(22,54,68,90,90,90),46,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 计算面多边形顶点的最大最小值 For h = ymin To ymax 扫描线循环 k = 0 For j = face_s(i) To face_e(i) - 1 面多边形的边循环 If Int(
25、yy(line_p(j + 1) Int(yy(line_p(j) Then t = (h - yy(line_p(j) - 0.5) / (yy(line_p(j + 1) - yy(line_p(j) If (t = 0 And t = 1) Then xjd(k) = xx(line_p(j) + (xx(line_p(j + 1) - xx(line_p(j) * t yjd(k) = h ： k = k + 1 计算扫描线与边的交点 End If End If Next Picture1.Line (xjd(0), yjd(0)-(xjd(1), yjd(1),RGB(face_s(
26、i) * 10, 50, 100) Next Next,47,正轴测投影(一个面正投影）,x = Array(0, 50, 50, 0, 0) y = Array(0, 0, 50, 50, 0) z = Array(50, 50,50, 50,50) for i=0 to 3 picture1.line(x(i),y(i)-(x(i+1),y(i+1) next,48,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)*
27、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) for i=0 to 4 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)*
28、Cos(rx) next for i=0 to 3 picture1.line(xx(i),yy(i)-(xx(i+1),yy(i+1) next,一个面正轴测投影,49,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) for i=0 to 9 xx(i)=x(i) * Cos(ry) + z(i) * Sin(ry) yy(i)= x(i)*Sin(ry)
29、*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) next for j=0 to 1 for i=fs(j) to fe(j)-1 picture1.line(xx(i),yy(i)-(xx(i+1),yy(i+1) next endif,两个面正轴测投影,50,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(5
30、0, 50,50, 50,50,0,0,50,50,0) fs=Array(0,5)：fe=Array(4,9) for i=0 to 9 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) next for j=0 to 1 c=(xx(fs(j)+1)- xx(fs(j)*(yy(fs(j)+2)- yy(fs(j)-(
31、xx(fs(j)+2)- xx(fs(j)*(yy(fs(j)+1)- yy(fs(j) if (-c0)then for i=fs(j) to fe(j)-1 picture1.line(xx(i),yy(i)-(xx(i+1),yy(i+1) next endif endif,两个面正轴测投影-消隐,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),51,2. 深度缓冲器算法(Z-buffer算法）,Z缓冲器
32、算法的基本思想是： 将投影平面每个像素所对应的所有面片（平面或曲面）的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。见图。 Z缓冲器算法基本思想,一种典型的、也是最简单的像空间消隐算法,52,帧缓存来存放每个象素的颜色值 初值可放对应背景颜色的值 深度缓存来存放每个象素的深度值。 初值取成z的极小值。,屏幕,53,深度缓冲器算法,算法描述 深度缓冲器所有单元均置为最小z值，帧缓冲器各单元均置为背景色，然后逐个处理多边形表中的各面片。 每扫描一行，计算该行各像素点（x，y）所对应的深度值z（x，y），并将结果与深度缓冲器中该像素单元所存储的深度值ZB（x，y）进行比较。 若zZB
33、（x，y）,则ZB（x，y）= z，同时将该像素的属性值I（x，y）写入帧缓冲器，即FB（x，y）= I（x，y）；否则不变。,54,算法描述：,for ( v= 0;vvmax;v+) for (u= 0; uumax; u+) 将帧缓冲器的第(u,v)单元置为背景色； 将Z缓冲器的第(u,v)单元置为-1(可见的最小深度值) ,for (每个多边形） for (多边形在投影平面上的投影区域内的每个像素(u,v) ) 计算多边形在当前像素(u,v)处的深度值d； if (d Z缓冲器的第(u,v)单元的值) 置帧缓冲器的第(u,v)单元值为当前多边形颜色； 置Z缓冲器的第(u,v)单元值为d
34、; ,55,深度缓冲器算法,深度值的计算 若已知多边形的方程，则可用增量法计算扫描线每一个像素的深度。设平面方程为： 则多边形面上的点（x，y）所对应的深度值为：,C0,56,由于所有扫描线上相邻点间的水平间距为1个像素单位，扫描线行与行之间的垂直间距也为1。因此可以利用这种连贯性来简化计算过程，如图所示。 深度计算,57,若已计算出（x，y）点的深度值为zi，沿x方向相邻连贯点（x+1，y）的深度值zi+1可由下式计算： 沿多边形左边界递归计算边界上各点的坐标： m为该边的斜率，沿该边的深度也可以递归计算出来，即：,58,如果该边是一条垂直边界，则计算公式简化为： 对于每条扫描线，首先根据公
35、式计算出与其相交的多边形最左边的交点所对应的深度值，然后，利用图形连贯性将该扫描线上所有的后续点计算出来。 所有的多边形处理完毕，即得消隐后的图形。,59,优点：1. 简单稳定，利于硬件实现 2. Z缓冲器算法的最大优点 ：Z-Buffer算法在象素级上以近物取代远物。形体在屏幕上的出现顺序是无关紧要的。可以轻而易举地处理隐藏面以及显示复杂曲面之间的交线。 缺点：1）需要一个额外的Z 缓冲器 2）在每个多边形占据的每个像素处都要 计算深度值，计算量大,60,3、扫描线算法,每个单元存放对应象素 当前最近面的深度值,（每一个扫描线用一个缓冲器）,61,方程：z=100,Z=(4x-12),0,4,10,10,10,10,10,12,16,20,10,10,10,10,10,12,16,20,16,20,20,