ch08——隱藏面及隱藏線的消除

1、第8章隱藏面和隱藏線的消除,隱藏面和隱藏線的消除是計算機圖形學中的一個基本問題。由于存在不透光的物體，因此阻擋了來自某些物體部分的光線到達觀察者，這些物體部分成為隱藏部分，隱藏部分是不可見的。為了使計算機生成的圖能真實地反映這一情況，必須把隱藏的部分從圖中消除。如果不把隱藏的線或面消除，還可能發(fā)生對圖的錯誤理解。,,圖8.1 兩種理解,基于圖像空間的方法以構成圖像的每一個像素為處理單元，對場景中的所有表面，確定相對于觀察點是可見

2、的表面，用該表面的顏色填充該像素。該算法多用于面消隱。算法的簡單描述如下：對于圖像中的每一個像素：在和投影點到像素連線相交的表面中，找到離觀察點最近的表面；用該表面上交點處的顏色填充該像素,隱藏面和隱藏線的消除有兩種基本的算法,基于物體空間的方法是以三維場景中的物體對象為處理單元，在所有對象之間進 行比較，除去完全不可見的物體和物體上不可見的部分。該算法多用于線消隱，也用于面消隱。算法的簡單描述如下： 對于三

3、維場景中的每一個物體：判定場景中的所有可見表面；用可見表面的顏色填充相應的像素以構成圖形；,隱藏面和隱藏線的消除有兩種基本的算法,假定1：,隱藏線和隱藏面消除所討論的對象是一個三維圖形，消隱后要在二維空間中表示出來，因此消隱后顯示的圖形將和三維空間至二維空間的投影方式有關。下面討論消隱算法時，都假定投影平面就是oxy平面，投影方向為負z軸方向的垂直投影。如果不是這種情況，可對消隱的對象先作變換，變成這種情況，然后再作消隱計算。

4、在投影平面就是oxy平面以及投影是透視時，可用變換（4.14）―（4.16）式。投影是平行投影，但投影方向不是負z軸方向，則可用變換（4.21）―（4.23）式。如果投影平面不是oxy平面，平行投影時則先要用變換（4.36）式，透視時先要用變換（4.33）式，式（4.33）中的常數(shù)A和B應滿足式（4.17）,,假定2：本章說明的各種消隱方法都假定構成對象的不同面不能相互貫穿，見圖8.1，也不能有循環(huán)遮擋的情況，如果有這種情況，可

5、把它們剖分成互不貫串和不循環(huán)遮擋的情況。例如用圖8.2（b）中的虛線便可把原來循環(huán)遮擋的三個平面，分割成不互相循環(huán)遮擋的四個面。,,圖8.2 貫穿和循環(huán)遮擋,8.1 多面體的隱藏線消除,設有多個互不相交的多面體，對它們的消隱問題，和他們的顯示方式有關。討論隱藏線消除問題，總假定它們是用線框方式來表示的。在這種方式下多面體用棱來表示。這時隱藏線便是某些不可見的棱或棱的一部分。如果能把各棱上可見和不可見部分的分界點找到，消隱問題也

6、就迎刃而解了。這些分界點都是多面體的各棱在oxy平面上投影間的交點，見圖8.3。這樣，問題就轉化成了在oxy平面上求很多直線的交點的計算。,圖8.3,8.1 多面體的隱藏線消除,在oxy平面上求很多直線的交點的計算。如果消隱對象有N條棱，用兩兩求交的方法求所有交點的工作量為O（N2）。當N很大時，這個工作量是可觀的。要提高算法的效率，就要設法減少求交的工作量。實際上交點個數(shù)遠小于O（N2），例如圖8.3的多面體有15條邊，如果

7、不計棱端點處的交點，棱在oxy平面上的投影相互間只有5個交點。這說明有很多棱在oxy平面上的投影相互間并不相交。問題在于如何能預先知道它們是不相交的，從而把它們排擠在求交計算之外。,,8.1 多面體的隱藏線消除,減少求交計算的若干方法：把后向面全部去掉 用邊界盒排除不相交的線段求交。 在后向面被刪除后，如果兩個相鄰的多邊形的公共邊都在兩個多邊形的凸包上，則這兩個多邊形不會發(fā)生一個遮擋另一個的現(xiàn)象。因而在考慮一個多邊形的邊的顯示

8、時，可以不考慮另一個多邊形對它的影響。,8.1 多面體的隱藏線消除,去掉后向面把內法線方向背向視點的面稱為前向面，如圖8.3中的IJFGH，F(xiàn)ABG，HCDI和IDEJ所在的面均為前向面。其余的面稱為后向面，例如圖8.3中JEAF和DEABC所在的面均為后向面，后向面總是看不見的，不會僅由于后向面的遮擋，而使別的棱成為不可見，因此可把后向面全部去掉，這不影響消隱結果。,8.1 多面體的隱藏線消除,設多邊形F的頂點為v1,

9、v2,…,vL，頂點vi的坐標為（xi yi zi）。頂點的次序要求這樣排列，使觀察者在多面體外沿著v1→v2→v3…→vL走時，多邊形的內部始終在它的右側。為了確定多邊形的內法線方向，可以計算多邊形在oxy平面上投影的有向面積。有向面積sp可如下計算如果sp≥0，則F所在的面為后向面。如果sp<0，則F所在的面為前向面。,,8.1 多面體的隱藏線消除,用邊界盒排除不相交的線段求交,,,8.1 多面

10、體的隱藏線消除,在后向面被刪除后，如果兩個相鄰的多邊形的公共邊都在兩個多邊形的凸包上，則這兩個多邊形不會發(fā)生一個遮擋另一個的現(xiàn)象。這時，在考慮一個多邊形的邊的顯示時，可以不考慮另一個多邊形對它的影響。,8.1 多面體的隱藏線消除,隱藏線消除實際計算過程 ：要對體一個一個來考慮，如考慮體A的顯示時，先確定可能遮擋A的那些體（包括體A本身），對體A的每個多邊形G，要找出可能遮擋它的所有多邊形--這些多邊形要從可能遮擋A的所有體的表

11、面多邊形中去找。然后對多邊形G的每一條邊L找出可能遮擋它的所有多邊形---這些多邊形要從可能遮擋多邊形G的所有多邊形中去找。（以上各步均采用邊界盒方法）找到所有可能遮擋邊L的多邊形后，便可求L和這些多邊形的交點，并決定L的可見部分。,,,,,,,,,L,,8.1 多面體的隱藏線消除,設邊L的二端點頂點是vi和vj，對邊vivj（即L）和每一個可能遮擋它的多邊形，都要作下列計算和判斷，以確定其隱藏關系。如果vi和vj都在多邊形

12、所在平面靠近觀察者的一側則這個多邊形不能遮擋直線段vivj，這時沒有必要再考慮vivj和這個多邊形的關系。 如果vi和vj不都在多邊形所在平面靠近觀察者的一側，且vivj和多邊形在oxy平面的投影之間有交點，那么把vivj和多邊形的邊界投影到oxy平面上，求出它們的投影之間的交點。對每一個交點還要判斷它在vivj上的對應點是在多邊形前面還是后面，只有在多邊形后面，交點才要保留。如圖8.6中邊v1v2和多邊形ABCD在oxy平

13、面上的投影雖然有交點Q，但它在v1v2上的對應點v卻在多邊形的前方，這種交點可不考慮。如果vivj和多邊形在oxy平面的投影之間沒有交點，那么，這時要判斷vi或vj在oxy平面上的投影是否在 多邊形投影的內部，如果在內部，則vivj就會整個被這個多邊形所遮擋住了。,,圖8.6,現(xiàn)在來說明確定L的可見部分的具體計算過程 ：（1）確定L頂點處的

14、與遮擋多邊形的前后位置關系設多邊形的頂點為 ， ，…， 其坐標為（ , , ），i=1,2,…,L。任取三個不在一直線上的頂點，設為 , , ，則這多邊形所在的平面方程為 或,8.1 多面體的隱藏線消除,,,,,,,,,,,設點vj的坐標為（xj, yj, zj），若z（xj, yj）<zj 則vj在多邊形所在平面的前面，否則認為vj在多邊形所在平面的后面。,,,其中,8.1 多面體的隱藏線消除

15、,（2）確定L與遮擋多邊形的交點同遮擋多邊形的前后位置關系：為了判斷邊vivj和多邊形在oxy平面的投影之間是否有交點，可首先計算求邊vivj和多邊形的邊界在oxy平面上投影的交點，我們可以把vivj的投影線段用參數(shù)方程表示:多邊形上任一邊的投影用用參數(shù)方程表示:求交點時解方程 可得 其中

16、 （8.9）只有當0≤l≤1和0≤t ≤1時線段和線段vivj在oxy平面上的投影才有交點為了判斷vIvj上對應交點的點是在多邊形所在平面的前面還是后面，則要去比較 和 ，若前者大于后者，則vivj上交點的對應點在多邊形所在平面的前面，否則在后面。,,,,,,,,8.1 多面體的隱藏線消除,（3）確定交點和多邊形的關系——是內點還是出點 ：由式（8.9）可知

17、 ,其中（）z是指向量在z軸上的投影。當 0時，QiQj由多邊形內離開多邊形到多邊形外（該交點稱為出點）。這個信息也要和交點的信息一起保存起來。,,,,,8.1 多面體的隱藏線消除,（4）確定Qi起點和多邊形的關系 判斷Qi點在多邊形內或外， 可以從Qi點出發(fā)沿x軸的正向作一射線，見圖8.8。 若該射線和多邊形邊界的交點個數(shù)是奇數(shù)，則Qi在多邊形內，否則就在多邊形外。 但正確地找

18、到交點的個數(shù)并不容易。如圖8.8中點Q6處，由于舍入誤差，計算時可能認為Q5 Q6， Q6 Q7和QiF均有交點，也可能算出一個交點或沒有求出交點，不同的交點數(shù)可得到完全不同的結果。----需要特殊處理,,圖8.8,8.1 多面體的隱藏線消除,（5）確定L的可見部分這里引入不可見階ivord的概念它是一個數(shù)字，是某個確定的點的屬性，代表了邊上從該點到下一個交點的部分被幾個多邊形遮擋。這里要分兩步來做：Step1.確定邊Q

19、iQj頂點處的不可見階 Step2.確定邊QiQj與遮擋多邊形交點處的不可見階。,8.1 多面體的隱藏線消除,（5）確定L的可見部分--Step1.確定邊QiQj頂點處的不可見階 首先將Qi處的ivord設置為0，對每一個和QiQj有交點的多邊形，從與該多邊形相交的交點中找出距離Qi最近的交點（交點參數(shù)最?。鐖D8.9中所示QiQj和多邊形H1的交點B，若這個交點為QiQj的出點，則在ivord上加1，交點為進點，則ivor

20、d不變。事實上Qi處的ivord反映了有幾個多邊形遮擋由Qi到QiQj與所有多邊形的所有交點中距離Qi最近的交點形成的線段，若Qi處不可見階為0，則QiQj從l=0至l= l1段為可見，否則為不可見。,圖8.9,8.1 多面體的隱藏線消除,（5）確定L的可見部分--Step2.確定邊QiQj與遮擋多邊形交點處的不可見階。 假設直線QiQj和所有的多邊形共有n個的交點，將直線與所有多邊形的交點按著交點參數(shù)的大小排序，形成統(tǒng)一的交點

21、序列 下面我們計算 的不可見階ivord, 注意這里L0不可見階就 是Qi的不可見階。首先將Li的不可見階ivord設置Li-1的不可見階如果Li處的交點為進點，說明該交點所在的多邊形不遮擋由參數(shù)Li-1 和Li所決定的直線段，而遮擋由參數(shù)Li 和Li+1所決定的直線段。因此Li的不可見階加1如果Li處的交點為出點，說明該交點所在的多邊形遮擋由參數(shù)Li-1 和Li所決定的直線段，而不遮擋由參數(shù)參數(shù)Li

22、 和Li+1所決定的直線段。因此Li的不可見階減1若Li處不可見階為0，則由參數(shù)Li 和Li+1所決定的直線段是可見的，否則為不可見。,,,,8.3 區(qū)域子分算法,討論一個面或面的一部分可見與否。 為了減少計算量，可先去掉所有的后向面。區(qū)域子分算法（warnock）是一種所謂分而治之的算法。整個屏幕稱為窗口，分而治之算法是一個遞推的四等分過程，每一次把矩形的窗口等分成四個相等的小矩形，分成的矩形也稱為窗口。每一次子分，均要把要顯

23、示的多邊形和窗口的關系作一判斷。,,8.3 區(qū)域子分算法,這種關系可有以下四種，即 多邊形包圍了窗口多邊形和窗口相交窗口包圍了多邊形窗口和多邊形分離,,8.3 區(qū)域子分算法,在窗口和每個多邊形的關系確定之后，有些窗口內的圖形便可顯示了。它們屬于下列三種情況之一。所有多邊形都和窗口分離，這時只要把窗口內所有的象素填上背景顏色。只有一個多邊形和窗口相交，或這個多邊形包含在窗口內。這時先對窗口內每一象素填上背景顏色，再對

24、窗口內多邊形部分用掃描線算法填色只有一個多邊形和窗口相交，這個多邊形把窗口整個包圍在內，或雖有幾個多邊形和窗口相交，但離觀察者最近的一個多邊形包圍了整個窗口，這時把整個窗口填上離觀察者最近的那個多邊形的顏色。對上述三種情況的窗口來說，圖已可畫出，因而不必再分細了。,8.3 區(qū)域子分算法,對上述三種情況不成立的窗口再一分為四，見圖8.18。分得的窗口重復上述的處理。對不能處理的窗口再一分為四。窗口的邊長越分越短，分了若干次后，窗口的

25、邊長就和一個象素的寬度一樣了，這時這個窗口對應的象素的顏色可取成最靠近觀察者的多邊形的顏色，或和這個窗口相交的多邊形顏色的平均值。,圖8.18,8.3 區(qū)域子分算法,Divide-Conqer算法的思想雖然簡單，具體實現(xiàn)時的細節(jié)要處理好，才能提高效率。下面介紹一些有效的處理方法。對所有的多邊形按其頂點的z坐標最大值（即最靠近觀察者的一個頂點的z坐標值）來排序。對一個具體窗口來說，隨著窗口不斷地被細分，這個多邊形序列的元素將越來越

26、少。窗口變小了，用邊界盒的辦法就可能判定一些多邊形和這個窗口是無交的，這些多邊形也不會和這個窗口的子窗口相交，因此對這個窗口來說這些多邊形可從多邊形序列中排除。此外窗口變小了，就可能被一個多邊形包含在內，這樣在這個窗口內，比這個多邊形遠離觀察者的多邊形都會被這個多邊形所遮擋，對這個窗口的子窗口來說這些多邊形也被遮擋了，因此對這個窗口來說，這些被遮擋的多邊形可從序列中去掉。,8.3 區(qū)域子分算法,對于不能用邊界盒辦法判斷和窗口不相交的

27、多邊形，則要經(jīng)過計算去確定它們之間的關系。這時可以采用與第四章中多邊形裁剪算法類似的方法去確定多邊形的窗口的邊界是否有交點。有交點時，說明多邊形和窗口有交。無交點時還要去確定它們是分離還是有包含關系。,8.3 區(qū)域子分算法,在找到了一個多邊形包圍所考慮的窗口后，就要把它和多邊形序列中其它多邊形離觀察者的遠近進行比較，把被它遮擋的多邊形從序列中去掉。為此可把窗口四個頂點坐標的x, y值代入那個包圍窗口的多邊形所在的平面方程，以求出

28、對應四個頂點處該平面的z坐標值。以zmin記這四個z坐標值的最小值，對序列中第i個多邊形，把它各頂點z坐標值的最大值記為zmaxi, 若滿足zmin≥zmaxi,則序列中第i個多邊形便被遮擋了，如圖8.19所示，多邊形AB包含了窗口，多邊形CD便可用此法證實是被遮擋的。但多邊形EF則不能用此方法證實被多邊形AB所遮擋。遇見這種情況可在窗口內多邊形EF上任找一點G（xG, yG，zG），把xG，yG代入多邊形AB所在的平面方程，求出

29、H點處的坐標z值zH，若zH >zG，則AB在窗口內遮擋了多邊形EF。,,Divide-Conqer算法的具體實現(xiàn)：,圖8.19,8.3 區(qū)域子分算法,區(qū)域子分法提出來后，有不少文章提出了一些改進。參考文章[88]中提出的方法是用多邊形的邊界來對窗口作劃分，這樣做的目的是盡量減少對窗口劃分的次數(shù)。,,,用多邊形的邊界來對窗口作劃分的方法,8.3 區(qū)域子分算法,用多邊形的邊界來對窗口作劃分的方法--算法思想：先用某種方法對各多

30、邊形在深度方向作初步的排序，例如可按多邊形頂點z坐標值的最大值zmaxi來排序，zmaxi大的排在前面?，F(xiàn)把多邊形序列中的第一個多邊形（裁剪多邊形）取為窗口。多邊形序列中的其它的多邊形都要被這窗口裁剪。裁剪的結果要建立兩個多邊形序列表，一個是窗口內的多邊形表，一個是窗口外的多邊形表。每一個被裁剪的多邊形裁剪后位于窗口內的部分放入內部表中位于窗口外的部分放在外部表中。圖8.21（a）和圖8.21（b）分別為圖8.20中多

31、邊形的內部表和外部表，圖8.20中多邊形1作為窗口。,,,,,,圖8.20,圖8.21,(a),(b),8.3 區(qū)域子分算法,下面要來確定裁剪多邊形（即取為窗口的那個多邊形）是否比內部表中的多邊形更靠近觀察者求出裁剪多邊形各頂點坐標z的極小值zminc,求出內部多邊形各頂點坐標z的極大值zmaxi對那些滿足 zminc> zmaxi的內部表中的多邊形，便可確認它被裁剪多邊形所遮擋若某一內部多邊形不滿足上式，則要從該多邊形

32、上取一點，作一和z軸平行的線，求出該線和兩個多邊形所在平面的交點，根據(jù)交點的位置便可準確地確定哪一個多邊形更靠近觀察者。,用多邊形的邊界來對窗口作劃分的方法--算法思想：,8.3 區(qū)域子分算法,如果發(fā)現(xiàn)內部表中某多邊形H比裁剪多邊形更靠近觀察者，這時則只好把多邊形H的原始多邊形（即未被裁剪時的多邊形）代替原來的裁剪多邊形重復上述工作。若裁剪多邊形確實比內部表中的多邊形都靠近觀察者，則裁剪多邊形便是完全可見的，可把它全部顯示出來。

33、,用多邊形的邊界來對窗口作劃分的方法--算法思想：,8.3 區(qū)域子分算法,下面則要去處理外部表中的各多邊型把外部表中第一個多邊形作為窗口（假定外部表中多邊形也是按原來的多邊形次序排序）對外部表中的其它多邊形作裁剪并確定遮擋關系在這過程中又形成新的外部表。每一個新的外部表中多邊形的個數(shù)均比原來的外部表中多邊形的個數(shù)少。這一過程要重復到外部表中不再有多邊形為止,用多邊形的邊界來對窗口作劃分的方法--算法思想：,8.4 Z緩沖器算法

34、,z緩沖器算法是最簡單的消除隱藏面算法之一z緩沖器是一組存貯單元其單元個數(shù)和屏幕上象素的個數(shù)相同也和幀緩沖器的單元個數(shù)相同，它們之間一一對應。,,,8.4 Z緩沖器算法,z緩沖器的設置z緩沖器中每個單元的位數(shù)取決于圖形在z方向的變化范圍，一般取20bits就可以了。z緩沖器中每單元的值是對應象素點所反應的物體上點的z坐標值。z緩沖器中每個單元的初值取成z的極小值，幀緩沖器每個單元的初值可放對應顏色的值,8.4 Z緩沖器算

35、法,圖形消隱和生成的過程就是給幀緩沖器和z緩沖器中相應單元填值的過程在把顯示物體的每個面上每一點的屬性（顏色或灰度）值填入幀緩沖器相應單元前，要把這點的z坐標值和z緩沖器中相應單元內的值作比較。只有前者大于后者時才改變幀緩沖器的那一個單元的值，同時z緩沖器中相應單元的值也要改成這點的z坐標值。如果這點的z坐標值小于z緩沖器中相應單元的值，則說明對應象素已顯示了物體上一個點的屬性，該點比要考慮的點更接近觀察者。這樣，無論幀緩沖器或z

36、緩沖器相應單元的值均不應改變。對顯示物體的每一個面上的每一個點都做上述處理后，便可得到消除了隱藏面的圖。,,,8.4 Z緩沖器算法,算法的優(yōu)點簡單、可靠不需要對顯示物體的面預先進行排序算法的缺點要很大的z緩沖器工作量較大：顯示物體的表面和象素對應的每一個點處都要計算它的z值 為了克服第一個缺點，可把整個平面分成若干區(qū)域，一區(qū)一區(qū)來顯示，這樣z緩沖器的單元數(shù)只要等于屏幕上一個區(qū)域的象素個數(shù)。如果把這個區(qū)域取成屏幕上一行

37、，就得到了掃描線z緩沖器算法。,8.4掃描線Z緩沖器算法,掃描線z緩沖器 --算法 思想z緩沖器的單元數(shù)可以取成和一行上的象素數(shù)目相同。從最上面的一條掃描線開始工作，向下對每一條掃描線作處理。對每一條掃描線來說，把相應的幀緩沖器單元置成底色，在z緩沖器中存放z的極小值。,8.4掃描線Z緩沖器算法,掃描線z緩沖器--算法 思想對每個多邊形檢查它在oxy平面上的投影和當前的掃描是否相交，若不相交，則不考慮該多邊形。如果相交，則掃

38、描線和多邊形邊界的交點一事實上是成對地出現(xiàn)對每對交點中間的象素計算多邊形所在平面對應點的深度（即z值），并和z緩沖器中相應單元存放的深度值作比較。若前者大于后者，則z緩沖器的相應單元內容要被求得的平面深度代替，幀緩沖器相應單元的內容也要換成該平面的屬性。對所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應了消隱后的圖形。對幀緩沖器每一行的單元都填上相應內容后也就得到了整個消隱后的圖。,8.4掃描線Z緩沖器算法,上述算法要花費

39、很多時間去計算在處理每一條掃描線時，要檢查各多邊形是否和該線相交還要計算多邊形所在平面上很多點的z值為了使這些工作能高效率地進行，可采取類似多邊形掃描轉換的掃描線算法處理。,8.4掃描線Z緩沖器算法,數(shù)據(jù)結構一個多邊形Y筒一個邊Y筒一個多邊形活化表一個邊活化表,,,,,,,,8.4掃描線Z緩沖器算法,建立一個多邊形Y筒--圖8.23是圖8.22的多邊形Y筒每個筒的深度和顯示屏幕行數(shù)相同。根據(jù)多邊形頂點Y坐標最大值來決定

40、放入多邊形Y筒的相應行數(shù)。多邊形Y筒要記錄多邊形所在平面方程ax+by+cz+d=0系數(shù)a，b，c和d，還要記錄和該多邊形在oxy平面上的投影相交的掃描線的條數(shù)Δy，以及多邊形的屬性colour和編號IP。,,,,圖8.22,圖8.23,8.4掃描線Z緩沖器算法,建立一個邊Y筒--圖8.24是圖8.22的邊Y筒每個筒的深度和顯示屏幕行數(shù)相同。根據(jù)邊兩端點較大的Y坐標值為決定放入邊Y筒的相應行數(shù)。邊Y筒中記錄的每一條邊要保存下

41、列信息：和該邊在oxy平面上的投影相交的掃描線條數(shù)Δy，該投影和相鄰的兩條掃描線交點的x坐標的差Δx，(由上到下掃描)該邊所屬多邊形的編號IP及邊的上端點x坐標的值x。,,,,,,,,,圖8.24,圖8.22,8.4掃描線Z緩沖器算法,建立一個多邊形活化表記錄在oxy平面上的投影和當前考慮的掃描線相交的多邊形，以圖8.22為例，當掃描線對應y=10或11時，多邊形活化表只有一個多邊形。當y=8時多邊形活化表如圖8.25。表

42、中的Δy值是已經(jīng)過修改的。（由上到下掃描，故！y=5,和!y=7）,,,圖8.22,圖8.25,8.4掃描線Z緩沖器算法,建立一個邊活化表邊活化表中存放多邊形邊界和掃描線相交的邊對。例如圖8.22中y=6的掃描線上的邊活化表中應有兩個對邊，一是和多邊形Ⅰ在oxy平面上的投影相交的兩條邊另一是和多邊形Ⅱ投影相交的兩條邊。,,,圖8.22,8.4掃描線Z緩沖器算法,邊活化表中每一邊對要保存下列信息,,8.4掃描線Z緩沖器算法,一開始

43、處理最上面的一條掃描線在處理前邊和多邊形的活化表均是空的。已建立圖8.23和圖8.24的兩個Y筒后在處理每條掃描線時要做下列工作 （1）把幀緩沖器相應行置成底色。 （2）z緩沖器的各單元放z的極小值。 （3）檢查多邊形的Y筒，如果有新的多邊形涉及該掃描線，則把它放入多邊形活化表中。 （4）如果有新的多邊形加入多邊形活化表，則要把該多邊形在oxy平面上的投影和掃描線相交的邊對加入邊活化表

44、中。 （5）如果有些邊在這條掃描線處結束了，而其所在的多邊形仍在多邊形活化表內，則可從邊的Y筒中找到該多邊形在oxy平面上的投影和掃描線相交的新的邊或邊對，修改或加到邊的活化表中去。（邊對在邊活化表中的次序是不重要的）。,算法步驟：--掃描,8.4掃描線Z緩沖器算法,下面從形成的活化邊表中取出一個邊對，令zx=zl，對每一個滿足xl≤x≤xr的坐標為（x，y）的象素（y是當前考慮的掃描線高度）從左到右依次作下列處理。先計算

45、這就是對應象素處多邊形所在平面的深度。如果此值比z緩沖器相應單元中存放的值大，則要用它代替z緩沖器相應單元中原來的值，并把幀緩存中相應單元改成這個多邊形的屬性。這項工作要對活化表中的每個邊對都做到，這項工作完成后，幀緩沖器相應行便存放了消隱后的結果。,,算法步驟：-消隱,8.4掃描線Z緩沖器算法,修改后的表便是下一條掃描線的邊活化表。對每一邊對可先計算若Δyl 或Δyr小于0，相應的邊就要從一個邊對中去掉，從邊活化表中找合

46、適的邊來代替。也有可能這兩條邊同時結束于某一點，這說明這一邊對可取消了。邊和下一條掃描線交點的x值可由下式求得多邊形所在平面對應下一條掃描線在x=xl處的深度,,算法步驟：--下面來說明對邊活化表修改的方法,8.4掃描線Z緩沖器算法,對多邊形活化表中每一個多邊形的Δy要做如下修改 當Δy<0時，該多邊形則要從多邊形活化表中刪除。做完這些工作后便可開始下一條掃描線的消隱工作。當把每一條掃描線的消隱工作都完成后，整個消隱

47、工作也就完成了。,算法步驟：--下面來說明對多邊形活化表修改的方法,8.5區(qū)間（跨距）掃描線算法,上節(jié)講的掃描線z緩沖器算法將消隱問題分散到每一條掃描線上去解決，這樣，問題變得較簡單了。但在每個象素處計算多邊形z值的工作量仍是很大的。實際上每條掃描線被各多邊形邊界在oxy平面上的投影分割成為數(shù)不多的區(qū)間，每一個區(qū)間上只顯示一個面，因此，只要在區(qū)間上任一點處，找出在該處z值最大的一個面，這個區(qū)間上的每個象素就用這個面的顏色來顯示。

48、這種做法就是所謂跨距掃描線算法。,8.5區(qū)間（跨距）掃描線算法,設多邊形的邊界在oxy平面上的投影和掃描線交點的橫坐標為xi，這些交點把掃描線分成一個小區(qū)間[xi, i+1]，每個小區(qū)間稱為一個跨距。在每個區(qū)間上最靠近觀察者的那個面就是這個區(qū)間上的可見面。為了在區(qū)間上找到離觀察者最近的面，只要去求出各多邊形（限于那些在oxy平面上的投影和所考慮的掃描線相交的多邊形）所在平面在區(qū)間左端點的z值，找出z值最大的一個面。如果兩個面恰好

49、在左端點相交時，可計算這兩個面在右端點的z值并做比較。,8.7 優(yōu)先級表算法,優(yōu)先級表算法按多邊形離觀察者的遠近來建立一張表距觀察者遠的優(yōu)先級低，近的優(yōu)先級高。如果這張表能正確地建立好，那么只要從優(yōu)先級低的多邊形開始，依次把多邊形的顏色填入幀緩沖存儲器中以形成該多邊形的圖形直到優(yōu)先級最高的多邊形的圖形送入幀緩沖器后，整幅圖就顯示好了。這種算法也稱為油畫家算法因為油畫家繪畫時常先畫底色，然后再一層層往上畫。,8.7 優(yōu)先級表算

50、法,上述算法的困難在于怎樣對多邊形做一個正確的排序。下面給出了一個動態(tài)的方法先根據(jù)每個多邊形頂點z坐標的極小值zmin的大小把多邊形做一個初步的排序。設zmin 最小的多邊形是P，它暫時成為優(yōu)先級最低的一個多邊形，把多邊形序列中其他多邊形記為Q現(xiàn)在先來確定P和其他多邊形Q的關系如果P的頂點z的坐標的極大值P zmax 比某一多邊形Q的頂點坐標的極小值Q zmin 還要小，即P zmax Q zmin，則必須做進一步的檢查，才能

51、確定P和Q的確切關系。,8.7 優(yōu)先級表算法,這種檢查分以下五項。P和Q在oxy平面上投影的邊界盒在x方向上不相交(見圖（a）)P和Q在oxy平面上投影的邊界盒在y方向上不相交(見圖（b）)P的各頂點均在Q的遠離視點的一側(見圖（c）)Q的各頂點均在P的靠近視點的一側(見圖（d）)P和Q在oxy平面上的投影不相交(見圖（e）) 上述五項只要有一項成立，P就不遮擋Q。 由于從第一項至第五項每項檢查所需的工作量是遞增，

52、因此檢查時要按第一至第五項次序進行。,,P,,,,x,y,,Q,,,,,,x,y,,,,Q,,,,Q,,（a）,（b）,（c）,（d）,（e）,8.7 優(yōu)先級表算法,如果上述五項檢查均不成立，則不能確定P不遮擋Q，這時要在多邊形序列中把P和Q交換一下次序，并對交換后的序列中優(yōu)先級最低的多邊形P′檢查，看P′是否遮擋別的多邊形。,8.7 優(yōu)先級表算法,在圖8.32，不可能找到一個多邊形不遮擋另一個多邊形。在圖8.33雖然P并不遮

53、擋Q，得它也不能使上述五項檢查成立。,圖8.32,圖8.33,8.7 優(yōu)先級表算法,對這兩種情況，如果不采取任何措施，而只在多邊形序列中交換P和Q的位置，這時新的P和Q仍不能滿足上述五項檢查，因而這樣做下去只會使多邊形不斷進行交換。為了避免這種現(xiàn)象產生，在優(yōu)先級最低的多邊形和其他多邊形交換時，要對原來的優(yōu)先級最低的多邊形做一標志，當有標志的多邊形再換成優(yōu)先級最低的多邊形時，則說明出現(xiàn)了圖 中的現(xiàn)象，這時可把P沿Q平面一分為二，見

54、圖8.33。把多邊形序列中原多邊形P從序列中刪掉，而把P分成的兩個多邊形加入多邊形表中。采用這種方法后，但可得到一個正確排序的多邊形的序列。,8.7 優(yōu)先級表算法,這種方法對有的多邊形互相貫串時也可適用。優(yōu)先級表算法可以較好地解決透明或半透明物體的存在，也可采用反走樣算法改善多邊形邊界的顯示效果。這個算法可推廣到解決三維立體的消隱問題。,8.7 優(yōu)先級表算法,優(yōu)先級表算法對解決動態(tài)顯示有很大的好處，例如飛機駕駛員訓練員在模擬