第九章基本造型方法9.1概述9.2結構實體幾何模型（CSG）9.3分解模型9.4邊界模型9.5非傳統造型技術9.1概述設計對象所含的信息可以分為兩個部分：非視覺信息和視覺信息。圖9.1對象的信息

計算機內對形狀信息的描述方法簡稱為造型（Modeling）的技術。造形技術主要由形狀表達和形狀操作兩個部分組成。1形狀表達的任務是將形狀的結構用數據結構模擬出來。這種描述形狀的數據結構稱為模型（Model）。2形狀操作的任務是實現對模型的生成、修改、綜合、分析、計算、顯示等等操作，以便完成設計過程中的各種造型任務。

1．實體造型技術（SolidModeling）

2．曲面造型技術（SurfaceModeling）

3．非幾何形體的造型技術

造型技術是CAD的核心技術之一。目前常用的造型技術有：

結構模型又稱結構實體幾何（ConstructiveSolidGeometry）模型，簡稱CSG。CSG含有一組簡單的幾何實體類型，如立方體、球、圓柱、圓錐等。它們稱為基元實體類型（PrimitiveSolidType）。CSG還含有一組施加于基元實體類型上的操作，這些操作包括：幾何變換、集合運算以及剖割、局部修改等其他造型操作。這是用二叉樹的形式記錄一個零件的所有組成體素拼合運算的過程，可以簡稱為體素拼合樹。

9.2結構實體幾何模型(CSG)

Wrench+/\cube3+/\+cube2/\cylinder1cube1圖9.2體素拼合實例

表9.1CSG節點數據結構OP_Code操作碼transformprimitive坐標變換基本體素left_Subtreeright_Subtree左子樹右子樹OP_Code01234

基本體素

求并

求差

求交

裝配

CSG的發展歷史體素拼合操作

要求：參與運算的體素必須是正規集。運算必須封閉，即運算產生的結果依然是正規集。正規化處理

圖9.3AB產生的非正規點集

對參與運算的元素進行分類

圖9.4曲線段X相對于二維域S的分類

圖9.5按照正規分類原則，XonS=NULL體素拼合操作 設S是體素A和B的正規運算結果，則拼合算法等價于從已知的(XinA,XonA,XoutA)和(XinB,XonB,XoutB)求(XinS,XonS,XoutS)，或可以寫做：SMC(X,A<op>B)=combine(SMC(X,A),SMC(X,B),<op>)表9.2點對于拼合體A∩B的分類

當集合運算的結果有二義性時，利用鄰域進行測試

圖9.6利用鄰域判斷點的分類性質

對于A與B的交集SN(P,S)=N(P,A)∩N(P,B)三、八叉樹的變換操作對一棵八叉樹的平移、旋轉、比例等等變換可以通過對該樹的point數組中所含的坐標的變換而完成，樹中其余結點的位置可以通過這些參數而推算出來。

四、計算分析操作五、圖形顯示計算分析操作包括實體的體積、重心、面積等性質的計算。由于八叉樹表達的嚴格有序性，這些操作的實現得到方便。樹上的算法往往是通過遞歸完成的。

圖形顯示包括剪載、消隱、真實感顯示等操作。其中有些算法，如消隱等，可利用八叉樹的空間有序性，以從遠到近地遍歷樹的方法實現。而另一些算法，如線框圖的輪廓線的提取，則比較麻煩。

CSG應用分治(divide-and-conquer)算法

圖9.7適用分治算法的CSG樹節點組織

procedureClassLine3D(L,S)ifSisaprimitivethenClassLine3DWrtPrim(L,S)elseCombineLine3D(ClassLine3D(L,Left_S),ClassLine3D(L,Right_S),Op_S)9.3分解模型

八叉樹表達2.八叉樹的操作3.線性八叉樹

9.3.1八叉樹表達八叉樹概念圖9.8正方體及其八個子正方體

(a)一個實體

(b)所對應的八叉樹表示

圖9.9實體及其八叉樹表示

八叉樹的數據結構

typedefstructoctreetype{classtype/*Black,White,Grey*/class；intdepth；/*深度控制值*/structoctreetype*octree[8]；}octreetype；struct{pointtypepoint[8]；/*存放正方形八個頂點之座標*/octreetype*rootptr；}roothead；octreetype*octreeptr；octreetypeoctree；

9.3.2八叉樹的操作八叉樹的操作主要有八叉樹的生成，集合運算，變換操作，分析計算和圖形顯示。

一、八叉樹的生成程序make-tree調用兩個子程序classify和setson,兩個子程序的功能如下：1.classtypeclassify(primitive,tree)；該子程序比較實體基元primitive和以tree為根的八叉樹的相交關系，返回black,white和grey等三個值之一。2.setson(tree)；該子程序使得tree結點產生8個兒子。make-tree(primitive,tree,depth)primitivetype*primitive；octreetype*tree；intdepth；

classtypeb；inti；b=classify(primitive,tree)；switch(b){casewhite：tree->class=white；break；caseblack：tree->class=black；break；default：if(depth==0)tree->class=black；else{tree->class=grey；setson(tree)；for(i=0；i<8；i++)make-tree(primitive,tree->octree[i],depth-1)；}/*defaultend.*/}/*switchend.*/}程序9.1實體轉換為八叉樹算法

二、八叉樹的集合運算

八叉樹的集合運算，是指對兩棵八叉樹進行并、交、差的運算而產生一棵新的八叉樹。

考慮兩棵八叉樹求交的操作，算法思想如下：設n1、n2是求交的兩棵八叉樹中相同位置的對應結點，n3是求交后新樹中的對應結點。則求交規則為：1．如果n1,n2同為葉結點，則有：2.如果n1是葉結點，n2不是，則有：3.如果n1,n2同為非葉結點，則n1,n2,n3同時分解至兒子層再進行求交。

9.3.3線性八叉樹八叉樹的缺陷兩種改進方法： 1.黑葉結點法

2.括號葉結點法

一、黑葉結點法黑葉結點法只列出樹中黑色結點。方法是將八叉樹中所有結點按層次和次序編號。編號的數字位長代表深度、數字大小代表次序，如圖9.10所示。

圖9.10八叉樹結點的編號

二、括號葉結點法

括號葉結點法用括號表示層次，按從左到右的次序列出所有的葉結點，并按照黑、白分類。例如，對圖9.9所示的八叉樹，可以表示為下列線性表：（（WWWBWWWW）BWWW（WBWBWWWW）WW）這張表雖然長了一些，但每個元素只有3種變化，即只占2bit的存儲空間，因此也大壓縮了存儲空間。

9.4邊界模型邊界表示法(B-rep)也稱為邊界模型(BoundaryModel)。3種物體類型——小面(一個小面可以有幾條邊界曲線，只要它們定義一個連通的物體)、邊和頂點，以及和它們有聯系的幾何信息共同構成了邊界表示的基本元素。除了小面、邊和頂點坐標等幾何信息外，邊界表示還必須表示這些小面、邊和頂點的相互聯系。通常將實體的所有幾何信息稱做“幾何”，而將它們內部的連接信息稱做“拓撲”。

圖9.11邊界表示的對象實例

翼邊結構

圖9.12圖9.11的翼邊結構的一個例子

圖9.13完整的翼邊結構

9.5非傳統造型技術分形造型2.粒子系統9.5.1分形造型歐氏幾何的主要描述工具是直線、平滑的曲線、平面及邊界整齊的平滑曲面，這些工具在描述一些抽象圖形或人造物體的形態時是非常有力的，但對于一些復雜的自然景象形態就顯得無能為力了，諸如山、樹、草、火、云、波浪等。這是由于從歐氏幾何來看，它們是極端無規則的。為了解決復雜圖形生成問題，分形(Fractal)造型應運而生。

基本概念

HelgeVonKoch

的雪花圖形

Mandelbrot的一個海岸線例子

分數維

D=(logN)/log(1/S)分形造型對模型的基本要求⒈能逼真地“再現”自然景象。所謂逼真是指從視覺效果上逼真，“再現”即不要求完全一致。⒉模型不依賴于觀察距離。即距離遠時可給出大致輪廓和一般細節，距離近時能給出更豐富細節。⒊模型說明應盡量簡單，模型應具有數據放大能力。⒋模型應便于交互地修改。⒌圖形生成的效率要高。