計算機圖形學(xué)講稿面消隱

1、2022/8/24浙江大學(xué)計算機圖形學(xué)1第九章 消隱消除隱藏面基本概念Z緩沖區(qū)(Z-Buffer)算法掃描線Z-buffer算法區(qū)間掃描線算法光線投射算法2022/8/24浙江大學(xué)計算機圖形學(xué)2基本概念投影變換失去了深度信息，往往導(dǎo)致圖形的二義性要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，簡稱為消隱。經(jīng)過消隱得到的投影圖稱為物體的真實圖形。 長方體線框投影圖的二義性 2022/8/24浙江大學(xué)計算機圖形學(xué)3基本概念消隱的對象是三維物體。三維體的表示主要有邊界表示和CSG表示等。消隱結(jié)果與觀察物體有關(guān)，也與視點有關(guān)。 線框圖 消隱圖 真實感圖形2022/

2、8/24浙江大學(xué)計算機圖形學(xué)4消隱的分類按消隱對象分類線消隱消隱對象是物體上的邊，消除的是物體上不可見的邊。 面消隱 消隱對象是物體上的面，消除的是物體上不可見的面。 2022/8/24浙江大學(xué)計算機圖形學(xué)5面消隱面消隱算法的分類Z緩沖器算法掃描線Z緩沖器算法 區(qū)間掃描線算法光線投射算法2022/8/24浙江大學(xué)計算機圖形學(xué)6面消隱算法的分類消隱算法的分類第一類（圖像空間的消隱算法）：以窗口內(nèi)的每個像素為處理單元；如Zbuffer、掃描線算法 for (窗口內(nèi)的每一個像素) 確定距視點最近的物體，以該物體表面的顏色來顯示像素 第二類（物體空間的消隱算法）：以場景中的物體為處理單元；如光線投射算

3、法for (場景中的每一個物體) 將其與場景中的其它物體比較，確定其表面的可見部分； 顯示該物體表面的可見部分； 2022/8/24浙江大學(xué)計算機圖形學(xué)7面消隱算法的分類第一類（圖像空間的消隱算法）：以窗口內(nèi)的每個像素為處理單元；for (窗口內(nèi)的每一個像素) 確定距視點最近的物體，以該物體表面的顏色來顯示像素假設(shè)場景中有k個物體，平均每個物體表面由h個多邊形構(gòu)成，顯示區(qū)域中有m x n個像素，則：算法的復(fù)雜度為：O(mnkh) 2022/8/24浙江大學(xué)計算機圖形學(xué)8面消隱算法的分類第二類（物體空間的消隱算法 ）：以場景中的物體為處理單元；for (場景中的每一個物體) 將其與場景中的其它物

4、體比較，確定其表面的可見部分；顯示該物體表面的可見部分；假設(shè)場景中有k個物體，平均每個物體表面由h個多邊形構(gòu)成，顯示區(qū)域中有m x n個像素，則：算法的復(fù)雜度為：O(kh)*(kh)2022/8/24浙江大學(xué)計算機圖形學(xué)9Z-Buffer算法由來： 幀緩沖器 保存各像素顏色值 Z緩沖器 -保存各像素處物體深度值 Z緩沖器中的單元與幀緩沖器中的單元一一對應(yīng)2022/8/24浙江大學(xué)計算機圖形學(xué)10Z-Buffer算法思想：先將Z緩沖器中每個單元的初始值置為最小值。當(dāng)要改變某個像素的顏色值時，首先檢查當(dāng)前多邊形的深度值是否大于該像素原來的深度值（保存在該像素所對應(yīng)的Z緩沖器的單元中），如果大于，說

5、明當(dāng)前多邊形更靠近觀察點，用它的顏色替換像素原來的顏色；否則說明在當(dāng)前像素處，當(dāng)前多邊形被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變。2022/8/24浙江大學(xué)計算機圖形學(xué)11Z-Buffer算法-算法描述 幀緩存全置為背景色深度緩存全置為最小Z值for(每一個多邊形) for(該多邊形所覆蓋的每個象素(x,y) ) 計算該多邊形在該象素的深度值Z(x,y); if(Z(x,y)大于Z緩存在(x,y)的值) 把Z(x,y)存入Z緩存中(x,y)處 把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處 需要計算的像素深度值次數(shù)=多邊形個數(shù)*多邊形平均占據(jù)的像素個數(shù)2022/8/2

6、4浙江大學(xué)計算機圖形學(xué)12Z-Buffer算法Z緩沖器算法是所有圖像空間算法中最簡單的一種隱藏面消除算法。它在象素級上以近物取代遠(yuǎn)物，與形體在屏幕上的出現(xiàn)順序無關(guān)。優(yōu)點：1）簡單穩(wěn)定，利于硬件實現(xiàn) 2）不需要整個場景的幾何數(shù)據(jù)缺點: 1）需要一個額外的Z緩沖器 2）在每個多邊形占據(jù)的每個像素處都要計算深度值，計算量大 2022/8/24浙江大學(xué)計算機圖形學(xué)13Z-Buffer算法-改進算法只用一個深度緩存變量zb的改進算法。一般認(rèn)為，Z-Buffer算法需要開一個與圖象大小相等的緩存數(shù)組ZB，實際上，可以改進算法，只用一個深度緩存變量zb。2022/8/24浙江大學(xué)計算機圖形學(xué)14Z-Buff

7、er算法-改進算法過程幀緩存全置為背景色for(屏幕上的每個象素(i,j) 深度緩存變量zb置最小值MinValue for(多面體上的每個多邊形Pk) if(象素點(i,j)在pk的投影多邊形之內(nèi))計算Pk在(i,j)處的深度值depth;if(depth大于zb)zb = depth;indexp = k; if(zb != MinValue) 在交點 (i,j) 處用多邊形Pindexp的顏色顯示 2022/8/24浙江大學(xué)計算機圖形學(xué)15Z-Buffer算法-改進算法關(guān)鍵問題：判斷象素點(i,j)是否在多邊形Pk的投影多邊形之內(nèi)計算多邊形Pk在點（i，j）處的深度。設(shè)多邊形Pk的平面方

8、程為：2022/8/24浙江大學(xué)計算機圖形學(xué)16掃描線Z-buffer算法由來：Z緩沖器算法中所需要的Z緩沖器容量較大，為克服這個缺點可以將整個繪圖區(qū)域分割成若干個小區(qū)域，然后一個區(qū)域一個區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個區(qū)域內(nèi)像素的個數(shù)就可以了。如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法。2022/8/24浙江大學(xué)計算機圖形學(xué)17掃描線Z-buffer算法算法思想:在處理當(dāng)前掃描線時，開一個一維數(shù)組作為當(dāng)前掃描線的Z-buffer。首先找出與當(dāng)前掃描線相關(guān)的多邊形，以及每個多邊形中相關(guān)的邊對。對每一個邊對之間的小區(qū)間上的各象素，計算深度，并與Z-buffer中的值比較

9、，找出各象素處可見平面。寫幀緩存。采用增量算法計算深度。2022/8/24浙江大學(xué)計算機圖形學(xué)18掃描線Z-buffer算法for ( v= 0;vvmax;v+)for (u= 0; u Z緩沖器的第u單元的值） 置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第u單元值為d; /處理下一條掃描線2022/8/24浙江大學(xué)計算機圖形學(xué)19掃描線Z-buffer算法改進之一：將窗口分割成掃描線Z緩沖器的單元數(shù)只要等于一條掃描線內(nèi)像素的個數(shù)就可以了。2022/8/24浙江大學(xué)計算機圖形學(xué)20掃描線Z-buffer算法改進之二：采用多邊形分類表、活化多邊形表避免多邊形與掃描線的盲目求

10、交2022/8/24浙江大學(xué)計算機圖形學(xué)21掃描線Z-buffer算法-多邊形分類表多邊形分類表（PT）：對多邊形進行分類的一維數(shù)組，長度等于繪圖窗口內(nèi)掃描線的數(shù)目。若一個多邊形在投影平面上的投影的最小v坐標(biāo)為v，則它屬于第v類。2022/8/24浙江大學(xué)計算機圖形學(xué)22掃描線Z-buffer算法-活化多邊形表活化多邊形表（APL）：記錄投影與當(dāng)前掃描線相交的多邊形。2022/8/24浙江大學(xué)計算機圖形學(xué)23掃描線Z-buffer算法-多邊形其中，多邊形的數(shù)據(jù)結(jié)構(gòu)如下：a,b,c,d：多邊形所在平面方程f(u,v,n)=au+bv+cn+d=0的系數(shù)。color:多邊形的顏色vmax:多邊形在

11、投影平面上的投影的最大v坐標(biāo)值。PI：多邊形的序號nextP：指向下一個多邊形結(jié)構(gòu)的指針2022/8/24浙江大學(xué)計算機圖形學(xué)24掃描線Z-buffer算法改進之三：利用邊、邊的分類表、邊對、活化邊對表避免邊與掃描線的盲目求交2022/8/24浙江大學(xué)計算機圖形學(xué)25掃描線Z-buffer算法-邊數(shù)據(jù)結(jié)構(gòu)邊：用來記錄多邊形的一條邊，其中vmax：邊的投影的上端點的v坐標(biāo)。u：邊的下端點的u坐標(biāo)n：邊的下端點的n坐標(biāo) Du：在該邊上v值增加一個單位時，u坐標(biāo)的變化量DnextE：指向下一條邊結(jié)構(gòu)的指針。2022/8/24浙江大學(xué)計算機圖形學(xué)26掃描線Z-buffer算法-邊的分類表邊的分類表（E

12、T）：當(dāng)一個多邊形進入活化多邊形表時，需為其建立一個邊分類表（ET）。這里，ET與其在掃描轉(zhuǎn)換多邊形的掃描線算法中的含義相同，是對多邊形的非水平邊進行分類的一維數(shù)組，長度等于繪圖窗口內(nèi)掃描線的數(shù)目。若一條邊在投影平面上的投影的下端點的v坐標(biāo)為v，則將該邊歸為第v類。2022/8/24浙江大學(xué)計算機圖形學(xué)27掃描線Z-buffer算法-邊對邊對：在一條掃描線上，同一多邊形的相鄰兩條邊構(gòu)成一個邊對。邊對中包含了如下信息：ul ：邊對的左側(cè)邊與掃描交點的u坐標(biāo)ul ：當(dāng)沿左側(cè)邊v坐標(biāo)遞增一個像素時， u坐標(biāo)的增量vlmax ：左側(cè)邊投影的上端點的v坐標(biāo)。2022/8/24浙江大學(xué)計算機圖形學(xué)28掃描

13、線Z-buffer算法-邊對ur ：邊對的右側(cè)邊與掃描交點的u坐標(biāo)ur ：當(dāng)沿右側(cè)邊v坐標(biāo)遞增一個像素時， u坐標(biāo)的增量vrmax ：右側(cè)邊投影的上端點的v坐標(biāo)。nl ：左側(cè)邊與掃描線交點的n坐標(biāo)PI ：多邊形的序號2022/8/24浙江大學(xué)計算機圖形學(xué)29掃描線Z-buffer算法-邊對nu ：當(dāng)沿掃描線u遞增一個像素時，多邊形所在平面n坐標(biāo)的增量，對方程au+bv+cn+d=0來說，nu =-a/c nv ：當(dāng)沿掃描線v遞增一個像素時，多邊形所在平面n坐標(biāo)的增量，類似，nv =-b/c (c!=0)nextEP:指向下一個邊對結(jié)構(gòu)的指針。2022/8/24浙江大學(xué)計算機圖形學(xué)30掃描線Z-

14、buffer算法-活化邊表對活化邊表對（AEPL）：記錄了活化多邊形表中與當(dāng)前掃描線相交的邊對，邊對在AEPL中的順序無關(guān)緊要。2022/8/24浙江大學(xué)計算機圖形學(xué)31掃描線Z-buffer算法改進之四：利用連貫性計算深度水平方向:當(dāng)沿掃描線u遞增一個像素時，多邊形所在平面n坐標(biāo)的增量，對方程au+bv+cn+d=0來說，nu =-a/c 豎直方向nv ：當(dāng)沿掃描線v遞增一個像素時，多邊形所在平面n坐標(biāo)的增量，nv =-b/c下一條掃描線與邊對左側(cè)邊交點處的深度值： nl=nl+DnuDul+Dnvumaxvmax2022/8/24浙江大學(xué)計算機圖形學(xué)32掃描線Z-buffer算法1、建多邊

15、形分類表：對每一個多邊形,若它在投影平面上的投影的最小v坐標(biāo)為v，則它屬于第v類。2、置活化多邊形表APL為空，置活化邊對表AEPL為空。3、對每條掃描線v，執(zhí)行下列步驟：（1）置幀緩存器第v行中的各單元為背景色。（2）置Z緩沖器各單元的值為最小的深度值。（3）檢查PT(多邊形分類表)的第v類是否非空，如果非空，將該類中的多邊形取出加入APL(活化多邊形表)中。（4）對新加入APL(活化多邊形表)中的多邊形，為其建立邊的分類表ET。（5）對新加入APL (活化多邊形表)中的多邊形，若它的ET（邊的分類表）中的第v類非空，將其中的邊配對插入AEPL（活化邊對表）中；2022/8/24浙江大學(xué)計算

16、機圖形學(xué)33掃描線Z-buffer算法（6）對AEPL（活化邊對表）中的每一個邊對，執(zhí)行下列步驟：深度值n=nl;for （u=ul;u Z緩沖器的第u單元的值） 置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色；置Z緩沖器的第u單元值為n; n=n+ nu;/計算下一個像素(u+1,v)處多邊形的深度值2022/8/24浙江大學(xué)計算機圖形學(xué)34掃描線Z-buffer算法（7）檢查APL (活化多邊形表) ，刪除那些滿足vmax=v的多邊形，釋放該多邊形的ET，并從AEPL（活化邊對表）中刪除屬于該多邊形的邊對。（8）檢查AEPL（活化邊對表）中的每一個邊對，執(zhí)行下列步驟： A 若vlmax=v

17、或vrmax=v，刪除邊對中的左側(cè)邊或右側(cè)邊。 B 若左側(cè)邊和右側(cè)邊都從邊對中刪除了，則從AEPL（活化邊對表）中刪去該邊對；若邊對中僅有一條邊被刪去了，則從該邊對所屬的多邊形的ET中找到另一條邊與余下的邊配對，組成新的邊對，加入AEPL（活化邊對表） ； C 計算下一條掃描線與邊對兩邊交點的u坐標(biāo)： ul=ul+Dul；ur=ur+Dur D 計算下一條掃描線與邊對左側(cè)邊交點處的深度值： nl=nl+DnuDul+Dnv（9）將掃描線遞增一個像素，v=v+12022/8/24浙江大學(xué)計算機圖形學(xué)35掃描線Z-buffer算法缺點在每一個被多邊形覆蓋像素處需要計算深度值被多個多邊形覆蓋的像素需

18、要多次計算深度值2022/8/24浙江大學(xué)計算機圖形學(xué)36區(qū)間掃描線算法 與Z-Buffer算法相比，掃描線算法有了很大改進，比如所需的Z-Buffer大大減小，計算深度利用了面連貫性等；缺點：每個像素處都計算深度值，甚至不止一次的計算，運算量仍然很大。改進：在一條掃描線上，每個區(qū)間只計算一次深度，即區(qū)間掃描線算法，又稱掃描線算法。 2022/8/24浙江大學(xué)計算機圖形學(xué)37區(qū)間掃描線算法基本思想：如下圖，多邊形P1、P2的邊界在投影平面上的投影將一條掃描線劃分成若干個區(qū)間0,u1u1,u2u2,u3u3,u4,u4,umax,覆蓋每個區(qū)間的有0個、1個或多個多邊形，但僅有一個可見。在區(qū)間上任

19、取一個像素，計算該像素處各多邊形（投影包含了該像素的多邊形）的深度值，深度值最大者即為可見多邊形，用它的顏色顯示整個區(qū)間。2022/8/24浙江大學(xué)計算機圖形學(xué)38區(qū)間掃描線算法注意：該算法要求多邊形不能相互貫穿，否則在同一區(qū)間上，多邊形深度值的次序會發(fā)生變化。如圖：在區(qū)間u1,u2上，多邊形P1的深度值大，在區(qū)間u3,u4上，多邊形P2的深度值大，而在區(qū)間u2,u3上，兩個多邊形的深度值次序發(fā)生交替。2022/8/24浙江大學(xué)計算機圖形學(xué)39區(qū)間掃描線算法數(shù)據(jù)結(jié)構(gòu)多邊形分類表活化多邊形表邊的分類表活化邊表類似于掃描線Z-Buffer算法中的數(shù)據(jù)結(jié)構(gòu)2022/8/24浙江大學(xué)計算機圖形學(xué)40區(qū)

20、間掃描線算法-算法描述for (繪圖窗口內(nèi)的每一條掃描線） 求投影與當(dāng)前掃描線相交的所有多邊形 求上述多邊形中投影與當(dāng)前掃描線相交的所 有邊，將它們記錄在活化邊表AEL中 求AEL中每條邊的投影與掃描線的交點； 按交點的u坐標(biāo)將AEL中各邊從左到右排序， 兩兩配對組成一個區(qū)間； for （AEL中每個區(qū)間） 求覆蓋該區(qū)間的所有多邊形，將它們記入活化多邊形表APL中； 在區(qū)間上任取一點，計算APL中各多邊形在該點的深度值，記深度最大者為P； 用多邊形P的顏色填充該區(qū)間 2022/8/24浙江大學(xué)計算機圖形學(xué)41區(qū)間掃描線算法相比較掃描線Z-Buffer算法而言，區(qū)間掃描線算法做了如下改進： 一、在一條掃描線上，以區(qū)間為單位確定多邊形的可見性 二、不再需要Z-Buffer2022/8/24浙江大學(xué)計算機圖形學(xué)42光線投射算法算法思想：將通過繪圖窗口內(nèi)每一個像素的投影線與場景中的所有多邊形求交。如果有交點，用深度值最大的交點（最近的）所屬的多邊形的顏色顯示相應(yīng)的像素；如果沒有交點，說明沒有多邊形的投影覆蓋此像素，用背景色顯示即可。2022/8/24浙江大學(xué)計