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

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

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

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

圖5-1立體出現(xiàn)的不同理解真實(shí)感圖形1)常規(guī)視覺上的真實(shí)（區(qū)分可見和不可見面）。2)表面效果的真實(shí)（表達(dá)材質(zhì)、光照、明暗等）。可見和不可見面

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

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

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

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

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

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

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

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

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

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

5.1.1減少直線求交

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

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

(2)按圖形種類進(jìn)行頂點(diǎn)表變換；

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

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

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

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

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

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

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

一般用x＝xi和z＝zi兩簇曲線表示,視點(diǎn)在Z軸方向.設(shè)，,i＝1，2……n，平面z＝zn是最靠近視點(diǎn)，于是平面Z＝zn上曲線都是可見的。而對(duì)于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)消隱，。改進(jìn)的曲面隱藏線消除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多邊形P1的邊表ET活化邊對(duì)表AET

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

xlylmaxxr

xryrmaxzlIPza

zb

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

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

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

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

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

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

將新的邊配對(duì)，加到活化邊對(duì)表AET中。

6.對(duì)AET中的每一對(duì)邊：

6.1對(duì)xl<x<xr

的每一個(gè)象素，按增量公式z=z-za計(jì)算各點(diǎn)深度depth。

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

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

8.對(duì)AET中的每一個(gè)邊對(duì)，作如下處理：8.1刪除ylmax或ylmax

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

、xl

和zl

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