第講計(jì)算機(jī)圖形學(xué)消隱算法

1、消隱(xio yn)算法 主要(zhyo)內(nèi)容: 一、概述二、消隱的基本技術(shù)三、凸多面體消除隱藏線四、消除隱藏面 共六十二頁 用計(jì)算機(jī)生成三維形體的真實(shí)圖形，是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容之一。在使用顯示設(shè)備描繪三維圖形時，必須把三維信息(xnx)作某種投影變換，在二維顯示表面上繪制出來。 由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性：要消除二義性，必須在繪制時消隱實(shí)際不可見得線和面，即消隱。經(jīng)過(jnggu)消隱的投影圖稱為物體的真實(shí)圖形。一、概述共六十二頁消隱(xio yn)不僅與消隱(xio yn)對象有關(guān)，還與觀察者的位置有關(guān)。如圖所示，由于視點(diǎn)的位置不同，物體的可見部分也不同：消隱

2、與觀察者的位置(wi zhi)關(guān)系共六十二頁按消隱的對象分類線消隱（Hidden-line）面消隱（Hidden-surface）按消隱空間分類物體空間消隱算法(sun f)圖像空間消隱算法共六十二頁線消隱（Hidden-line） 消隱對象是物體上不可見的線，一般用于線框圖。當(dāng)用筆式繪圖儀或其它畫線設(shè)備繪制圖形(txng)時，主要使用這種算法。面消隱（Hidden-surface） 消隱對象是物體上不可見的面，一般用于填色圖。當(dāng)用光柵掃描顯示器繪制圖形時，主要使用這種算法。 早期圖形顯示器是用線條表示圖形，消隱主要是消隱線問題。使用光柵顯示器后，物體可用連續(xù)變化的色調(diào)(s dio)來描述，消

3、隱算法的研究漸漸轉(zhuǎn)向消隱面的問題。 共六十二頁第一種是物空間算法。它以三維場景中的物體對像作為(zuwi)處理單元的，在所有的對像之間進(jìn)行比較，除去完全不可見的的物體和物體上不可見的部分。常用于線框表示立體的線隱藏，也用于面隱藏。for (場景中的每一個(y )物體) 將其與場景中的其它物體比較，確定其表面的可見部分；顯示該物體表面的可見部分； 隱藏線（面）的消除的兩種基本算法特點(diǎn)是：算法可以達(dá)到相當(dāng)高的精度。 共六十二頁第二種是像空間算法。 它以構(gòu)成(guchng)圖形的每一個像素為處理單元的，確定場景中哪些表面的像素相對于觀察點(diǎn)而言是可見的，用該表面的顏色填充該像素。常用于隱藏面。特點(diǎn)是：

4、算法精度低，只能達(dá)到屏幕精度為止，但速度往往更高。 其算法是對每一個像素:在和投影點(diǎn)到像素的連線相交的表面中找到離觀察點(diǎn)最近的表面用該表面上交點(diǎn)處的顏色填充該像素。 for (窗口內(nèi)的每一個(y )像素) 確定距視點(diǎn)最近的物體，以該物體表 面的顏色來顯示像素共六十二頁算法(sun f)復(fù)雜度 假設(shè)場景中有k個物體(wt)，平均每個物體表面由h個多邊形構(gòu)成，顯示區(qū)域中有m x n個像素，則： 第一種算法的復(fù)雜度為： O(kh)(kh) 第二種算法的復(fù)雜度為：O(mnkh)共六十二頁9物空間消隱算法: 需對物體表面的h個多邊形中的每個面與其余h-1個面進(jìn)行比較，精確地求出物體上每個棱邊(ln bi

5、n)或每個面的遮擋關(guān)系。算法的計(jì)算量正比于h2，即算法復(fù)雜度為：O(h)2) 。 則：k個物體的算法復(fù)雜度為：O(kh)2) 。共六十二頁10象空間消隱算法： 這類算法對屏幕上的每個象素進(jìn)行判斷(pndun)，以決定物體上哪個多邊形在該象素 點(diǎn)上是可見的。若屏幕上有mn個象素點(diǎn)，每個物體表面上有h個多邊形，則該類消隱算法計(jì)算量正比于mnh。 則： k個物體的算法復(fù)雜度為： O(mnkh) 。共六十二頁 各種消隱算法均采用一定形式的幾何排序。通過排序，可搜查出位置上靠近觀察者的幾何元素，確定幾何元素之間在位置上的遮擋關(guān)系，解決消隱計(jì)算的主要問題。各種算法都有各自的排序方法和排序次序(cx)。排序

6、次序(cx)影響算法的效率。 算法(sun f)排序共六十二頁二、 消隱基本(jbn)技術(shù) 為了提高(t go)消隱算法的效率，各種消隱算法常采用一些有效的消隱基本算法。利用連貫性將透視投影轉(zhuǎn)換成平行投影包圍盒技術(shù)背面剔除空間分割技術(shù)物體分層表示共六十二頁 物體(wt)連貫性面的連貫性 區(qū)域連貫性 掃描線的連貫性 深度連貫性 利用(lyng)連貫性 連貫性是指從一個事物到另一個事物，其屬性值(如顏色值、空間位置)通常是平緩過渡的性質(zhì)。例如： 棱邊的連貫性是指：棱邊的可見性在它與其他棱邊相交時才發(fā)生變換； 面的連貫性是指：如果面的一部分是可見的，則一般情況下整個面都是可見的。共六十二頁物體連貫性

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

8、比如，2D的矩形，3D的立方塊、長方體、球等。目的： 避免盲目的求交測試； 各物體間的比較等。一個好的包圍盒要具有兩個條件：包圍和充分緊密包圍著形體；對其的測試比較簡單。例：矩形包圍盒及長方體包圍盒提高算法效率共六十二頁包圍盒不相交，線段和多邊形也不相交，線段完全可見，無需就線段和多邊形的遮擋關(guān)系進(jìn)行進(jìn)一步判斷?？赏茝V到面與面的遮擋快速判斷。例如：兩個空間多邊形A、B在投影(tuyng)平面上的投影(tuyng)分別為A，B ，因?yàn)锳 、B的矩形包圍盒不相交，則A、B不相交，無須進(jìn)行遮擋測試。右圖：包圍盒相交，投影也相交；包圍盒相交，投影不相交。AABB共六十二頁 背面(bimin)剔除 外法

9、向 外法向與投影方向(fngxing)（觀察方向(fngxing)）的夾角判斷：前向面與后向面（背面）剔除依據(jù)： 物體表面是封閉的，背面總是被前向面所遮擋，從而始終是 不可見的。共六十二頁法向向量N 視線向量V法向向量N 法向向量N 90 90共六十二頁 視線-法線夾角法N 面的法向量(xingling)V 面上一點(diǎn)指向觀察點(diǎn)的向量 = cos-1( )0= 時 可見 = 0N . V02共六十二頁、空間(kngjin)分割技術(shù)依據(jù)：場景中的物體，它們的投影在投影平面上 是否有相互(xingh)遮擋的重疊部分？ 對于根本不存在相互遮擋關(guān)系的物體，應(yīng) 避免這種不必要的測試。方法：將投影平面上的窗

10、口分成若干小區(qū)域；為每個小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷哪個物體可見時，只要對本區(qū)域的相關(guān)物體表中的物體進(jìn)行比較即可。共六十二頁復(fù)雜度比較： 假定每個小區(qū)域的相關(guān)物體表中平均有h個物體，場景中有k個物體，由于物體在場景中的分布是分散(fnsn)的，顯然h遠(yuǎn)小于k。 根據(jù)物空間消隱方法所述，其算法復(fù)雜度為O(h2),遠(yuǎn)小于O(k2)。共六十二頁 物體(wt)分層表示表示形式：模型(mxng)變換中的樹形表示方式原理：減少場景中物體的個數(shù)，降低算法復(fù)雜度。方法： 將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)物體的包圍盒，當(dāng)兩個父節(jié)點(diǎn)之間不存在遮擋關(guān)系時，就勿對兩者的子節(jié)點(diǎn)

11、做進(jìn)一步測試。 父節(jié)點(diǎn)之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測試。共六十二頁 將透視(tush)投影轉(zhuǎn)換成平行投影 消隱與透視關(guān)系較密切，體現(xiàn)在： 1）消隱必須在投影之前完成；因?yàn)橄[需要物體三維信息，投影后只有二維信息； 2）物體之間的遮擋關(guān)系與投影中心（視點(diǎn)(sh din)） 的選取有關(guān)； 3）物體之間的遮擋關(guān)系與投影方式有關(guān)，在平行投影時，其遮擋關(guān)系可通過深度值來確定。共六十二頁 凸多面體的每個面要么(yo me)可見，要么(yo me)不可見；不可能出現(xiàn)一個面部分可見，部分不可見。xyz三、凸多面體隱藏(yncng)線的消除 凸多面體是由若干個平面圍成的物體。假設(shè)這些平面方程為：

12、ai x+bi y+ci z+di=0 (i=1,2,n)調(diào)整系數(shù)的符號，使每個平面的法向量（ai,bi,ci）指向多面體內(nèi)部。 如果投影方向?yàn)椋╔p,Yp,Zp）,那么（ai,bi,ci）(Xp,Yp,Zp）0時，此平面為不可見面，在作圖時，此面不繪制。共六十二頁凸多面體消隱的基本原理表面外法線與其可見性的關(guān)系 設(shè)平面Pi上任一點(diǎn)(y din)的外法矢ni與該點(diǎn)的視線矢量vi的數(shù)量積： 從而有 其中i為ni與vi之間的夾角，i=1，2，m，這里m為平面數(shù)。共六十二頁當(dāng) cosi0 ，即 0i /2 時，Pi為朝前面，為可見的，應(yīng)該畫出；當(dāng) cosi0 ，即 /2 face_zmax(i) T

13、hen face_zmax(i) = zz(line_p(j) Next jNext i 求各面最大Z坐標(biāo) XYZ0123456750共六十二頁 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): fac

14、e_zmax(i) = face_zmax(L): face_zmax(L) = k End If Next i 對面表根據(jù)(gnj)最大Z坐標(biāo)從小到大排序 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)共六十二

15、頁For i = 0 To 5 多邊形面循環(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 計(jì)算(j sun)面多邊形頂點(diǎn)的最大最小值 For h = ymin To ymax 掃描線循環(huán) k = 0 For j = face_s(i) To face_e(i) - 1 面多邊形的邊循環(huán) If Int(yy(line_p(j + 1) Int(yy(line_p(j) Then t = (h - yy(line_p(j)

16、 - 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兩個面正軸測投影(tuyng)-消隱 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. 深度(shnd)緩沖

17、器算法(Z-buffer算法）Z緩沖器算法的基本思想是： 將投影平面每個像素所對應(yīng)(duyng)的所有面片（平面或曲面）的深度進(jìn)行比較，然后取離視線最近面片的屬性值作為該像素的屬性值。見圖。 Z緩沖器算法基本思想S3S2S1(x,y)XvZvYv一種典型的、也是最簡單的像空間消隱算法共六十二頁幀緩存來存放每個象素的顏色值初值可放對應(yīng)背景(bijng)顏色的值深度緩存來存放每個象素的深度值。初值取成z的極小值。Z緩沖器每個單元存放對應(yīng)象素當(dāng)前最近面的深度值幀緩沖器每個單元存放對應(yīng)象素的顏色值屏幕(pngm)共六十二頁深度(shnd)緩沖器算法算法描述深度(shnd)緩沖器所有單元均置為最小z值，

18、幀緩沖器各單元均置為背景色，然后逐個處理多邊形表中的各面片。每掃描一行，計(jì)算該行各像素點(diǎn)（x，y）所對應(yīng)的深度值z（x，y），并將結(jié)果與深度緩沖器中該像素單元所存儲的深度值ZB（x，y）進(jìn)行比較。若zZB（x，y）,則ZB（x，y）= z，同時將該像素的屬性值I（x，y）寫入幀緩沖器，即FB（x，y）= I（x，y）；否則不變。共六十二頁算法(sun f)描述：for ( v= 0;vvmax;v+) for (u= 0; u Z緩沖器的第(u,v)單元的值) 置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第(u,v)單元值為d; 共六十二頁深度(shnd)緩沖器算法深度值的計(jì)

19、算若已知多邊形的方程，則可用增量法計(jì)算掃描線每一個像素的深度。設(shè)平面(pngmin)方程為：則多邊形面上的點(diǎn)（x，y）所對應(yīng)的深度值為： C0 共六十二頁由于所有(suyu)掃描線上相鄰點(diǎn)間的水平間距為1個像素單位，掃描線行與行之間的垂直間距也為1。因此可以利用這種連貫性來簡化計(jì)算過程，如圖所示。 深度計(jì)算共六十二頁若已計(jì)算出（x，y）點(diǎn)的深度值為zi，沿x方向相鄰連貫點(diǎn)（x+1，y）的深度值zi+1可由下式計(jì)算： 沿多邊形左邊界遞歸計(jì)算邊界上各點(diǎn)的坐標(biāo)： m為該邊的斜率(xil)，沿該邊的深度也可以遞歸計(jì)算出來，即： 共六十二頁如果該邊是一條(y tio)垂直邊界，則計(jì)算公式簡化為： 對于每條掃描線，首先根據(jù)公式計(jì)算出與其相交的多邊形最左邊的交點(diǎn)所對應(yīng)的深度值，然后，利用圖形