計(jì)算機(jī)圖形學(xué)（第3版）課件：消除隱藏線和隱藏面

2024/12/141計(jì)算機(jī)圖形學(xué)

消除隱藏線和隱藏面的算法第一節(jié)線面比較法消除隱藏線第二節(jié)浮動(dòng)水平線算法第三節(jié)深度排序算法第四節(jié)z-緩沖算法第五節(jié)掃描線算法第六節(jié)區(qū)域分割算法

第七節(jié)BSP樹算法第八節(jié)光線投影算法消隱 面消隱 線消隱三維形體表示為多邊形表面形集合投影約定為沿著z軸正向的投影消除隱藏面算法： 圖像空間算法 客體空間算法圖像空間(屏幕坐標(biāo)系)算法對(duì)顯示設(shè)備上每一個(gè)可分辨像素進(jìn)行判斷，看組成物體的多個(gè)多邊形表面中哪一個(gè)在該像素上可見(jiàn)，即要對(duì)每一像素檢查所有的表面?？腕w空間(觀察坐標(biāo)系)算法把注意力集中在分析要顯示形體各部分之間的關(guān)系上，這種算法對(duì)每一個(gè)組成形體的表面，都要與其它各表面進(jìn)行比較，以便消去不可見(jiàn)的面或面的不可見(jiàn)部分。第一節(jié)線面比較法消除隱藏線

多面體的面可見(jiàn)性

對(duì)象：凸多面體 可見(jiàn)面：朝向觀察位置的面 觀察方向：由指向觀察位置的一個(gè)方向向量k給出， 考查面的外法向量是n，則這兩個(gè)向量的夾角

滿足0

/2時(shí)，所考查面是可見(jiàn)的，否則就是不可見(jiàn)的把n和k記作則面為可見(jiàn)面不可見(jiàn)面退化為線。

設(shè)空間有一個(gè)四面體，頂點(diǎn)A，B，C，D的坐標(biāo)依次是(0,0,0),(2,0,1),(4,0,0),(3,2,1)從z軸正向無(wú)窮遠(yuǎn)處觀察,求各面的可見(jiàn)性 觀察方向向量是k=(0,0,1)=(0,0,1)-(0,0,0),觀察位置(0,0,1),A(0,0,0)是面DAB,ACB上的點(diǎn)。

(0,0,0)(2,0,1)(4,0,0)(3,2,1)(0,0,0)(2,0,1)(4,0,0)(3,2,1)

三角面DAB的法向量是:

因此,n·k=4>0，面DAB為可見(jiàn)面.類似計(jì)算可知，面DBC是可見(jiàn)面,面ADC是不可見(jiàn)面。

(0,0,0)(2,0,1)(4,0,0)(3,2,1)

三角面ACB的法向量是:

因此,n·k=0，面ACB退化為線。

利用外法線就可以判斷凸多面體上各表面的可見(jiàn)性，由此就能解決對(duì)單個(gè)凸多面體的隱藏線和隱藏面的消除問(wèn)題。 單個(gè)凸多面體──可見(jiàn)面上的線是可見(jiàn)線， 多個(gè)凸多面體或非凸多面體──用上面的方法預(yù)處理，排除以后不必考慮的不可見(jiàn)面，剩下可能可見(jiàn)面。 可能可見(jiàn)的棱線:在可見(jiàn)面上或與可見(jiàn)面有公共邊線面比較法：(觀察位置位于Z軸負(fù)方向無(wú)窮遠(yuǎn)處)0.預(yù)處理，用外法線法判斷出所有可能可見(jiàn)面思想：求出所有可能可見(jiàn)面，可能可見(jiàn)面上的線段是可能可見(jiàn)線。每一條可能可見(jiàn)線和每一個(gè)可能可見(jiàn)面比較，從而確定出可見(jiàn)線、隱藏線及可見(jiàn)線上的隱藏部分?！€段↓多邊形表面可能可見(jiàn)線和可能可見(jiàn)面 空間任一線段，只有其投影與多邊形表面的投影范圍發(fā)生交疊時(shí)，才可能與多邊形表面有遮檔關(guān)系一個(gè)多邊形表面的投影范圍1.范圍檢查：最大最小檢驗(yàn)，即通過(guò)比較有關(guān)的最大或最小值來(lái)判定范圍的交疊情形。（xv,yv方向）①求出線段的投影

xmin1,xmax1,ymin1,ymax1②求出多邊形表面的投影范圍（zv平面上包含多邊形投影的最小矩形）

xmin2,xmax2,ymin2,ymax2

③比較投影范圍：在xv方向:若xmax1<=xmin2或xmax2<=xmin1,則無(wú)遮擋關(guān)系在yv方向：若ymax1<=ymin2或ymax2<=ymin1,則無(wú)遮擋關(guān)系2.zv方向粗略的深度檢查。若線段投影的最大z坐標(biāo)zmax1小于多邊形表面投影范圍最小的z坐標(biāo)zmin2，則線段完全在表面前面，不發(fā)生遮擋現(xiàn)象，可以不必再往下做精確的深度檢驗(yàn)。zmax1<=

zmin23.精確的深度檢驗(yàn)已知z1,求z1

在平面的投影點(diǎn)z1’設(shè)平面方程為Ax+By+Cz+D=0直線L1的參數(shù)方程X=x1，Y=y1，Z=z1+t，代入平面方程得：Ax1+By1+C(z1+t)+D=0解得若t≥0,則z1≤z1’，靠近視點(diǎn)可見(jiàn)若t＜0,則z1>z1’，遠(yuǎn)離視點(diǎn)線段P1P2若z1≤z1’且z2≤z2’，則線段不被遮擋若z1≥

z1’且z2≥

z2’

，有可能遮擋需要進(jìn)一步檢查若非以上兩種情況，必然相交，求出交點(diǎn)，交點(diǎn)將原線段分成兩段，分別屬于上面兩種情況4.進(jìn)一步檢查對(duì)平面遮擋了線段的哪些部分做精確計(jì)算求線段投影與多邊形邊框投影的交點(diǎn)設(shè)交點(diǎn)已經(jīng)求出，設(shè)其對(duì)應(yīng)的參數(shù)λ，按從小到大依次排序后是λ1，λ2，…，則這些交點(diǎn)將投影線段分成的各子線段的可見(jiàn)性應(yīng)是可見(jiàn)，不可見(jiàn)交替出現(xiàn)。判斷子線段的可見(jiàn)性：

取子線段上任意一點(diǎn)，若這點(diǎn)在多邊形各邊投影所形成的封閉多邊形內(nèi)，該子線段就不可見(jiàn)，否則就可見(jiàn)。

線面遮擋判斷算法如下：1)視點(diǎn)和線段在給定平面的同側(cè)，線段不被給定平面遮擋。2)線段的投影和平面的投影的包圍盒不相交，線段不被平面遮擋。3)計(jì)算直線與平面是否相交。若無(wú)相交轉(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值。若無(wú)交點(diǎn)，轉(zhuǎn)7）步。5)所求的各交點(diǎn)將線段的投影分成若干段，求出第一段中點(diǎn)。6)若第一段中點(diǎn)在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋，其它段依次交替取值進(jìn)行判斷。7)算法結(jié)束。線面消隱算法(){

坐標(biāo)變換; for(對(duì)每一個(gè)面FACEi的每一條邊EDGEj)將二元組<EDGEj,i>壓入堆棧

while(棧不空){ <EDGEj,i0>=棧頂；

for(i!=i0的每個(gè)面FACEi){ if(EDGEj被FACEi全部遮擋){將EDGEj清空;break;} if(EDGEj被FACEi部分遮擋){

從EDGEj中將被遮擋的部分裁掉; if(EDGEj被分成若干段){

其中的一段作為當(dāng)前段;

將其他段及相應(yīng)的i壓入堆棧; } } } if(EDGEj段不為空)

顯示EDGEj; }}第二節(jié)浮動(dòng)水平線算法

由于曲面方程的這種特定的表示形式,它的消隱繪圖常采用浮動(dòng)水平線算法,并且在圖像空間中實(shí)現(xiàn)。算法的基本思想是,用一系列與坐標(biāo)平面平行的平面(x,y或z為定值)去切割曲面,得到一系列平面曲線,用這些平面曲線表示曲面,把三維問(wèn)題轉(zhuǎn)化為二維問(wèn)題。

假設(shè)它是關(guān)于單自變量x的單值函數(shù),把這些曲線一一投影到z=0平面上,立即可得到一個(gè)消隱算法。首先將z=zi的平行平面按其離觀察點(diǎn)距離的遞增順序排序,然后從離觀察點(diǎn)最近的平面開(kāi)始,求出這一平行平面族交于曲面的剖面曲線,即對(duì)于圖像空間中的每一x值,求出其對(duì)應(yīng)的y值。在相鄰兩個(gè)x值之間,用直線段表示曲線。最后由近及遠(yuǎn),逐條畫出已消去不可見(jiàn)部分的曲線。

算法的實(shí)現(xiàn)相當(dāng)簡(jiǎn)單,只要設(shè)置兩個(gè)長(zhǎng)度等于圖像空間在x方向分辨率的一組數(shù)組即可。一個(gè)為上水平線數(shù)組,用于存儲(chǔ)每一x值處平面曲線所取到的最大y值;一個(gè)為下水平線數(shù)組,用于存儲(chǔ)每一x值處平面曲線所取到的最小y值。

顯然,兩個(gè)數(shù)組中的值記錄了當(dāng)前的水平線位置,每畫出一條新的曲線,就要相應(yīng)修改這兩個(gè)數(shù)組。這兩條浮動(dòng)水平線在z=0平面上形成了三個(gè)帶設(shè)在任意時(shí)刻所畫最后一點(diǎn)為xn,當(dāng)前要畫的點(diǎn)是xn+k,根據(jù)xn和xn+k在三個(gè)帶中的位置,算法可表述為:對(duì)于當(dāng)前平面曲線上的任一給定x值,若其對(duì)應(yīng)的y值均大于先前曲線上同一x對(duì)應(yīng)的最大y值或小于對(duì)應(yīng)的最少y值,則曲線可見(jiàn);否則不可見(jiàn)。若從上一x值(xn)至當(dāng)前x值(xn+k)之間的曲線段變成可見(jiàn)或不可見(jiàn),則求交點(diǎn)(xi)。若從xn至xn+k之間的曲線段全部可見(jiàn),則畫出整個(gè)曲線段;若該曲線段由可見(jiàn)變成不可見(jiàn),則畫出從xn至xi之間的曲線段;若該曲線段由不可見(jiàn)變成可見(jiàn),則畫出從xi至xn+k之間的曲線段。最后,修改上、下水平線數(shù)組。

如果對(duì)于某些x值,相對(duì)應(yīng)的y值不存在,那么上、下水平線數(shù)組的值將無(wú)法確定。這時(shí),需對(duì)已知點(diǎn)做線性插值,以便求得上、下水平線數(shù)組中相應(yīng)元素的值。

算法允許觀察者在任何角度下對(duì)曲面進(jìn)行觀察,并且可以有透視投影和平行投影兩種選擇。為了保證圖形總是自左至右出現(xiàn)在屏幕上,若0°<θ<180°,z按遞減順序變化,同一平面內(nèi),x按遞增順序變化;若180°<θ<360°,z按遞增順序變化,同一平面內(nèi),x按遞減順序變化。第三節(jié)深度排序算法

深度排序算法：先畫最遠(yuǎn)的，再畫最近的（優(yōu)先級(jí)算法，畫家算法）深度排序算法的主要步驟：1.

把所有的多邊形按頂點(diǎn)最大z坐標(biāo)值進(jìn)行排序。（客體空間）(觀察坐標(biāo)系)2.解決當(dāng)多邊形z范圍發(fā)生交疊時(shí)出現(xiàn)的不明確問(wèn)題。3.按最大z坐標(biāo)值逐漸減小的次序，對(duì)每個(gè)多邊形進(jìn)行掃描轉(zhuǎn)換。（圖像空間）(屏幕坐標(biāo)系)

算法的基本思想是按多邊形離開(kāi)觀察位置的距離進(jìn)行排序，然后按照距離減少的次序，把每個(gè)多邊形內(nèi)部點(diǎn)應(yīng)有的像素值送入幀緩存存貯器中。 算法考查多邊形的深度次序是在客體空間中進(jìn)行，圖形顯示時(shí)覆蓋步驟是在圖像空間中實(shí)現(xiàn)，所以可以說(shuō)是一個(gè)客體空間和圖像空間的混合算法。不明確問(wèn)題檢驗(yàn)方法

所有多邊形按頂點(diǎn)最大z坐標(biāo)值排序后得到一個(gè)排序表，設(shè)P是排在表中最后的那個(gè)多邊形。 設(shè)Q是排在P前面并且z坐標(biāo)范圍與其發(fā)生交疊的一個(gè)多邊形，對(duì)Q與P的次序關(guān)系進(jìn)行檢查。z坐標(biāo)范圍發(fā)生交疊的QP次序檢查，可按下列五步進(jìn)行，每個(gè)步驟判斷一種情況。1.多邊形的x坐標(biāo)范圍不相交疊，所以多邊形不相交疊。2.多邊形的y坐標(biāo)范圍不相交疊，所以多邊形不相交疊。3.P整個(gè)在Q遠(yuǎn)離觀察點(diǎn)的一側(cè)。4.Q整個(gè)在P的靠近觀察點(diǎn)的一側(cè)。5.多邊形在z=0平面上的投影本身不相交疊。以上五步中任何一步成立，都可以說(shuō)明當(dāng)前排序正確如果五步檢查都為假，就假定P是遮擋了Q，交換P和Q在排序表中的位置。(QP

PQ)

如果仍做交換，算法會(huì)永遠(yuǎn)循環(huán)下去而沒(méi)有結(jié)果。 為了避免循環(huán)，可以做一個(gè)限制。當(dāng)做過(guò)首次五步檢查后，發(fā)生某個(gè)多邊形被移到排序表的末尾時(shí)，就立即加上一個(gè)標(biāo)記，以后就不能再做移動(dòng)。出現(xiàn)再次應(yīng)該移動(dòng)時(shí)，用一個(gè)多邊形所在的平面，把另一個(gè)多邊形裁剪分為兩個(gè)。PQ第四節(jié)z

緩沖算法

z

緩沖算法:(深度緩沖算法)是一種最簡(jiǎn)單的圖像空間算法。幀緩沖存儲(chǔ)器:存儲(chǔ)各點(diǎn)的像素值，初始化為背景值。z緩沖存儲(chǔ)器:存儲(chǔ)相應(yīng)的z值。初始化最大z值。對(duì)每一個(gè)多邊形，不必進(jìn)行深度排序算法要求的初始排序，立即就可以逐個(gè)進(jìn)行掃描轉(zhuǎn)換。掃描轉(zhuǎn)換時(shí)，對(duì)每個(gè)多邊形內(nèi)部的任意點(diǎn)(x,y),實(shí)施如下步驟：1.計(jì)算在點(diǎn)(x,y)處多邊形的深度值z(mì)(x,y)。2.如果計(jì)算所得的z(x,y)值，小于在z

緩沖存儲(chǔ)器中點(diǎn)

x

y

處記錄的深度值，那么就做：（1）把值z(mì)

x

y

送入z

緩沖存儲(chǔ)器的點(diǎn)(x,y)處。（2）把多邊形在深度z(x

y

處應(yīng)有的像素值，送入幀緩沖存儲(chǔ)器的點(diǎn)

x

y

處。

算法中深度計(jì)算，可通過(guò)多邊形的頂點(diǎn)坐標(biāo)求出所在平面的方程，然后再使用平面方程，對(duì)每個(gè)點(diǎn)

x

y

，解出相應(yīng)的z。對(duì)面方程解出z：設(shè)在點(diǎn)

x

y

處的深度值是z1:則在點(diǎn)(x+Δx,y)處的深度值就是z

緩沖算法的工作流程：幀緩沖區(qū)置成背景色；z緩沖區(qū)置成最大z值；for(各個(gè)多邊形){

掃描轉(zhuǎn)換該多邊形；

for(計(jì)算多邊形所覆蓋的每個(gè)像素(x,y)){

計(jì)算多邊形在該像素的深度值Z(x,y)；

if(Z(x,y)小于Z緩沖區(qū)中的(x,y)處的值) {

把Z(x,y)存入Z緩沖區(qū)中的(x,y)處； 把多邊形在(x,y)處的亮度值存入幀緩存區(qū)的(x,y)處；

} }}第五節(jié)掃描線算法

消除隱藏面的掃描線算法：圖像空間算法圖像的建立是通過(guò)每次處理一條掃描線來(lái)完成的。第二章第三節(jié)多邊形掃描轉(zhuǎn)換算法→推廣

多邊形填充算法：針對(duì)一個(gè)多邊形做掃描轉(zhuǎn)換 掃描線消隱算法：同時(shí)對(duì)多個(gè)多邊形做掃描轉(zhuǎn)換。ET表（邊表）中各登記項(xiàng)按邊的較小的y坐標(biāo)遞增排列；每一登記項(xiàng)下的“吊桶”，按所記x坐標(biāo)遞增排列。ET中吊桶的內(nèi)容：

1.與較小的y坐標(biāo)對(duì)應(yīng)的端點(diǎn)的x坐標(biāo)xmin。

2.邊的另一端點(diǎn)的較大的y坐標(biāo)ymax。

3.x的增量Δx，它實(shí)際上是邊的斜率的倒數(shù)，是從一條掃描線走到下一條掃描線時(shí)，按x方向遞增的步長(zhǎng)。

4.邊所屬多邊形的標(biāo)記。

5.指針指向下一條邊。AET表（活躍邊表）：存儲(chǔ)與當(dāng)前掃描線相交的各邊的信息。PT表（PolygonTable，多邊形表）：記錄多邊形信息，一個(gè)記錄對(duì)應(yīng)一個(gè)多邊形。一個(gè)記錄的內(nèi)容：

1．多邊形所在平面方程的系數(shù)A,B,C,D在需要比較深度時(shí)，要通過(guò)對(duì)所在(x,y)，根據(jù)平面方程解出深度z。2．

每個(gè)多邊形的亮度或顏色值。實(shí)際做掃描轉(zhuǎn)換時(shí)應(yīng)用。3．

一個(gè)“進(jìn)入\退出”標(biāo)志，初值為“假(退出)”。在掃描轉(zhuǎn)換處理時(shí)，用以標(biāo)記掃描線對(duì)該多邊形是“進(jìn)入”，還是“退出”。APT表（活躍多邊形表）：與當(dāng)前掃描線相交的所有多邊形，按深度遞增排序。掃描線y=α:AET表中有AB,AC,

到AB時(shí)，F(xiàn)lagABC=1，AB到AC一段用ABC的顏色填充到AC時(shí)，F(xiàn)lagABC=0，掃描線y=β：

AET表中有四項(xiàng)AB,AC,FD,FEF,

到AB時(shí)，F(xiàn)lagABC=1，AB到AC一段用ABC的顏色填充到AC時(shí)，F(xiàn)lagABC=0，AC到FD之間填充背景色到FD時(shí)，F(xiàn)lagDEF=1，F(xiàn)D到FE之間填充DEF顏色到FE時(shí)，F(xiàn)lagDEF=0掃描線y=γ：

AET表中有四項(xiàng)AB,DE,CB,FE

到AB時(shí)，F(xiàn)lagABC=1，AB到DE之間填A(yù)BC的顏色到DE時(shí)，F(xiàn)lagDEF=1，做深度比較，求（x’,γ）的深度

若ZDEF<ZABC

，則DE到BC之間填DEF的顏色到BC時(shí)，F(xiàn)lagABC=0，BC到EF之間填DEF顏色到EF時(shí)，F(xiàn)lagDEF=0

2024/12/1446Polygonfill(EdgeTableET,COLORREFcolor){1.y=置y為邊表ET中各登記項(xiàng)對(duì)應(yīng)的y坐標(biāo)中最小的值;2.活躍邊表AET初始化為空表;3.若AET非空或ET非空，則做下列步驟，否則算法結(jié)束{3.1.將ET中登記項(xiàng)y對(duì)應(yīng)的各“吊桶”合并到表AET中,將AET中各吊桶按x坐標(biāo)遞增排序；3.2.在掃描線y上，按照AET表提供的x坐標(biāo)對(duì),用color實(shí)施填充；3.3.將AET表中有y=ymax的各項(xiàng)清除出表；3.4.對(duì)AET中留下的各項(xiàng)，分別將x換為x+1/m，求出AET中各邊與下一條掃描線交點(diǎn)的x坐標(biāo)；3.5.y=y＋1，返回步驟3處理下一條掃描線。}}ABCDEF

通過(guò)以上的討論，可以寫出整個(gè)掃描線算法實(shí)施的步驟。 首先正確形成邊表ET和多邊形表PT之后，實(shí)施步驟就與第二章敘述的多邊形填充的掃描線算法的實(shí)施步驟基本相同，只是需要把那里的步驟:在掃描線y上，按照AET表提供的x坐標(biāo)對(duì)，用color實(shí)施填充修改加細(xì)如下：

1.將實(shí)施掃描轉(zhuǎn)換時(shí)遍查AET表中各“吊桶”的指針i初始置為1，掃描線正在多少個(gè)多邊形內(nèi)的累計(jì)數(shù)值s初始置為零，將活動(dòng)多邊形表，即掃描線正在通過(guò)的多邊形按深度遞增次序排列而形成的表，記為p，初始置為空。ABCDEF2.設(shè)第i個(gè)“吊桶”記錄的相應(yīng)多邊形是A。若A的“進(jìn)入/退出”標(biāo)記FA為“假”，則改FA為“真”，將A加到表P的前面，s增加1。否則，F(xiàn)A即為“真”，則改FA為“假”，將P中的A去掉，s減少1。3.若s=0，則到5。（這時(shí)掃描線不在任何多邊形內(nèi)，正通過(guò)背景，不必做掃描轉(zhuǎn)換。）若s=1，則到4（這時(shí)掃描線只在一個(gè)多邊形內(nèi)，不必做深度比較，去做掃描轉(zhuǎn)換。）若前面兩個(gè)判斷都為“假”，掃描線至少在兩個(gè)多邊形內(nèi)，應(yīng)做深度比較。對(duì)表P前面兩個(gè)多邊形做深度比較，比較后放回應(yīng)保證P表中的多邊形按深度遞增的次序。4.對(duì)第i個(gè)和第i+1個(gè)“吊桶”存有的x坐標(biāo)指示的掃描線上的一段，按照P表最前面多邊形指示的亮度或顏色，實(shí)施掃描轉(zhuǎn)換。5.i增加1，若i所指已無(wú)“吊桶”，步驟結(jié)束，去下一步驟（刪除y=ymax的邊）。否則，回到步驟2。

ABCDEF兩個(gè)多邊形建立的“吊桶”已排序的邊表

ABCDEF兩個(gè)多邊形在zv=0平面上的投影

設(shè)有兩個(gè)空間的三角形ABC、DEF,各頂點(diǎn)的坐標(biāo)依次是A(1,1,10),B(2,5,10),C(5,3,10),D(3,4,5),E(4,6,5),F(6,2,5)。

ABCDEFisPPT表說(shuō)明FABCFDEF11(ABC)true1?到3填A(yù)BC的亮度或顏色值22(DEF,ABC)true在步驟3.2.3發(fā)生深度比較，比較結(jié)果DEF更靠近觀察者，它仍在P表前面，3到3?填DEF的亮度或顏色值31(DEF)false3?到5填DEF的亮度或顏色值40()falseABCDEF

如果按照步驟3的條件決定是否做深度比較，會(huì)有許多深度比較是不必要的。例如，假定有一個(gè)大的多邊形GHIJ在兩個(gè)三角形ABC和DEF的后面。在掃描線y=γ離開(kāi)邊CB時(shí)，按步驟3的條件判斷，掃描線還同時(shí)在DEF和GHIJ中，應(yīng)該做深度比較，但是在大多數(shù)可以假定沒(méi)有多邊形穿透另一個(gè)多邊形的情況下，DEF和GHIJ的深度關(guān)系并沒(méi)有變化，深度比較是不必要的。如果掃描線從一個(gè)被遮擋的多邊形中走出，深度比較將是不必要的；掃描線從一個(gè)遮擋了其它多邊形的多邊形中走出，深度比較才可能必要。

事實(shí)上前面給出的算法基本步驟沒(méi)有很好地利用深度的相關(guān)性。深度相關(guān)性是指多個(gè)多邊形之間的深度關(guān)系，常常對(duì)于一組相鄰的掃描線來(lái)說(shuō)是不變化的。如果在某條掃描線上，在AET表中保存的邊及次序關(guān)系，與在前面一條掃描線上時(shí)完全相同，那么深度關(guān)系就不會(huì)變化，深度比較也就并不必要了。例如，圖7.21中的掃描線γ到γ+1就是這種情形，在兩條掃描線上AET表中的邊及次序關(guān)系都是AB，DE，CB，F(xiàn)E。但從γ+1到γ+2，DE，CB的次序要變化為CB，DE，次序關(guān)系就變化了。利用深度的相關(guān)性可以對(duì)算法作出改進(jìn)。

上圖所示是一個(gè)多邊形穿透了另一個(gè)多邊形。為使算法能處理這種情況，應(yīng)該把其中的多邊形KLM分成兩個(gè)多邊形KLL’M’和L’MM’，加進(jìn)了一條沒(méi)有的邊M’L’。

關(guān)于背景的處理，1、把更新緩沖存儲(chǔ)器整個(gè)初始化為某個(gè)合適的值，于是算法就只需處理掃描線在多邊形內(nèi)的情形。2、定義一個(gè)大的矩形，讓它包含了客體中所有的多邊形，位于比其它多邊形都更遠(yuǎn)離觀察者的平行于投影平面的一個(gè)平面上，并具有某個(gè)合適的亮度或顏色值。3、修改算法，使得掃描線不在任何多邊形內(nèi)時(shí)，就往幀緩沖存儲(chǔ)器中送入背景的像素值。3.2.3深度比較條件太寬松，實(shí)際很多不必要的的比較改進(jìn)1：假定沒(méi)有多邊形穿透另一個(gè)多邊形的情況下，如果掃描線從一個(gè)被遮擋的多邊形中走出，深度比較將是不必要的；掃描線從一個(gè)遮擋了其它多邊形的多邊形中走出，深度比較才可能必要。改進(jìn)2：利用深度相關(guān)性，對(duì)于一組相鄰的掃描線來(lái)說(shuō)，次序關(guān)系不發(fā)生變化，多邊形之間的深度關(guān)系不發(fā)生變化的。改進(jìn)3：對(duì)于穿透情況的處理，將一個(gè)多邊形分成兩個(gè)子多邊形改進(jìn)4：背景顏色處理（1）幀緩存初始為某個(gè)特定的值（2）定義一個(gè)包含了客體中所有的多邊形，位于比其它多邊形都更遠(yuǎn)離觀察者的平行于投影平面的一個(gè)平面上，并具有某個(gè)合適的亮度或顏色值。

（3）修改算法。當(dāng)掃描線不在任何多邊形內(nèi)時(shí)，就往幀緩沖存儲(chǔ)器中送入背景的像素值。

第六節(jié)區(qū)域分割算法

區(qū)域分割算法：

將投影平面分割成區(qū)域，考察區(qū)域內(nèi)的圖像。

1.如果容易決定在這個(gè)區(qū)域內(nèi)某些多邊形是可見(jiàn)的，顯示那些可見(jiàn)的多邊形，完成對(duì)這一區(qū)域的顯示任務(wù)。否則，將區(qū)域再分割成小的區(qū)域，對(duì)小的區(qū)域遞歸地進(jìn)行判斷。

2.由于區(qū)域逐漸變小，在每個(gè)區(qū)域內(nèi)的多邊形逐漸變小，最終總可以判定哪些多邊形是可見(jiàn)的。 該算法利用了區(qū)域的相關(guān)性，即位于適當(dāng)大小的區(qū)域內(nèi)的所有像素，表示的其實(shí)是同一個(gè)表面。 區(qū)域分割算法：圖像空間算法區(qū)域的相關(guān)性:是指位于適當(dāng)大小的區(qū)域內(nèi)的所有像素，表示的其實(shí)是同一個(gè)表面。在遞歸分割的每一步，要顯示客體中每個(gè)多邊形的投影多邊形與所考察區(qū)域之間的關(guān)系，必然是下列四種之一：1.包圍的多邊形，即多邊形包圍了所考察的區(qū)域。2.相交的多邊形，即多邊形所考察的區(qū)域相交。3.被包含的多邊形，即多邊形全部在所考察的區(qū)域之內(nèi)。4.分離的多邊形，即多邊形與所考察的區(qū)域完全分離。

包圍的相交的被包含的分離的

包圍的相交的被包含的分離的

若區(qū)域與多邊形為下面的四種情況，不必再做進(jìn)一步的分割，可直接繪制。

1．所有的多邊形與區(qū)域分離，所以在區(qū)域內(nèi)只需顯示背景值。

2．只有一個(gè)相交的多邊形，或者只有一個(gè)被包含的多邊形。這時(shí)可以對(duì)區(qū)域首先填充背景值，然后對(duì)多邊形進(jìn)行掃描轉(zhuǎn)換。在某些顯示設(shè)備上，將整個(gè)幀緩沖存儲(chǔ)器都初始化為背景值，可能更為方便。對(duì)于相交的多邊形，只是被包含的部分被掃描轉(zhuǎn)換。

3．只有一個(gè)包圍的多邊形，無(wú)其它的多邊形。整個(gè)區(qū)域填充該多邊形的像素值。

包圍的相交的被包含的分離的 4．有多于一個(gè)的包圍的、相交的或被包圍的多邊形，且至少有一個(gè)包圍的多邊形。檢查是否能有一個(gè)包圍的多邊形，它位于所有其它多邊形的前面。如果有，就可以讓整個(gè)區(qū)域都填充為這個(gè)多邊形的像素值。具體的檢查方法是，對(duì)所有的多邊形，計(jì)算其所在平面在區(qū)域的四個(gè)角點(diǎn)的應(yīng)有深度，即相應(yīng)的z坐標(biāo)，如果有一個(gè)包圍的多邊形對(duì)應(yīng)的四個(gè)z坐標(biāo)，都小于其它多邊形的對(duì)應(yīng)z坐標(biāo)，那么這個(gè)包圍的多邊形就位于所有其它多邊形的前面。

包圍的相交的被包含的分離的若區(qū)域與多邊形為下面的四種情況，不必再做進(jìn)一步的分割，可直接繪制：1．所有的多邊形與區(qū)域分離，所以在區(qū)域內(nèi)只需顯示背景值。2．只有一個(gè)相交的多邊形，或者只有一個(gè)被包含的多邊形。這時(shí)可以對(duì)區(qū)域首先填充背景值，然后對(duì)多邊形進(jìn)行掃描轉(zhuǎn)換。（相交的多邊形，只對(duì)被包含的部分做掃描轉(zhuǎn)換）3．只有一個(gè)包圍的多邊形，無(wú)其它的多邊形。整個(gè)區(qū)域填充該多邊形的像素值。（1,2,3用范圍檢查）多個(gè)多邊形與之相交、包圍、或被包含，且有一個(gè)包圍的多邊形位于其它多邊形最前面，區(qū)域填充為該多邊形的顏色。（深度檢查）

區(qū)域經(jīng)過(guò)分割變小以后，只需要考慮被包含的多邊形和相交的多邊形的變化。 因?yàn)榉蛛x的或包圍的多邊形，對(duì)變小的區(qū)域，仍然保持是分離的或包圍的。分割達(dá)到顯示設(shè)備的分辨能力之后就可以停止，即最小的區(qū)域可以是顯示表面上的一個(gè)像素單位。如果在做了最大數(shù)目的分割之后，仍然不能確定該如何填充，那么，就計(jì)算所有相關(guān)的多邊形在這個(gè)不可再分區(qū)域?qū)?yīng)點(diǎn)的范圍的中心z坐標(biāo)值，取z坐標(biāo)最小的多邊形像素值填充這個(gè)區(qū)域。

包圍的相交的被包含的分離的（4）（2）（3）（1）如何判斷包圍的多邊形位于其它多邊形最前面：1.對(duì)所有的多邊形，計(jì)算其所在平面在區(qū)域的四個(gè)角點(diǎn)的應(yīng)有深度，即相應(yīng)的z坐標(biāo)，如果有一個(gè)包圍的多邊形的對(duì)應(yīng)四個(gè)z坐標(biāo)，都小于其它多邊形的對(duì)應(yīng)z坐標(biāo)，那么這個(gè)包圍的多邊形就位于所有其它多邊形的前面。2.判別相交的多邊形是否在整個(gè)包圍多邊形的后面，將相交多邊形的頂點(diǎn)坐標(biāo)代入包圍多邊形的平面方程，判別符號(hào)。

區(qū)域分割成子區(qū)域：

1.子區(qū)域需考察的情況：只需考慮父區(qū)域被包含的或相交的多邊形。對(duì)于分離的或包圍的多邊形，進(jìn)行區(qū)域分割之后仍保持分離包圍的關(guān)系。

2.分割中止的條件：一個(gè)像素單位或最大數(shù)目的分割對(duì)于仍不能判斷的，則找出中心點(diǎn)，計(jì)算中心點(diǎn)對(duì)應(yīng)的所有多邊形的z值，取z值最小的多邊形像素值來(lái)填充該區(qū)域。

3.分割方法（1）等分（2）按多邊形頂點(diǎn)做分割（3）按多邊形投影進(jìn)行分割 Wanock首先提出的最初的區(qū)域分割算法是每次把區(qū)域分成四個(gè)正方形。 下圖做了5次區(qū)域分割的情形，其中區(qū)域內(nèi)標(biāo)出的數(shù)字，表示前面所說(shuō)的四種情形中的哪一種，可以作出決定。沒(méi)有標(biāo)出數(shù)字的區(qū)域是還不能做出決定。（1）等分：分割區(qū)域?yàn)檎叫?/p>

1．所有的多邊形與區(qū)域分離。2．只有一個(gè)相交的多邊形，或者只有一個(gè)被包含的多邊形。3．只有一個(gè)包圍的多邊形，無(wú)其它的多邊形。4．多個(gè)多邊形與之相交、包圍、或被包含，且有一個(gè)包圍的多邊形位于其它多邊形最前面（2）按照頂點(diǎn)位置來(lái)做分割(先A后B)區(qū)域分割不一定總是等分，當(dāng)區(qū)域內(nèi)有多邊形的頂點(diǎn)時(shí)，可以按照頂點(diǎn)位置來(lái)做分割，這樣可以少做一些分割。

圍繞多邊形頂點(diǎn)分割（先是A，后是B）

1．所有的多邊形與區(qū)域分離。2．只有一個(gè)相交的多邊形，或者只有一個(gè)被包含的多邊形。3．只有一個(gè)包圍的多邊形，無(wú)其它的多邊形。4．多個(gè)多邊形與之相交、包圍、或被包含，且有一個(gè)包圍的多邊形位于其它多邊形最前面（3）按照多邊形投影選擇區(qū)域做分割 區(qū)域分割還可以按照客體中多邊形投影的范圍進(jìn)行，這可以少做很多分割。

Weiler和Atherton提出的算法，直接就用多邊形的投影做為分割的區(qū)域。選擇用做分割的區(qū)域時(shí)，可以按照多邊形各頂點(diǎn)坐標(biāo)最小值的遞增次序按照多邊形投影選擇區(qū)域做分割

（3）按照多邊形投影選擇區(qū)域做分割 按深度進(jìn)行預(yù)排序。 用距視點(diǎn)最近的多邊形對(duì)所有多邊形進(jìn)行裁剪和區(qū)域分類。 刪去位于離視點(diǎn)最近的多邊形之后的其他多邊形。 必要時(shí)遞歸地進(jìn)行分割。 最后用深度排序消除所有不確定性。按照多邊形投影選擇區(qū)域做分割

第七節(jié)BSP樹算法

二叉空間剖分(BinarySpace-Partitioning,BSP)樹算法是一種判別物體可見(jiàn)性的有效算法。它類似于深度排序算法,將表面由后往前地在屏幕上繪出。該算法特別適用于場(chǎng)景中位置固定不變,僅視點(diǎn)移動(dòng)的情況。一、構(gòu)造BSP樹BSP樹取場(chǎng)景中的一個(gè)多邊形作為分割面,遞歸地將空間分為兩個(gè)子空間。場(chǎng)景中的其他多邊形中,完全位于剖分平面某一側(cè)的多邊形被歸入相應(yīng)的子空間,與剖分面相交的多邊形沿剖分面被分割成兩部分,分別放入相應(yīng)的子空間。這兩個(gè)子空間再分別選一個(gè)多邊形作分割面遞歸地子分下去,直到每個(gè)子空間只剩一個(gè)多邊形為止。上述劃分過(guò)程可用二叉樹方便地表示出來(lái),二叉樹的根為最初被選作分割面的多邊形。BSP樹的構(gòu)造在景物空間內(nèi)完成。為簡(jiǎn)單起見(jiàn),這里假設(shè)每個(gè)多邊形和分割面都垂直于紙面。先取多邊形1作為分割面,分割面與多邊形2相交,將其分為多邊形2a和2b,多邊形2a和3在分割面的前面,多邊形2b、4和5在分割面的后面,見(jiàn)圖7-27中BSP樹生成的中間過(guò)程。然后從“樹”枝中選取多邊形3作為分割面,其“前”枝子空間包含多邊形2a,“后”枝子空間為空。至此,樹的這一分枝分割完畢,返回到根,處理樹的“后”枝。取多邊形5作為分割面,分割后,多邊形4歸入其前枝,多邊形2b歸入其后枝。因?yàn)槊恳蛔涌臻g都僅包含了一個(gè)多邊形,故這個(gè)分枝也分割完畢。實(shí)際上,多邊形4和多邊形5是共面的,在這種情況下,可放入任一分枝。因?yàn)槌跏挤指蠲婧秃竺婷恳蛔涌臻g的分割面的選取是任意的,表示同一場(chǎng)景的BSP樹并不唯一。二、BSP樹遍歷BSP樹算法的一個(gè)明顯優(yōu)勢(shì)在于BSP樹不依賴于視點(diǎn)的位置,其顯示算法在圖像空間執(zhí)行。依據(jù)BSP樹確定可見(jiàn)面時(shí),僅需知道視點(diǎn)與樹的根結(jié)點(diǎn)多