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

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