計算機圖形學課件21-40講

第21講三維曲面的表示

—B樣條曲面

第21講三維曲面的表示

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

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

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

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

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

—實體及相關概念3．正則（點）集和正則集合運算

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

第22講三維實體的表示

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

第22講三維實體的表示

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

正則集合運算包括正則并、正則交和正則差。它們是由相應集合運算再取正則點集所構成的運算。

第22講三維實體的表示

—實體及相關概念6．二維流形

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

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

—邊界表示法2．多面體

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

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

—邊界表示法3．邊界表示數(shù)據(jù)結構

對實體的表示包括對實體幾何性質(zhì)的表示和拓撲關系的表示。幾何性質(zhì)包括位置、長度和大小等。拓撲關系則表示實體之間的相鄰、相離、相交和包含等關系。描述多面體的頂點、邊和面之間拓撲（鄰接）關系的數(shù)據(jù)結構有很多種，比較典型的有翼邊數(shù)據(jù)結構和對稱數(shù)據(jù)結構及它們的變種。

第23講三維實體的表示

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

第23講三維實體的表示

—邊界表示法5．邊界表示數(shù)據(jù)結構（續(xù)）（2）對稱數(shù)據(jù)結構在對稱數(shù)據(jù)結構中，顯式地存儲了4種拓撲關系：面到邊、邊到面、點到邊、以及邊到點。該數(shù)據(jù)結構可以表達實體的面、環(huán)、邊和點的信息。

第24講三維實體的表示

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

掃描表示法也稱為推移表示法，該表示法用一個物體和該物體的一條移動軌跡來描述一個新的物體。做掃描運動的物體稱為掃描體。掃描表示法的兩個關鍵要素是掃描體和掃描軌跡。平移掃描體和旋轉掃描體是用掃描表示法構成新物體的最常見方法。第24講三維實體的表示

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

第24講三維實體的表示

—掃描表示法第24講三維實體的表示

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

第24講三維實體的表示

—掃描表示法第24講三維實體的表示

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

第25講

三維實體的表示

—構造實體幾何表示法

1．構造實體幾何表示法的概念

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

第25講

三維實體的表示

—構造實體幾何表示法2．體素的表示第25講

三維實體的表示

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

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

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

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

—八叉樹表示法第26講三維實體的表示

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

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

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

第26講三維實體的表示

—八叉樹表示法5．八叉樹表示法的缺點

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

第27講三維形體輸出

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

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

第27講三維形體輸出

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

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

第27講三維形體輸出

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

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

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

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

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

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

第28講三維形體輸出

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

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

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

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

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

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

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

—觀察空間1．觀察空間

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

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

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

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

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

第30講三維形體輸出

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

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

第30講三維形體輸出

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

第31講

三維形體輸出

—空間轉換

1．用戶（世界）坐標系到觀察坐標系的變換

第31講

三維形體輸出

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

三維形體輸出

—空間轉換3．窗口到視圖的變換

第31講

三維形體輸出

—空間轉換4．規(guī)格化坐標(NDC)到設備坐標(DC)的變換

第32講三維形體輸出

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

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

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

第32講三維形體輸出

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

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

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

第33講

消隱技術

—深度緩存算法

1．消隱的概念

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

消隱技術

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

第33講

消隱技術

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

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

消隱技術

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

第33講

消隱技術

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

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

第34講消隱技術—掃描線算法1．相關性和深度值計算

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

z=(-ax-by-d)/c。在點（xi,yi）處，zi=(-d-axi-byi)/c；而在點（xi+1,yi）處（用逐點掃描來處理），zi+1=(-d-a(xi+1)-byi)/c。因為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I=KaIa

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

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

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

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

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

真實感圖形生成技術—多邊形明暗處理

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

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

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

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

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

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

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

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

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

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

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

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

Ilocal=Ied+Ild+Ils+Iltr

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

第38講真實感圖形生成技術

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

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

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

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

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

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

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

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

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