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

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

?幾何造型

?形體表示

?邊界表示模型

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

3.5.1引言

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

實(shí)體三種模型。

?幾何造型歷史：早期的線框表示

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

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

NURBS+邊界表示

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

正則形體

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

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

維流形（即該形體是連通的），我們稱

該形體為正則形體，否則稱為非正則形

體。

清華大學(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ù)化、變

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

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

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

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

352形體表示模型I?

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

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

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)一

致，即為滿（該立方體充滿形體）或?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)化了隱藏線(或面)的消除，因?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ì)形體的表示受體素的種類和對(duì)體素操作的種

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

域有較大的局限性。

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

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

本體素的交線倒圓角；

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

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

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

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

(c)特征表示

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

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

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

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

表示仍然要通過(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í)需要這些信息。

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

類。

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

用戶特征造型器(特征模型J

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

圖3.2.9特征形狀表示

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

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

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

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

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

-但是，便于用戶輸入形體，在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)表示，可以是直線或曲線，曲線邊可用

一系列控制點(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è)面的外法矢向外，稱為正向面；反之，稱

為反向面。

清華大學(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è)位置

-邊可以是直線邊或曲線邊，邊的端點(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ù)目滿足歐拉公式

v-e+f=2

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

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

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

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

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稱為G的外部，此時(shí)正則形體G需滿足:

(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中的正則形體，則稱〈0P〉為正

則集合算子。

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

?分類

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

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

類元素組成的集合，G為一正則集合，則

S相對(duì)于G的成員分類函數(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)：由求交得到的交線將原形體的面進(jìn)行分割，形

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

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

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

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

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

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

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

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

(4)取舍：根據(jù)拓?fù)湓氐念愋图捌湎鄬?duì)另一形體的分類

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

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

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

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

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

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

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

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

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

3.6歸類求交

?幾何造型中，通常利用集合運(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)一求交->歸類求交

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

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

?多面體模型

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

問(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)，大多采用精確的

邊界表示模型。

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

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

Bezier曲線、B樣條曲線等，也可以是平面、球面、

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

十分復(fù)雜。

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

用，導(dǎo)致了歸類求交思想的產(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:圓柱與立方體的所有面

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

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

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

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

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

3.6.2歸類求交策略

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

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

-線：3D直線段、二次曲線（包括圓弧和整圓、橢

圓弧和橢圓、拋物線段、雙曲線段）、Bezier曲

線（有理和非有理）、B樣條曲線、NURBS曲線。

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

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

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

NURBS曲面。

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

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

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

一類元素，在具體求交算法中要考慮它

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

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

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

線線、線面六種。

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

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

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

的求交

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

面之間的求交

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

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

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

-直線一自由曲線/自由曲面的求交

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

-平面一自由曲線/自由曲面的求交

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

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

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

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

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

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

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

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

363基本的求交算法

?曲線曲面求交的基本方法主要有：

-代數(shù)方法

-幾何方法

-離散方法

-跟蹤方法

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

1.代數(shù)方法

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

求出曲面的交線。

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

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

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

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

程代入隱式方程的方法，可以將交線表示為

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

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

解交線。

?兩個(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í)別出交線的形狀和類型，從而可精確求出

交線。

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

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

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

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

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

以更加迅速和可靠。

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

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

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

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

3,幾何求交：

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

直線

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

圓

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

3.離散方法

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

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

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

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

線段，連接這些交線段即得到精確交

線的近似結(jié)果。

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

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

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

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

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

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

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

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

?缺點(diǎn)：

-離散法求出的交線逼近精度不高。如果要求

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

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

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

產(chǎ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)，從而求

出整條交線的方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

-如何處理相切的情況。

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

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

-曲線一曲線求交

?近似交點(diǎ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)，。為兩切線的交點(diǎn)；由于

Q在曲線P。）在尸&）的切線上，有

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)的曲面類型和7種標(biāo)

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

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

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

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

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

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

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

兩種，且依附于模型實(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è)指針被稱為一個(gè)實(shí)例。

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

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

和裝配件(Assemblies)。

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

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

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

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

-曲線。主要依附于面，但也依附于體和裝配

件作為構(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è)在造型器頂部，稱為核心界面(KI),

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

型器。

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

Frustrum、GO(GraphicsOutput)和FG

(ForeignGeometry)。

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

-Frustrum：Frust