計(jì)算機(jī)圖形學(xué) 隱面算法課件

消除隱藏面姓名：XX專業(yè)：XXXX導(dǎo)師：XX教授學(xué)號(hào)：XXXXXXXXX消除隱藏面隱面算法用于消除物體上不可見的表面主要針對(duì)表面模型，不僅要求畫出物體的各個(gè)可見棱邊，而且還要求填充各個(gè)表面點(diǎn)取樣算法畫家算法Z緩沖區(qū)算法掃描線算法區(qū)域采樣算法在繪制物體真實(shí)圖形時(shí)，總是在投影面取一組離散點(diǎn)，在各離散點(diǎn)解決消隱問題，以確定顏色、亮度，用于顯示屏幕上的像素。消除隱藏面

畫家算法畫家算法基本思想：

畫家的作畫時(shí)，先涂背景色，然后由遠(yuǎn)及近的將景物畫上，順序暗示出所畫物體之間的相互遮擋關(guān)系。所以稱為畫家算法。因此，畫家算法又被稱為深度排序算法或表優(yōu)先級(jí)算法?；驹恚?）先把屏幕置成背景色；2）將場(chǎng)景中的物體的各個(gè)面按其距觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點(diǎn)遠(yuǎn)的優(yōu)先級(jí)低，放在表頭；距觀察點(diǎn)近的優(yōu)先級(jí)高，放在表尾）該表稱為深度優(yōu)先級(jí)表。3）然后按照從遠(yuǎn)到近（從表頭到表尾）的順序逐個(gè)繪制物體表面。消除隱藏面

畫家算法深度優(yōu)先級(jí)表的建立一、多邊形優(yōu)先級(jí)的考慮首先對(duì)一個(gè)簡(jiǎn)單的畫面，可以直接建立一個(gè)確定的深度優(yōu)先表如圖（a）所示。深度方向上無重疊。當(dāng)畫面略微復(fù)雜一點(diǎn)，無法按簡(jiǎn)單的Z向排序建立確定的深度優(yōu)先表，以確定每一個(gè)多邊形的優(yōu)先級(jí)，如圖（b）所示。深度方向上有重疊QXZPRQXZP（a）（b）R消除隱藏面

畫家算法深度優(yōu)先級(jí)表的建立二、投影重疊判斷：測(cè)試按照難度遞增順序排列：yyy包圍盒定義：一個(gè)形體的包圍盒指的是包圍它的簡(jiǎn)單形體。一個(gè)好的包圍盒要具有兩個(gè)條件：包圍和充分緊密包圍著形體；對(duì)其的測(cè)試比較簡(jiǎn)單。

1.P和Q在oxy平面上投影的包圍盒在x方向上不相交，圖a；2.P和Q在oxy平面上投影的包圍盒在y方向上不相交,圖b；3.P在Q之后。P的各頂點(diǎn)均在Q的遠(yuǎn)離視點(diǎn)的一側(cè),圖d；4.Q在P之前。Q的各頂點(diǎn)均在P的靠近視點(diǎn)的一側(cè),圖e；5.P和Q在觀察平面oxy上的投影不相交,圖c；上面5項(xiàng)只要有一項(xiàng)成立，P就不遮擋Q，不需要重新排序消除隱藏面

畫家算法深度優(yōu)先級(jí)表的建立對(duì)于某一重疊表面，上述五項(xiàng)測(cè)試均不成立，則需在有序表中調(diào)換兩個(gè)面的位置。S,S,S

S,S,SSSSzS,S

S,S有重疊SS調(diào)換兩個(gè)面的位置后，需要對(duì)調(diào)換過順序的表面重復(fù)上述5項(xiàng)測(cè)試……消除隱藏面

畫家算法深度優(yōu)先級(jí)表的建立解決方法是沿多邊形所在平面間的交線循環(huán)分割這些多邊形。無法直接建立正確的深度優(yōu)先表消除隱藏面

畫家算法排序計(jì)算量大；多邊形相交或循環(huán)重疊時(shí)，必須分割多邊形。畫家算法的不足：消除隱藏面

Z緩沖區(qū)算法Z緩沖區(qū)算法基本思想：

投影平面每個(gè)像素所對(duì)應(yīng)的所有面片（平面或曲面）的深度進(jìn)行比較，然后取離視線最近面片的屬性值作為該像素的屬性值。

Z緩沖器算法基本思想消除隱藏面

Z緩沖區(qū)算法實(shí)現(xiàn)方法幀緩存區(qū)深度緩存區(qū)存放每個(gè)像素的深度值。Z緩沖器每個(gè)單元存放對(duì)應(yīng)像素當(dāng)前最近面的深度值存放每個(gè)像素的顏色值。幀緩沖器每個(gè)單元存放對(duì)應(yīng)像素的顏色值屏幕消除隱藏面

Z緩沖區(qū)算法算法描述：for(v=0;v<vmax;v++)for(u=0;u<umax;u++){將幀緩沖器的第(u,v)單元置為背景色；將Z緩沖器的第(u,v)單元置為最小深度值；

}for(每個(gè)多邊形）for(多邊形在投影平面上的投影區(qū)域內(nèi)的每個(gè)像素(u,v)){計(jì)算多邊形在當(dāng)前像素(u,v)處的深度值d； if(d>Z緩沖器的第(u,v)單元的值) {置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第(u,v)單元值為d;}}幀緩沖器各單元均置為背景色，深度緩沖器所有單元均置為最小z值，然后逐個(gè)處理多邊形表中的各面片。計(jì)算各像素點(diǎn)（x，y）所對(duì)應(yīng)的深度值z(mì)（x，y），并將結(jié)果與深度緩沖器中該像素單元所存儲(chǔ)的深度值ZB（x，y）進(jìn)行比較。若z＞ZB（x，y）,則ZB（x，y）=z，同時(shí)將該像素的顏色值I（x，y）寫入幀緩沖器，即IB（x，y）=I（x，y）；否則不變。消除隱藏面

Z緩沖區(qū)算法深度值的計(jì)算若已知多邊形的方程，則可用增量法計(jì)算掃描線每一個(gè)像素的深度。設(shè)平面方程為：

C≠0

則多邊形面上的點(diǎn)（x，y）所對(duì)應(yīng)的深度值為：消除隱藏面

Z緩沖區(qū)算法深度值的計(jì)算

由于所有掃描線上相鄰點(diǎn)間的水平間距為1個(gè)像素單位，掃描線行與行之間的垂直間距也為1。因此可以利用這種連貫性來簡(jiǎn)化計(jì)算過程，如圖所示。

若已計(jì)算出（x，y）點(diǎn)的深度值為zi，沿x方向相鄰連貫點(diǎn)（x+1，y）的深度值z(mì)i+1可由下式計(jì)算：消除隱藏面

Z緩沖區(qū)算法深度值的計(jì)算沿多邊形左邊界遞歸計(jì)算邊界上各點(diǎn)的坐標(biāo)：

m為該邊的斜率，沿該邊的深度也可以遞歸計(jì)算出來，即：如果該邊是一條垂直邊界，則計(jì)算公式簡(jiǎn)化為：消除隱藏面

Z緩沖區(qū)算法深度值的計(jì)算對(duì)于每條掃描線，首先根據(jù)公式計(jì)算出與其相交的多邊形最左邊的交點(diǎn)所對(duì)應(yīng)的深度值，然后，利用圖形連貫性將該掃描線上所有的后續(xù)點(diǎn)計(jì)算出來。所有的多邊形處理完畢，即得消隱后的圖形。

消除隱藏面

Z緩沖區(qū)算法Z緩沖區(qū)算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)1.簡(jiǎn)單穩(wěn)定，利于硬件實(shí)現(xiàn)2.Z緩沖器算法的最大優(yōu)點(diǎn)：Z緩存器算法在像素級(jí)上以近物取代遠(yuǎn)物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的?？梢暂p而易舉地處理隱藏面以及顯示復(fù)雜曲面之間的交線。缺點(diǎn)1.需要一個(gè)額外的Z緩沖器，需更大的存儲(chǔ)空間，例如，當(dāng)像素?cái)?shù)目為500*500時(shí)，就需要250K個(gè)深度值的存儲(chǔ)空間。深度值一般用浮點(diǎn)數(shù)表示，每個(gè)數(shù)占4個(gè)字節(jié)，故共需要1M字節(jié)的額外存儲(chǔ)空間。2.在每個(gè)多邊形占據(jù)的每個(gè)像素處都要計(jì)算深度值，計(jì)算量大。消除隱藏面

掃描線算法掃描線算法

基本思想：按掃描行的順序處理一幀畫面，在由視點(diǎn)和掃描線所決定的掃描平面上解決消隱問題。

基本步驟：把物體各面投影到屏幕上計(jì)算掃描線與物體各投影面的相交區(qū)間。當(dāng)兩個(gè)區(qū)間在深度方向上重疊時(shí)，采用深度測(cè)試確定可見部分。典型實(shí)現(xiàn)：掃描線Z緩沖區(qū)算法掃描線間隔連貫性算法消除隱藏面

掃描線算法掃描線Z緩沖器每個(gè)單元存放對(duì)應(yīng)像素當(dāng)前最近面的深度值（每一個(gè)掃描線用一個(gè)緩沖器）掃描線Z緩沖區(qū)算法消除隱藏面

掃描線算法3,2,107,2,107,4,103,4,101234z=103,5,08,4,208,0,20123Z=(4x-12)0410101010101216101010101012162016202020……消除隱藏面

區(qū)域采樣算法區(qū)域采樣算法

區(qū)域采樣算法是利用圖形的區(qū)域連貫性，在連續(xù)的區(qū)域上確定可見面及其顏色、亮度。基本思想：

把物體投影到全屏幕窗口上，然后遞歸地分割窗口，直到窗口內(nèi)目標(biāo)足夠簡(jiǎn)單，可以直接顯示為止?；静襟E：首先將場(chǎng)景中的多邊形投影到繪圖窗口內(nèi)，判斷窗口是否足夠簡(jiǎn)單，若是，則算法結(jié)束；否則將窗口進(jìn)一步分為四塊。對(duì)此四個(gè)小窗口重復(fù)上述過程，直到窗口僅為一個(gè)像素大小。此時(shí)可能有多個(gè)多邊形覆蓋了該像素，計(jì)算它們的深度值，以最近的顏色顯示該像素即可。消除隱藏面

區(qū)域采樣算法如何判斷窗口是否足夠簡(jiǎn)單

存在下列情況之一即可稱為窗口足夠簡(jiǎn)單：

1）窗口為空，即多邊形與窗口的關(guān)系是分離的，圖a；

2）窗口內(nèi)僅含一個(gè)多邊形，即有一個(gè)多邊形與窗口的關(guān)系是包含或相交。此時(shí)先對(duì)多邊形投影進(jìn)行裁剪，再對(duì)裁剪結(jié)果進(jìn)行填充，圖b、c。【判別方法：借助剪裁算法來解決，這里不必求出交點(diǎn)和進(jìn)行裁剪，只要判斷出多邊形含于窗口內(nèi)，或多邊形某邊與窗口某邊有相交即可。】

3）有一個(gè)多邊形的投影包圍了窗口，并且它是最靠近觀察點(diǎn)的，以該多邊形顏色填充窗口，圖d。消除隱藏面

區(qū)域采樣算法

如何判斷包圍和分離的關(guān)系？轉(zhuǎn)角累計(jì)檢查法:按順時(shí)針方向或逆時(shí)針方向繞多邊形依次累加多邊形各邊起點(diǎn)與終點(diǎn)對(duì)窗口內(nèi)任意一點(diǎn)所張的夾角。按累計(jì)角度之和可以判定：若角度之和等于0，則表示多邊形與窗口分離；若角度之和等于±360o*n，則表示多邊形包圍窗口(n次)。多邊形窗口窗口多邊形α消除隱藏面

區(qū)域采樣算法

如何判斷包圍和分離的關(guān)系？區(qū)域檢查法:區(qū)域編碼多邊形頂點(diǎn)編碼多邊形邊的編碼多邊形的編碼區(qū)域編碼窗口四條邊所在直線將屏幕劃分成9個(gè)區(qū)域，對(duì)窗口以外的8個(gè)區(qū)域按逆時(shí)針（或順時(shí)針）進(jìn)行編碼，編碼為0~7。

多邊形頂點(diǎn)編碼多邊形v0v1…vn的頂點(diǎn)vi的投影落在哪個(gè)區(qū)域，那個(gè)區(qū)域的編碼便作為該頂點(diǎn)的編碼，記為Vi。消除隱藏面

區(qū)域采樣算法

如何判斷包圍和分離的關(guān)系？區(qū)域檢查法:區(qū)域編碼多邊形頂點(diǎn)編碼多邊形邊的編碼多邊形的編碼多邊形邊的編碼多邊形的邊vivi+1的編碼定義為Vi(i+1)=vi+1-vi，令Vn(n+1)=Vn0i=0,1…n；當(dāng)Vi(i+1)>4時(shí)，取Vi(i+1)=Vi(i+1)-8；當(dāng)Vi(i+1)<-4時(shí)，取Vi(i+1)=Vi(i+1)+8；當(dāng)Vi=±4時(shí)，取該邊與窗口邊的延長(zhǎng)線的交點(diǎn)將該邊分為兩段，對(duì)兩段分別按上面的規(guī)則編碼，再令Vi(i+1)等于兩者之和。多邊形的編碼定義多邊形的編碼為其邊的編碼之和，則消除隱藏面

區(qū)域采樣算法

例：STEP1：區(qū)域編碼STEP2：多邊形頂點(diǎn)編碼

v0=1,v1=3,v2=7,STEP3：多邊形邊的編碼V01=3-1=2,V12=7-3=4,V20=1-7=-6(＜-4),故V20=-6+8=2。STEP4：多邊形的編碼V01+V12+V20=2+（-4）+2=0。取v1v2與窗口上邊所在直線的交點(diǎn)v’將其分為兩段，兩段的編碼分別為-2，6（＞4，故為6-8=-2），

從而V12=-2+（-2）=-4。因此，多邊形與窗口分離。消除隱藏面

區(qū)域采樣算法

STEP2：多邊形頂點(diǎn)編碼

V0=5,V1=7,V2=3,STEP3：多邊形邊的編碼V01=7-5=2,V12=3-7=-4,V20=5-3=2.STEP4：多邊形的編碼V01+V12+V20=2+4+2=8。取v1v2與窗口上邊所在直線的交點(diǎn)v’將其分為兩段，兩段的編碼分別為-6(＜-4，故為-6+8=2)，2從而V12=2+2=4。因此，多邊形與窗口關(guān)系是包圍。例：STEP1：區(qū)域編碼消除隱藏面

區(qū)域采樣算法

顏色顯示在判斷結(jié)束，確?！按翱谥心繕?biāo)簡(jiǎn)單”以后，應(yīng)判斷出以下三種情況：①窗口為空，不含任何物體，這是顯示為背景色；②窗口內(nèi)含有一個(gè)多邊形（內(nèi)含或相交），這時(shí)用窗口對(duì)多邊形剪裁，顯示多邊形在窗口中的部分；③有一個(gè)多邊形包圍窗口，并且比其他多邊形離視點(diǎn)近，這時(shí)，用該多邊形的顏色顯示窗口。紋理紋理

物體表面的細(xì)節(jié)分為兩類一類是由物體表面顏色色彩、明