可見(jiàn)面判別算法

1、Computer Graphics電子科技大學(xué)計(jì)算機(jī)學(xué)院電子科技大學(xué)計(jì)算機(jī)學(xué)院 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用計(jì)算機(jī)生成三維形體的真實(shí)圖形，是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容之一。在使用顯示設(shè)備描繪三維圖形時(shí)，必須把三維信息作某種投影變換，在二顯示表面上繪制出來(lái)。n由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性：n要消除二義性，必須在繪制時(shí)隱藏實(shí)際不可見(jiàn)的線和面，即消隱。經(jīng)過(guò)消隱的投影圖稱為物體的真實(shí)圖形。CHP9 visible surface detection Designed by Lgs .UESTCn不同消隱算法考慮的因素n速度問(wèn)題實(shí)時(shí)模擬，如飛行模擬n真實(shí)度問(wèn)題計(jì)算機(jī)動(dòng)畫(huà)，有連續(xù)色調(diào)，能產(chǎn)生陰影、透明、表面紋理及反射、折射等視覺(jué)效果n在進(jìn)行消隱算法的設(shè)計(jì)時(shí)，應(yīng)在計(jì)算速度和圖形細(xì)節(jié)之間進(jìn)行

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

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

5、.UESTC13121),(cos|ppvppupwzwywxpwvunnwnw計(jì)算公式：計(jì)算公式：表面定向理論與定向法表面定向理論與定向法 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)的坐標(biāo)系的坐標(biāo)系(右手和左手右手和左手)后向面后向面(back faces)消除法消除法 Designed by Lgs .UESTCnIDEA: Depth-buffer method 像空間算法像空間算法深度緩沖器算法（深度緩沖器算法（Z-Buffer）XvZvYvview direction(x,y)s1s2s3n如圖，如圖，s1平面平面距離投影平面距離投影平面最近，所以投最近，所以投影點(diǎn)（影點(diǎn)（x，y）將保存將保存s1平面平面上相應(yīng)點(diǎn)的屬上相應(yīng)點(diǎn)的屬性信息。性信息。 Designed b

7、y Lgs .UESTCnIDEA: Depth-buffer methodn刷新緩沖器用來(lái)存儲(chǔ)圖像空間中每一個(gè)象素的屬性，刷新緩沖器用來(lái)存儲(chǔ)圖像空間中每一個(gè)象素的屬性，Z緩沖緩沖器是用來(lái)存儲(chǔ)圖像空間中每一個(gè)可見(jiàn)象素相應(yīng)的深度器是用來(lái)存儲(chǔ)圖像空間中每一個(gè)可見(jiàn)象素相應(yīng)的深度(或或Z坐標(biāo)坐標(biāo))，是一個(gè)獨(dú)立的深度緩沖器。，是一個(gè)獨(dú)立的深度緩沖器。n計(jì)算將要寫(xiě)入刷新緩沖器象素的深度計(jì)算將要寫(xiě)入刷新緩沖器象素的深度(或或Z值值)，并與已存儲(chǔ)，并與已存儲(chǔ)在在Z緩沖器中該象素的原來(lái)深度進(jìn)行比較緩沖器中該象素的原來(lái)深度進(jìn)行比較 ：若新象素點(diǎn)位于：若新象素點(diǎn)位于刷新緩沖器中原象素點(diǎn)的前面，則將新象素點(diǎn)的屬性寫(xiě)入

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

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

10、efresh-Buffer中保存的是這些表面的對(duì)應(yīng)屬性值。中保存的是這些表面的對(duì)應(yīng)屬性值。深度緩沖器算法（深度緩沖器算法（Z-Buffer） Designed by Lgs .UESTCnProblem:計(jì)算采樣點(diǎn)計(jì)算采樣點(diǎn)(x,y)的深度的深度z(x,y) n設(shè)平面方程為：設(shè)平面方程為：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)點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單，易于處理隱藏面以及顯示曲面之間的交簡(jiǎn)單，易于處理隱藏面以及顯示曲面之間的交貫線。被顯示的畫(huà)面可以任意復(fù)雜，因?yàn)閳D像空間的大貫線。被顯示的畫(huà)面可以任意復(fù)雜，因?yàn)閳D像空間的大小是固定的，最壞情況下，計(jì)算量隨畫(huà)面復(fù)雜程度線性小是固定的，最壞情況下，計(jì)算量隨畫(huà)面復(fù)雜程度線性增長(zhǎng)。由于被顯示的元素可按任意順序?qū)懭霂彌_器和增長(zhǎng)。由于被顯示的元素可按任意順序?qū)懭霂彌_器和Z緩沖器，所以不需要進(jìn)行深度排序，節(jié)省了排序時(shí)間。緩沖器，所以不需要進(jìn)行深度排序，

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

13、個(gè)表面進(jìn)行擴(kuò)展，使每個(gè)單元位置對(duì)應(yīng)一個(gè)表面鏈表。鏈表。nA的含義：的含義：nantialiased：反走樣；（主要應(yīng)用于物體邊界）：反走樣；（主要應(yīng)用于物體邊界）naccumulation-buffer：累計(jì)緩沖器；：累計(jì)緩沖器；narea-averaged：區(qū)域平均；：區(qū)域平均；A緩沖器法緩沖器法 Designed by Lgs .UESTCn單元的深度域和強(qiáng)度域：?jiǎn)卧纳疃扔蚝蛷?qiáng)度域：n深度域：存儲(chǔ)一個(gè)正或負(fù)的實(shí)數(shù)。為正，表示該象素具有唯一的深度域：存儲(chǔ)一個(gè)正或負(fù)的實(shí)數(shù)。為正，表示該象素具有唯一的表面深度；為負(fù)，表示多個(gè)面共同對(duì)該象素點(diǎn)產(chǎn)生影響。表面深度；為負(fù)，表示多個(gè)面共同對(duì)該象素點(diǎn)產(chǎn)生

14、影響。n強(qiáng)度域：存儲(chǔ)表面的強(qiáng)度信息（深度域?yàn)檎┗蛑羔槪ㄉ疃扔驗(yàn)閺?qiáng)度域：存儲(chǔ)表面的強(qiáng)度信息（深度域?yàn)檎┗蛑羔槪ㄉ疃扔驗(yàn)樨?fù)）。負(fù)）。A緩沖器法緩沖器法Id0d0surf1surf2surf3 Designed by Lgs .UESTCnSurf(i)中含有的數(shù)據(jù)項(xiàng)：中含有的數(shù)據(jù)項(xiàng)：nRGB強(qiáng)度分量強(qiáng)度分量n表面的標(biāo)識(shí)名表面的標(biāo)識(shí)名n透明性參數(shù)透明性參數(shù)n其他表面繪制參數(shù)其他表面繪制參數(shù)n深度深度n覆蓋度覆蓋度n指向下一表面的指針指向下一表面的指針A緩沖器法緩沖器法 Designed by Lgs .UESTC掃描線算法（掃描線算法（像空間算法像空間算法）nidea：判別與各條掃：判別與各條掃

15、描線相交的所有表面描線相交的所有表面的可見(jiàn)性，記算各重的可見(jiàn)性，記算各重疊表面的深度以找出疊表面的深度以找出距離觀察平面最近的距離觀察平面最近的表面，將其相應(yīng)屬性表面，將其相應(yīng)屬性寫(xiě)入刷新緩沖器。寫(xiě)入刷新緩沖器。n避免對(duì)被遮擋區(qū)域的避免對(duì)被遮擋區(qū)域的采樣是進(jìn)一步提高掃采樣是進(jìn)一步提高掃描線算法計(jì)算效率的描線算法計(jì)算效率的關(guān)鍵。關(guān)鍵。掃描線算法原理圖掃描線算法原理圖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ù)據(jù)結(jié)構(gòu)：三張表數(shù)據(jù)結(jié)構(gòu)：三張表n邊表邊表:保存線段端點(diǎn)坐標(biāo)、線段斜率的倒數(shù)、和指向多邊形表中對(duì)應(yīng)保存線段端點(diǎn)坐標(biāo)、線段斜率的倒數(shù)、和指向多邊形表中對(duì)應(yīng)多邊形的指針；多邊形的指針；n多邊形表：包含各多邊形面的平面方程系數(shù)、表面屬性信息以及指多邊形表：包含各多邊形面的平面方程系數(shù)、表面屬性信息以及指向邊表的指針；向邊表的指針；n有效邊表：也稱活化邊表，包含與當(dāng)前掃描線相交的邊，并將這些有效邊表：也稱活化邊表，包含與當(dāng)前掃描線相交的邊，并將這些邊按邊按x升序排列；升序排列；n面標(biāo)志面標(biāo)志Flag：on（開(kāi)始，左邊界）或者（開(kāi)始，左

17、邊界）或者off（結(jié)束，右邊界）；（結(jié)束，右邊界）；n算法關(guān)鍵：分割子區(qū)間，確定子區(qū)間上的唯一可見(jiàn)面。算法關(guān)鍵：分割子區(qū)間，確定子區(qū)間上的唯一可見(jiàn)面。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為了使算法能處理為了使算法能處理互相貫互相貫穿的多邊形穿的多邊形，掃描線上的，掃描線上的分割點(diǎn)不僅應(yīng)包含各多邊分割點(diǎn)不僅應(yīng)包含各多邊形的邊與掃描線的交點(diǎn)，形的邊與掃描線的交點(diǎn)，而且應(yīng)包含這些貫穿邊界而且應(yīng)包含這些貫穿邊界與掃描線的交點(diǎn)與掃描線的交點(diǎn)( (圖中紅色圖中紅色為貫穿邊界為貫穿邊界) )(a)(a)貫穿貫穿 Designed by Lgs .UESTC掃描線算法掃描線算法n循環(huán)遮擋情況的處理循環(huán)遮擋情況的處理:n將多邊形進(jìn)行劃分以消除將多邊形進(jìn)行劃分以消除循環(huán)遮擋循環(huán)遮擋 n圖中紅色為劃分邊界圖中紅色為劃分邊界(b)(b)循環(huán)遮擋循環(huán)遮擋 Desi

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