華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用 第二部分 圖形學(xué)基礎(chǔ)

1、計算機圖形學(xué)基礎(chǔ)算法計算機圖形學(xué)基礎(chǔ)算法1、三維形體的計算機表達2、圖形變換、圖形變換3、基礎(chǔ)算法、基礎(chǔ)算法4、線框及消隱顯示、線框及消隱顯示5、真實感顯示、真實感顯示 6、圖形學(xué)的其它應(yīng)用、圖形學(xué)的其它應(yīng)用 現(xiàn)實生活中的產(chǎn)品都是由不同類型的三維(3D)幾何形狀構(gòu)成的集合體。描述產(chǎn)品對象的形狀、大小、位置與結(jié)構(gòu)等幾何信息的模型稱為幾何模型(Geometric Model)。利用計算機圖形技術(shù)可在計算機內(nèi)部描述產(chǎn)品的幾何模型和屬性(如顏色、紋理等)，并生成直觀真實感的圖形。 三維幾何形體的表達 計算機中表示形體幾何模型計算機中表示形體幾何模型通常用：通常用： 線框模型線框模型 表面模型表面模型

2、實體模型實體模型 線框模型和表面模型保存的線框模型和表面模型保存的三維形體信息都不完整。三維形體信息都不完整。 只有實體模型才能夠完整地、只有實體模型才能夠完整地、無歧義地表示三維形體。無歧義地表示三維形體。 點點用三維坐標表示，是最基本的元素用三維坐標表示，是最基本的元素邊邊是形體相鄰面的交界，可為空間直線或曲線是形體相鄰面的交界，可為空間直線或曲線環(huán)環(huán)是有序、有向的封閉邊界，是有序、有向的封閉邊界，外環(huán)外環(huán)僅一個，逆時針方向，僅一個，逆時針方向，內(nèi)環(huán)內(nèi)環(huán)可有可無，也可多個，方向順時針?？捎锌蔁o，也可多個，方向順時針。面面是一個單連通區(qū)域，可以是平面或曲面，由一個外環(huán)是一個單連通區(qū)域，可以是

3、平面或曲面，由一個外環(huán)和若干個內(nèi)環(huán)組成；面的方向由面的法矢決定，法矢向和若干個內(nèi)環(huán)組成；面的方向由面的法矢決定，法矢向外為正向面。外為正向面。基本概念及定義實體實體是由若干個面組成的閉包，實體的邊界是有限個是由若干個面組成的閉包，實體的邊界是有限個面的集合。面的集合。形體表面上任一點的足夠小的形體表面上任一點的足夠小的鄰域鄰域在拓撲上應(yīng)是一個在拓撲上應(yīng)是一個等價的封閉圓，即圍繞該點的形體鄰域在二維空間中等價的封閉圓，即圍繞該點的形體鄰域在二維空間中可構(gòu)成一個單連通域，我們把滿足該定義的形體稱為可構(gòu)成一個單連通域，我們把滿足該定義的形體稱為正則形體正則形體。否則為。否則為非正則形體非正則形體，如

4、存在懸面、懸邊的，如存在懸面、懸邊的長方體為非正則形體。長方體為非正則形體。 線框模型線框模型用頂點和棱邊表示三維形體，其棱邊可以為直線直線、圓弧圓弧、二次曲線二次曲線及樣條曲線樣條曲線組成 。 線框模型在計算機內(nèi)存儲的數(shù)據(jù)結(jié)構(gòu)： 頂點表：記錄各頂點坐標值； 棱線表：記錄每條棱線所連接的兩頂點。class POINT class EDGE double v3; /坐標值 int start_point_no; /邊的起點 int pointtype; /點的屬性 int end_point_no; /邊的終點 CURVE cur； /邊方程定義； . . 以立方體為例，其線框模型結(jié)構(gòu)如下表：優(yōu)

5、點優(yōu)點結(jié)構(gòu)簡單，計算機內(nèi)部易于表達，繪制快速；1. 物體的三維數(shù)據(jù)可以產(chǎn)生任意視圖，為生成工程圖帶來了方便缺點缺點有二義性，缺少表面輪廓信息，當形狀復(fù)雜、棱線過多時，會引起模糊理解。 2. 在數(shù)據(jù)結(jié)構(gòu)中缺少邊與面、面與體之間關(guān)系的信息。從原理上講，此種模型不能消除隱藏線、計算物性、生成數(shù)控加工刀具軌跡、有限元網(wǎng)格剖分、物體干涉檢驗等。表面模型 表面模型是用有連接順序的棱邊圍成的有限區(qū)域來定義形體的表面,再由表面的集合來定義形體。 表面可以是平面，也可以是柱面、球面等類型的二次曲面，也可是樣條曲面構(gòu)成的自由曲面。 表面模型是在線框模型的基礎(chǔ)上，增加有關(guān)面邊信息以及表面特征、棱邊的連接方向等內(nèi)容。

6、 表面模型存儲幾何信息的方法是建立三表結(jié)構(gòu)，即頂點表、邊表和面表。 1）頂點坐標值存放在頂點表頂點表中； 2）含有指向頂點表指針的邊表邊表，用來為多邊形的每條邊標識頂點； 3）面表面表有指向邊表的指針，用來為每個表面標識其組成邊。class POINT class EDGE class FACE 同線框模型 同線框模型 int edge_num； /邊數(shù) int *edge_no; /邊鏈表 int face_type; /面類型 SURFACE sur；/面方程 . . . 表面模型唯一沒有解決的問題是形體究竟在表面的哪一側(cè)，因而在物性計算、有限元分析等應(yīng)用中，表面模型在形體的表示上仍然缺乏

7、完整性。 表面模型可以滿足面面求交，線面消隱、明暗處理和數(shù)控加工的要求。 表面模型的特點表面模型的特點實體模型 為了解決形體存在于表面的哪一側(cè)的問題，可采用實體模型來描述三維立體 在表面模型的基礎(chǔ)上可用三種方法來定義表面的哪一側(cè)存在實體。1）給出實體存在一側(cè)的一點；2）直接用表面的外法矢來指明實體存在的一側(cè)；3）用有向棱邊隱含地表示表面的外法矢方向，該方用有向棱邊隱含地表示表面的外法矢方向，該方 法為法為CADCAD系統(tǒng)廣泛采用。系統(tǒng)廣泛采用。 （思考：為什么不直接用法矢？） 用有向棱邊隱含地表示表面的外法矢方向時，規(guī)定有向棱邊按右手法則右手法則取向：沿著閉合的棱沿著閉合的棱邊所得的方向與表面

8、外法矢方向邊所得的方向與表面外法矢方向一致。一致。 思考：相鄰兩個面的公共棱思考：相鄰兩個面的公共棱邊的方向不會矛盾嗎？邊的方向不會矛盾嗎？ （有矛盾，（有矛盾，CAD系統(tǒng)中增加系統(tǒng)中增加“環(huán)環(huán)” 的定義解決矛盾）的定義解決矛盾）class POINT class EDGE class FACE 同線框模型 同線框模型 int edge_num； /邊數(shù) EDGE * edge; /邊鏈表 int face_type; /面類型 SURFACE sur； /面方程 . . . 數(shù)據(jù)結(jié)構(gòu)如下：數(shù)據(jù)結(jié)構(gòu)如下： 根據(jù)實體模型，可以進行物性計算（如體積、質(zhì)量，慣量）、有限元分析等應(yīng)用。 從前面的實體模

9、型可知，本質(zhì)上我們?nèi)匀徊捎昧诵误w的邊界表面的數(shù)學(xué)描述代替實體描述，并非真正描述了實體內(nèi)部屬性。 這種典型的邊界表面描述方法通常稱為實體的邊界表達方法（BREP），這在后面內(nèi)容將詳細介紹。線框、表面與實體模型的比較模型表示模型表示應(yīng)用范圍應(yīng)用范圍局限性局限性二維線框二維線框畫二維線框圖（工程圖）畫二維線框圖（工程圖）無法觀察參數(shù)的變化，不可無法觀察參數(shù)的變化，不可能產(chǎn)生有實際意義的形體能產(chǎn)生有實際意義的形體三維線框三維線框畫二、三維線框圖畫二、三維線框圖不能表示實體、圖形會有不能表示實體、圖形會有二義性二義性表面模型表面模型藝術(shù)圖形、形體表面的藝術(shù)圖形、形體表面的顯示、數(shù)控加工顯示、數(shù)控加工不能

10、表示實體不能表示實體實體模型實體模型物性計算、有限元分析物性計算、有限元分析用集合運算構(gòu)造形體用集合運算構(gòu)造形體只能產(chǎn)生正則形體只能產(chǎn)生正則形體抽象形體的層次較低抽象形體的層次較低1、三維形體的計算機表達、三維形體的計算機表達2、圖形變換3、基礎(chǔ)算法、基礎(chǔ)算法4、線框及消隱顯示、線框及消隱顯示5、真實感顯示、真實感顯示 6、圖形學(xué)的其它應(yīng)用、圖形學(xué)的其它應(yīng)用圖形變換圖形變換 在CAD系統(tǒng)中，經(jīng)常將顯示的形體進行放大縮小、旋轉(zhuǎn)、平移等，以便用戶更清楚地觀察或編輯操作。實現(xiàn)形體放大縮小、旋轉(zhuǎn)、平移的方法是圖形變換。 在CAD系統(tǒng)中，常用的圖形變換有平移、旋轉(zhuǎn)、比例、投影等變換。二維圖形變換二維圖形

11、變換三三維維圖圖形形變變換換簡單幾何形體的圖形變換應(yīng)用舉例Tzyxzzyyxxzyxzzyyxx111111888212121888212121式中：T為所要進行的圖形變換矩陣 假定一六面體ABCDEFGH各點的坐標分別為（x 1, y 1, z 1）,., (x 8, y 8, z 8)，則經(jīng)過圖形變換后的坐標為：圖形的顯示流程圖形的顯示流程1、三維形體的計算機表達、三維形體的計算機表達2、圖形變換、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示、線框及消隱顯示5、真實感顯示、真實感顯示 6、圖形學(xué)的其它應(yīng)用、圖形學(xué)的其它應(yīng)用1）網(wǎng)格剖分算法）網(wǎng)格剖分算法 目前三維幾何圖形的顯示算法均是基于三角形網(wǎng)

12、格，且算法不斷被固化到硬件中（如顯卡、圖形加速卡等），如： 三維游戲及動畫 復(fù)雜場景渲染顯示 CAD模型顯示 有限元分析 科學(xué)數(shù)據(jù)可視化 電影、戰(zhàn)場仿真A A）平面上的三角剖分）平面上的三角剖分任意多邊形的三角剖分平面點集的三角剖分邊界離散網(wǎng)格生成網(wǎng)格后處理分析、顯示軟件一般處理過程B B）參數(shù)曲面的三角剖分）參數(shù)曲面的三角剖分 為了顯示三維零件形體，CAD系統(tǒng)內(nèi)部提供參數(shù)曲面的三角剖分算法，對形體的每一個表面都進行三角剖分，如圖所示。 經(jīng)過三角剖分處理，三維零件形體表面都生成并記錄了完整的多面體離散數(shù)據(jù)（即顯示數(shù)據(jù)） CAD系統(tǒng)中的顯示算法（線框圖、消隱圖、真實感顯示圖等）大多數(shù)都是基于該多

13、面體離散數(shù)據(jù)的算法處理。C) C) 空間散亂點集的三角剖分（曲面重建）空間散亂點集的三角剖分（曲面重建）?合理分割數(shù)據(jù)并準確重建原產(chǎn)品特征約束模型仍存在困難?快速重建與產(chǎn)品外形拓撲一致的網(wǎng)格局部網(wǎng)格基于三維局部網(wǎng)格基于三維DelaunayDelaunay的構(gòu)造的構(gòu)造重建的網(wǎng)格拓撲同產(chǎn)品局部外形拓撲一致局部點集的三維Delaunay剖分得到對應(yīng)的Voronoi圖連接Voronoi區(qū)中心點得到局部構(gòu)造網(wǎng)格在八叉樹點集中快速得到繞中心點的鄰域點集D) D) 有限元單元網(wǎng)格三角剖分有限元單元網(wǎng)格三角剖分有限元網(wǎng)格生成技術(shù)發(fā)展到現(xiàn)在,已經(jīng)出現(xiàn)了大量的不同實現(xiàn)方法。當前廣泛使用的Delaunay三角化、推

14、進波前法和八叉樹方法等。 三維幾何數(shù)據(jù)壓縮是指對描述三維場景的模型數(shù)據(jù)進行壓縮,以便于模型數(shù)據(jù)的存儲和網(wǎng)絡(luò)傳輸,在分布式虛擬現(xiàn)實、協(xié)同應(yīng)用、多用戶視頻游戲、模型數(shù)據(jù)在計算機內(nèi)部的存儲和傳輸有著非常重要的意義。 事實上三維圖形的信息容量有時也非常大，給存儲和傳輸帶來了嚴重的障礙，必須進行壓縮編碼才適應(yīng)現(xiàn)有的網(wǎng)絡(luò)傳輸技術(shù)，而且在一些需實時處理的應(yīng)用場合更需要壓縮技術(shù)的支持。2）三角形網(wǎng)格壓縮單分辨率模型的幾何數(shù)據(jù)壓縮單分辨率模型的幾何數(shù)據(jù)壓縮是指對物體的一種層次細節(jié)的多邊形網(wǎng)格表示形式的幾何數(shù)據(jù)進行壓縮。使之生成：三角形條帶、扇形、網(wǎng)格 每個三角形獨立地由其3個頂點的9個坐標來表述,如果用浮點數(shù),

15、則需要36個字節(jié)來描述一個三角形(暫且不考慮顏色、法向、紋理坐標等屬性數(shù)據(jù))； 這種表述方案使得每個頂點約需被描述6次,浪費了大量存儲空間。 一種改進的方案是頂點和三角形分開表示，每個頂點用其3個浮點數(shù)表示的位置坐標確定;而每個三角形,則用三角形描述表來表示,其中每個表項僅包含該三角形的3個頂點序號.這使得存儲空間得到很大程度的節(jié)省。 三角形條帶的引入進一步減少了不必要的頂點傳輸：兩個相鄰的三角形公用一條邊,那么從第二個三角形開始,一個新頂點的加入和其前一個三角形的一條邊即可構(gòu)成另一三角形,這使得每個頂點最多必須傳送兩次。V0V2V3V4V5V1V10V9V8V7V6V12V11V14V13V

16、15V0V1V70110111110110000000000000該技術(shù)有利于緩解圖形顯示硬件傳輸瓶頸，加速顯示速度 多分辨率模型的壓縮是面向多分辨率模型的壓縮方法，多分辨率模型可分為： 離散多分辨率模型 連續(xù)多分辨率模型 離散多分辨率模型是對復(fù)雜的三角形網(wǎng)格通過簡化算法逐步得到不同細節(jié)層次的多個三角網(wǎng)格模型 連續(xù)多分辨率模型則是通過一種緊湊的模型表示方法,可生成任意多個不同分辨率的模型（不介紹） 。多分辨率模型的幾何數(shù)據(jù)壓縮離散多分辨率模型的壓縮離散多分辨率模型的壓縮 離散多分辨率模型是對復(fù)雜的三角形網(wǎng)格經(jīng)過一系列簡化操作得到了多個不同分辨率的多邊形網(wǎng)格模型。 這種簡化算法通過對三角形網(wǎng)格施

17、以局部的變化而逐步得到不同的細節(jié)層次(LOD)，為了保證對原始網(wǎng)格的足夠近似,每個簡化步驟都須得到控制。 在分布式圖形應(yīng)用中,針對多分辨率模型,累進傳輸是一個非常有效的傳送措施。 該方案的思想是首先傳輸LOD層次中一個最低分辨率的模型，然后在繪制操作開始的同時傳送一系列的細化操作（類似 JPGE2000思想）； 逐步細化的LOD顯示可以與更加細化LOD操作信息的傳送同步進行,減少了操作人員的等待時間。 但是由于累進傳輸對全局狀態(tài)設(shè)置的要求以及累進傳輸受到傳輸速度的制約,使得累進傳輸?shù)难芯窟M展較為緩慢。 隨著研究的逐步深入，會使得幾何壓縮的算法更加成熟和先進，更能滿足網(wǎng)絡(luò)幾何圖形傳輸、分布式更能

18、滿足網(wǎng)絡(luò)幾何圖形傳輸、分布式虛擬環(huán)境、電子購物等的應(yīng)用需求虛擬環(huán)境、電子購物等的應(yīng)用需求,進一步推動計算機圖形學(xué)向前發(fā)展。3）相交測試與碰撞測試）相交測試與碰撞測試在計算機圖形學(xué)、CAD、CAE中經(jīng)常遇到相交測試盒碰撞測試（運動物體）。如鼠標拾取，視窗裁剪、曲面求交、光線跟蹤、布爾運算、裝配干涉校驗、動畫漫游、運動碰撞、機器人與機床刀具的軌跡規(guī)劃等。尤其對較大規(guī)模數(shù)據(jù)的模型而言，相交測試和碰撞測試的速度對系統(tǒng)影響很大?；径x：基本定義：射線：r(t) = o + t dO:原點，d：射線方向T：參數(shù)軸對齊包容盒（矩形盒）：通常稱：AABB表面平行于坐標面有向包容盒：簡稱：OBB 即任意方向的

19、AABB往往由一個中心，三個單位矢量和三個半邊長定義包容盒離散有向多面體簡稱 kDOPn3n1n2n4s1d1maxd1min由k/2（k為偶數(shù)）個規(guī)一化法矢ni定義，每個ni有兩個標量值dimin和dimax，由三元組（ni，dimin，dimax）描述一個平板層Si ，所有平板層的交集是kDOP的實際體積，上圖為8DOP。包容盒的創(chuàng)建：AABB：直接比較所有多面體（前面的離散多面體）頂點坐標即可得kDOP：是AABB得擴展，將所有多面體頂點坐標投影到kDOP的每條法線ni上，然后保留dimin、dimax，所有這些值定義一個最小的kDOP。球體包容盒：球體包容盒：計算比較麻煩。較為簡單的方

20、法是先計算AABB，再計算AABB的中心，以此為球心，球心到最遠頂點的距離即為半徑。其它更好更優(yōu)的算法可查資料。顯然，最遠距離兩點最為球的直徑是最優(yōu)解，關(guān)鍵是快速搜索。OBB：計算方法較多，較繁瑣。方法之一是： 1）計算凸包 2）計算凸包質(zhì)心 3）計算協(xié)方差矩陣的特征向量 4) 其特征向量即為OBB三個方向 5）向三個方向投影即可求出半長值A(chǔ)ABB、圓球包容盒比較粗糙（分塊多包容盒改進），算法簡單、圓球包容盒比較粗糙（分塊多包容盒改進），算法簡單KDOP比比AABB更緊致，但計算較多更緊致，但計算較多OBB則較則較kDOP更優(yōu)更優(yōu)選用何種包容盒視復(fù)雜度而定。選用何種包容盒視復(fù)雜度而定。測試算法

21、實現(xiàn)基本原則：1）盡可能用最簡單算法排除或確定相交情形；2）充分利用前一次計算結(jié)果；3）如果使用了多種測試，可以嘗試改變內(nèi)部順序，或許會有意外收效；4）盡量避免復(fù)雜計算（如sin，cos，開方等）5）盡量降低維數(shù)，使問題簡化；6）相交測試復(fù)雜時，先用包容盒排除7）養(yǎng)成計時比較的習(xí)慣，采用真實數(shù)據(jù)及計算環(huán)境8）確保計算魯棒性常用相交測試算法：射線球體測試；射線長方體測試；線段長方體測試；射線三角形測試；射線多邊形測試；平面長方體測試；三角形三角形測試；三角形長方體測試；BVBV測試（AABB、KDOP、球、OBB兩兩之間）.。碰撞處理分為：碰撞測試、碰撞確定、碰撞反應(yīng)碰撞處理在游戲中是最重要的算

22、法之一，目前算法很多，文獻很多，目前沒有一個算法能夠?qū)λ星樾味加行У奶幚硭惴?。常見測試方法有：1）用射線測試2）BSP樹測試3）一般層次構(gòu)造測試4）kDOP樹測試5）OBB樹測試（較KDOP方法好）。一般剛體處理簡單一些，柔軟物體（液體、衣物）處理更難。1、三維形體的計算機表達、三維形體的計算機表達2、圖形變換、圖形變換3、基礎(chǔ)算法、基礎(chǔ)算法4、線框及消隱顯示5、真實感顯示、真實感顯示 6、圖形學(xué)的其它應(yīng)用、圖形學(xué)的其它應(yīng)用顯示器顯示原理顯示器顯示原理常規(guī)顯示器上的圖形由熒光屏的點陣組成，電子束按行列次序掃描點矩陣，并由顯示內(nèi)容來控制所掃描的點是否發(fā)亮，每掃描一遍稱為一幀。熒光屏上每一點稱象

23、素（Pixel）。每個象素都對應(yīng)于Buffer中的一個存儲單元，里面存放著該象素的顯示亮度值。象素的亮度值控制電子束對熒光屏的轟擊強度，象素在幀緩存寄存器中的位置編碼控制電子束的偏轉(zhuǎn)位置。 分辨率（Resolution）是光柵掃描顯示設(shè)備最重要的指標 顯示器用于顯示字符、圖形（觸摸顯示屏還可作為輸入設(shè)備）計算機圖形的具體應(yīng)用范圍很廣，但是從基本的處理技術(shù)看只有兩類：l 線條類：線條類：如工程圖、地圖、曲線圖表等；l 明暗圖類（與照片相似）：明暗圖類（與照片相似）：為了生成圖形，首先要有原始數(shù)據(jù)或數(shù)學(xué)模型，如工程人員構(gòu)思的機械零件模型，飛機的總體方案模型，地形航測的判讀數(shù)據(jù)等等。這些數(shù)字化的輸入

24、經(jīng)過計算機處理后變成圖形輸出。三維圖形的線框顯示屬于第一類三維圖形的濃淡圖及真實感顯示是第二類 經(jīng)過三角剖分處理，計算機內(nèi)部增加了完整的三維形體逼近多面體近似表達數(shù)據(jù)結(jié)構(gòu)（即表面全部由以三角形為主的多邊形構(gòu)成，如右下圖所示）。 在線框顯示模型中，為顯示方便，分別對邊界邊和內(nèi)部邊作標識。 顯示方法：遍歷所有多邊形網(wǎng)格的點表和邊表。 兩種顯示狀態(tài)可以任選： a）僅顯示輪廓邊（內(nèi)部邊不顯示） b）顯示所有離散多邊形特點：簡單快捷，但有二義性。 1）線框圖顯示算法）線框圖顯示算法 線框顯示往往導(dǎo)致理解的二義性，如下圖。 為消除二義性，CAD系統(tǒng)經(jīng)常采用消除遮擋的不可見線或面的顯示算法。 習(xí)慣上稱作消除

25、隱藏線和隱藏面消除隱藏線和隱藏面，簡稱消隱消隱。消隱算法的分類：消隱算法的分類：消隱的對象是三維物體，消隱結(jié)果與觀察物體有關(guān)，也與視點有關(guān)。2）線框消隱顯示算法）線框消隱顯示算法(c)多面體的輪廓分類多面體的輪廓分類A）凸多面體消隱算法）凸多面體消隱算法 設(shè)V為由視點出發(fā)的觀察向量，N為某多邊形面的法向量。若V N0，稱該多邊形為后向面后向面。若V N0，稱該多邊形為前向面前向面。 如右圖c，后向面總是看不見的。 (a)前向面前向面 (b)后向面后向面 d) 凸多面體凸多面體 因此，對凸多面體（右圖因此，對凸多面體（右圖d）消隱，）消隱，僅需判斷前向面僅需判斷前向面(即即VN0)，畫出所有，畫

26、出所有前向面的各棱邊即可。前向面的各棱邊即可。 為加速計算，將凸多面體變換，使為加速計算，將凸多面體變換，使觀察方向觀察方向V與與Z軸方向一致，則僅判斷軸方向一致，則僅判斷前向面的法矢分量前向面的法矢分量 Nz 0） for(該面所有棱邊） 畫出棱邊； End凸多面體消隱算法如下：VnizxyB）任意多面體消隱算法）任意多面體消隱算法算法思路：算法思路： 1）為運算方便，對視錐以外的物體應(yīng)先行裁剪過慮，以減少不必要的運算。 2）后向面上的所有棱邊都不可見 3）對每一個前向面的所有棱邊判斷可見性，即判斷面對線的遮擋關(guān)系。 在判斷面與線的遮擋關(guān)系過程中，要反復(fù)地進行線線、線面之間的求交運算，因此因

27、此求交計算速度將是關(guān)鍵。求交計算速度將是關(guān)鍵。線面求交 線線求交某一直線段對任一平面的遮擋關(guān)系判斷算法：某一直線段對任一平面的遮擋關(guān)系判斷算法： (1)若線段兩端點及視點在給定平面同側(cè)（圖a），線段可見，轉(zhuǎn)7 (2)若線段投影與平面投影的包圍盒無交（圖b），線段可見，轉(zhuǎn)7 圖a 視點與線段同側(cè) 圖b 包圍盒不交 (3)求直線與平面的交點。若無交點，轉(zhuǎn)4； 否則，交點在線段內(nèi)部或外部，則判斷 a）若交點在線段內(nèi)部，交點將線段分成兩段， 與視點同側(cè)的一段可見，轉(zhuǎn)7； 剩余另一段在視點異側(cè)，轉(zhuǎn)4繼續(xù)判斷。 b）若交點在線段外部，轉(zhuǎn)4繼續(xù)判斷。 (4)求剩下線段的投影與平面邊界投影的所有交點 根據(jù)交點

28、在原直線方程的參數(shù)值求出Z值(即深度) 若無交點，轉(zhuǎn)5。 (5)以上所求得的各交點將線段的投影分成若干段，求出第一段中點。 (6)若第一段中點在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值進行判斷。（見圖d）(7)當前循環(huán)結(jié)束，各可見段進入下一個面的比較，直至所有面比較完畢。圖d 分段交替取值 上述算法為一條邊，一個面的情況，對多條邊、上述算法為一條邊，一個面的情況，對多條邊、多個面則通過循環(huán)嵌套實現(xiàn)。多個面則通過循環(huán)嵌套實現(xiàn)。 如果消隱對象有N條棱，當N很大時，用兩兩求交的方法這個工作量是很大的O（N2）。為了提高算法的效率，需要設(shè)法減少求交的工作量，因此相交

29、測試是關(guān)鍵。 如上述算法中僅需對可見子線段與其余平面進行類似的可見性判斷，對不可見線段不予計算。 不同消隱算法的關(guān)鍵在于加速計算的策略和方法不同消隱算法的關(guān)鍵在于加速計算的策略和方法不同?，F(xiàn)在的商用不同。現(xiàn)在的商用CAD系統(tǒng)消隱算法正確率不能達到系統(tǒng)消隱算法正確率不能達到100%，速度也有待提高。，速度也有待提高。 重點在于線段可見性的判斷速度和正確性。重點在于線段可見性的判斷速度和正確性。 對CAD圖形來說，需要顯示輪廓，而非內(nèi)部三角形邊界，為此必須對前面的算法修正： 1）三角剖分時，標識是否內(nèi)部邊界； 2）計算是否輪廓邊界； 3）內(nèi)部邊、輪廓邊不必計算消隱； 4）對其它邊進行正常消隱計算。

30、C）畫家算法原理 1) 把屏幕置成背景色; 2）物體的各個面按其離視點的遠近進行排序，排序結(jié)果存在一張深度優(yōu)先級表中; 3）按照從表頭到表尾的順序逐個用背景色填充繪制各個面，用指定顏色繪制面的邊界。 由于后顯示的圖形取代先顯示的畫面，而后顯示的圖形所代表的面離視點更近，所以由遠及近的繪制各面，就相當于消除隱藏面。這與油畫作家作畫的過程類似，先畫遠景，再畫中景，最后畫近景。由于這個原因，該算法習(xí)慣上稱為畫家算法畫家算法或列表優(yōu)先算法列表優(yōu)先算法。 這種算法必須首先建立深度優(yōu)先級表。遮擋關(guān)系判斷示意圖 畫家算法原理簡單，關(guān)鍵是如何對場景中物體按深度排序畫家算法原理簡單，關(guān)鍵是如何對場景中物體按深度

31、排序。 其缺點是只能處理互不相交的面，而且深度優(yōu)先級表中面的順序可能出錯。 在兩個面相交，三個以上的面重疊的情形，用任何排序方法都在兩個面相交，三個以上的面重疊的情形，用任何排序方法都不能排出正確的序。這時只能把有關(guān)的面進行分割后再排序。不能排出正確的序。這時只能把有關(guān)的面進行分割后再排序。 畫家算法既可用于線框圖消隱，也可用于簡單的濃淡圖繪制（只需按指定顏色繪制多邊形，不必畫邊界）1、三維形體的計算機表達、三維形體的計算機表達2、圖形變換、圖形變換3、基礎(chǔ)算法、基礎(chǔ)算法4、線框及消隱顯示、線框及消隱顯示5、真實感顯示 6、圖形學(xué)的其它應(yīng)用、圖形學(xué)的其它應(yīng)用真實感顯示 1 1）光照效果影響因素

32、）光照效果影響因素2 2）簡單效果的濃淡圖生成）簡單效果的濃淡圖生成3 3）一般性效果圖形生成）一般性效果圖形生成4 4）真實感效果圖生成）真實感效果圖生成5 5）紋理映射）紋理映射1）光照效果影響因素）光照效果影響因素 當光照射到物體表面時，當光照射到物體表面時，物體對光會發(fā)生反射、物體對光會發(fā)生反射、透射、吸收、衍射、折射和干涉。透射、吸收、衍射、折射和干涉。 被物體吸收的部分轉(zhuǎn)化為熱。被物體吸收的部分轉(zhuǎn)化為熱。 顏色是人對光的生理反映顏色是人對光的生理反映，反射、透射的光進入，反射、透射的光進入人的視覺系統(tǒng)，使我們能看見物體的顏色。人的視覺系統(tǒng)，使我們能看見物體的顏色。 為模擬這一現(xiàn)象，

33、我們建立一些數(shù)學(xué)模型來替代為模擬這一現(xiàn)象，我們建立一些數(shù)學(xué)模型來替代復(fù)雜的物理模型。這些模型就稱為復(fù)雜的物理模型。這些模型就稱為明暗效應(yīng)模型明暗效應(yīng)模型或者或者光照明模型光照明模型。思考：我們所見物體的顏色是怎樣形成的？思考：我們所見物體的顏色是怎樣形成的？ 影響觀察物體顏色的主要因素有哪些？影響觀察物體顏色的主要因素有哪些？ 在不考慮人的生理因素的情況下，在不考慮人的生理因素的情況下，物體的顏色與物體的顏色與光源顏色、物體表面物理特性、表面粗糙度、周邊環(huán)光源顏色、物體表面物理特性、表面粗糙度、周邊環(huán)境等因素有關(guān)境等因素有關(guān)。 在正常的情況下，光沿著直線傳播，當光遇到介在正常的情況下，光沿著直

34、線傳播，當光遇到介質(zhì)不同的表面時，會產(chǎn)生反射和折射現(xiàn)象，而且質(zhì)不同的表面時，會產(chǎn)生反射和折射現(xiàn)象，而且在反在反射和折射的時候，它們遵循反射定律和折射定律。射和折射的時候，它們遵循反射定律和折射定律。研究光照模型的目的：研究光照模型的目的： 確定物體表面的每一個多邊形或者多邊形中確定物體表面的每一個多邊形或者多邊形中的每一個點的顏色，以便實現(xiàn)具有真實感顯示效的每一個點的顏色，以便實現(xiàn)具有真實感顯示效果的三維形體渲染繪制。果的三維形體渲染繪制。A A）單顏色填充多邊形）單顏色填充多邊形 算法思路：根據(jù)多面體表面的平面法矢決定顏色值，直接調(diào)用直接調(diào)用OpenGL的多邊形填充算法即可的多邊形填充算法即

35、可。 算法簡單，但輪廓分明，各多邊形之間過渡不光滑。2）簡單效果的濃淡圖生成）簡單效果的濃淡圖生成B B）GouraudGouraud模型模型 算法思想： 為使多邊形邊界之間光滑顯示，先計算多邊形各頂點光強，后通過雙線性插值，計算多邊形內(nèi)各點光強。 能保證多邊形邊界顏色的連續(xù)性，但高光模糊，有時出現(xiàn)過亮或過暗條紋（即馬赫效應(yīng)）。 計算較為簡單，計算較為簡單，OpenGL算法已實現(xiàn)硬件加速算法已實現(xiàn)硬件加速。算法步驟：算法步驟：For（每一個三角形） 1) 計算多邊形頂點的平均法向； 2) 根據(jù)基本光照模型計算頂點的平均光強； 3) 通過線性插值，計算多邊形的邊上的各點光強； 4) 通過線性插值

36、，計算多邊形內(nèi)部各點的光強。3）一般性效果圖形生成）一般性效果圖形生成簡單光照明模型簡單光照明模型-Phong模型濃淡圖繪制算法實現(xiàn)濃淡圖繪制算法實現(xiàn)A A） 理想漫反射理想漫反射B B） 鏡面反射鏡面反射 C C） 環(huán)境光環(huán)境光 D D） PhongPhong光照明模型光照明模型A A） Z Z緩沖器緩沖器(Z-Buffer)(Z-Buffer)算法算法 B B） 掃描線算法掃描線算法 C C） 區(qū)間掃描線算法區(qū)間掃描線算法 簡單光照明模型簡單光照明模型-Phong模型 簡單光照明模型簡單光照明模型模擬物體表面對光的反射作用。 光源被假定為點光源點光源，反射作用被細分為鏡面反射鏡面反射(Sp

37、ecular Reflection)和漫反射漫反射(Diffuse Reflection)。 簡單光照明模型簡單光照明模型只考慮物體對直接光照的反射作用，而物體間的光反射作用，只用環(huán)環(huán)境光境光(Ambient Light)來表示。不妨設(shè)：不妨設(shè)： 入射光強為入射光強為I Il l 物體表面上點物體表面上點P P 的法向為的法向為N N 從點從點P P指向光源的向量為指向光源的向量為L L 兩者間的夾角為兩者間的夾角為 圖 漫反射A A） 理想漫反射理想漫反射 當光源來自一個方向時，當光源來自一個方向時，漫反射光均勻向各方向漫反射光均勻向各方向傳播，與視點無關(guān)傳播，與視點無關(guān)，它是由表面的粗糙不

38、平引起的，它是由表面的粗糙不平引起的，因而可假定漫反射光的空間分布是均勻的。因而可假定漫反射光的空間分布是均勻的。p 如果如果 I Il l 表示點光源的強度，表示點光源的強度，k kd d 表示物體表面漫反射系數(shù)，則表示物體表面漫反射系數(shù)，則漫反射方程可描述為：漫反射方程可描述為： cosdlkII )2 ( 0 若若N N為物體表面的單位法向量，為物體表面的單位法向量，L L為物體表面上一點為物體表面上一點指向光源的單位矢量，則：指向光源的單位矢量，則： )(LN dlkII)(1iniliIILN 如果有多個光源，則光強度計算式為：如果有多個光源，則光強度計算式為： 圖 漫反射B B）鏡

39、面反射）鏡面反射 對于理想鏡面，反射光集中在一個方向，并遵守反射定律。 對一般的光滑表面，反射光集中對一般的光滑表面，反射光集中在一個范圍內(nèi)，且由反射定律決定的在一個范圍內(nèi)，且由反射定律決定的反射方向光強最大反射方向光強最大。 圖 鏡面反射光 因此，對于同一點來說，從不同位置所觀察到的鏡面反因此，對于同一點來說，從不同位置所觀察到的鏡面反射光強是不同的。鏡面反射光強可表示為：射光強是不同的。鏡面反射光強可表示為： Ks Ks是與物體有關(guān)的鏡面反射系數(shù)，是與物體有關(guān)的鏡面反射系數(shù)，a a 為視線方向為視線方向V V與反與反射方向射方向R R的夾角，的夾角，n n為反射指數(shù)，反映了物體表面的光澤程

40、度，為反射指數(shù)，反映了物體表面的光澤程度，一般為一般為1 120002000，數(shù)目越大物體表面越光滑。，數(shù)目越大物體表面越光滑。 鏡面反射光將會在反射方向附近形成很亮的光斑，鏡面反射光將會在反射方向附近形成很亮的光斑，稱為高光現(xiàn)象稱為高光現(xiàn)象。 鏡面反射光產(chǎn)生的高光區(qū)域只反映光源的顏色鏡面反射光產(chǎn)生的高光區(qū)域只反映光源的顏色 將將V和和R都格式化為單位向量，鏡面反射光強可表都格式化為單位向量，鏡面反射光強可表示為：示為：式中式中： 對多個光源：對多個光源： 圖 鏡面反射光NLNLR)2( C C）環(huán)境光）環(huán)境光 環(huán)境光是指光源間接對物體的影響，是在物體和環(huán)境之間多環(huán)境光是指光源間接對物體的影響

41、，是在物體和環(huán)境之間多次反射，最終達到平衡時的一種光。次反射，最終達到平衡時的一種光。 近似地認為同一環(huán)境下的環(huán)境光，其近似地認為同一環(huán)境下的環(huán)境光，其光強分布是均勻光強分布是均勻的，它的，它在在任何一個方向上的分布都相同任何一個方向上的分布都相同。例如，透過厚厚云層的陽光就。例如，透過厚厚云層的陽光就可以稱為環(huán)境光。可以稱為環(huán)境光。 在簡單光照明模型中，用一個常數(shù)來模擬環(huán)境光，用式子表在簡單光照明模型中，用一個常數(shù)來模擬環(huán)境光，用式子表示為：示為： 其中：其中：Ia 為環(huán)境光的光強為環(huán)境光的光強 Ka為物體對環(huán)境光的反射系數(shù)為物體對環(huán)境光的反射系數(shù) D D）PhongPhong光照明模型光照

42、明模型 綜上分析，綜上分析，Phong光照明模型表述為：光照明模型表述為：由物體表面上一由物體表面上一點點 P 反射到視點的光強反射到視點的光強 I 為環(huán)境光的反射光強為環(huán)境光的反射光強 I e、理想漫、理想漫反射光強反射光強 I d、和鏡面反射光、和鏡面反射光 I s 的總和的總和，即：，即：按按R、G、B三種顏色分量展開計算得：三種顏色分量展開計算得：I I e I d I s由此可得：由此可得： 用用Phong模型進行計算時，對物體表面上每個點模型進行計算時，對物體表面上每個點P，均，均需計算光線的反射方向需計算光線的反射方向R，再由，再由V計算（計算（RV），為減少計），為減少計算，可

43、作如下假設(shè)：算，可作如下假設(shè)： a) 光源在無窮遠處，即光線方向光源在無窮遠處，即光線方向L為常數(shù)；為常數(shù)； b) 視點在無窮遠處，即視線方向視點在無窮遠處，即視線方向V為常數(shù)；為常數(shù)； c) 為避免計算反射方向為避免計算反射方向R，用（用（HN）代替（）代替（RV），）， 這里這里H為為L和和V的平分向量的平分向量 ，即：，即： H （LV）/ | LV | 注意：注意：Phong模型對物體表面的每一點的光強進行計算，顯模型對物體表面的每一點的光強進行計算，顯然其計算量較大。然其計算量較大。PhongPhong模型計算實例模型計算實例 圖中可以看出高光指數(shù)、漫反射及鏡面系數(shù)對顯示效果的影響圖

44、中可以看出高光指數(shù)、漫反射及鏡面系數(shù)對顯示效果的影響 Phong Phong光照明模型是真實感圖形學(xué)中提出的第一個有影響光照明模型是真實感圖形學(xué)中提出的第一個有影響的光照明模型，生成圖象的真實度已達到可接受程度。的光照明模型，生成圖象的真實度已達到可接受程度。 但在實際應(yīng)用中，它是一個經(jīng)驗?zāi)Ｐ?，還具有以下的一些但在實際應(yīng)用中，它是一個經(jīng)驗?zāi)Ｐ?，還具有以下的一些問題：問題： 用用PhongPhong模型顯示出的物體象塑料，沒有質(zhì)感；模型顯示出的物體象塑料，沒有質(zhì)感； 沒有考慮距離對光照強度的衰減影響；沒有考慮距離對光照強度的衰減影響； 環(huán)境光是常量，沒有考慮物體之間相互的反射光；環(huán)境光是常量，沒

45、有考慮物體之間相互的反射光； 鏡面反射的顏色是光源的顏色，與物體的材料無關(guān)；鏡面反射的顏色是光源的顏色，與物體的材料無關(guān)； 鏡面反射的計算在入射角很大時會產(chǎn)生失真；鏡面反射的計算在入射角很大時會產(chǎn)生失真； PhongPhong模型是簡單的局部光照模型，對物體間相互反射及模型是簡單的局部光照模型，對物體間相互反射及折射、陰影處理欠缺等。折射、陰影處理欠缺等。 濃淡圖繪制算法實現(xiàn)過程濃淡圖繪制算法實現(xiàn)過程 通過前面介紹的通過前面介紹的gouraudgouraud模型、模型、PhongPhong光照模型可光照模型可計算物體表面上點的顏色值計算物體表面上點的顏色值。 為了顯示形體的三維真實感效果圖，下

46、面介紹多為了顯示形體的三維真實感效果圖，下面介紹多面體面體濃淡圖的如何繪制濃淡圖的如何繪制。 由于空間三維物體是連續(xù)點集。顯由于空間三維物體是連續(xù)點集。顯然直接計算點的顏色將無法確定計算采然直接計算點的顏色將無法確定計算采樣點的位置和數(shù)目。樣點的位置和數(shù)目。 事實上，我們僅能看到屏幕所能顯示的區(qū)域。如事實上，我們僅能看到屏幕所能顯示的區(qū)域。如果能夠求得屏幕上每一個象素點所對應(yīng)的物體上點果能夠求得屏幕上每一個象素點所對應(yīng)的物體上點的顏色，這樣就可繪制整個圖形。的顏色，這樣就可繪制整個圖形。 為了得到屏幕上某象素點所對應(yīng)的物體上點的顏為了得到屏幕上某象素點所對應(yīng)的物體上點的顏色，假定作經(jīng)過該象素點

47、的一條射線，射線平行于觀色，假定作經(jīng)過該象素點的一條射線，射線平行于觀察視線，則射線與多面體物體可能有多個交點。察視線，則射線與多面體物體可能有多個交點。 如果物體不是透明的，則處于最前面的交點的顏如果物體不是透明的，則處于最前面的交點的顏色即為所求色即為所求，如右圖所示。，如右圖所示。 最簡單的算法最簡單的算法ZZ緩沖區(qū)（緩沖區(qū)（Z ZBufferBuffer）算法）算法 為計算物體表面上對應(yīng)象素點的顏色為計算物體表面上對應(yīng)象素點的顏色 ，用幀緩存器存，用幀緩存器存放每個象素顏色（按光照模型計算），用深度緩存空間來放每個象素顏色（按光照模型計算），用深度緩存空間來存放每個象素深度值存放每個象

48、素深度值Z，稱為稱為Z緩沖器（即緩沖器（即ZBuffer）。A A） Z Z緩沖器緩沖器(Z-Buffer)(Z-Buffer)算法算法 cz繪制時思路：繪制時思路： a）Z 緩沖器中每個單元值是對應(yīng)象素點所反映物緩沖器中每個單元值是對應(yīng)象素點所反映物體對象的體對象的 z 坐標值，初值取成坐標值，初值取成 z 的極小值。的極小值。 b）將待處理的景物表面上的采樣點變換到圖像空）將待處理的景物表面上的采樣點變換到圖像空間，計算其深度值間，計算其深度值 z。 c）并根據(jù)采樣點在屏幕上的投影位置，將其）并根據(jù)采樣點在屏幕上的投影位置，將其 z 值值與已存貯在與已存貯在 z 緩存器中相應(yīng)象素處的原可見

49、點的深度值緩存器中相應(yīng)象素處的原可見點的深度值進行比較。進行比較。 d）如果該采樣點位于）如果該采樣點位于Z緩存器所記錄的可見點之緩存器所記錄的可見點之前，則將該采樣點處的表面顏色填入幀緩存器相應(yīng)象素，前，則將該采樣點處的表面顏色填入幀緩存器相應(yīng)象素，同時用其深度值更新同時用其深度值更新 z 緩存器存貯的深度值。否則，不緩存器存貯的深度值。否則，不寫入也不更新。寫入也不更新。Z-Buffer算法（）算法（） for (i=0，1，m ) /m：窗口水平方向象素數(shù)目：窗口水平方向象素數(shù)目 for (j=1，n） / n：窗口垂直方向象素數(shù)目：窗口垂直方向象素數(shù)目 用背景色初始化幀緩存用背景色初始

50、化幀緩存CB：CB(i,j)=背景色；背景色；用最小用最小Z值初始化深度緩存：值初始化深度緩存：ZB(i,j)=Zmin；for(每一個多邊形每一個多邊形) 將該多邊形進行投影變換；將該多邊形進行投影變換；掃描轉(zhuǎn)換該多邊形在視平面上的掃描轉(zhuǎn)換該多邊形在視平面上的投影多邊形投影多邊形；for (該多邊形所覆蓋的每個象素該多邊形所覆蓋的每個象素(i,j) ) 計算該多邊形在該象素的深度值計算該多邊形在該象素的深度值Zi,j；if( Zi,j ZB(i,j）) ZB(i,j) Zi,j；計算該多邊形在該象素的顏色值計算該多邊形在該象素的顏色值Ci,j；CB(i,j)= Ci,j； 注：對投影多邊形進

51、行裁剪得到有效區(qū)域，可加快顯示速度注：對投影多邊形進行裁剪得到有效區(qū)域，可加快顯示速度 Z-Buffer算法在象素級上以近物取代遠物。形體算法在象素級上以近物取代遠物。形體在屏幕上的出現(xiàn)順序是無關(guān)緊要的。這種取代方法實在屏幕上的出現(xiàn)順序是無關(guān)緊要的。這種取代方法實現(xiàn)起來遠比總體排序靈活簡單，有利于硬件實現(xiàn)?，F(xiàn)起來遠比總體排序靈活簡單，有利于硬件實現(xiàn)。 然而然而Z-Buffer算法存在缺點：占用空間大，沒有算法存在缺點：占用空間大，沒有利用圖形的相關(guān)性與連續(xù)性。利用圖形的相關(guān)性與連續(xù)性。 Z-Buffer算法以算法簡算法以算法簡單著稱，但也以占空間大而聞名。單著稱，但也以占空間大而聞名。 Z-B

52、uffer算法需要開一個與圖象大小相等的緩存算法需要開一個與圖象大小相等的緩存數(shù)組數(shù)組ZB，可一次性顯示。，可一次性顯示。 當然，也可只用一個深度緩存變量當然，也可只用一個深度緩存變量zb，但需逐點，但需逐點計算顯示，顯示效率低下。計算顯示，顯示效率低下。 B）掃描線掃描線Z-bufferZ-buffer算法算法 如何如何減少減少Z-buffer的緩沖內(nèi)存的緩沖內(nèi)存，并，并利用相關(guān)性利用相關(guān)性提高點提高點與多邊形的包含性測試和深度計算速度，就得到與多邊形的包含性測試和深度計算速度，就得到掃描線掃描線Z-buffer算法算法。 從最上掃描線開始向下對每條掃描線作處理。對每條從最上掃描線開始向下對

53、每條掃描線作處理。對每條掃描線來說，把相應(yīng)的幀緩沖器單元置成底色，在掃描線來說，把相應(yīng)的幀緩沖器單元置成底色，在z緩沖器緩沖器中存放中存放z的極小值。的極小值。 與與Zbuffer算法相比，掃描線算法相比，掃描線Zbuffer將整個繪圖窗將整個繪圖窗口內(nèi)的消隱問題分解到一條條掃描線上解決，使所需的口內(nèi)的消隱問題分解到一條條掃描線上解決，使所需的Z緩沖器大大減少。緩沖器大大減少。 對對每個多邊形檢查它在每個多邊形檢查它在oxy平面上的投影平面上的投影和當前掃描線是否相交和當前掃描線是否相交（如右上圖），若不相（如右上圖），若不相交則跳過該多邊形；交則跳過該多邊形； 若相交則掃描線和多邊形邊界交點

54、一定成若相交則掃描線和多邊形邊界交點一定成對出現(xiàn)，對出現(xiàn)，對每對交點間的象素計算多邊形所在對每對交點間的象素計算多邊形所在平面對應(yīng)點的深度平面對應(yīng)點的深度(即即 z 值值)，并和，并和z緩沖器中相緩沖器中相應(yīng)深度值比較。應(yīng)深度值比較。 對所有多邊形和幀緩沖器每一行都作上述對所有多邊形和幀緩沖器每一行都作上述處理。利用處理。利用多邊形多邊形Y桶桶分類、分類、活化邊表活化邊表處理相處理相鄰掃描線和象素的連貫性，提高算法效率。鄰掃描線和象素的連貫性，提高算法效率。交線交線C C） 區(qū)間掃描線算法區(qū)間掃描線算法 掃描線掃描線z緩沖器算法將消隱問題分緩沖器算法將消隱問題分散到每一條掃描線上去解決，這樣問

55、散到每一條掃描線上去解決，這樣問題變得較簡單了。但題變得較簡單了。但在每個象素處計在每個象素處計算多邊形算多邊形z值的工作量仍是很大值的工作量仍是很大。 實際上實際上每條掃描線被各多邊形邊界每條掃描線被各多邊形邊界在在oxy平面上的投影分割成為數(shù)不多的平面上的投影分割成為數(shù)不多的區(qū)間區(qū)間（如右圖），每一個區(qū)間上只顯（如右圖），每一個區(qū)間上只顯示一個面。示一個面。 因此，因此，只要在區(qū)間上任一點處，只要在區(qū)間上任一點處，找出在該處找出在該處z值最大的一個面值最大的一個面，這個區(qū)，這個區(qū)間上的每個象素就用這個面的顏色來間上的每個象素就用這個面的顏色來顯示。這就是所謂顯示。這就是所謂區(qū)間掃描線算法區(qū)

56、間掃描線算法。 區(qū)間掃描線算法使得在一條掃區(qū)間掃描線算法使得在一條掃描線上描線上每個區(qū)間只計算一次深度值，每個區(qū)間只計算一次深度值，不需要不需要Z緩沖器緩沖器。 它是把當前掃描線與各它是把當前掃描線與各多邊形多邊形在投影平面的投影的交點進行排序在投影平面的投影的交點進行排序后，使后，使掃描線分為若干子區(qū)間掃描線分為若干子區(qū)間。 因此，只要因此，只要在該區(qū)間任一點處在該區(qū)間任一點處找出在該處找出在該處 z 值最大的一個面值最大的一個面，這，這個區(qū)間上的每一個象素就用這個面?zhèn)€區(qū)間上的每一個象素就用這個面的顏色來顯示。的顏色來顯示。 當然，現(xiàn)在計算機的硬件發(fā)展很快，緩存數(shù)組當然，現(xiàn)在計算機的硬件發(fā)展

57、很快，緩存數(shù)組所耗空間已不是障礙。所耗空間已不是障礙。 PhongPhong模型的區(qū)間掃描線繪制算法，模型的區(qū)間掃描線繪制算法，CADCAD系統(tǒng)中最常用系統(tǒng)中最常用 4 4）真實感效果圖生成）真實感效果圖生成 A) A) 全局關(guān)照模型全局關(guān)照模型 B) B) 光線跟蹤光線跟蹤 C) C) 輻射度算法輻射度算法A A）整體光照明模型）整體光照明模型 簡單光簡單光照明模型和照明模型和局部光局部光照明模型，雖然可以產(chǎn)生物體的真照明模型，雖然可以產(chǎn)生物體的真實感圖象，但它們都只是處理光源直接照射物體表面的光強計算，實感圖象，但它們都只是處理光源直接照射物體表面的光強計算，不能很好的模擬光的折射、反射和

58、陰影等，也不能用來表示物體不能很好的模擬光的折射、反射和陰影等，也不能用來表示物體間的相互光照明影響。間的相互光照明影響。 而基于簡單光照明模型的光透射模型，雖然可以模擬光的折而基于簡單光照明模型的光透射模型，雖然可以模擬光的折射，但是這種折射的計算范圍很小，不能很好的模擬多個透明體射，但是這種折射的計算范圍很小，不能很好的模擬多個透明體之間的復(fù)雜光照明現(xiàn)象。之間的復(fù)雜光照明現(xiàn)象。 對于上述的這些問題，就必須要有一個更精確的光照明模型。對于上述的這些問題，就必須要有一個更精確的光照明模型。整體光照明模型就是這樣的一種模型，它是相對于局部光照明模整體光照明模型就是這樣的一種模型，它是相對于局部光

59、照明模型而言的。在現(xiàn)有的整體光照明模型中，主要有型而言的。在現(xiàn)有的整體光照明模型中，主要有光線跟蹤光線跟蹤和和輻射輻射度度兩種繪制方法。兩種繪制方法。 B B）光線跟蹤算法的基本思想）光線跟蹤算法的基本思想 光線跟蹤算法是真實感圖形學(xué)中的主要算法之一，算法具有原光線跟蹤算法是真實感圖形學(xué)中的主要算法之一，算法具有原理簡單、實現(xiàn)方便和能夠生成各種逼真的視覺效果等優(yōu)點。理簡單、實現(xiàn)方便和能夠生成各種逼真的視覺效果等優(yōu)點。 在真實感圖形學(xué)對光線跟蹤算法的研究中，在真實感圖形學(xué)對光線跟蹤算法的研究中，Whitted提出了第提出了第一個整體光照模型，并給出一般性光線跟蹤算法的范例，綜合考慮一個整體光照模

60、型，并給出一般性光線跟蹤算法的范例，綜合考慮了光的反射、折射透射、陰影等。了光的反射、折射透射、陰影等。 光線跟綜過程示意圖 簡單光透射模型把透射光分為理想漫透射和規(guī)則透射。簡單光透射模型把透射光分為理想漫透射和規(guī)則透射。 由光源發(fā)出的光稱為由光源發(fā)出的光稱為直接光直接光，物體對直接光的反射或折，物體對直接光的反射或折射稱為射稱為直接反射直接反射和和直接折射直接折射。 把物體表面間對光的反射和折射稱為把物體表面間對光的反射和折射稱為間接光間接光，間接反射，間接反射，間接折射。間接折射。這是光線在物體間的傳播方式，是光線跟蹤算法這是光線在物體間的傳播方式，是光線跟蹤算法的基礎(chǔ)。的基礎(chǔ)。 由光源發(fā)