ch-隱藏面和隱藏線的消除實(shí)用

會計(jì)學(xué)1ch——隱藏面和隱藏線的消除實(shí)用隱藏面和隱藏線的消除是計(jì)算機(jī)圖形學(xué)中的一個(gè)基本問題。由于存在不透光的物體，因此阻擋了來自某些物體部分的光線到達(dá)觀察者，這些物體部分成為隱藏部分，隱藏部分是不可見的。為了使計(jì)算機(jī)生成的圖能真實(shí)地反映這一情況，必須把隱藏的部分從圖中消除。如果不把隱藏的線或面消除，還可能發(fā)生對圖的錯誤理解。

圖8.1兩種理解第1頁/共61頁基于圖像空間的方法以構(gòu)成圖像的每一個(gè)像素為處理單元，對場景中的所有表面，確定相對于觀察點(diǎn)是可見的表面，用該表面的顏色填充該像素。該算法多用于面消隱。算法的簡單描述如下：對于圖像中的每一個(gè)像素：在和投影點(diǎn)到像素連線相交的表面中，找到離觀察點(diǎn)最近的表面；用該表面上交點(diǎn)處的顏色填充該像素隱藏面和隱藏線的消除有兩種基本的算法第2頁/共61頁基于物體空間的方法是以三維場景中的物體對象為處理單元，在所有對象之間進(jìn)行比較，除去完全不可見的物體和物體上不可見的部分。該算法多用于線消隱，也用于面消隱。算法的簡單描述如下：對于三維場景中的每一個(gè)物體：判定場景中的所有可見表面；用可見表面的顏色填充相應(yīng)的像素以構(gòu)成圖形；隱藏面和隱藏線的消除有兩種基本的算法第3頁/共61頁假定1：隱藏線和隱藏面消除所討論的對象是一個(gè)三維圖形，消隱后要在二維空間中表示出來，因此消隱后顯示的圖形將和三維空間至二維空間的投影方式有關(guān)。下面討論消隱算法時(shí)，都假定投影平面就是oxy平面，投影方向?yàn)樨?fù)z軸方向的垂直投影。如果不是這種情況，可對消隱的對象先作變換，變成這種情況，然后再作消隱計(jì)算。在投影平面就是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）第4頁/共61頁假定2：本章說明的各種消隱方法都假定構(gòu)成對象的不同面不能相互貫穿，見圖8.1，也不能有循環(huán)遮擋的情況，如果有這種情況，可把它們剖分成互不貫串和不循環(huán)遮擋的情況。例如用圖8.2（b）中的虛線便可把原來循環(huán)遮擋的三個(gè)平面，分割成不互相循環(huán)遮擋的四個(gè)面。

圖8.2貫穿和循環(huán)遮擋第5頁/共61頁8.1多面體的隱藏線消除

設(shè)有多個(gè)互不相交的多面體，對它們的消隱問題，和他們的顯示方式有關(guān)。討論隱藏線消除問題，總假定它們是用線框方式來表示的。在這種方式下多面體用棱來表示。這時(shí)隱藏線便是某些不可見的棱或棱的一部分。如果能把各棱上可見和不可見部分的分界點(diǎn)找到，消隱問題也就迎刃而解了。這些分界點(diǎn)都是多面體的各棱在oxy平面上投影間的交點(diǎn)，見圖8.3。這樣，問題就轉(zhuǎn)化成了在oxy平面上求很多直線的交點(diǎn)的計(jì)算。

圖8.3第6頁/共61頁8.1多面體的隱藏線消除在oxy平面上求很多直線的交點(diǎn)的計(jì)算。如果消隱對象有N條棱，用兩兩求交的方法求所有交點(diǎn)的工作量為O（N2）。當(dāng)N很大時(shí)，這個(gè)工作量是可觀的。要提高算法的效率，就要設(shè)法減少求交的工作量。實(shí)際上交點(diǎn)個(gè)數(shù)遠(yuǎn)小于O（N2），例如圖8.3的多面體有15條邊，如果不計(jì)棱端點(diǎn)處的交點(diǎn)，棱在oxy平面上的投影相互間只有5個(gè)交點(diǎn)。這說明有很多棱在oxy平面上的投影相互間并不相交。問題在于如何能預(yù)先知道它們是不相交的，從而把它們排擠在求交計(jì)算之外。

第7頁/共61頁8.1多面體的隱藏線消除減少求交計(jì)算的若干方法：把后向面全部去掉

用邊界盒排除不相交的線段求交。

在后向面被刪除后，如果兩個(gè)相鄰的多邊形的公共邊都在兩個(gè)多邊形的凸包上，則這兩個(gè)多邊形不會發(fā)生一個(gè)遮擋另一個(gè)的現(xiàn)象。因而在考慮一個(gè)多邊形的邊的顯示時(shí)，可以不考慮另一個(gè)多邊形對它的影響。

第8頁/共61頁8.1多面體的隱藏線消除去掉后向面把內(nèi)法線方向背向視點(diǎn)的面稱為前向面，如圖8.3中的IJFGH，F(xiàn)ABG，HCDI和IDEJ所在的面均為前向面。其余的面稱為后向面，例如圖8.3中JEAF和DEABC所在的面均為后向面，后向面總是看不見的，不會僅由于后向面的遮擋，而使別的棱成為不可見，因此可把后向面全部去掉，這不影響消隱結(jié)果。

第9頁/共61頁8.1多面體的隱藏線消除設(shè)多邊形F的頂點(diǎn)為v1,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所在的面為前向面。第10頁/共61頁8.1多面體的隱藏線消除用邊界盒排除不相交的線段求交

第11頁/共61頁8.1多面體的隱藏線消除在后向面被刪除后，如果兩個(gè)相鄰的多邊形的公共邊都在兩個(gè)多邊形的凸包上，則這兩個(gè)多邊形不會發(fā)生一個(gè)遮擋另一個(gè)的現(xiàn)象。這時(shí)，在考慮一個(gè)多邊形的邊的顯示時(shí)，可以不考慮另一個(gè)多邊形對它的影響。

第12頁/共61頁8.1多面體的隱藏線消除隱藏線消除實(shí)際計(jì)算過程：要對體一個(gè)一個(gè)來考慮，如考慮體A的顯示時(shí)，先確定可能遮擋A的那些體（包括體A本身），對體A的每個(gè)多邊形G，要找出可能遮擋它的所有多邊形--這些多邊形要從可能遮擋A的所有體的表面多邊形中去找。然后對多邊形G的每一條邊L找出可能遮擋它的所有多邊形---這些多邊形要從可能遮擋多邊形G的所有多邊形中去找。（以上各步均采用邊界盒方法）找到所有可能遮擋邊L的多邊形后，便可求L和這些多邊形的交點(diǎn)，并決定L的可見部分。

L第13頁/共61頁8.1多面體的隱藏線消除

設(shè)邊L的二端點(diǎn)頂點(diǎn)是vi和vj，對邊vivj（即L）和每一個(gè)可能遮擋它的多邊形，都要作下列計(jì)算和判斷，以確定其隱藏關(guān)系。如果vi和vj都在多邊形所在平面靠近觀察者的一側(cè)則這個(gè)多邊形不能遮擋直線段vivj，這時(shí)沒有必要再考慮vivj和這個(gè)多邊形的關(guān)系。

如果vi和vj不都在多邊形所在平面靠近觀察者的一側(cè)，且vivj和多邊形在oxy平面的投影之間有交點(diǎn)，那么把vivj和多邊形的邊界投影到oxy平面上，求出它們的投影之間的交點(diǎn)。對每一個(gè)交點(diǎn)還要判斷它在vivj上的對應(yīng)點(diǎn)是在多邊形前面還是后面，只有在多邊形后面，交點(diǎn)才要保留。如圖8.6中邊v1v2和多邊形ABCD在oxy平面上的投影雖然有交點(diǎn)Q，但它在v1v2上的對應(yīng)點(diǎn)v卻在多邊形的前方，這種交點(diǎn)可不考慮。如果vivj和多邊形在oxy平面的投影之間沒有交點(diǎn)，那么，這時(shí)要判斷vi或vj在oxy平面上的投影是否在多邊形投影的內(nèi)部，如果在內(nèi)部，則vivj就會整個(gè)被這個(gè)多邊形所遮擋住了。

圖8.6第14頁/共61頁現(xiàn)在來說明確定L的可見部分的具體計(jì)算過程：（1）確定L頂點(diǎn)處的與遮擋多邊形的前后位置關(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在多邊形所在平面的后面。其中第15頁/共61頁8.1多面體的隱藏線消除（2）確定L與遮擋多邊形的交點(diǎn)同遮擋多邊形的前后位置關(guān)系：為了判斷邊vivj和多邊形在oxy平面的投影之間是否有交點(diǎn)，可首先計(jì)算求邊vivj和多邊形的邊界在oxy平面上投影的交點(diǎn)，我們可以把vivj的投影線段用參數(shù)方程表示:多邊形上任一邊的投影用用參數(shù)方程表示:求交點(diǎn)時(shí)解方程

可得

其中（8.9）只有當(dāng)0≤l≤1和0≤t≤1時(shí)線段和線段vivj在oxy平面上的投影才有交點(diǎn)為了判斷vIvj上對應(yīng)交點(diǎn)的點(diǎn)是在多邊形所在平面的前面還是后面，則要去比較 和，若前者大于后者，則vivj上交點(diǎn)的對應(yīng)點(diǎn)在多邊形所在平面的前面，否則在后面。

第16頁/共61頁8.1多面體的隱藏線消除（3）確定交點(diǎn)和多邊形的關(guān)系——是內(nèi)點(diǎn)還是出點(diǎn)

：由式（8.9）可知,其中（）z是指向量在z軸上的投影。當(dāng)<0時(shí)，QiQj由多邊形外進(jìn)入多邊形內(nèi)（該交點(diǎn)稱為進(jìn)點(diǎn)），當(dāng)>0時(shí)，QiQj由多邊形內(nèi)離開多邊形到多邊形外（該交點(diǎn)稱為出點(diǎn)）。這個(gè)信息也要和交點(diǎn)的信息一起保存起來。

第17頁/共61頁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)，否則就在多邊形外。但正確地找到交點(diǎn)的個(gè)數(shù)并不容易。

如圖8.8中點(diǎn)Q6處，由于舍入誤差，計(jì)算時(shí)可能認(rèn)為Q5Q6，Q6Q7和QiF均有交點(diǎn)，也可能算出一個(gè)交點(diǎn)或沒有求出交點(diǎn)，不同的交點(diǎn)數(shù)可得到完全不同的結(jié)果。----需要特殊處理

圖8.8第18頁/共61頁8.1多面體的隱藏線消除（5）確定L的可見部分這里引入不可見階ivord的概念它是一個(gè)數(shù)字，是某個(gè)確定的點(diǎn)的屬性，代表了邊上從該點(diǎn)到下一個(gè)交點(diǎn)的部分被幾個(gè)多邊形遮擋。這里要分兩步來做：Step1.確定邊QiQj頂點(diǎn)處的不可見階

Step2.確定邊QiQj與遮擋多邊形交點(diǎn)處的不可見階。

第19頁/共61頁8.1多面體的隱藏線消除（5）確定L的可見部分--Step1.確定邊QiQj頂點(diǎn)處的不可見階首先將Qi處的ivord設(shè)置為0，對每一個(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)，則ivord不變。事實(shí)上Qi處的ivord反映了有幾個(gè)多邊形遮擋由Qi到QiQj與所有多邊形的所有交點(diǎn)中距離Qi最近的交點(diǎn)形成的線段，若Qi處不可見階為0，則QiQj從l=0至l=l1段為可見，否則為不可見。

圖8.9第20頁/共61頁8.1多面體的隱藏線消除（5）確定L的可見部分--Step2.確定邊QiQj與遮擋多邊形交點(diǎn)處的不可見階。

假設(shè)直線QiQj和所有的多邊形共有n個(gè)的交點(diǎn)，將直線與所有多邊形的交點(diǎn)按著交點(diǎn)參數(shù)的大小排序，形成統(tǒng)一的交點(diǎn)序列下面我們計(jì)算的不可見階ivord,注意這里L(fēng)0不可見階就是Qi的不可見階。首先將Li的不可見階ivord設(shè)置Li-1的不可見階如果Li處的交點(diǎn)為進(jìn)點(diǎn)，說明該交點(diǎn)所在的多邊形不遮擋由參數(shù)Li-1

和Li所決定的直線段，而遮擋由參數(shù)Li

和Li+1所決定的直線段。因此Li的不可見階加1如果Li處的交點(diǎn)為出點(diǎn)，說明該交點(diǎn)所在的多邊形遮擋由參數(shù)Li-1

和Li所決定的直線段，而不遮擋由參數(shù)參數(shù)Li

和Li+1所決定的直線段。因此Li的不可見階減1若Li處不可見階為0，則由參數(shù)Li

和Li+1所決定的直線段是可見的，否則為不可見。第21頁/共61頁8.3區(qū)域子分算法

討論一個(gè)面或面的一部分可見與否。

為了減少計(jì)算量，可先去掉所有的后向面。區(qū)域子分算法（warnock）是一種所謂分而治之的算法。整個(gè)屏幕稱為窗口，分而治之算法是一個(gè)遞推的四等分過程，每一次把矩形的窗口等分成四個(gè)相等的小矩形，分成的矩形也稱為窗口。每一次子分，均要把要顯示的多邊形和窗口的關(guān)系作一判斷。第22頁/共61頁8.3區(qū)域子分算法這種關(guān)系可有以下四種，即

多邊形包圍了窗口多邊形和窗口相交窗口包圍了多邊形窗口和多邊形分離第23頁/共61頁8.3區(qū)域子分算法在窗口和每個(gè)多邊形的關(guān)系確定之后，有些窗口內(nèi)的圖形便可顯示了。它們屬于下列三種情況之一。所有多邊形都和窗口分離，這時(shí)只要把窗口內(nèi)所有的象素填上背景顏色。只有一個(gè)多邊形和窗口相交，或這個(gè)多邊形包含在窗口內(nèi)。這時(shí)先對窗口內(nèi)每一象素填上背景顏色，再對窗口內(nèi)多邊形部分用掃描線算法填色只有一個(gè)多邊形和窗口相交，這個(gè)多邊形把窗口整個(gè)包圍在內(nèi)，或雖有幾個(gè)多邊形和窗口相交，但離觀察者最近的一個(gè)多邊形包圍了整個(gè)窗口，這時(shí)把整個(gè)窗口填上離觀察者最近的那個(gè)多邊形的顏色。對上述三種情況的窗口來說，圖已可畫出，因而不必再分細(xì)了。

第24頁/共61頁8.3區(qū)域子分算法對上述三種情況不成立的窗口再一分為四，見圖8.18。分得的窗口重復(fù)上述的處理。對不能處理的窗口再一分為四。窗口的邊長越分越短，分了若干次后，窗口的邊長就和一個(gè)象素的寬度一樣了，這時(shí)這個(gè)窗口對應(yīng)的象素的顏色可取成最靠近觀察者的多邊形的顏色，或和這個(gè)窗口相交的多邊形顏色的平均值。

圖8.18第25頁/共61頁8.3區(qū)域子分算法Divide-Conqer算法的思想雖然簡單，具體實(shí)現(xiàn)時(shí)的細(xì)節(jié)要處理好，才能提高效率。下面介紹一些有效的處理方法。對所有的多邊形按其頂點(diǎn)的z坐標(biāo)最大值（即最靠近觀察者的一個(gè)頂點(diǎn)的z坐標(biāo)值）來排序。對一個(gè)具體窗口來說，隨著窗口不斷地被細(xì)分，這個(gè)多邊形序列的元素將越來越少。窗口變小了，用邊界盒的辦法就可能判定一些多邊形和這個(gè)窗口是無交的，這些多邊形也不會和這個(gè)窗口的子窗口相交，因此對這個(gè)窗口來說這些多邊形可從多邊形序列中排除。此外窗口變小了，就可能被一個(gè)多邊形包含在內(nèi)，這樣在這個(gè)窗口內(nèi)，比這個(gè)多邊形遠(yuǎn)離觀察者的多邊形都會被這個(gè)多邊形所遮擋，對這個(gè)窗口的子窗口來說這些多邊形也被遮擋了，因此對這個(gè)窗口來說，這些被遮擋的多邊形可從序列中去掉。第26頁/共61頁8.3區(qū)域子分算法

對于不能用邊界盒辦法判斷和窗口不相交的多邊形，則要經(jīng)過計(jì)算去確定它們之間的關(guān)系。這時(shí)可以采用與第四章中多邊形裁剪算法類似的方法去確定多邊形的窗口的邊界是否有交點(diǎn)。有交點(diǎn)時(shí)，說明多邊形和窗口有交。無交點(diǎn)時(shí)還要去確定它們是分離還是有包含關(guān)系。第27頁/共61頁8.3區(qū)域子分算法在找到了一個(gè)多邊形包圍所考慮的窗口后，就要把它和多邊形序列中其它多邊形離觀察者的遠(yuǎn)近進(jìn)行比較，把被它遮擋的多邊形從序列中去掉。為此可把窗口四個(gè)頂點(diǎn)坐標(biāo)的x,y值代入那個(gè)包圍窗口的多邊形所在的平面方程，以求出對應(yīng)四個(gè)頂點(diǎn)處該平面的z坐標(biāo)值。以zmin記這四個(gè)z坐標(biāo)值的最小值，對序列中第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所在的平面方程，求出H點(diǎn)處的坐標(biāo)z值zH，若zH

>zG，則AB在窗口內(nèi)遮擋了多邊形EF。

Divide-Conqer算法的具體實(shí)現(xiàn)：圖8.19第28頁/共61頁8.3區(qū)域子分算法區(qū)域子分法提出來后，有不少文章提出了一些改進(jìn)。參考文章[88]中提出的方法是用多邊形的邊界來對窗口作劃分，這樣做的目的是盡量減少對窗口劃分的次數(shù)。

用多邊形的邊界來對窗口作劃分的方法第29頁/共61頁8.3區(qū)域子分算法用多邊形的邊界來對窗口作劃分的方法--算法思想：先用某種方法對各多邊形在深度方向作初步的排序，例如可按多邊形頂點(diǎn)z坐標(biāo)值的最大值zmaxi來排序，zmaxi大的排在前面?，F(xiàn)把多邊形序列中的第一個(gè)多邊形（裁剪多邊形）取為窗口。多邊形序列中的其它的多邊形都要被這窗口裁剪。裁剪的結(jié)果要建立兩個(gè)多邊形序列表，一個(gè)是窗口內(nèi)的多邊形表，一個(gè)是窗口外的多邊形表。每一個(gè)被裁剪的多邊形裁剪后位于窗口內(nèi)的部分放入內(nèi)部表中位于窗口外的部分放在外部表中。圖8.21（a）和圖8.21（b）分別為圖8.20中多邊形的內(nèi)部表和外部表，圖8.20中多邊形1作為窗口。圖8.20圖8.21(a)(b)第30頁/共61頁8.3區(qū)域子分算法下面要來確定裁剪多邊形（即取為窗口的那個(gè)多邊形）是否比內(nèi)部表中的多邊形更靠近觀察者求出裁剪多邊形各頂點(diǎn)坐標(biāo)z的極小值zminc,求出內(nèi)部多邊形各頂點(diǎn)坐標(biāo)z的極大值zmaxi對那些滿足

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

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

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

8.4Z緩沖器算法圖形消隱和生成的過程就是給幀緩沖器和z緩沖器中相應(yīng)單元填值的過程在把顯示物體的每個(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)單元的值，則說明對應(yīng)象素已顯示了物體上一個(gè)點(diǎn)的屬性，該點(diǎn)比要考慮的點(diǎn)更接近觀察者。這樣，無論幀緩沖器或z緩沖器相應(yīng)單元的值均不應(yīng)改變。對顯示物體的每一個(gè)面上的每一個(gè)點(diǎn)都做上述處理后，便可得到消除了隱藏面的圖。

第36頁/共61頁

8.4Z緩沖器算法算法的優(yōu)點(diǎn)簡單、可靠不需要對顯示物體的面預(yù)先進(jìn)行排序算法的缺點(diǎn)要很大的z緩沖器工作量較大：顯示物體的表面和象素對應(yīng)的每一個(gè)點(diǎn)處都要計(jì)算它的z值

為了克服第一個(gè)缺點(diǎn)，可把整個(gè)平面分成若干區(qū)域，一區(qū)一區(qū)來顯示，這樣z緩沖器的單元數(shù)只要等于屏幕上一個(gè)區(qū)域的象素個(gè)數(shù)。如果把這個(gè)區(qū)域取成屏幕上一行，就得到了掃描線z緩沖器算法。

第37頁/共61頁8.4掃描線Z緩沖器算法

掃描線z緩沖器

--算法思想z緩沖器的單元數(shù)可以取成和一行上的象素?cái)?shù)目相同。從最上面的一條掃描線開始工作，向下對每一條掃描線作處理。對每一條掃描線來說，把相應(yīng)的幀緩沖器單元置成底色，在z緩沖器中存放z的極小值。

第38頁/共61頁

8.4掃描線Z緩沖器算法掃描線z緩沖器--算法思想對每個(gè)多邊形檢查它在oxy平面上的投影和當(dāng)前的掃描是否相交，若不相交，則不考慮該多邊形。如果相交，則掃描線和多邊形邊界的交點(diǎn)一事實(shí)上是成對地出現(xiàn)對每對交點(diǎn)中間的象素計(jì)算多邊形所在平面對應(yīng)點(diǎn)的深度（即z值），并和z緩沖器中相應(yīng)單元存放的深度值作比較。若前者大于后者，則z緩沖器的相應(yīng)單元內(nèi)容要被求得的平面深度代替，幀緩沖器相應(yīng)單元的內(nèi)容也要換成該平面的屬性。對所有的多邊形都作上述處理后，幀緩沖器中這一行的值便反應(yīng)了消隱后的圖形。對幀緩沖器每一行的單元都填上相應(yīng)內(nèi)容后也就得到了整個(gè)消隱后的圖。第39頁/共61頁8.4掃描線Z緩沖器算法上述算法要花費(fèi)很多時(shí)間去計(jì)算在處理每一條掃描線時(shí)，要檢查各多邊形是否和該線相交還要計(jì)算多邊形所在平面上很多點(diǎn)的z值為了使這些工作能高效率地進(jìn)行，可采取類似多邊形掃描轉(zhuǎn)換的掃描線算法處理。

第40頁/共61頁8.4掃描線Z緩沖器算法數(shù)據(jù)結(jié)構(gòu)一個(gè)多邊形Y筒一個(gè)邊Y筒一個(gè)多邊形活化表一個(gè)邊活化表xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP2第41頁/共61頁8.4掃描線Z緩沖器算法建立一個(gè)多邊形Y筒--圖8.23是圖8.22的多邊形Y筒每個(gè)筒的深度和顯示屏幕行數(shù)相同。根據(jù)多邊形頂點(diǎn)Y坐標(biāo)最大值來決定放入多邊形Y筒的相應(yīng)行數(shù)。多邊形Y筒要記錄多邊形所在平面方程ax+by+cz+d=0系數(shù)a，b，c和d，還要記錄和該多邊形在oxy平面上的投影相交的掃描線的條數(shù)Δy，以及多邊形的屬性colour和編號IP。

圖8.22圖8.23第42頁/共61頁8.4掃描線Z緩沖器算法建立一個(gè)邊Y筒--圖8.24是圖8.22的邊Y筒每個(gè)筒的深度和顯示屏幕行數(shù)相同。根據(jù)邊兩端點(diǎn)較大的Y坐標(biāo)值為決定放入邊Y筒的相應(yīng)行數(shù)。邊Y筒中記錄的每一條邊要保存下列信息：和該邊在oxy平面上的投影相交的掃描線條數(shù)Δy，該投影和相鄰的兩條掃描線交點(diǎn)的x坐標(biāo)的差Δx，(由上到下掃描)該邊所屬多邊形的編號IP及邊的上端點(diǎn)x坐標(biāo)的值x。

圖8.24圖8.22第43頁/共61頁8.4掃描線Z緩沖器算法建立一個(gè)多邊形活化表記錄在oxy平面上的投影和當(dāng)前考慮的掃描線相交的多邊形，以圖8.22為例，當(dāng)掃描線對應(yīng)y=10或11時(shí)，多邊形活化表只有一個(gè)多邊形。當(dāng)y=8時(shí)多邊形活化表如圖8.25。表中的Δy值是已經(jīng)過修改的。（由上到下掃描，故！y=5,和!y=7）圖8.22圖8.25第44頁/共61頁8.4掃描線Z緩沖器算法建立一個(gè)邊活化表邊活化表中存放多邊形邊界和掃描線相交的邊對。例如圖8.22中y=6的掃描線上的邊活化表中應(yīng)有兩個(gè)對邊，一是和多邊形Ⅰ在oxy平面上的投影相交的兩條邊另一是和多邊形Ⅱ投影相交的兩條邊。xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP2圖8.22第45頁/共61頁8.4掃描線Z緩沖器算法邊活化表中每一邊對要保存下列信息xl左交點(diǎn)的x坐標(biāo)值Δxl左交點(diǎn)所在邊和兩相鄰掃描線交點(diǎn)的x坐標(biāo)之差Δyl以和左交點(diǎn)所在邊相交的掃描線條數(shù)為初值，以后每處理一條掃描線減1xr右交點(diǎn)的x坐標(biāo)值Δxr右交點(diǎn)所在邊和兩相鄰掃描線交點(diǎn)的x坐標(biāo)之差Δyr以和右交點(diǎn)所在邊相交的掃描線條數(shù)為初值，以后每處理一條掃描線減1zl左交點(diǎn)處多邊形所在平面的深度值Δzx沿掃描線向右走過一個(gè)象素時(shí)，多邊形所在平面深度的增量。對方程為ax+by+cz+d=0的平面來說Δzx=–a/c（c≠0）Δzy沿y方向向下移過一根掃描線時(shí)，多邊形所在平面深度的增量。對方程為ax+by+cz+d=0的平面來說Δzy=b/c（c≠0）IP所在多邊形的編號xl=4,!xl=1,!yl=3,xr=7,!xr=0,!yr=3,zl1,zx1,zy1,IP1xl=5,!xl=5/6,!yl=5,xr=9/8,!xr=3/8,!yr=5,zl2,zx2,zy2,IP2第46頁/共61頁8.4掃描線Z緩沖器算法一開始處理最上面的一條掃描線在處理前邊和多邊形的活化表均是空的。已建立圖8.23和圖8.24的兩個(gè)Y筒后在處理每條掃描線時(shí)要做下列工作

（1）把幀緩沖器相應(yīng)行置成底色。（2）z緩沖器的各單元放z的極小值。（3）檢查多邊形的Y筒，如果有新的多邊形涉及該掃描線，則把它放入多邊形活化表中。（4）如果有新的多邊形加入多邊形活化表，則要把該多邊形在oxy平面上的投影和掃描線相交的邊對加入邊活化表中。（5）如果有些邊在這條掃描線處結(jié)束了，而其所在的多邊形仍在多邊形活化表內(nèi)，則可從邊的Y筒中找到該多邊形在oxy平面上的投影和掃描線相交的新的邊或邊對，修改或加到邊的活化表中去。（邊對在邊活化表中的次序是不重要的）。算法步驟：--掃描第47頁/共61頁8.4掃描線Z緩沖器算法下面從形成的活化邊表中取出一個(gè)邊對，令zx=zl，對每一個(gè)滿足xl≤x≤xr的坐標(biāo)為（x，y）的象素（y是當(dāng)前考慮的掃描線高度）從左到右依次作下列處理。先計(jì)算這就是對應(yīng)象素處多邊形所在平面的深度。如果此值比z緩沖器相應(yīng)單元中存放的值大，則要用它代替z緩沖器相應(yīng)單元中原來的值，并把幀緩存中相應(yīng)單元改成這個(gè)多邊形的屬性。這項(xiàng)工作要對活化表中的每個(gè)邊對都做到，這項(xiàng)工作完成后，幀緩沖器相應(yīng)行便存放了消隱后的結(jié)果。

算法步驟：-消隱第48頁/共61頁8.4掃描線Z緩沖器算法修改后的表便是下一條掃描線的邊活化表。對每一邊對可先計(jì)算

若Δyl

或Δyr小于0，相應(yīng)的邊就要從一個(gè)邊對中去掉，從邊活化表中找合適的邊來代替。也有可能這兩條邊同時(shí)結(jié)束于某一點(diǎn)，這說明這一邊對可取消了。邊和下一條掃描線交點(diǎn)的x值可由下式求得多邊形所在平面對應(yīng)下一條掃描線在x=xl處的深度

算法步驟：--下面來說明對邊活化表修改的方法第49頁/共61頁8.4掃描線Z緩沖器算法對多邊形活化表中每一個(gè)多邊形的Δy要做如下修改

當(dāng)Δy<0時(shí)，該多邊形則要從多邊形活化表中刪除。做完這些工作后便可開始下一條掃描線的消隱工作。當(dāng)把每一條掃描線的消隱工作都完成后，整個(gè)消隱工作也就完成了。算法步驟：--下面來說明對多邊形活化表修改的方法第50頁/共61頁8.5區(qū)間（跨距）掃描線算法

上節(jié)講的掃描線z緩沖器算法將消隱問題分散到每一條掃描線上去解決，這樣，問題變得較簡單了。但在每個(gè)象素處計(jì)算多邊形z值的工作量仍是很大的。實(shí)際上每條掃描線被各多邊形邊界在oxy平面上的投影分割成為數(shù)不多的區(qū)間，每一個(gè)區(qū)間上只顯示一個(gè)面，因此，只要在區(qū)間上任一點(diǎn)處，找出在該處z值最大的一個(gè)面，這個(gè)區(qū)間上的每個(gè)象素就用這個(gè)面的顏色來顯示。這種做法就是所謂跨距掃描線算法。第51頁/共61頁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è)面恰好在左端點(diǎn)相交時(shí)，可計(jì)算這兩個(gè)面在右端點(diǎn)的z值并做比較。

第52頁/共61頁8.7優(yōu)先級表算法

優(yōu)先級表算法按多邊形離觀察者的遠(yuǎn)近來建立一張表距觀察者遠(yuǎn)的優(yōu)先級低，近的優(yōu)先級高。如果這張表能正確地建立好，那么只要從優(yōu)先級低的多邊形開始，依次把多邊形的顏色填入幀緩沖存儲器中以形成該多邊形的圖形直到優(yōu)先級最高的多邊形的圖形送入幀緩沖器后，整幅圖就顯示好了。這種算法也稱為油畫家算法因?yàn)橛彤嫾依L畫時(shí)常先畫底色，然后再一層層往上畫。

第53頁/共61頁8.7優(yōu)先級表算法上述算法的困難在于怎樣對多邊形做一個(gè)正確的排序。下面給出了一個(gè)動態(tài)的方法先根據(jù)每個(gè)多邊形頂點(diǎn)z坐標(biāo)的極小值zmin的大小把多邊形做一個(gè)初步的排序。設(shè)zmin

最小的多邊形是P，它暫時(shí)成為優(yōu)先級最低的一個(gè)多邊形，把多邊形序列中其他多邊形記為Q現(xiàn)在先來確定P和其他多邊形Q的關(guān)系如果P的頂點(diǎn)z的坐標(biāo)的極大值Pzmax

比某一多邊形Q的頂點(diǎn)坐標(biāo)的極小值