第10章隱藏面的消除

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

for(窗口內的每一個像素) {

確定距視點最近的物體，以該物體表面的顏色來顯示像素

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

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

，因為A’

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

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

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

返回第二步;

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

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

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

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

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

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

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

A：如果大于，說明當前多邊形更靠近觀察點，用它的顏色替換像素原來的顏色；

B：否則說明在當前像素處，當前多邊形被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變第30頁第10章隱藏面的消除10.4Z緩沖器算法算法{ 幀緩存全置為背景色； 深度緩存全置為最小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)處；

} } }}需要計算的像素深度值次數

=多邊形個數*多邊形平均占據的像素個數第31頁第10章隱藏面的消除10.4Z緩沖器算法特點Z緩沖器算法是所有圖像空間算法中最簡單的一種隱藏面消除算法。在像素級上以近物取代遠物，與形體在屏幕上的出現順序無關。優點

1）簡單穩定，利于硬件實現

2）不需要整個場景的幾何數據缺點

1）需要一個額外的Z緩沖器

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

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

{

求出多邊形在投影平面上的投影與當前掃描線的相交區間；

for（該區間內的每個像素(u,v)）

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

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

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

for(繪圖窗口內的每一條掃描線）

{

求投影與當前掃描線相交的所有多邊形；求上述多邊形中投影與當前掃描線相交的所有邊，將它們記錄在活性邊表AEL中；求AEL中每條邊的投影與掃描線的交點；按交點的u坐標將AEL中各邊從左到右排序，兩兩配對組成一個區間；

for（AEL中每個區間）

{

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

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

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

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

for(場景中每一個多邊形）

{

將投影線與多邊形求交；

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

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

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