西安交通大學(xué)計算機圖形學(xué)課件(15)

1、1第13章 可見面判別算法楊新宇Chapter 13Chapter 132可見面判別算法w在生成真實感圖形時，考慮最多的是如何判別出從某一特定觀察位置所能看到的場景中的內(nèi)容。w目前，已經(jīng)有多種解決該間題的途徑，人們?yōu)椴煌膽?yīng)用場合開發(fā)出了相當(dāng)數(shù)目的算法，從而有效地判別可見物體。其中，一些算法的內(nèi)存開銷較大，有些算法的處理時間較長，而其他一些算法則僅針對某些特定的物體類型。w為某個特定的應(yīng)用背景選擇算法時，應(yīng)考慮場景復(fù)雜度、待顯示物體的類型、顯示設(shè)備及最終畫面是靜態(tài)還是動態(tài)等因素。w這些算法通常稱為可見面判別（visible-suface detection ）算法，有時也稱為隱藏面消除算法，盡

2、管判別可見面與隱藏面之間有細微的差別。w例如，在顯示線框方式的圖形時，可能僅僅希望使用虛線輪廓或其他方式來顯示隱藏面而不必消除它們，從而保留物體的外形特征。w本章介紹應(yīng)用于三維場景中的最常用的一些可見面判別算法。Chapter 133主要內(nèi)容w可見面判別算法的分類w后向面判別w深度緩沖器算法wA緩沖器算法w掃描線算法w深度排序算法wBSP樹算法w區(qū)域細分算法八叉樹算法光線投射算法曲面線框算法可見性判別函數(shù)Chapter 13413-1可見面判別算法的分類w 可見面判別算法的分類，通常是根據(jù)其處理場景時是直接對物體定義進行處理還是處理它們的投影圖像。這兩種類型分別稱為物空間算法和像空間算法。n物

3、空間算法物空間算法：將場景中的各物體和物體的各個組成部分相互進行比較，從而最終判別出哪些面是可見的；n像空間算法像空間算法 ：在投影平面上逐點判斷各像素所對應(yīng)的可見面。Chapter 135w 第10 章曾介紹過一種快速簡便的、判別多面體后向面的物空間算法，它建立在內(nèi)外測試法的基礎(chǔ)之上。 w 假設(shè)有一點（x , y , z ）和一個平面參數(shù)為A 、B 、C 、D 的多邊形面，如果： Ax+By+Cz + D 0 則該多邊形為后向面。 w另外，若將物體描述轉(zhuǎn)換至投影坐標(biāo)系中，若觀察方向平行于觀察坐標(biāo)系中的Zv軸，則V = ( 0 , 0 ，Vz），且 V N =VzC 因此，只須考查法向量N 的

4、z 分量C 的符號。 Chapter 137后向面判別w 在一個沿著Zv軸反向觀察的右手觀察系統(tǒng)中（圖13 . 2 ) ，若C 0 ，則該多邊形為一后向面。同時，無法觀察到法向量的z 分量C =0 的所有多邊形面，因為觀察方向與該面相切。這樣，一旦某多邊形面的法向量的z分量值： C depth (x, y)，則 其中， 為背景屬性， 為表面像素點（x，y）上的投影屬性值。backgnd,0,depth(x y),refresh(x y)I,surfdepth(x,y)z,refresh(x y)I(x,y)backgndI),(surfyxIChapter 1311深度緩沖器算法w 某多邊形面

5、上點 (x, y) 的對應(yīng)深度值可由平面方程計算如下： w 其相鄰點（x+1，y）的深度值可由下列等式得到： 或CDByx AzCDByx)1A(zCAz zChapter 131213-4 A 緩沖器算法 wA 緩沖器算法是深度緩沖器算法的延伸（“ z-buffer ”中的z 則表示深度）。此處，A 表示反走樣（antialiased ）、區(qū)域平均（area -averaged ）和累計緩沖器（accumulation-buffer ）。Lucasfilm在曲面繪制系統(tǒng)REYES ( Renders Everything You Ever Saw）中成功實現(xiàn)了該算法。w深度緩沖器算法的一個缺

6、點是：它在每個像素點只能找到一個可見面。即它只能處理非透明表面，而無法處理多個表面的累計強度值，對于圖13 . 8 所示的透明表面，這種處理又是必需的。 Chapter 1313A緩沖器算法w A 緩沖器算法對深度緩沖器進行了擴充，使其每一個位置均對應(yīng) 于一個表面鏈表。因此，不僅可以考慮各像素點處多個表面的強 度值，還可以對物體的邊界進行反走樣處理。 w A 緩沖器中每個單元均包含兩個域：l深度域 存儲一個正的或負的實數(shù)； l強度域 存儲表面的強度信息或指針值。 Chapter 1314A緩沖器算法 RGB 強度分量 透明性參數(shù) 深度 覆蓋度 l若深度域值為正，則該值表示覆蓋該像素點的惟一表面

7、的深度，強度域中存儲該表面上該點顏色的RGB 分量和像素覆蓋率（見圖13 . 9 ( a ) ）。l若深度域值為負，則表示多個面共同對該像素點產(chǎn)生影響。如圖13 . 9 ( b )）所示，強度域存儲一個表面數(shù)據(jù)鏈表的指針，列表中表面的數(shù)據(jù)項包括： 表面的標(biāo)識名 其他表面繪制參數(shù) 指向下一表面的指針Chapter 1315A緩沖器算法w A緩沖器可以按照類似于深度緩沖器算法進行創(chuàng)建，即沿每條掃描線確定各像素點所對應(yīng)的覆蓋表面。表面可分割為多邊形網(wǎng)格，并利用像素邊界對其進行裁剪。采用透明因子和表面覆蓋度，以所有覆蓋表面作用的平均值計算每個像素點處的強度值。Chapter 131613-5掃描線算法

8、w 是像空間的隱面消除算法，是多邊形區(qū)域填充中掃描線算法的延伸。此處，處理的是多個表面，而非填充單個多邊形面。w 逐條處理各條掃描線時，首先要判別與其相交的所有表面的可見性，然后計算各重疊表面的深度值以找到離觀察平面最近的表面。一旦確定了某像素點所對應(yīng)的可見面，可以得到該點的強度值，并將其置入刷新緩沖器。 Chapter 1317掃描線算法w假設(shè)如第10 章所述，為各表面建立一張邊表和一張多邊形表。邊表中包含場景中各線段的端點坐標(biāo)、線段斜率的倒數(shù)和指向多邊形表中對應(yīng)多邊形的指針。 w多邊形表中則包含各多邊形面的平面方程系數(shù)、表面強度信息以及指向邊表的指針。w為加速查找與掃描線相交的表面，可以由

9、邊表中提取信息，建立一張活化邊表。該表僅包含與當(dāng)前掃描線相交的邊，并將它們按x 升序排列。 w另外，可為各個多邊形面定義一個標(biāo)志位，以表示掃描線上某像素點位于多邊形內(nèi)或多邊形外。掃描線由左向右進行處理，在面的左邊界處，標(biāo)志位為“on ”（開始），而右邊界處的標(biāo)志位為“off ”（結(jié)束）。Chapter 1318掃描線算法w 圖13 . 10 舉例說明了掃描線算法如何確定掃描線上各像素點所對應(yīng)的可見面。 Chapter 1319掃描線算法 w 掃描線1 所對應(yīng)的活化邊表中，包含了邊表中邊AB 、BC 、EH和FG 的信息?？疾檫匒B 與BC 間沿線的像素點，只有面S1的標(biāo)志位為“on ”。因此，

10、可將面S1的強度信息直接從多邊形表移入刷新緩沖器中而無須計算深度值。 w 同樣，在邊EH 與FG 間，僅有面S2的標(biāo)志位為“on ”。而掃描線1 的其余部分與所有表面均不相交，這些像素點的強度值應(yīng)為背景強度。可以在初始化工作中將緩沖器的所有單元均置為背景強度。Chapter 1320掃描線算法 w 對于圖13 . 10 中的掃描線2 和3 ?；罨叡戆?AD、EH、BC、FG。在掃描線2 上邊AD 與EH 間的部分，只有面S1的標(biāo)志位為“on ”。而在邊EH 與BC 間的部分，所有面的標(biāo)志位均為“on ”。其間，必須用平面參數(shù)來為兩個表面計算深度值。w 例如，若面S1 的深度小于面S2 ，

11、則將面S1的強度值置入刷新緩沖器中，直到邊界BC 。然后將面S1的標(biāo)志位置為“off ”， 再將面S2的強度值置入刷新緩沖器，直到邊FG 。Chapter 1321掃描線算法 w 逐條處理掃描線時，應(yīng)利用線段的連貫性。如圖13 . 10所示，掃描線3 與掃描線2 具有相同的活化邊表，由于線段交點沒有發(fā)生變化，因此無須在邊EH 與BC 間再進行深度計算。兩個表面必須處于相同的方向，類似于掃描線2 中的情況，因此將面S1置入刷新緩沖器而無須更多的計算。Chapter 1322掃描線算法 w 若場景中出現(xiàn)循環(huán)遮擋，則需要將表面進行劃分以消除循環(huán)，圖13 . 11 中的虛線表示可以在此處將表面分割為兩

12、個獨立部分，以消除循環(huán)遮擋。Chapter 132313-6深度排序算法w深度排序算法（depth-sorting method）同時運用物空間與像空間操作，以實現(xiàn)以下基本功能： l表面按深度遞減方向排序； l由深度最大的表面開始，逐個對表面進行掃描轉(zhuǎn)換。w排序操作同時在像空間和物空間完成，而多邊形面的掃描轉(zhuǎn)換僅在像空間完成。Chapter 1324深度排序算法w 這種隱藏面消除算法通常稱為畫家算法。畫家在繪制一幅圖畫時，總是先在畫紙上涂上背景色，然后畫上遠處的物體，接著是近一些的物體，以此步驟，最后畫上最近的物體。這樣，最近的物體覆蓋了部分背景色和遠處的物體，每一層總是在前一層的景物上覆蓋。

13、w 采用同樣的技術(shù)，首先將表面根據(jù)它們與觀察平面的距離排序，然后在刷新緩沖器中置入最遠處表面的強度值，接著按深度遞減順序逐個選取后繼表面，并將其屬性值“涂”在幀緩沖器上，覆蓋了部分前面處理過的表面。 Chapter 1325深度排序算法w按深度在幀緩沖器上繪制多邊形面可以分幾步進行： 1.假定沿負z軸方向觀察，表面按它們z坐標(biāo)的最低值排序，深度最大的面S需要與其他表面比較，以確定是否在深度方向存在重疊；Chapter 1326深度排序算法w若沒有重疊，則對S進行掃描轉(zhuǎn)換。圖13.12表示在xy平面上投影相互重疊的兩個表面，但它們在深度方向上則沒有重疊。可以按同樣步驟逐個處理列表中的后繼表面。如

14、果沒有重疊存在，則按深度順序處理表面，直至所有表面均完成掃描轉(zhuǎn)換。w若在表中某處發(fā)現(xiàn)深度重疊，則需要進行一些比較以確定是否有必要對部分表面重新排序。 Chapter 1327深度排序算法n可對與S有重疊的所有表面進行以下測試，只要其中任意一項成立，則無須重新排序。測試按難度遞增順序排列： w兩表面在xy平面上投影的包圍矩形無重疊；w相對于觀察位置，面S 完全位于重疊表面之后；w相對于觀察位置，重疊表面完全位于面S 之前； w兩表面在觀察平面上的投影無重疊。 Chapter 132813-7 BSP樹算法w BSP（ binary space-partitioning ）樹算法是一種判別物體可見

15、性的有效算法。該算法類似于畫家算法，將表面由后往前地在屏幕上繪出，該算法特別適用于場景中物體位置固定不變、僅視點移動的情況。w 利用BSP 樹來判別表面的可見性，其主要操作是在每次分割空間時，判別該表面相對于視點與分割平面的位置關(guān)系，即位于其內(nèi)側(cè)還是外側(cè)，圖13 . 19 表示了該算法的基本思想。 Chapter 1329BSP樹算法Chapter 1330BSP樹算法w首先，平面P1將空間分割為兩部分，一組物體位于P1的后面（相對于視點），而另一組則在P1之前。 w如果某物體與P1相交，則立刻將其一分為二并分別標(biāo)識為A 和B 。此時，圖中A 與C 位于P1之前，而B 和D在P1之后。w對空間

16、進行了二次分割，并生成如圖13 . 19 （ b ）所示的二叉樹表示。 Chapter 133113-8區(qū)域細分算法w區(qū)域細分算法雖然本質(zhì)上是一種像空間算法，但使用了一些物空間操作來完成表面的深度排序。w該算法充分利用場景中區(qū)域的連貫性，將視野集中于包含表面的區(qū)域；并將整個觀察范圍細分為越來越小的矩形單元，直至每個單元僅包含單個可見表面的投影或不含任何表面。Chapter 1332區(qū)域細分算法w 為了實現(xiàn)區(qū)域細分算法，必須首先找到一種區(qū)域測試手段，可以很快地判別出某一區(qū)域僅包含某一表面的一部分，或告訴用戶該表面太復(fù)雜、難以分析。w 從整個視圖開始，應(yīng)用該測試來確定是否應(yīng)將一完整區(qū)域分割為一些小

17、矩形單元。若測試表明視圖相當(dāng)復(fù)雜，則需要將其分割，然后再對各個小區(qū)域進行測試。w 若測試表明還無法確定表面的可見性，則必須再次細分區(qū)域，直至最終的區(qū)域易于分析，即它屬于某一個單元或僅覆蓋一個像素。Chapter 1333區(qū)域細分算法w在一個區(qū)域內(nèi)比較某表面與該區(qū)域邊界，可以確定該表面的可見性。根據(jù)表面與區(qū)域邊界的相互關(guān)系，可以將其分為四類：w包圍表面完全包含區(qū)域。 w重疊表面部分位于區(qū)域內(nèi)，部分位于區(qū)域外。w內(nèi)含表面完全在區(qū)域內(nèi)。w分離表面完全在區(qū)域外。Chapter 1334區(qū)域細分算法u可以根據(jù)這四種類別來給出表面的可見性測試。若以下條件之一為真，則無需再對區(qū)域進行分割：所有表面均為區(qū)域的

18、分離表面；在區(qū)域內(nèi)只有一個內(nèi)含表面、重疊表面或包圍表面；在區(qū)域邊界內(nèi)，某包圍表面遮擋了其他所有表面。Chapter 133513-9八叉樹算法w當(dāng)按照八叉樹表示來描述觀察體時，通常按由前往后的順序?qū)瞬鏄涔?jié)點映射到觀察表面，從而消除隱藏面。在圖13.24中，空間區(qū)域的前部（相對于視點）為體元0、1、2、3。體元的前表面均可見，這些體元尾部的表面和后部體元（4、5、6、7）的表面都可能被前部的表面所遮擋。Chapter 1336八叉樹算法w 對于圖13 . 24 所示的觀察方向，按體元順序0 、1 、2 、3 、4 、5 、6 、7 來處理八叉樹節(jié)點中的數(shù)據(jù)可消除隱藏面，這實際上是對八叉樹的深度

19、優(yōu)先遍歷。因此，將在節(jié)點4 、5 、6 、7 之前訪問代表體元0 、1 、2 、3 的節(jié)點。同樣，0號體元中的前面4 個子體元將在后面4 個子體元之前被訪問，對于每個八分體元的八叉樹遍歷將按照這個順序進行。w 一種顯示八叉樹的算法是：首先遞歸地由前往后遍歷八叉樹節(jié)點，將八叉樹映射為可見區(qū)域的四叉樹；然后將可見面的四叉樹表示置入幀緩沖器中。 Chapter 1337八叉樹算法w 圖13 . 25 描述一個空間區(qū)域內(nèi)的八叉體元和相應(yīng)觀察平面上對應(yīng)的四叉體元。八叉體元0 和4 直接影響四叉體元0 ，四叉體元1 的顏色值從八叉體元1 和5 獲得。另外兩個四叉體元的值可以分別從與之對應(yīng)的一對八叉體元中得

20、到。 Chapter 133813-10光線投射算法w 如果考查由視點出發(fā)穿過觀察平面上一像素而射入場景的一條射 線 （ 如 圖 1 3 . 26 ） ，則可以確定出場景中與該射線相交的物體。 Chapter 1339光線投射算法w 光線投射（ray casting ）建立于幾何光學(xué)的基礎(chǔ)之上，它沿光線的路徑追蹤可見面，是一種有效的可見性判別手段。由于場景中有無限多條光線，而我們僅對穿過像素的光線感興趣，因此可考慮從像素出發(fā)，逆向跟蹤射入場景的光線路徑。光線投射算法對于包含曲面，特別是球面的場景有很高的效率。Chapter 1340光線投射算法w 光線投射算法可以看做是深度緩沖器算法（13.3

21、節(jié)）的一種變形。n在深度緩沖器算法中，每次處理一個表面并對表面上的每個投影點計算深度值。計算出來的值與以前保存的深度值進行比較，從而確定每個像素所對應(yīng)的可見表面。n在光線投射算法中，每次處理一個像素，并沿光線的投射路徑計算出該像素所對應(yīng)的所有表面的深度值。 Chapter 134113-11曲面w 對于曲面物體，最有效的可見性判別算法為光線投射算法和八叉樹算法。n在光線投射算法中，首先計算出光線與表面的交點，然后找出沿光線方向離像素最近的交點。 n而在八叉樹算法中，一旦根據(jù)物體的定義建立起相應(yīng)的八叉樹表示，即可用同樣的算法對可見面進行判別，而無須考慮曲面類型。Chapter 1342曲面w 常常利用一組多邊形表面來近似表示曲面。這樣，在表面列表中，使用一個多邊形網(wǎng)格來替代每個曲面。然后，即可使用以前所介紹的隱藏面消隱算法進行處理。w 對于其他