第九章 基本造型方法

第九章基本造型方法9.1概述9.2結(jié)構(gòu)實(shí)體幾何模型（CSG）9.3分解模型9.4邊界模型9.5非傳統(tǒng)造型技術(shù)9.1概述設(shè)計(jì)對象所含的信息可以分為兩個部分：非視覺信息和視覺信息。圖9.1對象的信息

計(jì)算機(jī)內(nèi)對形狀信息的描述方法簡稱為造型（Modeling）的技術(shù)。造形技術(shù)主要由形狀表達(dá)和形狀操作兩個部分組成。1形狀表達(dá)的任務(wù)是將形狀的結(jié)構(gòu)用數(shù)據(jù)結(jié)構(gòu)模擬出來。這種描述形狀的數(shù)據(jù)結(jié)構(gòu)稱為模型（Model）。2形狀操作的任務(wù)是實(shí)現(xiàn)對模型的生成、修改、綜合、分析、計(jì)算、顯示等等操作，以便完成設(shè)計(jì)過程中的各種造型任務(wù)。

1．實(shí)體造型技術(shù)（SolidModeling）

2．曲面造型技術(shù)（SurfaceModeling）

3．非幾何形體的造型技術(shù)

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

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

9.2結(jié)構(gòu)實(shí)體幾何模型(CSG)

Wrench+/\cube3+/\+cube2/\cylinder1cube1圖9.2體素拼合實(shí)例

表9.1CSG節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)OP_Code操作碼transformprimitive坐標(biāo)變換基本體素left_Subtreeright_Subtree左子樹右子樹OP_Code01234

基本體素

求并

求差

求交

裝配

CSG的發(fā)展歷史體素拼合操作

要求：參與運(yùn)算的體素必須是正規(guī)集。運(yùn)算必須封閉，即運(yùn)算產(chǎn)生的結(jié)果依然是正規(guī)集。正規(guī)化處理

圖9.3AB產(chǎn)生的非正規(guī)點(diǎn)集

對參與運(yùn)算的元素進(jìn)行分類

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

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

當(dāng)集合運(yùn)算的結(jié)果有二義性時，利用鄰域進(jìn)行測試

圖9.6利用鄰域判斷點(diǎn)的分類性質(zhì)

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

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

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

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

圖9.7適用分治算法的CSG樹節(jié)點(diǎn)組織

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

八叉樹表達(dá)2.八叉樹的操作3.線性八叉樹

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

(a)一個實(shí)體

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

圖9.9實(shí)體及其八叉樹表示

八叉樹的數(shù)據(jù)結(jié)構(gòu)

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

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

一、八叉樹的生成程序make-tree調(diào)用兩個子程序classify和setson,兩個子程序的功能如下：1.classtypeclassify(primitive,tree)；該子程序比較實(shí)體基元primitive和以tree為根的八叉樹的相交關(guān)系，返回black,white和grey等三個值之一。2.setson(tree)；該子程序使得tree結(jié)點(diǎn)產(chǎn)生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實(shí)體轉(zhuǎn)換為八叉樹算法

二、八叉樹的集合運(yùn)算

八叉樹的集合運(yùn)算，是指對兩棵八叉樹進(jìn)行并、交、差的運(yùn)算而產(chǎn)生一棵新的八叉樹。

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

9.3.3線性八叉樹八叉樹的缺陷兩種改進(jìn)方法： 1.黑葉結(jié)點(diǎn)法

2.括號葉結(jié)點(diǎn)法

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

圖9.10八叉樹結(jié)點(diǎn)的編號

二、括號葉結(jié)點(diǎn)法

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

9.4邊界模型邊界表示法(B-rep)也稱為邊界模型(BoundaryModel)。3種物體類型——小面(一個小面可以有幾條邊界曲線，只要它們定義一個連通的物體)、邊和頂點(diǎn)，以及和它們有聯(lián)系的幾何信息共同構(gòu)成了邊界表示的基本元素。除了小面、邊和頂點(diǎn)坐標(biāo)等幾何信息外，邊界表示還必須表示這些小面、邊和頂點(diǎn)的相互聯(lián)系。通常將實(shí)體的所有幾何信息稱做“幾何”，而將它們內(nèi)部的連接信息稱做“拓?fù)洹薄?/p>

圖9.11邊界表示的對象實(shí)例

翼邊結(jié)構(gòu)

圖9.12圖9.11的翼邊結(jié)構(gòu)的一個例子

圖9.13完整的翼邊結(jié)構(gòu)

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

基本概念

HelgeVonKoch

的雪花圖形

Mandelbrot的一個海岸線例子

分?jǐn)?shù)維

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