計(jì)算機(jī)圖形學(xué)：第七章 消除隱藏線和隱藏面

1、第七章 消除隱藏線和隱藏 面的算法 消隱 面消隱 線消隱三維形體表示為多邊形表面集合投影約定為沿著z軸正向的正交投影消除隱藏面算法： 圖象空間算法 客體空間算法 圖象空間算法對顯示設(shè)備上每一個(gè)可分辨象素進(jìn)行判斷，看組成物體的多個(gè)多邊形表面中哪一個(gè)在該象素上可見，即要對每一象素檢查所有的表面?？腕w空間算法把注意力集中在分析要顯示形體各部分之間的關(guān)系上，這種算法對每一個(gè)組成形體的表面，都要與其它各表面進(jìn)行比較，以便消去不可見的面或面的不可見部分。第一節(jié) 線面比較法消除隱藏線 多面體的面可見性 凸多面體的可見面就是朝向觀察位置的面 設(shè)觀察方向由指向觀察位置的一個(gè)方向向量k給出，所考查的面的外法向量是

2、n，則這兩個(gè)向量的夾角 滿足0 /2時(shí)，所考查面是可見的，否則就是不可見的 把n和k記作 則分子 為正 ，則 ,面為可見；若為負(fù)，則 ，面為不可見；若為零，則 ，此面退化為線。 設(shè)空間有一個(gè)四面體，頂點(diǎn)A，B，C，D的坐標(biāo)依次是（0,0,0）,（2,0,1）,（4,0,0）,(3,2,1),沿z軸正向觀察,求各面的可見性 觀察方向向量是k=(0,0,1),三角面DAB的法向量是: 因此, , 面DAB為可見面.類似計(jì)算可知，面DBC是可見面,面ADC是不可見面,面ACB退化為線。 利用外法線就可以判斷凸多面體上各表面的可見性，由此就能解決對單個(gè)凸多面體的隱藏線和隱藏面的消除問題。 消除隱藏線的

3、線面比較法的最先一步就是利用外法線判斷出所有可能的可見面，可能可見面上的線段是可能可見線。要依次用每一條可能可見線，與每一個(gè)可能可見面比較，從而確定出可見線、隱藏線及可見線上的隱藏部分。 可能可見線和可能可見面 空間任一線段，只有其投影與多邊形表面的投影范圍發(fā)生交迭時(shí)，才可能與多邊形表面有遮檔關(guān)系 一個(gè)多邊形表面的投影范圍 范圍檢查也稱為最大最小檢驗(yàn)，即通過比較有關(guān)的最大或最小值來判定范圍的交迭情形。 按Xv方向?qū)ν队胺秶臋z查，可分別計(jì)算出投影線段和多邊形表面投影范圍X坐標(biāo)的最大值和最小值，設(shè)分別是 于是若 或者 ,線段和多邊形表面就必然沒有遮擋關(guān)系。 顯然按xv方向或按yv方向都可以類似地

4、做范圍檢查，這時(shí)可避免消除隱藏面時(shí)很多不必要的深度比較。 zv方向的范圍檢查是沿zv方向觀察時(shí)粗略的深度檢驗(yàn)。 在此范圍檢查中若線段投影的最大z坐標(biāo) 小于多邊形表面投影范圍最小的z坐標(biāo) ，則線段完全在表面前面，根本不發(fā)生遮擋現(xiàn)象，可以不必再往下做精確的深度檢驗(yàn)。 精確深度檢驗(yàn) l2 線段不會(huì)被遮擋; 線段有可能被遮擋; 求交點(diǎn) 直線L1的參數(shù)方程可寫成X=x1，Y=y1，Z=z1+t，代入平面方程得： 若t0,則Z1 ，若t0 Z1 。 需要檢查出某一段子線段是否可見。為此可以取子線段上任意一點(diǎn)，若這點(diǎn)在多邊形表面各邊線的投影所形成的封閉多邊形內(nèi)，這子線段就不可見，否則就可見。 空間一條線段可

5、能被一個(gè)多邊形表面遮擋的消除隱藏線的算法的步驟如下： 做xv方向和yv方向的范圍檢查；若不能判定，則接著做zv方向的范圍檢查即粗略的深度比較；若還不能判定就再進(jìn)行精確的深度比較，比較時(shí)應(yīng)計(jì)算線段兩端點(diǎn)在可能遮擋它的平面上的投影點(diǎn)，比較相應(yīng)的坐標(biāo)。這時(shí)可能出現(xiàn)線段與平面相交需要用交點(diǎn)，這些交點(diǎn)把線段的投影分成兩部分考慮的情況。判定得知線段確實(shí)被平面遮擋了哪些部分做精確計(jì)算，計(jì)算是求出線段的投影與遮擋平面上多邊形表面邊框投影的所有交點(diǎn)，這些交點(diǎn)把線段的投影分成可見和不可見的一些子線段。對子線段的可見性，先取上面一點(diǎn)做點(diǎn)的包含性檢驗(yàn)來進(jìn)行判斷。 線面消隱算法（） 坐標(biāo)變換； for (對每一個(gè)面FA

6、CEi的每一條邊EDGEj)將二元組壓入堆棧； while(棧不空) =棧頂； 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)水平線算法 若存在M個(gè)象素，則建立M個(gè)內(nèi)存單元 ，稱之為上浮水平線數(shù)組，在這些單元中先放上初值，初值應(yīng)取成小于 。曲面方程設(shè) 平面 是最靠近觀察者的，從平面上 的曲線

7、 水平方向每個(gè)象素的對應(yīng)xj坐標(biāo)值，計(jì)算 若 ，則點(diǎn) 是可見點(diǎn)，并把 內(nèi)容變成 。若 ，則 為不可見，則不改變 的內(nèi)容。 上圖c點(diǎn)附近的虛線部分應(yīng)是可見的，但按上述算法卻成了不可見了。為了解決這個(gè)問題，可另建立M個(gè)單元 ，可稱之為下浮水平線數(shù)組。 初值取成 或比這更大一點(diǎn)得數(shù)，每次求出 If thenIf then 如果函數(shù) 是用離散點(diǎn)形式 給出，則可如下處理。這時(shí)的 單元個(gè)數(shù)不是由顯示器在x方向的象素個(gè)數(shù)來定，而是根據(jù)給定的離散點(diǎn)在x方向的個(gè)數(shù)來定。 基本想法是用線性插值法所得直線來代替兩個(gè)點(diǎn)之間的曲線。若上述判斷結(jié)果為 均為不可見，則認(rèn)為平面 上的從 的一段曲線為不可見。若兩點(diǎn)均為可見，則

8、用這兩點(diǎn)的連線代替原來這兩點(diǎn)之間的曲線，并認(rèn)為可見的，若這兩點(diǎn)中有一點(diǎn)可見，如圖的A點(diǎn)，另一點(diǎn)則為不可見，如圖中的B點(diǎn)，這時(shí)要求出點(diǎn)連線的交點(diǎn)E。AE部分為可見，EB為不可見。ABCDEZi+1Zi 一般用 兩族曲線來表示一曲面時(shí)常用斜投影。 為了得到消隱后曲面表示，不能對兩族曲線分別消隱在疊加在一起，正確的做法是對兩族曲線一起做，即處理好平面 一段曲線后，馬上處理平面 的一段曲線。對這兩族曲線用公共的 X=XkZ=ZiB第三節(jié) 深度排序算法 深度排序算法的主要步驟：1.把所有的多邊形按頂點(diǎn)最大z坐標(biāo)值進(jìn) 行排序。2. 解決當(dāng)多邊形z范圍發(fā)生交迭時(shí)出現(xiàn)不 明確問題。3. 按最大z坐標(biāo)值逐漸減小

9、的次序，對每 個(gè)多邊形進(jìn)行掃描轉(zhuǎn)換。 算法的基本思想是按多邊形離開觀察位置的距離進(jìn)行排序，然后按照距離減少的次序，把每個(gè)多邊形內(nèi)部點(diǎn)應(yīng)有的象素值送入幀緩存存貯器中。 算法考查多邊形的深度次序是在客體空間中進(jìn)行，圖形顯示時(shí)覆蓋步驟是在圖象空間中實(shí)現(xiàn)，所以可以說是一個(gè)客體空間和圖象空間的混合算法。不明確問題檢驗(yàn)方法 所有多邊形按頂點(diǎn)最大z坐標(biāo)值排序后得到一個(gè)排序表，設(shè)P是排在表中最后的那個(gè)多邊形。 設(shè)Q是排在P前面并且z坐標(biāo)范圍與其發(fā)生交迭的一個(gè)多邊形，對Q與P的次序關(guān)系進(jìn)行檢查。 檢查可以按下面列出的五個(gè)步驟進(jìn)行，每個(gè)步驟判斷一種情況。 1多邊形的x坐標(biāo)范圍不相交迭，所以多 邊形不相交迭。2多邊

10、形的y坐標(biāo)范圍不相交迭，所以多 邊形不相交迭。3. P整個(gè)在Q遠(yuǎn)離觀察點(diǎn)的一側(cè)。4. Q整個(gè)在P的靠近觀察點(diǎn)的一側(cè)。5. 多邊形在z=0平面上的投影本身不相交 迭。 如果所有這五步檢查都為假，就假定P是遮擋了Q，交換P和Q在排序表中的位置。 如果仍做交換，算法會(huì)永遠(yuǎn)循環(huán)下去而沒有結(jié)果。 為了避免循環(huán)，可以做一個(gè)限制。當(dāng)做過首次五步檢查后，發(fā)生某個(gè)多邊形被移到排序表的末尾時(shí)，就立即加上一個(gè)標(biāo)記，以后就不能再做移動(dòng)。出現(xiàn)再次應(yīng)該移動(dòng)時(shí)，用一個(gè)多邊形所在的平面，把另一個(gè)多邊形剪裁分為兩個(gè)。PQ第四節(jié) 畫家算法 畫家算法又稱深度優(yōu)先級表法，它是深度排序算法的一種具體實(shí)現(xiàn)。 先畫遠(yuǎn)景，再畫中景，最后畫近

11、景。 81 0 01 1 01 1 11 0 10 0 00 1 00 1 10 0 161 2 3 42 6 7 36 5 8 75 1 4 84 3 7 85 6 2 1 邊界表示 三元組表示物體頂點(diǎn)的坐標(biāo)。 四元組表示物體的某個(gè)面由哪些頂點(diǎn)構(gòu)成，每個(gè)面頂點(diǎn)個(gè)數(shù)都是4個(gè)。 程序中所使用的數(shù)據(jù)結(jié)構(gòu)包括點(diǎn)記錄（vertex）、面記錄（patch）和排序數(shù)組。點(diǎn)記錄由五個(gè)域構(gòu)成。其中，三個(gè)域用于存儲點(diǎn)的空間坐標(biāo)，另外兩個(gè)域用于存儲點(diǎn)的投影（屏幕）坐標(biāo)。面記錄由四個(gè)域組成，每個(gè)域存放對應(yīng)的頂點(diǎn)號。排序數(shù)組的每個(gè)元素有兩個(gè)域，其中一個(gè)域存放面與視點(diǎn)的距離，另一個(gè)域存放該面的面號。 Readkeybo

12、ard：打開物體的邊界表示數(shù)據(jù)文件，從鍵盤讀進(jìn)旋轉(zhuǎn)角和透視角，物體表面的顏色參數(shù)（色彩和飽和度），光源方向。Vertices：讀進(jìn)頂點(diǎn)的空間坐標(biāo)，計(jì)算物體的包圍球半徑，把物體縮小到單位球中去，計(jì)算物體各頂點(diǎn)在屏幕上的投影坐標(biāo)。 開始Patches：讀進(jìn)面定義數(shù)據(jù)，求出各面與視點(diǎn)的距離，把面號與距離放進(jìn)排序數(shù)組。然后以面與視點(diǎn)的距離為參照值，對數(shù)組進(jìn)行排序。 Gmode：使終端進(jìn)入圖形狀態(tài)，設(shè)備參數(shù)初始化Setpen：建立查色表 Painting：從排好序的數(shù)組中依次取出一面號，計(jì)算對應(yīng)面的法向量，再計(jì)算該面的光強(qiáng)，然后顯示該面。 Amode：終端返回文字狀態(tài)。 結(jié)束第五節(jié) z緩沖算法 z緩沖算

13、法(深度緩沖算法)是一種最簡單的圖象空間算法。對每一個(gè)點(diǎn)，這個(gè)算法不僅需要有一個(gè)更新緩沖器存儲各點(diǎn)的象素值，而且還需要有一個(gè)z緩沖存儲器存儲相應(yīng)的z值。更新緩沖存儲器初始化為背景值，z緩沖存儲器初始化為可以表示的最大z值。對每一個(gè)多邊形，不必進(jìn)行深度排序算法要求的初始排序，立即就可以逐個(gè)進(jìn)行掃描轉(zhuǎn)換。 掃描轉(zhuǎn)換時(shí),對每個(gè)多邊形內(nèi)部的任意點(diǎn)(x,y),實(shí)施如下步驟： 1 計(jì)算在點(diǎn)(x,y)處多邊形的深度值Z(x,y)。 2如果計(jì)算所得的Z(x,y)值，小于在z緩 沖存儲器中點(diǎn)xy處記錄的深度值， 那么就做： （1）把值Z(x,y)送入z緩沖存儲器的點(diǎn)x,y 處。 （2）把多邊形在深度Z(x,y)

14、處應(yīng)有的象素 值，送入更新緩沖存儲器的點(diǎn)x,y處。 算法中深度計(jì)算，可通過多邊形的頂點(diǎn)坐標(biāo)求出所在平面的方程，然后再使用平面方程，對每個(gè)點(diǎn)xy，解出相應(yīng)的z。 對面方程 解出z是： 則在點(diǎn)（x+x,y）處的深度值就是設(shè)在點(diǎn)（x,y）處的深度值是z1: 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ū)的

15、 (x,y)處； 第六節(jié) 掃描線算法 掃描線算法是圖象空間算法，它建立圖象是通過每次處理一條掃描線來完成的。這個(gè)算法是第二章討論的多邊形填充的掃描線算法的推廣。在多邊形填充的掃描線算法中，只是對一個(gè)多邊形做掃描轉(zhuǎn)換，而這里是同時(shí)對多個(gè)多邊形做掃描轉(zhuǎn)換。 要建立一個(gè)邊表ET。ET中各登記項(xiàng)按邊的較小的y坐標(biāo)遞增排列；每一登記項(xiàng)下的“吊桶”，按所記x坐標(biāo)遞增排列?！暗跬啊敝懈黜?xiàng)的內(nèi)容依次是：1與較小的y坐標(biāo)對應(yīng)的端點(diǎn)的x坐標(biāo)xmin。2邊的另一端點(diǎn)的較大的y坐標(biāo)ymax。3x的增量x，它實(shí)際上是邊的斜率的 倒數(shù)，是從一條掃描線走到下一條掃 描線時(shí)，按x方向遞增的步長。4. 邊所屬多邊形的標(biāo)記。 設(shè)

16、有兩個(gè)空間的三角形ABC、DEF,各頂點(diǎn)的坐標(biāo)依次是（1,1,10）,（2,5,10）,（5,3,10）,（3,4,5）,（4,6,5）,（6,2,5）. 兩個(gè)多邊形在zv=0平面上的投影 ABCDEF兩個(gè)多邊形建立的“吊桶”已排序的邊表 2圖 7.21 還需要一個(gè)多邊形表PT(polygon Table)，其中要包含下列信息：1每個(gè)多邊形所在平面方程的系數(shù)。在需要比較深度時(shí)，要通過對所在（x,y），根據(jù)平面方程解出深度z。2每個(gè)多邊形的亮度或顏色值。實(shí)際做掃描轉(zhuǎn)換時(shí)應(yīng)用。3一個(gè)“進(jìn)入退出”標(biāo)志，初值為“假”。在掃描轉(zhuǎn)換處理時(shí)，用以標(biāo)記掃描線對該多邊形是“進(jìn)入”，還是“退出”。 象在多邊形填充

17、的掃描線算法中一樣，操作通過一個(gè)活躍邊表AET進(jìn)行。 通過以上的討論，可以寫出整個(gè)掃描線算法實(shí)施的步驟。 首先正確形成邊表ET和多邊形表PT之后，實(shí)施步驟就與第二章敘述的多邊形填充的掃描線算法的實(shí)施步驟基本相同，只是需要把那里的步驟:在掃描線y上，按照AET表提供的x坐標(biāo)對，用color實(shí)施填充修改加細(xì)如下： 1 將實(shí)施掃描轉(zhuǎn)換時(shí)遍查AET表中各“吊桶”的指針i初始置為1，掃描線正在多少個(gè)多邊形內(nèi)的累計(jì)數(shù)值s初始置為零，將活躍多邊形表，即掃描線正在通過的多邊形按深度遞增次序排列而形成的表，記為p，初始置為空。2 設(shè)第i個(gè)“吊桶”記錄的相應(yīng)多邊形是A。若A的“進(jìn)入/退出”標(biāo)記FA為“假”，則改F

18、A為“真”，將A加到表P的前面，s增加1。否則，F(xiàn)A即為“真”，則改FA為“假”，將P中的A去掉，s減少1。 3 若s=0，則到5。（這時(shí)掃描線不在任何多邊形內(nèi)，正通過背景，不必做掃描轉(zhuǎn)換。）若s=1，則到4（這時(shí)掃描線只在一個(gè)多邊形內(nèi)，不必做深度比較，去做掃描轉(zhuǎn)換。）若前面兩個(gè)判斷都為“假”，掃描線至少在兩個(gè)多邊形內(nèi)，應(yīng)做深度比較。對表P前面兩個(gè)多邊形做深度比較，比較后放回應(yīng)保證P表中的多邊形按深度遞增的次序。4 對第i個(gè)和第i+1個(gè)“吊桶”存有的x坐標(biāo)指示的掃描線上的一段，按照P表最前面多邊形指示的亮度或顏色，實(shí)施掃描轉(zhuǎn)換。 5 i增加1，若i所指已無“吊桶”，步驟結(jié)束，去下一步驟（刪除y

19、=ymax的邊）。否則，回到步驟2。在掃描線y=4，實(shí)施前面步驟的各步驟，情形如表7.1所示。 is PPT表 FABC FDEF 說明 11(ABC)true1 到3填A(yù)BC的亮度或顏色值 22(DEF, ABC)true在步驟3發(fā)生深度比較，比較結(jié)果DEF更靠近觀察者，它仍在P表前面，3到3 填DEF的亮度或顏色值 31(DEF)false3 到5填DEF的亮度或顏色值 40( ) false 如果按照步驟3的條件決定是否做深度比較，會(huì)有許多深度比較是不必要的。例如，假定有一個(gè)大的多邊形GHIJ在兩個(gè)三角形ABC和DEF的后面。在掃描線y=離開邊CB時(shí)，按步驟3的條件判斷，掃描線還同時(shí)在D

20、EF和GHIJ中，應(yīng)該做深度比較，但是在大多數(shù)可以假定沒有多邊形穿透另一個(gè)多邊形的情況下，DEF和GHIJ的深度關(guān)系并沒有變化，深度比較是不必要的。如果掃描線從一個(gè)被遮擋的多邊形中走出，深度比較將是不必要的；掃描線從一個(gè)遮擋了其它多邊形的多邊形中走出，深度比較才可能必要。三個(gè)多邊形 事實(shí)上前面給出的算法基本步驟沒有很好地利用深度的相關(guān)性。深度相關(guān)性是指多個(gè)多邊形之間的深度關(guān)系，常常對于一組相鄰的掃描線來說是不變化的。如果在某條掃描線上，在AET表中保存的邊及次序關(guān)系，與在前面一條掃描線上時(shí)完全相同，那么深度關(guān)系就不會(huì)變化，深度比較也就并不必要了。例如，圖7.21中的掃描線r+1到r+2就是這種

21、情形，在兩條掃描線上AET表中的邊及次序關(guān)系都是AB， DE ， CB ，F(xiàn)E。但從r到r+1，DE，CB的次序要變化為CB，DE，次序關(guān)系就變化了。利用深度的相關(guān)性可以對算法作出改進(jìn)。 上圖所示是一個(gè)多邊形穿透了另一個(gè)多邊形。為使算法能處理這種情況，應(yīng)該把其中的多邊形KLM分成兩個(gè)多邊形KLLM和LMM，加進(jìn)了一條沒有的邊ML。或者修改算法，使能夠在逐條掃描線的處理進(jìn)行中，發(fā)現(xiàn)掃描線上的穿透點(diǎn)。 關(guān)于背景的處理，最簡單的辦法是把更新緩沖存儲器整個(gè)初始化為某個(gè)合適的值，于是算法就只需處理掃描線在多邊形內(nèi)的情形。另一個(gè)辦法是，定義一個(gè)大的矩形，讓他包含了客體中所有的多邊形，位于比其它多邊形都更遠(yuǎn)

22、離觀察者的平行于投影平面的一個(gè)平面上，并具有某個(gè)合適的亮度或顏色值。再一個(gè)辦法就是修改算法。使得每當(dāng)掃描線不在任何多邊形內(nèi)時(shí)，就往幀緩沖存儲器中送入背景的象素值。 第七節(jié) 區(qū)域分割算法 區(qū)域分割算法將投影平面分割成區(qū)域，考察區(qū)域內(nèi)的圖象。如果容易決定在這個(gè)區(qū)域內(nèi)某些多邊形是可見的，那么就可以顯示那些可見的多邊形，完成對這一區(qū)域的顯示任務(wù)。否則，就將區(qū)域再分割成小的區(qū)域，對小的區(qū)域遞歸地進(jìn)行判斷。由于區(qū)域逐漸變小，在每個(gè)區(qū)域內(nèi)的多邊形逐漸變少，最終總可以判定哪些多邊形是可見的。這個(gè)算法利用的區(qū)域的相關(guān)性，這種相關(guān)性是指位于適當(dāng)大小的區(qū)域內(nèi)的所有象素，表示的其實(shí)是同一個(gè)表面。 在遞歸分割的每一步，

23、要顯示客體中每個(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í)可以對區(qū)域首先填充背景值，然后對多邊形進(jìn)行掃描轉(zhuǎn)換。在某些顯示設(shè)備上，將整個(gè)幀緩沖存儲

24、器都初始化為背景值，可能更為方便。對于相交的多邊形，只是被包含的部分被掃描轉(zhuǎn)換。 3.只有一個(gè)包圍的多邊形，無其它的多邊形。整個(gè)區(qū)域填充該多邊形的象素值。 4. 有多于一個(gè)的包圍的、相交的或被包含的多邊形，且至少有一個(gè)包圍的多邊形。檢查是否能有一個(gè)包圍的多邊形，它位于所有其它多邊形的前面。如果有，就可以讓整個(gè)區(qū)域都填充為這個(gè)多邊形的象素值。具體的檢查方法是，對所有的多邊形，計(jì)算其所在平面在區(qū)域的四個(gè)角點(diǎn)的應(yīng)有深度，即相應(yīng)的z坐標(biāo)，如果有一個(gè)包圍的多邊形的相應(yīng)四個(gè)z坐標(biāo)，都小于其它多邊形的對應(yīng)z坐標(biāo)，那么這個(gè)包圍的多邊形就位于所有其它多邊形的前面。情形4的兩種情形 區(qū)域經(jīng)過分割變小以后，只需要考

25、慮包含的多邊形和相交的多邊形的變化。 因?yàn)榉蛛x的或包圍的多邊形，對變小的區(qū)域，仍然保持是分離的或包圍的。分割進(jìn)行到達(dá)到顯示設(shè)備的分辨能力之后就可以停止，即最小的區(qū)域可以是顯示表面上的一個(gè)象素單位。如果在做了準(zhǔn)備做的最大數(shù)目的分割之后，仍然不能做出應(yīng)該如何填充的決定，那么，就計(jì)算所有有關(guān)多邊形在這個(gè)不可再分區(qū)域?qū)?yīng)的點(diǎn)的范圍的中心處的z坐標(biāo)值，取z坐標(biāo)最小的多邊形象素值填充這個(gè)區(qū)域。 Warnock首先提出的最初的區(qū)域分割算法是每次把區(qū)域分成四個(gè)正方形。下圖所示是對一個(gè)投影是一個(gè)三角形和一個(gè)長方體的場景，做了5次區(qū)域分割的情形，其中區(qū)域內(nèi)標(biāo)出的數(shù)字，表示可以作出決定的前面所說的四種情形中的哪一種

26、。沒有標(biāo)出數(shù)字的區(qū)域是還不能做出決定。分割區(qū)域?yàn)檎叫?區(qū)域分割不一定總是等分，當(dāng)區(qū)域內(nèi)有多邊形的頂點(diǎn)時(shí)，可以按照頂點(diǎn)位置來做分割，這樣顯然可以少做一些分割。 圍繞多邊形頂點(diǎn)分割（先是A，后是B） 區(qū)域分割還可以按照客體中多邊形投影的范圍進(jìn)行，這可以少做很多分割。 Weiler和Atherton提出的算法，直接就用多邊形的投影做為分割的區(qū)域。選擇用做分割的區(qū)域時(shí)，可以按照多邊形各頂點(diǎn)坐標(biāo)最小值的遞增次序 按照多邊形投影選擇區(qū)域做分割 第八節(jié) BSP樹算法 BSP（binary space-partitioning）樹算法將表面由后往前地在屏幕上繪出，該算法特別適用于場景中物體位置固定不變、僅視

27、點(diǎn)移動(dòng)的情況。 利用BSP樹來判別表面的可見性，其主要操作是在每次分割空間時(shí)，判別該表面相對于視點(diǎn)與分割平面的位置關(guān)系，即位于其內(nèi)側(cè)還是外側(cè)。 平面P1將空間分割為兩部分，一組物體位于P1的后面（相對于視點(diǎn)），而另一組則在P1之前，而B和D在P1之后。平面P2對空間進(jìn)行了二次分割，并生成如圖（b）所示的二叉樹表示。在這棵樹上，物體用葉節(jié)點(diǎn)表示，分割平面前方的物體組作為左分支，而后方的物體組為右分支。 法向量法向量 對于由多邊形面組成的物體，可以選擇與多邊形面重合的分割平面，利用平面方程來區(qū)分“內(nèi)”、“外”多邊形頂點(diǎn)。隨著將每個(gè)多邊形面作為分割平面，可生成一棵樹，與分割平面相交的每個(gè)多邊形將被分割為兩部分。一旦BSP樹創(chuàng)建完畢，即可選擇樹上的面并由后往前顯示，即前面物體覆蓋后面的物體。目前已有許多系統(tǒng)借助硬件來完成BSP樹創(chuàng)建和處理的快速實(shí)現(xiàn)。 第九節(jié) 八叉樹算法 當(dāng)按照八叉樹表示來描述觀察體時(shí)，通常按由前往后的順序?qū)瞬鏄涔?jié)點(diǎn)映射到觀察表面，從而消除隱藏面。 空間區(qū)域的前部（相對于視點(diǎn)）為體元0、1、2、3。體元的前表面均可見，這些體元尾部的表面和后部體元（4、5、6、7）的表面都可能被前部的表面所遮擋。 編號的八分區(qū)域 觀察方向 1023457 對于當(dāng)前視線，體元0、1、2、3中的物體總是遮擋后面體元中的物體 顯示八叉