計(jì)算機(jī)圖形學(xué) 消隱.ppt

《計(jì)算機(jī)圖形學(xué) 消隱.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第十一講面消隱？基本概念？提高消隱算法效率的常見(jiàn)方法？畫(huà)家算法？Z緩沖器算法？掃描線Z緩沖器算法？區(qū)域子分算法？光線投射算法基本概念產(chǎn)生真實(shí)感的方法之一：反映三維場(chǎng)景中的相互遮擋關(guān)系面消隱與線消隱表面模型與線框模型物體表面：平面與曲面面消隱對(duì)象：由平面多邊形構(gòu)成的多面體基本概念消隱算法的分類1）類：以窗口內(nèi)的每個(gè)像素為處理單元；for(窗口內(nèi)的每一個(gè)像素){確定距視點(diǎn)最近的物體，以該物體表面的顏色來(lái)顯示像素}2）類：以場(chǎng)景中的物體為處理單元；for(場(chǎng)景中的每一個(gè)物體){將其與場(chǎng)景中的其它物體比較，確定其表面的可見(jiàn)部分；顯示

2、該物體表面的可見(jiàn)部分；}基本概念算法復(fù)雜度假設(shè)場(chǎng)景中有k個(gè)物體，平均每個(gè)物體表面由h個(gè)多邊形構(gòu)成，顯示區(qū)域中有mxn個(gè)像素，則：第一種算法的復(fù)雜度為：O(mnkh)第二種算法的復(fù)雜度為：O((kh)*(kh))提高消隱算法效率的常見(jiàn)方法利用連貫性將透視投影轉(zhuǎn)換成平行投影包圍盒技術(shù)背面剔除空間分割技術(shù)物體分層表示提高消隱算法效率的常見(jiàn)方法1利用連貫性物體連貫性面的連貫性區(qū)域連貫性掃描線的連貫性深度連貫性提高消隱算法效率的常見(jiàn)方法2將透視投影轉(zhuǎn)換成平行投影消隱與透視關(guān)系密切,體現(xiàn)有：1）消隱必須在投影之前完成；2）物體之間的遮

3、擋關(guān)系與投影中心（視點(diǎn)）的選取有關(guān)；3）物體之間的遮擋關(guān)系與投影方式有關(guān)提高消隱算法效率的常見(jiàn)方法3圖12.3加入面消隱步驟的三維圖形顯示流程圖p285(參見(jiàn)圖8.30p162）圖12.4先將透視投影轉(zhuǎn)換成平行投影，南后再消隱p285(參見(jiàn)圖8.33p167）。（避免除法，提高了效率）提高消隱算法效率的常見(jiàn)方法4包圍盒技術(shù)定義：一個(gè)形體的包圍盒指的是包圍它的簡(jiǎn)單形體。比如，…該技術(shù)常用于：避免盲目的求交測(cè)試；各種物體間的比較等。一個(gè)好的包圍盒要具有兩個(gè)條件：包圍和充分緊密包圍著形體；對(duì)其的測(cè)試比較簡(jiǎn)單。例：使用矩形包圍合及長(zhǎng)

4、方體包圍合來(lái)提高算法效率…提高消隱算法效率的常見(jiàn)方法5背面剔除外法向外法向與投影方向（觀察方向）的夾角前向面與后向面（背面）剔除依據(jù)：物體表面是封閉的，背面總是被前向面所遮擋，從而始終是不可見(jiàn)的。提高消隱算法效率的常見(jiàn)方法6空間分割技術(shù)依據(jù)：場(chǎng)景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對(duì)于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測(cè)試。方法：將投影平面上的窗口分成若干小區(qū)域；為每個(gè)小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個(gè)物體可見(jiàn)時(shí)，只要對(duì)該區(qū)域的相

5、關(guān)物體表中的物體進(jìn)行比較即可。提高消隱算法效率的常見(jiàn)方法6復(fù)雜度比較：不妨假定每個(gè)小區(qū)域的相關(guān)物體表中平均有h個(gè)物體，場(chǎng)景中有k個(gè)物體，由于物體在場(chǎng)景中的分布是分散的，顯然h遠(yuǎn)小于k。根據(jù)第二種消隱方法所述，其算法復(fù)雜度為O(h*h),遠(yuǎn)小于O(k*k)。提高消隱算法效率的常見(jiàn)方法7物體分層表示表示形式：模型變換中的樹(shù)形表示方式原理：減少場(chǎng)景中物體的個(gè)數(shù)，從而降低算法復(fù)雜度。方法：將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的包圍盒，當(dāng)兩個(gè)父節(jié)點(diǎn)之間不存在遮擋關(guān)系時(shí)，就沒(méi)有必要對(duì)兩者的子節(jié)點(diǎn)做進(jìn)一步測(cè)試。父節(jié)點(diǎn)之間的遮擋關(guān)系可以

6、用它們之間的包圍盒進(jìn)行預(yù)測(cè)試。畫(huà)家算法由來(lái)：畫(huà)家的作畫(huà)順序暗示出所畫(huà)物體之間的相互遮擋關(guān)系算法基本思路：1）先將場(chǎng)景中的物體按其距觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點(diǎn)遠(yuǎn)的稱優(yōu)先級(jí)低，放在表頭；距觀察點(diǎn)近的稱優(yōu)先級(jí)高，放在表尾。該表稱為深度優(yōu)先級(jí)表）2）然后按照從表頭到表尾的順序逐個(gè)繪制物體。畫(huà)家算法關(guān)鍵：如何對(duì)場(chǎng)景中的物體按深度（遠(yuǎn)近）排序，建立深度優(yōu)先級(jí)表？一種針對(duì)多邊形的排序算法如下：假定在規(guī)范化投影坐標(biāo)系uvn中,投影方向是n軸的負(fù)向，因而n坐標(biāo)大距觀察者近。記nmin(P)nmax(P)

7、分別為多邊形P的各個(gè)頂點(diǎn)n坐標(biāo)的最小值和最大值，算法步驟如下：畫(huà)家算法Step1:將場(chǎng)景中所有多邊形存入一個(gè)線性表（鏈表或數(shù)組），記為L(zhǎng);Step2:如果L中僅有一個(gè)多邊形，算法結(jié)束；否則根據(jù)每個(gè)多邊形的nmin對(duì)它們預(yù)排序。不妨假定多邊形P落在表首，即nmin(P)為最小。再記Q為L(zhǎng)–{P}(表中其余多邊形）中任意一個(gè)；Step3:判別P,Q之間的關(guān)系，有如下二種：step3.1:對(duì)有的Q，有nmax(P)

8、存在某一個(gè)多邊形Q，使nmax(P)>nmin(Q),需進(jìn)一步判別：step3.2.1若P,Q投影P’,Q’的包圍盒不相交，則P,Q在表中的次序不重要，令L=L–{P},返回step2;否則進(jìn)行下一步。step3.2.2若P的所有頂點(diǎn)位于Q所在平面的不可見(jiàn)的一側(cè)，則P,Q關(guān)系正確，令L=L