計(jì)算機(jī)圖形學(xué)第九章部分

1、2024/3/31,1,第九章：真實(shí)感圖形學(xué),9.1 消隱用計(jì)算機(jī)生成三維物體的真實(shí)圖形，是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容。真實(shí)圖形在仿真模擬、幾何造型、廣告影視、指揮控制和科學(xué)計(jì)算的可視化等許多領(lǐng)域都有廣泛應(yīng)用在用顯示設(shè)備描述物體的圖形時，必須把三維信息經(jīng)過某種投影變換，在二維的顯示表面上繪制出來。由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性(如圖9.1所示)要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習(xí)慣上稱作消除

2、隱藏線和隱藏面，或簡稱為消隱。經(jīng)過消隱得到的投影圖稱為物體的真實(shí)圖形,2024/3/31,2,第九章：真實(shí)感圖形學(xué),圖9.1 長方體線框投影圖的二義性,圖9.2線框圖           圖9.3 消隱圖            圖9.4真實(shí)感圖形,2

3、024/3/31,3,第九章：真實(shí)感圖形學(xué),消隱的分類消隱的對象是三維物體。三維體的表示有邊界表示和CSG(結(jié)構(gòu)實(shí)體幾何學(xué))表示等。最簡單的表示方式是用表面上的平面多邊形表示。如物體的表面是曲面，則將曲面用多個平面多邊形近似。 消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān)。 按消隱對象分類線消隱 消隱對象是物體上的邊，消除的是物體上不可見的邊面消隱消隱對象是物體上的面，消除的是物體上不可見的面,2024/3/31,4,第九章：真實(shí)感

4、圖形學(xué),Southerland根據(jù)消隱空間的不同，將消隱算法分為三類物體空間的消隱算法 (光線投射、Roberts) 將場景中每一個面與其他每個面比較，求出所有點(diǎn)、邊、面遮擋關(guān)系圖像空間的消隱算法 (Z－buffer、掃描線、warnock)對屏幕上每個象素進(jìn)行判斷，決定哪個多邊形在該象素可見物體空間和圖像空間的消隱算法 (畫家算法)在物體空間中預(yù)先計(jì)算面的可見性優(yōu)先級，再在圖像空間中生成消隱圖,2024/3/31,5,第九

5、章：真實(shí)感圖形學(xué),消除隱藏線對造型的要求 在線框顯示模型中，用邊界線表示有界平面，用邊界線及若干參數(shù)曲線表示參數(shù)曲面，所以待顯示的所有實(shí)體均為線但線不可能對線有遮擋關(guān)系，只有面或體才有可能對線形成遮擋故消隱算法要求造型系統(tǒng)中有面的信息，最好有體的信息。正則形體的消隱可利用其面的法向量，這樣比一般情況快的多坐標(biāo)變換 為運(yùn)算方便，一般通過平移、旋轉(zhuǎn)、透視等各種坐標(biāo)變換，將視點(diǎn)變換到Z軸的正無窮大處，視線方向變?yōu)閆軸的負(fù)方向。變換

6、后，坐標(biāo)Z值反映了相應(yīng)點(diǎn)到視點(diǎn)的距離，可以作為判斷遮擋的依據(jù)。另外，對視錐以外的物體應(yīng)先行慮掉，以減少不必要的運(yùn)算,2024/3/31,6,第九章：真實(shí)感圖形學(xué),線消隱中最基本的運(yùn)算 判斷面對線的遮擋關(guān)系。體也要分解為面，再判斷面與線的遮擋關(guān)系。在遮擋判斷中，要反復(fù)地進(jìn)行線線、線面之間的求交運(yùn)算,2024/3/31,7,第九章：真實(shí)感圖形學(xué),平面對直線段的遮擋判斷算法不失一般性，取視點(diǎn)在Z軸正無窮遠(yuǎn)，視線為Z軸負(fù)方向，物體投影到X

7、OY平面上若線段的兩端點(diǎn)及視點(diǎn)在給定多邊形的同側(cè)，線段不被其遮擋，轉(zhuǎn)7。(深度檢測，多邊形頂點(diǎn)的最大Z坐標(biāo)小于等于線段端點(diǎn)的最小Z坐標(biāo)，多邊形完全在線段之后，不可能遮擋線段，即線段完全可見),圖9.6 視點(diǎn)與線段同側(cè),2024/3/31,8,第九章：真實(shí)感圖形學(xué),若線段的投影與多邊形投影的包圍盒(覆蓋多邊形投影的最小矩形區(qū)域)無交，線段不被給定多邊形遮擋，轉(zhuǎn)7求直線與相應(yīng)多邊形的交。若無交點(diǎn)（平行），轉(zhuǎn)4。否則，交點(diǎn)在線段內(nèi)部或外部

8、。若交點(diǎn)在線段內(nèi)部，交點(diǎn)將線段分成兩段，與視點(diǎn)同側(cè)的一段不被遮擋，另一段在視點(diǎn)異側(cè)，轉(zhuǎn)4再判；若交點(diǎn)在線段外部，轉(zhuǎn)4,圖9.7 包圍盒不交,2024/3/31,9,第九章：真實(shí)感圖形學(xué),求所剩線段(可能被遮擋部分)的投影與多邊形邊界投影的所有交點(diǎn)，并根據(jù)交點(diǎn)在原直線參數(shù)方程中的參數(shù)值求出Z值(即深度)。若無交點(diǎn)，轉(zhuǎn)5以上所求得的各交點(diǎn)將線段的投影分成若干段，求出第一段中點(diǎn)若第一段中點(diǎn)在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其

9、他段的遮擋關(guān)系可依次交替取值進(jìn)行判斷結(jié)束,,圖9.8 分段交替取值,2024/3/31,10,第九章：真實(shí)感圖形學(xué),如果消隱對象有N條棱，當(dāng)N很大時，用兩兩求交的方法這個工作量是很大的O(N2)。為了提高算法的效率，需要設(shè)法減少求交的工作量設(shè)V為由視點(diǎn)出發(fā)的觀察向量，N為某多邊形面的法向量若V·N>0，稱該多邊形為后向面若V·N<0，稱該多邊形為前向面如下圖中的JEAF、HCBG和DEABC所在

10、的面均為后向面后向面總是看不見的，不會僅由于后向面的遮擋，而使別的棱成為不可見的。因此可以把這些后向面全部去掉，這并不影響消隱結(jié)果,2024/3/31,11,第九章：真實(shí)感圖形學(xué),,圖 9.9   (a)前向面         (b)后向面       

11、 (c)多面體的隱藏線消除,2024/3/31,12,第九章：真實(shí)感圖形學(xué),消除隱藏面在使用光柵圖形顯示器繪制物體的真實(shí)圖形時，必須解決消除隱藏面的問題畫家算法(列表優(yōu)先算法)先把屏幕置成背景色再把物體的各個面按其離視點(diǎn)的遠(yuǎn)近進(jìn)行排序，離視點(diǎn)遠(yuǎn)者(Z最小)在表頭，離視點(diǎn)近者(Z最大)在表尾，排序結(jié)果存在一張深度優(yōu)先級表中從表頭到表尾逐個取出多邊形投影到屏幕并顯示多邊形包含的實(shí)心區(qū)域由于后顯示的圖形取代先顯示的畫面

12、，而后顯示的圖形所代表的面離視點(diǎn)更近，所以由遠(yuǎn)及近的繪制各面，就相當(dāng)于消除隱藏面這與油畫作家作畫的過程類似，先畫遠(yuǎn)景，再畫中景，最后畫近景,2024/3/31,13,第九章：真實(shí)感圖形學(xué),檢驗(yàn)深度優(yōu)先級表中相鄰面的順序深度重疊判斷若P,Q是深度優(yōu)先級表中兩個相鄰的多邊形，且Zmax(P)≥Zmin(P)≥Zmax(Q)，則Q不可能遮擋P的任何部分，可以在P之前畫出。完成這一測試需使多邊形數(shù)據(jù)結(jié)構(gòu)包括所有頂點(diǎn)的最小和最大Z坐標(biāo)投影

13、重疊判斷如果P和Q在XY平面上的投影的包圍盒不重疊，則P,Q不可能互相遮擋，其順序無關(guān)緊要。完成這一測試需把最大和最小的X,Y坐標(biāo)存在面的數(shù)據(jù)表里,2024/3/31,14,第九章：真實(shí)感圖形學(xué),P在Q之前（條件1比條件3嚴(yán)格）如果P的所有頂點(diǎn)在Q所在平面的可見一側(cè)，則Q不會遮擋P的任何部分。完成這一測試需把P的各頂點(diǎn)坐標(biāo)代入Q的平面方程，如果所得式子的符號與視點(diǎn)代入方程的符號相同，則P在Q的可見一側(cè)。面的數(shù)據(jù)表需包含方程系數(shù)Q在

14、P之前如果“P在Q之前”測試失敗，應(yīng)該進(jìn)行“Q在P之前”的逆測試，即把所有Q的頂點(diǎn)代入P的方程檢驗(yàn)與代入視點(diǎn)得到的符號是否相同，如果測試通過應(yīng)該把P,Q在深度優(yōu)先級表中的順序顛倒過來,2024/3/31,15,第九章：真實(shí)感圖形學(xué),精確的重疊測試如果所有測試失敗，就必須對多邊形在XY平面上的投影作求交計(jì)算計(jì)算時不必具體求出重疊部分，只要能判斷出前后順序即可最簡單的方法是對每對邊(一條P邊，一條Q邊)作線段求交測試，若沒有循環(huán)重疊

15、情況，則只要求出第一個交點(diǎn)，在交點(diǎn)處進(jìn)行深度比較即可確定二者順序畫家算法原理簡單。其關(guān)鍵是如何對場景中的物體按深度排序它的缺點(diǎn)是只能處理互不相交的面，而且深度優(yōu)先級表中面的順序可能出錯。在兩個面相交，三個以上的面重疊的情形，用任何排序方法都不能排出正確的序。這時只能把有關(guān)的面進(jìn)行分割后再排序,2024/3/31,16,第九章：真實(shí)感圖形學(xué),2024/3/31,17,第九章：真實(shí)感圖形學(xué),Z緩沖區(qū)(Z-Buffer)算法畫家算法中，

16、深度排序計(jì)算量大，而且排序后，還需再檢查相鄰的面，以確保在深度優(yōu)先級表中前者在前，后者在后。若遇到多邊形相交，或多邊形循環(huán)重疊的情形，還必須分割多邊形為了避免這些復(fù)雜的運(yùn)算，人們發(fā)明了Z緩沖區(qū)(Z-Buffer)算法。在這個算法里，不僅需要有幀緩存來存放每個象素的顏色值，還需要一個深度緩存來存放每個象素的深度值Z緩沖器中每個單元的值是對應(yīng)象素點(diǎn)所反映對象的z坐標(biāo)值，Z緩沖器中每個單元的初值取成z的極小值（離視點(diǎn)最遠(yuǎn)）。幀緩沖器每個單

17、元的初值可放對應(yīng)背景顏色的值圖形消隱的過程就是給幀緩沖器和Z緩沖器中相應(yīng)單元填值的過程,2024/3/31,18,第九章：真實(shí)感圖形學(xué),,圖9.10 Z緩沖區(qū)示意圖,2024/3/31,19,第九章：真實(shí)感圖形學(xué),在把顯示對象的每個面上每一點(diǎn)的屬性(顏色或灰度)值填入幀緩沖器相應(yīng)單元前，要把這點(diǎn)的z坐標(biāo)值和z緩沖器中相應(yīng)單元的值進(jìn)行比較只有前者大于后者時（離視點(diǎn)更近）才改變幀緩沖器的那一單元的值，同時z緩沖器中相應(yīng)單元的值也要改成這

18、點(diǎn)的z坐標(biāo)值如果這點(diǎn)的z坐標(biāo)值小于z緩沖器中的值，則說明對應(yīng)象素已經(jīng)顯示了對象上一個點(diǎn)的屬性，該點(diǎn)要比考慮的點(diǎn)更接近觀察點(diǎn)對顯示對象的每個面上的每個點(diǎn)都做了上述處理后，便可得到消除了隱藏面的圖,2024/3/31,20,第九章：真實(shí)感圖形學(xué),多邊形在各象素深度值的增量求法對于一給定的多邊形，在某一點(diǎn)(x,y)的深度值可通過平面方程ax+by+cz+d=0表示為z=(-d-ax-by)/c若在(x,y)處求出z值是z1,則在(x+

19、Δx,y)處的z值為z1-a/c(Δx)。這里a/c是常數(shù)，且一般取Δx=1。所以當(dāng)已知(x,y)處的深度值時，求(x+1,y)處的深度值只要做一次減法Z-Buffer算法在象素級上以近物取代遠(yuǎn)物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的。這種取代方法實(shí)現(xiàn)起來遠(yuǎn)比總體排序靈活簡單，有利于硬件實(shí)現(xiàn)Z-Buffer算法的缺點(diǎn)占用空間大，沒有利用圖形的相關(guān)性與連續(xù)性。 Z-Buffer算法以算法簡單著稱，但也以占空間大而聞名。一般認(rèn)為，Z-B

20、uffer算法需要開一個與圖象大小相等的緩存數(shù)組ZB，實(shí)際上，可以改進(jìn)算法，只用一個深度緩存變量zb,2024/3/31,21,第九章：真實(shí)感圖形學(xué),Z-Buffer算法(){  幀緩存全置為背景色   深度緩存全置為最小Z值   for(每一個多邊形)   { 掃描轉(zhuǎn)換該多邊形    

21、 for(該多邊形所覆蓋的每個象素(x,y) )     { 計(jì)算該多邊形在該象素的深度值Z(x,y);        if(Z(x,y)大于Z緩存在(x,y)的值)       

22、 {  把Z(x,y)存入Z緩存中(x,y)處           把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處 }       }   }

23、},2024/3/31,22,第九章：真實(shí)感圖形學(xué),區(qū)間掃描線算法與Z－buffer算法相比，掃描線Z－buffer算法(未講)做了兩點(diǎn)改進(jìn)將整個繪圖窗口內(nèi)的消隱問題分解到一條條掃描線上解決，使所需的Z緩沖器大大減少計(jì)算深度值時，利用了面連貫性，只用了一個加法。但它在每個象素處都計(jì)算深度值，進(jìn)行深度比較。因此，被多個多邊形覆蓋的象素區(qū)處還要進(jìn)行多次計(jì)算，計(jì)算量仍然很大區(qū)間掃描線算法克服了這一缺陷，使得在一條掃描線上每個區(qū)間只計(jì)

24、算一次深度值，并且不需要Z緩沖器它是把當(dāng)前掃描線與各多邊形在投影平面的投影的交點(diǎn)進(jìn)行排序后，使掃描線分為若干子區(qū)間。因此，只要在區(qū)間任一點(diǎn)處找出在該處z值最大的一個面，這個區(qū)間上的每一個象素就用這個面的顏色來顯示,2024/3/31,23,第九章：真實(shí)感圖形學(xué),,圖9.15  掃描線與多邊形的投影相交得到若干子區(qū)間,2024/3/31,24,第九章：真實(shí)感圖形學(xué),確定小區(qū)間的顏色小區(qū)間上沒有任何多邊形，如[a4,a5]，這

25、時該小區(qū)間用背景色顯示小區(qū)間上只有一個多邊形，如[a1,a2]，[a3,a4]，[a5,a6]，[a7,a8]，以對應(yīng)多邊形在該處的顏色顯示小區(qū)間上存在兩個或兩個以上的多邊形, 形如[a6,a7]，必須通過深度測試判斷可見多邊形，并表示為其顏色若允許物體表面相互貫穿時，還必須求出它們在掃描平面(ZX平面)的交點(diǎn)。用這些交點(diǎn)把該小區(qū)間分成更小的子區(qū)間(稱為間隔)，在這些間隔上決定哪個多邊形可見。如將[a2,a3]區(qū)間分成[a2,b]

26、[b,a3]兩個子區(qū)間為了確定某間隔內(nèi)哪一多邊形可見，可在間隔內(nèi)任取一采樣點(diǎn)(如間隔中點(diǎn))，分析該點(diǎn)處哪個多邊形離視點(diǎn)最近，該多邊形即是在該間隔內(nèi)可見的多邊形。在[a2,b]上F2可見，在[b,a3]F1可見,2024/3/31,25,第九章：真實(shí)感圖形學(xué),圖9.16 (a)兩個平面在屏幕上的投影 (b)無貫穿的情形   (c) 相互貫穿的情形掃描線段a2a3在空間多邊形上的交線投影到XZ平面去判斷Z大小,2024/3/3

27、1,26,第九章：真實(shí)感圖形學(xué),區(qū)域子分割算法(Warnack算法，區(qū)域采樣算法)畫家算法、Z緩沖區(qū)算法和掃描線算法都是點(diǎn)取樣算法，繪制圖形時總是在投影面取一組離散點(diǎn)，在各個離散點(diǎn)解決消隱問題，以及確定顏色亮度，用于顯示屏幕上的對應(yīng)象素區(qū)域采樣算法是利用區(qū)域的連貫性，在連續(xù)的區(qū)域上確定可見面及其顏色、亮度區(qū)域采樣算法基本思想把物體投影到全屏幕窗口上，然后遞歸分割窗口，直到窗口內(nèi)目標(biāo)足夠簡單可以顯示為止首先，該算法把初始窗口取作

28、屏幕坐標(biāo)系的矩形，將場景中的多邊形投影到窗口內(nèi)如果窗口內(nèi)沒有物體則按背景色顯示；若窗口內(nèi)只有一個面，則把該面顯示出來,2024/3/31,27,第九章：真實(shí)感圖形學(xué),否則，窗口內(nèi)含有兩個以上的面，則把窗口等分成四個子窗口。對每個小窗口再做上述同樣的處理。這樣反復(fù)地進(jìn)行下去。如果到某個時刻，窗口僅有象素那么大，而窗口內(nèi)仍有兩個以上的面，這時不必再分割，只要取窗口內(nèi)最近的可見面的顏色或所有可見面的平均顏色作為該象素的值四叉樹算法假設(shè)全

29、屏幕窗口分辨率為1024×1024。窗口以左下角點(diǎn)(x，y)和邊寬s定義。下圖為使用棧結(jié)構(gòu)實(shí)現(xiàn)的區(qū)域子分割算法流圖。由于算法中每次遞歸的把窗口分割成四個與原窗口相似的小窗口，故這種算法通常稱為四叉樹算法,2024/3/31,28,第九章：真實(shí)感圖形學(xué),2024/3/31,29,第九章：真實(shí)感圖形學(xué),,圖9.19  區(qū)域子分割算法流圖,2024/3/31,30,第九章：真實(shí)感圖形學(xué),窗口與多邊形的覆蓋關(guān)系內(nèi)含、相交、

30、包圍和分離判斷內(nèi)含和相交關(guān)系可以借助于裁剪算法來解決不必具體求出交點(diǎn)和裁剪，只要判斷出多邊形含于窗口內(nèi)或多邊形某邊與窗口某邊有交就可以了判斷包圍和分離的轉(zhuǎn)角檢查方法按順時針或逆時針方向繞多邊形邊界一周，累計(jì)相鄰的兩個頂點(diǎn)對窗口所張的角之和∑α，若∑α＝360º, 則多邊形包含窗口。若∑α＝0， 則多邊形與窗口分離判斷包圍和分離區(qū)域編碼法把窗口外的平面區(qū)域分為八個區(qū)，編號為0-7, 多邊形的每個頂點(diǎn)一定落在某個區(qū)域內(nèi)

31、，否則為前述的內(nèi)含或相交關(guān)系。頂點(diǎn)所在區(qū)的編號就作為頂點(diǎn)的編號,2024/3/31,31,第九章：真實(shí)感圖形學(xué),窗口與多邊形的覆蓋關(guān)系內(nèi)含、相交、包圍和分離判斷內(nèi)含和相交關(guān)系可以借助于裁剪算法來解決不必具體求出交點(diǎn)和裁剪，只要判斷出多邊形含于窗口內(nèi)或多邊形某邊與窗口某邊有交就可以了判斷包圍和分離的轉(zhuǎn)角檢查方法按順時針或逆時針方向繞多邊形邊界一周，累計(jì)相鄰的兩個頂點(diǎn)對窗口所張的角之和∑α，若∑α＝360º, 則多邊形包

32、含窗口。若∑α＝0， 則多邊形與窗口分離判斷包圍和分離區(qū)域編碼法把窗口外的平面區(qū)域分為八個區(qū)，編號為0-7, 多邊形的每個頂點(diǎn)一定落在某個區(qū)域內(nèi)，否則為前述的內(nèi)含或相交關(guān)系。頂點(diǎn)所在區(qū)的編號就作為頂點(diǎn)的編號,2024/3/31,32,第九章：真實(shí)感圖形學(xué),圖9.18  (a)內(nèi)含 (b)多邊形與窗口相交 (c)包圍 (d)窗口和多邊形分離,2024/3/31,33,第九章：真實(shí)感圖形學(xué),2024/

33、3/31,34,第九章：真實(shí)感圖形學(xué),2024/3/31,35,第九章：真實(shí)感圖形學(xué),對每條邊，令α＝(終點(diǎn)編碼)－(起點(diǎn)編碼)若α>4 則α＝ α－8; 若α4)=7-8=-1 a23=7-7=0 a34=0-7=-7(<-4)=-7+8=1 a45=1-0=1 a51=0-1=-1 可判斷多邊形與窗口分離,

34、2024/3/31,36,第九章：真實(shí)感圖形學(xué),2024/3/31,37,第九章：真實(shí)感圖形學(xué),a=±4的特殊情況a12=3-7=-4, a23=2, a31=2, 若a＝-4不做特殊處理，則∑a＝0, 把多邊形包含窗口誤判為與窗口分離若把線段a12分成兩段，則a1m=0-7=-7(4)=7-8=-1,∑a＝2+2-3-1=0, 正確判斷多邊形與窗口分離,2024/3/31,38,第九章：真實(shí)感圖形學(xué),2024/3/31,

35、39,第九章：真實(shí)感圖形學(xué),下列情況之一發(fā)生時，窗口足夠簡單，可以直接顯示所有多邊形均與窗口分離。該窗口置背景色只有一個多邊形與窗口相交，或該多邊形包含窗口，則先整個窗口置背景色，在對多邊形在窗口內(nèi)部分掃描線算法繪制有一個多邊形包圍了窗口，或窗口與多個多邊形相交，但有一個多邊形包圍窗口，而且在最前面最靠近觀察點(diǎn),2024/3/31,40,第九章：真實(shí)感圖形學(xué),光線投射算法考察由視點(diǎn)出發(fā)穿過觀察屏幕的一象素而射入場景的一條射線，則

36、可確定出場景中與該射線相交的物體。在計(jì)算出光線與物體表面的交點(diǎn)之后，離象素最近的交點(diǎn)的所在面片的顏色為該象素的顏色；如果沒有交點(diǎn)，說明沒有多邊形的投影覆蓋此象素，用背景色顯示它即可從光線投射算法與Z緩沖器算法相比，僅僅是內(nèi)外循環(huán)顛倒一下順序，所以它們的算法復(fù)雜度類似。區(qū)別在于光線投射算法不需要Z緩沖器。為了提高本算法的效率可以使用包圍盒技術(shù)，空間分割技術(shù)以及物體的層次表示方法等來加速,2024/3/31,41,第九章：真實(shí)感圖形學(xué),,

37、圖9.20  將通過屏幕各象素的投影線與場景中的物體表面求交,2024/3/31,42,第九章：真實(shí)感圖形學(xué),算法描述for(屏幕上的每一象素){ 形成通過該屏幕象素(u,v)的射線；  for(場景中的每個物體)    將射線與該物體求交；  if (存在交點(diǎn))    以最近的交點(diǎn)所屬的顏色顯示象素