CG隱藏面的消除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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