可见面判别算法优秀PPT.ppt
可见面判别算法第1页，本讲稿共42页 真实感图形绘制流程场景造型取景变换背面剔除视域四棱锥裁剪透视变换隐面消除、场景造型光亮度计算扫描转换、场景造型第2页，本讲稿共42页取景变换（1/5）场景坐标系场景坐标系场景的局部局部坐标系完成物体的造型 场景的世界世界坐标系（整体坐标系）放入待绘制的场景，定义物体之间的相互位置观察坐标系观察坐标系也称摄像机坐标系摄像机坐标系，或者视点坐标系视点坐标系完成取景变换所需建立的第一个坐标系第3页，本讲稿共42页取景变换（2/5）建立观察坐标系的步骤确定观察参考点观察参考点，即视点位置视点位置可以设在任何位置通常选在靠近或在物体的表面将视点位置取为视点坐标系的原点确定观察方向观察方向，即视线方向视线方向一般取深度坐标轴，即ze轴的正向为简便起见，设为总是指向场景坐标系的原点确定观察平面观察平面，即视平面位置视平面位置一般取过视点且垂直于视线方向的平面，即xeye平面第4页，本讲稿共42页取景变换（3/5）场景坐标系场景坐标系一般取右手右手坐标系观察坐标系观察坐标系通常取左手左手坐标系符合人们的观察习惯 xwzwywzexeye视点E观察坐标系为左手坐标系场景坐标系为右手坐标系O第5页，本讲稿共42页取景变换（4/5）将物体投影到观察平面之前必须将场景坐标系中的点转换到观察坐标系中 这一过程称为取景变换取景变换，也称视向变换视向变换包括平移和旋转的一系列几何变换的级联 取景变换矩阵 第6页，本讲稿共42页取景变换（5/5）场景坐标系原点平移到视场景坐标系原点平移到视点位置点位置E绕绕xe轴逆时针旋转轴逆时针旋转90 绕绕ye轴顺时针旋转轴顺时针旋转角角绕绕xe轴逆时针旋转轴逆时针旋转角角调整调整x轴指向轴指向对对x轴作对称变换轴作对称变换xwzwywzexeyeEOCxCyCzxwzwywzexe yeEOCxCyCz90 xwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCz第7页，本讲稿共42页消隐算法按实现方式不同分为两大类按实现方式不同分为两大类：景物空间景物空间（object space）消隐算法直接在视点坐标系中确定视点不可见的表面区域将它们表达成同原表面一致的数据结构侧重于景中各物体之间的几何关系图像空间图像空间（image space）消隐算法 在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域将其颜色作为该像素的显示光亮度 侧重于向屏幕投影后形成的图像第8页，本讲稿共42页背面剔除算法背面剔除算法背面剔除算法背面剔除算法 法向向量N 视线向量V法向向量N 法向向量N 90 90第9页，本讲稿共42页隐藏面的消除-画家算法画家算法（1/3）画家算法画家算法 1972年年M.E.Newell受画家由远至近作画的启发受画家由远至近作画的启发景物空间消隐算法景物空间消隐算法第10页，本讲稿共42页隐藏面的消除-画家算法画家算法（2/3）基本步骤基本步骤生成深度优先级队列生成深度优先级队列据视点距离远远的多边形优先级低，排在队列的前端据视点距离近近的多边形优先级高，排在队列的后端 从队列中依次取出多边形，计算其表面光亮度计算其表面光亮度写入帧缓冲器写入帧缓冲器 直到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器第11页，本讲稿共42页隐藏面的消除-画家算法画家算法（3/3）优点优点：透明或半透明物体图形的动态显示动态显示飞行训练模拟器中显示飞机着陆时的情景场景中的物体是不变的，只是视点在变化只是视点在变化只要事先把不同视点的景物的优先级队列算出再实时地采用画家算法来显示图形就可以实现图形的快速消隐与显示 第12页，本讲稿共42页隐藏面消除-Weiler-Atherton算法算法（1/3）Weiler-Atherton算法算法景物空间消隐算法基于Weiler-Atherton多边形裁剪操作 第13页，本讲稿共42页隐藏面消除-Weiler-Atherton算法算法（2/3）基本步骤基本步骤 1)深度预排序，形成深度预排序，形成景物多边形表景物多边形表 将变换到屏幕坐标系中的景物表面按各顶点的z最小值进行排序2)当前具有当前具有最大最大z值值的景物表面作为裁剪多边形的景物表面作为裁剪多边形CP 深度最大、离视点最近3)用用CP对景物多边形表中排在后面的表面进行对景物多边形表中排在后面的表面进行裁剪裁剪 产生内部多边形Pin和外部多边形Pout 裁剪多边形将主多边形裁剪为内部多边形和外部多边形B1B2裁剪多边形Pc主多边形Ps第14页，本讲稿共42页隐藏面消除-Weiler-Atherton算法算法（3/3）4)比较比较Pc与与Pin的深度，检查的深度，检查Pc是否真正离视点最近是否真正离视点最近是，则Pc为可见表面不是，则取Pin为新的Pc，重复步骤3)5)将位于将位于Pc之外的景物表面组成外裁剪结果多边形表之外的景物表面组成外裁剪结果多边形表 取表中深度最大的表面为Pc，重复步骤3)6)递归进行直到外裁剪结果多边形表为空时为止递归进行直到外裁剪结果多边形表为空时为止 第15页，本讲稿共42页隐藏面的消除-BSP树算法树算法（1/2）BSP树算法树算法Binary Space Partitioning景物空间消隐算法基于BSP树，对景物表面进行二叉分类与画家算法类似，景物多边形由远至近绘制特别适合的场合特别适合的场合 场景中物体位置固定不变物体位置固定不变、仅视点移动仅视点移动第16页，本讲稿共42页隐藏面的消除-BSP树算法树算法（2/2）基本步骤基本步骤 选一剖分平面选一剖分平面P1，将场景空间分割成两个，将场景空间分割成两个半空间半空间剖分结果表示为一棵剖分结果表示为一棵BSP树树叶节点叶节点：景物左分支左分支：位于剖分平面前面的景物右分支右分支：位于剖分平面后面的景物依据视点位置，对子空间进行分类依据视点位置，对子空间进行分类包含视点的子空间标识为“front”另一侧子空间标识为“back”递归搜索递归搜索该该BSP树，优先绘制标识为树，优先绘制标识为“back”的子空间中所含的景物的子空间中所含的景物 BfrontfrontbackbackACDP1P2P2frontfrontfrontbackbackbackACDB第17页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（1/8）深度缓冲器算法深度缓冲器算法Depthbuffer algorithm图像空间消隐算法1975年，Catmull提出 第18页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（2/8）基本思想基本思想将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较取最靠近视点的表面的属性值作为该像素的属性值用Zbuffer记录该表面在该像素点的深度深度用framebuffer记录该表面在该像素点的颜色或亮度值颜色或亮度值第19页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（3/8）深度缓冲器深度缓冲器帧缓冲器的扩充也称Z-Buffer算法算法第20页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（4/8）流程：流程：for（场景中的每一个多边形）（场景中的每一个多边形）扫描转换该多边形；扫描转换该多边形；for（多边形所覆盖的每一个像素点（多边形所覆盖的每一个像素点(x,y)）计算多边形在该像素点的深度值计算多边形在该像素点的深度值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)处；处；当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像第21页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（5/8）优点优点简单简单在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂曲面之间的交线。计算量呈线性复杂度计算量呈线性复杂度场景中景物表面采样点的数目无需对各景物表面片作深度预排序无需对各景物表面片作深度预排序景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器易于硬件实现易于硬件实现图形工作站上配置由硬件实现的深度缓冲器算法很多微型机上都装有基于深度缓冲器算法的图形加速卡第22页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（6/8）缺点缺点需要很大的存储空间需要很大的存储空间象素数目为500500，深度值采用浮点类型（4字节）除刷新缓存外，还需500*500*4=1M字节的额外存储空间在实现反走样、处理透明和半透明等效果方面存在在实现反走样、处理透明和半透明等效果方面存在困难，并由此会产生巨大的处理时间开销困难，并由此会产生巨大的处理时间开销由于在帧缓冲器内的同一象素点上可见表面的写入顺序是不确定的，所以可能导致画面上的局部错误。第23页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（7/8）改进一：减少需要相对测试的多边形平面数改进一：减少需要相对测试的多边形平面数最小最大测试最小最大测试 不重叠,不可能互相遮蔽 测试无确定结果 对每条边进行最小最大测试XminXmax第24页，本讲稿共42页隐藏面消除-深度缓冲器算法深度缓冲器算法（8/8）改进二：利用连贯性计算深度改进二：利用连贯性计算深度水平方向水平方向竖直方向竖直方向改进三：降低对存储空间的需求改进三：降低对存储空间的需求图像空间划分为4、16甚至更多的子正方形或条状区域在最小情况下，只对应一条扫描线的深度缓冲器扫描线相关算法扫描线相关算法第25页，本讲稿共42页隐藏面的消除-扫描线相关算法（扫描线相关算法（1/3）扫描线相关算法扫描线相关算法按扫描线顺序处理一帧画面在扫描平面扫描平面（ZOX平面）上解决消隐问题由视点和扫描线所决定深度缓冲器算法的一维版本深度缓冲器算法的一维版本深度缓冲器所需的存储空间屏幕水平分辨率每个深度值所占的存储位数 第26页，本讲稿共42页隐藏面的消除for(每条扫描线每条扫描线)将扫描线帧缓冲器将扫描线帧缓冲器f_buf置成背景色；置成背景色；将扫描线深度缓冲器将扫描线深度缓冲器Z_buf置成最小值；置成最小值；for(每个多边形每个多边形)求出该多边形与当前扫描线的相交区间；求出该多边形与当前扫描线的相交区间；for(相交区间内每个象素点相交区间内每个象素点(x,y)计算多边形在该处的深度值计算多边形在该处的深度值z；if(多边形在该处的深度值多边形在该处的深度值z Z_buf在该处的值在该处的值)用多边形在该处的深度值用多边形在该处的深度值z取代取代Z_buf在该处的值；在该处的值；用多边形在该处的亮度值取代用多边形在该处的亮度值取代f_buf在该处的值；在该处的值；用用f_buf的内容显示当前扫描线；的内容显示当前扫描线；第27页，本讲稿共42页隐藏面的消除-扫描线相关算法（扫描线相关算法（3/3）缺点缺点在每一个被多边形覆盖像素处需要计算深度值被多个多边形覆盖的像素需要多次计算深度值改进改进在一条扫描线上，以区间为单位确定多边形的可见性在一条扫描线上，以区间为单位确定多边形的可见性第28页，本讲稿共42页隐藏面的消除-Warnock算法算法（1/4）Warnock算法算法图像空间消隐算法区域的连贯性 也称区域细分区域细分area-subdivision实质分而治之 第29页，本讲稿共42页隐藏面的消除-Warnock算法算法（2/4）基本思想基本思想观察整个窗口区域观察整个窗口区域判别窗口是否单纯判别窗口是否单纯窗口内无任何可见物体无任何可见物体窗口已被一个可见面片完全充满已被一个可见面片完全充满将非单纯的窗口四等分为四个子窗口将非单纯的窗口四等分为四个子窗口对每个子窗口再进一步判别是否是单纯的对每个子窗口再进一步判别是否是单纯的直到窗口单纯或窗口边长已缩至一个象素点为止直到窗口单纯或窗口边长已缩至一个象素点为止 即使即使10241024分辨率分辨率视图被细分视图被细分10次后，也能使每个子窗口覆盖一个像素次后，也能使每个子窗口覆盖一个像素 第30页，本讲稿共42页隐藏面的消除-Warnock算法算法（3/4）关键步骤关键步骤分析观察窗口与所有投影后多边形面片之间的关系分离分离内含内含相交相交包围包围判别窗口是否单纯判别窗口是否单纯第31页，本讲稿共42页隐藏面的消除-Warnock算法算法（4/4）基本步骤基本步骤对每个窗口判断对每个窗口判断与多边形与多边形分离分离仅仅包含包含一个多边形一个多边形与一个多边形与一个多边形相交相交被一个多边形所被一个多边形所包围包围且窗口内无其它多边形且窗口内无其它多边形至少被一个多边形所包围，且此多边形至少被一个多边形所包围，且此多边形距离视点距离视点最近最近否则继续细分窗口，并重复以上测试否则继续细分窗口，并重复以上测试第32页，本讲稿共42页 光线投射算法（1/4）Ray CastingAppel提出提出建立在几何光学基础之上建立在几何光学基础之上对于包含曲面、特别是球面的场景效率高对于包含曲面、特别是球面的场景效率高第33页，本讲稿共42页 光线投射算法（2/4）基本思想基本思想观察者之所以能看见景物观察者之所以能看见景物光源发出的光照射到物体上的结果其中一部分光到达人的眼睛引起视觉到达观察者眼中的光到达观察者眼中的光由物体表面反射通过表面折射或透射若若从光源出发跟踪光线从光源出发跟踪光线则只有极少量的光能到达观察者的眼睛效率低从视点或像素出发，仅对穿过像素的光线反向跟踪从视点或像素出发，仅对穿过像素的光线反向跟踪当光线路径到达一个可见的不透明物体的表面时停止追踪当光线路径到达一个可见的不透明物体的表面时停止追踪第34页，本讲稿共42页将景物通过透视投影变换透视投影变换到图像空间反向跟踪一条穿过像素点的光线反向跟踪一条穿过像素点的光线决定它与场景中的哪一景物表面相交交点按深度排序交点按深度排序需求出该光线与景物表面的所有可能的交点具有具有最大最大z z值的交点值的交点对应的面就是屏幕上该像素对应的对应的面就是屏幕上该像素对应的可见面可见面离视点最近该像素处的显示值由相应物体的属性决定对屏幕上所有像素都进行如上处理后，算法结束 视点光线投影面上的像素位置物体假设假设视点视点位于z轴正向投影平面投影平面（屏幕）垂直于z轴反向跟踪一条穿过像素点的光线光线投射算法（3/4）第35页，本讲稿共42页光线投射算法（4/4）光线投射算法光线投射算法 for(y=0;y=ymax;y+)for(x=0;x=xmax;x+)形成通过像素形成通过像素(x,y)的投影线；的投影线；for(场景中的每一个多边形）场景中的每一个多边形）将投影线与多边形求交；将投影线与多边形求交；if(有交点有交点)以最近交点所属多边形的颜色显示像素以最近交点所属多边形的颜色显示像素(x,y);else 以背景颜色显示像素以背景颜色显示像素(x,y);第36页，本讲稿共42页阴影处理（1/6）判断视点、光源以及物体之间的位置关系判断视点、光源以及物体之间的位置关系 从视点可见，从光源也可见从视点可见，从光源也可见从视点可见，从光源不可见从视点可见，从光源不可见 相对于部分光源可见，相对于另一部分光源不可见相对于部分光源可见，相对于另一部分光源不可见第37页，本讲稿共42页阴影处理（2/6）当观察方向与光源方向重合时当观察方向与光源方向重合时观察者看不到任何阴影可以不进行阴影测试当观察方向与光源方向不一致当观察方向与光源方向不一致或光源多且光源体制比较复杂时或光源多且光源体制比较复杂时必须进行阴影处理 第38页，本讲稿共42页阴影处理（3/6）阴影由两部分组成阴影由两部分组成本影本影任何光线都照不到的区域呈现为全黑的轮廓分明的区域 半影半影 可接收到分布光源照射的部分光线的区域 通常位于本影周围，呈现为半明半暗的区域 本半区影区影区影无光源面光源照射形成的本影与半影第39页，本讲稿共42页阴影处理（4/6）点光源点光源只能产生本影只能产生本影位于有限距离内的分布光源位于有限距离内的分布光源可同时产生本影和半影可同时产生本影和半影需要的阴影计算量大第40页，本讲稿共42页阴影处理（5/6）计算阴影的过程计算阴影的过程相当于两次消隐过程相当于两次消隐过程对每个光源进行消隐对每个光源进行消隐对视点的位置进行消隐对视点的位置进行消隐好处好处改变视点位置改变视点位置，第一次消隐过程不必重新计算第41页，本讲稿共42页阴影处理（6/6）产生的本影包括产生的本影包括自身阴影面自身阴影面假设视点在点光源位置，用背面剔除背面剔除的方法求出投射阴影投射阴影从光源向物体的所有可见面投射光线将这些面投影到场景中得到投影面将这些投影面与场景中其它平面求交线，可得阴影多边形 自身阴影自身阴影投射阴影投射阴影第42页，本讲稿共42页
