圖形學(xué)第5章隱藏線

第五章隱藏面和隱藏線的消除

三維立體模型主要有:線框結(jié)構(gòu)模型,表面模型,實體模型.

問題:線框結(jié)構(gòu)模型會出現(xiàn)錯誤理解.投影變換失去了深度信息，往往導(dǎo)致圖形的二義性

圖5-1立體出現(xiàn)的不同理解真實感圖形1)常規(guī)視覺上的真實（區(qū)分可見和不可見面）。2)表面效果的真實（表達材質(zhì)、光照、明暗等）?？梢姾筒豢梢娒?/p>

對于空間任何一個不透明的物體，只能看到該物體上朝向視線方向的那部分表面，而其余的表面是不可能看見的。對于包含有多個物體的場景，只能看到前面的物體，被擋在后面的物體是不可能看見的。提出問題

在給定視點和視線方向后，決定場景中哪些物體的表面是可見的，哪些是被遮擋不可見的。

消隱:解決顯示三維立體的圖形中消去不可見部分的方法,包括隱藏線和隱藏面.消隱算法也就成了真實感圖形的基本算法。

線框圖消隱圖真實感圖形消隱結(jié)果與觀察物體有關(guān)，也與視點有關(guān)。消隱

要繪出意義明確的，有真實感的立體圖形，首先必須消去形體中的不可見部分，而只表現(xiàn)可見部分。這就要去尋求解決顯示三維立體的圖形中消去不可見部分的方法，稱為消隱。消隱——隱線隱面消隱的分類按消隱對象分類線消隱:消隱對象是物體上的邊，消除的是物體上不可見的邊。面消隱

:消隱對象是物體上的面，消除的是物體上不可見的面。按消隱空間分類物體空間的消隱算法

（光線投射、Roberts）：將場景中每一個面與其他每個面比較，求出所有點、邊、面遮擋關(guān)系。圖像空間的消隱算法

(Z－buffer、掃描線、Warnock)：對屏幕上每個象素進行判斷，決定哪個多邊形在該象素可見。物體空間和圖像空間的消隱算法

(畫家算法):在物體空間中預(yù)先計算面的可見性優(yōu)先級，再在圖像空間中生成消隱圖。5.1多面體的隱藏線消除

三維模型一般用三種方法：線框模型、表面模型和實體模型。對于線框模型來說，所謂的消隱就是要消去線框模型中的隱藏線。

5.1.1減少直線求交

線框結(jié)構(gòu)模型,則隱藏線便是某些不可見的棱或棱的一部分。解決方法:找到各棱上可見和不可見部分的分界點，這些分界點都是多面體的各棱在oxy平面上投影間的交點。把內(nèi)法線方向背向視點的面稱為前向面，如圖5-2中的IJFGH，F(xiàn)ABG，HCDI和IDEJ所在的面為前向面，其余為后向面。圖5-2棱間交點只有5個5.1.2凸多面體的隱線消去1.定義:凸多面體是由多個平面凸多邊形包圍而成的立體.2.方法:對于單個凸多面體來說，只要畫出了立體上的全部朝前面，也就是正確地畫出了消隱后的立體圖形，因為凸多面體本身不存在朝前面間的遮擋關(guān)系。過程：

(1)建立描述立體圖形的數(shù)據(jù)結(jié)構(gòu)；

(2)按圖形種類進行頂點表變換；

(3)按環(huán)表計算各面的Ｂ值，根據(jù)其正負號判別是否可見；

(4)連點畫出可見面的邊框線段。1)數(shù)據(jù)結(jié)構(gòu)面表：面號，環(huán)指針。環(huán)表：組環(huán)逆向頂點號。頂點表：頂點坐標（x,y,z）。2)內(nèi)法向的計算設(shè)多邊形F的頂點為v1,v2…vi，頂點vi坐標為（xi,yi,zi）。頂點的次序：使觀察者在多面體外沿著v1→v2→vi走時，多邊形的內(nèi)部始終在他的左側(cè).計算多邊形在oxy平面上投影的有向面積B，計算方法如下：如果B≥0，則F所在的面為后相面。平面方程凸多面體:由若干個平面圍成的物體，這些平面方程為：平面的法向量n為（ai，bi，ci）或（-ai，-bi，-ci），規(guī)定n的選取滿足下列條件：對物體內(nèi)一點P0（x0，y0，z0）使得n·（x0，y0，z0）T＋di>0，這樣規(guī)定的法向量n指向了物體內(nèi)部隱藏面判斷視點與第i個面上一點連線方向為（li，mi，ni），則第i個面為自隱藏面的判斷方法是：對于任意凸對面體，可先求出所有隱藏面，然后檢查每條邊，若此邊為兩隱藏面的交線，則此邊是隱藏線，用虛線表示或消除。5.1.3凹多面體的隱藏線消除任意平面體消隱包括凹多面體、立體群。問題：空間一段線段AB和一個多邊形π，判斷線段是否被多邊形遮擋。如果全被遮擋則是隱藏線；若部分遮擋，則求出隱藏部分。方法:以視點為投影中心，把線段與多邊形頂點投影到投影面上，將各對應(yīng)投影點連線的方程與直線聯(lián)立求解，即可求得線段與多邊形投影的交點。算法思路：(1)計算Ｂ，判別出所有的朝前面作潛在可見面；(2)處理潛在可見面間的遮擋關(guān)系，落實到棱邊；(3)求出可見段的交集，繪成圖形。Ａ、Ｂ、Ｃ均為潛在可見面。其前后順序為Ｃ，Ｂ，Ａ。所以

一條邊線可能被多個面所遮擋。線段AB與多邊形投影的關(guān)系可能有兩種：線段與多邊形的任何邊都不相交；線段AB與投影多邊形有交點。1．線段與多邊形的任何邊都不相交又分兩種：即線段AB與投影多邊形分離，或線段AB在投影多邊形之中。前一種情況，線段完全可見。后一種情況，線段完全可見或完全隱藏，邊界盒排除不相交的線段求交方法:

把點vi在oxy平面上的投影記成Qi（xi，yi）。直線段Q1Q2的邊界盒是一包含這直線的邊平行于坐標軸的最小矩形，這個矩形由四個參數(shù)

xmin=min（x1，x2），ymin=min（y1，y2）

xmax=max（x1，x2），ymax=max（y1，y2）

如果兩個邊界盒的參數(shù)為xmini，ymini，xmaxi，ymaxi，i=1,2.當(dāng)它們滿足 （xmin1>xmax2）或（ymin1>ymax2） （xmin2>xmax1）或（ymin2>ymax1）這兩個邊界盒不相交，因而原來的兩條邊也不會相交。2.線段AB與投影多邊形有交點:平面對直線段的遮擋判斷算法(1)若線段的兩端點及視點在給定平面的同側(cè)，線段不被給定平面遮擋，轉(zhuǎn)7(2)若線段的投影與平面投影的包圍盒無交，線段不被給定平面遮擋，轉(zhuǎn)7(3)求直線與相應(yīng)平面的交。若無交點，轉(zhuǎn)4。否則，交點在線段內(nèi)部或外部。若交點在線段內(nèi)部，交點將線段分成兩段，與視點同側(cè)的一段不被遮擋，另一段在視點異側(cè)，轉(zhuǎn)4再判；若交點在線段外部，轉(zhuǎn)4。(4)求所剩線段的投影與平面邊界投影的所有交點，并根據(jù)交點在原直線參數(shù)方程中的參數(shù)值求出Z值(即深度)。若無交點，轉(zhuǎn)5。5)以上所求得的各交點將線段的投影分成若干段，求出第一段中點。(6)若第一段中點在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值進行判斷。(7)結(jié)束。視點與線段同側(cè)包圍盒不交分段交替取值分析:(1)每條線段上所有點具有相同的隱藏性。(2)可以從線段中點向視點引射線，僅當(dāng)此射線也多邊形相交時，線段才被多邊形隱藏。(3)依次把多邊形的邊進行對比便得到所有隱藏線。5.2曲面隱藏線消除（1）曲面由方程表示，建立M個象素，則建立M個內(nèi)存單元yu(j)稱之為上浮水平線數(shù)組，在這些單元中先放上初值，初值應(yīng)取成小于min(f(x,z))。

一般用x＝xi和z＝zi兩簇曲線表示,視點在Z軸方向.設(shè)，,i＝1，2……n，平面z＝zn是最靠近視點，于是平面Z＝zn上曲線都是可見的。而對于z＝zi平面上的曲線y＝f(x，zi)，在區(qū)間x∈[a，b]上只有兩種情況是可見的。(1)

f(x，zi)>maxf(x，zj)x∈[a，b](i<j)(2)

f(x，zi)<minf(x，zj)x∈[a，b](i<j)其余線段上應(yīng)當(dāng)消隱，。改進的曲面隱藏線消除

上述方法對下圖的曲面是不適用的，圖中的c點附近的虛線部分應(yīng)是可見的，但按上述算法卻成了不可見了。改進的曲面隱藏線消除技術(shù)首先，另外建立M個單元，。并計算若

則為可見，并如下修改或的值，可以表示為：5.3消除隱藏面問題：為了讓曲面在圖形顯示器上顯示，需要把對應(yīng)的曲面某點在屏幕的位置決定出來，即把曲面點變換成圖像中的點，這過程就是光柵化過程，于是有些曲面或曲面一部分會被遮擋住，因此需要解決消除隱藏面的問題。5.3.1區(qū)域子分算法算法思想：采用分而治之的策略，將整個屏幕看作為窗口，采用一個遞歸的四等分過程，每一次把矩形的窗口等分成四個相等的小矩形，分成的矩形也稱為窗口。每一次子分，均要把要顯示的多邊形和窗口的關(guān)系作一判斷。這種關(guān)系可有以下四種，如圖5-9所示。(a)分離（b）內(nèi)含(c)相交(d)包圍

圖5-9多邊形與窗口的關(guān)系在窗口和每個多邊形的關(guān)系確定以后，分下列三種情況。⑴所有多邊形都和窗口分離，這時只要把窗口內(nèi)所有的象素填上背景顏色。⑵只有一個多邊形和窗口相交，或這個多邊形包含在窗口內(nèi)。這時先對窗口內(nèi)每一象素填上背景顏色，再對窗口內(nèi)多邊形部分用掃描線算法填色。⑶只有一個多邊形和窗口相交，這個多邊形把窗口整個包圍在內(nèi)，或雖有幾個多邊形和窗口相交，但離觀察者最近的一個多邊形包圍了整個窗口，這時把整個窗口填上離觀察者最近的那個多邊形的顏色。對上述三種情況不成立的窗口再一分為四，分得的窗口重復(fù)上述的處理。當(dāng)窗口的邊長和一個象素的寬度基本相等，則取最靠近觀察者的多邊形的顏色，或這個窗口相交的多邊形顏色的平均值。5.3.2畫家算法

畫家算法源于油畫的作畫過程。根據(jù)景物的深度，先往畫布（背景色）上涂遠景的顏色，然后再涂上近景的顏色。這樣由遠及近，后涂的顏色遮蓋掉先涂的顏色，最終得到的結(jié)果就相當(dāng)于消除了隱藏面。

畫家算法的思想：把景物中各個面按其離視點的距離進行排序建成深度優(yōu)先級表。然后由遠至近取出表中的多邊形投影到屏幕上，近的后投的,覆蓋了遠的先投的，結(jié)果相當(dāng)于消除了隱藏面。算法特點：畫家算法的優(yōu)點是簡單，容易實現(xiàn)，可以作為實現(xiàn)更復(fù)雜算法的基礎(chǔ)。它的缺點是只能處理互不相交的面，而且，深度優(yōu)先級表中面的順序可能出錯。畫家算法的關(guān)鍵技術(shù)：對多邊形進行深度排序設(shè)每個多邊形有一些頂點，這些頂點各有一個Z坐標，取其中Z坐標最小的記為Zmin，取其中Z坐標最大的記為Zmax，于是每一個多邊形都有自己的Zmax和Zmin。按Zmin的大小把多邊形初步排序。假設(shè)Zmin最小的多邊形為P，它暫時成為優(yōu)先級最低的一個多邊形。對其他任意一個多邊形Q，研究P與Q的關(guān)系：對場景中的物體按深度排序深度重疊測試.1.若Zmax(P)<Zmin(Q)，則P不為遮擋Q。 若Zmax(P)>Zmin(Q)而又有Zmin(P)<Zmin(Q)，則需要作進一步檢查。投影重疊判斷2.P和Q在oxy平面上投影的包圍盒在x方向上不相交3.P和Q在oxy平面上投影的包圍盒在y方向上不相交4.P在Q之后。P的各頂點均在Q的遠離視點的一側(cè)5.Q在P之前。Q的各頂點均在P的靠近視點的一側(cè)說明：（1）上面五項中有一項成立，則P就不遮擋Q。（2）如果上述五項都不成立，則說明Q有部分被P遮擋了。于是要對P，Q兩多邊形在xoy平面的投影進行求交運算，在交點處進行深度比較，判斷出前后順序便可。（3）若遇到多邊形相交或循環(huán)重疊（如圖5-11（f））情況，還需要在相交處分割多邊形，再進行判斷。多邊形的畫家算法的實現(xiàn)：1）對每個多邊形頂點求Zmin。以Zmin為排序關(guān)鍵碼，建立相應(yīng)的深度排序表。表中第一個多邊形是最小的Zmin，記這多邊形為P，同時，設(shè)視點位于Z軸方向的無窮遠處，于是根據(jù)坐標系規(guī)定，P是離視點最遠的多邊形。2）取第二個多邊形為Q。3）檢查Q與P的關(guān)系。如果Zmax(P)<Zmin(Q)，則P不遮擋Q，將P寫入幀緩存。如果滿足上述五個條件之一，則P不遮擋Q，于是P寫入幀緩存。5.3.3Z緩沖算法Z緩沖算法又稱為深度緩沖算法，是一種簡單而且有效的隱藏面消除算法。

Z緩沖算法需要兩張表來存放相應(yīng)的數(shù)據(jù)幀緩存:來存放每個象素的顏色值初值取成z的極小值深度緩存:來存放每個象素的深度值。初值可放對應(yīng)背景顏色的值。算法過程1.Z緩沖器的值與空間一點的z值進行比較，若Z緩沖器的值小，則不變，即Z緩沖器的值不變，幀緩存的值也不變2.若Z緩沖器的值大，則Z緩沖器的值用此z值表示，同時幀緩存的對應(yīng)值用空間點對應(yīng)的多邊形顏色填。3.對顯示對象的每個面上的每個點都做了上述處理后，便可得到消除了隱藏面的圖。Z-Buffer算法（）{ 幀緩存全置為背景色 深度緩存全置為最大Z值

for(每一個多邊形) {掃描轉(zhuǎn)換該多邊形

for(該多邊形所覆蓋的每個象素(x,y)) { 計算該多邊形在該象素的深度值Z(x,y); if(Z(x,y)小于Z緩存在(x,y)的值) {把Z(x,y)存入Z緩存中(x,y)處 把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處} }}}算法優(yōu)點:Z-Buffer算法在象素級上以近物取代遠物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的。這種取代方法實現(xiàn)起來遠比總體排序靈活簡單，有利于硬件實現(xiàn)。缺點：占用空間大，沒有利用圖形的相關(guān)性與連續(xù)性。改進算法：只用一個深度緩存變量zb

Z-Buffer算法需要開一個與圖象大小相等的緩存數(shù)組ZB，實際上，可以改進算法，只用一個深度緩存變量zb。z-Buffer(){ 幀緩存全置為背景色

for(屏幕上的每個象素(i,j)){深度緩存變量zb置最小值MinValue for(多面體上的每個多邊形Pk) { if(象素點(i,j)在pk的投影多邊形之內(nèi)) {

計算Pk在(i,j)處的深度值depth;if(depth小于zb) { zb=depth; indexp=k; } } } If(zb!=MinValue)計算多邊形Pindexp在交點(I,j)處的光照顏色并顯示

}}關(guān)鍵問題：（1）判斷象素點(i,j)是否在pk的投影多邊形之內(nèi)（2）計算多邊形Pk在點（i，j）處的深度。設(shè)多邊形Pk的平面方程為：

（2）深度計算方法：（1）點與多邊形的包含性檢測射線法由被測點P處向y=-方向作射線交點個數(shù)是奇數(shù)，則被測點在多邊形內(nèi)部否則，偶數(shù)，在多邊形外部。(1)在處理當(dāng)前掃描線時，開一個一維數(shù)組作為當(dāng)前掃描線的Z-buffer。首先找出與當(dāng)前掃描線相關(guān)的多邊形，以及每個多邊形中相關(guān)的邊對。(2)對每一個邊對之間的小區(qū)間上的各象素，計算深度，并與Z-buffer中的值比較，找出各象素處可見平面。(3)計算顏色，寫幀緩存。采用增量算法計算深度。5.3.4掃描線Z緩沖算法數(shù)據(jù)結(jié)構(gòu)(1)多邊形Y表：將所有多邊形存在多邊形Y表中。

(2)根據(jù)多邊形頂點中最小的y坐標，插入多邊形Y表中的相應(yīng)位置。(3)多邊形Y表中只保存多邊形的序號和其頂點的最大y坐標。根據(jù)序號可以從定義多邊形的數(shù)據(jù)結(jié)構(gòu)中取多邊形信息待消隱對象

多邊形y表活化多邊形表APT:與當(dāng)前掃描線相交的多邊形。APT是一個動態(tài)的鏈表邊Y表ET:活化多邊形表中的每一個多邊形都有一個邊表ET

多邊形P1的邊表ET活化邊對表AET

在一條掃描線上，同一多邊形的相鄰兩條邊構(gòu)成一個邊對?；罨叡鞟ET中存放當(dāng)前多邊形中與當(dāng)前掃描線相交的各邊對的信息。xl

xlylmaxxr

xryrmaxzlIPza

zb

5.3.5掃描線Z-buffer算法(){ 建多邊形y表；對每一個多邊形根據(jù)頂點最小的y值，將多邊形置入多邊形y表。 活化多邊形表APT，活化邊表AET初始化為空。

For(每條掃描線i，i從小到大) { 1.幀緩存CB置為背景色。

2.深度緩存ZB(一維數(shù)組)置為無窮大。

3.將對應(yīng)掃描線i的，多邊形y表中的多邊形加入到活化多邊形表APT中。

4.對新加入的多邊形，生成其相應(yīng)的邊Y表。

5.對APT中每一個多邊形，若其邊Y表中對應(yīng)掃描線I增加了新的邊，

將新的邊配對，加到活化邊對表AET中。

6.對AET中的每一對邊：

6.1對xl<x<xr

的每一個象素，按增量公式z=z-za計算各點深度depth。

6.2與ZB中的量比較，depth<ZB(I),則令ZB(I)=depth，并計算顏色值，寫幀緩存。

7.刪除APT中，多邊形頂點最大y坐標為I的多邊形，并刪除相應(yīng)的邊。

8.對AET中的每一個邊對，作如下處理：8.1刪除ylmax或ylmax

已等于I的邊。若一邊對中只刪除了其中一邊，需對該多邊形的邊重新配對。8.2用增量公式計算新的xl

、xl

和zl

}}5.3.6區(qū)間掃描線算法基本思想：它是把當(dāng)前掃描線與各多邊形在投影平面的投影的交點進行排序后，使掃描線分為若干子區(qū)間。只要在區(qū)