《可见面判别算法》PPT课件.ppt

1、曾 智 勇 福建师范大学软件学院,第9章 可见面判别算法,真实感图形绘制流程,取景变换（1/5）,场景坐标系 场景的局部坐标系 完成物体的造型 场景的世界坐标系（整体坐标系） 放入待绘制的场景，定义物体之间的相互位置,观察坐标系 也称摄像机坐标系，或者视点坐标系 完成取景变换所需建立的第一个坐标系,取景变换（2/5）,建立观察坐标系的步骤 确定观察参考点，即视点位置 可以设在任何位置 通常选在靠近或在物体的表面 将视点位置取为视点坐标系的原点 确定观察方向，即视线方向 一般取深度坐标轴，即ze轴的正向 为简便起见，设为总是指向场景坐标系的原点 确定观察平面，即视平面位置 一般取过视点且垂直于视

2、线方向的平面，即xeye平面,取景变换（3/5）,场景坐标系 一般取右手坐标系 观察坐标系 通常取左手坐标系 符合人们的观察习惯,取景变换（4/5）,将物体投影到观察平面之前 必须将场景坐标系中的点转换到观察坐标系中 这一过程称为取景变换，也称视向变换 包括平移和旋转的一系列几何变换的级联 取景变换矩阵,取景变换（5/5）,场景坐标系原点平移到视点位置E 绕xe轴逆时针旋转90 绕ye轴顺时针旋转角 绕xe轴逆时针旋转角 调整x轴指向 对x轴作对称变换,消隐算法,按实现方式不同分为两大类： 景物空间（object space） 消隐算法 直接在视点坐标系中确定视点不可见的表面区域 将它们表达成

3、同原表面一致的数据结构 侧重于景中各物体之间的几何关系 图像空间（image space）消隐算法 在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域 将其颜色作为该像素的显示光亮度 侧重于向屏幕投影后形成的图像,背面剔除算法,背面剔除算法,隐藏面的消除-画家算法 （1/3）,画家算法 1972年M.E.Newell 受画家由远至近作画的启发 景物空间消隐算法,隐藏面的消除-画家算法 （2/3）,基本步骤 生成深度优先级队列 据视点距离远的多边形优先级低，排在队列的前端 据视点距离近的多边形优先级高，排在队列的后端 从队列中依次取出多边形，计算其表面光亮度 写入帧缓冲器

4、直到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器,隐藏面的消除-画家算法 （3/3）,优点： 透明或半透明物体 图形的动态显示 飞行训练模拟器中显示飞机着陆时的情景 场景中的物体是不变的，只是视点在变化 只要事先把不同视点的景物的优先级队列算出 再实时地采用画家算法来显示图形 就可以实现图形的快速消隐与显示,隐藏面消除-Weiler-Atherton算法（1/3）,Weiler-Atherton算法 景物空间消隐算法 基于Weiler-Atherton多边形裁剪操作,隐藏面消除-Weiler-Atherton算法（2/3）,基本步骤 1)深度预排序，形成景物多边形表 将变换到屏幕坐标系中

5、的景物表面 按各顶点的z最小值进行排序 2)当前具有最大z值的景物表面作为裁剪多边形CP 深度最大、离视点最近 3)用CP对景物多边形表中排在后面的表面进行裁剪 产生内部多边形Pin和外部多边形Pout,隐藏面消除-Weiler-Atherton算法（3/3）,4)比较Pc与Pin的深度，检查Pc是否真正离视点最近 是，则Pc为可见表面 不是，则取Pin为新的Pc，重复步骤3) 5)将位于Pc之外的景物表面组成外裁剪结果多边形表 取表中深度最大的表面为Pc，重复步骤3) 6)递归进行直到外裁剪结果多边形表为空时为止,隐藏面的消除- BSP树算法（1/2）,BSP树算法 Binary Space

6、 Partitioning 景物空间消隐算法 基于BSP树，对景物表面进行二叉分类 与画家算法类似，景物多边形由远至近绘制 特别适合的场合 场景中物体位置固定不变、仅视点移动,隐藏面的消除-BSP树算法（2/2）,基本步骤 选一剖分平面P1，将场景空间分割成两个半空间 剖分结果表示为一棵BSP树 叶节点：景物 左分支：位于剖分平面前面的景物 右分支：位于剖分平面后面的景物 依据视点位置，对子空间进行分类 包含视点的子空间标识为“front” 另一侧子空间标识为“back” 递归搜索该BSP树，优先绘制标识为“back”的子空间中所含的景物,隐藏面消除-深度缓冲器算法（1/8）,深度缓冲器算法

7、Depthbuffer algorithm 图像空间消隐算法 1975年，Catmull提出,隐藏面消除-深度缓冲器算法（2/8）,基本思想 将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较 取最靠近视点的表面的属性值作为该像素的属性值 用Zbuffer记录该表面在该像素点的深度 用framebuffer记录该表面在该像素点的颜色或亮度值,隐藏面消除-深度缓冲器算法（3/8）,深度缓冲器 帧缓冲器的扩充 也称Z-Buffer算法,隐藏面消除-深度缓冲器算法（4/8）,流程： for（场景中的每一个多边形） 扫描转换该多边形； for（多边形所覆盖的每一个像素点(x,y)） 计算多边

8、形在该像素点的深度值z(x,y)； if（z(x,y) Z-buf中对应此像素点(x,y)的z值） 把多边形在(x,y)处的深度值z(x,y)存入Z-buf中的(x,y)处； 把多边形在(x,y)处的亮度值存入f-buf中的(x,y)处； 当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像,隐藏面消除-深度缓冲器算法（5/8）,优点 简单 在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂曲面之间的交线。 计算量呈线性复杂度 场景中景物表面采样点的数目 无需对各景物表面片作深度预排序 景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器 易于硬件实现 图形工作站上配置由硬

9、件实现的深度缓冲器算法 很多微型机上都装有基于深度缓冲器算法的图形加速卡,隐藏面消除-深度缓冲器算法（6/8）,缺点 需要很大的存储空间 象素数目为500500，深度值采用浮点类型（4字节） 除刷新缓存外，还需500*500*4=1M字节的额外存储空间 在实现反走样、处理透明和半透明等效果方面存在困难，并由此会产生巨大的处理时间开销 由于在帧缓冲器内的同一象素点上可见表面的写入顺序是不确定的，所以可能导致画面上的局部错误。,隐藏面消除-深度缓冲器算法（7/8）,改进一：减少需要相对测试的多边形平面数 最小最大测试,隐藏面消除-深度缓冲器算法（8/8）,改进二：利用连贯性计算深度 水平方向 竖直

10、方向,改进三：降低对存储空间的需求 图像空间划分为4、16甚至更多的子正方形或条状区域 在最小情况下，只对应一条扫描线的深度缓冲器 扫描线相关算法,隐藏面的消除-扫描线相关算法（1/3）,扫描线相关算法 按扫描线顺序处理一帧画面 在扫描平面（ZOX平面）上解决消隐问题 由视点和扫描线所决定 深度缓冲器算法的一维版本 深度缓冲器所需的存储空间 屏幕水平分辨率每个深度值所占的存储位数,隐藏面的消除,for (每条扫描线) 将扫描线帧缓冲器f_buf置成背景色； 将扫描线深度缓冲器Z_buf置成最小值； for (每个多边形) 求出该多边形与当前扫描线的相交区间； for (相交区间内每个象素点(x

11、,y) 计算多边形在该处的深度值z； if (多边形在该处的深度值z Z_buf在该处的值) 用多边形在该处的深度值z取代Z_buf在该处的值； 用多边形在该处的亮度值取代f_buf在该处的值； 用f_buf的内容显示当前扫描线； ,隐藏面的消除-扫描线相关算法（3/3）,缺点 在每一个被多边形覆盖像素处需要计算深度值 被多个多边形覆盖的像素需要多次计算深度值,改进 在一条扫描线上，以区间为单位确定多边形的可见性,隐藏面的消除- Warnock算法（1/4）,Warnock算法 图像空间消隐算法 区域的连贯性 也称区域细分 area-subdivision 实质 分而治之,隐藏面的消除- Wa

12、rnock算法（2/4）,基本思想 观察整个窗口区域 判别窗口是否单纯 窗口内无任何可见物体 窗口已被一个可见面片完全充满 将非单纯的窗口四等分为四个子窗口 对每个子窗口再进一步判别是否是单纯的 直到窗口单纯或窗口边长已缩至一个象素点为止 即使10241024分辨率 视图被细分10次后，也能使每个子窗口覆盖一个像素,隐藏面的消除- Warnock算法（3/4）,关键步骤,判别窗口是否单纯,隐藏面的消除- Warnock算法（4/4）,基本步骤 对每个窗口判断 与多边形分离 仅包含一个多边形 与一个多边形相交 被一个多边形所包围且窗口内无其它多边形 至少被一个多边形所包围，且此多边形距离视点最近

13、 否则继续细分窗口，并重复以上测试,光线投射算法（1/4）,Ray Casting Appel提出 建立在几何光学基础之上 对于包含曲面、特别是球面的场景效率高,光线投射算法（2/4）,基本思想 观察者之所以能看见景物 光源发出的光照射到物体上的结果 其中一部分光到达人的眼睛引起视觉 到达观察者眼中的光 由物体表面反射 通过表面折射或透射 若从光源出发跟踪光线 则只有极少量的光能到达观察者的眼睛 效率低 从视点或像素出发，仅对穿过像素的光线反向跟踪 当光线路径到达一个可见的不透明物体的表面时停止追踪,将景物通过透视投影变换到图像空间 反向跟踪一条穿过像素点的光线 决定它与场景中的哪一景物表面相

14、交 交点按深度排序 需求出该光线与景物表面的所有可能的交点 具有最大z值的交点对应的面就是屏幕上该像素对应的可见面 离视点最近 该像素处的显示值由相应物体的属性决定 对屏幕上所有像素都进行如上处理后，算法结束,假设 视点位于z轴正向 投影平面（屏幕）垂直于z轴,反向跟踪一条穿过像素点的光线,光线投射算法（3/4）,光线投射算法（4/4）,光线投射算法 for(y=0;y=ymax;y+) for(x=0;x=xmax;x+) 形成通过像素(x,y)的投影线； for(场景中的每一个多边形） 将投影线与多边形求交； if(有交点) 以最近交点所属多边形的颜色显示像素(x,y); else 以背景颜色显示像素(x,y); ,阴影处理 （1/6）,判断视点、光源以及物体之间的位置关系 从视点可见，从光源也可见 从视点可见，从光源不可见 相对于部分光源可见，相对于另一部分光源不可见,阴影处理（2/6）,当观察方向与光源方向重合时 观察者看不到任何阴影 可以不进行阴影测试 当观察方向与光源方向不一致 或光源多且光源体制比较复杂时 必须进行阴影处理,阴影处理（3/6）,阴影由两部分组成 本影 任何光线都照不到的区域 呈现为全黑的轮廓分明的区域 半影 可接收到分布光源照射的部分光线的区域 通常位于本影周围，呈现为半明半暗的区域,面光源照射形成的本影与半影,阴影处