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

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

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

3、維場(chǎng)景中的每一個(gè)物體：判定場(chǎng)景中的所有可見表面；用可見表面的顏色填充相應(yīng)的像素以構(gòu)成圖形；,隱藏面和隱藏線的消除有兩種基本的算法,假定1：,隱藏線和隱藏面消除所討論的對(duì)象是一個(gè)三維圖形，消隱后要在二維空間中表示出來(lái)，因此消隱后顯示的圖形將和三維空間至二維空間的投影方式有關(guān)。下面討論消隱算法時(shí)，都假定投影平面就是oxy平面，投影方向?yàn)樨?fù)z軸方向的垂直投影。如果不是這種情況，可對(duì)消隱的對(duì)象先作變換，變成這種情況，然后再作消隱計(jì)算。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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