華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件

計(jì)算機(jī)圖形學(xué)基礎(chǔ)算法1、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示

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

三維幾何形體的表達(dá)現(xiàn)實(shí)生活中的產(chǎn)品都是由不同類型的三維(3D)幾2計(jì)算機(jī)中表示形體幾何模型通常用：

線框模型表面模型實(shí)體模型線框模型和表面模型保存的三維形體信息都不完整。只有實(shí)體模型才能夠完整地、無(wú)歧義地表示三維形體。

計(jì)算機(jī)中表示形體幾何模型通常用：3點(diǎn)用三維坐標(biāo)表示，是最基本的元素邊是形體相鄰面的交界，可為空間直線或曲線環(huán)是有序、有向的封閉邊界，外環(huán)僅一個(gè)，逆時(shí)針?lè)较?，?nèi)環(huán)可有可無(wú)，也可多個(gè)，方向順時(shí)針。面是一個(gè)單連通區(qū)域，可以是平面或曲面，由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)組成；面的方向由面的法矢決定，法矢向外為正向面。基本概念及定義點(diǎn)用三維坐標(biāo)表示，是最基本的元素基本概念及定義4實(shí)體是由若干個(gè)面組成的閉包，實(shí)體的邊界是有限個(gè)面的集合。形體表面上任一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圓，即圍繞該點(diǎn)的形體鄰域在二維空間中可構(gòu)成一個(gè)單連通域，我們把滿足該定義的形體稱為正則形體。否則為非正則形體，如存在懸面、懸邊的長(zhǎng)方體為非正則形體。

實(shí)體是由若干個(gè)面組成的閉包，實(shí)體的邊界是有限個(gè)面的集合。形體5線框模型線框模型用頂點(diǎn)和棱邊表示三維形體，其棱邊可以為直線、圓弧、二次曲線及樣條曲線組成。

線框模型線框模型用頂點(diǎn)和棱邊表示三維形體，其棱邊可以為直線、6線框模型在計(jì)算機(jī)內(nèi)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)：

頂點(diǎn)表：記錄各頂點(diǎn)坐標(biāo)值；

棱線表：記錄每條棱線所連接的兩頂點(diǎn)。classPOINTclassEDGE{{doublev[3];//坐標(biāo)值intstart_point_no;//邊的起點(diǎn)intpointtype;//點(diǎn)的屬性intend_point_no;//邊的終點(diǎn)

CURVEcur；//邊方程定義；

…………..

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

2）含有指向頂點(diǎn)表指針的邊表，用來(lái)為多邊形的每條邊標(biāo)識(shí)頂點(diǎn)；

3）面表有指向邊表的指針，用來(lái)為每個(gè)表面標(biāo)識(shí)其組成邊。1）頂點(diǎn)坐標(biāo)值存放在頂點(diǎn)表中；10classPOINTclassEDGEclassFACE{{{

同線框模型同線框模型intedge_num；//邊數(shù)

int*edge_no;//邊鏈表

intface_type;//面類型

SURFACEsur；//面方程

………….………….…………….}}}classPOINTclassE11

表面模型唯一沒(méi)有解決的問(wèn)題是形體究竟在表面的哪一側(cè)，因而在物性計(jì)算、有限元分析等應(yīng)用中，表面模型在形體的表示上仍然缺乏完整性。表面模型可以滿足面面求交，線面消隱、明暗處理和數(shù)控加工的要求。表面模型的特點(diǎn)表面模型唯一沒(méi)有解決的問(wèn)題是形體究竟在表面的哪一側(cè)，12實(shí)體模型為了解決形體存在于表面的哪一側(cè)的問(wèn)題，可采用實(shí)體模型來(lái)描述三維立體在表面模型的基礎(chǔ)上可用三種方法來(lái)定義表面的哪一側(cè)存在實(shí)體。1）給出實(shí)體存在一側(cè)的一點(diǎn)；2）直接用表面的外法矢來(lái)指明實(shí)體存在的一側(cè)；3）用有向棱邊隱含地表示表面的外法矢方向，該方法為CAD系統(tǒng)廣泛采用。

（思考：為什么不直接用法矢？）實(shí)體模型為了解決形體存在于表面的哪一側(cè)的問(wèn)題，可采用實(shí)13用有向棱邊隱含地表示表面的外法矢方向時(shí)，規(guī)定有向棱邊按右手法則取向：沿著閉合的棱邊所得的方向與表面外法矢方向一致。思考：相鄰兩個(gè)面的公共棱邊的方向不會(huì)矛盾嗎？

（有矛盾，CAD系統(tǒng)中增加“環(huán)”的定義解決矛盾）classPOINTclassEDGEclassFACE{{{

同線框模型同線框模型intedge_num；//邊數(shù)

EDGE*edge;//邊鏈表

intface_type;//面類型

SURFACEsur；//面方程

………….………….………….}}}數(shù)據(jù)結(jié)構(gòu)如下：用有向棱邊隱含地表示表面的外法矢方向時(shí)，規(guī)定有向棱邊14根據(jù)實(shí)體模型，可以進(jìn)行物性計(jì)算（如體積、質(zhì)量，慣量）、有限元分析等應(yīng)用。從前面的實(shí)體模型可知，本質(zhì)上我們?nèi)匀徊捎昧诵误w的邊界表面的數(shù)學(xué)描述代替實(shí)體描述，并非真正描述了實(shí)體內(nèi)部屬性。這種典型的邊界表面描述方法通常稱為實(shí)體的邊界表達(dá)方法（BREP），這在后面內(nèi)容將詳細(xì)介紹。根據(jù)實(shí)體模型，可以進(jìn)行物性計(jì)算（如體積、質(zhì)量，慣量）15線框、表面與實(shí)體模型的比較模型表示應(yīng)用范圍局限性二維線框畫二維線框圖（工程圖）無(wú)法觀察參數(shù)的變化，不可能產(chǎn)生有實(shí)際意義的形體三維線框畫二、三維線框圖不能表示實(shí)體、圖形會(huì)有二義性表面模型藝術(shù)圖形、形體表面的顯示、數(shù)控加工不能表示實(shí)體實(shí)體模型物性計(jì)算、有限元分析用集合運(yùn)算構(gòu)造形體只能產(chǎn)生正則形體抽象形體的層次較低線框、表面與實(shí)體模型的比較模型表示應(yīng)用范圍局限性二維線框畫二161、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示

6、圖形學(xué)的其它應(yīng)用1、三維形體的計(jì)算機(jī)表達(dá)17圖形變換在CAD系統(tǒng)中，經(jīng)常將顯示的形體進(jìn)行放大縮小、旋轉(zhuǎn)、平移等，以便用戶更清楚地觀察或編輯操作。實(shí)現(xiàn)形體放大縮小、旋轉(zhuǎn)、平移的方法是圖形變換。在CAD系統(tǒng)中，常用的圖形變換有平移、旋轉(zhuǎn)、比例、投影等變換。圖形變換在CAD系統(tǒng)中，經(jīng)常將顯示的形體進(jìn)行放大縮小18二維圖形變換二維圖形變換19華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件20三維圖形變換三維圖形變換21簡(jiǎn)單幾何形體的圖形變換應(yīng)用舉例式中：T為所要進(jìn)行的圖形變換矩陣

假定一六面體ABCDEFGH各點(diǎn)的坐標(biāo)分別為（x1,y1,z1）,…..,(x8,y8,z8)，則經(jīng)過(guò)圖形變換后的坐標(biāo)為：簡(jiǎn)單幾何形體的圖形變換應(yīng)用舉例式中：T為所要進(jìn)行的圖形變換矩22圖形的顯示流程圖形的顯示流程231、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示

6、圖形學(xué)的其它應(yīng)用1、三維形體的計(jì)算機(jī)表達(dá)241）網(wǎng)格剖分算法目前三維幾何圖形的顯示算法均是基于三角形網(wǎng)格，且算法不斷被固化到硬件中（如顯卡、圖形加速卡等），如：三維游戲及動(dòng)畫復(fù)雜場(chǎng)景渲染顯示

CAD模型顯示有限元分析科學(xué)數(shù)據(jù)可視化電影、戰(zhàn)場(chǎng)仿真1）網(wǎng)格剖分算法目前三維幾何圖形的顯示算法均是基于25A）平面上的三角剖分任意多邊形的三角剖分平面點(diǎn)集的三角剖分邊界離散網(wǎng)格生成網(wǎng)格后處理分析、顯示軟件一般處理過(guò)程A）平面上的三角剖分任意多邊形的三角剖分平面點(diǎn)集的三角剖分邊26B）參數(shù)曲面的三角剖分為了顯示三維零件形體，CAD系統(tǒng)內(nèi)部提供參數(shù)曲面的三角剖分算法，對(duì)形體的每一個(gè)表面都進(jìn)行三角剖分，如圖所示。B）參數(shù)曲面的三角剖分為了顯示三維零件形體，CAD系27經(jīng)過(guò)三角剖分處理，三維零件形體表面都生成并記錄了完整的多面體離散數(shù)據(jù)（即顯示數(shù)據(jù)）CAD系統(tǒng)中的顯示算法（線框圖、消隱圖、真實(shí)感顯示圖等）大多數(shù)都是基于該多面體離散數(shù)據(jù)的算法處理。經(jīng)過(guò)三角剖分處理，三維零件形體表面都生成并記錄了完整28C)空間散亂點(diǎn)集的三角剖分（曲面重建）C)空間散亂點(diǎn)集的三角剖分（曲面重建）29???合理分割數(shù)據(jù)并準(zhǔn)確重建原產(chǎn)品特征約束模型仍存在困難???快速重建與產(chǎn)品外形拓?fù)湟恢碌木W(wǎng)格???合理分割數(shù)???快速重建與產(chǎn)品30局部網(wǎng)格基于三維Delaunay的構(gòu)造重建的網(wǎng)格拓?fù)渫a(chǎn)品局部外形拓?fù)湟恢戮植奎c(diǎn)集的三維Delaunay剖分得到對(duì)應(yīng)的Voronoi圖連接Voronoi區(qū)中心點(diǎn)得到局部構(gòu)造網(wǎng)格在八叉樹點(diǎn)集中快速得到繞中心點(diǎn)的鄰域點(diǎn)集局部網(wǎng)格基于三維Delaunay的構(gòu)造重建的網(wǎng)格拓?fù)渫a(chǎn)品局31D)有限元單元網(wǎng)格三角剖分有限元網(wǎng)格生成技術(shù)發(fā)展到現(xiàn)在,已經(jīng)出現(xiàn)了大量的不同實(shí)現(xiàn)方法。當(dāng)前廣泛使用的Delaunay三角化、推進(jìn)波前法和八叉樹方法等。D)有限元單元網(wǎng)格三角剖分有限元網(wǎng)格生成技術(shù)發(fā)展到現(xiàn)在,已32華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件33三維幾何數(shù)據(jù)壓縮是指對(duì)描述三維場(chǎng)景的模型數(shù)據(jù)進(jìn)行壓縮,以便于模型數(shù)據(jù)的存儲(chǔ)和網(wǎng)絡(luò)傳輸,在分布式虛擬現(xiàn)實(shí)、協(xié)同應(yīng)用、多用戶視頻游戲、模型數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)和傳輸有著非常重要的意義。事實(shí)上三維圖形的信息容量有時(shí)也非常大，給存儲(chǔ)和傳輸帶來(lái)了嚴(yán)重的障礙，必須進(jìn)行壓縮編碼才適應(yīng)現(xiàn)有的網(wǎng)絡(luò)傳輸技術(shù)，而且在一些需實(shí)時(shí)處理的應(yīng)用場(chǎng)合更需要壓縮技術(shù)的支持。2）三角形網(wǎng)格壓縮三維幾何數(shù)據(jù)壓縮是指對(duì)描述三維場(chǎng)景的模型數(shù)據(jù)進(jìn)34單分辨率模型的幾何數(shù)據(jù)壓縮單分辨率模型的幾何數(shù)據(jù)壓縮是指對(duì)物體的一種層次細(xì)節(jié)的多邊形網(wǎng)格表示形式的幾何數(shù)據(jù)進(jìn)行壓縮。使之生成：三角形條帶、扇形、網(wǎng)格每個(gè)三角形獨(dú)立地由其3個(gè)頂點(diǎn)的9個(gè)坐標(biāo)來(lái)表述,如果用浮點(diǎn)數(shù),則需要36個(gè)字節(jié)來(lái)描述一個(gè)三角形(暫且不考慮顏色、法向、紋理坐標(biāo)等屬性數(shù)據(jù))；這種表述方案使得每個(gè)頂點(diǎn)約需被描述6次,浪費(fèi)了大量存儲(chǔ)空間。一種改進(jìn)的方案是頂點(diǎn)和三角形分開表示，每個(gè)頂點(diǎn)用其3個(gè)浮點(diǎn)數(shù)表示的位置坐標(biāo)確定;而每個(gè)三角形,則用三角形描述表來(lái)表示,其中每個(gè)表項(xiàng)僅包含該三角形的3個(gè)頂點(diǎn)序號(hào).這使得存儲(chǔ)空間得到很大程度的節(jié)省。

三角形條帶的引入進(jìn)一步減少了不必要的頂點(diǎn)傳輸：兩個(gè)相鄰的三角形公用一條邊,那么從第二個(gè)三角形開始,一個(gè)新頂點(diǎn)的加入和其前一個(gè)三角形的一條邊即可構(gòu)成另一三角形,這使得每個(gè)頂點(diǎn)最多必須傳送兩次。單分辨率模型的幾何數(shù)據(jù)壓縮單分辨率模型的幾何數(shù)據(jù)壓縮是指對(duì)物35該技術(shù)有利于緩解圖形顯示硬件傳輸瓶頸，加速顯示速度該技術(shù)有利于緩解圖形顯示硬件傳輸瓶頸，加速顯示速度36多分辨率模型的壓縮是面向多分辨率模型的壓縮方法，多分辨率模型可分為：離散多分辨率模型連續(xù)多分辨率模型離散多分辨率模型是對(duì)復(fù)雜的三角形網(wǎng)格通過(guò)簡(jiǎn)化算法逐步得到不同細(xì)節(jié)層次的多個(gè)三角網(wǎng)格模型連續(xù)多分辨率模型則是通過(guò)一種緊湊的模型表示方法,可生成任意多個(gè)不同分辨率的模型（不介紹）。多分辨率模型的幾何數(shù)據(jù)壓縮多分辨率模型的壓縮是面向多分辨率模型的壓縮方37離散多分辨率模型的壓縮離散多分辨率模型是對(duì)復(fù)雜的三角形網(wǎng)格經(jīng)過(guò)一系列簡(jiǎn)化操作得到了多個(gè)不同分辨率的多邊形網(wǎng)格模型。這種簡(jiǎn)化算法通過(guò)對(duì)三角形網(wǎng)格施以局部的變化而逐步得到不同的細(xì)節(jié)層次(LOD)，為了保證對(duì)原始網(wǎng)格的足夠近似,每個(gè)簡(jiǎn)化步驟都須得到控制。離散多分辨率模型的壓縮離散多分辨率模型是對(duì)復(fù)雜38在分布式圖形應(yīng)用中,針對(duì)多分辨率模型,累進(jìn)傳輸是一個(gè)非常有效的傳送措施。該方案的思想是首先傳輸LOD層次中一個(gè)最低分辨率的模型，然后在繪制操作開始的同時(shí)傳送一系列的細(xì)化操作（類似JPGE2000思想）；逐步細(xì)化的LOD顯示可以與更加細(xì)化LOD操作信息的傳送同步進(jìn)行,減少了操作人員的等待時(shí)間。但是由于累進(jìn)傳輸對(duì)全局狀態(tài)設(shè)置的要求以及累進(jìn)傳輸受到傳輸速度的制約,使得累進(jìn)傳輸?shù)难芯窟M(jìn)展較為緩慢。隨著研究的逐步深入，會(huì)使得幾何壓縮的算法更加成熟和先進(jìn)，更能滿足網(wǎng)絡(luò)幾何圖形傳輸、分布式虛擬環(huán)境、電子購(gòu)物等的應(yīng)用需求,進(jìn)一步推動(dòng)計(jì)算機(jī)圖形學(xué)向前發(fā)展。在分布式圖形應(yīng)用中,針對(duì)多分辨率模型,累進(jìn)傳39華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件403）相交測(cè)試與碰撞測(cè)試在計(jì)算機(jī)圖形學(xué)、CAD、CAE中經(jīng)常遇到相交測(cè)試盒碰撞測(cè)試（運(yùn)動(dòng)物體）。如鼠標(biāo)拾取，視窗裁剪、曲面求交、光線跟蹤、布爾運(yùn)算、裝配干涉校驗(yàn)、動(dòng)畫漫游、運(yùn)動(dòng)碰撞、機(jī)器人與機(jī)床刀具的軌跡規(guī)劃等。尤其對(duì)較大規(guī)模數(shù)據(jù)的模型而言，相交測(cè)試和碰撞測(cè)試的速度對(duì)系統(tǒng)影響很大。3）相交測(cè)試與碰撞測(cè)試在計(jì)算機(jī)圖形學(xué)、CAD、CAE中經(jīng)常遇41基本定義：射線：r(t)=o+t·dO:原點(diǎn)，d：射線方向T：參數(shù)基本定義：射線：r(t)=o+t·d42軸對(duì)齊包容盒（矩形盒）：通常稱：AABB表面平行于坐標(biāo)面有向包容盒：簡(jiǎn)稱：OBB即任意方向的AABB往往由一個(gè)中心，三個(gè)單位矢量和三個(gè)半邊長(zhǎng)定義包容盒軸對(duì)齊包容盒（矩形盒）：有向包容盒：包容盒43離散有向多面體簡(jiǎn)稱k－DOPn3n1n2n4s1d1maxd1min由k/2（k為偶數(shù)）個(gè)規(guī)一化法矢ni定義，每個(gè)ni有兩個(gè)標(biāo)量值dimin和dimax，由三元組（ni，dimin，dimax）描述一個(gè)平板層Si，所有平板層的交集是k－DOP的實(shí)際體積，上圖為8－DOP。離散有向多面體n3n1n2n4s1d1maxd1min由k/44包容盒的創(chuàng)建：AABB：直接比較所有多面體（前面的離散多面體）頂點(diǎn)坐標(biāo)即可得k－DOP：是AABB得擴(kuò)展，將所有多面體頂點(diǎn)坐標(biāo)投影到k－DOP的每條法線ni上，然后保留dimin、dimax，所有這些值定義一個(gè)最小的k－DOP。球體包容盒：計(jì)算比較麻煩。較為簡(jiǎn)單的方法是先計(jì)算AABB，再計(jì)算AABB的中心，以此為球心，球心到最遠(yuǎn)頂點(diǎn)的距離即為半徑。其它更好更優(yōu)的算法可查資料。顯然，最遠(yuǎn)距離兩點(diǎn)最為球的直徑是最優(yōu)解，關(guān)鍵是快速搜索。包容盒的創(chuàng)建：AABB：直接比較所有多面體（前面的離散多面體45OBB：計(jì)算方法較多，較繁瑣。方法之一是：1）計(jì)算凸包2）計(jì)算凸包質(zhì)心3）計(jì)算協(xié)方差矩陣的特征向量4)其特征向量即為OBB三個(gè)方向5）向三個(gè)方向投影即可求出半長(zhǎng)值A(chǔ)ABB、圓球包容盒比較粗糙（分塊多包容盒改進(jìn)），算法簡(jiǎn)單K－DOP比AABB更緊致，但計(jì)算較多OBB則較k－DOP更優(yōu)選用何種包容盒視復(fù)雜度而定。OBB：計(jì)算方法較多，較繁瑣。方法之一是：AABB、圓球包容46測(cè)試算法實(shí)現(xiàn)基本原則：1）盡可能用最簡(jiǎn)單算法排除或確定相交情形；2）充分利用前一次計(jì)算結(jié)果；3）如果使用了多種測(cè)試，可以嘗試改變內(nèi)部順序，或許會(huì)有意外收效；4）盡量避免復(fù)雜計(jì)算（如sin，cos，開方等）5）盡量降低維數(shù)，使問(wèn)題簡(jiǎn)化；6）相交測(cè)試復(fù)雜時(shí)，先用包容盒排除7）養(yǎng)成計(jì)時(shí)比較的習(xí)慣，采用真實(shí)數(shù)據(jù)及計(jì)算環(huán)境8）確保計(jì)算魯棒性測(cè)試算法實(shí)現(xiàn)基本原則：47常用相交測(cè)試算法：射線——球體測(cè)試；射線——長(zhǎng)方體測(cè)試；線段——長(zhǎng)方體測(cè)試；射線——三角形測(cè)試；射線——多邊形測(cè)試；平面——長(zhǎng)方體測(cè)試；三角形——三角形測(cè)試；三角形——長(zhǎng)方體測(cè)試；BV——BV測(cè)試（AABB、K－DOP、球、OBB兩兩之間）……………..。常用相交測(cè)試算法：48碰撞處理分為：碰撞測(cè)試、碰撞確定、碰撞反應(yīng)碰撞處理在游戲中是最重要的算法之一，目前算法很多，文獻(xiàn)很多，目前沒(méi)有一個(gè)算法能夠?qū)λ星樾味加行У奶幚硭惴ā３Ｒ?jiàn)測(cè)試方法有：1）用射線測(cè)試2）BSP樹測(cè)試3）一般層次構(gòu)造測(cè)試4）k－DOP樹測(cè)試5）OBB樹測(cè)試（較K－DOP方法好）。。。。。。一般剛體處理簡(jiǎn)單一些，柔軟物體（液體、衣物）處理更難。碰撞處理分為：碰撞測(cè)試、碰撞確定、碰撞反應(yīng)491、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示

6、圖形學(xué)的其它應(yīng)用1、三維形體的計(jì)算機(jī)表達(dá)50顯示器顯示原理常規(guī)顯示器上的圖形由熒光屏的點(diǎn)陣組成，電子束按行列次序掃描點(diǎn)矩陣，并由顯示內(nèi)容來(lái)控制所掃描的點(diǎn)是否發(fā)亮，每掃描一遍稱為一幀。熒光屏上每一點(diǎn)稱象素（Pixel）。每個(gè)象素都對(duì)應(yīng)于Buffer中的一個(gè)存儲(chǔ)單元，里面存放著該象素的顯示亮度值。象素的亮度值控制電子束對(duì)熒光屏的轟擊強(qiáng)度，象素在幀緩存寄存器中的位置編碼控制電子束的偏轉(zhuǎn)位置。分辨率（Resolution）是光柵掃描顯示設(shè)備最重要的指標(biāo)顯示器用于顯示字符、圖形（觸摸顯示屏還可作為輸入設(shè)備）顯示器顯示原理常規(guī)顯示器上的圖形由熒光屏的點(diǎn)陣組成，電子束按51計(jì)算機(jī)圖形的具體應(yīng)用范圍很廣，但是從基本的處理技術(shù)看只有兩類：線條類：如工程圖、地圖、曲線圖表等；明暗圖類（與照片相似）：為了生成圖形，首先要有原始數(shù)據(jù)或數(shù)學(xué)模型，如工程人員構(gòu)思的機(jī)械零件模型，飛機(jī)的總體方案模型，地形航測(cè)的判讀數(shù)據(jù)等等。這些數(shù)字化的輸入經(jīng)過(guò)計(jì)算機(jī)處理后變成圖形輸出。三維圖形的線框顯示屬于第一類三維圖形的濃淡圖及真實(shí)感顯示是第二類計(jì)算機(jī)圖形的具體應(yīng)用范圍很廣，但是從基本的處理技術(shù)看只有兩類52經(jīng)過(guò)三角剖分處理，計(jì)算機(jī)內(nèi)部增加了完整的三維形體逼近多面體近似表達(dá)數(shù)據(jù)結(jié)構(gòu)（即表面全部由以三角形為主的多邊形構(gòu)成，如右下圖所示）。在線框顯示模型中，為顯示方便，分別對(duì)邊界邊和內(nèi)部邊作標(biāo)識(shí)。顯示方法：遍歷所有多邊形網(wǎng)格的點(diǎn)表和邊表。兩種顯示狀態(tài)可以任選：

a）僅顯示輪廓邊（內(nèi)部邊不顯示）

b）顯示所有離散多邊形特點(diǎn)：簡(jiǎn)單快捷，但有二義性。1）線框圖顯示算法經(jīng)過(guò)三角剖分處理，計(jì)算機(jī)內(nèi)部增加了完整的三維形體逼近53線框顯示往往導(dǎo)致理解的二義性，如下圖。為消除二義性，CAD系統(tǒng)經(jīng)常采用消除遮擋的不可見(jiàn)線或面的顯示算法。習(xí)慣上稱作消除隱藏線和隱藏面，簡(jiǎn)稱消隱。線框顯示往往導(dǎo)致理解的二義性，如下圖。54消隱算法的分類：消隱的對(duì)象是三維物體，消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)有關(guān)。2）線框消隱顯示算法消隱算法的分類：消隱的對(duì)象是三維物體，消隱結(jié)果與觀察物體有關(guān)55

(c)多面體的輪廓分類A）凸多面體消隱算法設(shè)V為由視點(diǎn)出發(fā)的觀察向量，N為某多邊形面的法向量。若V·N>0，稱該多邊形為后向面。若V·N<0，稱該多邊形為前向面。如右圖c，后向面總是看不見(jiàn)的。

(a)前向面

(b)后向面d)凸多面體因此，對(duì)凸多面體（右圖d）消隱，僅需判斷前向面(即V·N<0)，畫出所有前向面的各棱邊即可。為加速計(jì)算，將凸多面體變換，使觀察方向V與Z軸方向一致，則僅判斷前向面的法矢分量Nz<0即可Vn(c)多面體的輪廓分類A）凸多面體消隱算法(56

//假設(shè)已知凸多面體的面—邊—頂點(diǎn)表Begin

對(duì)凸多面體變換使V與Z同向；for（所有的面）

{計(jì)算該面法矢的z分量Nz；

if（Nz>0）{for(該面所有棱邊）畫出棱邊；

}}End凸多面體消隱算法如下：Vnizxy//假設(shè)已知凸多面體的面—邊—頂點(diǎn)表凸多面體消隱算57B）任意多面體消隱算法算法思路：

1）為運(yùn)算方便，對(duì)視錐以外的物體應(yīng)先行裁剪過(guò)慮，以減少不必要的運(yùn)算。

2）后向面上的所有棱邊都不可見(jiàn)

3）對(duì)每一個(gè)前向面的所有棱邊判斷可見(jiàn)性，即判斷面對(duì)線的遮擋關(guān)系。在判斷面與線的遮擋關(guān)系過(guò)程中，要反復(fù)地進(jìn)行線線、線面之間的求交運(yùn)算，因此求交計(jì)算速度將是關(guān)鍵。線面求交線線求交B）任意多面體消隱算法線面求交線線求58某一直線段對(duì)任一平面的遮擋關(guān)系判斷算法：

(1)若線段兩端點(diǎn)及視點(diǎn)在給定平面同側(cè)（圖a），線段可見(jiàn)，轉(zhuǎn)7

(2)若線段投影與平面投影的包圍盒無(wú)交（圖b），線段可見(jiàn)，轉(zhuǎn)7圖a視點(diǎn)與線段同側(cè)

圖b包圍盒不交某一直線段對(duì)任一平面的遮擋關(guān)系判斷算法：圖a視點(diǎn)與線段59(3)求直線與平面的交點(diǎn)。若無(wú)交點(diǎn)，轉(zhuǎn)4；否則，交點(diǎn)在線段內(nèi)部或外部，則判斷

a）若交點(diǎn)在線段內(nèi)部，交點(diǎn)將線段分成兩段，與視點(diǎn)同側(cè)的一段可見(jiàn)，轉(zhuǎn)7；剩余另一段在視點(diǎn)異側(cè)，轉(zhuǎn)4繼續(xù)判斷。

b）若交點(diǎn)在線段外部，轉(zhuǎn)4繼續(xù)判斷。

(4)求剩下線段的投影與平面邊界投影的所有交點(diǎn)根據(jù)交點(diǎn)在原直線方程的參數(shù)值求出Z值(即深度)若無(wú)交點(diǎn)，轉(zhuǎn)5。

(3)求直線與平面的交點(diǎn)。若無(wú)交點(diǎn)，轉(zhuǎn)4；60

(5)以上所求得的各交點(diǎn)將線段的投影分成若干段，求出第一段中點(diǎn)。

(6)若第一段中點(diǎn)在平面的投影內(nèi)，則相應(yīng)的段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值進(jìn)行判斷。（見(jiàn)圖d）(7)當(dāng)前循環(huán)結(jié)束，各可見(jiàn)段進(jìn)入下一個(gè)面的比較，直至所有面比較完畢。圖d分段交替取值(5)以上所求得的各交點(diǎn)將線段的投影分成若干段，求出第一段61

上述算法為一條邊，一個(gè)面的情況，對(duì)多條邊、多個(gè)面則通過(guò)循環(huán)嵌套實(shí)現(xiàn)。如果消隱對(duì)象有N條棱，當(dāng)N很大時(shí)，用兩兩求交的方法這個(gè)工作量是很大的O（N2）。為了提高算法的效率，需要設(shè)法減少求交的工作量，因此相交測(cè)試是關(guān)鍵。如上述算法中僅需對(duì)可見(jiàn)子線段與其余平面進(jìn)行類似的可見(jiàn)性判斷，對(duì)不可見(jiàn)線段不予計(jì)算。

不同消隱算法的關(guān)鍵在于加速計(jì)算的策略和方法不同?，F(xiàn)在的商用CAD系統(tǒng)消隱算法正確率不能達(dá)到100%，速度也有待提高。重點(diǎn)在于線段可見(jiàn)性的判斷速度和正確性。上述算法為一條邊，一個(gè)面的情況，對(duì)多條邊、多個(gè)面則62對(duì)CAD圖形來(lái)說(shuō)，需要顯示輪廓，而非內(nèi)部三角形邊界，為此必須對(duì)前面的算法修正：1）三角剖分時(shí)，標(biāo)識(shí)是否內(nèi)部邊界；2）計(jì)算是否輪廓邊界；3）內(nèi)部邊、輪廓邊不必計(jì)算消隱；4）對(duì)其它邊進(jìn)行正常消隱計(jì)算。對(duì)CAD圖形來(lái)說(shuō)，需要顯示輪廓，而非內(nèi)部三角63C）畫家算法原理

1)把屏幕置成背景色;2）物體的各個(gè)面按其離視點(diǎn)的遠(yuǎn)近進(jìn)行排序，排序結(jié)果存在一張深度優(yōu)先級(jí)表中;3）按照從表頭到表尾的順序逐個(gè)用背景色填充繪制各個(gè)面，用指定顏色繪制面的邊界。由于后顯示的圖形取代先顯示的畫面，而后顯示的圖形所代表的面離視點(diǎn)更近，所以由遠(yuǎn)及近的繪制各面，就相當(dāng)于消除隱藏面。這與油畫作家作畫的過(guò)程類似，先畫遠(yuǎn)景，再畫中景，最后畫近景。由于這個(gè)原因，該算法習(xí)慣上稱為畫家算法或列表優(yōu)先算法。

這種算法必須首先建立深度優(yōu)先級(jí)表。C）畫家算法原理64華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件65遮擋關(guān)系判斷示意圖

畫家算法原理簡(jiǎn)單，關(guān)鍵是如何對(duì)場(chǎng)景中物體按深度排序。其缺點(diǎn)是只能處理互不相交的面，而且深度優(yōu)先級(jí)表中面的順序可能出錯(cuò)。

在兩個(gè)面相交，三個(gè)以上的面重疊的情形，用任何排序方法都不能排出正確的序。這時(shí)只能把有關(guān)的面進(jìn)行分割后再排序。

畫家算法既可用于線框圖消隱，也可用于簡(jiǎn)單的濃淡圖繪制（只需按指定顏色繪制多邊形，不必畫邊界）遮擋關(guān)系判斷示意圖畫家算法原理簡(jiǎn)單，關(guān)鍵是如何661、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示6、圖形學(xué)的其它應(yīng)用1、三維形體的計(jì)算機(jī)表達(dá)67真實(shí)感顯示

1）光照效果影響因素2）簡(jiǎn)單效果的濃淡圖生成3）一般性效果圖形生成4）真實(shí)感效果圖生成5）紋理映射真實(shí)感顯示1）光照效果影響因素681）光照效果影響因素當(dāng)光照射到物體表面時(shí)，物體對(duì)光會(huì)發(fā)生反射、透射、吸收、衍射、折射和干涉。

被物體吸收的部分轉(zhuǎn)化為熱。

顏色是人對(duì)光的生理反映，反射、透射的光進(jìn)入人的視覺(jué)系統(tǒng)，使我們能看見(jiàn)物體的顏色。為模擬這一現(xiàn)象，我們建立一些數(shù)學(xué)模型來(lái)替代復(fù)雜的物理模型。這些模型就稱為明暗效應(yīng)模型或者光照明模型。思考：我們所見(jiàn)物體的顏色是怎樣形成的？影響觀察物體顏色的主要因素有哪些？1）光照效果影響因素當(dāng)光照射到物體表面時(shí)，物69在不考慮人的生理因素的情況下，物體的顏色與光源顏色、物體表面物理特性、表面粗糙度、周邊環(huán)境等因素有關(guān)。在正常的情況下，光沿著直線傳播，當(dāng)光遇到介質(zhì)不同的表面時(shí)，會(huì)產(chǎn)生反射和折射現(xiàn)象，而且在反射和折射的時(shí)候，它們遵循反射定律和折射定律。在不考慮人的生理因素的情況下，物體的顏色與光源70研究光照模型的目的：確定物體表面的每一個(gè)多邊形或者多邊形中的每一個(gè)點(diǎn)的顏色，以便實(shí)現(xiàn)具有真實(shí)感顯示效果的三維形體渲染繪制。研究光照模型的目的：確定物體表面的每一個(gè)多邊71A）單顏色填充多邊形算法思路：根據(jù)多面體表面的平面法矢決定顏色值，直接調(diào)用OpenGL的多邊形填充算法即可。算法簡(jiǎn)單，但輪廓分明，各多邊形之間過(guò)渡不光滑。2）簡(jiǎn)單效果的濃淡圖生成A）單顏色填充多邊形2）簡(jiǎn)單效果的濃淡圖生成72B）Gouraud模型算法思想：為使多邊形邊界之間光滑顯示，先計(jì)算多邊形各頂點(diǎn)光強(qiáng)，后通過(guò)雙線性插值，計(jì)算多邊形內(nèi)各點(diǎn)光強(qiáng)。能保證多邊形邊界顏色的連續(xù)性，但高光模糊，有時(shí)出現(xiàn)過(guò)亮或過(guò)暗條紋（即馬赫效應(yīng)）。

計(jì)算較為簡(jiǎn)單，OpenGL算法已實(shí)現(xiàn)硬件加速。B）Gouraud模型算法思想：為使多邊形73算法步驟：For（每一個(gè)三角形）{1)計(jì)算多邊形頂點(diǎn)的平均法向；2)根據(jù)基本光照模型計(jì)算頂點(diǎn)的平均光強(qiáng)；3)通過(guò)線性插值，計(jì)算多邊形的邊上的各點(diǎn)光強(qiáng)；4)通過(guò)線性插值，計(jì)算多邊形內(nèi)部各點(diǎn)的光強(qiáng)。}算法步驟：For（每一個(gè)三角形）743）一般性效果圖形生成簡(jiǎn)單光照明模型--Phong模型濃淡圖繪制算法實(shí)現(xiàn)A）理想漫反射B）鏡面反射

C）環(huán)境光

D）

Phong光照明模型A）Z緩沖器(Z-Buffer)算法

B）掃描線算法

C）區(qū)間掃描線算法

3）一般性效果圖形生成簡(jiǎn)單光照明模型--Phong模型濃淡圖75簡(jiǎn)單光照明模型--Phong模型

簡(jiǎn)單光照明模型模擬物體表面對(duì)光的反射作用。光源被假定為點(diǎn)光源，反射作用被細(xì)分為鏡面反射(SpecularReflection)和漫反射(DiffuseReflection)。簡(jiǎn)單光照明模型只考慮物體對(duì)直接光照的反射作用，而物體間的光反射作用，只用環(huán)境光(AmbientLight)來(lái)表示。簡(jiǎn)單光照明模型--Phong模型簡(jiǎn)單光照明模76不妨設(shè)：

入射光強(qiáng)為Il

物體表面上點(diǎn)P的法向?yàn)镹

從點(diǎn)P指向光源的向量為L(zhǎng)

兩者間的夾角為圖

漫反射A）理想漫反射當(dāng)光源來(lái)自一個(gè)方向時(shí)，漫反射光均勻向各方向傳播，與視點(diǎn)無(wú)關(guān)，它是由表面的粗糙不平引起的，因而可假定漫反射光的空間分布是均勻的。p不妨設(shè)：圖漫反射A）理想漫反射p77如果Il表示點(diǎn)光源的強(qiáng)度，kd表示物體表面漫反射系數(shù)，則漫反射方程可描述為：

(0≤≤若N為物體表面的單位法向量，L為物體表面上一點(diǎn)指向光源的單位矢量，則：

如果有多個(gè)光源，則光強(qiáng)度計(jì)算式為：圖

漫反射如果Il表示點(diǎn)光源的強(qiáng)度，kd表示物體表面漫反78B）鏡面反射

對(duì)于理想鏡面，反射光集中在一個(gè)方向，并遵守反射定律。

對(duì)一般的光滑表面，反射光集中在一個(gè)范圍內(nèi)，且由反射定律決定的反射方向光強(qiáng)最大。

圖

鏡面反射光因此，對(duì)于同一點(diǎn)來(lái)說(shuō)，從不同位置所觀察到的鏡面反射光強(qiáng)是不同的。鏡面反射光強(qiáng)可表示為：Ks是與物體有關(guān)的鏡面反射系數(shù)，a為視線方向V與反射方向R的夾角，n為反射指數(shù)，反映了物體表面的光澤程度，一般為1～2000，數(shù)目越大物體表面越光滑。B）鏡面反射圖鏡面反射光因此，對(duì)79

鏡面反射光將會(huì)在反射方向附近形成很亮的光斑，稱為高光現(xiàn)象。

鏡面反射光產(chǎn)生的高光區(qū)域只反映光源的顏色將V和R都格式化為單位向量，鏡面反射光強(qiáng)可表示為：式中：

對(duì)多個(gè)光源：圖

鏡面反射光鏡面反射光將會(huì)在反射方向附近形成很亮的光斑，稱80

C）環(huán)境光

環(huán)境光是指光源間接對(duì)物體的影響，是在物體和環(huán)境之間多次反射，最終達(dá)到平衡時(shí)的一種光。近似地認(rèn)為同一環(huán)境下的環(huán)境光，其光強(qiáng)分布是均勻的，它在任何一個(gè)方向上的分布都相同。例如，透過(guò)厚厚云層的陽(yáng)光就可以稱為環(huán)境光。在簡(jiǎn)單光照明模型中，用一個(gè)常數(shù)來(lái)模擬環(huán)境光，用式子表示為：

其中：Ia為環(huán)境光的光強(qiáng)Ka為物體對(duì)環(huán)境光的反射系數(shù)

C）環(huán)境光其中：Ia為環(huán)境光的光強(qiáng)81

D）Phong光照明模型

綜上分析，Phong光照明模型表述為：由物體表面上一點(diǎn)P反射到視點(diǎn)的光強(qiáng)I為環(huán)境光的反射光強(qiáng)Ie、理想漫反射光強(qiáng)Id、和鏡面反射光Is

的總和，即：按R、G、B三種顏色分量展開計(jì)算得：I＝Ie

＋I(xiàn)d

＋I(xiàn)s由此可得：D）Phong光照明模型按R、G、B三種顏色分量展開計(jì)算得82用Phong模型進(jìn)行計(jì)算時(shí)，對(duì)物體表面上每個(gè)點(diǎn)P，均需計(jì)算光線的反射方向R，再由V計(jì)算（R·V），為減少計(jì)算，可作如下假設(shè)：

a)光源在無(wú)窮遠(yuǎn)處，即光線方向L為常數(shù)；

b)視點(diǎn)在無(wú)窮遠(yuǎn)處，即視線方向V為常數(shù)；c)為避免計(jì)算反射方向R，用（H·N）代替（R·V），這里H為L(zhǎng)和V的平分向量，即：

H＝（L＋V）/|L＋V|注意：Phong模型對(duì)物體表面的每一點(diǎn)的光強(qiáng)進(jìn)行計(jì)算，顯然其計(jì)算量較大。用Phong模型進(jìn)行計(jì)算時(shí)，對(duì)物體表面上每個(gè)83Phong模型計(jì)算實(shí)例圖中可以看出高光指數(shù)、漫反射及鏡面系數(shù)對(duì)顯示效果的影響Phong模型計(jì)算實(shí)例84Phong光照明模型是真實(shí)感圖形學(xué)中提出的第一個(gè)有影響的光照明模型，生成圖象的真實(shí)度已達(dá)到可接受程度。但在實(shí)際應(yīng)用中，它是一個(gè)經(jīng)驗(yàn)?zāi)Ｐ?，還具有以下的一些問(wèn)題：用Phong模型顯示出的物體象塑料，沒(méi)有質(zhì)感；沒(méi)有考慮距離對(duì)光照強(qiáng)度的衰減影響；環(huán)境光是常量，沒(méi)有考慮物體之間相互的反射光；鏡面反射的顏色是光源的顏色，與物體的材料無(wú)關(guān)；鏡面反射的計(jì)算在入射角很大時(shí)會(huì)產(chǎn)生失真；

Phong模型是簡(jiǎn)單的局部光照模型，對(duì)物體間相互反射及折射、陰影處理欠缺等。Phong光照明模型是真實(shí)感圖形學(xué)中提出的第一個(gè)有85濃淡圖繪制算法實(shí)現(xiàn)過(guò)程

通過(guò)前面介紹的gouraud模型、Phong光照模型可計(jì)算物體表面上點(diǎn)的顏色值。為了顯示形體的三維真實(shí)感效果圖，下面介紹多面體濃淡圖的如何繪制。由于空間三維物體是連續(xù)點(diǎn)集。顯然直接計(jì)算點(diǎn)的顏色將無(wú)法確定計(jì)算采樣點(diǎn)的位置和數(shù)目。

事實(shí)上，我們僅能看到屏幕所能顯示的區(qū)域。如果能夠求得屏幕上每一個(gè)象素點(diǎn)所對(duì)應(yīng)的物體上點(diǎn)的顏色，這樣就可繪制整個(gè)圖形。濃淡圖繪制算法實(shí)現(xiàn)過(guò)程通過(guò)前面介紹的gouraud模86

為了得到屏幕上某象素點(diǎn)所對(duì)應(yīng)的物體上點(diǎn)的顏色，假定作經(jīng)過(guò)該象素點(diǎn)的一條射線，射線平行于觀察視線，則射線與多面體物體可能有多個(gè)交點(diǎn)。

如果物體不是透明的，則處于最前面的交點(diǎn)的顏色即為所求，如右圖所示。

最簡(jiǎn)單的算法——Z緩沖區(qū)（Z－Buffer）算法為了得到屏幕上某象素點(diǎn)所對(duì)應(yīng)的物體上點(diǎn)的顏色，87為計(jì)算物體表面上對(duì)應(yīng)象素點(diǎn)的顏色，用幀緩存器存放每個(gè)象素顏色（按光照模型計(jì)算），用深度緩存空間來(lái)存放每個(gè)象素深度值Z，稱為Z緩沖器（即Z－Buffer）。A）Z緩沖器(Z-Buffer)算法

cz為計(jì)算物體表面上對(duì)應(yīng)象素點(diǎn)的顏色，用幀緩存88繪制時(shí)思路：a）Z緩沖器中每個(gè)單元值是對(duì)應(yīng)象素點(diǎn)所反映物體對(duì)象的z坐標(biāo)值，初值取成z的極小值。

b）將待處理的景物表面上的采樣點(diǎn)變換到圖像空間，計(jì)算其深度值z(mì)。

c）并根據(jù)采樣點(diǎn)在屏幕上的投影位置，將其z值與已存貯在z緩存器中相應(yīng)象素處的原可見(jiàn)點(diǎn)的深度值進(jìn)行比較。

d）如果該采樣點(diǎn)位于Z緩存器所記錄的可見(jiàn)點(diǎn)之前，則將該采樣點(diǎn)處的表面顏色填入幀緩存器相應(yīng)象素，同時(shí)用其深度值更新z緩存器存貯的深度值。否則，不寫入也不更新。繪制時(shí)思路：89Z-Buffer算法（）{for(i=0，1，…，m)//m：窗口水平方向象素?cái)?shù)目

for(j=1，…，n）//n：窗口垂直方向象素?cái)?shù)目

{用背景色初始化幀緩存CB：CB(i,j)=背景色；

用最小Z值初始化深度緩存：ZB(i,j)=Zmin；

}

for(每一個(gè)多邊形)

{將該多邊形進(jìn)行投影變換；

掃描轉(zhuǎn)換該多邊形在視平面上的投影多邊形；

for(該多邊形所覆蓋的每個(gè)象素(i,j))

{計(jì)算該多邊形在該象素的深度值Zi,j；

if(Zi,j>ZB(i,j）)

{ZB(i,j)＝Zi,j；

計(jì)算該多邊形在該象素的顏色值Ci,j；

CB(i,j)=Ci,j；

}

}

}

}注：對(duì)投影多邊形進(jìn)行裁剪得到有效區(qū)域，可加快顯示速度Z-Buffer算法（）90Z-Buffer算法在象素級(jí)上以近物取代遠(yuǎn)物。形體在屏幕上的出現(xiàn)順序是無(wú)關(guān)緊要的。這種取代方法實(shí)現(xiàn)起來(lái)遠(yuǎn)比總體排序靈活簡(jiǎn)單，有利于硬件實(shí)現(xiàn)。然而Z-Buffer算法存在缺點(diǎn)：占用空間大，沒(méi)有利用圖形的相關(guān)性與連續(xù)性。Z-Buffer算法以算法簡(jiǎn)單著稱，但也以占空間大而聞名。Z-Buffer算法需要開一個(gè)與圖象大小相等的緩存數(shù)組ZB，可一次性顯示。當(dāng)然，也可只用一個(gè)深度緩存變量zb，但需逐點(diǎn)計(jì)算顯示，顯示效率低下。Z-Buffer算法在象素級(jí)上以近物取代遠(yuǎn)物91

B）掃描線Z-buffer算法

如何減少Z-buffer的緩沖內(nèi)存，并利用相關(guān)性提高點(diǎn)與多邊形的包含性測(cè)試和深度計(jì)算速度，就得到掃描線Z-buffer算法。從最上掃描線開始向下對(duì)每條掃描線作處理。對(duì)每條掃描線來(lái)說(shuō)，把相應(yīng)的幀緩沖器單元置成底色，在z緩沖器中存放z的極小值。B）掃描線Z-buffer算法如何減少Z92與Z－buffer算法相比，掃描線Z－buffer將整個(gè)繪圖窗口內(nèi)的消隱問(wèn)題分解到一條條掃描線上解決，使所需的Z緩沖器大大減少。對(duì)每個(gè)多邊形檢查它在oxy平面上的投影和當(dāng)前掃描線是否相交（如右上圖），若不相交則跳過(guò)該多邊形；若相交則掃描線和多邊形邊界交點(diǎn)一定成對(duì)出現(xiàn)，對(duì)每對(duì)交點(diǎn)間的象素計(jì)算多邊形所在平面對(duì)應(yīng)點(diǎn)的深度(即z值)，并和z緩沖器中相應(yīng)深度值比較。對(duì)所有多邊形和幀緩沖器每一行都作上述處理。利用多邊形Y桶分類、活化邊表處理相鄰掃描線和象素的連貫性，提高算法效率。交線與Z－buffer算法相比，掃描線Z－buff93C）區(qū)間掃描線算法

掃描線z緩沖器算法將消隱問(wèn)題分散到每一條掃描線上去解決，這樣問(wèn)題變得較簡(jiǎn)單了。但在每個(gè)象素處計(jì)算多邊形z值的工作量仍是很大。實(shí)際上每條掃描線被各多邊形邊界在oxy平面上的投影分割成為數(shù)不多的區(qū)間（如右圖），每一個(gè)區(qū)間上只顯示一個(gè)面。因此，只要在區(qū)間上任一點(diǎn)處，找出在該處z值最大的一個(gè)面，這個(gè)區(qū)間上的每個(gè)象素就用這個(gè)面的顏色來(lái)顯示。這就是所謂區(qū)間掃描線算法。C）區(qū)間掃描線算法掃描線z緩沖器算法將消94區(qū)間掃描線算法使得在一條掃描線上每個(gè)區(qū)間只計(jì)算一次深度值，不需要Z緩沖器。它是把當(dāng)前掃描線與各多邊形在投影平面的投影的交點(diǎn)進(jìn)行排序后，使掃描線分為若干子區(qū)間。因此，只要在該區(qū)間任一點(diǎn)處找出在該處z值最大的一個(gè)面，這個(gè)區(qū)間上的每一個(gè)象素就用這個(gè)面的顏色來(lái)顯示。當(dāng)然，現(xiàn)在計(jì)算機(jī)的硬件發(fā)展很快，緩存數(shù)組所耗空間已不是障礙。區(qū)間掃描線算法使得在一條掃描線上每個(gè)區(qū)間只計(jì)95華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件96

Phong模型的區(qū)間掃描線繪制算法，CAD系統(tǒng)中最常用Phong模型的區(qū)間掃描線繪制算法97

4）真實(shí)感效果圖生成

A)全局關(guān)照模型

B)光線跟蹤

C)輻射度算法4）真實(shí)感效果圖生成98A）整體光照明模型簡(jiǎn)單光照明模型和局部光照明模型，雖然可以產(chǎn)生物體的真實(shí)感圖象，但它們都只是處理光源直接照射物體表面的光強(qiáng)計(jì)算，不能很好的模擬光的折射、反射和陰影等，也不能用來(lái)表示物體間的相互光照明影響。而基于簡(jiǎn)單光照明模型的光透射模型，雖然可以模擬光的折射，但是這種折射的計(jì)算范圍很小，不能很好的模擬多個(gè)透明體之間的復(fù)雜光照明現(xiàn)象。對(duì)于上述的這些問(wèn)題，就必須要有一個(gè)更精確的光照明模型。整體光照明模型就是這樣的一種模型，它是相對(duì)于局部光照明模型而言的。在現(xiàn)有的整體光照明模型中，主要有光線跟蹤和輻射度兩種繪制方法。A）整體光照明模型簡(jiǎn)單光照明模型和局部光照明99B）光線跟蹤算法的基本思想

光線跟蹤算法是真實(shí)感圖形學(xué)中的主要算法之一，算法具有原理簡(jiǎn)單、實(shí)現(xiàn)方便和能夠生成各種逼真的視覺(jué)效果等優(yōu)點(diǎn)。在真實(shí)感圖形學(xué)對(duì)光線跟蹤算法的研究中，Whitted提出了第一個(gè)整體光照模型，并給出一般性光線跟蹤算法的范例，綜合考慮了光的反射、折射透射、陰影等。光線跟綜過(guò)程示意圖B）光線跟蹤算法的基本思想光線跟蹤算法是真實(shí)100簡(jiǎn)單光透射模型把透射光分為理想漫透射和規(guī)則透射。由光源發(fā)出的光稱為直接光，物體對(duì)直接光的反射或折射稱為直接反射和直接折射。把物體表面間對(duì)光的反射和折射稱為間接光，間接反射，間接折射。這是光線在物體間的傳播方式，是光線跟蹤算法的基礎(chǔ)。由光源發(fā)出的光到達(dá)物體表面后，產(chǎn)生反射和折射，簡(jiǎn)單光照明模型和光透射模型模擬了這兩種現(xiàn)象。在簡(jiǎn)單光照明模型中，反射被分為理想漫反射和鏡面反射光。簡(jiǎn)單光透射模型把透射光分為理想漫透射和規(guī)則透101

最基本的光線跟蹤算法是跟蹤鏡面反射和折射。從光源發(fā)出的光遇到物體的表面，發(fā)生反射和折射，光就改變方向，沿著反射方向和折射方向繼續(xù)前進(jìn)，直到遇到新的物體。但是光源發(fā)出光線，經(jīng)反射與折射，只有很少部分可以進(jìn)入人的眼睛。因此實(shí)際光線跟蹤算法的跟蹤方向與光傳播的方向是相反的，而是視線跟蹤。由視點(diǎn)與象素(x，y)發(fā)出一根射線，與第一個(gè)物體相交后，在其反射與折射方向上進(jìn)行跟蹤，如圖所示。

最基本的光線跟蹤算法是跟蹤鏡面反射和折射。102此時(shí)，光線在離視點(diǎn)最近的景物表面交點(diǎn)處的走向有以下三種可能：★當(dāng)前交點(diǎn)所在的景物表面為理想漫射面。跟蹤結(jié)束。★當(dāng)前所在的景物表面為理想鏡面．光線沿其鏡面反射方向繼續(xù)跟蹤?！锂?dāng)前交點(diǎn)所在的景物表面為規(guī)則透射面．光線沿其規(guī)則透射方向繼續(xù)跟蹤。顯然，上述過(guò)程是一遞歸跟蹤過(guò)程。對(duì)每一根穿過(guò)屏幕象素中心的光線的跟蹤構(gòu)成了一棵二義樹。雖然光線在景物間的反射和折射可以無(wú)限地進(jìn)行下，但在實(shí)際計(jì)算時(shí)不可能做無(wú)休止的光線跟蹤，因而需要給出光線跟蹤的終判條件。如設(shè)定跟蹤層數(shù)，光亮度小于給定值等條件。此時(shí)，光線在離視點(diǎn)最近的景物表面交點(diǎn)處的走向103華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件104華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件105C）輻射度方法輻射度方法是繼光線跟蹤算法后，真實(shí)感圖形繪制技術(shù)的一個(gè)重要進(jìn)展。光線跟蹤算法成功地模擬了景物表面間的鏡面反射、規(guī)則透射及陰影等整體光照效果。由于光線跟蹤算法的采樣特性和局部光照模型的不完善性，該方法難于模擬景物表面之間的多重漫反射效果，因而不能反映色彩滲透現(xiàn)象。將熱輻射工程中的輻射度方法引入到計(jì)算機(jī)圖形學(xué)中，用輻射度方法成功地模擬了理想漫反射表面間的多重漫反射效果。

經(jīng)過(guò)十多年的發(fā)展，輻射度方法模擬的場(chǎng)景越來(lái)越復(fù)雜，圖形效果越來(lái)越真實(shí)。C）輻射度方法輻射度方法是繼光線跟蹤算法后，106與前面介紹的光照模型與繪制方法有所不同，輻射度方法基于物理學(xué)的能量平衡原理，它采用數(shù)值求解技術(shù)來(lái)近似每一個(gè)景物表面的輻射度分布。

在圖形繪制場(chǎng)景中，景物表面的輻射度分布與視點(diǎn)選取無(wú)關(guān)，輻射度方法是一個(gè)視點(diǎn)獨(dú)立(Viewindependent)的算法。由于其視點(diǎn)無(wú)關(guān)性，使之可廣泛應(yīng)用于虛擬環(huán)境的漫游(walkthrough)系統(tǒng)中。與前面介紹的光照模型與繪制方法有所不同，輻射107華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件108a）二維紋理映射概念b）紋理的表示方法c）紋理映射實(shí)現(xiàn)方法

d）其它紋理映射方法5）紋理映射a）二維紋理映射概念5）紋理映射109二維紋理映射實(shí)質(zhì)上是從二維紋理平面到三維景物表面的一個(gè)映射(如右圖)。通常，二維紋理在一個(gè)紋理空間（s,t）坐標(biāo)系內(nèi)的矩形區(qū)域中用光強(qiáng)度值來(lái)定義，其中每一點(diǎn)處，均定義有一灰度值或顏色值。而場(chǎng)景中的物體表面則在景物空間（u，v）坐標(biāo)系中定義的，投影平面上的象素點(diǎn)是在圖象空間內(nèi)的直角坐標(biāo)系xoy中定義的。a）二維紋理映射概念二維紋理映射實(shí)質(zhì)上是從二維紋理平面到三維景物表面的一個(gè)映110在繪制時(shí)，應(yīng)用紋理映射方法可以方便地確定景物表面上任一可見(jiàn)點(diǎn)P處在紋理空間中的對(duì)應(yīng)位置(s,t)；而(s,t)處所定義的紋理值或顏色值即描述了景物表面在P處的某種紋理屬性。把該點(diǎn)處的紋理顏色值作為漫反射系數(shù)代入光照模型（如簡(jiǎn)化的Phong反射模型）中進(jìn)行計(jì)算，就能夠生成具有紋理效果的真實(shí)感圖象。紋理影射技術(shù)可分為如下兩步進(jìn)行：

a）紋理表示：確定表面的哪些參數(shù)需定義成紋理形式，即確定紋理屬性。

b）映射紋理：建立紋理空間與景物空間及景物空間與屏幕圖象空間之間的映射關(guān)系。在繪制時(shí)，應(yīng)用紋理映射方法可以方便地確定景物表面上任一可111b）紋理的表示方法

二維紋理最常見(jiàn)的表示方法就是數(shù)字化的彩色圖象，其分辨率用m×n表示，顏色數(shù)用2k表示，例如，k=1表示黑白（二值）圖象；用位圖（BitMap）文件（BMP文件）或其它格式的圖象文件（例如：PCX，TIFF或JPEG等圖象文件）保存。紋理的另外一種表示方法就是用解析函數(shù)或過(guò)程來(lái)表示。例如：我們可以用三維空間中定義的共振函數(shù)（正弦函數(shù)）來(lái)生成木紋理或大理石紋理，這種紋理映射方法稱為過(guò)程紋理映射。b）紋理的表示方法

紋理的另外一種表示方112c）紋理映射實(shí)現(xiàn)方法

大體上，實(shí)現(xiàn)紋理影射的方法有兩類：

a）將紋理模式映射到景物表面，然后再?gòu)木拔锉砻嬗成涞酵队捌矫?，即：紋理空間→景物空間→圖象空間；

為簡(jiǎn)化計(jì)算，由紋理空間向景物空間映射采用線性映射：

由景物空間向圖象空間變換通過(guò)平行或透視投影來(lái)實(shí)現(xiàn)。b）將象素區(qū)域映射到景物表面，再由景物表面映射到紋理空間，即：圖象空間→景物空間→紋理空間。

這一類方法避免了象素的分割計(jì)算，并能簡(jiǎn)化反走樣處理；但是它一般需要計(jì)算投影變換和紋理映射的逆變換。c）紋理映射實(shí)現(xiàn)方法

大體上，實(shí)現(xiàn)紋理影射的方法有兩類113華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件114環(huán)境映射（反射映射）如茶具上映射房間背景凸凹紋理（如桔子皮的模擬）幾何擾動(dòng)

法矢擾動(dòng)過(guò)程紋理（體紋理）：三維木材材質(zhì)效果三維大理石效果d）其它紋理映射方法環(huán)境映射（反射映射）d）其它紋理映射方法1151、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示6、圖形學(xué)的其它應(yīng)用1、三維形體的計(jì)算機(jī)表達(dá)1161）基于圖像的繪制技術(shù)2）人體建模（皮膚、肌肉、頭發(fā)、表情、衣服、運(yùn)動(dòng)）與虛擬主持人3）基于點(diǎn)的造型4）科學(xué)數(shù)據(jù)可視化體可視化及數(shù)字人體技術(shù)場(chǎng)可視化（流體、磁場(chǎng)、溫度、應(yīng)力等）5）自然景觀仿真6）地理信息系統(tǒng)7）非照片真實(shí)感圖形繪制8）動(dòng)畫與游戲9）其它1）基于圖像的繪制技術(shù)1171）基于圖像的繪制技術(shù)1）基于圖像的繪制技術(shù)118二種思路：1）通過(guò)紋理映射方法把圖片貼到三維模型上漫游，但要注意紋理拼接，全景圖的合成

生產(chǎn)車間漫游2）直接在二維圖像的基礎(chǔ)上實(shí)現(xiàn)漫游，但漫游的路徑應(yīng)和圖像采樣路徑不能過(guò)大的誤差，否則視圖插值后失真嚴(yán)重。

博物館旅游，風(fēng)景旅游二種思路：119華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件120華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件1212）人體建模與虛擬主持人（皮膚、肌肉、頭發(fā)、表情、衣服、運(yùn)動(dòng)）虛擬主持人：通過(guò)建模賦予其和真人一樣的動(dòng)感及豐富的個(gè)性，和真實(shí)主持人相配合（增強(qiáng)現(xiàn)實(shí)技術(shù)）人體建模：盡可能象真人一樣，廣泛用于3D游戲，二種思路：利用IBR技術(shù)將真人紋理進(jìn)行映射

直接基于物理的三維建模技術(shù)2）人體建模與虛擬主持人（皮膚、肌肉、頭發(fā)、表情、衣服、運(yùn)動(dòng)1223）基于點(diǎn)的造型基于點(diǎn)的點(diǎn)云處理技術(shù)以點(diǎn)作為繪制和造型的基本元素克服網(wǎng)格方法的高度復(fù)雜性和低魯棒性無(wú)需顯式存儲(chǔ)拓?fù)涓叨鹊臄?shù)據(jù)局部性3）基于點(diǎn)的造型基于點(diǎn)的點(diǎn)云處理技術(shù)以點(diǎn)作為繪制和造型的基本1234）科學(xué)數(shù)據(jù)可視化體可視化及數(shù)字人體技術(shù)“數(shù)字人體—人體系統(tǒng)數(shù)字學(xué)”是當(dāng)今醫(yī)學(xué)科學(xué)、生命科學(xué)、信息科學(xué)、智能科學(xué)技術(shù)和計(jì)算機(jī)科學(xué)技術(shù)的高度綜合。難點(diǎn)：三維重建過(guò)程中的特征分類

4）科學(xué)數(shù)據(jù)可視化體可視化及數(shù)字人體技術(shù)“數(shù)字人體—人體系統(tǒng)124場(chǎng)可視化（流體、磁場(chǎng)、溫度、應(yīng)力等）——等值面生成分形數(shù)據(jù)顯示場(chǎng)可視化（流體、磁場(chǎng)、溫度、應(yīng)力等）——等值面生成分形數(shù)據(jù)顯125自然景觀仿真自然景觀仿真1265）地理信息系統(tǒng)已二維地圖為基礎(chǔ)，對(duì)重要地點(diǎn)進(jìn)行三維建模及IBR技術(shù)，如通過(guò)漫游引導(dǎo)消防滅火等數(shù)字地圖，GPS導(dǎo)航圖、城市規(guī)劃用谷歌地圖的街景查看功能可以在網(wǎng)上360度全方位查看紐約市、舊金山、芝加哥和其它12個(gè)城市的街景。實(shí)現(xiàn)方法：全方位谷歌攝影車現(xiàn)場(chǎng)拍攝。原理：GIS＋I(xiàn)BR2007年被時(shí)代周刊評(píng)為最佳發(fā)明5）地理信息系統(tǒng)已二維地圖為基礎(chǔ)，對(duì)重要地點(diǎn)進(jìn)行三維建模及I1276）非照片真實(shí)感圖形繪制（NPR）以非真實(shí)感效果的造型、繪制和動(dòng)畫算法形成畫家手工風(fēng)格的圖形。6）非照片真實(shí)感圖形繪制（NPR）以非真實(shí)感128華中科技大學(xué)大學(xué)CAD技術(shù)及應(yīng)用-第二部分-圖形課件1297）動(dòng)畫、游戲、電影特技我國(guó)網(wǎng)游業(yè)的發(fā)展，史玉柱的傳奇生涯7）動(dòng)畫、游戲、電影特技我國(guó)網(wǎng)游業(yè)的發(fā)展，史玉柱的傳奇生涯13089年與3伙伴4000元巨人創(chuàng)業(yè)，91年遷珠海，92年底，銷售近2億元95年,巨人“三大戰(zhàn)役”，12種保健品、10種藥品、10幾款軟件推向市場(chǎng)94年初，巨人大廈開工，預(yù)計(jì)3年、72層、需12億，96年資金告急，97年初籌資未果，爆發(fā)財(cái)務(wù)危機(jī)停工，負(fù)債2.5億，內(nèi)地“首負(fù)”。2000年，運(yùn)作“腦白金”（前“腦黃金”），創(chuàng)大量財(cái)富，并以“神秘人”身份清償預(yù)售樓花款04年進(jìn)軍網(wǎng)游，成立征途網(wǎng)絡(luò)，05年《征途》推出，06年達(dá)6.26億，07年月利潤(rùn)上市，美國(guó)上市。計(jì)算機(jī)游戲5個(gè)元素：圖像、聲音、操作界面、游戲性、故事好的游戲需仔細(xì)策劃，包括市場(chǎng)定位、劇本、角色CG＋多媒體技術(shù)是基礎(chǔ)89年與3伙伴4000元巨人創(chuàng)業(yè)，91年遷珠海，92年底，銷131特技：動(dòng)畫變形(基于圖像)特技：動(dòng)畫變形(基于圖像)132特技：動(dòng)畫變形（幾何＋圖像）特技：動(dòng)畫變形（幾何＋圖像）133可以粗略地將CG電影分為場(chǎng)景和角色兩部分。全CG的場(chǎng)景其代表是虛擬現(xiàn)實(shí)(VirtualReality)技術(shù)，當(dāng)然作為CG技術(shù)在一個(gè)更高層面上的體現(xiàn)，VR技術(shù)的廣度和深度可以大大超越電影的范疇與局限性。VR技術(shù)起先用于一些發(fā)達(dá)國(guó)家飛機(jī)駕駛員和汽車駕駛員的模擬體驗(yàn)上，整個(gè)生態(tài)場(chǎng)景由計(jì)算機(jī)實(shí)時(shí)動(dòng)態(tài)生成，根據(jù)受測(cè)者的行為而模擬出不同后果。如VR系統(tǒng)在美國(guó)紐約市海德天文館的應(yīng)用，據(jù)稱該天文館擁有全球最大的產(chǎn)生身臨其境效果的虛擬系統(tǒng)。利用數(shù)字技術(shù)，該系統(tǒng)能投影50萬(wàn)顆星星，而利用機(jī)械投影系統(tǒng)一般只能投影1萬(wàn)2千顆星星。VR技術(shù)的出現(xiàn)進(jìn)一步拓寬了CG應(yīng)用的空間。

VR技術(shù)很快就在電腦游戲等娛樂(lè)領(lǐng)域體現(xiàn)出無(wú)窮的魅力和商業(yè)價(jià)值，對(duì)于電影來(lái)說(shuō)，虛擬現(xiàn)實(shí)是交互式電影(InteractiveMovie)的實(shí)現(xiàn)途徑之一，試想由觀眾親涉其間，控制角色的舉動(dòng)，從而對(duì)場(chǎng)景產(chǎn)生互動(dòng)后果，這是怎樣一個(gè)夢(mèng)幻般的體驗(yàn)?。∥磥?lái)電影中，虛擬現(xiàn)實(shí)完全可能與現(xiàn)實(shí)分庭抗禮，使觀眾真正置身于一個(gè)虛實(shí)莫辨的主觀體驗(yàn)的境界之中。VR與CG電影當(dāng)前我國(guó)的創(chuàng)意產(chǎn)業(yè)政策，創(chuàng)意產(chǎn)業(yè)園興建熱潮可以粗略地將CG電影分為場(chǎng)景和角色兩部分。V1341、幾何物體的計(jì)算機(jī)表達(dá)方法2、三維圖形變換方法3、三角剖分作用、典型方法，為什么要進(jìn)行幾何壓縮4、三維模型的線框消隱圖顯示方法5、三維模型的濃淡圖顯示方法6、三維場(chǎng)景的真實(shí)感圖形顯示方法7、結(jié)合本人的專業(yè)背景，舉例說(shuō)明對(duì)圖形學(xué)的需求思考與討論1、幾何物體的計(jì)算機(jī)表達(dá)方法思考與討論135計(jì)算機(jī)圖形學(xué)基礎(chǔ)算法1、三維形體的計(jì)算機(jī)表達(dá)2、圖形變換3、基礎(chǔ)算法4、線框及消隱顯示5、真實(shí)感顯示

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

三維幾何形體的表達(dá)現(xiàn)實(shí)生活中的產(chǎn)品都是由不同類型的三維(3D)幾137計(jì)算機(jī)中表示形體幾何模型通常用：

線框模型表面模型實(shí)體模型線框模型和表面模型保存的三維形體信息都不完整。只有實(shí)體模型才能夠完整地、無(wú)歧義地表示三維形體。

計(jì)算機(jī)中表示形體幾何模型通常用：138點(diǎn)用三維坐標(biāo)表示，是最基本的元素邊是形體相鄰面的交界，可為空間直線或曲線環(huán)是有序、有向的封閉邊界，外環(huán)僅一個(gè)，逆時(shí)針?lè)较?，?nèi)環(huán)可有可無(wú)，也可多個(gè)，方向順時(shí)針。面是一個(gè)單連通區(qū)域，可以是平面或曲面，由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)組成；面的方向由面的法矢決定，法矢向外為正向面?；靖拍罴岸x點(diǎn)用三維坐標(biāo)表示，是最基本的元素基本概念及定義139實(shí)體是由若干個(gè)面組成的閉包，實(shí)體的邊界是有限個(gè)面的集合。形體表面上任一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圓，即圍繞該點(diǎn)的形體鄰域在二維空間中可構(gòu)成一個(gè)單連通域，我們把滿足該定義的形體稱為正則形體。否則為非正則形體，如存在懸面、懸邊的長(zhǎng)方體為非正則形體。

實(shí)體是由若干個(gè)面組成的閉包，實(shí)體的邊界是有限個(gè)面的集合。形體140線框模型線框模型用頂點(diǎn)和棱邊表示三維形體，其棱邊可以為直線、圓弧、二次曲線及樣條曲線組成。

線框模型線框模型用頂點(diǎn)和棱邊表示三維形體，其棱邊可以為直線、141線框模型在計(jì)算機(jī)內(nèi)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)：

頂點(diǎn)表：記錄各頂點(diǎn)坐標(biāo)值；

棱線表：記錄每條棱線所連接的兩頂點(diǎn)。classPOINTclassEDGE{{doublev[3];//坐標(biāo)值intstart_point_no;//邊的起點(diǎn)intpointtype;//點(diǎn)的屬性intend_point_no;//邊的終點(diǎn)