第七章隐藏面的消除.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 隐藏面的消除,基本概念,提高消隐算法效率的常用方法,画家算法,Z,缓冲器算法,扫描线,Z,缓冲器算法,扫描线算法,区域子分算法,光线投射算法,基本概念（,1/3,）,空间遮挡关系,隐藏面与隐藏线、可见面与可见线,基本概念（,2/3,）,表面模型,-,面消隐,线框模型,-,线消隐,两类方法（算法复杂性）,方法一：以像素为处理单元,for(,窗口内的每一个像素）,确定据视点最近的物体（可见性判断）；,用该物体表面的颜色显示像素；,基本概念（,3/3,）,方法二：以场景中物体为处理单元,for(,场景中的每一个物体）,将该物体与场景中的其它物体进行比较，确定其表面的可见部分；,显示该物体表面的可见部分；,提高消隐算法效率的常用方法,利用连贯性,物体的连贯性,面的连贯性,区域的连贯性,扫描线的连贯性,深度的连贯性,提高消隐算法效率的常用方法,将透视投影变换为平行投影,消隐与投影方式有关,提高消隐算法效率的常用方法,在平行投影方式下，物体遮挡关系的确定,提高消隐算法效率的常用方法,在透视投影方式下，物体遮挡关系的确定,提高消隐算法效率的常用方法,包含消隐的三维图形显示流程图,提高消隐算法效率的常用方法,包围盒技术,包围盒,-,包围目标的简单形体,包围,简单,常用的包围盒,长方体,球,圆柱,提高消隐算法效率的常用方法,应用,避免盲目求交,提高消隐算法效率的常用方法,背面剔除,前向面与后向面（背面）,背面是不可见的,提高消隐算法效率的常用方法,空间分割技术,提高消隐算法效率的常用方法,物体的分层表示,消隐的基本（核心）问题,排序,整体排序：画家算法,点排序：,Z-Buffer,算法、光线投射算法,区间排序：扫描线算法,区域排序：区域子分算法,画家算法（,1/6,）,画家作画,画家算法（,2/6,）,画家算法,建立深度优先级表,画家消隐算法,对场景中的多边形按深度进行排序，,形成深度优先级表；,按从远到近的顺序显示多边形；,画家算法（,3/6,）,排序,一维空间（数轴）上点的排序,画家算法（,4/6,）,二维平面上直线段的排序,在规范观察坐标系,uvn,下，观察方向，,n,的负方向，,n,坐标大者距观察者更近。记,n,max,(P),n,min,(P),为多边形,P,的各个顶点,n,坐标的最大值和最小值。,排序算法概述：,(1),场景中所有多边形存入一个线性表（链表或数组）,L,中；,(2),如果,L,中仅有一个多边形，算法结束；否则根据每个多边形的,nmix,对他们进行预排序，不妨假定,P,落在表首，即,n,min,(P),，再记,Q,为,L,P,中的任一个。,(3),判别,P,和,Q,的关系,对所有的,Q,，有,n,max,(P)n,min,(Q),，进一步判断四种情况：,见图,三维空间中多边形的排序,（,a,）在投影平面上的投影,P,Q,不相交，,L=L-P,返回,(2),；否则进行下一步：,（,b,）,P,的所有顶点位于,Q,的平面不可见一侧，,P,Q,的关系正确，,L=L-P,返回,(2),；否则进行下一步：,（,c,）,Q,的所有顶点位于,P,的平面可见一侧，,P,Q,的关系正确，,L=L-P,返回,(2),；否则进行下一步：,（,d,）对投影,P,与,Q,求交，如果不相交，无顺序要求，,L=L-P,返回,(2),；如果有交，在相交区域内取点，判断,P,Q,的深度，如果,P,的深度小，说明,P,，,Q,关系正确，,L=L-P,返回,(2),；否则交换,P,与,Q,，返回第,(3),步,.,画家算法（,6/6,）,空间多边形的排序算法？,问题：计算量大，循环遮挡,Z,缓冲器算法（,1/6,）,深度与可见性,u,v,n,umax,vmax,Z,缓冲器算法（,2/6,）,Z,（深度）缓冲器,Z,缓冲器算法（,3/6,）,算法,Z,缓冲器消隐算法,for(v=0;v vmax;v+)/,初始化,for(u=0;uZ,缓冲器的第,(u,v),单元的值）,置,Z,缓冲器的第,(u,v),单元的深度值为,d;,置帧缓冲器的第,(u,v),单元的颜色值为当前多边形颜色值；,Z,缓冲器算法（,5/6,）,计算过程,umax,vmax,Z,缓冲器算法（,6/6,）,优点,算法简单、稳定,便于硬件加速,不需要整个场景的几何数据,缺点,需要,Z,缓冲器,计算复杂度大,需要计算的像素深度值次数,=,多边形个数*多边形平均占据的像素个数,扫描线,Z,缓冲器算法,改进之一：将窗口分割成扫描线,扫描线,Z,缓冲器算法,算法,扫描线,Z,缓冲器消隐算法,for(v=0;v vmax;v+)/,初始化,for(u=0;uZ,缓冲器的第,(u,v),单元的值）,置,Z,缓冲器的第,(u,v),单元的深度值为,d;,置帧缓冲器的第,u,个单元的颜色值为当前多边形颜色值；,扫描线,Z,缓冲器算法,改进之二：采用多边形分类表、活化多边形表避免多边形与扫描线的盲目求交,扫描线,Z,缓冲器算法,扫描线,Z,缓冲器算法,算法,扫描线,Z,缓冲器消隐算法,建立多边形分类表；,for(v=0;v vmax;v+)/,初始化,for(u=0;uZ,缓冲器的第,(u,v),单元的值）,置,Z,缓冲器的第,(u,v),单元的深度值为,d;,置帧缓冲器的第,u,个单元的颜色值为当前多边形颜色值；,扫描线,Z,缓冲器算法,改进之三：利用边、边的分类表、边对、活化边对表避免边与扫描线的盲目求交,扫描线,Z,缓冲器算法,扫描线,Z,缓冲器算法,算法,扫描线,Z,缓冲器消隐算法,建立多边形分类表；,建立每一个多边形的边的分类表；,for(v=0;v vmax;v+)/,初始化,for(u=0;uZ,缓冲器的第,(u,v),单元的值）,置,Z,缓冲器的第,(u,v),单元的深度值为,d;,置帧缓冲器的第,u,个单元的颜色值为当前多边形颜色值；,扫描线,Z,缓冲器算法,改进之四：利用连贯性计算深度,水平方向,竖直方向,umax,vmax,扫描线,Z,缓冲器算法,缺点,在每一个被多边形覆盖像素处需要计算深度值,被多个多边形覆盖的像素需要多次计算深度值,v,扫描线算法,改进之一：在一条扫描线上，以区间为单位确定多边形的可见性,(,区间上任取一点计算深度,),扫描线算法,例外：多边形相互贯穿,改进之二：不需要,Z-Buffer,扫描线算法,数据结构,多边形分类表,活化多边形表,边的分类表,活化边表,扫描线算法,扫描线消隐算法,建立多边形分类表；,建立每一个多边形的边的分类表；,for(v=0;v vmax;v+)/,初始化,建立活化边表；,for(u=0;uumax;u+),置,Z,缓冲器的第,u,个单元的深度值为,-1,（最小的深度值）,;,置帧缓冲器的第,(u,v),单元的颜色值为背景色；,for(,活化边表中的每一个区间）,计算覆盖该区间的所有多边新的深度值，记最前面的多边形为,P,；,以,P,的颜色显示该区间；,区域子分算法（,1/2,）,原理,利用区域的连贯性提高排序的效率,分割窗口直到窗口足够简单,区域子分算法（,2/2,）,窗口足够简单的条件,光线投射算法（,1/3),原理,光线投射算法,(2/3),基本问题,光线与物体表面的求交,光线投射算法,(3/3),光线投射算法,for(v=0;v=vmax;v+),for(u=0;u=umax;u+),形成通过像素,(u,v),的投影线；,for(,场景中的每一个多边形）,将投影线与多边形求交；,if(,有交点,),以最近交点所属多边形的颜色显示像素,(u,v);,else,以背景颜色显示像素,(u,v);,作业,任选一个：,实现一个画家算法,实现一个,Z-buffer,算法,