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