CG10-隱藏面的消除

第10章隱藏面的消除

（Hidden-SurfaceRemoval)計(jì)算機(jī)科學(xué)系2014第2頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第3頁(yè)第10章隱藏面的消除10.1基本概念問(wèn)題投影變換失去了深度信息，往往導(dǎo)致圖形的二義性及失去遮擋關(guān)系要消除二義性和保持遮擋關(guān)系，就必須在繪制時(shí)消除被遮擋的不可見(jiàn)的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，簡(jiǎn)稱為消隱經(jīng)過(guò)消隱得到的投影圖稱為物體的真實(shí)圖形長(zhǎng)方體線框投影圖的二義性失去遮擋關(guān)系第4頁(yè)第10章隱藏面的消除10.1基本概念消隱的對(duì)象三維物體三維體的表示主要采用邊界（多邊形）表示消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān)線框圖消隱圖真實(shí)感圖形第5頁(yè)第10章隱藏面的消除10.1基本概念消隱分類消除隱藏面：確定可見(jiàn)面（消除不可見(jiàn)面）——表面表示物體（本章討論）消除隱藏線：消除不可見(jiàn)線——線框表示物體長(zhǎng)方體線框投影圖的二義性失去遮擋關(guān)系第6頁(yè)第10章隱藏面的消除10.1基本概念面消隱算法分類投影窗口內(nèi)的像素為處理單元?！_定最近點(diǎn)

for(窗口內(nèi)的每一個(gè)像素) {

確定距視點(diǎn)最近的物體，以該物體表面的顏色來(lái)顯示像素

}圖像空間－image-space第7頁(yè)第10章隱藏面的消除10.1基本概念面消隱算法分類（續(xù)）場(chǎng)景中的物體為處理單元。——物體上的面是否最近for(場(chǎng)景中的每一個(gè)物體){

將其與場(chǎng)景中的其它物體比較，確定其表面的可見(jiàn)部分；顯示該物體表面的可見(jiàn)部分；}場(chǎng)景空間－object-space第8頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第9頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法主要技術(shù)利用連貫性相鄰事物的屬性之間有一定的連貫性，其屬性值通常是平緩過(guò)渡的，如顏色值、空間位置關(guān)系等包括：物體連貫性面的連貫性區(qū)域連貫性掃描線連貫性深度連貫性第10頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法主要技術(shù)（1）利用連貫性物體連貫性：如果物體A與物體B是完全相互分離的，則在消隱時(shí)，只需比較A、B兩物體之間的遮擋關(guān)系，無(wú)須對(duì)它們的表面多邊形逐一進(jìn)行測(cè)試。例如，若A距視點(diǎn)較B遠(yuǎn)，則在測(cè)試B上的表面的可見(jiàn)性時(shí)，無(wú)須考慮A的表面面的連貫性：一張面內(nèi)的各種屬性值一般都是緩慢變化的，允許采用增量形式對(duì)其進(jìn)行計(jì)算第11頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法主要技術(shù)（1）利用連貫性區(qū)域連貫性：區(qū)域指屏幕上一組相鄰的像素，它們通常為同一個(gè)可見(jiàn)面所占據(jù)，可見(jiàn)性相同。區(qū)域連貫性表現(xiàn)在一條掃描線上即為掃描線上的每個(gè)區(qū)間內(nèi)只有一個(gè)面可見(jiàn)掃描線的連貫性：相鄰兩條掃描線上，可見(jiàn)面的分布情況相似深度連貫性：同一表面上的相鄰部分深度是相近的，而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同第12頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（2）透視投影轉(zhuǎn)換為平行投影消隱在投影前完成物體間的遮擋關(guān)系與投影中心相關(guān)物體間的遮擋關(guān)系與投影方式相關(guān)第13頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（3）包圍盒技術(shù)定義：一個(gè)形體的包圍盒指的是包圍它的簡(jiǎn)單形體兩個(gè)條件包圍盒充分緊密包圍著形體對(duì)其的測(cè)試比較簡(jiǎn)單主要包圍盒長(zhǎng)方體正方體球第14頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法應(yīng)用—避免盲目求交例如：兩個(gè)空間多邊形A、B在投影平面上的投影分別為A’，B’

，因?yàn)锳’

、B’的矩形包圍盒不相交，則A’、B’不相交，無(wú)須進(jìn)行遮擋測(cè)試。右下圖(a)包圍盒相交，投影也相交；(b)包圍盒相交，投影不相交第15頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（4）背面剔除外法向：規(guī)定每個(gè)多邊形的外法向都是指向物體外部的前向面：若多邊形的外法向與投影方向（觀察方向）的夾角為鈍角，稱為前向面后向面：若多邊形的外法向與投影方向（觀察方向）的夾角為銳角，稱為后向面（背面）投影方向夾角為180－u第16頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（4）背面剔除（續(xù)）剔除依據(jù)：背面總是被前向面所遮擋，從而不可見(jiàn)前向面后向面JEAF、HCBG、JIHGF為后向面CGVABDEFHIJNVnVn第17頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（5）空間分割技術(shù)依據(jù)：場(chǎng)景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對(duì)于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測(cè)試原因：物體在場(chǎng)景中分散，有些物體的投影相距甚遠(yuǎn)，不會(huì)存在遮擋關(guān)系方法：將投影平面上的窗口分成若干小區(qū)域；為每個(gè)小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個(gè)物體可見(jiàn)時(shí)，只要對(duì)該區(qū)域的相關(guān)物體表中的物體進(jìn)行比較第18頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（6）物體的分層表示表示形式：模型變換中的樹(shù)形表示方式原理：減少場(chǎng)景中物體的個(gè)數(shù)，從而降低算法復(fù)雜度第19頁(yè)第10章隱藏面的消除10.2提高消隱算法效率的常用方法（6）物體的分層表示（續(xù)）方法：將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的包圍盒，當(dāng)兩個(gè)父節(jié)點(diǎn)之間不存在遮擋關(guān)系時(shí)，就沒(méi)有必要對(duì)兩者的子節(jié)點(diǎn)做進(jìn)一步測(cè)試。父節(jié)點(diǎn)之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測(cè)試第20頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第21頁(yè)第10章隱藏面的消除10.3畫(huà)家算法－Painter’sAlgorithm背景畫(huà)家的作畫(huà)順序暗示出所畫(huà)物體之間的相互遮擋關(guān)系第22頁(yè)第10章隱藏面的消除10.3畫(huà)家算法－Painter’sAlgorithm算法基本思想：1）先把屏幕置成背景色2）將場(chǎng)景中的物體按其距觀察點(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è)繪制物體。關(guān)鍵如何對(duì)場(chǎng)景中的物體按深度（遠(yuǎn)近）排序，建立深度優(yōu)先級(jí)表？第23頁(yè)第10章隱藏面的消除10.3畫(huà)家算法多邊形的排序算法*1）將場(chǎng)景中所有多邊形存入一個(gè)線性表，記為L(zhǎng)；2）如果L中僅有一個(gè)多邊形，算法結(jié)束；否則根據(jù)每個(gè)多邊形的Zmin

對(duì)它們預(yù)排序。不妨假定多邊形P落在L的表首，即Zmin(P)為最小。再記Q為L(zhǎng)–{P}(表中其余多邊形）中任意一個(gè)；3）判別P,Q之間的關(guān)系，有如下二種： （1）對(duì)所有的Q，有Zmax(P)<Zmin(Q),

則多邊形P的確距觀察點(diǎn)最遠(yuǎn)，它不可能遮擋別的多邊形。令L=L–{P},

返回第二步;

（2）存在某一個(gè)多邊形Q，使Zmax(P)>Zmin(Q)，需進(jìn)一步判別：第24頁(yè)第10章隱藏面的消除10.3畫(huà)家算法（A）若P,Q的投影P’,Q’的包圍盒不相交(圖a)，則P,Q在表中的次序不重要，令L=L–{P},返回2）;否則進(jìn)行下一步（B）若P的所有頂點(diǎn)位于Q所在平面的不可見(jiàn)的一側(cè)(圖b)，則P,Q關(guān)系正確，令L=L–{P},

返回2）;否則進(jìn)行下一步第25頁(yè)第10章隱藏面的消除10.3畫(huà)家算法（C）若Q的所有頂點(diǎn)位于P所在平面的可見(jiàn)的一側(cè)(圖c)，則P,Q關(guān)系正確，令L=L–{P},

返回2）;否則進(jìn)行下一步（D）對(duì)P,Q投影P’,Q’求交，若P’,Q’不相交(圖d)，則P,Q在表中的次序不重要，令L=L–{P},

返回2）;否則在它們所相交的區(qū)域中任取一點(diǎn)，計(jì)算P,Q在該點(diǎn)的深度值，如果P的深度小，則P,Q關(guān)系正確，令L=L–{P},

返回2）;否則交換P,Q,返回3）第26頁(yè)第10章隱藏面的消除10.3畫(huà)家算法問(wèn)題*不能處理多邊形循環(huán)遮擋和多邊形相互穿透解決方法：分割第27頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第28頁(yè)第10章隱藏面的消除10.4Z緩沖器算法又稱為Z－Buffer算法(深度緩沖depth-buffer)組成：幀緩沖器--保存各像素顏色值

Z緩沖器--保存各像素處物體深度值

Z緩沖器中的單元與幀緩沖器中的單元一一對(duì)應(yīng)第29頁(yè)第10章隱藏面的消除10.4Z緩沖器算法基本思想（1）先將Z緩沖器中個(gè)單元的初始值置為最小值。（2）當(dāng)要改變某個(gè)像素的顏色值時(shí)，首先檢查當(dāng)前多邊形的深度值是否大于該像素原來(lái)的深度值（保存在該像素所對(duì)應(yīng)的Z緩沖器的單元中），

A：如果大于，說(shuō)明當(dāng)前多邊形更靠近觀察點(diǎn)，用它的顏色替換像素原來(lái)的顏色；

B：否則說(shuō)明在當(dāng)前像素處，當(dāng)前多邊形被前面所繪制的多邊形遮擋了，是不可見(jiàn)的，像素的顏色值不改變第30頁(yè)第10章隱藏面的消除10.4Z緩沖器算法算法{ 幀緩存全置為背景色； 深度緩存全置為最小Z值；

for(每一個(gè)多邊形) {

for(該多邊形所覆蓋的每個(gè)像素(x,y)){

計(jì)算該多邊形在該像素的深度值Z(x,y);

if(Z(x,y)大于Z緩存在(x,y)的值) {

把Z(x,y)存入Z緩存中(x,y)處；把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處；

} } }}需要計(jì)算的像素深度值次數(shù)

=多邊形個(gè)數(shù)*多邊形平均占據(jù)的像素個(gè)數(shù)第31頁(yè)第10章隱藏面的消除10.4Z緩沖器算法特點(diǎn)Z緩沖器算法是所有圖像空間算法中最簡(jiǎn)單的一種隱藏面消除算法。在像素級(jí)上以近物取代遠(yuǎn)物，與形體在屏幕上的出現(xiàn)順序無(wú)關(guān)。優(yōu)點(diǎn)

1）簡(jiǎn)單穩(wěn)定，利于硬件實(shí)現(xiàn)

2）不需要整個(gè)場(chǎng)景的幾何數(shù)據(jù)缺點(diǎn)

1）需要一個(gè)額外的Z緩沖器

2）每個(gè)多邊形占據(jù)的每個(gè)像素處都要計(jì)算深度值，計(jì)算量大第32頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第33頁(yè)第10章隱藏面的消除10.5掃描線Z緩沖器算法由來(lái)Z緩沖器算法中所需要的Z緩沖器容量較大，為克服這個(gè)缺點(diǎn)可以將整個(gè)繪圖區(qū)域分割成若干個(gè)小區(qū)域，然后一個(gè)區(qū)域一個(gè)區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個(gè)區(qū)域內(nèi)像素的個(gè)數(shù)如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法第34頁(yè)第10章隱藏面的消除10.5掃描線Z緩沖器算法算法思想在處理當(dāng)前掃描線時(shí)，用一個(gè)一維數(shù)組作為當(dāng)前掃描線的Z-buffer。首先找出與當(dāng)前掃描線相關(guān)的多邊形，以及每個(gè)多邊形中相關(guān)的邊對(duì)。對(duì)每一個(gè)邊對(duì)之間的小區(qū)間上的各像素，計(jì)算深度，并與Z-buffer中的值比較，找出各像素處可見(jiàn)平面。寫(xiě)幀緩存。采用增量算法計(jì)算深度第35頁(yè)第10章隱藏面的消除10.5掃描線Z緩沖器算法算法（p291）*

for(v=0;v<vmax;v++){ for(u=0;u<umax;u++){將幀緩沖器的第(u,v)單元置為背景色；將Z緩沖器的第u單元置為最小值；}for(每個(gè)多邊形）

{

求出多邊形在投影平面上的投影與當(dāng)前掃描線的相交區(qū)間；

for（該區(qū)間內(nèi)的每個(gè)像素(u,v)）

{計(jì)算多邊形在該像素處的深度值d；

if(d>Z緩沖器的第u單元的值）

{置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色；置Z緩沖器的第u單元值為d;}}}//處理下一條掃描線}第36頁(yè)第10章隱藏面的消除10.5掃描線Z緩沖器算法缺點(diǎn)在每一個(gè)被多邊形覆蓋像素處需要計(jì)算深度值被多個(gè)多邊形覆蓋的像素需要多次計(jì)算深度值第37頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第38頁(yè)第10章隱藏面的消除10.6掃描線算法比較與Z-Buffer算法相比，掃描線Z算法有了很大改進(jìn)，比如所需的Z-Buffer大大減小，計(jì)算深度利用了面連貫性等缺點(diǎn)：每個(gè)像素處都計(jì)算深度值，甚至不止一次的計(jì)算，運(yùn)算量仍然很大改進(jìn)：在一條掃描線上，每個(gè)區(qū)間只計(jì)算一次深度，即掃描線算法，又稱區(qū)間掃描線算法第39頁(yè)第10章隱藏面的消除10.6掃描線算法基本思想多邊形P1、P2的邊界在投影平面上的投影將一條掃描線劃分成若干個(gè)區(qū)間[0,u1][u1,u2][u2,u3][u3,u4],[u4,umax]覆蓋每個(gè)區(qū)間的有0個(gè)、1個(gè)或多個(gè)多邊形，但僅有一個(gè)可見(jiàn)。在區(qū)間上任取一個(gè)像素，計(jì)算該像素處各多邊形（投影包含了該像素的多邊形）的深度值，深度值最大者即為可見(jiàn)多邊形，用它的顏色顯示整個(gè)區(qū)間第40頁(yè)第10章隱藏面的消除10.6掃描線算法注意*該算法要求多邊形不能相互貫穿，否則在同一區(qū)間上，多邊形深度值的次序會(huì)發(fā)生變化如圖：在區(qū)間[u1,u2]上，多邊形P1的深度值大，在區(qū)間[u3,u4]上，多邊形P2的深度值大，而在區(qū)間[u2,u3]上，兩個(gè)多邊形的深度值次序發(fā)生交替第41頁(yè)第10章隱藏面的消除10.6掃描線算法算法*

for(繪圖窗口內(nèi)的每一條掃描線）

{

求投影與當(dāng)前掃描線相交的所有多邊形；求上述多邊形中投影與當(dāng)前掃描線相交的所有邊，將它們記錄在活性邊表AEL中；求AEL中每條邊的投影與掃描線的交點(diǎn)；按交點(diǎn)的u坐標(biāo)將AEL中各邊從左到右排序，兩兩配對(duì)組成一個(gè)區(qū)間；

for（AEL中每個(gè)區(qū)間）

{

求覆蓋該區(qū)間的所有多邊形，將它們記入活化多邊形表APL中；在區(qū)間上任取一點(diǎn)，計(jì)算APL中各多邊形在該點(diǎn)的深度值，記深度最大者為P；用多邊形P的顏色填充該區(qū)間；

}}第42頁(yè)第10章隱藏面的消除10.6掃描線算法數(shù)據(jù)結(jié)構(gòu)（類似于掃描線Z-Buffer算法中的數(shù)據(jù)結(jié)構(gòu)）*多邊形分類表PT活性多邊形表APL邊的分類表ET活性邊表AEPL改進(jìn)*在一條掃描線上，以區(qū)間為單位確定多邊形的可見(jiàn)性不再需要Z-Buffer第43頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第44頁(yè)第10章隱藏面的消除10.7光線投射算法基本思想將通過(guò)繪圖窗口內(nèi)每一個(gè)像素的投影線與場(chǎng)景中的所有多邊形求交。如果有交點(diǎn)，用深度值最大的交點(diǎn)（最近的）所屬的多邊形的顏色顯示相應(yīng)的像素；如果沒(méi)有交點(diǎn)，說(shuō)明沒(méi)有多邊形的投影覆蓋此像素，用背景色顯示第45頁(yè)第10章隱藏面的消除10.7光線投射算法算法

for(v=0;v<vmax;v++) for(u=0;u<umax;u++) {

形成通過(guò)像素(u,v)的投影線；

for(場(chǎng)景中每一個(gè)多邊形）

{

將投影線與多邊形求交；

if(有交點(diǎn)） 以最近交點(diǎn)所屬多邊形的顏色顯示像素(u,v) else

以背景色顯示像素(u,v)；

} }第46頁(yè)第10章隱藏面的消除第10章隱藏面的消除基本概念提高消隱算法效率的常用方法畫(huà)家算法Z緩沖器算法掃描線Z緩沖器算法掃描線算法光線投射算法OpenGL相關(guān)函數(shù)第47頁(yè)第10章隱藏面的消除10.8OpenGL相關(guān)函數(shù)多邊形剔除函數(shù)－消除后向面（背面）激活：glEnable（GL_CULL_FACE）無(wú)效：glDisable（GL_CULL_FACE）剔除背面：glCullFace（GL_BACK）intmain(intargc,char**argv){glutInit(&argc,argv);glutInitDisplayMode(GLUT_DOUBLE|GLUT_RGBglutInitWindowSize(300,300);glutCreateWindow("cube");glutDisplay