1、三維幾何模型在計算機內的表示CAD/CAM 的核心技術是幾何造型技術一項研究在計算機中如何表示物體模型形狀的技術。在 CAD/CAM 技術四十多年的發展歷程中，經歷了四次重大的變革。60 年代初期的CAD 系統只能處理簡單的線框模型，提供二維的繪圖環境，用途比較單。進入 70 年代，根據汽車造型中的設計需求，法國人提出了貝塞爾算法，隨之產生了三維曲面造型系統CATIA 。它的出現，標志著CAD 技術從單純模仿工程圖紙的三視圖模式中解放出來，首次實現以計算機完整描述產品零件的主要信息。這是CAD 發展歷史中的第一次重大飛躍。1979 年， SDRC 公司發布了世界上第一個完全基于實體造型技術的大

2、型CAD/CAE 軟件IDEAS。由于實體造型技術能夠精確表達零件的全部屬性，在理論上有助于統一CAD 、CAE 、 CAM的模型表達，給設計帶來了驚人的方便性。可以說，實體造型技術的普及應用標志著CAD發展史上的第二次技術革命。但是，在當時的硬件條件下，實體造型的計算及顯示速度太慢，限制了它在整個行業的推廣。90 年代初期，參數化技術逐漸成熟，標志著CAD技術的第三次革命。參數化技術的成功應用，使得它在1990年前后幾乎成為CAD業界的標準。隨后， SDRC 攻克了欠約束情況下全參數的方程組求解問題，形成了一套獨特的變量化造型理論。SDRC將變量化技術成功的應用到CAD系統中，標志著CAD技

3、術的第四次革命。隨著CAD技術和幾何造型技術的發展，近年來，市場上出現了一大批優秀的幾何造型軟件及工具。例如， PTC 公司的產品Pro/E 、 SDRC 的產品 I-DEAS Master Series、 UGS 公司的產品Unigraphics、IBM公司的產品CATIA/CADAM、Autodesk公司的產品MDT 、Spatial Tech公司的ACIS 、 EDS公司的Parasolid等。在國內，清華大學、北京航空航天大學、華中理工大學、浙江大學、上海交通大學、西北工業大學，以及其他一些單位也發表了一些關于特征造型技術研究的論著，并開發了一些特征造型系統，例如：清華大學開發的TiG

4、ems造型系統，北京航空航天大學研制出的微機版金銀花 （LONICERA） ”系統，武漢開目信息技術有限責任公司開發的開目三維CAD軟件等等。造型系統簡介Parasolid 和 ACIS 是兩個最有代表性的幾何造型系統的開發平臺。在早期開發的實體造型系統中，英國的劍橋大學研制出了BUILD-1和BUILD-2系統，但都沒有公開使用。80年代初期，研究小組的一部分人組建了Shape Data公司，并開發了實體造型系統Romulus。1986 年， Shape Data并入 EDS Uni graphics之后，推出了功能強大的幾何造型核心Parasolid 。同時， Shape Data部分保留

5、人員研制了新的造型核心，就是后來由SpatialTechnology 公司推出的幾何造型系統核心ACIS 。Parasolid 和 ACIS 并不是面向最終用戶的應用系統，而是 幾何引擎”，作為應用系統的核心。用戶可用它們作為平臺，開發自己的應用系統。當今許多流行的商用CAD/CAM 軟件，如Uni graphics 、Solidedge 、Solidwork 、 MDT 等，都是在Parasolid 或 ACIS 的基礎上開發出來的。Parasolid 有較強的造型功能，但是只能支持正則實體造型。它提供的主要功能有：集合運算、特征的創建和編輯、局部操作、數據交換文件接口等。Parasolid

6、 采用精確的邊界表示，包括拓撲、幾何和關聯三種數據類型。ACIS 具有和 Parasolid 相似的形體結構，但在系統結構上采用了核心和外殼相結合的方式。 ACIS 支持線框、表面和實體的統一表示，支持非正則形體的造型。在上述幾何實體造型系統中，通常都會提供一些基本的形體輸入方法，以及拉伸，旋轉，蒙皮，掃描等直接構造形體的方法，通過集合運算對形體進行拼合。雖然對這些造型方法的研究取得了一系列新進展，但是集合運算仍基本局限在對兩個體進行正則運算（交，并，差）上，而且結果形體的信息都已經包含在兩個參加運算的原始形體之中，不能引入新的信息。實際應用中，有些機械零件具有特定的形狀特征，不能通過集合運算

7、來直接完成，或者直接實現時操作步驟非常復雜。但是，它們的生成方法和集合運算非常相似，可以看作是集合運算的擴展。拔模和抽殼都屬于這一類型的造型方法。三維形體的表示三維造型技術是建立恰當的模型來表示自然界中形態豐富的三維物體的技術，根據造型對象將造型技術分成3 類。第一類是曲面造型，主要研究計算機內如何描述一張曲面，及曲面的顯示與控制。曲面造型又分成規則曲面和不規則曲面兩種。不規則曲面造型方法主要有貝塞爾曲線曲面、 B 樣條曲線曲面和孔斯曲面等。（二維曲線：Nurbs （通過擬合點）、三次 B 樣條（通過控制點）、貝塞爾（控制點和擬合點重合）和波浪線（ B 樣條）第二類是立體造型方法，主要研究在計

8、算機內如何定義、表示一個三維物體，主要有體素構造法、邊界表示法和八叉數法等等。曲面造型和立體造型合稱幾何模型造型。該技術主要應用在機械行業輔助設計制造領域（CAD ）。第三類是自然景物模擬，主要研究在計算機內如何模擬自然景物，如云、流水、樹等。該造型技術主要應用在游戲和藝術造型等領域。如下主要說說幾何模型的表示。在計算機中，表示幾何形體的方法通常有三種：線框模型、表面模型和實體模型一、 線框模型該模型采用三維形體的全部頂點及邊的集合來描述三維形體，即用頂點表和邊表兩個表的數據結構來表示三維模型。每條邊由兩個頂點表示。主要優點是結構簡單，處理容易。描述二維目標十分理想。但對三維物體， 存在如下缺

9、點：1） 沒有面的信息，它不能表示表面含有曲面的物體。2） 不能明確定義點與物體之間的關系。3） 點和邊信息容易出現二義性。二、 表面模型在線框模型的基礎上，增加了物體中的面的信息，用面的集合來表示物體，每個面由多條有向邊構成，用環來定義面的邊界，即是用頂點表、邊表和面表來描述模型。表面模型又分為平面模型和曲面模型。前者以多邊形網格為基礎。后者以參數曲面塊為基礎。表面模型存在的不足就是它只能表示物體的表面邊界，而不能表達出真實實體的屬性，很難確認一個表面模型表示的三維圖形是一個實體還是一個空殼。這 個不足，在實體模型中得到了解決。三、 實體模型實體模型是最高級的模型，它能完整表示物體的所有形體

10、信息，可以無歧義地確定一個點是在物體外部還是內部或表面上。實體模型使用有向邊的右手法則來確定所在面的外法線方向。即用右手沿邊的順序方向握住，大拇指所指向為該面的外法線方向。法線方向指向體外。體外實體模型存在著不同的數據結構，在這些結構中存在一個共同點，即數據結構不僅記錄了物體全部的幾何信息，而且還記錄了所有的點、線、面、體的拓撲信息（即空間位置關系）。實體模型的構造通常使用體素（即原始的基本實體），經集合論中的交、并、差運算構成復雜形體。1.實體的定義實體就是有效的物體，即客觀世界中確實存在的物體，要在計算機內表示、 構造一個實體，就必須給出實體的確切定義（即用最小的數據結構唯一地確 定實體的

11、形狀和位置。）如下圖帶有懸掛面的立方體就不是實體，在客觀世 界中不可能存在這樣的物體。作為實體應滿足如下條件：1 . 剛性。一個實體必須具有一定的形狀（流體不屬于實體）2.維數一致性。一個實體的各個部分必須是三維的，不能存在懸掛的、孤立的邊界。3.有限性。一個實體必須占有有限的空間。4.邊界確定性。根據實體的邊界，可確定實體的內部或外部。5.封閉性。經過集合運算后，仍然是有效的實體。實體的表面必須具備如下性質：1. 連通性。表面任意兩點都可用表面上的一條路徑連接起來。2. 邊界性。3. 非自相交性。一個實體表面不可自相交。4. 可定向性。一個實體的表面兩則可明確定義出實體的內側和外側。5.性。

12、一個表面的封閉性由多邊形網格各元素的拓撲關系確定的。條邊連接且僅連接兩個面，每條邊有且僅有兩個端點。封閉即每從點集拓撲角度給出實體的定義。將三維實體看作是空間中點的集合，與邊界點共同組成。它由內點內點是指點集中的這樣一些點：它們具有完全包含于該點集的充分小的點集中除內點外的所有的點就是邊界點。領域。所以三維物體A可表示為:A= bA,iAbA為物體A的邊界點集；iA為物體A的內部點集。定義點集的正則運算r 如下 ：rA = ciAi 為取 A 的內點運算；c 為取閉包運算；A 為一個點集。iA 為 A 的全體內點組成的集合，稱為A 的內部，它是一個開集（“開集”可以理解為沒有邊界值去判斷點是否

13、為內點）。ciA 為 A 的內部的閉包，是iA 與其邊界點的并集。（據此可以理解“閉包”的含義），它本身是一個閉集，（“閉集”可以理解為可以通過明確的邊界值來判斷點是否在集合中）。正則運算即為：先對物體取內點再取閉包的運算。rA 稱為物體 A 的正則點集如圖：顒晟釀二纏內點M會血憾JL颶心帶有懸邊的二維點集內點集合 iAA（沒有粗邊界）正則點集ciA（有粗邊界 ）以上圖中，圖1有懸邊所以點集不是有效實體，圖2沒有邊界，不是滿足“封閉性”所以也不是實體。圖3為正則點集，封閉性，也滿足實體的其他條件，所以為實體。正則點集有時也不一定是實體。如下圖：二錐流體左圖為正則點集，但它不是有效的物體。由此，

14、就會涉及到另外一個概念“二維流體”。二維流體是指對于實體表面上的任何一點，都可以找到一個圍繞著它的任意小的領域，該領域在拓撲（即是空間位置）上與平面上的一個圓盤是等價的（也就是在表面上存在著一個領域圍繞著某個點）。這意味著，在領域的點集和圓盤之間存在著連續的一對一的對應關系。如上右圖，立體表面上任一點都存在與圓盤同構的領域。而左圖，兩個立方體共享邊被四個面共享，其上的點不存在這樣的唯一的領域（在上圖中，共享邊的點，存在圍繞它的領域有兩個）。有了上述概念后，實體可以這樣描述為：對于一個占據有限空間的正則點集， 如果其表面是二維流形，則該正則點集為實 體（有效物體）。2?正則集合運算能產生正則幾何

15、體（有正則點集組成的形體）的集合運算稱為正則集合運算。正則集合運算與傳統集合運算的區別主要是在對產生結果的邊界面的處理上，其內部點的處理是一致的。正則運算主要是考慮如何消除或不產生懸點、懸邊和懸面_ 。如下圖：c=Anp （傳統交）C=A n* B （正則交）上圖，左邊為傳統的交運算結果，右邊為正則的交運算結果。在傳統的集合運算符后加“號表示正則運算符。實現正則集合運算有兩種方法：間接法和直接法。間接法是先按普通集合運算求出結果，后用一些規則判斷，以消除不符合正則幾何定義的部分（即懸邊、懸面等），從而得到正則幾何體。直接法是定義正則集合算子的表達式，用以直接得出符合正則幾何體定義的結果。正則幾

16、何運算定義如下：A* B = r（ A B） ;式中 表示傳統集合并、交、差算子；* 表示相應的正則并、交、差算子；r 是集合的正則化算子。實體造型是以立方體、圓柱體、球體、錐體、環狀體等多種基本體素為單位元素，通過集合運算（拼合或布爾運算 ），生成所需要的幾何形體。這些形體具有完整的幾何信息，是真實而唯一的三維物體。所以，實體造型包括兩部分內容：即體素定義和描述，以及體素之間的布爾運算 （并、交、差 ）。布爾運算是構造復雜實體的有效工具。目前常用的實體表示方法主要有：構造實體幾何法（CSG）、邊界表示法 （BRep ）和掃描法。物體的 CSG 樹表示物體的體素構造表示法（Con struct

17、ive Solid Geometry, CSG）是用兩個物體間的并、交、差正則集合運算操作生成一個新的物體的方法。CSG 表示法：先定義一些形狀比較簡單的常用體素，如方塊、圓柱、圓錐、球、棱柱等。然后用集合運算并、交、差把體素修改成復雜形狀的形體。早期的CSG模型僅使用代數方程及半空間的概念，體素只支持多面體與二次曲面體，而不支持表面含有自由曲面的實體。整個模型是棵樹結構，最終形體的表面交線與有效區域沒有顯式給出，不能直接用于NC加工與有限元分析等后繼處理。集合運算構造實體的過程可用二叉樹結構表示，稱該二叉樹為CSG 樹。樹的葉節點表示體素或帶有幾何變換參數的體素，非葉節點表示施加于其子節點的

18、正則集合算子，或稱布爾算子。樹的根節點表示集合運算的最終結果，也即希望得到的實體。邊界表示法邊界表示法（ Brep-Boundary Representation）通過描述物體的邊界來表示一個物體。所謂的邊界是指物體的內部點與外部點的分界面，定義了物體的邊界，該物體也就被唯一地定義了。如下圖：邊界表示法一個重要的特點是：描述物體的信息包括幾何信息與拓撲信息兩個方面。幾何信息是指物體在歐氏空間中的位置、形狀和大小；而拓撲信息是指拓撲元素（頂點、邊和表面）的數量及其相互間的連接關系。拓撲信息構成物體的骨架”，而幾何信息則猶如附著在這一骨架”上的肌肉”。幾何信息有面（ face ）、環（ loop

19、）、邊（ edge ）和點（ vertex ），拓撲信息有模型（model ）、 區域（ region ）、外殼（ shell ）、面引用（ face use ）、環引用（ loop use ）、邊引用（edge use ）和點引用（ vertex use ）。如下圖是用輻射邊數據結構表示的一個形體模型，注意其中實體、面、線是用統一的數據結構表示的。lace use *- f lace*use* vertex uat* l ctftxtopoltsay gtomdry頂點頂點（ Vertex ）的位置用（幾何）點（Point ）來表示。點是幾何造型中的最基本的元素，自由曲線、曲面或其它形體均可

20、用有序的點集表示。用計算機存儲、管理、輸出形體的實質就是對點集及其連接關系的處理。在正則形體定義中，不允許孤立點存在。邊邊（ Edge ）是兩個鄰面 （對正則形體而言 ）、或多個鄰面 （對非正則形體而言）的交集，邊有方向，它由起始頂點和終止頂點來界定。邊的形狀（Curve ）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描述，也可用顯式、隱式或參數方程來描述。形體中與一條空間曲線相聯系，以及包含其兩個端點和引用它的所有環邊等信息的拓撲元素稱為邊。環環（ Loop ）是有序、有向邊（Edge ）組成的封閉邊界。環中的邊不能相交，相鄰兩條邊共享一個端點。環有方向、內外之分

21、，外環邊通常按逆時針方向排序，內環邊通常按順時針方向排序。面面（ Face ）由一個外環和若干個內環（可以沒有內環）來表示，內環完全在外環之內。根據環的定義，在面上沿環的方向前進，左側總在面內，右側總在面外。面有方向性，一般用其外法矢方向作為該面的正向。若一個面的外法矢向外，稱為正向面；反之，稱為反向面。面的形狀（ Surface ）由面的幾何信息來表示，可以是平面或曲面，平面可用平面方程來描述，曲面可用控制多邊形或型值點來描述，也可用曲面方程（隱式、顯式或參數形式）來描述。對于參數曲面，通常在其二維參數域上定義環，這樣就可由一些二維的有向邊來表示環，集合運算中對面的分割也可在二維參數域上進行

22、。體體（ Body ）是面的并集。在正則幾何造型系統中，要求體是正則的，非正則形體的造型技術將線框、表面和實體模型統一起來，可以存取維數不一致的幾何元素，并可對維數不一致的幾何元素進行求交分類，從而擴大了幾何造型的形體覆蓋域。幾何形體是由封閉表面圍成的空間，是歐氏空間中非空、有界的封閉子集，其邊界是有限個面的并集。外殼外殼是一些點、邊、環、面的集合，其所含的面集有可能圍成封閉的三維區域，從而構成一個實體；外殼還可以表示任意的一張曲面或若干個曲面構成的面組；外殼還可以是一條邊或一個孤立點。外殼中的環和邊有時被稱為線框環”和線框邊”這是因為它們可以用于表示形體的線框圖。區域由一組外殼組成，而模型由

23、區域組成。正則形體對于任一形體，如果它是三維歐氏空間R3 中非空、有界的封閉子集，且其邊界是二維流形（即該形體是連通的），則稱該形體為正則形體，否則稱為非正則形體。在這種表示法中，由于物體的點、邊和表面以獨立對象的形式的存在，所以可以方便地對物體進行各種局部修改。多面體的頂點、邊和表面之間的拓撲關系可用9 種不同的形式予以描述：1 . 頂點相鄰性，表示v-v2 . 頂點一邊相鄰性，表示v-e3 ?頂點一面相鄰性，表示v-f4 . 邊一頂點，e-v5. 邊一邊e-e6 ?邊一面e-f7 . 面一頂點f-v& 面一邊f-e9 . 面一面f-f邊界表示的數據結構兩種典型的邊界表示法數據結構主要包括：

24、翼邊結構，雙向邊表( DCELDoublyConnected Edge List)，半邊結構，四邊結構，輻射邊(Radial-Edge)結構等等。其中半邊結構非常適合表示正則形體。翼邊結構在頂點、邊、表面等組成物體的三要素中，翼邊結構以邊為中心來組織數據。如下圖：struct EdgeVertex P1,P2;Loop *LeftLoop,*RightLoop;struct Edge *ercw,*ercc,*elcc,*elcw;上圖菱邊 e 作為有向線段，其數據結構中包含有兩個指針，分別指向e 的兩個端點：起點 P1 和終點 P2 。此外， e 中還設置有兩個環指針，分別指向菱邊e 所鄰接

25、的兩表面上的環 Loop左和 Loop 右。這樣就確定了菱邊e 與相鄰表面之間的拓撲關系。為了能從邊e出發找到它所在的任一閉合面環上的其他菱邊，在e 中又增加了四個邊指針ercw 、ercc 、elcc 、 elcw ，ercc 表示 e 在右面環中沿逆時針方向所連接的下一條菱邊，elcw 表示 e 在左面環中沿順時針方向所連接的下一條邊，余類推。由于翼邊結構邊的構造和使用比較復雜，后來在此結構基礎上改進，提出了半邊數據結構。半邊結構已成為邊界表示的主流數據結構。半邊數據結構實體的 B-rep 表示模型是一非常復雜的模型，要求能夠表達出多面體各幾何元素之間完整的幾何和拓撲關系，并且允許對這種幾

26、何和拓撲關系進行修改?在 B-rep 表示中，體、面、邊和頂點是最基本的幾何元素，在實體的拼合、顯示、分析計算或人機交互過程中，對基本幾何元素的下列操作是必不可少的：增加或刪除體、面、邊或頂點；已知一個體，查找它的所有面、所有邊或所有頂點；已知一個面或一個邊，查找它所屬于的體；已知一個面，順序查找圍成它所有邊；已知一個邊，查找交于該邊的所有面，或著查找該邊的鄰邊，或者查找該邊的兩個端點；已知一個頂點，查找交于該頂點的所有邊或所有面。以上這些基本操作的效率直接影響著整個實體造型系統的效率。一個 B-rep 數據結構應當方便、迅速地實現幾何元素的這些查詢或增刪操作.為了查詢或操作方便，必須建立各幾

27、何元素間的拓撲關系，且引入其它輔助元素，例如在許多B-rep 數據結構中具有環結點，用來表示面的內、外封閉邊界?在B-rep 的數據結構設計時，除了需要考慮時間的因素外，還要考慮空間的因素，即模型所占計算機內存的大小，但往往這兩方面是互相矛盾的.要想各個幾何元素之間查詢迅速，必然要在它們之間建立廣泛的聯系，這樣必然增加存儲空間的占用量。反過來也是如此，而半邊數據結構就很好的權衡了空間和時間的問題。在構成多面體的三要素（點、邊、面）中，半邊數據結構仍以邊為核心，但為了方便表達拓撲關系，它將一條邊表示成拓撲意義上方向相反的兩條半邊”所以稱為半邊數據結構，其結構入圖：Bi 點斤血冇半邊數據結構共包含六個結點：體、面、環、邊、半邊和頂點?半邊是一連接兩個頂點并具有一固定方向的線段?一系列首