（一）蘇小紅哈爾濱工業大學計算機科學與技術學院第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軸逆時針旋轉90o繞ye軸順時針旋轉Ψ角繞xe軸逆時針旋轉θ角調整x軸指向對x軸作對稱變換xwzwywzexeyeEOCxCyCzΨxwzwywzexeyeEOCxCyCz90oxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ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）當觀察方向與光源方向重合時觀察者看不到任何陰影可以不進行陰影測試當觀察方向與光源方向不一致或光源多且光源體制比較復雜時必須進行陰影