计算机图形学教程（第5版 微课版）课件 第8章 真实感图形显示-1

（一）苏小红哈尔滨工业大学计算机科学与技术学院第8章真实感图形生成2

真实感图形绘制流程场景造型取景变换背面剔除和视域四棱锥裁剪计算场景中可见面的光亮度和颜色

透视投影隐藏面消除

3取景变换（1/6）场景坐标系场景的局部坐标系完成物体的造型场景的世界坐标系（整体坐标系）放入待绘制的场景，定义物体之间的相互位置如果物体被设置了动画动画系统将提供一个随时间变化的变换矩阵逐帧把物体变换到世界坐标系中xzyzyx4取景变换（2/6）观察坐标系也称摄像机坐标系，或者视点坐标系完成取景变换所需建立的第一个坐标系5取景变换（3/6）建立观察坐标系的步骤确定观察参考点，即视点位置可以设在任何位置通常选在靠近或在物体的表面将视点位置取为视点坐标系的原点确定观察方向，即视线方向一般取深度坐标轴，即ze轴的正向为简便起见，设为总是指向场景坐标系的原点确定观察平面，即视平面位置一般取过视点且垂直于视线方向的平面，即xeye平面6取景变换（4/6）场景坐标系一般取右手坐标系观察坐标系通常取左手坐标系符合人们的观察习惯xwzwywzexeye视点E观察坐标系为左手坐标系场景坐标系为右手坐标系O7取景变换（5/6）将物体投影到观察平面之前必须将场景坐标系中的点转换到观察坐标系中

这一过程称为取景变换，也称视向变换包括平移和旋转的一系列几何变换的级联取景变换矩阵8取景变换（6/6）场景坐标系原点平移到视点位置E绕xe轴逆时针旋转90º绕ye轴顺时针旋转Ψ角绕xe轴逆时针旋转θ角调整x轴指向对x轴作对称变换xwzwywzexeyeEOCxCyCzΨxwzwywzexeyeEOCxCyCz90ºxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ9消隐算法（1/2）消隐的基本（核心）问题：排序整体排序：画家算法点排序：Z-Buffer算法、光线投射算法区间排序：扫描线算法区域排序：区域子分算法10消隐算法（2/2）按实现方式不同分为两大类：景物空间（objectspace）

消隐算法直接在视点坐标系中确定视点不可见的表面区域将它们表达成同原表面一致的数据结构侧重于景中各物体之间的几何关系图像空间（imagespace）消隐算法

在投影屏幕上，以屏幕像素为采样单位，确定投影于每一像素的可见景物表面区域将其颜色作为该像素的显示光亮度侧重于向屏幕投影后形成的图像11提高消隐算法效率的常用方法（1/5）提高消隐算法效率利用各种形式的相关性（连贯性）物体的连贯性面的连贯性区域的连贯性扫描线的连贯性帧的连贯性12提高消隐算法效率的常用方法（2/5）包围盒技术避免盲目求交包围盒--包围目标的简单形体包围简单常用的包围盒长方体球圆柱13提高消隐算法效率的常用方法（3/5）空间分割技术14提高消隐算法效率的常用方法（5/5）背面剔除算法

法向向量N

视线向量V法向向量N

法向向量N<90°<90°可见可见不可见>90°15隐藏面的消除-画家算法

（1/4）画家算法

1972年M.E.Newell受画家由远至近作画的启发景物空间消隐算法16隐藏面的消除-画家算法

（2/4）基本思想画家消隐算法{

对场景中的多边形按深度进行排序， 形成深度优先级队列； 按从远到近的顺序显示多边形；}也称优先级表算法17隐藏面的消除-画家算法

（3/4）基本步骤生成深度优先级队列据视点距离远的多边形优先级低，排在队列的前端据视点距离近的多边形优先级高，排在队列的后端从队列中依次取出多边形，计算其表面光亮度写入帧缓冲器

直到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器18隐藏面的消除-画家算法

（4/4）优点：简单，容易实现适于图形的动态显示飞行训练模拟器中显示飞机着陆时的情景场景中的物体是不变的，只是视点在变化只要事先把不同视点的景物的优先级队列算出再实时地采用画家算法来显示图形就可以实现图形的快速消隐与显示缺点：深度排序计算量大19隐藏面的消除-画家算法

（4/4）问题：深度优先级表的建立是动态进行的。假定观察方向同Z轴同向，则最初可按各面的最小z值排序。但排序可能出错尽管面S1的最小z值小于面S2的最小z值，但正确顺序是面S2位于面S1前若存在两面相交和循环遮挡，必须求交分割后再进行排序20隐藏面的消除-画家算法

（4/4）算法(1）计算各面最小z值zmin，并以此值的优先级进行排序，建立初步的深度优先表；(2）表空结束。否则取表中深度最大的面Sn,检查表中其它各面Sk(k=0,1,...,n-1)与Sn是否在Z方向存在重叠的关系。存在，记重叠面为Sj转(3)。否则，将Sn写入帧缓冲器，n=n-1转(2)；(3)检查Sn是否遮挡Sj，不遮挡则将Sn写入帧缓存器，n=n-1转(2)。否则，交换Sn和Sj在表中位置，转(2)。如果Sn和Sj已经交换过位置，则两面交叉遮挡，转(4)；(4)用Sn和Sj的交线分割Sn为两部分，转(1)。21隐藏面消除-Weiler-Atherton算法（1/3）Weiler-Atherton算法景物空间消隐算法基于Weiler-Atherton多边形裁剪操作22隐藏面消除-Weiler-Atherton算法（2/3）基本步骤

1)深度预排序，形成景物多边形表

将变换到屏幕坐标系中的景物表面按各顶点的z最小值进行排序2)当前具有最大z值的景物表面作为裁剪多边形CP

深度最大、离视点最近3)用CP对景物多边形表中排在后面的表面进行裁剪

产生内部多边形Pin和外部多边形Pout

裁剪多边形将主多边形裁剪为内部多边形和外部多边形PinPout裁剪多边形CP主多边形SP23隐藏面消除-Weiler-Atherton算法（3/3）4)比较CP与Pin的深度，检查CP是否真正离视点最近是，则CP为可见表面不是，则取Pin为新的CP，重复步骤3)5)将位于CP之外的景物表面组成外裁剪结果多边形表

取表中深度最大的表面为CP，重复步骤3)6)递归进行直到外裁剪结果多边形表为空时为止24隐藏面的消除-BSP树算法（1/2）BSP树算法BinarySpacePartitioning景物空间消隐算法基于BSP树，对景物表面进行二叉分类与画家算法类似，景物多边形由远至近绘制特别适合的场合场景中物体位置固定不变、仅视点移动25隐藏面的消除-BSP树算法（2/2）基本步骤

选一剖分平面P1，将场景空间分割成两个半空间剖分结果表示为一棵BSP树叶节点：景物左分支：位于剖分平面前面的景物右分支：位于剖分平面后面的景物依据视点位置，对子空间进行分类包含视点的子空间标识为“front”另一侧子空间标识为“back”递归搜索该BSP树，优先绘制标识为“back”的子空间中所含的景物P1P2P2frontfrontfrontbackbackbackACDB与物体相交，就将它分割为两个物体

BfrontfrontbackbackACDP1P226隐藏面消除-深度缓冲器算法（1/10）深度缓冲器算法Depth—bufferalgorithm图像空间消隐算法1975年，Catmull提出在像素级上以近物取代远物有利于硬件实现，但需要较多存储空间27隐藏面消除-深度缓冲器算法（2/10）深度与可见性uvnxmaxymax28隐藏面消除-深度缓冲器算法（3/10）基本思想将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较取最靠近视点的表面的属性值作为该像素的属性值用frame—buffer记录该表面在该像素点的颜色或亮度值用Z—buffer记录该表面在该像素点的深度深度缓冲器帧缓冲器的扩充也称Z-Buffer算法29隐藏面消除-深度缓冲器算法（4/10）基本步骤

取景变换、透视变换、扫描转换将物体描述转化为屏幕坐标系中的投影坐标初始化深度缓冲器初始化为离视点最远的最小值帧缓冲器初始化为背景的属性值30隐藏面消除-深度缓冲器算法（5/10）流程：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)处；

}}}当所有的多边形都处理完后，帧缓冲器中的内容即为消除隐藏面后的图像31隐藏面消除-深度缓冲器算法（6/10）优点简单，可轻而易举地处理任意复杂的画面在象素级上以近物代替远物，易于消除隐藏面，并准确显示复杂曲面之间的交线。计算量呈线性复杂度O(n)n:场景中景物表面采样点的数目图象空间的大小是固定的，计算量最多随画面复杂度线性增长无需对各景物表面片作深度预排序景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器易于硬件实现图形工作站上带有用于消隐的深度缓存，克服了深度缓存算法占用大量存储单元的缺点很多微型机上都装有基于深度缓冲器算法的图形加速卡32隐藏面消除-深度缓冲器算法（7/10）缺点需要很大的存储空间例如：象素数目500×500，深度值采用浮点型（4字节）除刷新缓存外，还需500*500*4=1M字节的额外存储空间在实现反走样、处理透明和半透明等效果方面存在困难，并产生巨大的处理时间开销由于在帧缓冲器内的同一象素点上可见表面的写入顺序是不确定的，所以可能导致画面上的局部错误。33隐藏面消除-深度缓冲器算法（8/10）改进一：减少需要相对测试的多边形平面数最小最大测试

不重叠,不可能互相遮蔽测试无确定结果

对每条边进行最小最大测试XminXmax34隐藏面消除-深度缓冲器算法（9/10）改进二：利用连贯性计算深度水平方向竖直方向xmaxymax35隐藏面消除-深度缓冲器算法（10/10）改进三：降低对存储空间的需求图像空间划分为4、16甚至更多的子正方形或条状区域在最小情况下，只对应一条扫描线的深度缓冲器扫描线相关算法36隐藏面的消除-扫描线相关算法（1/5）扫描线相关算法按扫描线顺序处理一帧画面在扫描平面（ZOX平面）上解决消隐问题由视点和扫描线所决定深度缓冲器算法的一维版本深度缓冲器所需的存储空间屏幕水平分辨率×每个深度值所占的存储位数37隐藏面的消除for(每条扫描线){

将扫描线帧缓冲器f_buf置成背景色；将扫描线深度缓冲器Z_buf置成最小值；

for(每个多边形){

求出该多边形与当前扫描线的相交区间；

for(相交区间内每个象素点(x,y)){

计算多边形在该处的深度值z；

if(多边形在该处的深度值z>Z_buf在该处的值){

用多边形在该处的深度值z取代Z_buf在该处的值；用多边形在该处的亮度值取代f_buf在该处的值；

}}}

用f_buf的内容显示当前扫描线；}38隐藏面的消除-扫描线相关算法（3/5）缺点在每一个被多边形覆盖像素处需要计算深度值被多个多边形覆盖的像素需要多次计算深度值39隐藏面的消除-扫描线相关算法（4/5）改进：区间扫描线算法在一条扫描线上，以区间为单位确定多边形的可见性小区间上没有任何多边形——用背景色显示小区间上只有一个多边形——用对应多边形在该小区间内的颜色显示小区间存在两个或两个以上的多边形——通过深度测试判断哪个多边形是可见的，然后，用可见多边形的颜色来显示40隐藏面的消除-扫描线相关算法（5/5）例外：多边形相互贯穿图7-23扫描线的区间细分xy扫描线ABCxzabcdefxzabcdefg(a)多边形在屏幕上的投影(b)无贯穿的多边形(c)相互贯穿的多边形41隐藏面的消除-Warnock算法（1/4）Warnock算法图像空间消隐算法区域的连贯性也称区域细分area-subdivision实质分而治之42隐藏面的消除-Warnock算法（2/4）基本思想观察整个窗口区域判别窗口是否单纯窗口内无任何可见物体窗口已被一个可见面片完全充满将非单纯的窗口四等分为四个子窗口对每个子窗口再进一步判别是否是单纯的直到窗口单纯或窗口边长已缩至一个象素点为止

即使1024×1024分辨率视图被细分10次后，也能使每个子窗口覆盖一个像素

43隐藏面的消除-Warnock算法（3/4）关键步骤分析观察窗口与所有投影后多边形面片之间的关系分离内含相交包围——判别窗口是否单纯44隐藏面的消除-Warnock算法（4/4）基本步骤对每个窗口判断与多边形分离仅包含一个多边形与一个多边形相交被一个多边形所包围且窗口内无其它多边形若至少被一个多边形所包围，且此多边形距离视点最近——最关键否则继续细分窗口，并重复以上测试45隐藏面的消除-Warnock算法（4/4）(1)将初始窗口入栈；(2)

栈空结束。否则，取出栈顶窗口转步骤(3)；(3)

检测确定当前窗口与多边形关系，若

A．条件①为真,以背景颜色显示当前窗口，转步骤(2)；

B．条件②为真，多边形内区域，以该多边形颜色显示，其它区域以背景颜色显示，转步骤(2)；

C．条件③为真,相交多边形位于窗口内的区域以该多边形颜色显示,其它区域以背景颜色显示,转步骤(2)；

D．条件④为真,以包围多边形颜色显示当前窗口,转步骤(2)；

E．条件①～④均不满足，转步骤(4)。(4)

对当前窗口进行再细分，细分后的子窗口存入堆栈，转(2)。46

光线投射算法（1/4）RayCastingAppel提出建立在几何光学基础之上的可见面判别算法对于包含曲面、特别是球面的场景效率高47

光线投射算法（2/4）基本思想观察者之所以能看见景物光源发出的光照射到物体上的结果其中一部分光到达人的眼睛引起视觉到达观察者眼中的光由物体表面反射通过表面折射或透射若从光源出发跟踪光线则只有极少量的光能到达观察者的眼睛效率低从视点或像素出发，仅对穿过像素的光线反向跟踪当光线路径到达一个可见的不透明物体的表面时停止追踪48将景物通过透视投影变换到图像空间反向跟踪一条穿过像素点的光线决定它与场景中的哪一景物表面相交交点按深度排序需求出该光线与景物表面的所有可能的交点具有最大z值的交点对应的面就是屏幕上该像素对应的可见面离视点最近该像素处的显示值由相应物体的属性决定对屏幕上所有像素都进行如上处理后，算法结束

视点光线投影面上的像素位置物体假设视点位于z轴正向投影平面（屏幕）垂直于z轴反向跟踪一条穿过像素点的光线光线投射算法（3/4）49光线投射算法（4/4）光线投射算法{for(y=0;y<=ymax;y++)for(x=0;x<=xmax;x++){形成通过像素(x,y)的投影线；

for(场景中的每一个多边形） 将投影线与多边形求交；

if(有交点)

以最近交点所属多边形的颜色显示像素(x,y);else

以背景颜色显示像素(x,y);}}50阴影生成（1/10）什么是阴影光源不能直接照射的区域对光源来说，不可见的面（隐藏面）考虑阴影的光照明方程51阴影生成（2/10）消隐的结果对于判别为不可见的点、线、面（透明和半透明物体除外）都予以消除，即不显示

阴影测试：判断视点、光源以及物体间的位置关系从视点可见，从光源也可见被测点与视点之间无任何遮挡利用光照模型计算该点的光亮度从视点可见，从光源不可见阴影区域，置为该机器的最大像素值相对于部分光源可见，相对于另一部分光源不可见在多光源的情况下52阴影生成（3/10）当观察方向与光源方向重合时观察者看不到任何阴影可以不进行阴影测试当观察方向与光源方向不一致或光源多且光源体制比较复杂时必须进行阴影