第5章隱藏線與隱藏面的消除5.1多面體的隱藏線消除

5.2曲面的隱藏線消除

5.3隱藏面的消除

習題5三維計算機圖形學方法中，利用計算機處理立體對象，所使用的表示立體對象的模型稱為立體模型。主要的立體模型有線框結構模型(wireframemodel)、表面模型(surface

model)、實體模型(solidmodel)，此外還有斷層圖像數據的重構、八叉樹描述的分層表示模型等。線框結構模型是將立體對象用輪廓線和小的元素面來描述的，這種對象模型的數據輸入方式簡單，容易操作，可以實現描述的快速性，經常被人們使用。但是由于線框表示會出現錯誤理解(如圖5-1所示，立方體可能有兩種不同的理解)，因此在計算機圖形的生成中，要求避免出現這種情況。對比一下圖5-1(a)和圖5-1(b)、(c)不難發(fā)現，圖(a)把應當遮擋的線也在圖中表現出來了，而圖(b)、(c)中，有些被遮擋的線就在圖中被消除了。因而為了避免多義性，應將被遮擋的線和面消除掉，這樣產生的圖更富有立體感，也更便于使用。圖5-1立體出現的不同理解隱藏線和隱藏面的消除所討論的對象是一個三維圖形，并要求消隱后在二維空間中表示，因此消隱后顯示的圖形將和三維空間到二維空間的投影方式有關。本章討論的消隱算

法都假定投影平面就是xoy平面，投影方向為負z軸方向的垂直投影。如果不是這種情況，可對消隱的對象先作變換，變成這種情況，然后再作消隱計算。此外，本章說明的各種消隱方法都假定構成對象的不同面不能互相貫穿，也不能有循環(huán)遮擋的情況。 5.1多面體的隱藏線消除

5.1.1減少直線求交

設有多個互不相交的多面體，它們的消隱問題和它們的顯示方式有關。討論隱藏線消除問題，總假設它們是用線框結構模型來表示的。在這種方式下多面體用棱來表示，這時隱藏線便是某些不可見的棱或棱的一部分。如果能把各棱上可見和不可見部分的分界點找到，消隱問題也就迎刃而解。這些分界點都是多面體的各棱在oxy平面上投影間的交點。這樣問題就轉化成了在oxy平面上求很多直線的交點的計算。假設消隱對象有N條棱，用兩兩求交的方法求所有交點的復雜度為O(N2)，當N很大時，這個工作量是很可觀的。所以要提高算法的效率，就要減少求交的工作量。實際上交點的個數遠小于O(N2)，這說明有很多棱在oxy平面上的投影相互并不相交，問題在于如何把它們排除在求交的計算之外。

把內法線方向背向視點的面稱為前向面，例如圖5-2中的IJFGH、FABG、HCDI和IDEJ所在的面為前向面，其余為后向面。圖5-2棱間交點只有5個設多邊形F的頂點為v1，v2，…vl，頂點vi坐標為(xi，yi，zi)。頂點的次序要求這樣排列：使觀察者在多面體外沿著v1→v2→…→vl走時，多邊形的內部始終在他的右側。為了確定多邊形的內法線方向，可以計算多邊形在oxy平面上投影的有向面積Sp，計算方法如下：如果Sp≥0，則F所在的面為后向面。在實際計算時，條件Sp≥0可放寬成Sp>－k×Sp，k為適當小的正數。這樣做的目的是為了消除誤差的影響，雖然這樣也可能把某些前向面誤認為后向面，但不會影響顯示結果。

另外一種減少直線求交的方法是用邊界盒排除不相交的線段。把點vi在oxy平面上的投影記成Qi，其坐標為(xi，yi)。直線段Q1Q2(見圖5-3)的邊界盒是一個包含這條直線的、邊平行于坐標軸的最小矩形，這個矩形由以下四個參數來確定：

xmin=min(x1，x2)，ymin=min(y1，y2)

xmax=max(x1，x2)，ymax=max(y1，y2)如果兩個邊界盒的參數為xmini、ymini、xmaxi、ymaxi，i=1，2，當它們滿足

(xmin1>xmax2)或(ymin1>ymax2)

(xmin2>xmax1)或(ymin2>ymax1)

時，這兩個邊界盒不相交，因而原來的兩條邊也不會相交。圖5-3邊的邊界盒上式僅是判斷邊相交的一個充分條件。圖5-3中Q1Q2和Q3Q4雖然不相交，但它們不滿足上式的要求。不過大量的不相交線段是可以用這個方法判斷出來的，所以這個方法在計算機圖形學中常常被采用。此外，邊界盒方法還可以用于判斷兩個多邊形或兩個多面體是否相交。5.1.2凸多面體的隱藏線消除

凸多面體是由若干個平面圍成的物體，這些平面的方程設為

aix+biy+ciz+di=0

(i=1,2,…，n)

平面的法向量n為(ai，bi，ci)或(－ai，－bi，－ci)，即－aix－biy－ciz－di=0也是這些平面的方程。為了方便下面的討論，規(guī)定n的選取滿足下列條件：對物體內一點P0(x0，y0，z0)，使得n·(x0，y0，z0)T＋di>0，這樣規(guī)定的法向量n指向了物體內部。于是，視點與第i個面上一點的連線方向為(li，mi，ni)，則第i個面為自隱藏面的判斷方法是

(ai,bi,ci)×(li,mi,ni)<0

對于任意凸多面體，可先求出所有隱藏面，然后檢查每條邊，若此邊為兩隱藏面的交線，則此邊是隱藏線，用虛線表示或消除。5.1.3凹多面體的隱藏線消除

注意到凹多面體的表面也都是多邊形，因此，一條邊是否為隱藏線的判斷，實質上是這樣一個問題：空間一條線段AB和一個多邊形π，判斷線段是否被多邊形遮擋。如果線段全被遮擋，則是隱藏線；若部分遮擋，則求出隱藏部分。以視點為投影中心，把線段與多邊形頂點投影到投影面上，將各對應投影點連線的方程與線段方程聯(lián)立求解，即可求得線段與多邊形投影的交點。這樣，線段AB與多邊形投影的關系可能有兩種：線段AB與多邊形的任何邊都不相交；線段AB與投影多邊形有交點。下面分別進行討論。

1．線段與多邊形的任何邊都不相交

此時又有兩種可能值，即線段AB與投影多邊形分離或線段AB在投影多邊形之中。前一種情況，線段完全可見；后一種情況，線段完全可見或完全隱藏，可以通過連線線段中點與視點來判斷。若此連線與空間多邊形沒有交點，則線段AB可見；若有交點，則AB被空間多邊形隱藏。

2．線段與投影多邊形有交點

此時投影多邊形的邊把投影線段分割成若干段，如圖5-4所示。圖5-4線段AB被分割成若干段每條線段上所有點具有相同的隱藏性，究竟是隱藏的還是可見的，需要進一步判斷是否落在多邊形投影的內部。這里要判斷線段中點是否落在多邊形的投影內，即判斷平面上

一點是否包含在一個多邊形的投影范圍內。若線段落在多邊形投影之外，則兩者之間不可能有隱藏關系。否則，線段可能被多邊形隱藏?？梢詮木€段中點向視點引射線，僅當此射線也與多邊形相交時，線段才被多邊形隱藏。這種判斷方法用于整條線段投影落在多邊形投影內的隱藏性判斷。根據上述方法，依次把多邊形的邊進行對比便可得到所有隱藏線。 5.2曲面的隱藏線消除

由方程y=f(x,z)表示的曲面經常出現在實際應用和科學計算中。在表示這個曲面的線框式立體圖時，一般用x＝xi=const和z＝zi=const兩簇曲線表示。曲面隱藏線的消除就是對這兩簇曲線進行檢測，判斷曲線哪些部分要被遮擋而隱藏，如圖5-5所示。圖5-5曲面的隱藏線消除在圖5-5中，先討論z＝zi=const的一簇曲線的消隱算法。設zi=z0+ih，i＝1，2,…,n，平面z＝zn是最靠近視點的。從平面z＝zn上的曲線y=f(x,zn)開始，對水平方向每一個像素的對應x坐標值xj，計算yjn=f(xj,zn)。

若yjn>yu(j)，則點(xj，yjn，zn)是可見點，并把yu(j)內容換成yjn;若yjn≤yu(j)，則點(xj，yjn，zn)為不可見，則不改變yu(j)的內容。對z＝zn平面上的曲線完成上述工作后，再對平面z＝zn－1上的曲線重復上述工作，這樣按z值遞減方向一條一條曲線處理過去，就得到一組消隱線簇了。

上述方法對圖5-6的曲面是不適用的。圖5-6(a)中的C點附近的虛線部分應是可見的，但按上述算法卻成了不可見了。圖5-6改進的曲面隱藏線消除為了解決圖5-6(a)中存在的問題，可以采用改進的曲面隱藏線消除技術。方法是另外建立M個單元yl(j)。用它的初值去乘maxf(x,z)或比這更大的數，每次求出

yji=f(xj,zi)，i=n，n－1，…，1，j=1，2，…

值后，若

yji>yu(j)或yji<yl(j)

則(xj，yji，zi)為可見，并按如下條件修改yu(j)或yl(j)的值:

若yji>yu(j)則yu(j)=yji

若yji<yl(j)則yl(j)=yji

若

yji>yu(j)或yji<yl(j)

不成立，則(xj，yji，zi)為不可見，也要修改yu(j)或yl(j)的值。這樣一來就不會出現圖5-6(a)中的錯誤了。如果函數y=f(x,y)是用離散點(xi，yj，zk),i，j，k=1，2，…形式給出的，這時yl(i)、yn(i)的單元個數不是由顯示器在x方向的像素個數確定的，而是根據給定的離散點在x方向的個數確定的?；鞠敕ㄊ怯镁€性插值法所得直線來代替兩個點之間的曲線。如果上述判斷結果為(xj，yji，zi)和(xj+1，yj+1,

i，zi)均為不可見，則認為平面z＝zi上的從x=xj至x=xj+1的一段曲線為不可見。若(xj，yji，zi)和(xj+1，yj+1,i，zi)兩點均為可見，則用這兩點的連線代替原來這兩點之間的曲線，并認為它是可見的。若這兩點有一點可見，如圖5-6(b)中的A點，另一點不可見，如圖5-6(b)中的B點，這時要求出點A(xj，yj,i+1)和點B(xj+1，yj+1,i+1)連線與點C(xj，yji)和D(xj+1，yj+1,i)連線的交點E，AE部分可見，EB為不可見。一般用x=xj和z＝zi兩簇曲線來表示一曲線時常用斜投影。為了得到消隱后的曲面表示，不能對兩簇曲線分別消隱再疊加在一起，如圖5-7所示。

在圖5-7中，會使一些該消隱的線未被消隱，如線段AB和CD，這兩段線段被曲面遮擋應該被消除，但是采用兩簇曲線分別消隱再疊加在一起，使得它們被顯示出來。正確的做法是對兩簇曲線一起做消隱，即處理好平面x=xk上z＝zi－1至z＝zi的一段曲線后，馬上處理平面z＝zi上x=xk－1至x=xk的一段曲線。對這兩簇曲線用公共的yu(i)和yl(j)來消隱，如圖5-8所示。圖5-7對兩簇曲線分別消隱再疊加在一起圖5-8對兩簇曲線一起做消隱

5.3隱藏面的消除

為了讓曲面在圖形顯示器上顯示，需要把對應的曲面上某點在屏幕的位置確定出來，即把曲面點變換成圖像中的點，這個過程就是光柵化過程。由于有些曲面或曲面的一部分會被遮擋住，因此需要解決消除隱藏面的問題。

5.3.1區(qū)域子分算法

區(qū)域子分(warnock)算法是一種所謂分而治之的算法。整個屏幕稱為窗口，區(qū)域子分算法是一個遞歸的四等分過程，每一次把矩形的窗口等分成四個相等的小矩形，分成的矩形也稱為窗口。每一次子分，均要對要顯示的多邊形和窗口的關系作一判斷。這種關系可以有四種，如圖5-9所示。圖5-9多邊形與窗口的關系圖5-9中，(a)分離，是指多邊形在窗口之外；(b)內含，是指多邊形在窗口之內；(c)相交，是指多邊形與窗口部分相交；(d)包圍，是指多邊形把窗口全部包含。

在窗口和每個多邊形的關系確定以后，有些窗口內的圖形便可顯示了。它們屬于下列三種情況之一：

(1)所有多邊形都和窗口分離，這時只要把窗口內所有的像素填上背景顏色即可。

(2)只有一個多邊形和窗口相交，或這個多邊形包含在窗口內，這時先對窗口內每一像素填上背景顏色，再對窗口內多邊形部分用掃描線算法填色。

(3)只有一個多邊形和窗口相交，這個多邊形把窗口整個包圍在內，或雖有幾個多邊形和窗口相交，但離觀察者最近的一個多邊形包圍了整個窗口，這時把整個窗口填上離觀察者最近的那個多邊形的顏色。

對上述三種情況的窗口來說，圖已可以畫出，因而不必再細分了。對上述三種情況不成立的窗口再一分為四，分得的窗口重復上述的處理。窗口的邊長越分越短，分了若干次后，窗口的邊長就和一個像素的寬度基本相等，這時這個窗口對應的像素的顏色可取成最靠近觀察者的多邊形的顏色，或是和這個窗口相交的多邊形顏色的平均值。更有效的處理方法是對所有的多邊形按其頂點的z坐標的最大值(即最靠近觀察者的一個頂點的z坐標值)來排序。對一個具體的窗口來說，隨著窗口不斷地被細分，這個多邊

形序列的元素將越來越少，用邊界盒的方法就可以判斷出一些多邊形和這個窗口是無交點的，并且和這個窗口的子窗口也不會相交，這樣相對這個窗口來說，這些多邊形可從多邊形序列中排除。此外窗口變小了，就可能被一個多邊形包含在內，這個多邊形就會把遠離觀察者的多邊形遮擋，因此對這個窗口來說，這些被遮擋的多邊形可以從序列中去掉。對于不能用邊界盒方法判斷的窗口來說，要經過計算去確定它們之間的關系。這時可以采用前面介紹的與多邊形裁剪快速算法類似的方法去確定多邊形和窗口的邊界是否有交點。

在實現區(qū)域細分法時，在數據結構上可用一棵四叉樹表示，每一個節(jié)點是一個窗口，每一個節(jié)點下有四個子節(jié)點對應于分成的四個子窗口。在編程時可用遞歸子程序方法或用堆棧的方法實現。5.3.2畫家算法

畫家算法是把對象空間方法與圖像空間方法結合在一起來消除隱藏面的方法。其原理是，先把顯示窗口設置成背景色，再把物體各個面按其離視點的遠近進行排序，離視點遠的多邊形平面放在表頭，離視點近的放在表尾，這樣得到一個深度優(yōu)先的表，然后按從表頭到表尾的順序逐個繪制各個面。由于后顯示的面會取代先顯示的面，而后顯示的面離視點更近一些，因此，由遠及近地繪制各個面，就相當于消除了隱藏面。這個方法與畫家作畫的過程類似，故取名為畫家算法。在畫家算法中物體采用邊界表示存儲，數據文件由若干個三元組和若干個四元組組成。三元組表示物體頂點的坐標，四元組表示物體的某個面由哪些頂點構成。圖5-10表示了一個立方體。

在實現畫家算法時，所使用的數據結構包括點記錄(vertex)、面記錄(patch)和排序數組。點記錄由五個域構成，其中，三個域用于存儲點的空間坐標，另外兩個域用于存儲點的投影坐標。面記錄由四個域存放對應的頂點號。排序數組的每一個元素有兩個域，其中一個域存放面與視點的距離，另一個域存放該面的面號。則畫家算法的步驟如下：圖5-10立方體

(1)打開物體的邊界表示數據文件，從鍵盤讀進旋轉角和透視角、物體表面的顏色參數(色彩和飽和度)、光源方向等。

(2)讀進頂點的空間坐標，計算物體的包圍球半徑，把物體縮小到單位球中去，計算物體各頂點在屏幕上的投影坐標。

(3)讀進面定義數據，求出各面與視點的距離，把面號與距離放進排序數組，然后以面與視點的距離為參照值，對數組進行排序。

(4)使終端進入圖形狀態(tài)，初始化設備參數，建立查色表。

(5)從排好序的數組中依次取出一個面號，計算該面的法向量，然后計算該面的光強，最后顯示該面。

畫家算法的優(yōu)點是簡單，容易實現，可以作為實現更復雜算法的基礎。它的缺點是只能處理互不相交的面，而且深度優(yōu)先級表中面的順序可能出錯。

畫家算法的關鍵問題是如何對多邊形進行深度排序。下面給出一種建立深度優(yōu)先級表的方法。

設每個多邊形有一些頂點，這些頂點各有一個z坐標，取其中z坐標最小的記為zmin，取其中z坐標最大的記為zmax，于是每一個多邊形都有自己的zmax和zmin。按zmin的大小把多邊形初步排序。假設zmin最小的多邊形為P，它暫時成為優(yōu)先級最低的一個多邊形。對其他任意一個多邊形Q，研究P與Q的關系：

(1)若zmax(P)<zmin(Q)，則P不會遮擋Q；

(2)若zmax(P)>zmin(Q)而又有zmin(P)<zmin(Q)，則需要作進一步檢查，按下面五種情況進行討論，如圖5-11所示。圖5-11

P與Q的相互關系在圖5-11中，圖(a)～(e)的P與Q是不遮擋的，(f)是相互遮擋的。對于P與Q的五種不遮擋關系，可以采用下述方法進行判別：

①P和Q在xoy平面上投影的包圍盒在x方向上不相交；

②P和Q在xoy平面上投影的包圍盒在y方向上不相交；

③P和Q在xoy平面上投影不相交；

④P的各頂點均在Q的遠離視點的一側；

⑤Q的各頂點均在P的靠近視點的一側。上面五項中有一項成立，則P就不遮擋Q。如果上述五項都不成立，則說明Q有部分被P遮擋了，于是要對P、Q兩多邊形在xoy平面上的投影進行求交運算，在交點處進行深度比較，判斷出前后順序便可。若遇到多邊形相交或循環(huán)重疊(如圖5-11(f)所示)情況，還需要在相交處分割多邊形，再進行判斷。

綜上所述，多邊形的畫家算法的算法步驟如下：

(1)對每個多邊形頂點求zmin。以zmin為排序關鍵碼，建立相應的深度排序表。表中第一個多邊形是最小的zmin，記該多邊形為P，同時，設視點位于z軸方向的無窮遠處，于是根據坐標系規(guī)定，P是離視點最遠的多邊形。

(2)取第二個多邊形為Q。

(3)檢查Q與P的關系。

①如果zmax(P)<zmin(Q)，則P不遮擋Q，將P寫入幀緩存。

②如果滿足上述五個不遮擋條件之一，則P不遮擋Q，于是P寫入幀緩存。

畫家算法原理簡單，其關鍵是如何對場景中的物體按深度排序。當然，排序方法對于互不相交的多邊形是很有效果的，但對于兩個多邊形相交或三個以上的多邊形重疊的情況，它就無能為力了，這時只能把相關的面進行分割后再進行排序。5.3.3

Z緩存算法

在畫家算法中，深度排序計算量大，而且排序后還需檢查相鄰的多邊形，以確保在深度優(yōu)先級表中前者在前，后者在后，若遇到多邊形相交或循環(huán)無序時還必須分割多邊形。

與畫家算法相比，Catual的Z緩存算法則簡單得多。Z緩存算法又稱為深度緩存算法，是一種簡單而且有效的隱藏面消除算法。Z緩存算法需要兩張表來存放相應的數據：一張表叫幀緩存，用來存放對應像素的顏色值；另一張表叫Z緩存，用來存放對應像素的深度值。Z緩存算法的示意圖如圖5-12所示。圖5-12

Z緩存算法的示意圖

Z緩存器是一組存儲單元，其單元個數和屏幕上像素的個數相同，也和幀緩存器的單元個數相同，而且它們之間是一一對應的。Z緩存器中每個單元存放的是對應像素點所反應的對象上點的z坐標值。Z緩存器中每個單元初值設置為z的極小值，而幀緩存中對應單元的初值取為背景色。圖形消隱的過程實際上就是根據Z緩存器的情況，給幀緩存對應單元填充相應的顏色值。具體講，Z緩存器的值與空間一點的z值進行比較，若Z緩存器的值大，則不變，即Z緩存器的值不變，幀緩存的值也不變；若Z緩存器的值小，則Z緩存器的值用此z值表示，同時幀緩存的對應值用空間點對應的多邊形顏色填充。對顯示對象的每個面上的每個點都作了上述處理后，便得到了消除隱藏面后的圖形。Z緩存算法如下：深度緩存算法的優(yōu)點是：

(1)方法簡單，在像素級上由近物代替遠物，從而達到消除隱藏面的要求，對于復雜形狀的景物，也可以實現消隱。

(2)計算量為線性復雜度O(n)，其中n為場景中景物表面采樣點的數目。所以，對于復雜畫面，此方法能較有效地顯示其算法的優(yōu)越性。

(3)由于景物表面上的可見點可按任意次序寫入Z緩存器和幀緩存，因此不必先對多邊形進行深度排序，節(jié)省了畫家算法中的排序時間。

(4)容易推廣至空間的自由曲面。事實上，只需在上述算法中把多邊形面改為自由曲面便可，故對描述一般場景是有效的方法。

(5)由于目前涉及的三維顯示都存在運行速度慢的問題，許多實時顯示需要硬件實現算法來加速，因而能否易于硬件實現也是衡量一個算法的指標之一。Z緩存算法易于硬件實現，所以Z緩存算法已成為計算機圖形學中消除隱藏面的標準方法。

當然，Z緩存算法也有許多缺點，該算法并沒有考慮物體固有的拓撲幾何結構。事實上，物體固有的幾何結構在空間構成一種空間構架，在這構架中有一些面本身不可見，無

需再拿來判斷。因而，Z緩存算法的運算中，隱含著大量不必要的計算。另外，有一些處理相對而言實現不了，如對透明、半透明效果就無法實現。為了解決上述問題，對Z緩存算法進行了一些改進。下面的算法中只使用了一個深度緩存變量zb，節(jié)省了Z緩存的空間。改進的Z緩存算法程序為：當然，上述算法中要求判斷像素點是否在多邊形中間，這個判斷有許多算法，可以見相關書籍。下面介紹的掃描線Z緩存算法，就是利用多邊形的相關性來提高點與多邊形的包含性測試和深度計算速度的。5.3.4掃描線算法

Z緩存算法的優(yōu)點是簡單、可靠，不需要對顯示對象的面預先進行排序，缺點是需要很大的Z緩存器，顯示對象的表面和像素對應的每一個點都要計算它的z值，因而工作量較大。為了克服這個缺點，可把整個平面分成若干區(qū)域，一區(qū)一區(qū)地顯示，這樣Z緩存器的單元數只要等于屏幕上一個區(qū)域的像素個數即可。如果這個區(qū)域取成屏幕上的一行，就

得到了掃描線Z緩存算法。掃描線Z緩存算法的主要思想是：按掃描行的順序處理一幀畫面，在由視點和掃描線所決定的掃描平面上進行消隱處理。具體過程如下：在處理當前掃描線時，定義一個一維數組作為當前掃描線的Z緩存器，找出與當前掃描線相關的多邊形，以及每個多邊形中相關的一對邊，對每個邊進行判斷，找出各像素處的可見多邊形面，計算其顏色并寫入幀緩存中。

掃描線Z緩存算法如下：從上述算法可知，在處理每一條掃描線時，要檢查各多邊形是否和該線相交，還要計算多邊形所在平面上很多點的z值，這都要花費很多時間去計算。為了使這些工作能高效率地進行，可以采用許多優(yōu)化算法，有興趣的讀者可以參考相關資料。5.3.5區(qū)間掃描線算法

掃描線Z緩存算法將消隱問題分散到每一條掃描線上去解決，這使問題變得較簡單。但在每個像素處，計算多邊形z值的工作量仍是很大的。實際上每條掃描線被各多邊形在

xoy平面上的投影分割成為數不多的區(qū)間，每一個區(qū)間只顯示一個面。因此，只要在區(qū)間上任一點處找到在該處z值最大的一個面，這個區(qū)間上的每個像素都可以用這個面的顏色

來顯示。這種方法就是所謂的區(qū)間掃描線算法。

設多邊形的邊界在xoy平面上的投影和掃描線交點的橫坐標為xi，在這些交點處把掃描線分成一個個小區(qū)間［xi，xi+1］，如圖5-13所示。圖5-13［xi，xi+1］稱為區(qū)間在每個區(qū)間上最靠近觀察者的那個面就是這個區(qū)間上的可見面。為了在區(qū)間上找到離視點最近的面，就要去求出各多邊形所在平面在區(qū)間左端點的z值，找到z值最