第八章面消隱

第八章面消隱第一頁，共三十一頁，編輯于2023年，星期四基本概念產(chǎn)生真實(shí)感的方法之一：反映三維場景中的相互遮擋關(guān)系面消隱與線消隱

表面模型與線框模型 物體表面：平面與曲面 面消隱對象：由平面多邊形構(gòu)成的多面體第二頁，共三十一頁，編輯于2023年，星期四基本概念消隱算法的分類 1）類：以窗口內(nèi)的每個(gè)像素為處理單元；

for(窗口內(nèi)的每一個(gè)像素) {確定距視點(diǎn)最近的物體，以該物體表面的顏色來顯示像素}

2）類：以場景中的物體為處理單元；

for(場景中的每一個(gè)物體) {將其與場景中的其它物體比較，確定其表面的可見部分； 顯示該物體表面的可見部分； }第三頁，共三十一頁，編輯于2023年，星期四基本概念算法復(fù)雜度假設(shè)場景中有k個(gè)物體，平均每個(gè)物體表面由h個(gè)多邊形構(gòu)成，顯示區(qū)域中有mxn個(gè)像素，則：

第一種算法的復(fù)雜度為：O(mnkh)第二種算法的復(fù)雜度為：O((kh)*(kh))第四頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法

利用連貫性將透視投影轉(zhuǎn)換成平行投影包圍盒技術(shù)背面剔除空間分割技術(shù)物體分層表示第五頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法

1利用連貫性物體連貫性 面的連貫性區(qū)域連貫性掃描線的連貫性 深度連貫性第六頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法2將透視投影轉(zhuǎn)換成平行投影消隱與透視關(guān)系密切,體現(xiàn)有：

1）消隱必須在投影之前完成； 2）物體之間的遮擋關(guān)系與投影中心（視點(diǎn)）的選取有關(guān)； 3）物體之間的遮擋關(guān)系與投影方式有關(guān)第七頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法4包圍盒技術(shù)

定義：一個(gè)形體的包圍盒指的是包圍它的簡單形體。比如，…

該技術(shù)常用于：避免盲目的求交測試； 各種物體間的比較等。

一個(gè)好的包圍盒要具有兩個(gè)條件： 包圍和充分緊密包圍著形體； 對其的測試比較簡單。

例：使用矩形包圍合及長方體包圍合來提高算法效率…第八頁，共三十一頁，編輯于2023年，星期四它的基本思想是，在復(fù)雜形體外包一個(gè)容易求交的包圍盒，例如長方體或球面等。在光線與該復(fù)雜物體求交之前，先判其是否與包圍盒相交，若與包圍盒不相交，說明它與包圍盒中的復(fù)雜形體也不相交，從而節(jié)約了時(shí)間。只有當(dāng)光線與包圍盒有交時(shí)，才有必要與復(fù)雜形體進(jìn)行求交運(yùn)算。若原復(fù)雜形體由多個(gè)部分組成，還可以為每個(gè)部分定義一個(gè)包圍盒，從而形成一棵包圍盒樹。線面求交時(shí)先從樹根結(jié)點(diǎn)開始判斷包圍盒，若光線與根結(jié)點(diǎn)的包圍盒不相交，則與原物體不相交，否則再判斷光線與每棵子樹的包圍盒是否相交，這樣可以按層次訪問包圍盒，免除了許多不必要的求交計(jì)算。只有當(dāng)訪問到樹的葉子節(jié)點(diǎn)時(shí)，才需進(jìn)行必要的求交計(jì)算。第九頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法5背面剔除

外法向 外法向與投影方向（觀察方向）的夾角 前向面與后向面（背面）

剔除依據(jù)：物體表面是封閉的，背面總是被前向面所遮擋，從而始終是不可見的。

第十頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法6空間分割技術(shù)

依據(jù)：場景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測試。

方法：將投影平面上的窗口分成若干小區(qū)域；為每個(gè)小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個(gè)物體可見時(shí)，只要對該區(qū)域的相關(guān)物體表中的物體進(jìn)行比較即可。

第十一頁，共三十一頁，編輯于2023年，星期四它的基本原理是，將物體所在的空間剖分為若干個(gè)小體素，為每個(gè)體素建一張表以保存在該體素中或部分在該體素中的物體。若一個(gè)物體在幾個(gè)體素中，則每個(gè)體素的表中都要記錄該物體。光線射出后，先與其遇到的第一個(gè)體素中的所有物體求交，若有交且交點(diǎn)在該體素中，則此體素中的最近交點(diǎn)就是系統(tǒng)中所有物體的最近交點(diǎn)，這樣就沒有必要與其它體素中的物體求交。若在第一個(gè)體素中無交，則再判下一個(gè)體素，直至找到交點(diǎn)或穿出剖分空間為止。由于只有射線穿過的體素中的物體才可能參與求交，從而大大地減少了求交次數(shù)?？臻g剖分法特別適合于離散法造型系統(tǒng)中的形體或由多個(gè)簡單形體構(gòu)成的復(fù)雜形體。這樣每個(gè)體素中的物體求交速度都很快，而且避免了絕大多數(shù)不必要的求交計(jì)算。第十二頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法6復(fù)雜度比較： 不妨假定每個(gè)小區(qū)域的相關(guān)物體表中平均有h個(gè)物體，場景中有k個(gè)物體，由于物體在場景中的分布是分散的，顯然h遠(yuǎn)小于k。根據(jù)第二種消隱方法所述，其算法復(fù)雜度為O(h*h),遠(yuǎn)小于O(k*k)。第十三頁，共三十一頁，編輯于2023年，星期四提高消隱算法效率的常見方法7物體分層表示

表示形式：模型變換中的樹形表示方式

原理：減少場景中物體的個(gè)數(shù)，從而降低算法復(fù)雜度。

方法：將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的包圍盒，當(dāng)兩個(gè)父節(jié)點(diǎn)之間不存在遮擋關(guān)系時(shí)，就沒有必要對兩者的子節(jié)點(diǎn)做進(jìn)一步測試。 父節(jié)點(diǎn)之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測試。第十四頁，共三十一頁，編輯于2023年，星期四光線投射算法

算法思路：將通過繪圖窗口內(nèi)每一個(gè)像素的投影線與場景中的所有多邊形求交。如果有交點(diǎn)，用深度值最大的交點(diǎn)（最近的）所屬的多邊形的顏色顯示相應(yīng)的像素；如果沒有交點(diǎn)，說明沒有多邊形的投影覆蓋此像素，用背景色顯示即可。第十五頁，共三十一頁，編輯于2023年，星期四光線投射算法算法描述：for(v=0;v<vmax;v++) for(u=0;u<umax;u++){形成通過像素(u,v)的投影線； for(場景中每一個(gè)多邊形） 將投影線與多邊形求交； if(有交點(diǎn)） 以最近交點(diǎn)所屬多邊形的顏色顯示像素(u,v) else 以背景色顯示像素(u,v)； }第十六頁，共三十一頁，編輯于2023年，星期四光線跟蹤算法使計(jì)算機(jī)產(chǎn)生圖形的真實(shí)感大幅度提高，但卓越的圖形繪制效果與昂貴的的計(jì)算開銷形成了鮮明的對比。為了使這一算法真正實(shí)用化，減少運(yùn)算量勢所必行，從此，許多人開始研究光線跟蹤的加速方法。光線跟蹤中最費(fèi)時(shí)的運(yùn)算是線面求交，有關(guān)資料表明，如果不采取加速措施，線面求交約占整個(gè)光線跟蹤時(shí)間的95％以上。因此，減少運(yùn)算量的關(guān)鍵在于提高線面求交的速度或減少線面求交的次數(shù)。第十七頁，共三十一頁，編輯于2023年，星期四畫家算法由來：畫家的作畫順序暗示出所畫物體之間的相互遮擋關(guān)系算法基本思路：

1）先將場景中的物體按其距觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點(diǎn)遠(yuǎn)的稱優(yōu)先級低，放在表頭；距觀察點(diǎn)近的稱優(yōu)先級高，放在表尾。該表稱為深度優(yōu)先級表）

2）然后按照從表頭到表尾的順序逐個(gè)繪制物體。第十八頁，共三十一頁，編輯于2023年，星期四畫家算法關(guān)鍵：如何對場景中的物體按深度（遠(yuǎn)近）排序，建立深度優(yōu)先級表？一種針對多邊形的排序算法如下：

假定在規(guī)范化投影坐標(biāo)系uvn中,投影方向是n軸的負(fù)向，因而n坐標(biāo)大距觀察者近。記nmin(P)nmax(P)分別為多邊形P的各個(gè)頂點(diǎn)n坐標(biāo)的最小值和最大值，算法步驟如下：第十九頁，共三十一頁，編輯于2023年，星期四畫家算法Step1:將場景中所有多邊形存入一個(gè)線性表（鏈表或數(shù)組），記為L;Step2:如果L中僅有一個(gè)多邊形，算法結(jié)束；否則根據(jù)每個(gè)多邊形的nmin對它們預(yù)排序。不妨假定多邊形P落在表首，即nmin(P)為最小。再記Q為L–{P}(表中其余多邊形）中任意一個(gè)；Step3:判別P,Q之間的關(guān)系，有如下二種：

step3.1:對有的Q，有nmax(P)<nmin(Q),則多邊形的確距觀察點(diǎn)最遠(yuǎn)，它不可能遮擋別的多邊形。令L=L–{P},返回step2;

step3.2:存在某一個(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所在平面的不可見的一側(cè)，則P,Q關(guān)系正確，令L=L–{P},返回step2;否則進(jìn)行下一步。

step3.2.3若Q的所有頂點(diǎn)位于P所在平面的可見的一側(cè)，則P,Q關(guān)系正確，令L=L–{P},返回step2;否則進(jìn)行下一步。

step3.2.4對P,Q投影P’,Q’求交，若P’,Q’不相交，則P,Q在表中的次序不重要，令L=L–{P},返回step2;否則在它們所相交的區(qū)域中任取一點(diǎn)，計(jì)算P,Q在該點(diǎn)的深度值，如果P的深度小，則P,Q關(guān)系正確，令L=L–{P},返回step2;否則交換P,Q,返回step3.第二十頁，共三十一頁，編輯于2023年，星期四畫家算法本算法不能處理的情況： 多邊形循環(huán)遮擋 多邊形相互穿透

解決辦法：分割成兩個(gè)第二十一頁，共三十一頁，編輯于2023年，星期四Z緩沖器算法由來：幀緩沖器–保存各像素顏色值z緩沖器--保存各像素處物體深度值

z緩沖器中的單元與幀緩沖器中的單元一一對應(yīng)思路：先將z緩沖器中個(gè)單元的初始值置為-1(規(guī)范視見體的最小n值）。當(dāng)要改變某個(gè)像素的顏色值時(shí)，首先檢查當(dāng)前多邊形的深度值是否大于該像素原來的深度值（保存在該像素所對應(yīng)的Z緩沖器的單元中），如果大于，說明當(dāng)前多邊形更靠近觀察點(diǎn)，用它的顏色替換像素原來的顏色；否則說明在當(dāng)前像素處，當(dāng)前多邊形被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變。

第二十二頁，共三十一頁，編輯于2023年，星期四Z緩沖器算法算法描述：

for(v=0;v<vmax;v++) for(u=0;u<umax;u++) {將幀緩沖器的第(u,v)單元置為背景色；將Z緩沖器的第(u,v)單元置為-1(可見的最小深度值)}for(每個(gè)多邊形） for（多邊形在投影平面上的投影區(qū)域內(nèi)的每個(gè)像素(u,v)）

{計(jì)算多邊形在當(dāng)前像素(u,v)處的深度值d； if(d>Z緩沖器的第(u,v)單元的值） {置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第(u,v)單元值為d;}}第二十三頁，共三十一頁，編輯于2023年，星期四Z緩沖器算法優(yōu)點(diǎn)：簡單穩(wěn)定，利于硬件實(shí)現(xiàn)缺點(diǎn)：1）需要一個(gè)額外的Z緩沖器 2）在每個(gè)多邊形占據(jù)的每個(gè)像素處都要計(jì)算深度值，計(jì)算量大第二十四頁，共三十一頁，編輯于2023年，星期四掃描線Z緩沖器算法由來：Z緩沖器算法中所需要的Z緩沖器容量較大，為克服這個(gè)缺點(diǎn)可以將整個(gè)繪圖區(qū)域分割成若干個(gè)小區(qū)域，然后一個(gè)區(qū)域一個(gè)區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個(gè)區(qū)域內(nèi)像素的個(gè)數(shù)就可以了。如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法。第二十五頁，共三十一頁，編輯于2023年，星期四掃描線Z緩沖器算法算法描述for(v=0;v<vmax;v++){ for(u=0;u<umax;u++)//對繪圖窗的每一條掃描線初始化 {將幀緩沖器的第(u,v)單元置為背景色；將Z緩沖器的第u單元置為-1（可見的最小深度值）}for(每個(gè)多邊形） {求出多邊形在投影平面上的投影與當(dāng)前掃描線的相交區(qū)間 for（該區(qū)間內(nèi)的每個(gè)像素(u,v)）

{計(jì)算多邊形在該像素處的深度值d； if(d>Z緩沖器的第u單元的值） {置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第u單元值為d;} }}}第二十六頁，共三十一頁，編輯于2023年，星期四區(qū)域子分算法由來：Z緩沖器算法與掃描線Z緩沖器算法中都是將像素孤立來考慮，未利用相鄰像素之間存在的屬性的連貫性，即區(qū)域的連貫性，所以算法效率不高。實(shí)際上，可見多邊形至少覆蓋了繪圖