可見面判別算法

1、Computer Graphics電子科技大學計算機學院電子科技大學計算機學院 Designed by Lgs .UESTCCHP9 visible surface detectionnvisible surface detectionnAlgorithm typen表面定向理論n后向面消除法（back-faces method）n深度緩沖法（depth-buffer method）nA緩沖器算法（A-buffer method）n掃描線算法（scan-line method）n深度排序算法（depth-sorting method） Designed by Lgs .UESTCn消隱的考慮：

2、n用計算機生成三維形體的真實圖形，是計算機圖形學研究的重要內容之一。在使用顯示設備描繪三維圖形時，必須把三維信息作某種投影變換，在二顯示表面上繪制出來。n由于投影變換失去了深度信息，往往導致圖形的二義性：n要消除二義性，必須在繪制時隱藏實際不可見的線和面，即消隱。經過消隱的投影圖稱為物體的真實圖形。CHP9 visible surface detection Designed by Lgs .UESTCn不同消隱算法考慮的因素n速度問題實時模擬，如飛行模擬n真實度問題計算機動畫，有連續(xù)色調，能產生陰影、透明、表面紋理及反射、折射等視覺效果n在進行消隱算法的設計時，應在計算速度和圖形細節(jié)之間進行

3、權衡，同一種算法無法兼顧CHP9 visible surface detection Designed by Lgs .UESTCn消隱算法的實現(xiàn)空間（兩種方法）n形體空間法(object-space method)n直接對形體定義進行處理（把形體和形體的某些部分彼此比較，以確定哪些表面和線作為一個整體是不可見的）n圖像空間法(image-space method)n對形體投影圖像進行處理（對投影平面上的每一個象素位置逐點檢測其可見性） CHP9 visible surface detection Designed by Lgs .UESTCdifference Designed by Lgs

4、 .UESTCnIdea（物空間算法物空間算法）n表面法矢量表面法矢量指向表面外部法線方向指向表面外部法線方向n視線矢量視線矢量物體表面任一點指向物體表面任一點指向視點的方向視點的方向n視角視角法矢量和視線矢量的夾角。法矢量和視線矢量的夾角。nwuv p1p2p2p3p4表面定向理論與定向法表面定向理論與定向法 Designed by Lgs .UESTCn判斷原則：判斷原則：n計算方法計算方法n計算計算sign（cos ）invisiblevisible)180,90()90, 0(000表面定向理論與定向法表面定向理論與定向法nwuv p1p2p2p3p4 Designed by Lgs

5、.UESTC13121),(cos|ppvppupwzwywxpwvunnwnw計算公式：計算公式：表面定向理論與定向法表面定向理論與定向法 Designed by Lgs .UESTCfacesbackinvisiblethendczbyaxifzyxpoviewdczbyax_0_) , , ( :int0后向面后向面(back faces)消除法（消除法（物空間算法物空間算法） Designed by Lgs .UESTCnEg: 左手系，左手系，view directionZ_axisXZYZvN(A,B,C)容易得知：容易得知：If C0back faces invisibleEls

6、e visible所謂的所謂的back face取決于取決于觀察的方向和觀察系統(tǒng)觀察的方向和觀察系統(tǒng)的坐標系的坐標系(右手和左手右手和左手)后向面后向面(back faces)消除法消除法 Designed by Lgs .UESTCnIDEA: Depth-buffer method 像空間算法像空間算法深度緩沖器算法（深度緩沖器算法（Z-Buffer）XvZvYvview direction(x,y)s1s2s3n如圖，如圖，s1平面平面距離投影平面距離投影平面最近，所以投最近，所以投影點（影點（x，y）將保存將保存s1平面平面上相應點的屬上相應點的屬性信息。性信息。 Designed b

7、y Lgs .UESTCnIDEA: Depth-buffer methodn刷新緩沖器用來存儲圖像空間中每一個象素的屬性，刷新緩沖器用來存儲圖像空間中每一個象素的屬性，Z緩沖緩沖器是用來存儲圖像空間中每一個可見象素相應的深度器是用來存儲圖像空間中每一個可見象素相應的深度(或或Z坐標坐標)，是一個獨立的深度緩沖器。，是一個獨立的深度緩沖器。n計算將要寫入刷新緩沖器象素的深度計算將要寫入刷新緩沖器象素的深度(或或Z值值)，并與已存儲，并與已存儲在在Z緩沖器中該象素的原來深度進行比較緩沖器中該象素的原來深度進行比較 ：若新象素點位于：若新象素點位于刷新緩沖器中原象素點的前面，則將新象素點的屬性寫入

8、刷新緩沖器中原象素點的前面，則將新象素點的屬性寫入刷新緩沖器，并將相應的深度刷新緩沖器，并將相應的深度(Z值值)也寫入也寫入Z緩沖器；否則，緩沖器；否則，刷新緩沖器和刷新緩沖器和Z緩沖器中的內容不變。緩沖器中的內容不變。n本算法的本算法的。深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTClAlgorithm description：設置刷新緩沖器為背景顏色設置刷新緩沖器為背景顏色(或光強度或光強度)設置設置Z緩沖器為最大緩沖器為最大Z值（深度最深，規(guī)范化后為值（深度最深，規(guī)范化后為1）while 對每一個多邊形對每一個多邊形 dobegin wh

9、ile 對多邊形中的每一個元素對多邊形中的每一個元素 do begin 計算該象素的深度計算該象素的深度z(x,y)深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTC/*比較比較z(x,y)與存儲在與存儲在Z緩沖其中該位置處的深度緩沖其中該位置處的深度Z(x,y)*/ if z(x,y)Z(x,y) then 將此多邊形的顏色將此多邊形的顏色(或光強度或光強度) 寫入幀緩沖器且寫入幀緩沖器且Z(x,y)z(x,y) endendend of algorithm*最終，最終，Z-buffer 中保存的是可見面的深度值，而中保存的是可見面的深度值，而R

10、efresh-Buffer中保存的是這些表面的對應屬性值。中保存的是這些表面的對應屬性值。深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTCnProblem:計算采樣點計算采樣點(x,y)的深度的深度z(x,y) n設平面方程為：設平面方程為：ax+by+cz+d=0 則則 z=-(ax+by+d)/c c0由于同一條掃描線上的由于同一條掃描線上的y分量為常量，所以沿掃描線上的象素分量為常量，所以沿掃描線上的象素 x1=x+x，y1=y處的深度為：處的深度為：z1 =-(ax1+by+d)/c =-(ax+by+d)/c-(a/c)x =z-(a/

11、c)x若若x=1，則，則 z=z-a/c深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTCn優(yōu)點：優(yōu)點：簡單，易于處理隱藏面以及顯示曲面之間的交簡單，易于處理隱藏面以及顯示曲面之間的交貫線。被顯示的畫面可以任意復雜，因為圖像空間的大貫線。被顯示的畫面可以任意復雜，因為圖像空間的大小是固定的，最壞情況下，計算量隨畫面復雜程度線性小是固定的，最壞情況下，計算量隨畫面復雜程度線性增長。由于被顯示的元素可按任意順序寫入幀緩沖器和增長。由于被顯示的元素可按任意順序寫入幀緩沖器和Z緩沖器，所以不需要進行深度排序，節(jié)省了排序時間。緩沖器，所以不需要進行深度排序，

12、節(jié)省了排序時間。n缺點：缺點：Z緩沖器需要占用大量存儲空間。若被顯示的畫緩沖器需要占用大量存儲空間。若被顯示的畫面經變換和剪取后，面經變換和剪取后，Z值在一定范圍內變化，則可采用固值在一定范圍內變化，則可采用固定精度的定精度的Z緩沖器。緩沖器。深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTCnIdea（像空間算法像空間算法）nz-buffer每個象素點只能對應一個可見面，只能處理每個象素點只能對應一個可見面，只能處理不透明表面。不能處理多個面的累計強度值。不透明表面。不能處理多個面的累計強度值。n對對z-buffer進行擴展，使每個單元位置對應一

13、個表面進行擴展，使每個單元位置對應一個表面鏈表。鏈表。nA的含義：的含義：nantialiased：反走樣；（主要應用于物體邊界）：反走樣；（主要應用于物體邊界）naccumulation-buffer：累計緩沖器；：累計緩沖器；narea-averaged：區(qū)域平均；：區(qū)域平均；A緩沖器法緩沖器法 Designed by Lgs .UESTCn單元的深度域和強度域：單元的深度域和強度域：n深度域：存儲一個正或負的實數(shù)。為正，表示該象素具有唯一的深度域：存儲一個正或負的實數(shù)。為正，表示該象素具有唯一的表面深度；為負，表示多個面共同對該象素點產生影響。表面深度；為負，表示多個面共同對該象素點產生

14、影響。n強度域：存儲表面的強度信息（深度域為正）或指針（深度域為強度域：存儲表面的強度信息（深度域為正）或指針（深度域為負）。負）。A緩沖器法緩沖器法Id0d0surf1surf2surf3 Designed by Lgs .UESTCnSurf(i)中含有的數(shù)據項：中含有的數(shù)據項：nRGB強度分量強度分量n表面的標識名表面的標識名n透明性參數(shù)透明性參數(shù)n其他表面繪制參數(shù)其他表面繪制參數(shù)n深度深度n覆蓋度覆蓋度n指向下一表面的指針指向下一表面的指針A緩沖器法緩沖器法 Designed by Lgs .UESTC掃描線算法（掃描線算法（像空間算法像空間算法）nidea：判別與各條掃：判別與各條掃

15、描線相交的所有表面描線相交的所有表面的可見性，記算各重的可見性，記算各重疊表面的深度以找出疊表面的深度以找出距離觀察平面最近的距離觀察平面最近的表面，將其相應屬性表面，將其相應屬性寫入刷新緩沖器。寫入刷新緩沖器。n避免對被遮擋區(qū)域的避免對被遮擋區(qū)域的采樣是進一步提高掃采樣是進一步提高掃描線算法計算效率的描線算法計算效率的關鍵。關鍵。掃描線算法原理圖掃描線算法原理圖0 0 x xy y掃描線掃描線2 2A A2 2A A3 3B B1 1B B2 2B B3 3B B4 4掃描線掃描線1 1掃描線掃描線3 3C C1 1C C2 2C C3 3C C4 4A AB BC C Designed b

16、y Lgs .UESTC掃描線算法掃描線算法nAlgorithm:n數(shù)據結構：三張表數(shù)據結構：三張表n邊表邊表:保存線段端點坐標、線段斜率的倒數(shù)、和指向多邊形表中對應保存線段端點坐標、線段斜率的倒數(shù)、和指向多邊形表中對應多邊形的指針；多邊形的指針；n多邊形表：包含各多邊形面的平面方程系數(shù)、表面屬性信息以及指多邊形表：包含各多邊形面的平面方程系數(shù)、表面屬性信息以及指向邊表的指針；向邊表的指針；n有效邊表：也稱活化邊表，包含與當前掃描線相交的邊，并將這些有效邊表：也稱活化邊表，包含與當前掃描線相交的邊，并將這些邊按邊按x升序排列；升序排列；n面標志面標志Flag：on（開始，左邊界）或者（開始，左

17、邊界）或者off（結束，右邊界）；（結束，右邊界）；n算法關鍵：分割子區(qū)間，確定子區(qū)間上的唯一可見面。算法關鍵：分割子區(qū)間，確定子區(qū)間上的唯一可見面。n特殊情形：貫穿情形、循環(huán)遮擋情形。特殊情形：貫穿情形、循環(huán)遮擋情形。 Designed by Lgs .UESTC掃描線算法掃描線算法A1掃描線算法原理圖掃描線算法原理圖0 0 x xy y掃描線掃描線2 2A A2 2A A3 3B B1 1B B2 2B B3 3B B4 4掃描線掃描線1 1掃描線掃描線3 3C C1 1C C2 2C C3 3C C4 4A AB BC C Designed by Lgs .UESTC掃描線算法掃描線算法

18、n貫穿情況的處理貫穿情況的處理: :n為了使算法能處理為了使算法能處理互相貫互相貫穿的多邊形穿的多邊形，掃描線上的，掃描線上的分割點不僅應包含各多邊分割點不僅應包含各多邊形的邊與掃描線的交點，形的邊與掃描線的交點，而且應包含這些貫穿邊界而且應包含這些貫穿邊界與掃描線的交點與掃描線的交點( (圖中紅色圖中紅色為貫穿邊界為貫穿邊界) )(a)(a)貫穿貫穿 Designed by Lgs .UESTC掃描線算法掃描線算法n循環(huán)遮擋情況的處理循環(huán)遮擋情況的處理:n將多邊形進行劃分以消除將多邊形進行劃分以消除循環(huán)遮擋循環(huán)遮擋 n圖中紅色為劃分邊界圖中紅色為劃分邊界(b)(b)循環(huán)遮擋循環(huán)遮擋 Desi

19、gned by Lgs .UESTC深度排序算法（畫家算法）深度排序算法（畫家算法）nDepth-sorting method, 同時運用物空間和象空間操作。同時運用物空間和象空間操作。nIdea：若場景中任何多邊形在深度上均不貫穿或循環(huán)遮擋，則各多：若場景中任何多邊形在深度上均不貫穿或循環(huán)遮擋，則各多邊形的優(yōu)先級順序可完全確定。邊形的優(yōu)先級順序可完全確定。 n深度排序算法深度排序算法：n將多邊形按深度進行排序：距視點近的優(yōu)先級高，距視點遠的優(yōu)先級低。將多邊形按深度進行排序：距視點近的優(yōu)先級高，距視點遠的優(yōu)先級低。n由優(yōu)先級低的多邊形開始逐個對多邊形進行掃描轉換。由優(yōu)先級低的多邊形開始逐個對多邊形進行掃描轉換。n其中的關鍵是將多邊形按深度進行排序！其中的關鍵是將多邊形按深度進行排序！ Designed by Lgs .UESTC深度排序算法（畫家算法）深度排序算法（畫家算法）n深度的重疊問題深度的重疊問題n無重疊情況：按深度無重疊情況：按深度優(yōu)先級順序處理各個優(yōu)先級順序處理各個表面表面S1S2Z1minZ1maxZ2minZ2maxs1s1和和s2s2無深度重疊無深度重疊 Designed by Lgs .UESTC深度排序算法（畫家算法）深度排序算法（畫家算法） Design