計(jì)算機(jī)圖形學(xué)-消隱課件

跨入計(jì)算機(jī)殿堂的入門篇計(jì)算機(jī)圖形學(xué)施智平shizhiping@第八章消隱本章內(nèi)容圖形的數(shù)據(jù)結(jié)構(gòu)消隱算法分類隱線算法隱面算法圖形的數(shù)據(jù)結(jié)構(gòu)

W.K.Giloi在其著作InteractiveComputerGraphics中提出：

ComputerGraphics=DataStructure+GraphicsAlgorithms+Language圖形的數(shù)據(jù)結(jié)構(gòu)圖形的幾何信息和拓?fù)湫畔⒒緢D形的數(shù)據(jù)結(jié)構(gòu)立體表示模型圖形的幾何信息和拓?fù)湫畔缀涡畔ⅲ好枋鰩缀卧乜臻g位置的信息。拓?fù)湫畔ⅲ好枋鰩缀卧刂g相互連接關(guān)系的信息。描述一個(gè)物體不僅要有幾何信息的描述而且還要有拓?fù)湫畔⒌拿枋?。因?yàn)橹挥袔缀涡畔⒌拿枋?，在表示上存在不惟一性。五個(gè)頂點(diǎn)，幾何信息已經(jīng)確定，如果拓?fù)湫畔⒉煌瑒t可產(chǎn)生不同圖形基本圖形的數(shù)據(jù)結(jié)構(gòu)在三維坐標(biāo)系下，描述一個(gè)物體不僅需要頂點(diǎn)表，而且還需要邊表和面表，才能完全表達(dá)清楚立體的數(shù)據(jù)結(jié)構(gòu)

頂點(diǎn)x坐標(biāo)y坐標(biāo)z坐標(biāo)P1x1＝0y1＝0z1＝0P2x2＝0y2＝az2＝0P3x3＝0y3＝az3＝aP4x4＝0y4＝0z4＝aP5x5＝ay5＝0z5＝0P6x6＝ay6＝az6＝0P7x7＝ay7＝az7＝aP8x8＝ay8＝0z8＝a表1立方體頂點(diǎn)表

邊起點(diǎn)終點(diǎn)E1P1P2E2P2P3E3P3P4E4P4P1E5P5P6E6P6P7E7P7P8E8P8P5E9P1P5E10P2P6E11P3P7E12P4P8表2立方體邊表

面邊1邊2邊3邊4F1E1E4E3E2F2E5E6E7E8F3E9E8E12E4F4E10E2E11E6F5E1E10E5E9F6E3E12E7E11表3立方體面表

立體表示模型計(jì)算機(jī)三維模型的描述經(jīng)歷了線框模型表面模型實(shí)體模型的發(fā)展，所表達(dá)的幾何體信息越來(lái)越完整線框模型（WireframeModel）線框模型只是用幾何體的邊線來(lái)表示立體的外形，就如同用邊線搭出的框架一樣，線框模型中沒(méi)有表面、體積等信息。線框模型只使用頂點(diǎn)表和邊表兩個(gè)數(shù)據(jù)結(jié)構(gòu)描述面點(diǎn)之間的拓?fù)潢P(guān)系線框模型的優(yōu)點(diǎn)：可以產(chǎn)生任意方向視圖，視圖間能保持正確的投影關(guān)系線框模型的缺點(diǎn)：因?yàn)樗欣膺吶坷L制出來(lái)，理解方面容易產(chǎn)生二義性線框模型不能進(jìn)行兩個(gè)面的求交運(yùn)算16立體線框模型表示

線框模型表示的二義性表面模型（SurfaceModel）表面模型是利用立體的外表面來(lái)構(gòu)造模型就如同在線框模型上蒙上了一層外皮，使立體具有了一定的輪廓，可以進(jìn)行消隱處理與線框模型相比，表面模型增加了一個(gè)面表，用以記錄邊面之間的拓?fù)潢P(guān)系。表面模型的優(yōu)點(diǎn)：可以進(jìn)行面著色，隱藏面消隱，以及表面積計(jì)算，有限元網(wǎng)格劃分等。缺點(diǎn)：表面模型仍缺乏體積的概念，

是一個(gè)立體的空殼無(wú)法進(jìn)行立體之間的相交運(yùn)算實(shí)體模型（SolidModel)實(shí)體模型，如同在立體表面模型的內(nèi)部進(jìn)行了填充，使之具有了如體積和重量等特性，更能反映立體的真實(shí)性，這時(shí)的立體才具有“體”的概念。實(shí)體模型與表面模型的不同之處在于確定了表面的哪一側(cè)存在實(shí)體在表面模型的基礎(chǔ)上采用有向棱邊隱含地表示表面的外法矢方向，使用右手法則取向：四個(gè)手指沿閉合的棱邊方向，大拇指方向與表面外法矢量方向一致立方體實(shí)體模型表示

拓?fù)浜戏ǖ牧Ⅲw在相鄰兩個(gè)面的公共邊界上，棱邊的方向正好相反實(shí)體模型只需將面表改成環(huán)表形式，就可確切地分清體內(nèi)體外實(shí)體模型和線框模型、表面模型的根本區(qū)別在于其數(shù)據(jù)結(jié)構(gòu)不僅記錄了全部幾何信息，而且記錄了全部點(diǎn)、線、面、體的拓?fù)湫畔?shí)體模型常采用集合論中的并、交、差等運(yùn)算來(lái)構(gòu)造復(fù)雜形體消隱算法分類無(wú)論多么復(fù)雜的空間物體，沿視線方向上都只能看到一部分表面，其余的表面背向觀察者不可見(jiàn)計(jì)算機(jī)圖形學(xué)的一個(gè)重要任務(wù)就是對(duì)空間物體的表面進(jìn)行可見(jiàn)性檢測(cè)，繪制出可見(jiàn)邊線和表面經(jīng)過(guò)消隱后得到的圖形稱為消隱圖根據(jù)消隱方法的不同，消隱算法可分為兩類：隱線算法用于消除物體上不可見(jiàn)的邊界線主要針對(duì)線框模型，要求畫出物體的各可見(jiàn)棱邊隱面算法用于消除物體上不可見(jiàn)的表面主要針對(duì)表面模型，不僅要求畫出物體的各個(gè)可見(jiàn)棱邊，而且還要求填充各個(gè)表面隱線算法

隱面算法

計(jì)算機(jī)圖形學(xué)的創(chuàng)始人Southerland根據(jù)消隱空間的不同，將消隱算法分為三類：物空間消隱算法：在描述物體的坐標(biāo)系空間中進(jìn)行消隱。像空間消隱算法：在物體投影后的二維圖像空間中進(jìn)行消隱。物像空間消隱算法：在描述物體的坐標(biāo)系空間和圖像空間同時(shí)進(jìn)行消隱。隱線算法線框模型消隱一般在物空間中進(jìn)行物空間消隱算法是根據(jù)邊界線的可見(jiàn)性檢測(cè)條件，判斷哪些邊界線是可見(jiàn)的，哪些邊界線是不可見(jiàn)的，在屏幕上只繪制可見(jiàn)邊界線。凸多面體消隱算法凸多面體消隱是最簡(jiǎn)單和最基本的情形凸多面體的性質(zhì)：連接立體上不同表面的任意兩點(diǎn)的直線完全位于該凸多面體之內(nèi)由凸多邊形構(gòu)成，其表面要么完全可見(jiàn)，要么完全不可見(jiàn)凸多面體消隱算法的關(guān)鍵是給出測(cè)試其表面邊界線可見(jiàn)性的判別式對(duì)于凸多面體的任一個(gè)面，其外法矢量和視矢量的夾角θ可進(jìn)行可見(jiàn)性檢測(cè)θ<90°時(shí)，可見(jiàn)；θ>90°時(shí)，不可見(jiàn)XYDFECANSB法向向量N

視線向量V法向向量N

法向向量N<90°<90°可見(jiàn)可見(jiàn)

不可見(jiàn)>90°H(xh,yh,zh)G(xg,yg,zg)E(xe,ye,ze)F(xf,yf,zf)圖-12計(jì)算表面法矢量

表面的外法線矢量面EFGH的外法線矢量N=EFEG；已知各頂點(diǎn)的三維坐標(biāo)時(shí)，可求出各表面的外法線矢量取面EFGH上的一點(diǎn)E（xE，yE，zE），其外法矢量為N，視矢量為S，外法矢量和視矢量的夾角為θ借助于點(diǎn)F（xF，yF，zF）和點(diǎn)G（xG，yG，zG）來(lái)計(jì)算面的外法矢量邊矢量EF的三個(gè)分量為：EFx＝xF－xE；EFy＝y(tǒng)F－yE；EFz＝zF－zE邊矢量EG的三個(gè)分量為：EGx＝xG－xE；EGy＝y(tǒng)G－yE；EGz＝zG－zE；面EFGH的外法矢量為兩個(gè)邊矢量的矢量積，外法矢量的三個(gè)分量為：外法矢量表示為：給定視點(diǎn)位置球面坐標(biāo)表示為：

其中：R為視徑，則對(duì)于前面EFGH上的E（xE，yE，zE）點(diǎn)的視矢量分量的計(jì)算公式為：視矢量表示為：表面外法矢量和視矢量的數(shù)量積為：cosθ的正負(fù)取決于分子（表面外法矢量和視矢量的數(shù)量積）：34（3）

凸多面體表面可見(jiàn)性檢測(cè)條件為：當(dāng)0°≤θ＜90°時(shí)

立方體表面可見(jiàn)，繪該表面多邊形當(dāng)θ=90°時(shí)，

表面外法矢量與視矢量垂直，立方體表面多邊形退化為一條直線，繪出該直線；當(dāng)90°＜θ≤180°時(shí)，

立方體表面不可見(jiàn)，不繪制該多邊形。立方體消隱前的透視變換圖如圖9-13所示，消隱后的透視變換圖如圖9-14所示。圖9-13消隱前的立方體圖9-14消隱后的立方體

隱面算法物體的表面模型一般在像空間中進(jìn)行消隱像空間消隱算法屬于像素級(jí)算法，以屏幕像素為采樣單位，確定投影于每一像素的可見(jiàn)表面顏色區(qū)域，并將可見(jiàn)表面顏色作為該像素的顯示顏色隱面算法主要包括：Z-Buffer算法、畫家算法、區(qū)域采樣算法等Z-Buffer算法Catmull在1974年提出了Z-Buffer算法在像空間中根據(jù)深度值確定最終繪制的立體各個(gè)表面的像素點(diǎn)顏色Z-Buffer算法也稱深度緩沖算法，通常x，y代表屏幕坐標(biāo)，而z則用來(lái)表示立體上各個(gè)面的深度，故名Z-Buffer算法Z-Buffer算法建立三維坐標(biāo)系如圖所示觀察者的視線方向沿著z軸負(fù)向，

指向xoy坐標(biāo)面對(duì)于圖示立方體，z軸與立方體的前面交于（x，y，z1），與立方體的后面交于（x，y，z2）前面和后面在屏幕上的投影坐標(biāo)（x，y）相同，但z1＞z2，（x，y，z1）離觀察者近，（x，y，z2）離觀察者遠(yuǎn)對(duì)于投影像素點(diǎn)（x，y），前面像素點(diǎn)（x，y，z1）的顏色將覆蓋后面像素點(diǎn)（x，y，z2）的顏色，顯示結(jié)果為前面像素點(diǎn)（x，y，z1）的RGB顏色Z-Buffer算法這樣Z-Buffer算法需要建立兩個(gè)緩沖器：深度緩沖器，用于記錄立體上每一個(gè)像素的深度值，初始化為立體的最小深度值（z坐標(biāo)）幀緩沖器，用于記錄立體上每個(gè)像素點(diǎn)的顏色值，初始化為屏幕的背景色Z-Buffer算法Z-Buffer算法對(duì)立體的各個(gè)表面全部進(jìn)行采樣，將采樣點(diǎn)變換到屏幕坐標(biāo)系的像空間，并記錄其深度z坐標(biāo)值。根據(jù)采樣點(diǎn)在屏幕上的投影位置，將其深度與已存儲(chǔ)在幀緩存器中相應(yīng)像素點(diǎn)處的深度值進(jìn)行比較如果新采樣點(diǎn)的深度值大于原可見(jiàn)點(diǎn)的深度值，表明新采樣點(diǎn)更靠近觀察者，遮住了原采樣點(diǎn)，則用新采樣點(diǎn)處的顏色值更新幀緩存器中相應(yīng)采樣點(diǎn)處的顏色值，同時(shí)用新采樣點(diǎn)的深度值更新深度緩存器中的采樣點(diǎn)的深度值；否則，不作更改。41圖21深度緩沖器圖22幀緩沖器

圖20屏幕像素點(diǎn)Z-Buffer算法實(shí)現(xiàn)的難點(diǎn)是如何計(jì)算采樣點(diǎn)的深度值z(mì)（x，y）對(duì)圖19所示的靜止立方體，立方體前面和后面都平行于xoy坐標(biāo)面，上面、下面、左面和右面四個(gè)表面皆與屏幕坐標(biāo)系的xoy面垂直，立方體的投影為正方形，這時(shí)，前面和后面的深度值很容易計(jì)算，立方體的消隱結(jié)果為正方形。旋轉(zhuǎn)立方體的動(dòng)態(tài)Z-Buffer消隱算法當(dāng)立方體處于圖-23所示的位置時(shí)，六個(gè)面都不與屏幕平行，需要根據(jù)每個(gè)面的平面方程計(jì)算其上各個(gè)像素點(diǎn)深度值，這里需要用到第四章已經(jīng)講解的有效邊表算法來(lái)訪問(wèn)面上的每一個(gè)像素點(diǎn)進(jìn)行消隱。視線方向?qū)τ趫D-24所示的立方體表面，其平面一般方程為：式中系數(shù)A，B，C是該平面的一個(gè)法矢量的坐標(biāo)，即根據(jù)表面頂點(diǎn)的坐標(biāo)值可以計(jì)算兩個(gè)邊矢量矢量矢量根據(jù)兩個(gè)邊矢量的叉積，可求系數(shù)A，B，C將A、B、C和點(diǎn)（x1,y1,z1）代入方程（9）從方程（9）可以得到當(dāng)前像素點(diǎn)（x，y）處的深度值：這里，如果C＝0，說(shuō)明表面的法矢量與z軸垂直，在xoy面內(nèi)的投影為一條直線，在算法中可以不予以考慮。如果已知掃描線yi與多邊形相交的像素點(diǎn)(xi,yi)處的深度值z(mì)(xi，yi)，其相鄰點(diǎn)(xi+1，yi)處的深度值為z(xi+1,yi）計(jì)算出多邊形每個(gè)面上各個(gè)像素點(diǎn)的深度值后，就可以使用Z-Buffer算法進(jìn)行消隱，旋轉(zhuǎn)立方體消隱效果如圖-25所示。使用Z-Buffer算法可以繪制帶有交叉面的立體圖形，如圖-26所示，這種圖形由于同一個(gè)面的深度值不一樣，只能使用Z-Buffer算法實(shí)現(xiàn)。圖-27所示為移動(dòng)交叉面的一個(gè)組件的動(dòng)態(tài)過(guò)程。49圖9-26交叉面的Z-Buffer算法圖9-27交叉面的組件可移動(dòng)的Z-Buf