消隱算法主要內(nèi)容:

一、概述二、消隱的基本技術(shù)三、凸多面體消除隱藏線四、消除隱藏面

用計算機(jī)生成三維形體的真實圖形，是計算機(jī)圖形學(xué)研究的重要內(nèi)容之一。在使用顯示設(shè)備描繪三維圖形時，必須把三維信息作某種投影變換，在二維顯示表面上繪制出來。由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性：

要消除二義性，必須在繪制時消隱實際不可見得線和面，即消隱。經(jīng)過消隱的投影圖稱為物體的真實圖形。一、概述消隱不僅與消隱對象有關(guān)，還與觀察者的位置有關(guān)。如圖所示，由于視點的位置不同，物體的可見部分也不同：消隱與觀察者的位置關(guān)系按消隱的對象分類線消隱（Hidden-line）面消隱（Hidden-surface）按消隱空間分類物體空間消隱算法圖像空間消隱算法線消隱（Hidden-line）消隱對象是物體上不可見的線，一般用于線框圖。當(dāng)用筆式繪圖儀或其它畫線設(shè)備繪制圖形時，主要使用這種算法。面消隱（Hidden-surface）消隱對象是物體上不可見的面，一般用于填色圖。當(dāng)用光柵掃描顯示器繪制圖形時，主要使用這種算法。

早期圖形顯示器是用線條表示圖形，消隱主要是消隱線問題。使用光柵顯示器后，物體可用連續(xù)變化的色調(diào)來描述，消隱算法的研究漸漸轉(zhuǎn)向消隱面的問題。

第一種是物空間算法。它以三維場景中的物體對像作為處理單元的，在所有的對像之間進(jìn)行比較，除去完全不可見的的物體和物體上不可見的部分。常用于線框表示立體的線隱藏，也用于面隱藏。for(場景中的每一個物體){將其與場景中的其它物體比較，確定其表面的可見部分；顯示該物體表面的可見部分；}隱藏線（面）的消除的兩種基本算法特點是：算法可以達(dá)到相當(dāng)高的精度。

第二種是像空間算法。它以構(gòu)成圖形的每一個像素為處理單元的，確定場景中哪些表面的像素相對于觀察點而言是可見的，用該表面的顏色填充該像素。常用于隱藏面。特點是：算法精度低，只能達(dá)到屏幕精度為止，但速度往往更高。

其算法是對每一個像素:在和投影點到像素的連線相交的表面中找到離觀察點最近的表面用該表面上交點處的顏色填充該像素。

for(窗口內(nèi)的每一個像素) {確定距視點最近的物體，以該物體表面的顏色來顯示像素}算法復(fù)雜度假設(shè)場景中有k個物體，平均每個物體表面由h個多邊形構(gòu)成，顯示區(qū)域中有mxn個像素，則：第一種算法的復(fù)雜度為：O((kh)×(kh))

第二種算法的復(fù)雜度為：O(mnkh)9物空間消隱算法:需對物體表面的h個多邊形中的每個面與其余h-1個面進(jìn)行比較，精確地求出物體上每個棱邊或每個面的遮擋關(guān)系。算法的計算量正比于h2，即算法復(fù)雜度為：O((h)2)

。則：k個物體的算法復(fù)雜度為：O((kh)2)

。10象空間消隱算法：這類算法對屏幕上的每個象素進(jìn)行判斷，以決定物體上哪個多邊形在該象素點上是可見的。若屏幕上有m×n個象素點，每個物體表面上有h個多邊形，則該類消隱算法計算量正比于mnh。則：k個物體的算法復(fù)雜度為：O(mnkh)

。各種消隱算法均采用一定形式的幾何排序。通過排序，可搜查出位置上靠近觀察者的幾何元素，確定幾何元素之間在位置上的遮擋關(guān)系，解決消隱計算的主要問題。各種算法都有各自的排序方法和排序次序。排序次序影響算法的效率。算法排序二、消隱基本技術(shù)為了提高消隱算法的效率，各種消隱算法常采用一些有效的消隱基本算法。利用連貫性將透視投影轉(zhuǎn)換成平行投影包圍盒技術(shù)背面剔除空間分割技術(shù)物體分層表示物體連貫性 面的連貫性區(qū)域連貫性掃描線的連貫性 深度連貫性利用連貫性連貫性是指從一個事物到另一個事物，其屬性值(如顏色值、空間位置)通常是平緩過渡的性質(zhì)。例如：

棱邊的連貫性是指：棱邊的可見性在它與其他棱邊相交時才發(fā)生變換；

面的連貫性是指：如果面的一部分是可見的，則一般情況下整個面都是可見的。物體連貫性若物體A與物體B是完全分離的，消隱時只需要比較兩物體之間的遮擋關(guān)系即可，不需要對它們的表面多邊形逐一進(jìn)行測試；

面的連貫性一張面內(nèi)的各種屬性值一般是緩慢變化的，可采用增量的形式對其進(jìn)行計算；

區(qū)域連貫性一個區(qū)域一般指屏幕上一組相鄰的象素，他們通常為同一個可見面所占據(jù)，可見性相同；

掃描線的連貫性在相鄰兩條掃描線上，可見面的分布情況相似；

深度連貫性同一表面上的相鄰部分深度是相近的，而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同，這樣只需取其上一點計算出深度值，比較該深度值便能得出結(jié)果；

包圍盒技術(shù)一個形體的包圍盒指的是包圍它的簡單形體。比如，2D的矩形，3D的立方塊、長方體、球等。目的：避免盲目的求交測試； 各物體間的比較等。一個好的包圍盒要具有兩個條件：包圍和充分緊密包圍著形體；對其的測試比較簡單。例：矩形包圍盒及長方體包圍盒提高算法效率包圍盒不相交，線段和多邊形也不相交，線段完全可見，無需就線段和多邊形的遮擋關(guān)系進(jìn)行進(jìn)一步判斷?？赏茝V到面與面的遮擋快速判斷。例如：兩個空間多邊形A、B在投影平面上的投影分別為A’，B’

，因為A’

、B’的矩形包圍盒不相交，則A’、B’不相交，無須進(jìn)行遮擋測試。右圖：包圍盒相交，投影也相交；包圍盒相交，投影不相交。AA’BB’背面剔除

外法向 外法向與投影方向（觀察方向）的夾角判斷：前向面與后向面（背面）剔除依據(jù)：物體表面是封閉的，背面總是被前向面所遮擋，從而始終是不可見的。法向向量N

視線向量V法向向量N

法向向量N<90°<90°可見可見

不可見>90°視線-法線夾角法N

面的法向量V

面上一點指向觀察點的向量=cos-1()0<=<時可見<=<=時不可見2N.V|N||V|N.V>0N.V<02、空間分割技術(shù)依據(jù)：場景中的物體，它們的投影在投影平面上是否有相互遮擋的重疊部分？對于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測試。方法：將投影平面上的窗口分成若干小區(qū)域；為每個小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷哪個物體可見時，只要對本區(qū)域的相關(guān)物體表中的物體進(jìn)行比較即可。復(fù)雜度比較：假定每個小區(qū)域的相關(guān)物體表中平均有h個物體，場景中有k個物體，由于物體在場景中的分布是分散的，顯然h遠(yuǎn)小于k。根據(jù)物空間消隱方法所述，其算法復(fù)雜度為O(h2),遠(yuǎn)小于O(k2)。物體分層表示表示形式：模型變換中的樹形表示方式原理：減少場景中物體的個數(shù)，降低算法復(fù)雜度。方法：將父節(jié)點所代表的物體看成子節(jié)點物體的包圍盒，當(dāng)兩個父節(jié)點之間不存在遮擋關(guān)系時，就勿對兩者的子節(jié)點做進(jìn)一步測試。父節(jié)點之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測試。將透視投影轉(zhuǎn)換成平行投影消隱與透視關(guān)系較密切，體現(xiàn)在：

1）消隱必須在投影之前完成；因為消隱需要物體三維信息，投影后只有二維信息；2）物體之間的遮擋關(guān)系與投影中心（視點）的選取有關(guān)；3）物體之間的遮擋關(guān)系與投影方式有關(guān)，在平行投影時，其遮擋關(guān)系可通過深度值來確定。凸多面體的每個面要么可見，要么不可見；不可能出現(xiàn)一個面部分可見，部分不可見。xyz三、凸多面體隱藏線的消除凸多面體是由若干個平面圍成的物體。假設(shè)這些平面方程為：

ai

x+bi

y+ci

z+di=0(i=1,2,…n)調(diào)整系數(shù)的符號，使每個平面的法向量（ai,bi,ci）指向多面體內(nèi)部。如果投影方向為（Xp,Yp,Zp）,那么（ai,bi,ci）·(Xp,Yp,Zp）<0時，此平面為不可見面，在作圖時，此面不繪制。凸多面體消隱的基本原理表面外法線與其可見性的關(guān)系

設(shè)平面Pi上任一點的外法矢ni與該點的視線矢量vi的數(shù)量積：

從而有

其中θi為ni與vi之間的夾角，i=1，2，…，m，這里m為平面數(shù)。當(dāng)

cosθi≥0

，即0≤θi≤π/2時，Pi為朝前面，為可見的，應(yīng)該畫出；當(dāng)cosθi<0，即π/2

<θi≤π時，Pi為朝后面，不可見，不畫出或用虛線表示。視線方向與外法線的關(guān)系如圖7-7。視線方向與外法線的關(guān)系

視線矢量平行于某一基本坐標(biāo)軸時夾角的計算：

當(dāng)視線矢量vi平行于某一基本坐標(biāo)軸時，那么平面的外法矢量n{A，B，C}與視線矢量的夾角就是外法矢量n與某一基本坐標(biāo)軸的夾角，分別用α、β、γ表示，視線矢量平行X、Y、Z軸時平面的外法矢量n{A，B，C}與坐標(biāo)軸的夾角。當(dāng)視線矢量平行Z軸時，有同理，若視線矢量平行X軸時，某平面的可見性由該平面外法矢量n在X軸的方向分量A所決定。若視線矢量平行y軸時，某平面的可見性由該平面外法矢量n在Y軸的方向分量B所決定。平面多邊形的外法矢量的計算為了判別物體上各表面是朝前面還是朝后面，需求出各表面（平面多邊形）指向物體外側(cè)的法矢量。如圖所示。物體表面外法矢量在圖中，平面P1P2P3的外法矢量·任意多邊形法矢量的算法方法如下：設(shè)法矢量，三個方向分量為：

式中：m為頂點號，若i≠n，則j=i+1；否則i=m，j=1。為避免在程序中出現(xiàn)兩種計算外法矢量的方法，建議凸多邊形也采用該算法進(jìn)行計算。多邊形所在的平面方程可寫成：

其中：，為平面上任意一點。算法實現(xiàn)的一般步驟根據(jù)表面的數(shù)據(jù)結(jié)構(gòu)，取頂點數(shù)據(jù)，計算表面的外法線矢量。計算外法線在投影方向上的分量的值。根據(jù)分量的值判斷表面的可見性。若表面可見畫出該表面，否則處理下一個表面。計算平面法向量已知平面上三個點的坐標(biāo)為（x1,y1,z1)、（x2,y2,z2)、（x3,y3,z3)，其順序符合右手規(guī)則，其大姆指所指方向為該平面的法向量（a,b,c),則：

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)如：投影面為XOY面，投影方向從（0，0，10）到（10，-10，0），即（10，-10，-10）（斜投影）0123面：（0，0，1）·(10，-10，-10）=-10不可見4567面：（0，0，-1）·(10，-10，-10）=10可見0145面：（0，1，0）·(10，-10，-10）=-10不可見2367面：（0，-1，0）·(10，-10，-10）=10可見0374面：（1，0，0）·(10，-10，-10）=10可見1256面：（-1，0，0）·(10，-10，-10）=-10不可見XZ01234567Y實體模型數(shù)據(jù)結(jié)構(gòu)之一000100001002000020000030010003001002003000200300

xyz01234567045910141519202425290123450123076547...0123456789..XZ01234567Yx=array(0,100,100,0,0,100,100,0)y=array(0,0,200,200,0,0,200,200)z=array(0,0,0,0,300,300,300,300)line_p=array(0,1,2,3,0,7,6,5,4,7,1,5,6,2,1,0,3,7,4,0,6,7,3,2,6,4,5,1,0,4)face_s=array(0,5,10,15,20,25)face_e=array(4,9,14,19,24,29)面表線表頂點表1.畫家算法(深度排序算法）是同時運(yùn)用物空間與像空間算法的操作，在物空間和像空間中完成排序，在像空間中完成掃描轉(zhuǎn)換。畫家的作畫時，先涂背景色，然后由遠(yuǎn)及近的將景物畫上，順序暗示出所畫物體之間的相互遮擋關(guān)系。所以稱為畫家算法。算法基本原理：1）先把屏幕置成背景色；2）將場景中的物體的各個面按其距觀察點的遠(yuǎn)近進(jìn)行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點遠(yuǎn)的優(yōu)先級低，放在表頭；距觀察點近的優(yōu)先級高，放在表尾）該表稱為深度優(yōu)先級表。3）然后按照從遠(yuǎn)到近（從表頭到表尾）的順序逐個繪制物體表面。也稱：表優(yōu)先級算法四、消除隱藏面深度優(yōu)先級表的建立、多邊形優(yōu)先級的考慮首先對一個簡單的畫面，可以直接建立一個確定的深度優(yōu)先表如圖（a）所示。深度方向上無重疊。當(dāng)畫面略微復(fù)雜一點，卻無法按簡單的Z向排序建立確定的深度優(yōu)先表，以確定每一個多邊形的優(yōu)先級，如圖（b）所示。深度方向上有重疊QXZPRQXZP（a）（b）二、投影重疊判斷：測試按照難度遞增順序排列：1.P和Q在oxy平面上投影的包圍盒在x方向上不相交；2.P和Q在oxy平面上投影的包圍盒在y方向上不相交；3.P在Q之后。P的各頂點均在Q的遠(yuǎn)離視點的一側(cè)；4.Q在P之前。Q的各頂點均在P的靠近視點的一側(cè)；5.P和Q在觀察平面oxy上的投影不相交；上面5項只要有一項成立，P就不遮擋Q，不需要重新排序yyy對于1、2兩種情況，可利用包圍盒技術(shù)測試。對于3、4兩種情況，可根據(jù)“內(nèi)外法”測試。即將S面的頂點坐標(biāo)代入R面的方程：AX+BY+CZ+D，檢查結(jié)果值的符號。一般使建立的平面方程的外法線方向正對著視點，如果結(jié)果值小于零，則表示S面在R面的內(nèi)側(cè)，即S面位于R面的后面‘結(jié)果值大于零，則表示S面在R面的外側(cè)，即S面位于R面的前面。測試1至4均為假，則需執(zhí)行測試5。在XY平面上利用直線方程計算兩表面邊界的交點。但兩表面在坐標(biāo)范圍x、y、z方向上均重疊，也有可能不相交。如圖所示。對于某一重疊表面，上述五項測試均不成立，則需在有序表中調(diào)換兩個面的位置。S,S,S

S,S,SSSSzS,S

S,S有重疊SS調(diào)換兩個面的位置后，需要對調(diào)換過順序的表面重復(fù)上述5項測試。。對于兩個或多個表面循環(huán)遮擋，該算法可能導(dǎo)致無限循環(huán)。此時，算法反復(fù)將重疊表面的位置進(jìn)行組合。為避免死循環(huán)?？蓪φ{(diào)至更遠(yuǎn)處的表面進(jìn)行標(biāo)識。執(zhí)行重排序后，若某個面的位置需再次交換，則表明存在交叉覆蓋的情況，如圖所示，將P沿Q所在平面分割成兩部分P1和P2，從表中去掉原多邊形P，而將P的這兩個新的部分插入原表中的適當(dāng)位置，使其仍保持按Zmin排序的性質(zhì)。對新形成的表，重新執(zhí)行第二步。無法直接建立正確的深度優(yōu)先表。解決方法是沿多邊形所在平面間的交線循環(huán)分割這些多邊形。排序計算量大；多邊形相交或循環(huán)重疊時，必須分割多邊形。畫家算法的不足：x=Array(0,80,80,0,0,80,80,0)y=Array(0,0,80,80,0,0,80,80)8個頂點的X。、Y、Z坐標(biāo)z=Array(0,0,0,0,80,80,80,80)line_p=Array(0,1,2,3,0,7,6,5,4,7,1,5,6,2,1,0,3,7,4,0,6,7,3,2,6,4,5,1,0,4)face_s=Array(0,5,10,15,20,25)face_e=Array(4,9,14,19,24,29)Fori=0To7

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)Nexti‘各頂點繞X軸和Y軸的旋轉(zhuǎn)變換Fori=0To5face_zmax(i)=0Forj=face_s(i)Toface_e(i)-1Ifzz(line_p(j))>face_zmax(i)Thenface_zmax(i)=zz(line_p(j))NextjNexti‘求各面最大Z坐標(biāo)

XYZ0123456750Fori=0To5L=iForm=i+1To5If(face_zmax(m)<face_zmax(L))ThenL=mNextmIf(L<>i)Thenk=face_s(i):face_s(i)=face_s(L):face_s(L)=kk=face_e(i):face_e(i)=face_e(L):face_e(L)=kk=face_zmax(i):face_zmax(i)=face_zmax(L):face_zmax(L)=kEndIfNexti

‘對面表根據(jù)最大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)Fori=0To5‘多邊形面循環(huán)

ymin=10000:ymax=0

Forj=face_s(i)Toface_e(i)-1If(yy(line_p(j))<ymin)Thenymin=yy(line_p(j))If(yy(line_p(j))>ymax)Thenymax=yy(line_p(j))

Next

‘計算面多邊形頂點的最大最小值

Forh=yminToymax

‘掃描線循環(huán)

k=0

Forj=face_s(i)Toface_e(i)-1‘面多邊形的邊循環(huán)

IfInt(yy(line_p(j+1)))<>Int(yy(line_p(j)))Thent=(h-yy(line_p(j))-0.5)/(yy(line_p(j+1))-yy(line_p(j)))If(t>=0Andt<=1)Then

xjd(k)=xx(line_p(j))+(xx(line_p(j+1))-xx(line_p(j)))*tyjd(k)=h：k=k+1

‘計算掃描線與邊的交點

EndIfEndIf

Next

Picture1.Line(xjd(0),yjd(0))-(xjd(1),yjd(1)),RGB(face_s(i)*10,50,100)

NextNext正軸測投影(一個面正投影）XYZ0123456750x=Array(0,50,50,0,0)y=Array(0,0,50,50,0)z=Array(50,50,50,50,50)fori=0to3picture1.line(x(i),y(i))-(x(i+1),y(i+1))nextxx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)x=Array(0,50,50,0,0)y=Array(0,0,50,50,0)z=Array(50,50,50,50,50)fori=0to4

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextfori=0to3picture1.line(xx(i),yy(i))-(xx(i+1),yy(i+1))next一個面正軸測投影XYZ0123456750x=Array(0,0,50,50,0,0,0,0,0,0)y=Array(0,50,50,0,0,0,50,50,0,0)z=Array(50,50,50,50,50,0,0,50,50,0)fs=Array(0,5)fe=Array(4,9)fori=0to9

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextforj=0to1fori=fs(j)tofe(j)-1picture1.line(xx(i),yy(i))-(xx(i+1),yy(i+1))nextendif兩個面正軸測投影x=Array(0,0,50,50,0,0,0,0,0,0)y=Array(0,50,50,0,0,0,50,50,0,0)z=Array(50,50,50,50,50,0,0,50,50,0)fs=Array(0,5)：fe=Array(4,9)fori=0to9

xx(i)=x(i)*Cos(ry)+z(i)*Sin(ry)yy(i)=x(i)*Sin(ry)*Sin(rx)+y(i)*Cos(rx)-z(i)*Cos(ry)*Sin(rx)zz(i)=-x(i)*Sin(ry)*Cos(rx)+y(i)*Sin(rx)+z(i)*Cos(ry)*Cos(rx)nextforj=0to1

c=(xx(fs(j)+1)-xx(fs(j)))*(yy(fs(j)+2)-yy(fs(j)))-(xx(fs(j)+2)-xx(fs(j)))*(yy(fs(j)+1)-yy(fs(j)))

if(-c>0)thenfori=fs(j)tofe(j)-1picture1.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.深度緩沖器算法(Z-buffer算法）Z緩沖器算法的基本思想是：

將投影平面每個像素所對應(yīng)的所有面片（平面或曲面）的深度進(jìn)行比較，然后取離視線最近面片的屬性值作為該像素的屬性值。見圖。

Z緩沖器算法基本思想S3S2S1(x,y)XvZvYv一種典型的、也是最簡單的像空間消隱算法幀緩存來存放每個象素的顏色值初值可放對應(yīng)背景顏色的值深度緩存來存放每個象素的深度值。初值取成z的極小值。Z緩沖器每個單元存放對應(yīng)象素當(dāng)前最近面的深度值幀緩沖器每個單元存放對應(yīng)象素的顏色值屏幕深度緩沖器算法算法描述深度緩沖器所有單元均置為最小z值，幀緩沖器各單元均置為背景色，然后逐個處理多邊形表中的各面片。每掃描一行，計算該行各像素點（x，y）所對應(yīng)的深度值z（x，y），并將結(jié)果與深度緩沖器中該像素單元所存儲的深度值ZB（x，y）進(jìn)行比較。若z＞ZB（x，y）,則ZB（x，y）=z，同時將該像素的屬性值I（x，y）寫入幀緩沖器，即FB（x，y）