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

地球科学与信息物理学院GIS中心1图形消隐2图形消隐基本概念提高消隐算法效率的常用方法画家算法Z缓冲器算法扫描线Z缓冲器算法OpenGL相关函数3问题投影变换失去了深度信息，往往导致图形的二义性及失去遮挡关系失去遮挡关系基本概念基本概念要消除二义性和保持遮挡关系，就必须在绘制（投影）时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线（HiddenLineRemoval）消除隐藏面（HiddenSurfaceRemoval）简称为消隐45消隐的对象三维物体三维体的表示主要采用边界（多边形）表示消隐结果与观察物体有关，也与视点位置和方向有关线框图消隐图真实感图形基本概念6消隐分类消除隐藏线：消除不可见线——线框表示物体消除隐藏面：确定可见面（消除不可见面）——表面表示物体基本概念7基本概念世界坐标系用户用来定义图形的坐标系，主要用于计算机图形场景中所有图形对象的空间定位和定义。观察坐标系可以在世界坐标系的任何位置、任何方向定义，通常以视点的位置为原点，通过用户指定的一个向上的观察向量来定义整个坐标系统。unvP0(x0,y0,z0)xyz8基本概念将世界坐标系中的三个坐标轴转换为与观察坐标系的三个坐标轴对应重合的逆变换平移变换，将观察参考点移到世界坐标系的原点处旋转变换，将u，v，n分别对应到x，y，z即绕x轴旋转角，绕y轴旋转角，绕z轴旋转角1000010000cossin00sincos10000cos0sin00100sin0cos10000cossin00sincos000012T10100001000010001zyxT消除隐藏线体=n个面基本运算线线间求交运算线面间求交运算9消除隐藏线平面对直线段的遮挡判断算法思路：先做简单判断，将计算量较大的判断留到后面做10消除隐藏线(1)若线段的两端点及视点在给定平面的同侧，线段不被给定平面遮挡(2)若线段的投影与平面投影的包围盒无交，线段不被给定平面遮挡，转711消除隐藏线(3)求直线与相应无穷平面的交。若无交点，转4。否则，交点在线段内部或外部。若交点在线段内部，交点将线段分成两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4再判；若交点在线段外部，转4。12P0(4)求所剩线段的投影与平面边界投影的所有交点。若无交点，转513P0P1P2P3P4P5(5)以上所求得的各交点将线段的投影分成若干段，求出第一段中点。(6)若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值进行判断。14P0P1P2P3P4P5消除隐藏线HiddenLineRemove(){坐标变换；for(对每个面Fj)for(Fj的每一条边Ei)将二元组Ei,j压入堆栈While(栈不空){Ei,j0=栈顶；for(j!=j0的每一个面Fj){if(Ei被Fj全部遮挡){将Ei清空；break;}if(Ei被Fj部分遮挡){从Ei中将被遮挡的部分裁掉；if(Ei被分成若干段){取其中的一段作为当前Ei段；将其它段及相应的j压栈;}}}if(Ei段不为空)显示Ei;}}While(栈不空){Ei,j0=栈顶；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提高消隐算法效率的常用方法背面剔除外法向：规定每个多边形的外法向都是指向物体外部的前向面：若多边形的外法向与投影方向（观察方向）的夹角为钝角，称为前向面后向面：若多边形的外法向与投影方向（观察方向）的夹角为锐角，称为后向面（背面）夹角为180－u投影方向2210.2提高消隐算法效率的常用方法剔除依据：背面总是被前向面所遮挡，从而不可见前向面后向面JEAF、HCBG、JIHGF为后向面CGVABDEFHIJNVnVn23提高消隐算法效率的常用方法空间分割技术遮挡判断依据：场景中的物体，它们的投影在投影平面上是否有重叠部分？对于根本不存在相互遮挡关系的物体，应避免这种不必要的测试原因：物体在场景中分散，有些物体的投影相距甚远，不会存在遮挡关系方法：将投影平面上的窗口分成若干小区域；为每个小区域建立相关物体表，表中物体的投影与该区域有相交部分；则在小区域中判断那个物体可见时，只要对该区域的相关物体表中的物体进行比较提高消隐算法效率的常用方法将投影平面上的窗口分成若干小区域2425提高消隐算法效率的常用方法物体的分层表示表示形式：模型变换中的树形表示方式原理：减少场景中物体的个数，从而降低算法复杂度26方法：将父节点所代表的物体看成子节点所代表物体的包围盒，当两个父节点之间不存在遮挡关系时，就没有必要对两者的子节点做进一步测试。父节点之间的遮挡关系可以用它们之间的包围盒进行预测试10.2提高消隐算法效率的常用方法27背景画家作画：先画远景后画近景画家的作画顺序暗示出所画物体之间的相互遮挡关系画家算法28算法基本思想：1）先把屏幕置成背景色2）将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾3）然后按照从远到近（从表头到表尾）的顺序逐个绘制物体画家算法29多边形的排序算法：根据深度排序深度zmin排序做一次初步排序保证zmin(P)zmin(Q),具体判别P,Q之间的关系zmax(P)zmin(Q),则多边形P的确距观察点最远，Q不可能遮挡别的多边形Pnmax(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问题不能处理多边形循环遮挡和多边形相互穿透解决方法：分割画家算法画家算法3334又称Z－Buffer算法(深度缓存depth-buffer)组成：帧缓冲器--保存各像素颜色值Z缓冲器--保存各像素处物体深度值Z缓冲区算法Z缓冲器中的单元与帧缓冲器中的单元一一对应Z缓冲区算法深度缓存depth-buffer3536算法（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区间扫描线算法特点：利用区间连贯性避免了每个像素上的多次深度计算通用性、可扩展性好可扩展应用到任意曲面体的消隐。48Warnock算法JohnEdwardWarnock（1940-）美国计算机科学家图形学、出版行业先驱者犹他大学数学与哲学学士数学硕士电子工程博士Adobe公司共同创始人16年CEO经历，直到2001年退休领导了Camelot项目，PDF