計(jì)算機(jī)圖形學(xué)課件21-40講

第21講三維曲面的表示

—B樣條曲面

第21講三維曲面的表示

—B樣條曲面第21講三維曲面的表示

—B樣條曲面第21講三維曲面的表示

—B樣條曲面第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念1．有效物體(實(shí)體)實(shí)體(或稱有效物體)是具有以下性質(zhì)的物體:（1）具有一定的形狀。（2）具有確定的封閉邊界。（3）是一個(gè)內(nèi)部連通的三維點(diǎn)集。（4）占據(jù)有限的空間。（5）經(jīng)過切割、粘合和連續(xù)形變后物體仍具有前面性質(zhì)。第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念2．有效物體(實(shí)體)（續(xù)）實(shí)體的表面具有以下性質(zhì)：（1）連通性：實(shí)體表面上的任意兩點(diǎn)間存在有實(shí)體表面的一條路徑將它們連接起來。（2）有界性：存在一個(gè)充分大的球面將實(shí)體包圍起來。（3）非自交性：實(shí)體的表面不能自相交。（4）閉合性：實(shí)體表面應(yīng)該是閉合的。第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念3．正則（點(diǎn)）集和正則集合運(yùn)算

集合的內(nèi)點(diǎn)是集合中的點(diǎn)，在該點(diǎn)的一個(gè)充分小鄰域內(nèi)的所有點(diǎn)都是集合中的元素。空間一點(diǎn)的任意鄰域內(nèi)既有集合中的點(diǎn)，又有集合外的點(diǎn)，則稱該點(diǎn)為集合的邊界點(diǎn)。內(nèi)點(diǎn)組成的集合稱為集合的內(nèi)部，邊界點(diǎn)組成的集合稱為集合的邊界。任意一個(gè)實(shí)體可以表示為內(nèi)部和邊界的并集。這個(gè)結(jié)論對(duì)于一般集合而言并不成立。

第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念4．正則（點(diǎn)）集和正則集合運(yùn)算（續(xù)）A表示包括球面的閉球，A的內(nèi)部是不包括球面的開球，A的邊界是球面，顯然A可以表示為內(nèi)部和邊界的并集。如果用B表示A中有理點(diǎn)的集合，則B的內(nèi)部為空集，B的邊界為A，顯然B不能表示為B的內(nèi)部和B的邊界的并集。也就是說，B不是一個(gè)實(shí)體。

第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念5．正則（點(diǎn)）集和正則集合運(yùn)算（續(xù)）集合與它的邊界的并集稱集合的閉包。取集合的內(nèi)部，再取內(nèi)部的閉包，所得的集合稱為原集合的正則（點(diǎn)）集。

正則集合運(yùn)算包括正則并、正則交和正則差。它們是由相應(yīng)集合運(yùn)算再取正則點(diǎn)集所構(gòu)成的運(yùn)算。

第22講三維實(shí)體的表示

—實(shí)體及相關(guān)概念6．二維流形

如果曲面上任意一點(diǎn)都存在一個(gè)充分小的鄰域，該鄰域與平面上的（開）圓盤同構(gòu)，即鄰域與圓盤之間存在連續(xù)的1-1映射，則稱該曲面為二維流形。對(duì)于一個(gè)占據(jù)有限空間的正則（點(diǎn)）集，如果其表面是二維流形，則該正則集為一個(gè)實(shí)體（有效物體）。第23講三維實(shí)體的表示

—邊界表示法1．邊界表示的概念通過實(shí)體的邊界來表示一個(gè)實(shí)體的方法稱為實(shí)體的邊界表示法。實(shí)體的邊界由平面多邊形或空間曲面片組成。通常情況下，曲面片最終離散成（平面）多邊形來處理。本講討論多面體的邊界表示。第23講三維實(shí)體的表示

—邊界表示法2．多面體

（1）平面多面體表面由平面多邊形構(gòu)成的空間三維體稱為平面多面體。要求多面體表面平面多邊形的邊最多屬于兩個(gè)多邊形，即要求多面體的表面具有二維流形的性質(zhì)。（2）簡(jiǎn)單多面體與球（拓?fù)洌┩瑯?gòu)的(平面)多面體稱為簡(jiǎn)單多面體。顯然，在一個(gè)簡(jiǎn)單多面體內(nèi)部不能有洞，它能經(jīng)過連續(xù)形變成為一個(gè)球。簡(jiǎn)單多面體滿足歐拉公式：

頂點(diǎn)-邊數(shù)+面數(shù)=2第23講三維實(shí)體的表示

—邊界表示法3．邊界表示數(shù)據(jù)結(jié)構(gòu)

對(duì)實(shí)體的表示包括對(duì)實(shí)體幾何性質(zhì)的表示和拓?fù)潢P(guān)系的表示。幾何性質(zhì)包括位置、長(zhǎng)度和大小等。拓?fù)潢P(guān)系則表示實(shí)體之間的相鄰、相離、相交和包含等關(guān)系。描述多面體的頂點(diǎn)、邊和面之間拓?fù)洌ㄠ徑樱╆P(guān)系的數(shù)據(jù)結(jié)構(gòu)有很多種，比較典型的有翼邊數(shù)據(jù)結(jié)構(gòu)和對(duì)稱數(shù)據(jù)結(jié)構(gòu)及它們的變種。

第23講三維實(shí)體的表示

—邊界表示法4．邊界表示數(shù)據(jù)結(jié)構(gòu)（續(xù)）（1）翼邊數(shù)據(jù)結(jié)構(gòu)這種數(shù)據(jù)結(jié)構(gòu)以邊為核心，從邊指向其它元素，從多面體的外面進(jìn)行觀察時(shí)，邊所指的對(duì)象包括：該邊的兩個(gè)頂（端）點(diǎn)、兩個(gè)相鄰面和四條鄰邊（每一鄰邊與一端點(diǎn)相關(guān)）。每一個(gè)頂點(diǎn)有一個(gè)指針指向以它為端點(diǎn)的某一條邊。每個(gè)面有一個(gè)指針指向它的一條邊。這種數(shù)據(jù)結(jié)構(gòu)便于查找元素之間的連接關(guān)系，但存儲(chǔ)量大，有冗余的存儲(chǔ)信息。

第23講三維實(shí)體的表示

—邊界表示法5．邊界表示數(shù)據(jù)結(jié)構(gòu)（續(xù)）（2）對(duì)稱數(shù)據(jù)結(jié)構(gòu)在對(duì)稱數(shù)據(jù)結(jié)構(gòu)中，顯式地存儲(chǔ)了4種拓?fù)潢P(guān)系：面到邊、邊到面、點(diǎn)到邊、以及邊到點(diǎn)。該數(shù)據(jù)結(jié)構(gòu)可以表達(dá)實(shí)體的面、環(huán)、邊和點(diǎn)的信息。

第24講三維實(shí)體的表示

—掃描表示法1．掃描表示的概念

掃描表示法也稱為推移表示法，該表示法用一個(gè)物體和該物體的一條移動(dòng)軌跡來描述一個(gè)新的物體。做掃描運(yùn)動(dòng)的物體稱為掃描體。掃描表示法的兩個(gè)關(guān)鍵要素是掃描體和掃描軌跡。平移掃描體和旋轉(zhuǎn)掃描體是用掃描表示法構(gòu)成新物體的最常見方法。第24講三維實(shí)體的表示

—掃描表示法2．掃描表示分類（1）平移掃描如果物體是二維平面區(qū)域，軌跡是垂直于該平面的直線段，掃描的結(jié)果為一柱體，這種簡(jiǎn)單的掃描稱為平移掃描。平移掃描所得到的物體稱為平移掃描體。如圖16所示為平移掃描體，圖中箭頭為掃描方向。

第24講三維實(shí)體的表示

—掃描表示法第24講三維實(shí)體的表示

—掃描表示法3．掃描表示分類（續(xù)）（2）旋轉(zhuǎn)掃描將二維區(qū)域繞一條軸旋轉(zhuǎn)形成新物體的掃描稱為旋轉(zhuǎn)掃描。旋轉(zhuǎn)掃描所得到的物體為旋轉(zhuǎn)體。如圖17所示為旋轉(zhuǎn)體。

第24講三維實(shí)體的表示

—掃描表示法第24講三維實(shí)體的表示

—掃描表示法4．掃描表示分類（續(xù)）（3）廣義掃描P為任意曲線，物體沿軌道P推移并且允許物體在推移中任意變化，由此形成新的物體，該方法稱為廣義掃描法。在廣義掃描法中，物體的尺寸、形狀和朝向在推移過程中都可以改變，因此由該方法可以得到形狀復(fù)雜的物體。廣義掃描法的表示能力遠(yuǎn)遠(yuǎn)強(qiáng)于平移掃描法和旋轉(zhuǎn)掃描法。

第25講

三維實(shí)體的表示

—構(gòu)造實(shí)體幾何表示法

1．構(gòu)造實(shí)體幾何表示法的概念

用簡(jiǎn)單的實(shí)體(也稱為體素)通過集合運(yùn)算組合成所需的物體的方法稱為構(gòu)造實(shí)體幾何表示法。常用的體素有長(zhǎng)方體、圓柱體、圓錐體、圓臺(tái)體、環(huán)和球等。在構(gòu)造實(shí)體幾何法中，集合運(yùn)算的實(shí)現(xiàn)過程可以用一棵二叉樹來描述，二叉樹的葉子結(jié)點(diǎn)表示體或幾何變換參數(shù)，非終端結(jié)點(diǎn)表示施加于其子結(jié)點(diǎn)的正則集合運(yùn)算或幾何變換，根結(jié)點(diǎn)表示的是運(yùn)算的最終結(jié)果。如果參與運(yùn)算的體素都是正則的，則所得的最終結(jié)果也是正則的，即結(jié)果為有效實(shí)體。

第25講

三維實(shí)體的表示

—構(gòu)造實(shí)體幾何表示法2．體素的表示第25講

三維實(shí)體的表示

—構(gòu)造實(shí)體幾何表示法3．構(gòu)造實(shí)體幾何表示法的主要應(yīng)用領(lǐng)域構(gòu)造實(shí)體幾何表示法既是實(shí)體表示法，又是實(shí)體構(gòu)造法，主要應(yīng)用于計(jì)算機(jī)輔助設(shè)計(jì)（CAD）。構(gòu)造實(shí)體幾何表示法也有其局限性。當(dāng)用戶輸入體素時(shí)，主要是給定體素的有關(guān)參數(shù)，如長(zhǎng)方體的長(zhǎng)、寬和高，然后由系統(tǒng)給出該體素的表面方程。當(dāng)對(duì)體素進(jìn)行求交運(yùn)算時(shí)，可以通過其表面方程進(jìn)行求交，但這種求交的結(jié)果難以用代數(shù)方程來表示，因而不便于繼續(xù)參與集合運(yùn)算。單純的構(gòu)造實(shí)體幾何方法存在著難以克服的困難，人們通常用構(gòu)造實(shí)體法輸入?yún)?shù)、定義體素，然后將其轉(zhuǎn)化為邊界表示，最后再進(jìn)行集合運(yùn)算和圖形輸出。第26講三維實(shí)體的表示

—八叉樹表示法1．八叉樹的概念

將物體所在的空間分割成立方體網(wǎng)格，物體由其所點(diǎn)用的立方體序列來表示，這種表示物體的方法稱為占有空間計(jì)數(shù)法。第26講三維實(shí)體的表示

—八叉樹表示法2．八叉樹的概念（續(xù)）如圖18所示，將物體所在空間用一個(gè)立方體（也稱為宇宙）來表示，如果該立方體完全被物體占有，那么該立方體表示為“滿”；如果該立方體與物體不交，則該立方體表示為“空”；其它情況下，將立方體等分為8個(gè)立方體，按本規(guī)則繼續(xù)標(biāo)識(shí)各個(gè)小立方體，直到立方體的大小達(dá)到所允許的分辨率為止。這種遞歸分割的物體表示形式可以用八叉樹來描述，稱為八叉樹表示法，它是一種層次結(jié)構(gòu)的占有空間計(jì)數(shù)法。第26講三維實(shí)體的表示

—八叉樹表示法第26講三維實(shí)體的表示

—八叉樹表示法3．八叉樹的概念（續(xù)）采用八叉樹表示法時(shí)，樹的根結(jié)點(diǎn)表示實(shí)體所在的空間，當(dāng)一個(gè)結(jié)點(diǎn)既不標(biāo)識(shí)為“滿”，也不標(biāo)識(shí)為“空”時(shí)，則存在該結(jié)點(diǎn)的8個(gè)子結(jié)點(diǎn)。對(duì)任何形式定義的物體可以建立八叉樹生成算法：利用物體的最大和最小坐標(biāo)值，可以圍繞該物體定義一個(gè)平行六面體，然后對(duì)包含物體的三維空間區(qū)域逐個(gè)卦限測(cè)試，直至生成八叉樹表示。第26講三維實(shí)體的表示

—八叉樹表示法4．八叉樹表示法的優(yōu)點(diǎn)

（1）可以用統(tǒng)一而且簡(jiǎn)單的形體來表示空間任意形狀的實(shí)體。（2）易于實(shí)現(xiàn)實(shí)體之間的集合運(yùn)算，如交、并和差等運(yùn)算。（3）易于檢查實(shí)體之間是否接觸。（4）易于計(jì)算實(shí)體的統(tǒng)計(jì)量，如體積、質(zhì)量和重量等。（5）在對(duì)實(shí)體進(jìn)行顯示時(shí)，易于實(shí)現(xiàn)消隱。

第26講三維實(shí)體的表示

—八叉樹表示法5．八叉樹表示法的缺點(diǎn)

（1）在分辨率較高時(shí)，所需的存儲(chǔ)容量較大。（2）難于實(shí)現(xiàn)某些幾何變換，如旋轉(zhuǎn)和任意比例系數(shù)的比例變換等。（3）只能近似地表示空間實(shí)體，難于轉(zhuǎn)換為表達(dá)更精確的邊界表示。

第27講三維形體輸出

—投影及其分類1．投影的概念

投影是從高維（物體）空間到低維（投影）空間的一種映射。在計(jì)算機(jī)圖形學(xué)中只限于討論從三維空間到二維空間的投影。如圖19所示，在三維空間中取一點(diǎn)，稱該點(diǎn)為投影中心（觀察點(diǎn)，視點(diǎn)）；再選定一個(gè)不經(jīng)過投影中心的平面，該平面稱為投影面（觀察面）；從投影中心向物體上各點(diǎn)發(fā)出射線，這些射線稱為投影線；投影線交于投影面，形成物體的象，該象稱為物體在投影面上的投影。

第27講三維形體輸出

—投影及其分類2．投影的概念(續(xù))第27講三維形體輸出

—投影及其分類3．投影的概念(續(xù))從物體得到它在投影面上的象的過程稱為投影變換。如果投影空間為平面，投影線為直線，則稱該投影為平面幾何投影。更復(fù)雜的投影可以采用曲線作為投影線，采用曲面作為投影面。

第27講三維形體輸出

—投影及其分類4．平面幾何投影分類平面幾何投影分為兩大類：透視投影和平行投影。當(dāng)投影中心到投影面的距離為有限值時(shí)，相應(yīng)的投影為透視投影；當(dāng)投影中心到投影面的距離為無窮大時(shí)，相應(yīng)的投影即為平行投影。第27講三維形體輸出

—投影及其分類5．平面幾何投影分類(續(xù))當(dāng)投影中心到投影面的距離充分大時(shí)，可以把這個(gè)充分大的值看成是無窮大，如太陽可以看成距我們無窮遠(yuǎn)。當(dāng)投影中心在無窮遠(yuǎn)處時(shí)，投影線相互平行，在定義投影時(shí)，只需指明投影方向。在定義透視投影時(shí)，需要指明投影中心。第28講三維形體輸出

—透視投影1．透視投影的特性

如圖20所示，在透視投影中，不平行于投影平面的平行線，經(jīng)過透視投影后交匯到一個(gè)點(diǎn)，該點(diǎn)稱為滅點(diǎn)。在透視投影中，不平行于投影平面的平行線，經(jīng)過透視投影后交匯到一個(gè)點(diǎn)，該點(diǎn)稱為滅點(diǎn)。主滅點(diǎn)的個(gè)數(shù)正好等于與投影面相交的坐標(biāo)軸的個(gè)數(shù)，顯然至多有三個(gè)主滅點(diǎn)。透視投影按主滅點(diǎn)個(gè)數(shù)分為一點(diǎn)透視、二點(diǎn)透視和三點(diǎn)透視。第28講三維形體輸出

—透視投影2．透視投影的特性(續(xù))第28講三維形體輸出

—透視投影3．透視投影的特性(續(xù))在三維空間中，平行線只在無窮遠(yuǎn)處相交，所以滅點(diǎn)可以看成是無窮遠(yuǎn)點(diǎn)在投影面上的投影點(diǎn)。主滅點(diǎn)的個(gè)數(shù)最多三個(gè)，但滅點(diǎn)的個(gè)數(shù)有無限多個(gè)。

第28講三維形體輸出

—透視投影4．透視投影的表示第28講三維形體輸出

—透視投影5．透視投影的表示(續(xù))第29講三維形體輸出

—平行投影1．平行投影的分類

平行投影分為正（射）投影和斜（射）投影。在正投影中，投影方向與投影面垂直；在斜投影中，投影線不垂直于投影面。在正投影中，當(dāng)投影面與x,y和z垂直時(shí)所得到的投影分別稱為正（主）視圖、側(cè)視圖和俯視圖，統(tǒng)稱為三視圖。三視圖常用于工程繪圖，在CAD軟件中經(jīng)常用到它們。第29講三維形體輸出

—平行投影2．平行投影的分類(續(xù))在正投影中，當(dāng)投影面與三個(gè)坐標(biāo)軸都不垂直時(shí)，所形成的投影稱為正軸測(cè)。根據(jù)投影面與坐標(biāo)軸的夾角之間的關(guān)系，正軸測(cè)分為等軸測(cè)、正二測(cè)和正三測(cè)。在斜投影中，當(dāng)投影方向與投影面成450角時(shí)，得到的投影稱為斜等測(cè)；當(dāng)投影方向與投影面成arctg(2)角度時(shí)，得到的投影稱為斜二測(cè)。與投影面垂直的直線段在斜等測(cè)中長(zhǎng)度保持不變，在斜二測(cè)中長(zhǎng)度減半。第29講三維形體輸出

—平行投影3．正投影第29講三維形體輸出

—平行投影4．正投影(續(xù))第30講三維形體輸出

—觀察空間1．觀察空間

投影面也稱為觀察平面，可以用一個(gè)點(diǎn)和一個(gè)向量來定義該平面，該點(diǎn)稱為觀察參考點(diǎn)（VRP），該向量稱為觀察平面法向量（VPN）。在觀察平面上指定的一個(gè)窗口稱為觀察窗口，其作用與圖形變換中的窗口類似，只有在觀察窗口內(nèi)的圖形被映射到視圖區(qū)。投影參考點(diǎn)（PRP）用于確定透視投影的投影中心和平行投影的投影方向。對(duì)于透視投影，投影中心即投影參考點(diǎn)；對(duì)于平行投影，投影方向平行于從投影參考點(diǎn)到觀察窗口中心的矢量。第30講三維形體輸出

—觀察空間2．觀察空間(續(xù))在透視投影中，從投影中心出發(fā)，過觀察窗口邊線的射線所圍成的四棱錐稱為透視投影的觀察空間；在平行投影中，從投影參考點(diǎn)到觀察窗口中心的方向?yàn)橥队胺较?，過觀察窗口邊線且平行于投影方向的直線包圍的四棱柱稱為平行投影的觀察空間。在觀察空間中，通常定義兩個(gè)裁剪平面—前裁剪面和后裁剪面。裁剪面平行于觀察平面。觀察空間位于前后裁剪面之間的部分稱為裁剪空間或視見體。第30講三維形體輸出

—觀察空間3．視圖系統(tǒng)

在計(jì)算機(jī)圖形學(xué)中，為了通過顯示設(shè)備來考察幾何物體的特性，引入了一系列用于顯示輸出的坐標(biāo)系統(tǒng)來組成不同的視圖系統(tǒng)（viewingsystem）。這些坐標(biāo)系統(tǒng)包括：（1）世界坐標(biāo)系(worldcoordinateSystems)該坐標(biāo)系統(tǒng)主要用于計(jì)算機(jī)圖形場(chǎng)景中的所有圖形對(duì)象的空間定位和定義，包括觀察者的位置、視線等等。計(jì)算機(jī)圖形系統(tǒng)中涉及的其它坐標(biāo)系統(tǒng)都是參照它進(jìn)行定義。第30講三維形體輸出

—觀察空間4．視圖系統(tǒng)(續(xù))（2）局部坐標(biāo)系(LocalCoordinateSystem)為考察物體方便起見，用獨(dú)立于世界坐標(biāo)系的局部坐標(biāo)系來定義物體幾何特性。通常是在不需要指定物體在世界坐標(biāo)系中的方位的情況下，使用局部坐標(biāo)系。一旦定義了“局部”物體，通過指定在局部坐標(biāo)系的原點(diǎn)在世界坐標(biāo)系中的方位，然后通過幾何變換，就可很容易地將“局部”物體放入世界坐標(biāo)系內(nèi)，使它由局部上升為全局。

第30講三維形體輸出

—觀察空間5．視圖系統(tǒng)(續(xù))（3）觀察坐標(biāo)系(Viewingcoordinatesystems)觀察坐標(biāo)系通常是以視點(diǎn)的位置為原點(diǎn)，通過用戶指定的一個(gè)觀察向量(viewupvector)來定義整個(gè)坐標(biāo)系統(tǒng)，缺省為左手坐標(biāo)系。觀察坐標(biāo)系主要用于從觀察者的角度對(duì)整個(gè)世界坐標(biāo)系內(nèi)的對(duì)象進(jìn)行重新定位和描述，從而簡(jiǎn)化幾何物體在投影面的成像的數(shù)學(xué)推導(dǎo)和計(jì)算。第30講三維形體輸出

—觀察空間6．視圖系統(tǒng)(續(xù))（4）成像面（視平面）坐標(biāo)系統(tǒng)它是一個(gè)二維坐標(biāo)系統(tǒng)，主要用于指定物體在成像面上的所有點(diǎn)，往往是通過指定成像面與視點(diǎn)之間的距離來定義成像面。成像面有時(shí)也稱投影面，可進(jìn)一步在投影面上定義稱為窗口的方形區(qū)域來實(shí)現(xiàn)部分成像。

第30講三維形體輸出

—觀察空間7．視圖系統(tǒng)(續(xù))（5）屏幕坐標(biāo)系統(tǒng)也稱設(shè)備坐標(biāo)系統(tǒng)，它主要用于某一特殊的計(jì)算機(jī)圖形顯示設(shè)備(如光柵顯示器)表面上點(diǎn)的定義。在多數(shù)情況下，對(duì)于每一個(gè)具體的顯示設(shè)備，都有一個(gè)單獨(dú)的坐標(biāo)系統(tǒng)。在定義了成像窗口的情況下，可進(jìn)一步在屏幕坐標(biāo)系統(tǒng)中定義稱為視圖區(qū)(viewport)的有界區(qū)域，視圖區(qū)中的成像即為實(shí)際所觀察到的圖形對(duì)象。

第31講

三維形體輸出

—空間轉(zhuǎn)換

1．用戶（世界）坐標(biāo)系到觀察坐標(biāo)系的變換

第31講

三維形體輸出

—空間轉(zhuǎn)換2．用戶（世界）坐標(biāo)系到觀察坐標(biāo)系的變換（續(xù)）第31講

三維形體輸出

—空間轉(zhuǎn)換3．窗口到視圖的變換

第31講

三維形體輸出

—空間轉(zhuǎn)換4．規(guī)格化坐標(biāo)(NDC)到設(shè)備坐標(biāo)(DC)的變換

第32講三維形體輸出

—三維裁剪第32講三維形體輸出

—三維裁剪2．三維編碼裁剪

三維裁剪是將空間的直線段相對(duì)于裁剪空間的6個(gè)面進(jìn)行裁剪。二維裁剪中的編碼裁剪和中點(diǎn)裁剪法都可以推廣到三維裁剪。三維編碼裁剪法將空間直線段的端點(diǎn)進(jìn)行6位二進(jìn)制編碼，根據(jù)其編碼來判定它與規(guī)范化投影空間的位置關(guān)系。與二維裁剪法一樣，如果線段兩端點(diǎn)的二進(jìn)制編碼為0，則該線段完全落在裁剪空間之內(nèi)；如果線段兩端點(diǎn)的二進(jìn)制編碼按位與結(jié)果非零，則線段在裁剪空間的外面；其它情況下，線段與裁剪空間的某個(gè)面相交。

第32講三維形體輸出

—三維裁剪3．三維編碼裁剪（續(xù)）第32講三維形體輸出

—三維裁剪4．三維編碼裁剪（續(xù)）第32講三維形體輸出

—三維裁剪5．空間線段與裁剪面求交

第33講

消隱技術(shù)

—深度緩存算法

1．消隱的概念

找出并消除物體中的不可見部分，稱為消隱。經(jīng)過消隱得到的圖形稱為消隱圖。有兩類消隱問題：線消隱（Hidden-line）和面消隱（Hidden-surface）。前者用于線框圖，后者用于填色圖。消隱算法可以分為兩大類：對(duì)象空間方法（ObjectSpaceMethods）和圖象空間方法（imageSpaceMethods）。第33講

消隱技術(shù)

—深度緩存算法2．消隱的概念（續(xù)）對(duì)象空間是對(duì)象三維空間。對(duì)象空間方法是通過分析對(duì)象的三維特性之間的關(guān)系來確定其是否可見。例如，將三維平面作為分析對(duì)象，通過比較各平面的參數(shù)來確定它們的可見性。圖象空間是對(duì)象投影后所在的二維空間。圖象空間方法是將對(duì)象投影后分解為象素，按照一定的規(guī)律，比較象素之間的z值，從而確定其是否可見。消隱算法涉及到排序和相關(guān)性。排序是為了確定消隱對(duì)象之間的遮擋關(guān)系。相關(guān)性是指物體或視圖區(qū)的圖象局部保持不變的一種性質(zhì)。

第33講

消隱技術(shù)

—深度緩存算法3．深度緩存算法

深度緩存（Z-buffer）算法是一種典型的、簡(jiǎn)單的圖象空間面消隱算法。該算法需要一個(gè)深度緩存數(shù)組ZB，此外還需要一個(gè)顏色屬性數(shù)組CB，它們的大小與屏幕上像素點(diǎn)的個(gè)數(shù)相同。第33講

消隱技術(shù)

—深度緩存算法4．深度緩存算法（續(xù)）Z-buffer算法的步驟如下：（1）初始化ZB和CB，使得ZB(i,j)=Zmax,CB(i,j)=背景色，i=1,…，m;j=1,…，n;（2）對(duì)多邊形P，計(jì)算它在點(diǎn)（i,j）處的深度值z(mì)i,j,（3）若zi,j<ZB(i,j),則ZB（i,j）=zi,j,CB(i,j)=多邊形P的顏色；（4）對(duì)每個(gè)多邊形重復(fù)（2）、（3）兩步，最終在CB中存放的就是消隱后的圖形。

第33講

消隱技術(shù)

—深度緩存算法5．深度緩存算法（續(xù)）深度緩存算法的最大缺點(diǎn)是兩個(gè)緩存占用的存儲(chǔ)單元太多?？梢詫蓚€(gè)幀緩存（ZB，CB）改為行緩存，計(jì)算出一條掃描線上的象素值就輸出，然后刷新行緩存，再計(jì)算下一條掃描線上的象素。這種方法可以減少緩存占用的存儲(chǔ)空間，但它無法利用多邊形中點(diǎn)的垂直相關(guān)性，因而勢(shì)必降低效率。隨著目前計(jì)算機(jī)硬件的高速發(fā)展，Z緩沖器算法已被硬化，成為最常用的一種消隱方法。許多顯示加速卡都支持這一算法。

第34講消隱技術(shù)—掃描線算法在多深度緩存算法中,沒有用到任何相關(guān)性。事實(shí)上，在判斷一個(gè)點(diǎn)是否在多邊形內(nèi)以及計(jì)算多邊形在一個(gè)點(diǎn)的深度值時(shí)，都可以利用邊的相關(guān)性和點(diǎn)的相關(guān)性。本講討論如何利用相關(guān)性來提高判斷速度和計(jì)算速度，然后導(dǎo)出掃描線消隱算法。

第34講消隱技術(shù)—掃描線算法1．相關(guān)性和深度值計(jì)算

先來分析多邊形中點(diǎn)與點(diǎn)在水平方向上的相關(guān)性。設(shè)某個(gè)多邊形所在的平面方程為：ax+by+cz+d=0若c不為0，則

z=(-ax-by-d)/c。在點(diǎn)（xi,yi）處，zi=(-d-axi-byi)/c；而在點(diǎn)（xi+1,yi）處（用逐點(diǎn)掃描來處理），zi+1=(-d-a(xi+1)-byi)/c。因?yàn)?/p>

xi+1=xi+1，所以zi+1=zi-a/c。類似地可推出平面多邊形內(nèi)的點(diǎn)在垂直方向上的相互關(guān)系。設(shè)多邊形一條邊的方程為

ax+by+c=0。將多邊形投影到XOY平面上，在y=yi點(diǎn)，xi=(-c-byi)/a;在yi+1點(diǎn)，因yi+1=yi+1，所以xi+1=xi-b/a。

第34講消隱技術(shù)—掃描線算法2．相關(guān)性和深度值計(jì)算（續(xù)）多邊形的點(diǎn)及其深度值的算法：1）將多邊形的邊按其y最小值排序，搜索多邊形中各頂點(diǎn)的y值，找出其中最小的值ymin和最大值ymax;2）令掃描線y=ymin到y(tǒng)max以增量為1變化。此時(shí)，(a)找出與當(dāng)前掃描線相交的所有邊，利用垂直相關(guān)性求出這些邊與掃描線的交點(diǎn),并將交點(diǎn)從小到大排序；(b)在相鄰兩交點(diǎn)之間選一點(diǎn)，判斷其是否在多邊形內(nèi),如果是，則利用水平相關(guān)性，求出兩交點(diǎn)之間各點(diǎn)的深度值；重復(fù)（b），直到當(dāng)前掃描線上在多邊形內(nèi)的點(diǎn)的深度都求出為止。第34講消隱技術(shù)—掃描線算法3．掃描線算法

掃描線算法的基本步驟如下：1）

對(duì)每個(gè)多邊形求取其頂點(diǎn)中所含的y的最小值ymin和最大值ymax，按ymin進(jìn)行排序，建立活性多邊形表，活性多邊形表中包含與當(dāng)前掃描線相交的多邊形。2.）對(duì)每條掃描線上的點(diǎn)置初值：Z值Z(x)取為最大，顏色I(xiàn)(x)取為背景色。

第34講消隱技術(shù)—掃描線算法4．掃描線算法（續(xù)）3）對(duì)每條掃描線y，找出所有與當(dāng)前掃描線相交的多邊形。對(duì)每個(gè)活性多邊形，求出掃描線在此多邊形內(nèi)的部分，對(duì)這些部分中每個(gè)象素x計(jì)算多邊形在此處的Z值。若Z小于Z(x)，則置Z(x)為Z，I(x)為多邊形在此處的顏色值。4）

對(duì)活性多邊形表中的所有多邊形都處理完畢后，所得的I(x)即為顯示的顏色，可進(jìn)行顯示并對(duì)下一條掃描線進(jìn)行處理，即掃描線的y=y+1。此時(shí)應(yīng)更新活性多邊形表。

第35講消隱技術(shù)—區(qū)域排序算法和列表優(yōu)先算法

1．區(qū)域排序算法

區(qū)域排序算法的基本思想是：在圖象空間中，將待顯示的所有多邊形按深度值從小到大排序，用前面可見多邊形去切割后面的多邊形，最終使得每個(gè)多邊形要么是完全可見，要么是完全不可見。用區(qū)域排序算法消隱，需要用到一種多邊形裁剪算法，這種裁剪算法不僅能處理凸多邊形，而且可以處理凹多邊形，以及內(nèi)部有空洞的多邊形。

第35講消隱技術(shù)—區(qū)域排序算法和列表優(yōu)先算法2．區(qū)域排序算法

（續(xù)）用一個(gè)多邊形對(duì)另一個(gè)多邊形進(jìn)行裁剪時(shí)，稱用來裁剪的多邊形為裁剪多邊形，另一個(gè)多邊形為被裁剪多邊形。算法要求多邊形的邊都是有向的，不妨設(shè)多邊形的外環(huán)總是順時(shí)針方向的。若兩多邊形相交，新的多邊形可以用“遇到交點(diǎn)后向右拐”的規(guī)則來生成。于是被裁剪多邊形被分為兩個(gè)乃至多個(gè)多邊形；我們把其中落在裁剪多邊形外的多邊形叫作外部多邊形；把落在裁剪多邊形之內(nèi)的多邊形叫作內(nèi)部多邊形。第35講消隱技術(shù)—區(qū)域排序算法和列表優(yōu)先算法3．區(qū)域排序消隱算法

（1）按各多邊形z最小值（或最大值、平均值）排序；（2）選擇當(dāng)前深度最小的多邊形為裁剪多邊形；（3）用裁剪多邊形對(duì)深度值更大的多邊形進(jìn)行裁剪；（4）比較裁剪多邊形與各個(gè)內(nèi)部多邊形的深度，如果裁剪多邊形深度大于某個(gè)內(nèi)部多邊形的深度，則恢復(fù)被裁剪的各個(gè)多邊形的原形，選擇新的裁剪多邊形，回到3）再做，否則做5）；

（5）選擇下一個(gè)深度最小的多邊形作為裁剪多邊形，從3）開始做，直到所有的多邊形都處理過為止。在得到的多邊形中，所有的內(nèi)部多邊形是不可見的，其余多邊形均為可見多邊形。第35講消隱技術(shù)—區(qū)域排序算法和列表優(yōu)先算法4．列表優(yōu)先算法列表優(yōu)先算法就是按多邊形離觀察者的遠(yuǎn)近建立一張表，距離觀察者近的優(yōu)先級(jí)高，遠(yuǎn)的優(yōu)先級(jí)低。正確地建立該表后，只要從優(yōu)先級(jí)低的多邊形開始，依次繪制相應(yīng)的多邊形，直到繪制出優(yōu)先級(jí)最高的多邊形為止，就生成了整個(gè)場(chǎng)景的繪制結(jié)果。該算法也稱為畫家算法，因?yàn)楫嫾依L畫時(shí)常先畫底色，然后再一層層往上畫。第35講消隱技術(shù)—區(qū)域排序算法和列表優(yōu)先算法5．列表優(yōu)先算法（續(xù)）列表優(yōu)先算法的困難之處在于怎樣對(duì)多邊形作出一個(gè)正確的排序。在預(yù)先劃分的多邊形集中，當(dāng)多邊形之間出現(xiàn)彼此遮擋的情況時(shí)，必須進(jìn)一步劃分多邊形集，直到不再出現(xiàn)沖突為止。第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型決定一個(gè)物體外觀的因素包括：（1）物體的幾何形狀；（2）物體的表面特征，如粗糙度、感光度、顏色和紋理等；（3）光源；（4）物體與光源的相對(duì)位置；（5）物體周圍環(huán)境。生成真實(shí)感圖形的關(guān)鍵在于考察影響物體外觀的各種因素，建立起合適的光照模型。第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型1．色彩模型

對(duì)于彩色光柵掃描顯示器，屏幕上顯示的一幅圖是由一個(gè)一個(gè)像素點(diǎn)組成的。每個(gè)像素點(diǎn)用紅（R）、綠（G）和藍(lán)（B）三基色混合而成的顏色來繪制。如圖24所示，三基色不僅可以混合成各種不同的顏色，還可以表示色彩不同的亮度，如R軸表示紅色，但從0到1紅色的亮度不斷增強(qiáng)。第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型2．色彩模型(續(xù))第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型3．簡(jiǎn)單光反射模型

當(dāng)光照射到物體的表面時(shí)，物體對(duì)光會(huì)產(chǎn)生反射、透射、散射和吸收作用。用公式可表示如下：

入射光=反射光+透射光+散射光+吸收光在簡(jiǎn)單光照模型中，假定光源是點(diǎn)光源，透射光和散射光近似于零。反射光由漫反射光、鏡面反射光和環(huán)境光三部分組成。第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型4．簡(jiǎn)單光反射模型(續(xù))（1）環(huán)境（泛）光環(huán)境（泛）光在任何方向上的分布都相同，用于模擬從環(huán)境中周圍物體投射到物體表面再反射出來的光。用公式表示為：

I=KaIa

其中Ka是漫反射常數(shù)，與物體表面性質(zhì)有關(guān)，Ia是入射的泛光光強(qiáng)，與環(huán)境的明暗度有關(guān)。

第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型5．簡(jiǎn)單光反射模型(續(xù))（2）漫反射光Lambert定律認(rèn)為，漫反射光在空間均勻分布，反射光強(qiáng)與入射光的入射角的余弦成正比，公式表示為：I=KdIlcosθ其中Kd是漫反射系數(shù)（率），與物體表面性質(zhì)有關(guān)，Il是光源的光強(qiáng)，θ是入射光與物體表面法向量之間的夾角。在實(shí)際應(yīng)用中，從周圍環(huán)境投射來的環(huán)境光或泛光也會(huì)有相當(dāng)?shù)挠绊?，此外，光的傳播以距離平方衰減，所以在某些應(yīng)用中還應(yīng)考慮距離效應(yīng)。第36講真實(shí)感圖形生成技術(shù)—簡(jiǎn)單光反射模型6．簡(jiǎn)單光反射模型(續(xù))（3）鏡面反射光第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理當(dāng)光源和視點(diǎn)在無窮遠(yuǎn)處時(shí)，在同一多邊形內(nèi)，使用簡(jiǎn)單光照模型計(jì)算出來的顏色和亮度值不變。即使是兩個(gè)不同的多邊形，只要它們的法向量相同，其表面的顏色和亮度就無法區(qū)分。對(duì)于法向量方向不同的多邊形，在多邊形的鄰接處會(huì)產(chǎn)生馬赫帶效應(yīng)，使觀察到的亮度變化比實(shí)際的亮度變化要大。

第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理1．雙線性亮度插值

雙線性亮度插值法也稱為Gouraud明暗處理法，它主要針對(duì)簡(jiǎn)單光反射模型中的漫反射項(xiàng)進(jìn)行附加處理。假定一曲面體由多面體表示，已知各多邊形的法向量，則對(duì)每一頂點(diǎn)，可取共享該頂點(diǎn)的各多邊形法向量的平均值作為該頂點(diǎn)處曲面的法向量，然后把該法向量代入光照明模型計(jì)算出頂點(diǎn)處曲面的光亮度。如圖25所示，頂點(diǎn)處的法向量可取共享該頂點(diǎn)的各多邊形的單位法向量的平均值：

NA=（N1+N2+N3+N4）/4第37講

真實(shí)感圖形生成技術(shù)—多邊形明暗處理

2．雙線性亮度插值（續(xù)）

第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理3．雙線性亮度插值（續(xù)）在采用掃描線算法對(duì)上述多邊形進(jìn)行繪制時(shí)，先用多邊形頂點(diǎn)的光亮度線性插值出當(dāng)前掃描平面與多邊形邊界交點(diǎn)處的光亮度值，然后再用交點(diǎn)的光亮度線性插值出多邊形與掃描平面相交區(qū)段上每一采樣點(diǎn)的光亮度值。

第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理4．雙線性法向量插值

雙線性向量插值法也稱為Phong明暗處理法，它的基本思想是對(duì)多邊形頂點(diǎn)處法向量做雙線性插值。在多邊形內(nèi)構(gòu)造一個(gè)連續(xù)變化的法向量函數(shù)，依據(jù)該函數(shù)計(jì)算多邊形內(nèi)各采樣點(diǎn)的法向量，并將它們代入光亮度計(jì)算公式，得到由多邊形近似表示的曲面上各采樣點(diǎn)處的光亮度值。第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理5．雙線性法向量插值

（續(xù)）Phong明暗處理從求解由多邊形近似表示的原曲面的法向量入手，畫面真實(shí)感較Gouraud有明顯的改進(jìn)。但是由于每一象素內(nèi)表面采樣點(diǎn)光亮度還需要光照明模型計(jì)算，故計(jì)算量較大。第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理6．雙線性亮度和法向量插值公式第37講真實(shí)感圖形生成技術(shù)—多邊形明暗處理7．雙線性亮度和法向量插值公式

（續(xù)）第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤模擬直接光照的模型稱為局部光照模型。在局部光照模型中，光線從光源出發(fā)直射到物體上，經(jīng)過漫反射、鏡面反射、環(huán)境光反射和透射達(dá)到視點(diǎn)。模擬間接光照的模型稱為整體光照模型。在整體光照模型中，光線來源于其它物體的反射或折射，從視線的反射或折射方向達(dá)到視點(diǎn)。第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤1．整體光照明模型

（1）Whitted模型Whitted模型除考慮光源在物體表面的直接照射而產(chǎn)生的光亮度外，還考慮了環(huán)境光在鏡面反射方向和規(guī)則透射方向?qū)φ丈潼c(diǎn)產(chǎn)生的作用。I=

Ilocal+IglobalIlocal=Ied+Ild+IlsIglobal=KRIR+KTIT第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤2．整體光照明模型（續(xù)）在Whitted模型中，局部光照模型中只考慮環(huán)境光（Ied)、漫反射光(Ild)和鏡面反射光(Ils)。整體光照模型中，KR和KT分別為反射系數(shù)和折射系數(shù)，IR和IT分別為從其它物體經(jīng)反射或折射達(dá)到視點(diǎn)的光強(qiáng)。第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤3．整體光照明模型（續(xù)）（2）Hall光照明模型Hall在Whitted模型的局部光亮度的計(jì)算中引進(jìn)了光源引起的規(guī)則透射分量Iltr，因而對(duì)透明物體，Hall模型的局部光亮度Ilocal計(jì)算公式為：

Ilocal=Ied+Ild+Ils+Iltr

Hall模型不僅反映物體表面的反射特性，而且能精確反映物體表面的透射特性；與Whitted模型相比，該模型能生成更為逼真的光照模型。

第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤4．光線跟蹤

（1）基本光線跟蹤算法光線跟蹤算法是生成真實(shí)感圖形的主要算法之一。主要的研究焦點(diǎn)在于：（1）快速確定光線與景物是否有交；（2）提高光線與景物的求交計(jì)算效率。由Whitted模型可知，物體表面光亮度由三部分組成：1）

由光源直接照射而引起的光亮度；2）來自環(huán)境中其它物體的入射光在表面產(chǎn)生的鏡面反射光亮度；3）來自環(huán)境中其它物體的入射光在表面產(chǎn)生的規(guī)則透射光亮度。第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤5．光線跟蹤（續(xù)）如圖28所示，由三個(gè)半透明的玻璃球組成的場(chǎng)景的光線跟蹤過程：假定從視點(diǎn)出發(fā)，穿過屏幕象素中心的光線與場(chǎng)景的最近交點(diǎn)為P1，由局部光照明模型計(jì)算出P1處的局部光亮度Ilocal。為了計(jì)算周圍環(huán)境在P1點(diǎn)產(chǎn)生的鏡面反射光和規(guī)則透射光，光線1在P1點(diǎn)處衍生出兩支新的光線：反射光線2和透射光線3。光線2和3繼續(xù)與場(chǎng)景中的景物相交，最近的交點(diǎn)為P2和P3。計(jì)算P2和P3向P1點(diǎn)的輻射光亮度Is和It，代入Whitted模型計(jì)算出象素P處的光亮度I。第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤6．光線跟蹤（續(xù)）第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤7．光線跟蹤（續(xù)）計(jì)算P2和P3處的光亮度時(shí)，除了計(jì)算直接照射的局部光照效果外，還需要考慮周圍環(huán)境對(duì)這兩點(diǎn)產(chǎn)生的整體光照效果。光線跟蹤的終止條件有以下兩種：1)光線射出畫面，即光線與場(chǎng)景中的景物沒有交點(diǎn)，或者與光線相交的最近景物表面為漫射面，或者當(dāng)前跟蹤層次已經(jīng)超過用戶設(shè)定的最大跟蹤層數(shù)；2）跟蹤光線對(duì)顯示象素光亮度的貢獻(xiàn)小于預(yù)先給定的值。第38講真實(shí)感圖形生成技術(shù)

—整體光照模型和光線跟蹤8．光線跟蹤與陰影陰影是真實(shí)感圖形的一個(gè)重要組成部分。景物表面的陰影是由于光源和周圍環(huán)境向景物表面投射的光被其它不透明景物遮擋而造成的。在光線跟蹤算法中，陰影計(jì)算與當(dāng)前交點(diǎn)處局部光亮度的計(jì)算聯(lián)系在一起。在計(jì)算場(chǎng)景中某光源在當(dāng)前交點(diǎn)處產(chǎn)生的局部光照效果時(shí)，首先確定當(dāng)前交點(diǎn)是否位于其它物體的陰影區(qū)域內(nèi)，如果是，當(dāng)前交點(diǎn)由于沒受到該光源的直接照射，局部光亮度只有環(huán)境光一項(xiàng)。第39講真實(shí)感圖形生成技術(shù)—漫反射和輻射在簡(jiǎn)單光照模型中，漫反射被看成是一個(gè)恒定的環(huán)境光。在光線跟蹤算法中，在各個(gè)漫反射方向跟蹤漫反射是不可能的。光線跟蹤只能解決物體間的光反射問題，而漫反射問題則由輻射度方法來解決。

第39講真實(shí)感圖形生成技術(shù)—漫反射和輻射1．輻射度方法

輻射度是指單位時(shí)間內(nèi)從曲面上單位面積漫反射出去的能量。輻射度方法把景物和光源視為一個(gè)封閉的系統(tǒng)，并假定景物的各個(gè)曲面片都是理想的漫反射面。當(dāng)曲面片用小平面片來近似時(shí)，假設(shè)小平面片的漫反射各向均等，且漫反射光能量為一常量。光線跟蹤算法計(jì)算屏幕上各像素點(diǎn)的亮度，而輻射度方法由計(jì)算景物表面上各點(diǎn)的亮度。第39講真實(shí)感圖形生成技術(shù)—漫反射和輻射