計算機圖形學 隱面算法課件

1、姓名：XX專業(yè)：XXXX導師：XX 教授學號：XXXXXXXXX隱面算法用于消除物體上不可見的表面主要針對表面模型，不僅要求畫出物體的各個可見棱邊，而且還要求填充各個表面點取樣算法點取樣算法畫家算法Z緩沖區(qū)算法掃描線算法區(qū)域采樣算法在繪制物體真實圖形時，總是在投影面取一組離散點，在各離散點解決消隱問題，以確定顏色、亮度，用于顯示屏幕上的像素。畫家算法畫家算法基本思想：基本思想： 畫家的作畫時，先涂背景色，然后由遠及近的將景物畫上，順序暗示出所畫物體之間的相互遮擋關(guān)系。所以稱為畫家算法。因此，畫家算法又被稱為深度排序算法或表優(yōu)先級算法。基本原理：基本原理：1）先把屏幕置成背景色；2）將場景中的物

2、體的各個面按其距觀察點的遠近進行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點遠的優(yōu)先級低，放在表頭；距觀察點近的優(yōu)先級高，放在表尾 ）該表稱為深度優(yōu)先級表。3）然后按照從遠到近（從表頭到表尾）的順序逐個繪制物體表面。深度優(yōu)先級表的建立一、多邊形優(yōu)先級的考慮 首先對一個簡單的畫面，可以直接建立一個確定的深度優(yōu)先表如圖（a）所示。深度方向上無重疊。 當畫面略微復雜一點，無法按簡單的Z向排序建立確定的深度優(yōu)先表，以確定每一個多邊形的優(yōu)先級，如圖（b）所示 。深度方向上有重疊Q QX XZ ZP PR RQ QX XZ ZP P（a a）（b b）R R深度優(yōu)先級表的建立二、投影重疊判斷：測試按

3、照難度遞增順序排列：y yy yy y包圍盒定義：一個形體的包圍盒指的是包圍它的簡單形體。一個好的包圍盒要具有兩個條件：包圍和充分緊密包圍著形體；對其的測試比較簡單。 1. P和Q在oxy平面上投影的包圍盒在x方向上不相交，圖a；2. P和Q在oxy平面上投影的包圍盒在y方向上不相交,圖b；3. P在Q之后。P的各頂點均在Q的遠離視點的一側(cè),圖d；4.Q在P之前。Q的各頂點均在P的靠近視點的一側(cè),圖e；5. P和Q在觀察平面oxy上的投影不相交,圖c；上面5項只要有一項成立，P就不遮擋Q，不需要重新排序深度優(yōu)先級表的建立對于某一重疊表面，上述五項測試均不成立，則需在有序表中調(diào)換兩個面的位置。S

4、, SS, S , S, S S S , S, S , , S S S SS S S S z zS, SS, S S S , S , S 有重疊S S S S調(diào)換兩個面的位置后，需要對調(diào)換過順序的表面重復上述5項測試深度優(yōu)先級表的建立解決方法是沿多邊形所在平面間的交線循環(huán)分割這些多邊形。無法直接建立正確的深度優(yōu)先表 排序計算量大； 多邊形相交或循環(huán)重疊時，必須分割多邊形。畫家算法的不足：畫家算法的不足：Z Z緩沖區(qū)算法緩沖區(qū)算法基本思想基本思想： 投影平面每個像素所對應(yīng)的所有面片（平面或曲面）的深度進行比較，然后取離視線最近面片的屬性值作為該像素的屬性值。 Z緩沖器算法基本思想實現(xiàn)方法幀緩存區(qū)

5、 深度緩存區(qū)存放每個像素的深度值。Z緩沖器每個單元存放對應(yīng)像素當前最近面的深度值存放每個像素的顏色值。幀緩沖器每個單元存放對應(yīng)像素的顏色值屏幕算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u Z緩沖器的第(u,v)單元的值) 置幀緩沖器的第(u,v)單元值為當前多邊形顏色； 置Z緩沖器的第(u,v)單元值為d; 幀緩沖器各單元均置為背景色，深度緩沖器所有單元均置為最小z值，然后逐個處理多邊形表中的各面片。計算各像素點（x，y）所對應(yīng)的深度值z（x，y），并將結(jié)果與深度緩沖器中該像素單元所存儲的深度值ZB（x，y）進行比較。若zZB（x，y）,則ZB（x，y

6、）= z，同時將該像素的顏色值I（x，y）寫入幀緩沖器，即IB（x，y）= I（x，y）；否則不變。深度值的計算若已知多邊形的方程，則可用增量法計算掃描線每一個像素的深度。設(shè)平面方程為： 0DCzByAxCDByAxz)(C0C0 則多邊形面上的點（x，y）所對應(yīng)的深度值為：深度值的計算 CAzCDByxAziii)1(1由于所有掃描線上相鄰點間的水平間距為1個像素單位，掃描線行與行之間的垂直間距也為1。因此可以利用這種連貫性來簡化計算過程，如圖所示。 若已計算出（x，y）點的深度值為zi，沿x方向相鄰連貫點（x+1，y）的深度值zi+1可由下式計算：深度值的計算沿多邊形左邊界遞歸計算邊界上各

7、點的坐標： mxxii11CBmAzCDyBmxAziiii)1()1(1CBzzii 1m為該邊的斜率，沿該邊的深度也可以遞歸計算出來，即：如果該邊是一條垂直邊界，則計算公式簡化為：深度值的計算對于每條掃描線，首先根據(jù)公式計算出與其相交的多邊形最左邊的交點所對應(yīng)的深度值，然后，利用圖形連貫性將該掃描線上所有的后續(xù)點計算出來。所有的多邊形處理完畢，即得消隱后的圖形。 Z Z緩沖區(qū)算法的優(yōu)缺點：緩沖區(qū)算法的優(yōu)缺點：優(yōu)點1. 簡單穩(wěn)定，利于硬件實現(xiàn)2.Z緩沖器算法的最大優(yōu)點 ：Z緩存器算法在像素級上以近物取代遠物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的。可以輕而易舉地處理隱藏面以及顯示復雜曲面之間的交

8、線。缺點1.需要一個額外的Z 緩沖器，需更大的存儲空間，例如，當像素數(shù)目為500*500時，就需要250K個深度值的存儲空間。深度值一般用浮點數(shù)表示，每個數(shù)占4個字節(jié)，故共需要1M字節(jié)的額外存儲空間。2.在每個多邊形占據(jù)的每個像素處都要計算深度值，計算量大。掃描線算法掃描線算法 基本基本思想思想： 按掃描行的順序處理一幀畫面，在由視點和掃描線所決定的掃描平面上解決消隱問題。 基本步驟：基本步驟：把物體各面投影到屏幕上計算掃描線與物體各投影面的相交區(qū)間。當兩個區(qū)間在深度方向上重疊時，采用深度測試確定可見部分。典型實現(xiàn)：典型實現(xiàn)：掃描線Z緩沖區(qū)算法掃描線間隔連貫性算法掃描線掃描線Z Z緩沖緩沖器器

9、每個單元存放每個單元存放對應(yīng)像素對應(yīng)像素當前最近面的深度值當前最近面的深度值（每一個掃描線用一個緩沖器）（每一個掃描線用一個緩沖器）掃描線Z緩沖區(qū)算法3,2,103,2,107,2,107,2,107,4,107,4,103,4,103,4,101 12 23 34 4z=10z=103,5,03,5,08,4,208,4,208,0,208,0,201 12 23 3Z=(4x-12)0 04 41010 1010 1010 1010 10101212 16161010 1010 1010 1010 10101212 1616 20201616 202020202020區(qū)域采樣算法區(qū)域采樣算

10、法 區(qū)域采樣算法區(qū)域采樣算法是利用圖形的區(qū)域連貫性，在連續(xù)的區(qū)域上確定可見面及其顏色、亮度?；净舅枷胨枷耄?把物體投影到全屏幕窗口上，然后遞歸地分割窗口，直到窗口內(nèi)目標足夠簡單，可以直接顯示為止?；静襟E：基本步驟：首先將場景中的多邊形投影到繪圖窗口內(nèi)，判斷窗口是否足夠簡單，若是，則算法結(jié)束；否則將窗口進一步分為四塊。對此四個小窗口重復上述過程，直到窗口僅為一個像素大小。此時可能有多個多邊形覆蓋了該像素，計算它們的深度值，以最近的顏色顯示該像素即可。如何判斷窗口是否足夠簡單如何判斷窗口是否足夠簡單 存在下列情況之一即可稱為窗口足夠簡單：1）窗口為空，即多邊形與窗口的關(guān)系是分離的，圖a；2）

11、窗口內(nèi)僅含一個多邊形，即有一個多邊形與窗口的關(guān)系是包含或相交。此時先對多邊形投影進行裁剪，再對裁剪結(jié)果進行填充，圖b、c。【判別方法： 借助剪裁算法來解決，這里不必求出交點和進行裁剪，只要判斷出多邊形含于窗口內(nèi)，或多邊形某邊與窗口某邊有相交即可?！?）有一個多邊形的投影包圍了窗口，并且它是最靠近觀察點的，以該多邊形顏色填充窗口，圖d。 如何判斷包圍和分離的關(guān)系？如何判斷包圍和分離的關(guān)系？轉(zhuǎn)角累計檢查法轉(zhuǎn)角累計檢查法:按順時針方向或逆時針方向繞多邊形依次累加多邊形各邊起點與終點對窗口內(nèi)任意一點所張的夾角。按累計角度之和可以判定： 若角度之和等于0，則表示多邊形與窗口分離； 若角度之和等于360

12、*n，則表示多邊形包圍窗口(n次)。多邊形多邊形窗口窗口窗口窗口多邊形多邊形 如何判斷包圍和分離的關(guān)系？如何判斷包圍和分離的關(guān)系？區(qū)域檢查法區(qū)域檢查法: : 區(qū)域編碼多邊形頂點編碼多邊形邊的編碼多邊形的編碼區(qū)域編碼窗口四條邊所在直線將屏幕劃分成9個區(qū)域，對窗口以外的8個區(qū)域按逆時針（或順時針）進行編碼，編碼為07。 多邊形頂點編碼多邊形v0v1vn的頂點vi的投影落在哪個區(qū)域，那個區(qū)域的編碼便作為該頂點的編碼，記為Vi。 如何判斷包圍和分離的關(guān)系？如何判斷包圍和分離的關(guān)系？區(qū)域檢查法區(qū)域檢查法: : 區(qū)域編碼多邊形頂點編碼多邊形邊的編碼多邊形的編碼多邊形邊的編碼多邊形的邊vivi+1的編碼定義

13、為Vi(i+1)=vi+1-vi，令Vn(n+1)=Vn0 i=0,1n；當Vi(i+1) 4時，取Vi(i+1) = Vi(i+1) -8；當Vi(i+1) -4時，取Vi(i+1) = Vi(i+1) +8；當Vi =4時，取該邊與窗口邊的延長線的交點將該邊分為兩段，對兩段分別按上面的規(guī)則編碼，再令Vi(i+1)等于兩者之和。多邊形的編碼定義多邊形的編碼為其邊的編碼之和 ，則8000niinii當多邊形包圍窗口當窗口與多邊形分離 例：例：STEP1STEP1：區(qū)域編碼STEP2STEP2：多邊形頂點編碼 v0=1,v1=3,v2=7,STEP3STEP3：多邊形邊的編碼 V01=3-1=2

14、, V12=7-3=4, V20=1-7=-6(-4),故V20=-6+8=2。STEP4STEP4：多邊形的編碼 V01+V12+V20=2+（-4）+2=0。 取v1v2與窗口上邊所在直線的交點v將其分為兩段，兩段的編碼分別為-2，6（4，故為6-8=-2）， 從而V12=-2+（-2）=-4。因此，多邊形與窗口分離。 STEP2STEP2：多邊形頂點編碼 V0=5,V1=7,V2=3,STEP3STEP3：多邊形邊的編碼 V01=7-5=2, V12=3-7=-4, V20=5-3=2.STEP4STEP4：多邊形的編碼 V01+V12+V20=2+4+2=8。 取v1v2與窗口上邊所在

15、直線的交點v將其分為兩段，兩段的編碼分別為-6(-4，故為-6+8=2)，2 從而V12=2+2=4。因此，多邊形與窗口關(guān)系是包圍。例：例：STEP1STEP1：區(qū)域編碼 顏色顯示顏色顯示在判斷結(jié)束，確?！按翱谥心繕撕唵巍币院?，應(yīng)判斷出以下三種情況：窗口為空，不含任何物體，這是顯示為背景色；窗口內(nèi)含有一個多邊形（內(nèi)含或相交），這時用窗口對多邊形剪裁，顯示多邊形在窗口中的部分；有一個多邊形包圍窗口，并且比其他多邊形離視點近，這時，用該多邊形的顏色顯示窗口。 物體表面的細節(jié)分為兩類一類是由物體表面顏色色彩、明暗變化體現(xiàn)出來的細節(jié)(取決于物體表面的)；一類是由物體表面不規(guī)則的細小凹凸造成的細節(jié)(取決于物體本身的)。紋理映射分類用來在光滑表面上產(chǎn)生花紋圖案的效果，用來使物體表面產(chǎn)生凹凸不平的效果進行紋理映射的過程主要是建立幾何和紋理圖片之間的幾何對應(yīng)關(guān)系，這種幾何對應(yīng)關(guān)系確立以后，紋理的某一塊對應(yīng)著場景中某個多邊形的某個位置，如果處理不好這種關(guān)系，那么紋理可能會出現(xiàn)在我們與預(yù)料之外的地方，甚至顛倒扭曲，或者紋理映射失敗。紋理映射的三個主要步驟：（1）定義紋理坐標；紋理坐標是紋理本身的像素位置，有了紋理坐標