計算機圖形chapter

1、清華大學清華大學 計算機圖形學計算機圖形學第二章 光柵圖形學2.1直線段的掃描轉換算法2.2圓弧的掃描轉換算法2.3多邊形的掃描轉換與區(qū)域填充2.4字符2.5裁剪2.6反走樣2.7消隱清華大學清華大學 計算機圖形學計算機圖形學2.7 消隱 消隱的分類 消除隱藏線 消除隱藏面 畫家算法 Z緩沖區(qū)(Z-Buffer)算法 掃描線Z-buffer算法 區(qū)域子分割算法 光線投射算法清華大學清華大學 計算機圖形學計算機圖形學基本概念 投影變換失去了深度信息，往往導致圖形的二義性 要消除二義性，就必須在繪制時消除被遮擋的不可見的線或面，習慣上稱作消除隱藏線和隱藏面，簡稱為消隱消隱。 經(jīng)過消隱得到的投影圖稱

2、為物體的真實圖形。長方體線框投影圖的二義性 清華大學清華大學 計算機圖形學計算機圖形學 消隱的對象是三維物體。三維體的表示主要有邊界表示和CSG表示等。 消隱結果與觀察物體有關，也與視點有關。 線框圖 消隱圖 真實感圖形清華大學清華大學 計算機圖形學計算機圖形學 物體的表示 CSG表示 邊界表示(體、面、環(huán)、邊、點)清華大學清華大學 計算機圖形學計算機圖形學2.7.1消隱的分類 按消隱對象分類 線消隱 消隱對象是物體上的邊，消除的是物體上不可見的邊。 面消隱 消隱對象是物體上的面，消除的是物體上不可見的面。 清華大學清華大學 計算機圖形學計算機圖形學Southerland按消隱空間分類 物體空

3、間的消隱算法 （光線投射、Roberts） 將場景中每一個面與其他每個面比較，求出所有點、邊、面遮擋關系。 Roberts的故事：IEEE CS計算機先驅獎清華大學清華大學 計算機圖形學計算機圖形學 圖像空間的消隱算法 (Zbuffer、掃描線、Warnock) 對屏幕上每個象素進行判斷，決定哪個多邊形在該象素可見。 物體空間和圖像空間的消隱算法 (畫家算法) 在物體空間中預先計算面的可見性優(yōu)先級，再在圖像空間中生成消隱圖。清華大學清華大學 計算機圖形學計算機圖形學2.7.2消除隱藏線 對造型的要求 在線框顯示模型中,要求造型系統(tǒng)中有面的信息，最好有體的信息。 坐標變換 將視點變換到Z軸的正無

4、窮大處，視線方向變?yōu)閆軸的負方向。清華大學清華大學 計算機圖形學計算機圖形學 最基本的運算 判斷面對線的遮擋關系.反復地進行線線、線面之間的求交運算清華大學清華大學 計算機圖形學計算機圖形學平面對直線段的遮擋判斷算法 視點與線段同側 包圍盒不交 分段交替取值 線面相交 線面平行，線在面后 線面交與線段外清華大學清華大學 計算機圖形學計算機圖形學(1) 若線段的兩端點及視點在給定平面的同側，線段不被給定平面遮擋，轉7(2) 若線段的投影與平面投影的包圍盒無交，線段不被給定平面遮擋，轉7(3)求直線與相應無窮平面的交。若無交點，轉4。否則，交點在線段內(nèi)部或外部。若交點在線段內(nèi)部，交點將線段分成兩段

5、，與視點同側的一段不被遮擋，另一段在視點異側，轉4再判；若交點在線段外部，轉4。清華大學清華大學 計算機圖形學計算機圖形學(4)求所剩線段的投影與平面邊界投影的所有交點，并根據(jù)交點在原直線參數(shù)方程中的參數(shù)值求出Z值(即深度)。若無交點，轉5。(5) 以上所求得的各交點將線段的投影分成若干段，求出第一段中點。(6) 若第一段中點在平面的投影內(nèi)，則相應的段被遮擋，否則不被遮擋；其他段的遮擋關系可依次交替取值進行判斷。(7) 結束。 清華大學清華大學 計算機圖形學計算機圖形學前向面、后向面 為了提高算法的效率，需要設法減少求交的工作量。 若V N0，稱該多邊形為后向面后向面。 若V N0，稱該多邊形

6、為前向面前向面。 后向面總是看不見的，不會由于后向面的遮擋，而使別的棱成為不可見的。因此計算時，可以把這些后向面全部去掉，這并不影響消隱結果。 示意圖 清華大學清華大學 計算機圖形學計算機圖形學 前向面 后向面 多面體的隱藏線消除圖3中的JEAF、HCBG和DEABC所在的面均為后向面。其它為前向面。V VABCDEFGHIJN NVnVn清華大學清華大學 計算機圖形學計算機圖形學線消隱 基本數(shù)據(jù)結構 面表(存放參與消隱的面) + 線表(存放待顯示的線) 算法 假設E為面F的一條邊, 需判別F以外每一個面與E的遮擋關系.清華大學清華大學 計算機圖形學計算機圖形學2.7.3消除隱藏面 3.3.1

7、畫家算法（列表優(yōu)先算法）列表優(yōu)先算法） 先把屏幕置成背景色， 再把物體的各個面按其離視點的遠近進行排序，排序結果存在一張深度優(yōu)先級表中。 然后按照從遠到近的順序逐個繪制各個面。 關鍵是如何對場景中的物體按深度排序清華大學清華大學 計算機圖形學計算機圖形學對場景中的物體按深度排序 深度重疊測試. Zmin(P)Zmin(Q),若Zmax(P)0，則弧長代數(shù)和增加，若f0，則弧長代數(shù)和減少iiiiyxxyf11清華大學清華大學 計算機圖形學計算機圖形學2.7.3.32.7.3.3掃描線掃描線Z-bufferZ-buffer算法算法 算法思想: 點Buffer, 面Buffer 到線Buffer 利

8、用圖形的連貫性 （指深度計算）清華大學清華大學 計算機圖形學計算機圖形學 在處理當前掃描線時，開一個一維數(shù)組作為當前掃描線的Z-buffer。首先找出與當前掃描線相關的多邊形，以及每個多邊形中相關的邊對。 對每一個邊對之間的小區(qū)間上的各象素，計算深度，并與Z-buffer中的值比較，找出各象素處可見平面。 計算顏色，寫幀緩存。采用增量算法計算深度。清華大學清華大學 計算機圖形學計算機圖形學 數(shù)據(jù)結構 多邊形Y表：將所有多邊形存在多邊形Y表中。 根據(jù)多邊形頂點中最小的y坐標，插入多邊形Y表中的相應位置。多邊形Y表中只保存多邊形的序號和其頂點的最大y坐標。根據(jù)序號可以從定義多邊形的數(shù)據(jù)結構中取多邊

9、形信息 待消隱對象 多邊形y表0 1 2 3 4 5 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e5清華大學清華大學 計算機圖形學計算機圖形學活化多邊形表APT:與當前掃描線相交的多邊形。APT是一個動態(tài)的鏈表邊Y表ET:活化多邊形表中的每一個多邊形都有一個邊表ET 多邊形P1的邊表ETIP2 Ymax2IP1 Ymax1IP2 Ymax2APTAPTy=2y=41234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e2清華大學清華大學 計算機圖形學計算機圖形學活化邊對表AET 在一條掃描線上，同一多

10、邊形的相鄰兩條邊構成一個邊對邊對。活化邊表AET中存放當前多邊形中與當前掃描線相交的各邊對的信息。 xl xl ylmax xr xr yr max zl IP za zb (示意圖見下頁)清華大學清華大學 計算機圖形學計算機圖形學AET(y=6)0 1 2 3 45 6 71234567xye0e1e2e3e4AET(y=2)e0e4e3e2e0e1清華大學清華大學 計算機圖形學計算機圖形學掃描線Z-buffer算法()建多邊形y表；對每一個多邊形根據(jù)頂點最小的y值，將多邊形置入多邊形y表。活化多邊形表APT，活化邊表AET初始化為空。For(每條掃描線i，i從小到大)1. 幀緩存CB置為背

11、景色。2. 深度緩存ZB (一維數(shù)組) 置為無窮大。3. 將對應掃描線i的，多邊形y表中的多邊形加入到活化多邊形表APT中。4. 對新加入的多邊形，生成其相應的邊Y表。5. 對APT中每一個多邊形，若其邊Y表中對應掃描線I增加了新的邊， 清華大學清華大學 計算機圖形學計算機圖形學將新的邊配對，加到活化邊對表AET中。6. 對AET中的每一對邊：6.1 對xl x xr 的每一個象素，按增量公式z = z - za計算各點深度depth。6.2 與ZB中的量比較，depth ZB(I), 則令ZB(I) =depth，并計算顏色值， 寫幀緩存。 7. 刪除APT中，多邊形頂點最大y坐標為I的多邊

12、形，并刪除相應的邊。8. 對AET中的每一個邊對，作如下處理：8.1 刪除ylmax或yrmax 已等于i的邊。若一邊對中只刪除了其中一邊， 需對該多邊形的邊重新配對。 8.2 用增量公式計算新的xl 、 xr 和zl - END清華大學清華大學 計算機圖形學計算機圖形學2.7.3.4區(qū)間掃描線算法a1a2a3a4a6a5a7a8F1F2清華大學清華大學 計算機圖形學計算機圖形學 基本思想： 它是把當前掃描線與各多邊形在投影平面的投影的交點進行排序后，使掃描線分為若干子區(qū)間。只要在區(qū)間任一點處找出在該處z值最大的一個面，這個區(qū)間上的每一個象素就用這個面的顏色來顯示。清華大學清華大學 計算機圖形

13、學計算機圖形學 算法的優(yōu)點：將逐點(象素、Pixel)計算 改為逐段計算 效率大大提高！清華大學清華大學 計算機圖形學計算機圖形學 如何確定小區(qū)間的顏色可分為三種情況：(1)小區(qū)間上沒有任何多邊形，如a4,a5，這時該小區(qū) 間用背景色顯示。(2)小區(qū)間上只有一個多邊形，如a1,a2a5,a6這時可 以對應多邊形在該處的顏色顯示。(3)小區(qū)間上存在兩個或兩個以上的多邊,形如a6,a7， 必須通過深度測試判斷哪個多邊形可見。清華大學清華大學 計算機圖形學計算機圖形學 兩個平面在屏幕上的投影 無貫穿的情形 相互貫穿的情形 若允許物體表面相互貫穿時，還必須求出它們在掃描平面（ZX平面）的交點。用這些交

14、點把該小區(qū)間分成更小的子區(qū)間（稱為間隔），在這些間隔上決定哪個多邊形可見。如將a2,a3區(qū)間分成a2,bb,a3兩個子區(qū)間。a1a2a3a4a1a2a3a4a1a2xa4byxxzz清華大學清華大學 計算機圖形學計算機圖形學 確定某間隔內(nèi)哪一多邊形可見: 可在間隔內(nèi)任取一采樣點（如間隔中點），分析該點處哪個多邊形離視點最近，該多邊形即是在該間隔內(nèi)可見的多邊形。清華大學清華大學 計算機圖形學計算機圖形學 具體實現(xiàn)： 采用類似的數(shù)據(jù)結構 多邊形Y表：將所有多邊形存在多邊形Y表中。 根據(jù)多邊形頂點中最小的y 坐標，插入多邊形Y表中的相應位置。多邊形Y表中只保存多邊形的序號和其頂點的最大y坐標。根據(jù)序

15、號可以從定義多邊形的數(shù)據(jù)結構中取多邊形信息。0 1 2 3 45 6 71234567xy1234560IP2 Ymax2IP1 Ymax1P1P2e0e1e2e3e4e5清華大學清華大學 計算機圖形學計算機圖形學 活化多邊形表APT:與當前掃描線相交的多邊形。APT是一個動態(tài)的鏈表。 邊Y表ET:活化多邊形表中的每一個多邊形都有一個邊表ET。 活化邊對表AET1234560Ymax, x,x,zYmax, x,x,zYmax, x,x,ze0e1e2清華大學清華大學 計算機圖形學計算機圖形學 區(qū)別：活化邊表中的結點是邊，而非邊對。a1a2a3a4a6a5a7a8F1F2清華大學清華大學 計算

16、機圖形學計算機圖形學 關鍵：如何知道每一個區(qū)間中，有幾個相關的多邊形？是哪幾個？清華大學清華大學 計算機圖形學計算機圖形學 解決方案：活化多邊形表中增加一個標志，flag=0, 每遇到它的邊，flag取反。a1a2a3a4a6a5a7a8F1F2清華大學清華大學 計算機圖形學計算機圖形學2.7.3.5區(qū)域子分割算法 (Warnack算法) 基本思想: 把物體投影到全屏幕窗口上，然后遞歸分割窗口，直到窗口內(nèi)目標足夠簡單，可以顯示為止。區(qū)域子分的過程清華大學清華大學 計算機圖形學計算機圖形學 算法步驟該算法把初始窗口取作屏幕坐標系的矩形，將場景中的多邊形投影到窗口內(nèi)。 如果窗口內(nèi)沒有物體則按背景色

17、顯示； 若窗口內(nèi)只有一個面，則把該面顯示出來。 否則，窗口內(nèi)含有兩個以上的面，則把窗口等分成四個子窗口。對每個小窗口再做上述同樣的處理。這樣反復地進行下去。清華大學清華大學 計算機圖形學計算機圖形學如果到某個時刻，窗口僅有象素那么大，而窗口內(nèi)仍有兩個以上的面，這時不必再分割，只要取窗口內(nèi)最近的可見面的顏色或所有可見面的平均顏色作為該象素的值。清華大學清華大學 計算機圖形學計算機圖形學 窗口與多邊形的覆蓋關系有四種：內(nèi)含、相交包圍和分離。如圖所示。內(nèi)含 多邊形與窗口相交 包圍 窗口和多邊形分離清華大學清華大學 計算機圖形學計算機圖形學 下列情況之一發(fā)生時，窗口足夠簡單，可以直接顯示： 所有多邊形均與窗口分離。該窗口置背景色清華大學清華大學 計算機圖形學計