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