计算机图形学第5讲图形消隐.ppt

1,图形消隐,2,图形消隐,基本概念提高消隐算法效率的常用方法画家算法Z缓冲器算法扫描线Z缓冲器算法OpenGL相关函数,3,问题投影变换失去了深度信息，往往导致图形的二义性及失去遮挡关系,失去遮挡关系,基本概念,基本概念,要消除二义性和保持遮挡关系，就必须在绘制（投影）时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线（HiddenLineRemoval）消除隐藏面（HiddenSurfaceRemoval）简称为消隐,4,5,消隐的对象三维物体三维体的表示主要采用边界（多边形）表示消隐结果与观察物体有关，也与视点位置和方向有关,线框图消隐图真实感图形,基本概念,6,消隐分类消除隐藏线：消除不可见线线框表示物体消除隐藏面：确定可见面（消除不可见面）表面表示物体,基本概念,7,基本概念,世界坐标系用户用来定义图形的坐标系，主要用于计算机图形场景中所有图形对象的空间定位和定义。观察坐标系可以在世界坐标系的任何位置、任何方向定义，通常以视点的位置为原点，通过用户指定的一个向上的观察向量来定义整个坐标系统。,8,基本概念,将世界坐标系中的三个坐标轴转换为与观察坐标系的三个坐标轴对应重合的逆变换平移变换，将观察参考点移到世界坐标系的原点处旋转变换，将u，v，n分别对应到x，y，z即绕x轴旋转角，绕y轴旋转角，绕z轴旋转角,消除隐藏线,体=n个面基本运算线线间求交运算线面间求交运算,9,消除隐藏线,平面对直线段的遮挡判断算法思路：先做简单判断，将计算量较大的判断留到后面做,10,消除隐藏线,(1)若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡(2)若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转7,11,消除隐藏线,(3)求直线与相应无穷平面的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。,12,P0,(4)求所剩线段的投影与平面边界投影的所有交点。若无交点，转5,13,P0,P1,P2,P3,P4,P5,(5)以上所求得的各交点将线段的投影分成若干段，求出第一段中点。(6)若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。,14,P0,P1,P2,P3,P4,P5,消除隐藏线,HiddenLineRemove()坐标变换；for(对每个面Fj)for(Fj的每一条边Ei)将二元组压入堆栈While(栈不空)=栈顶；for(j!=j0的每一个面Fj)if(Ei被Fj全部遮挡)将Ei清空；break;if(Ei被Fj部分遮挡)从Ei中将被遮挡的部分裁掉；if(Ei被分成若干段)取其中的一段作为当前Ei段；将其它段及相应的j压栈;if(Ei段不为空)显示Ei;,While(栈不空)=栈顶；for(j!=j0的每一个面Fj)if(Ei被Fj全部遮挡)将Ei清空；break;if(Ei被Fj部分遮挡)从Ei中将被遮挡的部分裁掉；if(Ei被分成若干段)取其中的一段作为当前Ei段；将其它段及相应的j压栈;if(Ei段不为空)显示Ei;,15,分治策略,简单的剔除,求每条边上的遮挡,16,面消隐算法分类投影窗口内的像素为处理单元确定最近点for(窗口内的每一个像素)确定距视点最近的物体，以该物体表面的颜色来显示像素,图像空间image-space,基本概念,17,面消隐算法分类（续）场景中的物体为处理单元物体上的面是否最近,for(场景中的每一个物体)将其与场景中的其它物体比较，确定其表面的可见部分；显示该物体表面的可见部分；,物体空间object-space,基本概念,18,提高消隐算法效率的常用方法,主要技术1.利用连贯性（SpatialCoherence）相邻物体的属性之间有一定的连贯性，其属性值通常是平缓过渡的，如颜色值、空间位置关系等包括：物体连贯性面的连贯性区域连贯性扫描线连贯性深度连贯性,19,提高消隐算法效率的常用方法,包围盒技术定义：一个形体的包围盒指的是包围它的简单形体两个条件包围盒充分紧密包围着形体对其的测试比较简单主要包围盒长方体正方体球,20,提高消隐算法效率的常用方法,作用避免盲目求交两个空间多边形A、B在投影平面上的投影分别为A，B，因为A、B的矩形包围盒不相交，则A、B不相交，无须进行遮挡测试一般情况下，判断两物体是否遮挡时，前一种情况大量存在，避免了物体间的复杂相交测试,21,提高消隐算法效率的常用方法,背面剔除外法向：规定每个多边形的外法向都是指向物体外部的前向面：若多边形的外法向与投影方向（观察方向）的夹角为钝角，称为前向面后向面：若多边形的外法向与投影方向（观察方向）的夹角为锐角，称为后向面（背面）,夹角为180u,投影方向,22,10.2提高消隐算法效率的常用方法,剔除依据：背面总是被前向面所遮挡，从而不可见,前向面后向面,JEAF、HCBG、JIHGF为后向面,C,G,N,V,n,V,n,23,提高消隐算法效率的常用方法,空间分割技术遮挡判断依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试原因：物体在场景中分散，有些物体的投影相距甚远，不会存在遮挡关系方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影与该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较,提高消隐算法效率的常用方法,将投影平面上的窗口分成若干小区域,24,25,提高消隐算法效率的常用方法,物体的分层表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，从而降低算法复杂度,26,方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试,10.2提高消隐算法效率的常用方法,27,背景画家作画：先画远景后画近景画家的作画顺序暗示出所画物体之间的相互遮挡关系,画家算法,28,算法基本思想：1）先把屏幕置成背景色2）将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体,画家算法,29,多边形的排序算法：根据深度排序深度zmin排序做一次初步排序保证zmin(P)nmin(Q)，需进一步判别:,画家算法,30,（A）若P,Q的投影P,Q的包围盒不相交，则P,Q在表中的次序不重要，不存在遮挡（B）对P,Q投影P,Q求交，若P,Q不相交，则P,Q在表中的次序不重要,画家算法,31,（C）若Q的所有顶点位于P所在平面的可见的一侧，则P,Q关系正确（D）若P的所有顶点位于Q所在平面的不可见的一侧，则P,Q关系正确,画家算法,32,问题不能处理多边形循环遮挡和多边形相互穿透解决方法：分割,画家算法,画家算法,33,34,又称ZBuffer算法(深度缓存depth-buffer)组成：帧缓冲器-保存各像素颜色值Z缓冲器-保存各像素处物体深度值,Z缓冲区算法,Z缓冲器中的单元与帧缓冲器中的单元一一对应,Z缓冲区算法,深度缓存depth-buffer,35,36,算法（1）先将Z-Buffer中个单元的初始值置为最小最小值代表无穷远（2）多边形扫描转换中，当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素原来的深度值如果大于说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色；同时保存深度值否则在当前像素处，当前多边形被前面所绘制的多边形遮挡了，像素的颜色值不改变,Z缓冲区算法,37,算法伪码帧缓存全置为背景色；深度缓存全置为最小Z值；for(每一个多边形)for(该多边形所覆盖的每个像素(x,y)计算该多边形在该像素的深度值Z(x,y);if(Z(x,y)大于Z缓存在(x,y)的值)把Z(x,y)存入Z缓存中(x,y)处；把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处；,Z缓冲区算法,38,特点Z-Buffer算法是所有图像空间算法中最简单的一种隐藏面消除算法。在像素级上以近物取代远物，与形体在屏幕上的出现顺序无关。优点简单稳定，利于硬件实现缺点需要一个额外的Z-Buffer，占用一定存储空间每个多边形占据的每个像素处都要计算深度值，计算量大,Z缓冲区算法,Z缓冲区算法,改进的Z缓冲区算法只用一个深度变量，无需深度缓存图像阅读点在多边形内,39,扫描线Z缓冲区算法,由来一般Z缓冲器算法中所需要的Z缓冲器容量较大扫描线Z缓冲器一般Z缓冲器算法未利用连续性计算深度多边形包含性测试多边形扫描转换扫描线算法避免包含性测试深度计算（增量算法）降低深度缓存空间,40,扫描线Z缓冲区算法,主要思想开一个一维数组作为当前扫描线的Z-buffer找出与当前扫描线相关的多边形，及每个多边形中相关的边对计算边对之间的深度增量算法若当前扫描像素可见计算像素颜色，写帧缓存更新深度缓存,41,扫描线Z缓冲区算法,数据结构（加速结构）单个多边形扫描转换算法边表（新边表、活性边表）扫描线Z-Buffer算法（多个多边形）边表活化边对表（AET）加入右边对信息，考虑扫描区间加入深度及其增量信息，用于增量算法活化多边形表考虑多个多边形多边形Y表存储多边形扫描线最大Y坐标,42,扫描线Z缓冲区算法,算法步骤与扫描线算法相似不同之处考虑多个多边形多边形外循环在每次循环结束前更新活化多边形表考虑深度信息在扫描每一对边中的像素时，用增量算法计算深度更新深度缓存,43,扫描线Z缓冲区算法,特点将整个绘图窗口内的消隐问题分解到一条条扫描线上解决，使所需的Z缓冲器大大减少计算深度值时，利用了面连贯性，只用了一个加法每个像素：计算N次深度值N为投影到该像素的多边形的个数,44,区间扫描线算法,进一步利用扫描线上的区间连贯性每个扫描线区间只计算一次深度值无需Z-Buffer思想要绘制深度最大多边形扫描线的上深度最大多边形在区间上是连贯的每个区间：找出深度最大的面区间的划分：由扫描线与多边形边界的交点确定,45,区间扫描线算法,如何获得区间上最大深度的面？区间上没有任何多边形：用背景色显示。区间上只有一个多边形：用对应多边形在该处的颜色显示区间上存在两个或两个以上的多边形？比较区间上采样点的深度,46,区间扫描线算法,如何获得区间上最大深度的面？区间上存在两个或两个以上的多边形？若允许多边形相互贯穿求两个多边形所在平面的交线求扫描线与交线投影的交点通过该交点将区间进一步细分,47,区间扫描线算法,特点：利用区间连贯性避免了每个像素上的多次深度计算通用性、可扩展性好可扩展应用到任意曲面体的消隐。,48,Warnock算法,JohnEdwardWarnock（1940-）美国计算机科学家图形学、出版行业先驱者犹他大学数学与哲学学士数学硕士电子工程博士Adobe公司共同创始人16年CEO经历，直到2001年退休领导了Camelot项目，PDF的前身1969年博士论文中提出用于消隐的Warnock算法,49,Warnock算法,思想：分治法将一个复杂情形分解为多个简单情形将大窗口的分解为小窗口如果小窗口足够简单，就显示大窗口：多个多边形投影相交小窗口很多情况下：单一多边形或多个多边形包围该窗口小窗口的下限：像素足够简单最坏情况：利用单个深度值的Z-Buffer算法,50,Warnock算法,如何分解？一个大窗口平均地分为4个与大窗口形状相似的小窗口四叉树,51,Warnock算法