可見面判別算法第1頁，共42頁，2023年，2月20日，星期一

真實感圖形繪制流程場景造型取景變換背面剔除視域四棱錐裁剪透視變換隱面消除、場景造型光亮度計算掃描轉(zhuǎn)換、場景造型第2頁，共42頁，2023年，2月20日，星期一取景變換（1/5）場景坐標(biāo)系場景的局部坐標(biāo)系完成物體的造型場景的世界坐標(biāo)系（整體坐標(biāo)系）放入待繪制的場景，定義物體之間的相互位置觀察坐標(biāo)系也稱攝像機(jī)坐標(biāo)系，或者視點坐標(biāo)系完成取景變換所需建立的第一個坐標(biāo)系第3頁，共42頁，2023年，2月20日，星期一取景變換（2/5）建立觀察坐標(biāo)系的步驟確定觀察參考點，即視點位置可以設(shè)在任何位置通常選在靠近或在物體的表面將視點位置取為視點坐標(biāo)系的原點確定觀察方向，即視線方向一般取深度坐標(biāo)軸，即ze軸的正向為簡便起見，設(shè)為總是指向場景坐標(biāo)系的原點確定觀察平面，即視平面位置一般取過視點且垂直于視線方向的平面，即xeye平面第4頁，共42頁，2023年，2月20日，星期一取景變換（3/5）場景坐標(biāo)系一般取右手坐標(biāo)系觀察坐標(biāo)系通常取左手坐標(biāo)系符合人們的觀察習(xí)慣xwzwywzexeye視點E觀察坐標(biāo)系為左手坐標(biāo)系場景坐標(biāo)系為右手坐標(biāo)系O第5頁，共42頁，2023年，2月20日，星期一取景變換（4/5）將物體投影到觀察平面之前必須將場景坐標(biāo)系中的點轉(zhuǎn)換到觀察坐標(biāo)系中

這一過程稱為取景變換，也稱視向變換包括平移和旋轉(zhuǎn)的一系列幾何變換的級聯(lián)取景變換矩陣第6頁，共42頁，2023年，2月20日，星期一取景變換（5/5）場景坐標(biāo)系原點平移到視點位置E繞xe軸逆時針旋轉(zhuǎn)90o繞ye軸順時針旋轉(zhuǎn)Ψ角繞xe軸逆時針旋轉(zhuǎn)θ角調(diào)整x軸指向?qū)軸作對稱變換xwzwywzexeyeEOCxCyCzΨxwzwywzexe

yeEOCxCyCz90oxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ第7頁，共42頁，2023年，2月20日，星期一消隱算法按實現(xiàn)方式不同分為兩大類：景物空間（objectspace）消隱算法直接在視點坐標(biāo)系中確定視點不可見的表面區(qū)域?qū)⑺鼈儽磉_(dá)成同原表面一致的數(shù)據(jù)結(jié)構(gòu)側(cè)重于景中各物體之間的幾何關(guān)系圖像空間（imagespace）消隱算法

在投影屏幕上，以屏幕像素為采樣單位，確定投影于每一像素的可見景物表面區(qū)域?qū)⑵漕伾鳛樵撓袼氐娘@示光亮度側(cè)重于向屏幕投影后形成的圖像第8頁，共42頁，2023年，2月20日，星期一背面剔除算法背面剔除算法

法向向量N視線向量V法向向量N

法向向量N<90°<90°可見可見不可見>90°第9頁，共42頁，2023年，2月20日，星期一隱藏面的消除-畫家算法

（1/3）畫家算法

1972年M.E.Newell受畫家由遠(yuǎn)至近作畫的啟發(fā)景物空間消隱算法第10頁，共42頁，2023年，2月20日，星期一隱藏面的消除-畫家算法

（2/3）基本步驟生成深度優(yōu)先級隊列據(jù)視點距離遠(yuǎn)的多邊形優(yōu)先級低，排在隊列的前端據(jù)視點距離近的多邊形優(yōu)先級高，排在隊列的后端從隊列中依次取出多邊形，計算其表面光亮度寫入幀緩沖器

直到隊列中所有多邊形的光亮度都計算完畢，并寫入幀緩沖器第11頁，共42頁，2023年，2月20日，星期一隱藏面的消除-畫家算法

（3/3）優(yōu)點：透明或半透明物體圖形的動態(tài)顯示飛行訓(xùn)練模擬器中顯示飛機(jī)著陸時的情景場景中的物體是不變的，只是視點在變化只要事先把不同視點的景物的優(yōu)先級隊列算出再實時地采用畫家算法來顯示圖形就可以實現(xiàn)圖形的快速消隱與顯示第12頁，共42頁，2023年，2月20日，星期一隱藏面消除-Weiler-Atherton算法（1/3）Weiler-Atherton算法景物空間消隱算法基于Weiler-Atherton多邊形裁剪操作第13頁，共42頁，2023年，2月20日，星期一隱藏面消除-Weiler-Atherton算法（2/3）基本步驟

1)深度預(yù)排序，形成景物多邊形表

將變換到屏幕坐標(biāo)系中的景物表面按各頂點的z最小值進(jìn)行排序2)當(dāng)前具有最大z值的景物表面作為裁剪多邊形CP

深度最大、離視點最近3)用CP對景物多邊形表中排在后面的表面進(jìn)行裁剪

產(chǎn)生內(nèi)部多邊形Pin和外部多邊形Pout

裁剪多邊形將主多邊形裁剪為內(nèi)部多邊形和外部多邊形B1B2裁剪多邊形Pc主多邊形Ps第14頁，共42頁，2023年，2月20日，星期一隱藏面消除-Weiler-Atherton算法（3/3）4)比較Pc與Pin的深度，檢查Pc是否真正離視點最近是，則Pc為可見表面不是，則取Pin為新的Pc，重復(fù)步驟3)5)將位于Pc之外的景物表面組成外裁剪結(jié)果多邊形表

取表中深度最大的表面為Pc，重復(fù)步驟3)6)遞歸進(jìn)行直到外裁剪結(jié)果多邊形表為空時為止

第15頁，共42頁，2023年，2月20日，星期一隱藏面的消除-BSP樹算法（1/2）BSP樹算法BinarySpacePartitioning景物空間消隱算法基于BSP樹，對景物表面進(jìn)行二叉分類與畫家算法類似，景物多邊形由遠(yuǎn)至近繪制特別適合的場合

場景中物體位置固定不變、僅視點移動第16頁，共42頁，2023年，2月20日，星期一隱藏面的消除-BSP樹算法（2/2）基本步驟

選一剖分平面P1，將場景空間分割成兩個半空間剖分結(jié)果表示為一棵BSP樹葉節(jié)點：景物左分支：位于剖分平面前面的景物右分支：位于剖分平面后面的景物依據(jù)視點位置，對子空間進(jìn)行分類包含視點的子空間標(biāo)識為“front”另一側(cè)子空間標(biāo)識為“back”遞歸搜索該BSP樹，優(yōu)先繪制標(biāo)識為“back”的子空間中所含的景物

BfrontfrontbackbackACDP1P2P2frontfrontfrontbackbackbackACDB第17頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（1/8）深度緩沖器算法Depth—bufferalgorithm圖像空間消隱算法1975年，Catmull提出第18頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（2/8）基本思想將投影到顯示屏上的每一個象素所對應(yīng)的多邊形表面的深度進(jìn)行比較取最靠近視點的表面的屬性值作為該像素的屬性值用Z—buffer記錄該表面在該像素點的深度用frame—buffer記錄該表面在該像素點的顏色或亮度值第19頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（3/8）深度緩沖器幀緩沖器的擴(kuò)充也稱Z-Buffer算法第20頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（4/8）流程：for（場景中的每一個多邊形）{

掃描轉(zhuǎn)換該多邊形；

for（多邊形所覆蓋的每一個像素點(x,y)）

{

計算多邊形在該像素點的深度值z(x,y)；

if（z(x,y)>Z-buf中對應(yīng)此像素點(x,y)的z值）

{

把多邊形在(x,y)處的深度值z(x,y)存入Z-buf中的(x,y)處；把多邊形在(x,y)處的亮度值存入f-buf中的(x,y)處；

}}}當(dāng)所有的多邊形都處理完后，幀緩沖器中的內(nèi)容即為消除隱藏面后的圖像第21頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（5/8）優(yōu)點簡單在象素級上以近物代替遠(yuǎn)物，易于消除隱藏面，并準(zhǔn)確顯示復(fù)雜曲面之間的交線。計算量呈線性復(fù)雜度場景中景物表面采樣點的數(shù)目無需對各景物表面片作深度預(yù)排序景物表面上的可見點可按任意次序?qū)懭肷疃染彌_器和幀緩沖器易于硬件實現(xiàn)圖形工作站上配置由硬件實現(xiàn)的深度緩沖器算法很多微型機(jī)上都裝有基于深度緩沖器算法的圖形加速卡第22頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（6/8）缺點需要很大的存儲空間象素數(shù)目為500×500，深度值采用浮點類型（4字節(jié)）除刷新緩存外，還需500*500*4=1M字節(jié)的額外存儲空間在實現(xiàn)反走樣、處理透明和半透明等效果方面存在困難，并由此會產(chǎn)生巨大的處理時間開銷由于在幀緩沖器內(nèi)的同一象素點上可見表面的寫入順序是不確定的，所以可能導(dǎo)致畫面上的局部錯誤。第23頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（7/8）改進(jìn)一：減少需要相對測試的多邊形平面數(shù)最小最大測試

不重疊,不可能互相遮蔽測試無確定結(jié)果對每條邊進(jìn)行最小最大測試XminXmax第24頁，共42頁，2023年，2月20日，星期一隱藏面消除-深度緩沖器算法（8/8）改進(jìn)二：利用連貫性計算深度水平方向豎直方向改進(jìn)三：降低對存儲空間的需求圖像空間劃分為4、16甚至更多的子正方形或條狀區(qū)域在最小情況下，只對應(yīng)一條掃描線的深度緩沖器掃描線相關(guān)算法第25頁，共42頁，2023年，2月20日，星期一隱藏面的消除-掃描線相關(guān)算法（1/3）掃描線相關(guān)算法按掃描線順序處理一幀畫面在掃描平面（ZOX平面）上解決消隱問題由視點和掃描線所決定深度緩沖器算法的一維版本深度緩沖器所需的存儲空間屏幕水平分辨率×每個深度值所占的存儲位數(shù)第26頁，共42頁，2023年，2月20日，星期一隱藏面的消除for(每條掃描線){

將掃描線幀緩沖器f_buf置成背景色；將掃描線深度緩沖器Z_buf置成最小值；

for(每個多邊形){

求出該多邊形與當(dāng)前掃描線的相交區(qū)間；

for(相交區(qū)間內(nèi)每個象素點(x,y)){

計算多邊形在該處的深度值z；

if(多邊形在該處的深度值z>Z_buf在該處的值){

用多邊形在該處的深度值z取代Z_buf在該處的值；用多邊形在該處的亮度值取代f_buf在該處的值；

}}}

用f_buf的內(nèi)容顯示當(dāng)前掃描線；}第27頁，共42頁，2023年，2月20日，星期一隱藏面的消除-掃描線相關(guān)算法（3/3）缺點在每一個被多邊形覆蓋像素處需要計算深度值被多個多邊形覆蓋的像素需要多次計算深度值改進(jìn)在一條掃描線上，以區(qū)間為單位確定多邊形的可見性第28頁，共42頁，2023年，2月20日，星期一隱藏面的消除-Warnock算法（1/4）Warnock算法圖像空間消隱算法區(qū)域的連貫性也稱區(qū)域細(xì)分area-subdivision實質(zhì)分而治之第29頁，共42頁，2023年，2月20日，星期一隱藏面的消除-Warnock算法（2/4）基本思想觀察整個窗口區(qū)域判別窗口是否單純窗口內(nèi)無任何可見物體窗口已被一個可見面片完全充滿將非單純的窗口四等分為四個子窗口對每個子窗口再進(jìn)一步判別是否是單純的直到窗口單純或窗口邊長已縮至一個象素點為止

即使1024×1024分辨率視圖被細(xì)分10次后，也能使每個子窗口覆蓋一個像素

第30頁，共42頁，2023年，2月20日，星期一隱藏面的消除-Warnock算法（3/4）關(guān)鍵步驟分析觀察窗口與所有投影后多邊形面片之間的關(guān)系分離內(nèi)含相交包圍——判別窗口是否單純第31頁，共42頁，2023年，2月20日，星期一隱藏面的消除-Warnock算法（4/4）基本步驟對每個窗口判斷與多邊形分離僅包含一個多邊形與一個多邊形相交被一個多邊形所包圍且窗口內(nèi)無其它多邊形至少被一個多邊形所包圍，且此多邊形距離視點最近否則繼續(xù)細(xì)分窗口，并重復(fù)以上測試第32頁，共42頁，2023年，2月20日，星期一光線投射算法（1/4）RayCastingAppel提出建立在幾何光學(xué)基礎(chǔ)之上對于包含曲面、特別是球面的場景效率高第33頁，共42頁，2023年，2月20日，星期一光線投射算法（2/4）基本思想觀察者之所以能看見景物光源發(fā)出的光照射到物體上的結(jié)果其中一部分光到達(dá)人的眼睛引起視覺到達(dá)觀察者眼中的光由物體表面反射通過表面折射或透射若從光源出發(fā)跟蹤光線則只有極少量的光能到達(dá)觀察者的眼睛效率低從視點或像素出發(fā)，僅對穿過像素的光線反向跟蹤當(dāng)光線路徑到達(dá)一個可見的不透明物體的表面時停止追蹤第34頁，共42頁，2023年，2月20日，星期一將景物通過透視投影變換到圖像空間反向跟蹤一條穿過像素點的光線決定它與場景中的哪一景物表面相交交點按深度排序需求出該光線與景物表面的所有可能的交點具有最大z值的交點對應(yīng)的面就是屏幕上該像素對應(yīng)的可見面離視點最近該像素處的顯示值由相應(yīng)物體的屬性決定對屏幕上所有像素都進(jìn)行如上處理后，算法結(jié)束

視點光線投影面上的像素位置物體假設(shè)視點位于z軸正向投影平面（屏幕）垂直于z軸反向跟蹤一條穿過像素點的光線光線投射算法（3/4）第35頁，共42頁，2023年，2月20日，星期一光線投射算法（4/4）光線投射算法{for(y=0;y<=ymax;y++)for(x=0;x<=xmax;x++){形成通過像素(x,y)的投影線；

for(場景中的每一個多邊形） 將投影線與多邊形求交；

if(有交點)

以最近交點所屬多邊形的顏色顯示像素(x,y);else

以背景顏色顯示像素(x,y);}}第36頁，共4