第九章 基本造型方法

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

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

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

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

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

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

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

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左子樹(shù)右子樹(shù)OP_Code01234

基本體素

求并

求差

求交

裝配

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

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

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

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

圖9.4曲線(xiàn)段X相對(duì)于二維域S的分類(lèi)

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

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

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

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

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

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

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

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

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

八叉樹(shù)表達(dá)2.八叉樹(shù)的操作3.線(xiàn)性八叉樹(shù)

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

(a)一個(gè)實(shí)體

(b)所對(duì)應(yīng)的八叉樹(shù)表示

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

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

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

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

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

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

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

考慮兩棵八叉樹(shù)求交的操作，算法思想如下：設(shè)n1、n2是求交的兩棵八叉樹(shù)中相同位置的對(duì)應(yīng)結(jié)點(diǎn)，n3是求交后新樹(shù)中的對(duì)應(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同時(shí)分解至兒子層再進(jìn)行求交。

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

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

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

圖9.10八叉樹(shù)結(jié)點(diǎn)的編號(hào)

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

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

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

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

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

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

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

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

基本概念

HelgeVonKoch

的雪花圖形

Mandelbrot的一個(gè)海岸線(xiàn)例子

分?jǐn)?shù)維

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