CG隱藏面的消除

1、第2頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第3頁第10章 隱藏面的消除n問題問題投影變換失去了深度信息，往往導致圖形的二義性及失投影變換失去了深度信息，往往導致圖形的二義性及失去遮擋關系去遮擋關系要消除二義性和保持遮擋關系，就必須在繪制時消除被要消除二義性和保持遮擋關系，就必須在繪制時消除被遮擋的不可見的線或面，習慣上稱作消除隱藏線和隱藏遮擋的不可見的線或面，習慣上稱作消除隱藏線和隱

2、藏面，簡稱為面，簡稱為消隱消隱經(jīng)過消隱得到的投影圖稱為物體的真實圖形經(jīng)過消隱得到的投影圖稱為物體的真實圖形長方體線框投影圖的二義性長方體線框投影圖的二義性失去遮擋關系失去遮擋關系第4頁第10章 隱藏面的消除n消隱的對象消隱的對象 三維物體三維物體 三維體的表示主要采用邊界（多邊形）表示三維體的表示主要采用邊界（多邊形）表示n消隱結果消隱結果 與觀察物體有關，也與視點有關與觀察物體有關，也與視點有關線框圖線框圖 消隱圖消隱圖 真實感圖形真實感圖形第5頁第10章 隱藏面的消除n消隱分類消隱分類 消除隱藏面：確定可見面（消除不可見面）消除隱藏面：確定可見面（消除不可見面）表面表示表面表示物體（本章討

3、論）物體（本章討論） 消除隱藏線：消除不可見線消除隱藏線：消除不可見線線框表示物體線框表示物體長方體線框投影圖的二義性長方體線框投影圖的二義性失去遮擋關系失去遮擋關系第6頁第10章 隱藏面的消除n面消隱算法分類面消隱算法分類 投影窗口內(nèi)的像素為處理單元。投影窗口內(nèi)的像素為處理單元。確定最近點確定最近點 for (for (窗口內(nèi)的每一個像素窗口內(nèi)的每一個像素) ) 確定距視點最近的物體，以該物體表面的顏色來顯示像素確定距視點最近的物體，以該物體表面的顏色來顯示像素 圖像空間圖像空間image-space第7頁第10章 隱藏面的消除n面消隱算法分類（續(xù)）面消隱算法分類（續(xù)） 場景中的物體為處理單

4、元。場景中的物體為處理單元。物體上的面是否最近物體上的面是否最近for (for (場景中的每一個物體場景中的每一個物體) ) 將其與場景中的其它物體比較，確定其表面的可見部分；將其與場景中的其它物體比較，確定其表面的可見部分； 顯示該物體表面的可見部分；顯示該物體表面的可見部分； 場景空間場景空間object-space第8頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第9頁第10章 隱藏

5、面的消除n主要技術主要技術 利用連貫性利用連貫性 相鄰事物的屬性之間有一定的連貫性，其屬性值通常相鄰事物的屬性之間有一定的連貫性，其屬性值通常是平緩過渡的，如顏色值、空間位置關系等是平緩過渡的，如顏色值、空間位置關系等 包括：包括：n物體連貫性物體連貫性n面的連貫性面的連貫性n區(qū)域連貫性區(qū)域連貫性n掃描線連貫性掃描線連貫性n深度連貫性深度連貫性第10頁第10章 隱藏面的消除n主要技術主要技術（1）利用連貫性）利用連貫性 物體連貫性：如果物體物體連貫性：如果物體A A與物體與物體B B是完全相互分離的，是完全相互分離的，則在消隱時，只需比較則在消隱時，只需比較A A、B B兩物體之間的遮擋關系，

6、兩物體之間的遮擋關系，無須對它們的表面多邊形逐一進行測試。例如，若無須對它們的表面多邊形逐一進行測試。例如，若A A距視點較距視點較B B遠，則在測試遠，則在測試B B上的表面的可見性時，無須上的表面的可見性時，無須考慮考慮A A的表面的表面 面的連貫性：一張面內(nèi)的各種屬性值一般都是緩慢變面的連貫性：一張面內(nèi)的各種屬性值一般都是緩慢變化的，允許采用增量形式對其進行計算化的，允許采用增量形式對其進行計算第11頁第10章 隱藏面的消除n主要技術主要技術（1）利用連貫性）利用連貫性 區(qū)域連貫性：區(qū)域指屏幕上一組相鄰的像素，它們通區(qū)域連貫性：區(qū)域指屏幕上一組相鄰的像素，它們通常為同一個可見面所占據(jù)，可

7、見性相同。區(qū)域連貫性常為同一個可見面所占據(jù)，可見性相同。區(qū)域連貫性表現(xiàn)在一條掃描線上即為掃描線上的每個區(qū)間內(nèi)只有表現(xiàn)在一條掃描線上即為掃描線上的每個區(qū)間內(nèi)只有一個面可見一個面可見 掃描線的連貫性：相鄰兩條掃描線上，可見面的分布掃描線的連貫性：相鄰兩條掃描線上，可見面的分布情況相似情況相似 深度連貫性：同一表面上的相鄰部分深度是相近的，深度連貫性：同一表面上的相鄰部分深度是相近的，而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同第12頁第10章 隱藏面的消除（2）透視投影轉(zhuǎn)換為平行投影）透視投影轉(zhuǎn)換為平行投影 消隱在投影前完成消隱在投影前完成 物體間的遮擋關系與投

8、影中心相關物體間的遮擋關系與投影中心相關 物體間的遮擋關系與投影方式相關物體間的遮擋關系與投影方式相關第13頁第10章 隱藏面的消除（3）包圍盒技術包圍盒技術定義：一個形體的包圍盒指的是包圍它的簡單形體定義：一個形體的包圍盒指的是包圍它的簡單形體兩個條件兩個條件 包圍盒充分緊密包圍著形體包圍盒充分緊密包圍著形體 對其的測試比較簡單對其的測試比較簡單主要包圍盒主要包圍盒 長方體長方體 正方體正方體 球球第14頁第10章 隱藏面的消除 應用應用避免盲目求交避免盲目求交例如：兩個空間多邊形例如：兩個空間多邊形A、B在投影平面上的投影分別為在投影平面上的投影分別為A，B ，因為，因為A 、B的矩形包圍

9、盒不相交，則的矩形包圍盒不相交，則A、B不相交不相交，無須進行遮擋測試。右下圖，無須進行遮擋測試。右下圖(a)包圍盒相交，投影也相交包圍盒相交，投影也相交；(b)包圍盒相交，投影不相交包圍盒相交，投影不相交第15頁第10章 隱藏面的消除（4）背面剔除背面剔除外法向：規(guī)定每個多邊形的外法向都是指向物體外部的外法向：規(guī)定每個多邊形的外法向都是指向物體外部的前向面：若多邊形的外法向與投影方向（觀察方向）的夾前向面：若多邊形的外法向與投影方向（觀察方向）的夾角為鈍角，稱為前向面角為鈍角，稱為前向面后向面：若多邊形的外法向與投影方向（觀察方向）的夾后向面：若多邊形的外法向與投影方向（觀察方向）的夾角為銳

10、角，稱為后向面（背面）角為銳角，稱為后向面（背面）投影方向投影方向夾角為夾角為180u第16頁第10章 隱藏面的消除（4）背面剔除（續(xù)）背面剔除（續(xù)）剔除依據(jù)：背面總是被前向面所遮擋，從而不可見剔除依據(jù)：背面總是被前向面所遮擋，從而不可見前向面前向面 后向面后向面JEAF、HCBG、JIHGF為為后向面后向面CGV VABDEFHIJN NVnVn第17頁第10章 隱藏面的消除（5）空間分割技術）空間分割技術 依據(jù)：場景中的物體，它們的投影在投影平面上是否有依據(jù)：場景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對于根本不重疊部分？（是否存在相互遮擋的可能？）對于

11、根本不存在相互遮擋關系的物體，應避免這種不必要的測試存在相互遮擋關系的物體，應避免這種不必要的測試 原因：物體在場景中分散，有些物體的投影相距甚遠，原因：物體在場景中分散，有些物體的投影相距甚遠，不會存在遮擋關系不會存在遮擋關系 方法：將投影平面上的窗口分成若干小區(qū)域；為每個小方法：將投影平面上的窗口分成若干小區(qū)域；為每個小區(qū)域建立相關物體表，表中物體的投影于該區(qū)域有相交區(qū)域建立相關物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個物體可見時，只要對該區(qū)部分；則在小區(qū)域中判斷那個物體可見時，只要對該區(qū)域的相關物體表中的物體進行比較域的相關物體表中的物體進行比較第18頁第10章 隱藏

12、面的消除（6）物體的分層表示）物體的分層表示 表示形式：模型變換中的樹形表示方式表示形式：模型變換中的樹形表示方式 原理：減少場景中物體的個數(shù)，從而降低算法復雜度原理：減少場景中物體的個數(shù)，從而降低算法復雜度第19頁第10章 隱藏面的消除（6）物體的分層表示（續(xù)）物體的分層表示（續(xù)） 方法：方法： 將父節(jié)點所代表的物體看成子節(jié)點所代表物將父節(jié)點所代表的物體看成子節(jié)點所代表物體的包圍盒，當兩個父節(jié)點之間不存在遮擋關系時，體的包圍盒，當兩個父節(jié)點之間不存在遮擋關系時，就沒有必要對兩者的子節(jié)點做進一步測試。父節(jié)點之就沒有必要對兩者的子節(jié)點做進一步測試。父節(jié)點之間的遮擋關系可以用它們之間的包圍盒進行預

13、測試間的遮擋關系可以用它們之間的包圍盒進行預測試第20頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第21頁第10章 隱藏面的消除n背景背景畫家的作畫順序暗示出所畫物體之間的相互遮擋關系畫家的作畫順序暗示出所畫物體之間的相互遮擋關系第22頁第10章 隱藏面的消除n算法基本思想：算法基本思想：1 1）先把屏幕置成背景色）先把屏幕置成背景色2 2）將場景中的物體按其距觀察點的遠近進行排序，結果放

14、）將場景中的物體按其距觀察點的遠近進行排序，結果放在一張線性表中；（線性表構造：距觀察點遠的稱優(yōu)先級在一張線性表中；（線性表構造：距觀察點遠的稱優(yōu)先級低，放在表頭；距觀察點近的稱優(yōu)先級高，放在表尾。該低，放在表頭；距觀察點近的稱優(yōu)先級高，放在表尾。該表稱為深度優(yōu)先級表）表稱為深度優(yōu)先級表）3 3）然后按照從遠到近（從表頭到表尾）的順序逐個繪制物）然后按照從遠到近（從表頭到表尾）的順序逐個繪制物體。體。n關鍵關鍵如何對場景中的物體按深度（遠近）排序，建立深度優(yōu)先如何對場景中的物體按深度（遠近）排序，建立深度優(yōu)先級表？級表？第23頁第10章 隱藏面的消除n多邊形的排序算法多邊形的排序算法*1 1）

15、將場景中所有多邊形存入一個線性表，記為）將場景中所有多邊形存入一個線性表，記為L；2 2）如果）如果L L中僅有一個多邊形，算法結束；否則根據(jù)每個多邊形的中僅有一個多邊形，算法結束；否則根據(jù)每個多邊形的Zmin 對它們預排序。不妨假定多邊形對它們預排序。不妨假定多邊形P P落在落在L L的表首，即的表首，即Zmin(P) 為最小。再記為最小。再記 Q 為為 L P (表中其余多邊形）中任意表中其余多邊形）中任意一個；一個；3 3）判別）判別P, Q之間的關系，有如下二種：之間的關系，有如下二種：（1 1）對所有的）對所有的Q，有，有Zmax(P) Zmin (Q)，需進一步需進一步判別判別：第

16、24頁第10章 隱藏面的消除（A）若若P, Q的投影的投影 P, Q 的包圍盒不的包圍盒不相交相交( (圖圖a) )，則，則P, Q 在表中的次序不在表中的次序不重要，令重要，令L = L L = L P , P , 返回返回2 2）; ;否否則進行下一步則進行下一步（B B）若）若 P 的所有頂點位于的所有頂點位于 Q 所在平面所在平面的不可見的一側(cè)的不可見的一側(cè)( (圖圖b) ) ，則，則P, Q關系關系正確，令正確，令L = L P, 返回返回 2 2）; ;否則否則進行下一步進行下一步第25頁第10章 隱藏面的消除（C）若若Q的所有頂點位于的所有頂點位于 P 所在平面的所在平面的可見的

17、一側(cè)可見的一側(cè)( (圖圖c) )，則，則P, Q關系正確，關系正確，令令L = = L P , 返回返回2 2）; ;否則進行下否則進行下一步一步（D）對對P, Q投影投影P, Q求交，若求交，若P, Q不不相交相交( (圖圖d) )，則，則P, Q在表中的次序不重在表中的次序不重要，令要，令L = L P , 返回返回 2 2）; ; 否則在否則在它們所相交的區(qū)域中任取一點，計算它們所相交的區(qū)域中任取一點，計算 P, Q在該點的深度值，如果在該點的深度值，如果 P 的深度的深度小，則小，則P, Q關系正確，令關系正確，令L = L P , 返回返回 2 2）; ;否則交換否則交換P, Q,

18、返回返回3 3）第26頁第10章 隱藏面的消除n問題問題* 不能處理不能處理多邊形循環(huán)遮擋和多邊形相互穿透多邊形循環(huán)遮擋和多邊形相互穿透解決方法：分割解決方法：分割第27頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第28頁第10章 隱藏面的消除n又稱為又稱為ZBuffer算法算法( (深度緩沖深度緩沖 depth-buffer) )n組成：組成： 幀緩沖器幀緩沖器 - - 保保存各像素顏色

19、值存各像素顏色值 Z 緩沖器緩沖器 - - 保保存各像素處物體深度值存各像素處物體深度值 Z 緩沖器中的單元與幀緩沖器中的單元一一對應緩沖器中的單元與幀緩沖器中的單元一一對應屏幕幀緩沖器Z緩沖器每個單元存放對應象素的顏色值每個單元存放對應象素的深度值第29頁第10章 隱藏面的消除n基本思想基本思想 （1 1）先將）先將 Z 緩沖器中個單元的初始值置緩沖器中個單元的初始值置為最小值。為最小值。 （2 2）當要改變某個像素的顏色值時，首先）當要改變某個像素的顏色值時，首先檢查當前多邊形的深度值是否大于該像素檢查當前多邊形的深度值是否大于該像素原來的深度值（保存在該像素所對應的原來的深度值（保存在該

20、像素所對應的Z Z緩沖器的單元中），緩沖器的單元中）， A：如果大于，說明當前多邊形更靠近觀如果大于，說明當前多邊形更靠近觀察點，用它的顏色替換像素原來的顏色；察點，用它的顏色替換像素原來的顏色； B：否則說明在當前像素處，當前多邊形否則說明在當前像素處，當前多邊形被前面所繪制的多邊形遮擋了，是不可見被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變的，像素的顏色值不改變第30頁第10章 隱藏面的消除n算法算法 幀緩存全置為背景色；幀緩存全置為背景色；深度緩存全置為最小深度緩存全置為最小 Z 值；值；for( (每一個多邊形每一個多邊形) ) for( (該多邊形所覆蓋的每個像素該多邊

21、形所覆蓋的每個像素(x, y) ) ) 計算該多邊形在該像素的深度值計算該多邊形在該像素的深度值 Z(x, y); if ( Z(x, y)大于大于Z緩存在緩存在(x, y)的值的值) ) 把把 Z(x, y)存入存入 Z 緩存中緩存中(x, y)處；處； 把多邊形在把多邊形在(x, y)處的顏色值存入幀緩存的處的顏色值存入幀緩存的(x, y)處；處； 需要計算的像素深度值次數(shù)需要計算的像素深度值次數(shù)= =多邊形個數(shù)多邊形個數(shù)* *多邊形平均占據(jù)的像素個數(shù)多邊形平均占據(jù)的像素個數(shù)第31頁第10章 隱藏面的消除n特點特點 Z 緩沖器算法是所有圖像空間算法中最簡單的一種隱藏緩沖器算法是所有圖像空間

22、算法中最簡單的一種隱藏面消除算法。面消除算法。在像素級上以近物取代遠物，與形體在屏在像素級上以近物取代遠物，與形體在屏幕上的出現(xiàn)順序無關。幕上的出現(xiàn)順序無關。優(yōu)點優(yōu)點 1 1）簡單穩(wěn)定，利于硬件實現(xiàn)）簡單穩(wěn)定，利于硬件實現(xiàn) 2 2）不需要整個場景的幾何數(shù)據(jù)不需要整個場景的幾何數(shù)據(jù)缺點缺點 1 1）需要一個額外的）需要一個額外的 Z 緩沖器緩沖器 2 2）每個多邊形占據(jù)的每個像素處都要計算深度值，）每個多邊形占據(jù)的每個像素處都要計算深度值， 計算量大計算量大第32頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器

23、算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第33頁第10章 隱藏面的消除10.5 掃描線掃描線Z緩沖器算法緩沖器算法n由來由來 Z 緩沖器算法中所需要的緩沖器算法中所需要的 Z 緩沖器容量較大，為克服這緩沖器容量較大，為克服這個缺點可以將整個繪圖區(qū)域分割成若干個小區(qū)域，然后一個缺點可以將整個繪圖區(qū)域分割成若干個小區(qū)域，然后一個區(qū)域一個區(qū)域地顯示，這樣個區(qū)域一個區(qū)域地顯示，這樣 Z 緩沖器的單元數(shù)只要等緩沖器的單元數(shù)只要等于一個區(qū)域內(nèi)像素的個數(shù)于一個區(qū)域內(nèi)像素的個數(shù)如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線如果將小區(qū)域

24、取成屏幕上的掃描線，就得到掃描線 Z 緩緩沖器算法沖器算法第34頁第10章 隱藏面的消除10.5 掃描線掃描線Z緩沖器算法緩沖器算法n算法思想算法思想在處理當前掃描線時，用一個一維數(shù)組作為當前掃描線的在處理當前掃描線時，用一個一維數(shù)組作為當前掃描線的Z-buffer。首先找出與當前掃描線相關的多邊形，以及每。首先找出與當前掃描線相關的多邊形，以及每個多邊形中相關的邊對。個多邊形中相關的邊對。對每一個邊對之間的小區(qū)間上的各像素，計算深度，并與對每一個邊對之間的小區(qū)間上的各像素，計算深度，并與Z-buffer中的值比較，找出各像素處可見平面。中的值比較，找出各像素處可見平面。寫幀緩存。采用增量算法

25、計算深度寫幀緩存。采用增量算法計算深度第35頁第10章 隱藏面的消除10.5 掃描線掃描線Z緩沖器算法緩沖器算法n算法（算法（p291）* for ( v= 0;vvmax;v+) for (u= 0; u Z緩沖器的第緩沖器的第u單元的值）單元的值） 置幀緩沖器的第置幀緩沖器的第(u,v)單元值為當前多邊形顏色；單元值為當前多邊形顏色； 置置Z緩沖器的第緩沖器的第u單元值為單元值為d; /處理下一條掃描線處理下一條掃描線第36頁第10章 隱藏面的消除n缺點缺點 在每一個被多邊形覆蓋像素處需要計算深度值在每一個被多邊形覆蓋像素處需要計算深度值 被多個多邊形覆蓋的像素需要多次計算深度值被多個多邊

26、形覆蓋的像素需要多次計算深度值第37頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第38頁第10章 隱藏面的消除n比較比較與與Z-Buffer算法相比，掃描線算法相比，掃描線Z算法有了很大改進，比如算法有了很大改進，比如所需的所需的Z-Buffer大大減小，計算深度利用了面連貫性等大大減小，計算深度利用了面連貫性等缺點：缺點：每個像素處都計算深度值，甚至不止一次的計算，每個像素處都計算深度值

27、，甚至不止一次的計算，運算量仍然很大運算量仍然很大改進：改進：在一條掃描線上，每個區(qū)間只計算一次深度，即掃在一條掃描線上，每個區(qū)間只計算一次深度，即掃描線算法，又稱區(qū)間掃描線算法描線算法，又稱區(qū)間掃描線算法第39頁第10章 隱藏面的消除n基本思想基本思想 多邊形多邊形P1、P2的邊界在投影平面上的投影將一條掃描線的邊界在投影平面上的投影將一條掃描線劃分成若干個區(qū)間劃分成若干個區(qū)間0,u1 u1,u2 u2,u3 u3,u4 , u4,umax 覆蓋每個區(qū)間的有覆蓋每個區(qū)間的有0個、個、1個或多個多邊形，但僅有一個個或多個多邊形，但僅有一個可見。在區(qū)間上任取一個像素，計算該像素處各多邊形可見。在

28、區(qū)間上任取一個像素，計算該像素處各多邊形（投影包含了該像素的多邊形）的深度值，深度值最大（投影包含了該像素的多邊形）的深度值，深度值最大者即為可見多邊形，用它的顏色顯示整個區(qū)間者即為可見多邊形，用它的顏色顯示整個區(qū)間第40頁第10章 隱藏面的消除n注意注意* *該算法要求多邊形不能相互貫穿，否則在同一區(qū)間上，該算法要求多邊形不能相互貫穿，否則在同一區(qū)間上，多邊形深度值的次序會發(fā)生變化多邊形深度值的次序會發(fā)生變化如圖：在區(qū)間如圖：在區(qū)間 u1 1, ,u2 2 上，多邊形上，多邊形P1 1的深度值大，在區(qū)間的深度值大，在區(qū)間 u3 3, ,u4 4 上，多邊形上，多邊形P2 2的深度值大，而在區(qū)

29、間的深度值大，而在區(qū)間 u2 2, ,u3 3 上，上，兩個多邊形的深度值次序發(fā)生交替兩個多邊形的深度值次序發(fā)生交替第41頁第10章 隱藏面的消除n算法算法* for (for (繪圖窗口內(nèi)的每一條掃描線）繪圖窗口內(nèi)的每一條掃描線） 求投影與當前掃描線相交的所有多邊形；求投影與當前掃描線相交的所有多邊形； 求上述多邊形中投影與當前掃描線相交的所有邊，將它們記錄在活性邊求上述多邊形中投影與當前掃描線相交的所有邊，將它們記錄在活性邊 表表AELAEL中；中； 求求AELAEL中每條邊的投影與掃描線的交點；中每條邊的投影與掃描線的交點； 按交點的按交點的u u坐標將坐標將AELAEL中各邊從左到右排

30、序，兩兩配對組成一個區(qū)間；中各邊從左到右排序，兩兩配對組成一個區(qū)間； for for （AELAEL中每個區(qū)間）中每個區(qū)間） 求覆蓋該區(qū)間的所有多邊形，將它們記入活化多邊形表求覆蓋該區(qū)間的所有多邊形，將它們記入活化多邊形表APLAPL中；中； 在區(qū)間上任取一點，計算在區(qū)間上任取一點，計算APLAPL中各多邊形在該點的深度值，記深度最中各多邊形在該點的深度值，記深度最大者為大者為P P； 用多邊形用多邊形P P的顏色填充該區(qū)間；的顏色填充該區(qū)間； 第42頁第10章 隱藏面的消除n數(shù)據(jù)結構（類似于掃描線數(shù)據(jù)結構（類似于掃描線Z-Buffer算法中的數(shù)據(jù)結算法中的數(shù)據(jù)結構）構）* 多邊形分類表多邊形

31、分類表PT 活性多邊形表活性多邊形表APL 邊的分類表邊的分類表ET 活性邊表活性邊表AEPLn改進改進* 在一條掃描線上，以區(qū)間為單位確定多邊形的可見性在一條掃描線上，以區(qū)間為單位確定多邊形的可見性 不再需要不再需要Z-Buffer第43頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第44頁第10章 隱藏面的消除n基本思想基本思想將通過繪圖窗口內(nèi)每一個像素的投影線與場景中的所有將通過繪圖窗

32、口內(nèi)每一個像素的投影線與場景中的所有多邊形求交。如果有交點，用深度值最大的交點（最近多邊形求交。如果有交點，用深度值最大的交點（最近的）所屬的多邊形的顏色顯示相應的像素；如果沒有交的）所屬的多邊形的顏色顯示相應的像素；如果沒有交點，說明沒有多邊形的投影覆蓋此像素，用背景色顯示點，說明沒有多邊形的投影覆蓋此像素，用背景色顯示第45頁第10章 隱藏面的消除n算法算法for ( v= 0;vvmax;v+)for ( v= 0;vvmax;v+)for (u= 0; uumax; u+)for (u= 0; uumax; u+) 形成通過像素形成通過像素(u,v)(u,v)的投影線；的投影線； fo

33、r (for (場景中每一個多邊形）場景中每一個多邊形） 將投影線與多邊形求交；將投影線與多邊形求交； if (if (有交點）有交點） 以最近交點所屬多邊形的顏色顯示像素以最近交點所屬多邊形的顏色顯示像素(u,v)(u,v) else else 以背景色顯示像素以背景色顯示像素(u,v)(u,v)； 第46頁第10章 隱藏面的消除n基本概念基本概念n提高消隱算法效率的常用方法提高消隱算法效率的常用方法n畫家算法畫家算法nZ緩沖器算法緩沖器算法n掃描線掃描線Z緩沖器算法緩沖器算法n掃描線算法掃描線算法n光線投射算法光線投射算法nOpenGL相關函數(shù)相關函數(shù)第47頁第10章 隱藏面的消除n多邊形剔除函數(shù)消除后向面（背面）多邊形剔除函數(shù)消除后向面（背面） 激活：激活：glEnable（GL