形體在計(jì)算機(jī)內(nèi)的表示課件

3.5形體在計(jì)算機(jī)內(nèi)的表示蹩

?幾何造型

?形體表示

?邊界表示模型

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.5.1引言

?計(jì)算機(jī)中表示形體，通常用線(xiàn)框、表面和

實(shí)體三種模型。

?幾何造型歷史：早期的線(xiàn)框表示

實(shí)體造型與曲面造型70'

獨(dú)立發(fā)展到互相溶合

NURBS+邊界表示

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

正則形體

?對(duì)于任一形體，如果它是3維歐氏空間中

非空、有界的封閉子集，且其邊界是二

維流形（即該形體是連通的），我們稱(chēng)

該形體為正則形體，否則稱(chēng)為非正則形

體。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

一些非正則形體的實(shí)例

(c)一條邊有兩個(gè)以上

(a)有懸面(b)有懸邊的鄰面(不連通)

圖3.2.1非正則形體實(shí)例

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-集合運(yùn)算（并、交、差）是構(gòu)造形體的

基本方法。正則形體經(jīng)過(guò)集合運(yùn)算后，

可能會(huì)產(chǎn)生懸邊、懸面等低于三維的形

體。

?Requicha在引入正則形體概念的同時(shí)，還

定義了正則集合運(yùn)算的概念。正則集合

運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則

形體，即丟棄懸邊、懸面等。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

集合運(yùn)算舉列

懸邊

C=AABC*=An*B

集合論的求交計(jì)算正則集合下的求交運(yùn)算

圖3.2.2二個(gè)二維圖形的交產(chǎn)圖3.2.3集合和正則的交運(yùn)算

生一個(gè)退化的結(jié)果

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?為了能夠處理非正則形體，產(chǎn)生了非正

則造型技術(shù)。

?九十年代以來(lái)，基于約束的參數(shù)化、變

量化造型和支持線(xiàn)框、曲面、實(shí)體統(tǒng)一

表示的非正則形體造型技術(shù)已成為幾何

造型技術(shù)的主流。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

352形體表示模型I?

在實(shí)體模型的表示中，基本上可以分

為分解表示、構(gòu)造表示和邊界表示三大類(lèi)。

1、分解表示

將形體按某種規(guī)則分解為小的更易于描述的部分，每

一小部分又可分為更小的部分，這種分解過(guò)程直至每

一小部分都能夠直接描述為止。

(a)將形體空間細(xì)分為小的立方體單元。這種表示方

法的優(yōu)點(diǎn)是簡(jiǎn)單，容易實(shí)現(xiàn)形體的交、并、差計(jì)算，

但是占用的存儲(chǔ)量太大，物體的邊界面沒(méi)有顯式的解

析表達(dá)式，不便于運(yùn)算。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

（b）八叉樹(shù)法表示形體.首先對(duì)形體定義一個(gè)外接立方

體，再把它分解成八個(gè)子立方體，并對(duì)立方體依次

編號(hào)為0,1,2,???,7o如果子立方體單元已經(jīng)一

致，即為滿(mǎn)（該立方體充滿(mǎn)形體）或?yàn)榭眨](méi)有形

體在其中），則該子立方體可停止分解；否則，需

要對(duì)該立方體作進(jìn)一步分解，再一分為八個(gè)子立方

體。在八叉樹(shù)中，非葉結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)都有八個(gè)分

支。

優(yōu)點(diǎn)主要是：

（1）形體表示的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(2)簡(jiǎn)化了形體的集合運(yùn)算。只需同時(shí)遍歷參加

集合運(yùn)算的兩形體相應(yīng)的八叉樹(shù)，無(wú)需進(jìn)行復(fù)雜的

求交運(yùn)算。

(3)簡(jiǎn)化了隱藏線(xiàn)(或面)的消除，因?yàn)樵诎瞬?/p>

樹(shù)表示中，形體上各元素已按空間位置排成了一定

的順序。

(4)分析算法適合于并行處理。

八叉樹(shù)表示的缺點(diǎn)：占用的存儲(chǔ)多，只能近似表示

形體，以及不易獲取形體的邊界信息等。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

具有子孫的節(jié)點(diǎn)

空節(jié)點(diǎn)

實(shí)節(jié)點(diǎn)

清華大學(xué)圖3.2.4用八叉樹(shù)表示形體十算機(jī)圖形學(xué)基礎(chǔ)

2.構(gòu)造表示。通常有掃描表示、構(gòu)造實(shí)體

幾何表示和特征表示三種。

(a)掃描表示?；谝粋€(gè)基體(一般是一個(gè)封

閉的平面輪廓)沿某一路徑運(yùn)動(dòng)而產(chǎn)生形體,

?掃描是生成三維形體的有效方法

?用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問(wèn)

題。

?掃描方法不能直接獲取形體的邊界信息，表示形

體的覆蓋域非常有限。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(a)(b)

回轉(zhuǎn)軸

(c)(d)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

圖3.2.5生成掃描形體的例子

圖3.2.6生成掃描體時(shí)維數(shù)不

一致的情況

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(b)構(gòu)造實(shí)體幾何表示(CSG).通過(guò)對(duì)體素定義

運(yùn)算而得到新的形體的一種表示方法。體素

可以是立方體、圓柱、圓錐等，也可以是半

空間，其運(yùn)算為變換或正則集合運(yùn)算并、交

差。

CSG表示可以看成是一棵有序的二叉樹(shù)。

?其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。

?非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換(平

移和/或旋轉(zhuǎn))操作，這種運(yùn)算或變換只對(duì)其緊

接著的子結(jié)點(diǎn)(子形體)起作用。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

圖3.2.7CSG表示

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?CSGM是無(wú)二義性的，但不是唯一的.

CSG表示的優(yōu)點(diǎn)：

?數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)

的管理比較容易；

?CSG表示可方便地轉(zhuǎn)換成邊界(Brep)表示；

?CSG方法表示的形體的形狀，比較容易修改。

CSG表示的缺點(diǎn)：

?對(duì)形體的表示受體素的種類(lèi)和對(duì)體素操作的種

類(lèi)的限制，也就是說(shuō)，CSG方法表示形體的覆蓋

域有較大的局限性。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?對(duì)形體的局部操作不易實(shí)現(xiàn)，例如，不能對(duì)基

本體素的交線(xiàn)倒圓角；

?由于形體的邊界幾何元素（點(diǎn)、邊、面）是隱含

地表示在CSG中，故顯示與繪制CSG表示的形體需

要較長(zhǎng)的時(shí)間。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(c)特征表示

-從應(yīng)用層來(lái)定義形體，因而可以較好的表達(dá)

設(shè)計(jì)者的意圖。從功能上可分為形狀、精度、

材料和技術(shù)特征。

-特征是面向應(yīng)用、面向用戶(hù)的。特征模型的

表示仍然要通過(guò)傳統(tǒng)的幾何造型系統(tǒng)來(lái)實(shí)現(xiàn)。

不同的應(yīng)用領(lǐng)域，具有不同的應(yīng)用特征。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并

不能直接得到特征的幾何元素信息，而在對(duì)

特征及在特征之間進(jìn)行操作時(shí)需要這些信息。

-特征方法表示形體的覆蓋域受限于特征的種

類(lèi)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

用戶(hù)特征造型器(特征模型J

幾何造型器幾何模型(b)圓柱(c)圓錐

圖3.2.9特征形狀表示

圖3.2.8基于特征的造型系統(tǒng)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?構(gòu)造表示的特點(diǎn)：

-構(gòu)造表示通常具有不便于直接獲取形體幾何

元素的信息、覆蓋域有限等缺點(diǎn)，

-但是，便于用戶(hù)輸入形體，在CAD/CAM系統(tǒng)

中，通常作為輔助表示方法。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.邊界表示(BR表示或BRep表示)

-按照體一面一環(huán)一邊一點(diǎn)的層次，詳細(xì)記錄

了構(gòu)成形體的所有幾何元素的幾何信息及其相

互連接的拓?fù)潢P(guān)系。

-邊界表示的一個(gè)重要特點(diǎn)是在該表示法中，

描述形體的信息包括幾何信息(Geometry)和

拓?fù)湫畔?Topology)兩個(gè)方面。

?拓?fù)湫畔⒚枋鲂误w上的頂點(diǎn)、邊、面的連接關(guān)系，

拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。

?形體的幾何信息猶如附著在“骨架”上的肌肉。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

Brep表示的優(yōu)點(diǎn)是：

-表示形體的點(diǎn)、邊、面等幾何元素是顯式表

示的，使得繪制Brep表示的形體的速度較快,

而且比較容易確定幾何元素間的連接關(guān)系；

-容易支持對(duì)物體的各種局部操作，比如進(jìn)行

倒角。

-便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如

精度、表面粗糙度等。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?Brep表布於

-數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)

內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；

-Brep表示不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)

用歐拉操作來(lái)保證Brep表示形體的有效性、正

則性等。

?Brep表示覆蓋域大，原則上能表示所有的

形體，而且易于支持形體的特征表示等，

Brep表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表

示方港在大學(xué)

計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?CSG與邊界表示成為兩大主流方法

80'

ACMSolidmodeling歐洲CSG會(huì)議

?邊界表示一統(tǒng)天下

歐洲ICSG會(huì)議一＞亞州GMP

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

353形體的邊界表示模型

3.5.3.1邊界表示的基本實(shí)體

?邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括：

1.頂點(diǎn)

2.邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)

來(lái)界定。邊的形狀（Curve）由邊的幾何信

息來(lái)表示，可以是直線(xiàn)或曲線(xiàn)，曲線(xiàn)邊可用

一系列控制點(diǎn)或型值點(diǎn)來(lái)描述，也可用顯式、

隱式或參數(shù)方程來(lái)描述。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.環(huán)。環(huán)(Loop)是有序、有向邊(Edge)

組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外

環(huán)邊通常按逆時(shí)針?lè)较蚺判?，?nèi)環(huán)邊通常按

順時(shí)針?lè)较蚺判颉?/p>

4.面。面(Face)由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)

(可以沒(méi)有內(nèi)環(huán))來(lái)表示，內(nèi)環(huán)完全在外環(huán)

之內(nèi)。

?若一個(gè)面的外法矢向外，稱(chēng)為正向面；反之，稱(chēng)

為反向面。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?面的形狀可以是平面或曲面。平面可用平

面方程來(lái)描述，曲面可用控制多邊形或型

值點(diǎn)來(lái)描述，也可用曲面方程(隱式、顯

式或參數(shù)形式)來(lái)描述。對(duì)于參數(shù)曲面，

通常在其二維參數(shù)域上定義環(huán)，這樣就可

由一些二維的有向邊來(lái)表示環(huán)，集合運(yùn)算

中對(duì)面的分割也可在二維參數(shù)域上進(jìn)行。

5.體。體(Body)是面的并集。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.5.3.2邊界表示的數(shù)據(jù)結(jié)構(gòu)

?翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，由美國(guó)斯坦

福大學(xué)Baumgart作為多面體的表示模式

提出。

-它用指針記錄了每一邊的兩個(gè)鄰面（即左外

環(huán)和右外環(huán)）、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的

兩個(gè)鄰邊（即左上邊、左下邊、右上邊和右

下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是

完備的，但它不能表示帶有精確曲面邊界的

實(shí)體。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

圖3.2.n翼邊數(shù)據(jù)結(jié)構(gòu)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?輻射邊：為了表示非正則形體，1986年，

Weiler提出了輻射邊(RadialEdge)數(shù)據(jù)結(jié)構(gòu)。

-輻射邊結(jié)構(gòu)的形體模型由幾何信息和拓?fù)湫畔?/p>

兩部分組成。

?幾何信息有面(face)、環(huán)(loop)、邊(edge)和

點(diǎn)(vertex)

?拓?fù)湫畔⒂心Ｐ?model)＞區(qū)域(region)＞外殼

(shell)、面引用(faceuse)、環(huán)引用(loopuse)、

邊引用(edgeuse)和點(diǎn)引用(vertexuse)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?點(diǎn)是三維空間的一個(gè)位置

-邊可以是直線(xiàn)邊或曲線(xiàn)邊，邊的端點(diǎn)可以重合。

?環(huán)是由首尾相接的一些邊組成，而且最后一條邊的終

點(diǎn)與第一條邊的起點(diǎn)重合；環(huán)也可以是一個(gè)孤立點(diǎn)。

外殼是一些點(diǎn)、邊、環(huán)、面的集合；

?外殼是一些點(diǎn)、邊、環(huán)、面的集合。

?區(qū)域由一組外殼組成。

?模型由區(qū)域組成。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

model

■

region

二二二=shell

,

faceuse----?face

,

廠-Aloopuse----?loop

-r…Aedgeuse?----?edge

M

V

:二；vertexuse——?vertex

topologygeometry

圖3.2.12輻射邊數(shù)據(jù)結(jié)構(gòu)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?清華大學(xué)開(kāi)發(fā)的幾何造型系統(tǒng)GEMS5.0中，米用的數(shù)據(jù)結(jié)構(gòu)如圖

?歐拉操作選讀

?集合運(yùn)算選讀

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.5.33歐拉操作

?對(duì)于任意的簡(jiǎn)單多面體，其面⑴、邊⑹、

頂點(diǎn)(v)的數(shù)目滿(mǎn)足歐拉公式

v-e+f=2

?對(duì)于任意的正則形體，引入形體的其它

幾個(gè)參數(shù)：形體所有面上的內(nèi)孔總數(shù)⑺、

穿透形體的孔洞數(shù)(h)和形體非連通部分

總數(shù)(s),則形體滿(mǎn)足公式：

v-e+f=2(s-h)+r

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

■修改過(guò)程中保證各幾何元素的數(shù)目保持這個(gè)關(guān)系式不變，

這一套操作就是歐拉操作。

?最為常用的幾種歐拉操作有：

(l)mvsf(v,f),生成含有一個(gè)點(diǎn)的面，并且構(gòu)成一個(gè)新的體。

(2)kvsf,刪除一個(gè)體，該體僅含有…個(gè)點(diǎn)的面。

⑶mev(vl,v2,e),生成一個(gè)新的點(diǎn)v2,連接該點(diǎn)到已有的點(diǎn)

vl,構(gòu)成一條新的邊。

(4)kev(e,v),刪除一條邊e和該邊的一個(gè)端點(diǎn)v。

(5)mef(vl,v2,fl,f2,e),連接面fl上的兩個(gè)點(diǎn)vl、v2,生成一

條新的邊e,并產(chǎn)生一個(gè)新的面。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(6)kef(e),刪除一條邊e和該邊的一個(gè)鄰面f。

(7)kemr(e),刪除一條邊e,生成該邊某一鄰面上的一新的

內(nèi)環(huán)。

(8)mekr(vl,v2,e),連接兩個(gè)點(diǎn)vl、v2,生成一條新的邊e,

并刪除掉vl和v2所在面上的一個(gè)內(nèi)環(huán)。

(9)kfmrh(fl,f2),刪除與面fl相接觸的一個(gè)面f2,生成面fl

上的一個(gè)內(nèi)環(huán)，并形成體上的一個(gè)通孔。

(10)mfkrh(fl,f2),刪除面fl上的一個(gè)內(nèi)環(huán)，生成一個(gè)新的

面f2,由此也刪除了體上的一個(gè)通孔。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

為了方便對(duì)形體的修改，還定義了兩個(gè)輔助的操作：

公共端點(diǎn)。

(ll)semv(el,v,e2),將邊el分割成兩段，生成一個(gè)新的點(diǎn)v

而一條新的邊e2。

(12)jekv(el,e2),合并兩條相鄰的邊el、e2,刪除它們的

公共端點(diǎn)。

?以上十種歐拉操作和兩個(gè)輔助操作，每?jī)蓚€(gè)一組，構(gòu)

成了六組互為可逆的操作。

?可以證明：歐拉操作是有效的，即用歐拉操作對(duì)形體

操作的結(jié)果在物理上是可實(shí)現(xiàn)的；歐拉操作是完備的

即任何形體都可用有限步驟的歐拉操作構(gòu)造出來(lái)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.534集合運(yùn)算

?正則集與正則集合運(yùn)算算子

-規(guī)定正則形體是三維歐氏空間中的正則集合，

因此可以將正則幾何形體描述如下：

設(shè)G是三維歐氏空間中的一個(gè)有界區(qū)域，且6=

bGUiG,其中bG是G的n—1維邊界，iG是G的內(nèi)部。

G的補(bǔ)空間cG稱(chēng)為G的外部，此時(shí)正則形體G需滿(mǎn)足:

(1)bG將iG和cG分為兩個(gè)互不連通的子空間；

(2)bG中的任意一點(diǎn)可以使iG和bG連通；

(3)bG中任一點(diǎn)存在切平面，其法矢指向cG子空間

(4)bG是二維流形。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?設(shè)〈OP〉是集合運(yùn)算算子（交、并或差），R3中

任意兩個(gè)正則形體A、B作集合運(yùn)算：

R=A<0P>B

運(yùn)算結(jié)果R仍是R3中的正則形體，則稱(chēng)〈0P〉為正

則集合算子。

正則并、正則交、正則差分別記為U*,C*、-*

?分類(lèi)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?Tilove對(duì)分類(lèi)問(wèn)題的定義為：設(shè)S為待分

類(lèi)元素組成的集合，G為一正則集合，則

S相對(duì)于G的成員分類(lèi)函數(shù)為：

C(S,G)={SinG,SoutG,SonG

其中，

SinG=SAiG,

SoutG=SAcG,

SonG=SnbG,

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?集合運(yùn)算算法

包括以下幾部分：

⑴求交：參與運(yùn)算的一個(gè)形體的各拓?fù)湓厍蠼?，求?/p>

的順序采用低維元素向高維元素進(jìn)行。用求交結(jié)果產(chǎn)

生的新元素（維數(shù)低于參與求交的元素）對(duì)求交元素

進(jìn)行劃分，形成一些子元素。

⑵成環(huán)：由求交得到的交線(xiàn)將原形體的面進(jìn)行分割，形

成一些新的面環(huán)。再加上原形體的懸邊、懸點(diǎn)經(jīng)求交

后得到的各子拓?fù)湓?，形成一拓?fù)湓厣杉?/p>

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(3)分類(lèi)：對(duì)形成的拓?fù)湓厣杉械拿恳煌負(fù)湓兀?/p>

取其上的一個(gè)代表點(diǎn)，根據(jù)點(diǎn)/體分類(lèi)的原則，決定該

點(diǎn)相對(duì)于另一形體的位置關(guān)系，同時(shí)考慮該點(diǎn)代表的

拓?fù)湓氐念?lèi)型(即其維數(shù))，來(lái)決定該拓?fù)湓叵?/p>

對(duì)于另一形體的分類(lèi)關(guān)系。

(4)取舍：根據(jù)拓?fù)湓氐念?lèi)型及其相對(duì)另一形體的分類(lèi)

關(guān)系，按照集合運(yùn)算的運(yùn)算符要求，決定拓?fù)湓厥?/p>

保留還是舍去；保留的拓?fù)湓匦纬梢粋€(gè)保留集。

⑸合并：對(duì)保留集中同類(lèi)型可合并的拓?fù)湓剡M(jìn)行合并,

包括面環(huán)的合并和邊的合并。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

(6)拼接：以拓?fù)湓氐墓蚕磉吔缱鳛槠溥B接標(biāo)志，按照

從高維到低維的順序，收集分類(lèi)后保留的拓?fù)湓兀?/p>

形成結(jié)果形體的邊界表示數(shù)據(jù)結(jié)構(gòu)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.6歸類(lèi)求交

?幾何造型中，通常利用集合運(yùn)算（并、交、差

運(yùn)算）實(shí)現(xiàn)復(fù)雜形體的構(gòu)造。集合運(yùn)算需要大

量的求交運(yùn)算。

?如何提高求交的實(shí)用性、穩(wěn)定性、速度、精度

等，對(duì)幾何造型系統(tǒng)至關(guān)重要。

?歷史上的觀念變化:簡(jiǎn)單體素的精確求交，

->NURBS統(tǒng)一求交->歸類(lèi)求交

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.6.1求交分類(lèi)簡(jiǎn)介

?多面體模型

-這種模型的求交計(jì)算主要是線(xiàn)段和平面的求交，求交

問(wèn)題的解決相對(duì)簡(jiǎn)單。

-多面體模型的缺點(diǎn)是明顯的。它只能近似表示形體，

同時(shí)，復(fù)雜形體表面的離散會(huì)帶來(lái)巨大的數(shù)據(jù)量。

?CSG模型

-在這種模型中，形體通過(guò)基本體素的組合來(lái)實(shí)現(xiàn)。二

次曲面的求交是這些造型系統(tǒng)中必不可少的。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

■當(dāng)前的幾何造型系統(tǒng)，大多采用精確的

邊界表示模型。

-在這種表示法中，形體的邊界元素和某類(lèi)幾何元素

相對(duì)應(yīng)，它們可以是直線(xiàn)、圓（圓?。?、二次曲線(xiàn)

Bezier曲線(xiàn)、B樣條曲線(xiàn)等，也可以是平面、球面、

二次曲面、Bezier曲面、B樣條曲面等，求交情況

十分復(fù)雜。

-二次曲面與各種自由曲面并存的混合表示模型的采

用，導(dǎo)致了歸類(lèi)求交思想的產(chǎn)生。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?“無(wú)處不在的求交”：GEMS實(shí)例!

令GEMS5.0-[Parti.PART]

與文件（E）州怎）海力MD版金（由快速成件0）工具⑥￡WM帆@/J1X1

1a涔61宿|叩川**|住a，5［?@@Q皎?聯(lián)卜際電險(xiǎn)際|

臣叵旬田園園⑨傷!⑦iL/］Wh?，.3〕曉g窟等口威名佇◎用意申於|屈|仁?|

jm幽。能|唐鄉(xiāng)喜沿?魏|］梟］蜃;場(chǎng)［解匐.

\

平

囪13

、2

平

因

<、

平

團(tuán)3

、

L原

總

e懸

體-

槽

痘T4、

梢

痘m

-is

Lil

如需幫助，語(yǔ)報(bào)Fl鍵

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?實(shí)體建模步驟剖析：

-草圖

—拉伸、填“體、面、環(huán)、點(diǎn)”結(jié)構(gòu)

-打孔，直徑為20cm:圓柱與立方體的所有面

求交線(xiàn)，成環(huán)、重填“體面環(huán)點(diǎn)”結(jié)構(gòu)

-打第二個(gè)孔，直徑為18cm:圓柱與立方體的

所有面、及第一個(gè)圓柱面求交線(xiàn)，成環(huán)、重

填“體面環(huán)點(diǎn)”結(jié)構(gòu)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.6.2歸類(lèi)求交策略

用到的幾何元素：（25種）

—點(diǎn)：3D點(diǎn)°

-線(xiàn)：3D直線(xiàn)段、二次曲線(xiàn)（包括圓弧和整圓、橢

圓弧和橢圓、拋物線(xiàn)段、雙曲線(xiàn)段）、Bezier曲

線(xiàn)（有理和非有理）、B樣條曲線(xiàn)、NURBS曲線(xiàn)。

-面：平面、二次曲面（包括球面、圓柱面、圓錐/

臺(tái)面、雙曲面、拋物面、橢球面和橢圓柱面）、

Bezier曲面（有理和非有理）、B樣條曲面、

NURBS曲面。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?將幾何元素進(jìn)行歸類(lèi)，利用同一類(lèi)元素

之間的共性來(lái)研究求交算法。同時(shí)對(duì)每

一類(lèi)元素，在具體求交算法中要考慮它

們的特性，以提高算法的效率，發(fā)揮混

合表示方法的優(yōu)勢(shì)。

?求交方法可分為：點(diǎn)點(diǎn)、點(diǎn)線(xiàn)、點(diǎn)面、

線(xiàn)線(xiàn)、線(xiàn)面六種。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?清華大學(xué)的GEMS5.0系統(tǒng)采用

-點(diǎn)、直線(xiàn)、平面、二次曲線(xiàn)等簡(jiǎn)單的幾何元素之間

的求交

-直線(xiàn)、平面、二次曲線(xiàn)等簡(jiǎn)單的幾何元素與二次曲

面之間的求交

-三維點(diǎn)與二次曲線(xiàn)/曲面之間的求交

—三維點(diǎn)與自由曲線(xiàn)、曲面之間的求交

-二次曲面與二次曲面之間的求交

-直線(xiàn)一自由曲線(xiàn)/自由曲面的求交

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-平面一自由曲線(xiàn)/自由曲面的求交

-自由曲線(xiàn)一自由曲線(xiàn)的求交

-自由曲線(xiàn)一自由曲面的求交

-二次曲線(xiàn)一自由曲線(xiàn)的求交

-二次曲線(xiàn)一自由曲面的求交

-自由曲面一自由曲面的求交

-二次曲面一自由曲線(xiàn)的求交

-二次曲面一自由曲面的求交

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

363基本的求交算法

?曲線(xiàn)曲面求交的基本方法主要有：

-代數(shù)方法

-幾何方法

-離散方法

-跟蹤方法

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

1.代數(shù)方法

-利用代數(shù)運(yùn)算，特別是求解代數(shù)方程的方法

求出曲面的交線(xiàn)。

-根據(jù)參與求交的兩曲面的表示形式的不同，

可以把求交分為三種情況。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?隱式表示和參數(shù)表示的曲面求交，通過(guò)把參數(shù)方

程代入隱式方程的方法，可以將交線(xiàn)表示為

g(u,v)=O的形式。此時(shí)得到的交線(xiàn)方程是平面代

數(shù)曲線(xiàn)方程，可根據(jù)平面代數(shù)曲線(xiàn)理論的方法求

解交線(xiàn)。

?兩個(gè)曲面都是參數(shù)表示的情形，只需要將其中之

一隱式化，然后用前面的方法求解。而參數(shù)多項(xiàng)

式或有理多項(xiàng)式曲面的隱式化通過(guò)消元來(lái)實(shí)現(xiàn)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?兩個(gè)曲面都是隱式曲面。一種方法是將其中一個(gè)

曲面參數(shù)化，然后用第一種情況來(lái)求解。但是，

一般情況下這種參數(shù)化很困難，對(duì)于某些情況可

以采用另外的方法計(jì)算參數(shù)化的曲面。

代數(shù)法的弱點(diǎn)是對(duì)誤差很敏感

?這是因?yàn)榇鷶?shù)法經(jīng)常需要判別某些量是否大于零

等于零或小于零，而在計(jì)算機(jī)中的浮點(diǎn)數(shù)近似表

示的誤差常常會(huì)使這種判別出現(xiàn)錯(cuò)誤。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?代數(shù)法實(shí)例：

-園與橢圓求交，化為求解4次方程，有公式

解。

-園與圓環(huán)求交，化為求解8次方程，迭代求

解。

-8次方程達(dá)到求解，不穩(wěn)定。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

2.幾何方法

-利用幾何的方法，對(duì)參與求交的曲面的形狀

大小、相互位置以及方向等進(jìn)行計(jì)算和判斷,

識(shí)別出交線(xiàn)的形狀和類(lèi)型，從而可精確求出

交線(xiàn)。

-幾何求交適應(yīng)性不是很廣，一般僅用于平面

以及二次曲面等簡(jiǎn)單曲面的求交

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-對(duì)于一些交線(xiàn)退化或相切的情形，交線(xiàn)往往

是點(diǎn)、直線(xiàn)或圓錐曲線(xiàn)，用幾何方法求交可

以更加迅速和可靠。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?幾何法實(shí)例：平面與圓柱求交

1.平面、圓柱參數(shù)的合法性檢查

2.平面變換到圓柱的局部坐標(biāo)系

3,幾何求交：

①如果平面與圓柱平行，不交或交于兩條

直線(xiàn)

②如果平面與圓柱垂直，不交或交于一個(gè)

圓

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.離散方法

-離散方法求交是利用分割的方法，將

曲面不斷離散成較小的曲面片，直到

每一子曲面片均可用比較簡(jiǎn)單的面片

然后用這些簡(jiǎn)單面片求交得一系列交

線(xiàn)段，連接這些交線(xiàn)段即得到精確交

線(xiàn)的近似結(jié)果。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?離散求交一般包括下面的過(guò)程：用包圍

盒作分離性檢查排除無(wú)交區(qū)域；根據(jù)平

坦性檢查判斷是否終止離散過(guò)程；連接

求出的交線(xiàn)段作為求交結(jié)果。

?由于Bezier曲面，B樣條曲面具有離散性

質(zhì)，使得它們最適合于離散法求交。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?缺點(diǎn)：

-離散法求出的交線(xiàn)逼近精度不高。如果要求

的精度較高，需要增加離散層數(shù)。這將大大

增加了數(shù)據(jù)儲(chǔ)存量和計(jì)算量。

-處于不同離散層數(shù)的相鄰子曲面片，由它們

產(chǎn)生的交線(xiàn)段可能會(huì)出現(xiàn)裂縫。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?高度估計(jì)問(wèn)題

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

4.跟蹤方法

-通過(guò)先求出初始交點(diǎn)，然后從已知的初始交

點(diǎn)出發(fā)，相繼跟蹤計(jì)算出下一交點(diǎn)，從而求

出整條交線(xiàn)的方法。

-跟蹤法的本質(zhì)是構(gòu)造交線(xiàn)滿(mǎn)足的微分方程組

先求出滿(mǎn)足方程組的某個(gè)某個(gè)初值解，通過(guò)

數(shù)值求解微分方程組的方法來(lái)計(jì)算整個(gè)交線(xiàn)

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-跟蹤方法在計(jì)算相繼交點(diǎn)的時(shí)候，利用了曲

面的局部微分性質(zhì)，一般采用數(shù)值迭代的方

法求解，使得計(jì)算效率較高。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?跟蹤法求交中考慮的主要問(wèn)題包括：

-如何求出初始交點(diǎn)并保證每一交線(xiàn)分支都有

初始交點(diǎn)被求出；

-如何計(jì)算奇異情況下的跟蹤方向以及合理選

取跟蹤的前進(jìn)步長(zhǎng)；

-如何處理相切的情況。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?跟蹤法實(shí)例：MAF方法

-曲線(xiàn)一曲線(xiàn)求交

?近似交點(diǎn)，

?切線(xiàn)求交，

?投影

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

MAF與Newton法的比較

?Newton法

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

MAF與Newton法的比較

?MAF法

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

假設(shè)尸&）為初始交點(diǎn)，。為兩切線(xiàn)的交點(diǎn)；由于

Q在曲線(xiàn)P。）在尸&）的切線(xiàn)上，有

0=P（，0）+9&）.4

于是

（0-尸1））。尸&）

ZA4一

儼"。）11

由此得到新交點(diǎn)尸（0+A。，如此反復(fù)迭代。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.7實(shí)體造型系統(tǒng)簡(jiǎn)介

?在早期開(kāi)發(fā)的實(shí)體造型系統(tǒng)中，值得提及的是

劍橋大學(xué)的BUILD-1系統(tǒng)。

?該研究小組的一部分人組建了ShapeData公司，

并開(kāi)發(fā)出實(shí)體造型系統(tǒng)Romulus,Romulus孕育

了最著名的兩個(gè)實(shí)體造型系統(tǒng)開(kāi)發(fā)環(huán)境：

Parasolid和ACIS。

?3.7.1Parasolid系統(tǒng)：Solidworks

?3.7.2ACIS系統(tǒng)：Autodesk,Solidedge

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.7.1.1Parasolid的主要功能

?Parasolid有較強(qiáng)的造型功能，但是只能支

持正則實(shí)體造型。主要功能包括：

-1.Parasolid采用自由曲面和解析曲面的混合

表示，共提供了10種標(biāo)準(zhǔn)的曲面類(lèi)型和7種標(biāo)

準(zhǔn)的曲線(xiàn)類(lèi)型，并且是完全集成的。

-2.Parasolid可用簡(jiǎn)單的方法生成復(fù)雜的實(shí)體,

實(shí)體之間可有多種方式的操作。

-3.用戶(hù)可用自己理解的工程特征進(jìn)行設(shè)計(jì)

-4.能夠提供非拓?fù)浜头菐缀螖?shù)據(jù)，稱(chēng)為屬性

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

屬性包括系統(tǒng)定義的屬性和用戶(hù)定義的屬性

兩種，且依附于模型實(shí)體(Entities)o

5.支持局部操作。包括：改變面幾何、變換

面幾何、使面成錐形、擺動(dòng)面、掃描面及刪

除面。提供了多半徑、變半徑的過(guò)渡功能。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.7.1.2Parasolid的模型結(jié)構(gòu)

?模型實(shí)體包括三種：

拓?fù)?、幾何和相關(guān)數(shù)據(jù)

圖3.4.1核心模型的實(shí)體

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

?1.拓?fù)鋵?shí)體

-(1)體(Body)：Parasolid模型通常包括一個(gè)

或多個(gè)體(Bodies)

-(2)殼(Shell)：殼是實(shí)體(Solid)和空氣之

間封閉的邊界

-(3)面(Face)、邊(Edge)和頂點(diǎn)(Vetex)

-(4)翼(Fin)：翼(Fins)表示一*條邊的一*側(cè)

每一條邊有一個(gè)左翼和一個(gè)右翼

-(5)環(huán)(Loop)：由一個(gè)面上封閉的翼組成。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-(7)裝配件(Assembly)和實(shí)例(Instance)：

一個(gè)裝配件是一個(gè)對(duì)其它裝配件或體的指針的集

合。每一個(gè)指針被稱(chēng)為一個(gè)實(shí)例。

-(8)世界(World)：世界是一個(gè)獨(dú)特的實(shí)體

(Entity),它包含模型中的所有的體(Bodies)

和裝配件(Assemblies)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

2.幾何實(shí)體（Entities）

-點(diǎn)。主要依附于頂點(diǎn)，它們也依附于體和裝

配件作為構(gòu)造幾何。

-曲線(xiàn)。主要依附于面，但也依附于體和裝配

件作為構(gòu)造幾何。

-曲面。主要依附于模型的邊或翼，但也依附

于體和裝配件作為構(gòu)造幾何。

-變換。變換表示幾何操作：平移、修剪等，

主要依附于實(shí)例。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.相關(guān)的數(shù)據(jù)實(shí)體

-(1)特征(feature)：是實(shí)體的集合，依附

于體和裝配件。

-(2)表(List)：提供了結(jié)構(gòu)化數(shù)據(jù)的方法，

它們一般獨(dú)立使用，也可依附于體和裝配件。

表有三種：整數(shù)表(Integer)、實(shí)數(shù)表(Real)

和標(biāo)志表(Tag)o

-(3)屬性(Attribute)：是用于附著信息到實(shí)

體的數(shù)據(jù)結(jié)構(gòu)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

3.7.1.3Parasolid的界面

?Parasolid有兩個(gè)界面。

-一個(gè)在造型器頂部，稱(chēng)為核心界面(KI),

通過(guò)KL用戶(hù)可以造型、操作對(duì)象和控制造

型器。

-另一個(gè)在造型器下部，它包括三個(gè)部分：

Frustrum、GO(GraphicsOutput)和FG

(ForeignGeometry)。

清華大學(xué)計(jì)算機(jī)圖形學(xué)基礎(chǔ)

-Frustrum：Frust