計(jì)算機(jī)圖形學(xué)ppt課件 第七章真實(shí)感圖形顯

1、第七章 真實(shí)感圖形顯示 消隱 光照 圖案與紋理 顏色空間 消隱 消隱的分類 消除隱藏線 消除隱藏面 消隱 投影變換失去了深度信息，往往導(dǎo)致圖形的 二義性 要消除二義性，就必須在繪制時消除被遮擋的不可 見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，簡稱 為消隱。 經(jīng)過消隱得到的投影圖稱為物體的真實(shí)圖形。 長方體線框投影圖的二義性 消隱 消隱的對象是三維物體。三維體的表示主要 有邊界表示和CSG表示等。 消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān)。 線框圖 消隱圖 真實(shí)感圖形 消隱的分類 按消隱對象分類 線消隱 消隱對象是物體上的邊，消除的是物體 上不可見的邊。 面消隱 消隱對象是物體上的面，消除的是物體

2、上不可見的面。 消除隱藏線 對造型的要求 在線框顯示模型中,要求造型系統(tǒng)中有面的 信息，最好有體的信息。 坐標(biāo)變換 將視點(diǎn)變換到Z軸的正無窮大處，視線方向 變?yōu)閆軸的負(fù)方向。 最基本的運(yùn)算 判斷面對線的遮擋關(guān)系.反復(fù)地進(jìn)行線線、 線面之間的求交運(yùn)算 求交運(yùn)算 射線與直線求交運(yùn)算射線與直線求交運(yùn)算 假定直線方程為 射線方程為 把射線方程代入直線方程得到 0cbyax 02 01 ytdy xtdx 0)( 0021 cbyaxtbdad 當(dāng) 時,直線與射線平行,若還有 ,則整 條射線與直線重合。當(dāng) 時，則 0 21 bdad 0 00 cbdad 0 21 bdad )/()( 21001 bd

3、adcbyaxt 當(dāng) 時，二者交點(diǎn)為 ，當(dāng) 時，無 交點(diǎn) 0 1 t),( 012011 ytdxtd0 1 t 射線與線段求交問題射線與線段求交問題 假定射線方程如上一樣，線段的兩端點(diǎn)為 ，則線段的方程為 ),(),( 222111 yxpyxp ) 10( )( )( 112 112 s ysyyy xsxxx 射線方程代入上式得到 11202 11201 )( )( ysyyytd xsxxxtd 令 ，當(dāng) 時，射線與線段平行。 這時若還有 ，則線段與射線（或其反向延 長線）重合。 如果 ，則得到 212211 ,yybxxb 0 1221 bdbd )/()(/ 01012121 yy

4、xxbbdd 0 /,/ 012 011 1 001 101 1 yyd xxd s byy bxx t 當(dāng) ，射線與線段有唯一交點(diǎn)。將 代入射線方程，或 將 代入線段方程求得。 100 11 st并且 1 t 1 s 射線與平面求交問題射線與平面求交問題 假設(shè)一空間射線起點(diǎn)為 ，方向?yàn)?則該射線方程為 ),( 000 zyx),( 321 ddd )0( 03 02 01 t ztdz ytdy xtdx 又假設(shè)一任意平面，其方程為 。將射線方程代入平面方程 得 0dczbyax 0)()()( 030201 dztdcytdbxtda 整理得0)()( 000321 dczbyaxtcdb

5、dad 顯然，當(dāng) ，射線與平面平行。此時若還有 ，則整條射線落在平面上。除了這種情況外，射 線 （或其反向延長線）與平面交于一點(diǎn)，參數(shù)為 0 321 cdbdad 0 000 dczbyax )/()( 3210003 cdbdaddczbyaxt 當(dāng) 時，交點(diǎn)在射線上，否則交點(diǎn)在射線得反向延長線上（不算交點(diǎn)） 0 3 t 消除隱藏線 凸多面體的隱藏線消除 凹多面體的隱藏線消除 面消隱 面消隱算法的分類 提高消隱算法效率的常見方法 畫家算法 Z緩沖器算法(Z-Buffer) 掃描線Z緩沖器算法 區(qū)域子分算法 光線投射算法 面消隱算法的分類 第一類（圖像空間的消隱算法）：以窗口內(nèi)的每個像 素為處

6、理單元；如Zbuffer、掃描線、Warnock算法 for (窗口內(nèi)的每一個像素) 確定距視點(diǎn)最近的物體，以該物體表面的顏色來顯示像 素 第二類（物體空間的消隱算法）：以場景中的物體為 處理單元；如光線投射算法 for (場景中的每一個物體) 將其與場景中的其它物體比較，確定其表面的可見部 分； 顯示該物體表面的可見部分； 面消隱算法的分類 第一類（圖像空間的消隱算法）算法復(fù)雜 度：假設(shè)場景中有k個物體，平均每個物體 表面由h個多邊形構(gòu)成，顯示區(qū)域中有m x n個像素，算法的復(fù)雜度為：O(mnkh) 第二類（物體空間的消隱算法 ）算法復(fù)雜 度:假設(shè)場景中有k個物體，平均每個物體 表面由h個多

7、邊形構(gòu)成，顯示區(qū)域中有m x n個像素，算法的復(fù)雜度為：O(kh)*(kh) 提高消隱算法效率的常見方法 利用連貫性 將透視投影轉(zhuǎn)換成平行投影 包圍盒技術(shù) 背面剔除 空間分割技術(shù) 物體分層表示 方法1-利用連貫性 相鄰事物的屬性之間有一定的連貫性，其屬性值通 常是平緩過渡的，如顏色值、空間位置關(guān)系等。 連貫性有： u物體連貫性 u面的連貫性 u區(qū)域連貫性 u掃描線的連貫性 u深度連貫性 方法1-利用連貫性 u物體連貫性：如果物體A與物體B是完全相互分離的， 則在消隱時，只需比較A、B兩物體之間的遮擋關(guān)系就可 以了，無須對它們的表面多邊形逐一進(jìn)行測試。例如， 若A距視點(diǎn)較B遠(yuǎn)，則在測試B上的表面

8、的可見性時，無 須考慮A的表面。 u面的連貫性：一張面內(nèi)的各種屬性值一般都是緩慢變 化的，允許采用增量形式對其進(jìn)行計(jì)算。 u區(qū)域連貫性：區(qū)域指屏幕上一組相鄰的像素，它們通 常為同一個可見面所占據(jù)，可見性相同。區(qū)域連貫性表 現(xiàn)在一條掃描線上即為掃描線上的每個區(qū)間內(nèi)只有一個 面可見。 方法1-利用連貫性 u掃描線的連貫性：相鄰兩條掃描線上，可見面的分布 情況相似。 u深度連貫性：同一表面上的相鄰部分深度是相近的， 而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同。這樣在 判斷表面間的遮擋關(guān)系時，只需取其上一點(diǎn)計(jì)算出深度 值，比較該深度值即可得到結(jié)果。 方法2-透視投影轉(zhuǎn)換成平行投影 消隱與透視關(guān)系密切,體

9、現(xiàn)在： 1）消隱必須在投影之前完成； 2）物體之間的遮擋關(guān)系與投影中心（視點(diǎn)）的選取有 關(guān)； 3）物體之間的遮擋關(guān)系與投影方式有關(guān) 方法3-包圍盒技術(shù) 包圍盒概念：一個形體的包圍盒指的是包圍它的簡單形 體。 一個好的包圍盒要具有兩個條件： 包圍和充分緊密包圍著形體； 對其的測試比較簡單。 方法3-包圍盒技術(shù) 應(yīng)用避免盲目求交 例如：兩個空間多邊形A、B在投影平面上的投影分 別為A，B ，因?yàn)锳 、B的矩形包圍盒不相交，則A、 B不相交，無須進(jìn)行遮擋測試。右下圖：包圍盒相 交，投影也相交；包圍盒相交，投影不相交。 方法4-背面剔除 外法向：規(guī)定每個多邊形的外法向都是指向物體外部的。 前向面：若多

10、邊形的外法向與投影方向（觀察方向）的 夾角為鈍角，稱為前向面。 后向面：若多邊形的外法向與投影方向（觀察方向）的 夾角為銳角，稱為后向面（背面） 。 剔除依據(jù)：背面總是被前向面所遮擋，從而不可見。 方法4-背面剔除 V V A B C D E F G H I J N N V n V n 前向面后向面多面體的隱藏線消除 圖中的JEAF、HCBG和DEABC所在的面均為后 向面。 其它為前向面。 方法5-空間分割技術(shù) 依據(jù)：場景中的物體，它們的投影在投影平面上是否有 重疊部分？（是否存在相互遮擋的可能？）對于根本不 存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測試。 方法：將投影平面上的窗口分成若干

11、小區(qū)域；為每個小 區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交 部分；則在小區(qū)域中判斷那個物體可見時，只要對該區(qū) 域的相關(guān)物體表中的物體進(jìn)行比較即可。 方法6-物體分層表示 表示形式：模型變換中的樹形表示方式 原理：減少場景中物體的個數(shù)，從而降低算法復(fù)雜度。 方法6-物體分層表示 方法： 將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的 包圍盒，當(dāng)兩個父節(jié)點(diǎn)之間不存在遮擋關(guān)系時，就沒有 必要對兩者的子節(jié)點(diǎn)做進(jìn)一步測試。父節(jié)點(diǎn)之間的遮擋 關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測試。 畫家算法（列表優(yōu)先算法） l由來：畫家的作畫順序暗示出所畫物體之間的相互遮擋關(guān)系 l算法基本思想： 1）先把屏幕置成背景色

12、 2）先將場景中的物體按其距觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果放在 一張線性表中；（線性表構(gòu)造：距觀察點(diǎn)遠(yuǎn)的稱優(yōu)先級低，放在 表頭；距觀察點(diǎn)近的稱優(yōu)先級高，放在表尾。該表稱為深度優(yōu)先 級表） 3）然后按照從遠(yuǎn)到近（從表頭到表尾）的順序逐個繪制物體。 關(guān)鍵：如何對場景中的物體按深度（遠(yuǎn)近）排序，建立深度優(yōu)先 級表？ 畫家算法（列表優(yōu)先算法） l一種針對多邊形的排序算法如下： Step 1:將場景中所有多邊形存入一個線性表，記為L； Step 2: 如果L中僅有一個多邊形，算法結(jié)束；否則根據(jù) 每個多邊形的Zmin對它們預(yù)排序。不妨假定多邊形P落 在表首，即Zmin(P)為最小。再記Q為L P(表中其余 多

13、邊形）中任意一個； Step 3: 判別P, Q之間的關(guān)系，有如下二種： （1）: 對所有的Q，有Zmax(P) Zmin (Q),需 進(jìn)一步判別： 畫家算法（列表優(yōu)先算法） 例子： A）若P,Q的投影P,Q的包圍盒不相交（圖a）， 則P,Q在表中的次序不重要，令L = L P, 返回step 2; 否則進(jìn)行下一步。 畫家算法（列表優(yōu)先算法） B）若P的所有頂點(diǎn)位于Q所在平面的不可見的一側(cè)(圖b)， 則P,Q關(guān)系正確，令L = L P, 返回step 2;否則進(jìn)行下 一步。 畫家算法（列表優(yōu)先算法） C）若Q的所有頂點(diǎn)位于P所在平面的可見的一側(cè)(圖c)， 則P,Q關(guān)系正確，令L = L P,

14、返回step 2;否則進(jìn)行下 一步。 畫家算法（列表優(yōu)先算法） D）對P,Q投影P,Q求交，若P,Q不相交(圖d)，則P,Q在表中的次序不重要， 令L = L P, 返回step 2;否則在它們所相交的區(qū)域中任取一點(diǎn)，計(jì)算P,Q在該 點(diǎn)的深度值，如果P的深度小，則P,Q關(guān)系正確，令L = L P, 返回step 2;否 則交換P,Q,返回step 3. 畫家算法（列表優(yōu)先算法） 本算法不能處理的情況： 多邊形循環(huán)遮擋 多邊形相互穿透 解決辦法：分割成兩個 Z-Buffer算法 由來： 幀緩沖器 保存各像素顏色值 Z緩沖器 -保存各像素處物體深度值 Z緩沖器中的單元與幀緩沖器中的單元一一對應(yīng) 屏

15、幕幀緩沖器Z緩沖器 每個單元存放對應(yīng) 象素的顏色值 每個單元存放對應(yīng) 象素的深度值 Z-Buffer算法 算法思想：先將Z緩沖器中個單元的初始值置為最小值。 當(dāng)要改變某個像素的顏色值時，首先檢查當(dāng)前多邊形的 深度值是否大于該像素原來的深度值（保存在該像素所 對應(yīng)的Z緩沖器的單元中），如果大于，說明當(dāng)前多邊 形更靠近觀察點(diǎn)，用它的顏色替換像素原來的顏色；否 則說明在當(dāng)前像素處，當(dāng)前多邊形被前面所繪制的多邊 形遮擋了，是不可見的，像素的顏色值不改變。 Z-Buffer算法-算法描述 幀緩存全置為背景色 深度緩存全置為最小Z值 for(每一個多邊形) for(該多邊形所覆蓋的每個象素(x,y) )

16、計(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ù) =多邊形個數(shù)多邊形個數(shù)*多邊形平均占據(jù)的多邊形平均占據(jù)的 像素個數(shù)像素個數(shù) Z-Buffer算法 Z緩沖器算法是所有圖像空間算法中最簡單的一種隱藏 面消除算法。它在象素級上以近物取代遠(yuǎn)物，與形體在 屏幕上的出現(xiàn)順序無關(guān)。 優(yōu)點(diǎn)：1）簡單穩(wěn)定，利于硬件實(shí)現(xiàn) 2）不需要整個場景的幾何數(shù)據(jù) 缺點(diǎn): 1）需要一個額外的Z緩沖器 2）在每個多邊形占據(jù)的每個像素處都要計(jì)

17、算 深度值，計(jì)算量大 Z-Buffer算法-改進(jìn)算法 只用一個深度緩存變量zb的改進(jìn)算法。 一般認(rèn)為，Z-Buffer算法需要開一個與圖象大小相 等的緩存數(shù)組ZB，實(shí)際上，可以改進(jìn)算法，只用一 個深度緩存變量zb。 Z-Buffer算法-改進(jìn)算法 幀緩存全置為背景色幀緩存全置為背景色 for(屏幕上的每個象素屏幕上的每個象素(i,j) 深度緩存變量深度緩存變量zb置最小值置最小值MinValue for(多面體上的每個多邊形多面體上的每個多邊形Pk) if(象素點(diǎn)象素點(diǎn)(i,j)在在pk的投影多邊形之內(nèi)的投影多邊形之內(nèi)) 計(jì)算計(jì)算Pk在在(i,j)處的深度值處的深度值depth; if(dep

18、th大于大于zb) zb = depth; indexp = k; if(zb != MinValue) 在交點(diǎn)在交點(diǎn) (i,j) 處用多邊形處用多邊形Pindexp的顏色顯示的顏色顯示 Z-Buffer算法-改進(jìn)算法 0dczbyax 關(guān)鍵問題：判斷象素點(diǎn)(i,j)是否在多邊形Pk的投影 多邊形之內(nèi) 計(jì)算多邊形Pk在點(diǎn)（i，j）處的深度。設(shè)多邊形Pk 的平面方程為： c dbjai depth 掃描線Z-buffer算法 由來：Z緩沖器算法中所需要的Z緩沖器容 量較大，為克服這個缺點(diǎn)可以將整個繪圖 區(qū)域分割成若干個小區(qū)域，然后一個區(qū)域 一個區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只 要等于一個區(qū)域內(nèi)

19、像素的個數(shù)就可以了。 如果將小區(qū)域取成屏幕上的掃描線，就得 到掃描線Z緩沖器算法。 掃描線Z-buffer算法 算法思想: 在處理當(dāng)前掃描線時，開一個一維數(shù)組作為當(dāng) 前掃描線的Z-buffer。首先找出與當(dāng)前掃描線找出與當(dāng)前掃描線 相關(guān)的多邊形，以及每個多邊形中相關(guān)的邊對相關(guān)的多邊形，以及每個多邊形中相關(guān)的邊對。 對每一個邊對之間的小區(qū)間上的各象素，計(jì)算 深度，并與Z-buffer中的值比較，找出各象素 處可見平面。 寫幀緩存。采用增量算法計(jì)算深度。 掃描線Z-buffer算法 for ( v= 0;vvmax;v+) for (u= 0; u Z緩沖器的第u單元的值） 置幀緩沖器的第(u,v

20、)單元值為當(dāng)前多邊形顏色； 置Z緩沖器的第u單元值為d; /處理下一條掃描線 掃描線Z-buffer算法 改進(jìn)之一：將窗口分割成掃描線 Z緩沖器的單元數(shù)只要等于一條掃描線內(nèi)像素的個數(shù)就可以 了。 掃描線Z-buffer算法 改進(jìn)之二：采用多邊形分類表、活化 多邊形表避免多邊形多邊形與掃描線的盲目 求交 多邊形分類表（PT）：對多邊形進(jìn)行分類 的一維數(shù)組，長度等于繪圖窗口內(nèi)掃描線 的數(shù)目。若一個多邊形在投影平面上的投 影的最小v坐標(biāo)為v，則它屬于第v類。 掃描線Z-buffer算法 掃描線Z-buffer算法 活化多邊形表（APL）：記錄 投影與當(dāng)前掃描線相交的多邊形。 掃描線Z-buffer算

21、法-多邊形 其中，多邊形的數(shù)據(jù)結(jié)構(gòu)如下： a,b,c,d：多邊形所在平面方程f(u,v,n)=au+bv+cn+d=0 的系數(shù)。 color:多邊形的顏色 vmax:多邊形在投影平面上的投影的最大v坐標(biāo)值。 PI：多邊形的序號 nextP：指向下一個多邊形結(jié)構(gòu)的指針 掃描線Z-buffer算法 改進(jìn)之三：利用邊、邊的分類表、邊對、活化邊 對表避免邊邊與掃描線的盲目求交 掃描線Z-buffer算法-邊數(shù)據(jù)結(jié)構(gòu) 邊：用來記錄多邊形的一條邊，其中vmax：邊的投影 的上端點(diǎn)的v坐標(biāo)。 u：邊的下端點(diǎn)的u坐標(biāo) n：邊的下端點(diǎn)的n坐標(biāo) u：在該邊上v值增加一個單位時，u坐標(biāo)的變化量 nextE：指向下一

22、條邊結(jié)構(gòu)的指針。 掃描線Z-buffer算法 邊的分類表（ET）：當(dāng)一個多邊形進(jìn)入活化多邊形表時， 需為其建立一個邊分類表（ET）。這里，ET與其在掃描 轉(zhuǎn)換多邊形的掃描線算法中的含義相同，是對多邊形的非 水平邊進(jìn)行分類的一維數(shù)組，長度等于繪圖窗口內(nèi)掃描線 的數(shù)目。若一條邊在投影平面上的投影的下端點(diǎn)的v坐標(biāo) 為v，則將該邊歸為第v類。 區(qū)域子分算法（Warnock 算法) 由來： Z緩沖器算法與掃描線Z緩沖器算法中都是 將像素孤立來考慮，未利用相鄰像素之間存在的 屬性的連貫性，即區(qū)域的連貫性，所以算法效率 不高。實(shí)際上，可見多邊形至少覆蓋了繪圖窗內(nèi) 的一塊區(qū)域，這塊區(qū)域由多邊形在投影平面上的

23、投影的邊界圍成。如果能將這類區(qū)域找出來，再 用相應(yīng)的多邊形顏色加以填充則避免了在每個像 素處計(jì)算深度值，消隱問題也就解決了。 區(qū)域子分算法（Warnock 算法） 算法基本思路：首先將場景中的多邊形投 影到繪圖窗口內(nèi)（假設(shè)它為邊長為k的正方 形），判斷窗口是否足夠簡單，若是則算法 結(jié)束；否則將窗口進(jìn)一步分為四塊。對此 四個小窗口重復(fù)上述過程，直到窗口僅為 一個像素大小。此時可能有多個多邊形覆 蓋了該像素，計(jì)算它們的深度值，以最近 的顏色顯示該像素即可。 區(qū)域子分算法（Warnock 算法） 何謂窗口足夠簡單？ 存在下列情況之一即可稱為窗口足夠簡單： 1）窗口為空，即多邊形與窗口的關(guān)系是分離的；

24、 2）窗口內(nèi)僅含一個多邊形，即有一個多邊形與窗 口的關(guān)系是包含或相交。此時先對多邊形投影進(jìn) 行裁剪，再對裁剪結(jié)果進(jìn)行填充； 3）有一個多邊形的投影包圍了窗口，并且它是最 靠近觀察點(diǎn)的，以該多邊形顏色填充窗口。 區(qū)域子分算法（Warnock 算法） 區(qū)域子分算法（Warnock 算法） 分離和包圍多邊形的判別：通常有3種判別 方法：射線檢查法，轉(zhuǎn)角累計(jì)檢查法和區(qū) 域檢查法。這三種檢查都假定相交的和內(nèi) 含的多邊形已經(jīng)事先判定了。 射線檢查法：從窗口內(nèi)的任意點(diǎn)，畫一 條射線至無窮遠(yuǎn)處，累計(jì)射線與多邊形 交點(diǎn)的個數(shù)。如果為偶數(shù)(或?yàn)榱?，則 此多邊形與窗口分離；否則，此多邊形 包圍窗口。但當(dāng)射線通過多

25、邊形的頂點(diǎn) 時，會得出錯誤結(jié)論。(如左圖)解決方 法有：當(dāng)射線通過多邊形的局部極值頂 點(diǎn)時，記入兩個交點(diǎn)；當(dāng)射線通過多邊 形的非局部極值頂點(diǎn)時，記入一交點(diǎn)。 y x p6 p7 p8 p4 p10 p9 p3 p1 p2 p5 y x p6 p4 p3 p1 p2 p5 p6 區(qū)域子分算法（Warnock 算法） 轉(zhuǎn)角累計(jì)檢查法:按順時針方向或逆時針方向繞多邊形依次累加多邊 形各邊起點(diǎn)與終點(diǎn)對窗口內(nèi)任意一點(diǎn)所張的夾角。按累計(jì)角度之和可 以判定： 若角度之和等于0，則表示多邊形與窗口分離； 若角度之和等于360 *n，則表示多邊形包圍窗口(n次)。 多邊形多邊形 窗口窗口 窗口窗口 多邊形多邊形

26、 區(qū)域子分算法（Warnock 算法 區(qū)域檢查法: 1）區(qū)域編碼 2）多邊形頂點(diǎn)編碼 3）多邊形邊的編碼 4）多邊形的編碼 區(qū)域子分算法（Warnock 算法) 1、區(qū)域編碼。窗口四條 邊所在直線將屏幕劃分成 9個區(qū)域，對窗口以外的 8個區(qū)域按逆時針（或順 時針）進(jìn)行編碼，編碼為 07。 2、多邊形頂點(diǎn)編碼。多 邊形v0v1vn的頂點(diǎn)vi的投 影落在哪個區(qū)域，那個區(qū) 域的編碼便作為該頂點(diǎn)的 編碼，記為Ii。 區(qū)域子分算法（Warnock 算法) 3、多邊形的編碼。多邊形的邊vivi+1的編碼 定義為i=Ii+1-Ii，i=0,1n；其中，令I(lǐng)n+1=I0， 并且，當(dāng)i 4時，取i = i -8

27、；當(dāng)i 4時， 取i = i +8； 當(dāng)i =+/-4時，取該邊與窗口邊的延長線的 交點(diǎn)將該邊分為兩段，對兩段分別按上面 的規(guī)則編碼，再令i等于兩者之和。 4、多邊形的編碼。定義多邊形的編碼為其 邊的編碼之和 ，則 區(qū)域子分算法（Warnock 算法) 8 0 0 0 n i i n i i 當(dāng)多邊形包圍窗口 當(dāng)窗口與多邊形分離 區(qū)域子分算法（Warnock 算法) 例如：I0=5,I1=7,I2=3, 0=7-5=2, 1=3-7=-4, 2=5-3=2, 因?yàn)?=-4,按 第三步的處理規(guī)則，取邊 v1v2與窗口上邊所在直線 的交點(diǎn)將v1v2分為兩段， 兩段的編碼分別為2，2， 從而2=4。

28、最終求出多 邊形的編碼為 0+ 1+2=2+4+2=8，因 此，該三角形包圍窗口。 區(qū)域子分算法（Warnock 算法) 如圖：I0=1,I1=3,I2=7, 0=3-1=2, 1=7-3=4, 2=1-7=-6。按第3步處理 規(guī)則，取v1v2與窗口上邊 所在直線的交點(diǎn)v將其分 為兩段，兩段的編碼分別 為-2，-2，從而1=-2+（- 2）=-4。而2=-6+8=2。 最終求出多邊形的編碼為 0+1+2=2+（-4）+2=0。 從而得出結(jié)論：多邊形與 窗口分離。 光線投射算法 算法思想：將通過繪圖窗口內(nèi)每一個像素的投影線與場景 中的所有多邊形求交。如果有交點(diǎn)，用深度值最大的交點(diǎn) （最近的）所屬

29、的多邊形的顏色顯示相應(yīng)的像素；如果沒 有交點(diǎn)，說明沒有多邊形的投影覆蓋此像素，用背景色顯 示即可。 光線投射算法-算法描述 for ( v= 0;vvmax;v+) for (u= 0; uumax; u+) 形成通過像素(u,v)的投影線； for (場景中每一個多邊形） 將投影線與多邊形求交； if (有交點(diǎn)） 以最近交點(diǎn)所屬多邊形的顏色顯示像素(u,v) else 以背景色顯示像素(u,v)； 光線投射算法 基本問題 光線與物體表面的求交 光線投射算法-算法描述 for ( v= 0;vvmax;v+) for (u= 0; uZf時，取S0=Sf 當(dāng)Z0 t,即ti。如果入射角不斷增大

30、，到一 定的程度，折射角t 90度，此時透射光線 沿著平行于分界面的方向傳播，稱此時的i 為臨界角度，記為c 。當(dāng)i c時，發(fā)生全 反射，透射與反射光合二為一。 光透射模型的研究 早期簡單透射現(xiàn)象的模擬 1980年，Whitted光透射模型，首次考慮了 光線的折射現(xiàn)象 1983年，在Whitted的基礎(chǔ)上，Hall光透射 模型，考慮了漫透射和規(guī)則透射光 整體光照明模型 簡單光照明模型亦稱局部光照明模型，其 假定物體是不透明的，只考慮光源的直接 照射，而忽略了光在環(huán)境景物之間的傳遞。 為了增加圖形的真實(shí)感，必須考慮環(huán)境的 漫射、鏡面反射和規(guī)則投射對景物表面產(chǎn) 生的整體照明效果。 整體光照明模型考

31、慮了物體之間的相互影 響以產(chǎn)生整體照明效果 整體光照明模型 物體表面入射光的構(gòu)成 （1）光源直接照射 （2）其它物體的反射光 （3）透射光 局部光照明模型僅考慮了（1） 整體光照明模型 例如：從視點(diǎn)觀察到的物體A表面 的亮度來源于三方面的貢獻(xiàn)： （1）光源直接照射到A的表面，然 后被反射到人眼中的光產(chǎn)生的。 （2）光源或其它物體的光經(jīng)A物體 折射到人眼中的光產(chǎn)生的。 （3）物體B的表面將光反射到物體A 的表面，再經(jīng)物體A的表面反射到 人眼中產(chǎn)生的。 局部光照明模型僅考慮了（1） Witted光照模型 Whitted光照模型基于如下假設(shè)： 物體表面向視點(diǎn)方向V輻射的光亮度I由三 部分組成： （1

32、）光源直接照射引起的反射光亮度Il。 （2）來自V的鏡面反射方向R的其它物體反 射或折射來的光的亮度Is。 （3）來自V的透射方向T的其它物體反射或 折射來的光的亮度It Witted光照模型 Witted光照模型：I= Il + Ks Is + KtIt 或 Is為鏡面反射方向的入射光強(qiáng)度；Ks為鏡面反射系數(shù)， 為01之間的一個常數(shù) It為折射方向光強(qiáng)，Kt為透射系數(shù)，是0 1之間的常 數(shù) Il的計(jì)算可采用Phong模型 因此，關(guān)鍵是Is和It的計(jì)算。如何計(jì)算呢？ tttsssl ICKICKII Witted光照模型-反射、折射方向計(jì)算 已知視線方向V，求其 反射方向R與折射方向 T（N是表面的法向方 向） 視線V的反射方向R 折射方向T VVNNR)(2 INT ti t i )coscos( 令 N V R L T i i t i t T、R方向確定后，下一步即可 計(jì)算沿二方向投射景物表面上 的光亮度，即 光線跟蹤（Raytracing） 該方法由Appel于1968年提出。 光線跟蹤算法的基本原理 自然界中光線的傳播過程 光源物體表面 物體表面 人眼 光線跟蹤過程-光線傳播的逆過程 光線跟蹤 從視點(diǎn)向每個象素發(fā)出一條光線，它與場景中的一些物體表面相交，最近的 交點(diǎn)即為可見點(diǎn)，記為P，像素的亮度