第5講 計算機圖形學消隱算法

1、消隱算法消隱算法 用計算機生成三維形體的真實圖形，是計算機圖形學研究用計算機生成三維形體的真實圖形，是計算機圖形學研究的重要內容之一。在使用顯示設備描繪三維圖形時，必須把三的重要內容之一。在使用顯示設備描繪三維圖形時，必須把三維信息作某種投影變換，在二維顯示表面上繪制出來。維信息作某種投影變換，在二維顯示表面上繪制出來。 由于投影變換失去了深度信息，往往導致圖形的二義性：由于投影變換失去了深度信息，往往導致圖形的二義性：要消除二義性，必須在繪制時消隱實際不可見得線和面，要消除二義性，必須在繪制時消隱實際不可見得線和面，即消隱。經過消隱的投影圖稱為物體的真實圖形。即消隱。經過消隱的投影圖稱為物體

2、的真實圖形。一、概述一、概述 消隱不僅與消隱對象有關，還與觀察者消隱不僅與消隱對象有關，還與觀察者的位置有關。如圖所示，由于視點的位的位置有關。如圖所示，由于視點的位置不同，物體的可見部分也不同：置不同，物體的可見部分也不同：消隱與觀察者的位置關系消隱與觀察者的位置關系按消隱的對象分類按消隱的對象分類線消隱（線消隱（Hidden-lineHidden-line）面消隱（面消隱（Hidden-surfaceHidden-surface）按消隱空間分類按消隱空間分類物體空間消隱算法物體空間消隱算法圖像空間消隱算法圖像空間消隱算法p線消隱（線消隱（Hidden-lineHidden-line） 消隱

3、對象是物體上不可見的線，一般用于消隱對象是物體上不可見的線，一般用于線框圖。當用筆式繪圖儀或其它畫線設備繪制線框圖。當用筆式繪圖儀或其它畫線設備繪制圖形時，主要使用這種算法。圖形時，主要使用這種算法。p面消隱面消隱（Hidden-surfaceHidden-surface） 消隱對象是物體上不可見的面，一般用于消隱對象是物體上不可見的面，一般用于填色圖。當用光柵掃描顯示器繪制圖形時，主填色圖。當用光柵掃描顯示器繪制圖形時，主要使用這種算法。要使用這種算法。 早期圖形顯示器是用線條表示圖形，消隱主要是消隱線早期圖形顯示器是用線條表示圖形，消隱主要是消隱線問題。使用光柵顯示器后，物體可用連續(xù)變化的

4、色調來描問題。使用光柵顯示器后，物體可用連續(xù)變化的色調來描述，消隱算法的研究漸漸轉向消隱面的問題。述，消隱算法的研究漸漸轉向消隱面的問題。 p第一種是物空間算法。第一種是物空間算法。它以三維場景中的物體對像作為處理單元的，在所它以三維場景中的物體對像作為處理單元的，在所有的對像之間進行比較，除去完全不可見的的物體有的對像之間進行比較，除去完全不可見的的物體和物體上不可見的部分。常用于線框表示立體的線和物體上不可見的部分。常用于線框表示立體的線隱藏，也用于面隱藏。隱藏，也用于面隱藏。for (for (場景中的每一個物體場景中的每一個物體) ) 將其與場景中的其它物體比較，確定其將其與場景中的其

5、它物體比較，確定其表面的可見部分；顯示該物體表面的可見部分；表面的可見部分；顯示該物體表面的可見部分； 隱藏線（面）的消除的兩種基本算法隱藏線（面）的消除的兩種基本算法特點是：算法可以達到相當高的精度。特點是：算法可以達到相當高的精度。 p第二種是像空間算法。第二種是像空間算法。 它以構成圖形的每一個像素為處理單元的，確定場景它以構成圖形的每一個像素為處理單元的，確定場景中哪些表面的像素相對于觀察點而言是可見的，用該表面中哪些表面的像素相對于觀察點而言是可見的，用該表面的顏色填充該像素。常用于隱藏面。的顏色填充該像素。常用于隱藏面。特點是：算法精度低，只能達到屏幕精度為止，但速度往特點是：算法

6、精度低，只能達到屏幕精度為止，但速度往往更高。往更高。 其算法是對每一個像素其算法是對每一個像素:l在和投影點到像素的連線相交的表面中找到離觀察點最近在和投影點到像素的連線相交的表面中找到離觀察點最近的表面的表面l用該表面上交點處的顏色填充該像素。用該表面上交點處的顏色填充該像素。 for (for (窗口內的每一個像素窗口內的每一個像素) ) 確定距視點最近的物體，以該物體表確定距視點最近的物體，以該物體表 面的顏色來顯示像素面的顏色來顯示像素 算法復雜度算法復雜度 假設場景中有假設場景中有k k個物體個物體，平均每個物體表面，平均每個物體表面由由h h個多邊形個多邊形構成，顯示區(qū)域中有構成

7、，顯示區(qū)域中有m x nm x n個像素個像素，則：則： 第一種算法的復雜度為：第一種算法的復雜度為： O(kh)O(kh)(kh)(kh) 第二種算法的復雜度為：第二種算法的復雜度為：O(mnkh)O(mnkh)9物空間消隱算法物空間消隱算法: : 需對物體表面的需對物體表面的h h個多邊形個多邊形中的每個面與其余中的每個面與其余h-1h-1個面進行比較，精確地求出物體上每個棱邊或個面進行比較，精確地求出物體上每個棱邊或每個面的遮擋關系。算法的計算量正比于每個面的遮擋關系。算法的計算量正比于h h2 2，即算即算法復雜度為：法復雜度為：O(h)O(h)2 2) ) 。 則：則：k k個物體個

8、物體的算法復雜度為：的算法復雜度為：O(kh)O(kh)2 2) ) 。10象空間消隱算法象空間消隱算法： 這類算法對屏幕上的每個象素進行判斷，以決這類算法對屏幕上的每個象素進行判斷，以決定物體上哪個多邊形在該象素定物體上哪個多邊形在該象素 點上是可見的。若屏點上是可見的。若屏幕上有幕上有m mn n個象素個象素點，每個物體表面上有點，每個物體表面上有h h個多邊形個多邊形，則該類消隱算法計算量正比于，則該類消隱算法計算量正比于mnhmnh。 則：則： k k個物體個物體的算法復雜度為：的算法復雜度為： O(mnkh)O(mnkh) 。 各種消隱算法均采用一定形式的幾何排序。通過排各種消隱算法

9、均采用一定形式的幾何排序。通過排序，可搜查出位置上靠近觀察者的幾何元素，確定幾何序，可搜查出位置上靠近觀察者的幾何元素，確定幾何元素之間在位置上的遮擋關系，解決消隱計算的主要問元素之間在位置上的遮擋關系，解決消隱計算的主要問題。各種算法都有各自的排序方法和排序次序。排序次題。各種算法都有各自的排序方法和排序次序。排序次序影響算法的效率。序影響算法的效率。 算法排序算法排序二、二、 消隱基本技術消隱基本技術 為了提高消隱算法的效率，為了提高消隱算法的效率，各種消隱算法各種消隱算法常常采用一些有效的采用一些有效的消隱消隱基本基本算法。算法。利用連貫性利用連貫性將透視投影轉換成平行投影將透視投影轉換

10、成平行投影包圍盒技術包圍盒技術背面剔除背面剔除空間分割技術空間分割技術物體分層表示物體分層表示 物體連貫性物體連貫性面的連貫性面的連貫性 區(qū)域連貫性區(qū)域連貫性 掃描線的連貫性掃描線的連貫性 深度連貫性深度連貫性p 利用連貫性利用連貫性 連貫性是指從一個事物到另一個事物，其連貫性是指從一個事物到另一個事物，其屬性值屬性值( (如顏色值、空間位置如顏色值、空間位置) )通常是平緩過渡通常是平緩過渡的性質。的性質。例如：例如： 棱邊的連貫性棱邊的連貫性是指：是指：棱邊的可見性在它與其他棱邊相交棱邊的可見性在它與其他棱邊相交時才發(fā)生變換時才發(fā)生變換； 面的連貫性面的連貫性是指：是指：如果面的一部分是可

11、見的，則一般情如果面的一部分是可見的，則一般情況下整個面都是可見的況下整個面都是可見的。 物體連貫性 若物體A與物體B是完全分離的，消隱時只需要比較兩物體之間的遮擋關系即可，不需要對它們的表面多邊形逐一進行測試； 面的連貫性一張面內的各種屬性值一般是緩慢變化的，可采用增量的形式對其進行計算； 區(qū)域連貫性一個區(qū)域一般指屏幕上一組相鄰的象素，他們通常為同一個可見面所占據(jù)，可見性相同； 掃描線的連貫性在相鄰兩條掃描線上，可見面的分布情況相似； 深度連貫性同一表面上的相鄰部分深度是相近的，而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同，這樣只需取其上一點計算出深度值，比較該深度值便能得出結果； p 包圍盒技

12、術包圍盒技術 一個形體的包圍盒指的是包圍它的簡單形體。一個形體的包圍盒指的是包圍它的簡單形體。比如，比如，2 2D D的矩形，的矩形，3 3D D的的立方塊、長方體、球等。立方塊、長方體、球等。目的：目的： 避免盲目的求交測試；避免盲目的求交測試； 各物體間的比較等。各物體間的比較等。一個好的包圍盒要具有兩個條件：一個好的包圍盒要具有兩個條件：包圍和充分緊密包圍著形體；包圍和充分緊密包圍著形體；對其的測試比較簡單。對其的測試比較簡單。例：例：矩形包圍盒及長方體包圍矩形包圍盒及長方體包圍盒提高算法效率盒提高算法效率 包圍盒不相交，線段和多邊形也不相交，線段完全可見，無需就線段和多邊形的遮擋關系進

13、行進一步判斷?？赏茝V到面與面的遮擋快速判斷。 例如：兩個空間多邊形A、B在投影平面上的投影分別為A，B ，因為A 、B的矩形包圍盒不相交，則A、B不相交，無須進行遮擋測試。右圖：包圍盒相交，投影也相交；包圍盒相交，投影不相交。AABBp 背面剔除背面剔除 外法向外法向 外法向與投影方向（觀察方向）的夾角判斷：外法向與投影方向（觀察方向）的夾角判斷：前向面與后向面（背面）前向面與后向面（背面）剔除依據(jù)：剔除依據(jù)： 物體表面是封閉的，背面總是被前物體表面是封閉的，背面總是被前向面所遮擋，從而始終是向面所遮擋，從而始終是 不可見的。不可見的。法向向量法向向量N 視線向量視線向量V法向向量法向向量N

14、法向向量法向向量N 90 90V VN N cos 視線視線- -法線夾角法法線夾角法N N 面的法向量面的法向量V V 面上一點指向觀察點的向量面上一點指向觀察點的向量 = = coscos-1-1( )( )0= 0= 時時 可見可見 = = = 00N N . . V V00 2 2p、空間分割技術、空間分割技術依據(jù)：依據(jù)：場景中的物體，它們的投影在投影平面上場景中的物體，它們的投影在投影平面上 是否有相互遮擋的重疊部分？是否有相互遮擋的重疊部分？ 對于根本不存在相互遮擋關系的物體，應對于根本不存在相互遮擋關系的物體，應 避免這種不必要的測試。避免這種不必要的測試。方法：方法：將投影平面

15、上的窗口分成若干小區(qū)域；為將投影平面上的窗口分成若干小區(qū)域；為每個小區(qū)域建立相關物體表，表中物體的投影于每個小區(qū)域建立相關物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷哪個物體該區(qū)域有相交部分；則在小區(qū)域中判斷哪個物體可見時，可見時，只要對本區(qū)域的相關物體表中的物體進只要對本區(qū)域的相關物體表中的物體進行比較即可行比較即可。復雜度比較：復雜度比較： 假定每個小區(qū)域的相關物體表中平均假定每個小區(qū)域的相關物體表中平均有有h h個個物體，場景中有物體，場景中有k k個物體，由于物體在場景中的分個物體，由于物體在場景中的分布是分散的，顯然布是分散的，顯然h h遠小于遠小于k k。 根據(jù)物空間

16、消隱方法所述，其算法復雜根據(jù)物空間消隱方法所述，其算法復雜度為度為O(hO(h2 2),),遠小于遠小于O(kO(k2 2) )。p 物體分層表示物體分層表示表示形式表示形式：模型變換中的樹形表示方式：模型變換中的樹形表示方式原理：原理：減少場景中物體的個數(shù)，降低算法復雜度減少場景中物體的個數(shù)，降低算法復雜度。方法方法： 將父節(jié)點所代表的物體看成子節(jié)點物體的將父節(jié)點所代表的物體看成子節(jié)點物體的包圍盒，當兩個父節(jié)點之間不存在遮擋關系時，包圍盒，當兩個父節(jié)點之間不存在遮擋關系時，就勿對兩者的子節(jié)點做進一步測試。就勿對兩者的子節(jié)點做進一步測試。 父節(jié)點之間的遮擋關系可以用它們之間的包父節(jié)點之間的遮擋

17、關系可以用它們之間的包圍盒進行預測試。圍盒進行預測試。p 將透視投影轉換成平行投影將透視投影轉換成平行投影 消隱與透視關系較密切，體現(xiàn)在消隱與透視關系較密切，體現(xiàn)在： 1 1）消隱必須在投影之前完成；）消隱必須在投影之前完成；因為消隱需要物體三維信息，投影后只有二維信息； 2 2）物體之間的遮擋關系與投影中心（視點）物體之間的遮擋關系與投影中心（視點） 的選取有關；的選取有關； 3 3）物體之間的遮擋關系與投影方式有關，）物體之間的遮擋關系與投影方式有關，在平行投影時，其遮擋關系可通過深度值來確定。l 凸多面體的每個面要么可見，要么凸多面體的每個面要么可見，要么不可見；不可能出現(xiàn)一個面部分可不

18、可見；不可能出現(xiàn)一個面部分可見，部分不可見。見，部分不可見。xyz三、凸多面體隱藏線的消除三、凸多面體隱藏線的消除l 凸多面體是由若干個平面圍成的物體。凸多面體是由若干個平面圍成的物體。假設這些平面方程為：假設這些平面方程為： ai x+bi y+ci z+di=0 (i=1,2,n)調整系數(shù)的符號，使每個平面的法向調整系數(shù)的符號，使每個平面的法向量（量（ai,bi,ci）指向多面體內部。指向多面體內部。l 如果投影方向為（如果投影方向為（Xp,Yp,Zp）,那么那么（ai,bi,ci）( (Xp,Yp,Zp）0時，時，此平面為不可見面，在作圖時，此平面為不可見面，在作圖時，此面不繪制。此面不

19、繪制。 凸多面體消隱的基本原理凸多面體消隱的基本原理 表面外法線與其可見性的關系表面外法線與其可見性的關系 設平面設平面Pi上任一點的外法矢上任一點的外法矢ni與該點的視線矢量與該點的視線矢量vi的數(shù)的數(shù)量積：量積： 從而有從而有 其中其中i為為ni與與vi之間的夾角，之間的夾角，i=1，2，m，這里，這里m為平面數(shù)。為平面數(shù)。iiiiivnvncos 當當 cos i i0 0 ，即，即 0 i i /2 時，時，Pi為朝前面，為可見的，應為朝前面，為可見的，應該畫出；該畫出； 當當 cos i i00 ，即，即 /2 face_zmax(i) Then face_zmax(i) = zz(

20、line_p(j) Next jNext i 求各面最大求各面最大Z坐標坐標 XYZ012345675050 For i = 0 To 5 L = i For m = i + 1 To 5 If (face_zmax(m) face_zmax(L) Then L = m Next m If (L i) Then k = face_s(i): face_s(i) = face_s(L): face_s(L) = k k = face_e(i): face_e(i) = face_e(L): face_e(L) = k k = face_zmax(i): face_zmax(i) = face_z

21、max(L): face_zmax(L) = k End If Next i 對面表根據(jù)最大對面表根據(jù)最大Z坐標從小到大排序坐標從小到大排序 face_s = Array(0, 5, 10, 15, 20, 25) face_e = Array(4, 9, 14, 19, 24, 29) face_zmax=Array(68,90,54,90,90,22) face_s = Array(25, 10, 0, 5, 15, 20) face_e = Array(29, 14, 4, 9, 19, 24) face_zmax=Array(22,54,68,90,90,90)For i = 0 To

22、 5 多邊形面多邊形面循環(huán)循環(huán) ymin = 10000: ymax = 0 For j = face_s(i) To face_e(i) - 1 If (yy(line_p(j) ymax) Then ymax = yy(line_p(j) Next 計算面多邊形頂點的最大最小值計算面多邊形頂點的最大最小值 For h = ymin To ymax 掃描線循環(huán)掃描線循環(huán) k = 0 For j = face_s(i) To face_e(i) - 1 面多邊形的邊循環(huán)面多邊形的邊循環(huán) If Int(yy(line_p(j + 1) Int(yy(line_p(j) Then t = (h -

23、 yy(line_p(j) - 0.5) / (yy(line_p(j + 1) - yy(line_p(j) If (t = 0 And t 0)then for i=fs(j) to fe(j)-1 picture1.line(xx(i),yy(i)-(xx(i+1),yy(i+1) next endifendif兩個面正軸測投影兩個面正軸測投影-消隱消隱 a=(y2- y1)(z3 - z1)- (y3- y1)(z2 - z1) b=(z2- z1)(x3 - x1)- (z3- z1)(x2 - x1) c=(x2- x1)(y3 - y1)- (x3- x1)(y2 - y1)2.

24、 深度緩沖器算法深度緩沖器算法(Z-buffer算法）算法） Z緩沖器算法的基本思想是緩沖器算法的基本思想是： 將投影平面每個像素所對應的所有面片（平面或曲面）將投影平面每個像素所對應的所有面片（平面或曲面）的深度進行比較，然后取離視線最近面片的屬性值作為該像的深度進行比較，然后取離視線最近面片的屬性值作為該像素的屬性值。見圖。素的屬性值。見圖。 Z緩沖器算法基本思想緩沖器算法基本思想S3S2S1(x,y)XvZvYv一種典型的、也是最簡單的像空間消隱算法一種典型的、也是最簡單的像空間消隱算法Z緩緩沖器沖器每個單元存放對應象素每個單元存放對應象素當前最近面的深度值當前最近面的深度值幀緩幀緩沖器

25、沖器每個單元存放對應象素每個單元存放對應象素的顏色值的顏色值深度緩沖器算法深度緩沖器算法 算法描述算法描述深度緩沖器所有單元均置為最小深度緩沖器所有單元均置為最小z值，幀緩沖值，幀緩沖器各單元均置為背景色，然后逐個處理多邊形器各單元均置為背景色，然后逐個處理多邊形表中的各面片。表中的各面片。每掃描一行，計算該行各像素點（每掃描一行，計算該行各像素點（x，y）所對）所對應的深度值應的深度值z（x，y），并將結果與深度緩沖），并將結果與深度緩沖器中該像素單元所存儲的深度值器中該像素單元所存儲的深度值ZB（x，y）進行比較。進行比較。若若zZB（x，y）,則則ZB（x，y）= z，同時將，同時將該像

26、素的屬性值該像素的屬性值I（x，y）寫入幀緩沖器，即）寫入幀緩沖器，即FB（x，y）= I（x，y）；否則不變。）；否則不變。算法描述：算法描述：for ( v= 0;vvmax;v+) for (u= 0; u Z緩沖器的第緩沖器的第(u,v)單元的值單元的值) 置幀緩沖器的第置幀緩沖器的第(u,v)單元值為當前多邊形顏色；單元值為當前多邊形顏色； 置置Z緩沖器的第緩沖器的第(u,v)單元值為單元值為d; 深度緩沖器算法深度緩沖器算法 深度值的計算深度值的計算若已知多邊形的方程，則可用增量法計若已知多邊形的方程，則可用增量法計算掃描線每一個像素的深度。設平面方算掃描線每一個像素的深度。設平面

27、方程為：程為：則多邊形面上的點（則多邊形面上的點（x，y）所對應的深）所對應的深度值為：度值為： CDByAxz)(C0C0 0DCzByAx 由于所有掃描線上相鄰點間的水平間距由于所有掃描線上相鄰點間的水平間距為為1個像素單位，掃描線行與行之間的垂個像素單位，掃描線行與行之間的垂直間距也為直間距也為1。因此可以利用這種連貫性。因此可以利用這種連貫性來簡化計算過程，如圖所示。來簡化計算過程，如圖所示。 深度計算深度計算 若已計算出（若已計算出（x，y）點的深度值為）點的深度值為zi，沿，沿x方向相鄰連貫點（方向相鄰連貫點（x+1，y）的深度值）的深度值zi+1可可由下式計算：由下式計算： 沿多邊形左邊界遞歸計算邊界上各點的坐標：沿多邊形左邊界遞歸計算邊界上各點的坐標： m為該邊的斜率，沿該邊的