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

2、外法向量是n，則這兩個向量的夾角 滿足0 /2時，所考查面是可見的，否則就是不可見的,把n和k記作 則,分子 為正 ，則 ,面為可見；若為負，則 ，面為不可見；若為零，則 ，此面退化為線。,設(shè)空間有一個四面體，頂點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為可見面.類似計算可知，面DBC是可見面,面ADC是不可見面,面ACB退化為線。,利用外法線就可以判斷凸多面體上各表面的可見性，由此就能解決對單個凸多面體的隱藏線和隱藏面的消除問題。

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

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

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

6、元組壓入堆棧； while(棧不空) =棧頂； for (i!= i0的每個面FACEi） if(EDGEj被FACEi全部遮擋) 將EDGEj清空；break; if(EDGEj被FACEi部分遮擋) 從EDGEj中將被遮擋的部分裁掉； if(EDGEj被分成若干段) 將其中的一段作為當(dāng)前段； 將其他段及相應(yīng)的i壓入堆棧； if(EDGEj段不為空) 顯示EDGEj； ,第二節(jié) 曲面隱藏線消除的浮動水平線算法,若存在M個象素，則建立M個內(nèi)存單元 ，稱之為上浮水平線數(shù)組，在這些單元中先放上初值，初值應(yīng)取成小于 。,曲面方程,設(shè),平面 是最靠近觀察者的，從平面上 的曲線,水平方向每個象素的對應(yīng)x

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

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

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

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

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

12、離，另一個域存放該面的面號。,Vertices：讀進頂點的空間坐標(biāo)，計算物體的包圍球半徑，把物體縮小到單位球中去，計算物體各頂點在屏幕上的投影坐標(biāo)。,第五節(jié) z緩沖算法,z緩沖算法(深度緩沖算法)是一種最簡單的圖象空間算法。對每一個點，這個算法不僅需要有一個更新緩沖器存儲各點的象素值，而且還需要有一個z緩沖存儲器存儲相應(yīng)的z值。更新緩沖存儲器初始化為背景值，z緩沖存儲器初始化為可以表示的最大z值。對每一個多邊形，不必進行深度排序算法要求的初始排序，立即就可以逐個進行掃描轉(zhuǎn)換。,掃描轉(zhuǎn)換時,對每個多邊形內(nèi)部的任意點(x,y),實施如下步驟： 1 計算在點(x,y)處多邊形的深度值Z(x,y)。

13、2如果計算所得的Z(x,y)值，小于在z緩 沖存儲器中點xy處記錄的深度值， 那么就做： （1）把值Z(x,y)送入z緩沖存儲器的點x,y 處。 （2）把多邊形在深度Z(x,y)處應(yīng)有的象素 值，送入更新緩沖存儲器的點x,y處。,算法中深度計算，可通過多邊形的頂點坐標(biāo)求出所在平面的方程，然后再使用平面方程，對每個點xy，解出相應(yīng)的z。,對面方程 解出 是：,則在點（x+x,y）處的深度值就是,設(shè)在點（x,y）處的深度值是z1:, z緩沖算法的工作流程： 更新緩沖區(qū)置成背景色； z緩沖區(qū)置成最大z值； for (各個多邊形) 掃描轉(zhuǎn)換該多邊形； for(計算多邊形所覆蓋的每個象素（x,y）) 計

14、算多邊形在該象素的深度值Z(x,y)； if(Z(x,y)小于Z緩沖區(qū)中的(x,y)處的值) 把Z(x,y)存入Z緩沖區(qū)中的(x,y)處； 把多邊形在(x,y)處的亮度值存入更新緩 存區(qū)的 (x,y)處； ,第六節(jié) 掃描線算法,掃描線算法是圖象空間算法，它建立圖象是通過每次處理一條掃描線來完成的。這個算法是第二章討論的多邊形填充的掃描線算法的推廣。在多邊形填充的掃描線算法中，只是對一個多邊形做掃描轉(zhuǎn)換，而這里是同時對多個多邊形做掃描轉(zhuǎn)換。,要建立一個邊表ET。ET中各登記項按邊的較小的y坐標(biāo)遞增排列；每一登記項下的“吊桶”，按所記x坐標(biāo)遞增排列?！暗跬啊敝懈黜椀膬?nèi)容依次是： 1與較小的y坐標(biāo)對

15、應(yīng)的端點的x坐標(biāo)xmin。 2邊的另一端點的較大的y坐標(biāo)ymax。 3x的增量x，它實際上是邊的斜率的 倒數(shù)，是從一條掃描線走到下一條掃 描線時，按x方向遞增的步長。 4. 邊所屬多邊形的標(biāo)記。,設(shè)有兩個空間的三角形ABC、DEF,各頂點的坐標(biāo)依次是（1,1,10）,（2,5,10）,（5,3,10）,（3,4,5）,（4,6,5）,（6,2,5）.,兩個多邊形在zv=0平面上的投影,兩個多邊形建立的“吊桶”已排序的邊表,2,圖 7.21,還需要一個多邊形表PT(polygon Table)，其中要包含下列信息： 1每個多邊形所在平面方程的系數(shù)。在需要比較深度時，要通過對所在（x,y），根據(jù)平

16、面方程解出深度z。 2每個多邊形的亮度或顏色值。實際做掃描轉(zhuǎn)換時應(yīng)用。 3一個“進入退出”標(biāo)志，初值為“假”。在掃描轉(zhuǎn)換處理時，用以標(biāo)記掃描線對該多邊形是“進入”，還是“退出”。 象在多邊形填充的掃描線算法中一樣，操作通過一個活躍邊表AET進行。,通過以上的討論，可以寫出整個掃描線算法實施的步驟。 首先正確形成邊表ET和多邊形表PT之后，實施步驟就與第二章敘述的多邊形填充的掃描線算法的實施步驟基本相同，只是需要把那里的步驟:在掃描線y上，按照AET表提供的x坐標(biāo)對，用color實施填充修改加細如下：,1 將實施掃描轉(zhuǎn)換時遍查AET表中各“吊桶”的指針i初始置為1，掃描線正在多少個多邊形內(nèi)的累計

17、數(shù)值s初始置為零，將活躍多邊形表，即掃描線正在通過的多邊形按深度遞增次序排列而形成的表，記為p，初始置為空。 2 設(shè)第i個“吊桶”記錄的相應(yīng)多邊形是A。若A的“進入/退出”標(biāo)記FA為“假”，則改FA為“真”，將A加到表P的前面，s增加1。否則，F(xiàn)A即為“真”，則改FA為“假”，將P中的A去掉，s減少1。,3 若s=0，則到5。（這時掃描線不在任何多邊形內(nèi)，正通過背景，不必做掃描轉(zhuǎn)換。）若s=1，則到4（這時掃描線只在一個多邊形內(nèi)，不必做深度比較，去做掃描轉(zhuǎn)換。）若前面兩個判斷都為“假”，掃描線至少在兩個多邊形內(nèi)，應(yīng)做深度比較。對表P前面兩個多邊形做深度比較，比較后放回應(yīng)保證P表中的多邊形按深度

18、遞增的次序。 4 對第i個和第i+1個“吊桶”存有的x坐標(biāo)指示的掃描線上的一段，按照P表最前面多邊形指示的亮度或顏色，實施掃描轉(zhuǎn)換。,5 i增加1，若i所指已無“吊桶”，步驟結(jié)束，去下一步驟（刪除y=ymax的邊）。否則，回到步驟2。在掃描線y=4，實施前面步驟的各步驟，情形如表7.1所示。,如果按照步驟3的條件決定是否做深度比較，會有許多深度比較是不必要的。例如，假定有一個大的多邊形GHIJ在兩個三角形ABC和DEF的后面。在掃描線y=離開邊CB時，按步驟3的條件判斷，掃描線還同時在DEF和GHIJ中，應(yīng)該做深度比較，但是在大多數(shù)可以假定沒有多邊形穿透另一個多邊形的情況下，DEF和GHIJ的

19、深度關(guān)系并沒有變化，深度比較是不必要的。如果掃描線從一個被遮擋的多邊形中走出，深度比較將是不必要的；掃描線從一個遮擋了其它多邊形的多邊形中走出，深度比較才可能必要。,三個多邊形,事實上前面給出的算法基本步驟沒有很好地利用深度的相關(guān)性。深度相關(guān)性是指多個多邊形之間的深度關(guān)系，常常對于一組相鄰的掃描線來說是不變化的。如果在某條掃描線上，在AET表中保存的邊及次序關(guān)系，與在前面一條掃描線上時完全相同，那么深度關(guān)系就不會變化，深度比較也就并不必要了。例如，圖7.21中的掃描線r+1到r+2就是這種情形，在兩條掃描線上AET表中的邊及次序關(guān)系都是AB，CB，DE，F(xiàn)E。但從r到r+1，DE，CB的次序要

20、變化為CB，DE，次序關(guān)系就變化了。利用深度的相關(guān)性可以對算法作出改進。,上圖所示是一個多邊形穿透了另一個多邊形。為使算法能處理這種情況，應(yīng)該把其中的多邊形KLM分成兩個多邊形KLLM和LMM，加進了一條沒有的邊ML?；蛘咝薷乃惴ǎ鼓軌蛟谥饤l掃描線的處理進行中，發(fā)現(xiàn)掃描線上的穿透點。,關(guān)于背景的處理，最簡單的辦法是把更新緩沖存儲器整個初始化為某個合適的值，于是算法就只需處理掃描線在多邊形內(nèi)的情形。另一個辦法是，定義一個大的矩形，讓他包含了客體中所有的多邊形，位于比其它多邊形都更遠離觀察者的平行于投影平面的一個平面上，并具有某個合適的亮度或顏色值。再一個辦法就是修改算法。使得每當(dāng)掃描線不在任何

21、多邊形內(nèi)時，就往幀緩沖存儲器中送入背景的象素值。,第七節(jié) 區(qū)域分割算法,區(qū)域分割算法將投影平面分割成區(qū)域，考察區(qū)域內(nèi)的圖象。如果容易決定在這個區(qū)域內(nèi)某些多邊形是可見的，那么就可以顯示那些可見的多邊形，完成對這一區(qū)域的顯示任務(wù)。否則，就將區(qū)域再分割成小的區(qū)域，對小的區(qū)域遞歸地進行判斷。由于區(qū)域逐漸變小，在每個區(qū)域內(nèi)的多邊形逐漸變少，最終總可以判定哪些多邊形是可見的。這個算法利用的區(qū)域的相關(guān)性，這種相關(guān)性是指位于適當(dāng)大小的區(qū)域內(nèi)的所有象素，表示的其實是同一個表面。,在遞歸分割的每一步，要顯示客體中每個多邊形的投影多邊形與所考察區(qū)域之間的關(guān)系，必然是下列四種之一： 1.包圍的多邊形，即多邊形包含了所

22、考察 的區(qū)域的全部。 2.相交的多邊形，即多邊形與所考察的區(qū) 域相交。 3. 被包含的多邊形,即多邊形全部在所 考察的區(qū)域之內(nèi)。 4. 分離的多邊形，即多邊形與所考察的 區(qū)域完全分離。,包圍的 相交的 被包含的 分離的,若區(qū)域與多邊形為下面的四種情況，不必再做進一步的分割，可直接繪制。 1所有的多邊形與區(qū)域分離，在區(qū)域內(nèi)只需顯示背景值。 2. 只有一個相交的多邊形，或者只有一個被包含的多邊形。這時可以對區(qū)域首先填充背景值，然后對多邊形進行掃描轉(zhuǎn)換。在某些顯示設(shè)備上，將整個幀緩沖存儲器都初始化為背景值，可能更為方便。對于相交的多邊形，只是被包含的部分被掃描轉(zhuǎn)換。,3.只有一個包圍的多邊形，無其它

23、的多邊形。整個區(qū)域填充該多邊形的象素值。 4. 有多于一個的包圍的、相交的或被包含的多邊形，且至少有一個包圍的多邊形。檢查是否能有一個包圍的多邊形，它位于所有其它多邊形的前面。如果有，就可以讓整個區(qū)域都填充為這個多邊形的象素值。具體的檢查方法是，對所有的多邊形，計算其所在平面在區(qū)域的四個角點的應(yīng)有深度，即相應(yīng)的z坐標(biāo)，如果有一個包圍的多邊形的相應(yīng)四個z坐標(biāo)，都小于其它多邊形的對應(yīng)z坐標(biāo)，那么這個包圍的多邊形就位于所有其它多邊形的前面。,情形4的兩種情形,區(qū)域經(jīng)過分割變小以后，只需要考慮包含的多邊形和相交的多邊形的變化。 因為分離的或包圍的多邊形，對變小的區(qū)域，仍然保持是分離的或包圍的。分割進行

24、到達到顯示設(shè)備的分辨能力之后就可以停止，即最小的區(qū)域可以是顯示表面上的一個象素單位。如果在做了準(zhǔn)備做的最大數(shù)目的分割之后，仍然不能做出應(yīng)該如何填充的決定，那么，就計算所有有關(guān)多邊形在這個不可再分區(qū)域?qū)?yīng)的點的范圍的中心處的z坐標(biāo)值，取z坐標(biāo)最小的多邊形象素值填充這個區(qū)域。,Warnock首先提出的最初的區(qū)域分割算法是每次把區(qū)域分成四個正方形。下圖所示是對一個投影是一個三角形和一個長方體的場景，做了5次區(qū)域分割的情形，其中區(qū)域內(nèi)標(biāo)出的數(shù)字，表示可以作出決定的前面所說的四種情形中的哪一種。沒有標(biāo)出數(shù)字的區(qū)域是還不能做出決定。,分割區(qū)域為正方形,區(qū)域分割不一定總是等分，當(dāng)區(qū)域內(nèi)有多邊形的頂點時，可以

25、按照頂點位置來做分割，這樣顯然可以少做一些分割。,圍繞多邊形頂點分割（先是A，后是B）,區(qū)域分割還可以按照客體中多邊形投影的范圍進行，這可以少做很多分割。 Weiler和Atherton提出的算法，直接就用多邊形的投影做為分割的區(qū)域。選擇用做分割的區(qū)域時，可以按照多邊形各頂點坐標(biāo)最小值的遞增次序,按照多邊形投影選擇區(qū)域做分割,第八節(jié) BSP樹算法,BSP（binary space-partitioning）樹算法將表面由后往前地在屏幕上繪出，該算法特別適用于場景中物體位置固定不變、僅視點移動的情況。 利用BSP樹來判別表面的可見性，其主要操作是在每次分割空間時，判別該表面相對于視點與分割平面的

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