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

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

2、體的各個(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）所示 。深度方向上有重疊Q QX XZ ZP PR RQ QX XZ ZP P（a a）（b b）R R深度優(yōu)先級(jí)表的建立二、投影重疊判斷：測(cè)試按

3、照難度遞增順序排列：y yy yy y包圍盒定義：一個(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

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

5、 深度緩存區(qū)存放每個(gè)像素的深度值。Z緩沖器每個(gè)單元存放對(duì)應(yīng)像素當(dāng)前最近面的深度值存放每個(gè)像素的顏色值。幀緩沖器每個(gè)單元存放對(duì)應(yīng)像素的顏色值屏幕算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u 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)行比較。若zZB（x，y）,則ZB（x，y

6、）= z，同時(shí)將該像素的顏色值I（x，y）寫入幀緩沖器，即IB（x，y）= I（x，y）；否則不變。深度值的計(jì)算若已知多邊形的方程，則可用增量法計(jì)算掃描線每一個(gè)像素的深度。設(shè)平面方程為： 0DCzByAxCDByAxz)(C0C0 則多邊形面上的點(diǎn)（x，y）所對(duì)應(yīng)的深度值為：深度值的計(jì)算 CAzCDByxAziii)1(1由于所有掃描線上相鄰點(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ì)算：深度值的計(jì)算沿多邊形左邊界遞歸計(jì)算邊界上各

7、點(diǎn)的坐標(biāo)： mxxii11CBmAzCDyBmxAziiii)1()1(1CBzzii 1m為該邊的斜率，沿該邊的深度也可以遞歸計(jì)算出來，即：如果該邊是一條垂直邊界，則計(jì)算公式簡(jiǎn)化為：深度值的計(jì)算對(duì)于每條掃描線，首先根據(jù)公式計(jì)算出與其相交的多邊形最左邊的交點(diǎn)所對(duì)應(yīng)的深度值，然后，利用圖形連貫性將該掃描線上所有的后續(xù)點(diǎn)計(jì)算出來。所有的多邊形處理完畢，即得消隱后的圖形。 Z Z緩沖區(qū)算法的優(yōu)缺點(diǎn)：緩沖區(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ù)雜曲面之間的交

8、線。缺點(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)：典型實(shí)現(xiàn)：掃描線Z緩沖區(qū)算法掃描線間隔連貫性算法掃描線掃描線Z Z緩沖緩沖器器

9、每個(gè)單元存放每個(gè)單元存放對(duì)應(yīng)像素對(duì)應(yīng)像素當(dāng)前最近面的深度值當(dāng)前最近面的深度值（每一個(gè)掃描線用一個(gè)緩沖器）（每一個(gè)掃描線用一個(gè)緩沖器）掃描線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)目標(biāo)足夠簡(jiǎn)單，可以直接顯示為止。基本步驟：基本步驟：首先將場(chǎng)景中的多邊形投影到繪圖窗口內(nèi)，判斷窗口是否足夠簡(jiǎn)單，若是，則算法結(jié)束；否則將窗口進(jìn)一步分為四塊。對(duì)此四個(gè)小窗口重復(fù)上述過程，直到窗口僅為一個(gè)像素大小。此時(shí)可能有多個(gè)多邊形覆蓋了該像素，計(jì)算它們的深度值，以最近的顏色顯示該像素即可。如何判斷窗口是否足夠簡(jiǎn)單如何判斷窗口是否足夠簡(jiǎn)單 存在下列情況之一即可稱為窗口足夠簡(jiǎn)單：1）窗口為空，即多邊形與窗口的關(guān)系是分離的，圖a；2）

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

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

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