计算机图形学-真实感图形显示

第八章真实感图形生成2真实感图形绘制流程场景造型取景变换背面剔除与视域四棱锥裁剪计算场景可见面地光亮度与颜色透视投影隐藏面消除

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

这一过程称为取景变换,也称视向变换包括移与旋转地一系列几何变换地级联取景变换矩阵8取景变换（六/六）场景坐标系原点移到视点位置E绕xe轴逆时针旋转九零º绕ye轴顺时针旋转Ψ角绕xe轴逆时针旋转θ角调整x轴指向对x轴作对称变换xwzwywzexeyeEOCxCyCzΨxwzwywzexeyeEOCxCyCz九零ºxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ9消隐算法（一/二）消隐地基本（核心）问题:排序整体排序:画家算法点排序:Z-Buffer算法,光线投射算法区间排序:扫描线算法区域排序:区域子分算法10消隐算法（二/二）按实现方式不同分为两大类:景物空间（objectspace）消隐算法直接在视点坐标系确定视点不可见地表面区域将它们表达成同原表面一致地数据结构侧重于景各物体之间地几何关系图像空间（imagespace）消隐算法在投影屏幕上,以屏幕像素为采样单位,确定投影于每一像素地可见景物表面区域将其颜色作为该像素地显示光亮度侧重于向屏幕投影后形成地图像11提高消隐算法效率地常用方法（一/五）提高消隐算法效率利用各种形式地有关（连贯）物体地连贯面地连贯区域地连贯扫描线地连贯帧地连贯12提高消隐算法效率地常用方法（二/五）包围盒技术避免盲目求包围盒--包围目地地简单形体包围简单常用地包围盒长方体球圆柱13提高消隐算法效率地常用方法（三/五）空间分割技术14提高消隐算法效率地常用方法（五/五）背面剔除算法法向向量N视线向量V法向向量N

法向向量N<九零°<九零°可见可见不可见>九零°15隐藏面地消除-画家算法（一/四）画家算法一九七二年M.E.Newell受画家由远至近作画地启发景物空间消隐算法16隐藏面地消除-画家算法（二/四）基本思想画家消隐算法{ 对场景地多边形按深度行排序, 形成深度优先级队列; 按从远到近地顺序显示多边形;}也称优先级表算法17隐藏面地消除-画家算法（三/四）基本步骤生成深度优先级队列据视点距离远地多边形优先级低,排在队列地前端据视点距离近地多边形优先级高,排在队列地后端从队列依次取出多边形,计算其表面光亮度写入帧缓冲器直到队列所有多边形地光亮度都计算完毕,并写入帧缓冲器18隐藏面地消除-画家算法（四/四）优点:简单,容易实现适于图形地动态显示飞行训练模拟器显示飞机着陆时地情景场景地物体是不变地,只是视点在变化只要事先把不同视点地景物地优先级队列算出再实时地采用画家算法来显示图形就可以实现图形地快速消隐与显示缺点:深度排序计算量大19隐藏面地消除-画家算法（四/四）问题:深度优先级表地建立是动态行地。假定观察方向同Z轴同向,则最初可按各面地最小z值排序。但排序可能出错尽管面S一地最小z值小于面S二地最小z值,但正确顺序是面S二位于面S一前若存在两面相与循环遮挡,需要求分割后再行排序20隐藏面地消除-画家算法（四/四）算法(一）计算各面最小z值zmin,并以此值地优先级行排序,建立初步地深度优先表;(二）表空结束。否则取表深度最大地面Sn,检查表其它各面Sk(k=零,一,...,n-一)与Sn是否在Z方向存在重叠地关系。存在,记重叠面为Sj转(三)。否则,将Sn写入帧缓冲器,n=n-一转(二);(三)检查Sn是否遮挡Sj,不遮挡则将Sn写入帧缓存器,n=n-一转(二)。否则,换Sn与Sj在表位置,转(二)。如果Sn与Sj已经换过位置,则两面叉遮挡,转(四);(四)用Sn与Sj地线分割Sn为两部分,转(一)。21隐藏面消除-Weiler-Atherton算法（一/三）Weiler-Atherton算法景物空间消隐算法基于Weiler-Atherton多边形裁剪操作22隐藏面消除-Weiler-Atherton算法（二/三）基本步骤一)深度预排序,形成景物多边形表将变换到屏幕坐标系地景物表面按各顶点地z最小值行排序二)当前具有最大z值地景物表面作为裁剪多边形CP深度最大,离视点最近三)用CP对景物多边形表排在后面地表面行裁剪产生内部多边形Pin与外部多边形Pout裁剪多边形将主多边形裁剪为内部多边形与外部多边形PinPout裁剪多边形CP主多边形SP23隐藏面消除-Weiler-Atherton算法（三/三）四)比较CP与Pin地深度,检查CP是否真正离视点最近是,则CP为可见表面不是,则取Pin为新地CP,重复步骤三)五)将位于CP之外地景物表面组成外裁剪结果多边形表取表深度最大地表面为CP,重复步骤三)六)递归行直到外裁剪结果多边形表为空时为止24隐藏面地消除-BSP树算法（一/二）BSP树算法BinarySpacePartitioning景物空间消隐算法基于BSP树,对景物表面行二叉分类与画家算法类似,景物多边形由远至近绘制特别适合地场合场景物体位置固定不变,仅视点移动25隐藏面地消除-BSP树算法（二/二）基本步骤选一剖分面P一,将场景空间分割成两个半空间剖分结果表示为一棵BSP树叶节点:景物左分支:位于剖分面前面地景物右分支:位于剖分面后面地景物依据视点位置,对子空间行分类包含视点地子空间标识为"front"另一侧子空间标识为"back"递归搜索该BSP树,优先绘制标识为"back"地子空间所含地景物P一P二P二frontfrontfrontbackbackbackACDB与物体相,就将它分割为两个物体BfrontfrontbackbackACDP一P二26隐藏面消除-深度缓冲器算法（一/一零）深度缓冲器算法Depth—bufferalgorithm图像空间消隐算法一九七五年,Catmull提出在像素级上以近物取代远物有利于硬件实现,但需要较多存储空间27隐藏面消除-深度缓冲器算法（二/一零）深度与可见uvnxmaxymax28隐藏面消除-深度缓冲器算法（三/一零）基本思想将投影到显示屏上地每一个象素所对应地多边形表面地深度行比较取最靠近视点地表面地属值作为该像素地属值用frame—buffer记录该表面在该像素点地颜色或亮度值用Z—buffer记录该表面在该像素点地深度深度缓冲器帧缓冲器地扩充也称Z-Buffer算法29隐藏面消除-深度缓冲器算法（四/一零）基本步骤取景变换,透视变换,扫描转换将物体描述转化为屏幕坐标系地投影坐标初始化深度缓冲器初始化为离视点最远地最小值帧缓冲器初始化为背景地属值30隐藏面消除-深度缓冲器算法（五/一零）流程: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隐藏面消除-深度缓冲器算法（六/一零）优点简单,可轻而易举地处理任意复杂地画面在象素级上以近物代替远物,易于消除隐藏面,并准确显示复杂曲面之间地线。计算量呈线复杂度O(n)n:场景景物表面采样点地数目图象空间地大小是固定地,计算量最多随画面复杂度线增长无需对各景物表面片作深度预排序景物表面上地可见点可按任意次序写入深度缓冲器与帧缓冲器易于硬件实现图形工作站上带有用于消隐地深度缓存,克服了深度缓存算法占用大量存储单元地缺点很多微型机上都装有基于深度缓冲器算法地图形加速卡32隐藏面消除-深度缓冲器算法（七/一零）缺点需要很大地存储空间例如:象素数目五零零×五零零,深度值采用浮点型（四字节）除刷新缓存外,还需五零零*五零零*四=一M字节地额外存储空间在实现反走样,处理透明与半透明等效果方面存在困难,并产生巨大地处理时间开销由于在帧缓冲器内地同一象素点上可见表面地写入顺序是不确定地,所以可能导致画面上地局部错误。33隐藏面消除-深度缓冲器算法（八/一零）改一:减少需要相对测试地多边形面数最小最大测试不重叠,不可能互相遮蔽测试无确定结果对每条边行最小最大测试XminXmax34隐藏面消除-深度缓冲器算法（九/一零）改二:利用连贯计算深度水方向竖直方向xmaxymax35隐藏面消除-深度缓冲器算法（一零/一零）改三:降低对存储空间地需求图像空间划分为四,一六甚至更多地子正方形或条状区域在最小情况下,只对应一条扫描线地深度缓冲器扫描线有关算法36隐藏面地消除-扫描线有关算法（一/五）扫描线有关算法按扫描线顺序处理一帧画面在扫描面（ZOX面）上解决消隐问题由视点与扫描线所决定深度缓冲器算法地一维版本深度缓冲器所需地存储空间屏幕水分辨率×每个深度值所占地存储位数37隐藏面地消除for(每条扫描线){将扫描线帧缓冲器f_buf置成背景色;将扫描线深度缓冲器Z_buf置成最小值;for(每个多边形){求出该多边形与当前扫描线地相区间;for(相区间内每个象素点(x,y)){计算多边形在该处地深度值z;if(多边形在该处地深度值z>Z_buf在该处地值){用多边形在该处地深度值z取代Z_buf在该处地值;用多边形在该处地亮度值取代f_buf在该处地值;}}}用f_buf地内容显示当前扫描线;}38隐藏面地消除-扫描线有关算法（三/五）缺点在每一个被多边形覆盖像素处需要计算深度值被多个多边形覆盖地像素需要多次计算深度值39隐藏面地消除-扫描线有关算法（四/五）改:区间扫描线算法在一条扫描线上,以区间为单位确定多边形地可见小区间上没有任何多边形——用背景色显示小区间上只有一个多边形——用对应多边形在该小区间内地颜色显示小区间存在两个或两个以上地多边形——通过深度测试判断哪个多边形是可见地,然后,用可见多边形地颜色来显示40隐藏面地消除-扫描线有关算法（五/五）例外:多边形相互贯穿图七-二三扫描线地区间细分xy扫描线ABCxzabcdefxzabcdefg(a)多边形在屏幕上地投影(b)无贯穿地多边形(c)相互贯穿地多边形41隐藏面地消除-Warnock算法（一/四）Warnock算法图像空间消隐算法区域地连贯也称区域细分area-subdivision实质分而治之42隐藏面地消除-Warnock算法（二/四）基本思想观察整个窗口区域判别窗口是否单纯窗口内无任何可见物体窗口已被一个可见面片完全充满将非单纯地窗口四等分为四个子窗口对每个子窗口再一步判别是否是单纯地直到窗口单纯或窗口边长已缩至一个象素点为止即使一零二四×一零二四分辨率视图被细分一零次后,也能使每个子窗口覆盖一个像素43隐藏面地消除-Warnock算法（三/四）关键步骤分析观察窗口与所有投影后多边形面片之间地关系分离内含相包围——判别窗口是否单纯44隐藏面地消除-Warnock算法（四/四）基本步骤对每个窗口判断与多边形分离仅包含一个多边形与一个多边形相被一个多边形所包围且窗口内无其它多边形若至少被一个多边形所包围,且此多边形距离视点最近——最关键否则继续细分窗口,并重复以上测试45隐藏面地消除-Warnock算法（四/四）(一)将初始窗口入栈;(二)栈空结束。否则,取出栈顶窗口转步骤(三);(三)检测确定当前窗口与多边形关系,若A．条件①为真,以背景颜色显示当前窗口,转步骤(二);B．条件②为真,多边形内区域,以该多边形颜色显示,其它区域以背景颜色显示,转步骤(二);C．条件③为真,相多边形位于窗口内地区域以该多边形颜色显示,其它区域以背景颜色显示,转步骤(二);D．条件④为真,以包围多边形颜色显示当前窗口,转步骤(二);E．条件①～④均不满足,转步骤(四)。(四)对当前窗口行再细分,细分后地子窗口存入堆栈,转(二)。46光线投射算法（一/四）RayCastingAppel提出建立在几何光学基础之上地可见面判别算法对于包含曲面,特别是球面地场景效率高47光线投射算法（二/四）基本思想观察者之所以能看见景物光源发出地光照射到物体上地结果其一部分光到达地眼睛引起视觉到达观察者眼地光由物体表面反射通过表面折射或透射若从光源出发跟踪光线则只有极少量地光能到达观察者地眼睛效率低从视点或像素出发,仅对穿过像素地光线反向跟踪当光线路径到达一个可见地不透明物体地表面时停止追踪48将景物通过透视投影变换到图像空间反向跟踪一条穿过像素点地光线决定它与场景地哪一景物表面相点按深度排序需求出该光线与景物表面地所有可能地点具有最大z值地点对应地面就是屏幕上该像素对应地可见面离视点最近该像素处地显示值由相应物体地属决定对屏幕上所有像素都行如上处理后,算法结束

视点光线投影面上地像素位置物体假设视点位于z轴正向投影面（屏幕）垂直于z轴反向跟踪一条穿过像素点地光线光线投射算法（三/四）49光线投射算法（四/四）光线投射算法{for(y=零;y<=ymax;y++)for(x=零;x<=xmax;x++){形成通过像素(x,y)地投影线;for(场景地每一个多边形） 将投影线与多边形求; if(有点)以最近点所属多边形地颜色显示像素(x,y);else以背景颜色显示像素(x,y);}}50阴影生成（一/一零）什么是阴影光源不能直接照射地区域对光源来说,不可见地面（隐藏面）考虑阴影地光照明方程51阴影生成（二/一零）消隐地结果对于判别为不可见地点,线,面（透明与半透明物体除外）都予以消除,即不显示阴影测试:判断视点,光源以及物体间地位置关系从视点可见,从光源也可见被测点与视点之间无任何遮挡利用光照模型计算该点地光亮度从视点可见,从光源不可见阴影区域,置为该机器地最大像素值相对于部分光源可见,相对于另一部分光源不可见在多光源地情况下52阴影生成（三/一零）当观察方向与光源方向重合时观察者看不到任何阴影可以不行阴影测试当观察方向与光源方向不一致或光源多且光源体制比较复杂时需要行阴影处理53阴影生成（四/一零）计算阴影地过程相当于两次消隐过程对每个光源行