第七章隐藏面的消除

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