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

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

?幾何造型

?形體表示

?邊界表示模型

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

3.5.1引言

?計算機中表示形體，通常用線框、表面和

實體三種模型。

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

實體造型與曲面造型70'

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

NURBS+邊界表示

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

正則形體

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

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

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

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

體。

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

一些非正則形體的實例

(c)一條邊有兩個以上

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

圖3.2.1非正則形體實例

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

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

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

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

體。

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

定義了正則集合運算的概念。正則集合

運算保證集合運算的結(jié)果仍是一個正則

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

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

集合運算舉列

懸邊

C=AABC*=An*B

集合論的求交計算正則集合下的求交運算

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

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

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

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

則造型技術(shù)。

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

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

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

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

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

352形體表示模型I?

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

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

1、分解表示

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

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

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

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

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

但是占用的存儲量太大，物體的邊界面沒有顯式的解

析表達式，不便于運算。

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

（b）八叉樹法表示形體.首先對形體定義一個外接立方

體，再把它分解成八個子立方體，并對立方體依次

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

致，即為滿（該立方體充滿形體）或為空（沒有形

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

要對該立方體作進一步分解，再一分為八個子立方

體。在八叉樹中，非葉結(jié)點的每個結(jié)點都有八個分

支。

優(yōu)點主要是：

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

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

(2)簡化了形體的集合運算。只需同時遍歷參加

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

求交運算。

(3)簡化了隱藏線(或面)的消除，因為在八叉

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

的順序。

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

八叉樹表示的缺點：占用的存儲多，只能近似表示

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

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

具有子孫的節(jié)點

空節(jié)點

實節(jié)點

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

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

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

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

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

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

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

題。

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

體的覆蓋域非常有限。

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

(a)(b)

回轉(zhuǎn)軸

(c)(d)

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

圖3.2.5生成掃描形體的例子

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

一致的情況

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

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

運算而得到新的形體的一種表示方法。體素

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

空間，其運算為變換或正則集合運算并、交

差。

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

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

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

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

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

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

圖3.2.7CSG表示

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

?CSGM是無二義性的，但不是唯一的.

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

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

的管理比較容易；

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

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

CSG表示的缺點：

?對形體的表示受體素的種類和對體素操作的種

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

域有較大的局限性。

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

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

本體素的交線倒圓角；

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

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

要較長的時間。

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

(c)特征表示

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

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

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

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

表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實現(xiàn)。

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

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

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

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

特征及在特征之間進行操作時需要這些信息。

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

類。

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

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

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

圖3.2.9特征形狀表示

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

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

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

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

元素的信息、覆蓋域有限等缺點，

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

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

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

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

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

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

互連接的拓撲關(guān)系。

-邊界表示的一個重要特點是在該表示法中，

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

拓撲信息(Topology)兩個方面。

?拓撲信息描述形體上的頂點、邊、面的連接關(guān)系，

拓撲信息形成物體邊界表示的“骨架”。

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

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

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

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

-表示形體的點、邊、面等幾何元素是顯式表

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

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

-容易支持對物體的各種局部操作，比如進行

倒角。

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

精度、表面粗糙度等。

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

?Brep表布於

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

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

-Brep表示不一定對應(yīng)一個有效形體，通常運

用歐拉操作來保證Brep表示形體的有效性、正

則性等。

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

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

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

示方港在大學(xué)

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

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

80'

ACMSolidmodeling歐洲CSG會議

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

歐洲ICSG會議一＞亞州GMP

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

353形體的邊界表示模型

3.5.3.1邊界表示的基本實體

?邊界模型表達形體的基本拓撲實體包括：

1.頂點

2.邊。邊有方向，它由起始頂點和終止頂點

來界定。邊的形狀（Curve）由邊的幾何信

息來表示，可以是直線或曲線，曲線邊可用

一系列控制點或型值點來描述，也可用顯式、

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

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

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

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

環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按

順時針方向排序。

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

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

之內(nèi)。

?若一個面的外法矢向外，稱為正向面；反之，稱

為反向面。

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

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

面方程來描述，曲面可用控制多邊形或型

值點來描述，也可用曲面方程(隱式、顯

式或參數(shù)形式)來描述。對于參數(shù)曲面，

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

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

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

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

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

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

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

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

提出。

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

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

兩個鄰邊（即左上邊、左下邊、右上邊和右

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

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

實體。

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

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

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

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

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

-輻射邊結(jié)構(gòu)的形體模型由幾何信息和拓撲信息

兩部分組成。

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

點(vertex)

?拓撲信息有模型(model)＞區(qū)域(region)＞外殼

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

邊引用(edgeuse)和點引用(vertexuse)。

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

?點是三維空間的一個位置

-邊可以是直線邊或曲線邊，邊的端點可以重合。

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

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

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

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

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

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

清華大學(xué)計算機圖形學(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é)計算機圖形學(xué)基礎(chǔ)

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

?歐拉操作選讀

?集合運算選讀

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

3.5.33歐拉操作

?對于任意的簡單多面體，其面⑴、邊⑹、

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

v-e+f=2

?對于任意的正則形體，引入形體的其它

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

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

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

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

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

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

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

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

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

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

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

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

(4)kev(e,v),刪除一條邊e和該邊的一個端點v。

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

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

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

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

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

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

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

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

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

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

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

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

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

為了方便對形體的修改，還定義了兩個輔助的操作：

公共端點。

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

而一條新的邊e2。

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

公共端點。

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

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

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

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

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

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

3.534集合運算

?正則集與正則集合運算算子

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

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

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

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

G的補空間cG稱為G的外部，此時正則形體G需滿足:

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

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

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

(4)bG是二維流形。

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

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

任意兩個正則形體A、B作集合運算：

R=A<0P>B

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

則集合算子。

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

?分類

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

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

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

S相對于G的成員分類函數(shù)為：

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

其中，

SinG=SAiG,

SoutG=SAcG,

SonG=SnbG,

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

?集合運算算法

包括以下幾部分：

⑴求交：參與運算的一個形體的各拓撲元素求交，求交

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

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

進行劃分，形成一些子元素。

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

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

后得到的各子拓撲元素，形成一拓撲元素生成集。

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

(3)分類：對形成的拓撲元素生成集中的每一拓撲元素，

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

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

拓撲元素的類型(即其維數(shù))，來決定該拓撲元素相

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

(4)取舍：根據(jù)拓撲元素的類型及其相對另一形體的分類

關(guān)系，按照集合運算的運算符要求，決定拓撲元素是

保留還是舍去；保留的拓撲元素形成一個保留集。

⑸合并：對保留集中同類型可合并的拓撲元素進行合并,

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

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

(6)拼接：以拓撲元素的共享邊界作為其連接標(biāo)志，按照

從高維到低維的順序，收集分類后保留的拓撲元素，

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

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

3.6歸類求交

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

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

量的求交運算。

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

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

?歷史上的觀念變化:簡單體素的精確求交，

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

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

3.6.1求交分類簡介

?多面體模型

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

問題的解決相對簡單。

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

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

?CSG模型

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

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

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

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

邊界表示模型。

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

相對應(yīng)，它們可以是直線、圓（圓?。⒍吻€

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

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

十分復(fù)雜。

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

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

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

?“無處不在的求交”：GEMS實例!

令GEMS5.0-[Parti.PART]

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

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

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

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

\

平

囪13

、2

平

因

<、

平

團3

、

L原

總

e懸

體-

槽

痘T4、

梢

痘m

-is

Lil

如需幫助，語報Fl鍵

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

?實體建模步驟剖析：

-草圖

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

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

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

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

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

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

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

3.6.2歸類求交策略

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

—點：3D點°

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

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

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

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

臺面、雙曲面、拋物面、橢球面和橢圓柱面）、

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

NURBS曲面。

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

?將幾何元素進行歸類，利用同一類元素

之間的共性來研究求交算法。同時對每

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

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

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

?求交方法可分為：點點、點線、點面、

線線、線面六種。

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

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

-點、直線、平面、二次曲線等簡單的幾何元素之間

的求交

-直線、平面、二次曲線等簡單的幾何元素與二次曲

面之間的求交

-三維點與二次曲線/曲面之間的求交

—三維點與自由曲線、曲面之間的求交

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

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

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

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

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

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

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

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

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

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

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

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

363基本的求交算法

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

-代數(shù)方法

-幾何方法

-離散方法

-跟蹤方法

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

1.代數(shù)方法

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

求出曲面的交線。

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

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

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

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

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

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

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

解交線。

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

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

式或有理多項式曲面的隱式化通過消元來實現(xiàn)。

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

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

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

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

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

代數(shù)法的弱點是對誤差很敏感

?這是因為代數(shù)法經(jīng)常需要判別某些量是否大于零

等于零或小于零，而在計算機中的浮點數(shù)近似表

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

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

?代數(shù)法實例：

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

解。

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

解。

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

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

2.幾何方法

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

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

識別出交線的形狀和類型，從而可精確求出

交線。

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

以及二次曲面等簡單曲面的求交

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

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

是點、直線或圓錐曲線，用幾何方法求交可

以更加迅速和可靠。

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

?幾何法實例：平面與圓柱求交

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

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

3,幾何求交：

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

直線

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

圓

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

3.離散方法

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

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

每一子曲面片均可用比較簡單的面片

然后用這些簡單面片求交得一系列交

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

線的近似結(jié)果。

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

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

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

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

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

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

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

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

?缺點：

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

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

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

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

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

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

?高度估計問題

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

4.跟蹤方法

-通過先求出初始交點，然后從已知的初始交

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

出整條交線的方法。

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

先求出滿足方程組的某個某個初值解，通過

數(shù)值求解微分方程組的方法來計算整個交線

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

-跟蹤方法在計算相繼交點的時候，利用了曲

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

法求解，使得計算效率較高。

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

?跟蹤法求交中考慮的主要問題包括：

-如何求出初始交點并保證每一交線分支都有

初始交點被求出；

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

取跟蹤的前進步長；

-如何處理相切的情況。

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

?跟蹤法實例：MAF方法

-曲線一曲線求交

?近似交點，

?切線求交，

?投影

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

MAF與Newton法的比較

?Newton法

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

MAF與Newton法的比較

?MAF法

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

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

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

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

于是

（0-尸1））。尸&）

ZA4一

儼"。）11

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

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

3.7實體造型系統(tǒng)簡介

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

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

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

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

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

Parasolid和ACIS。

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

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

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

3.7.1.1Parasolid的主要功能

?Parasolid有較強的造型功能，但是只能支

持正則實體造型。主要功能包括：

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

表示，共提供了10種標(biāo)準的曲面類型和7種標(biāo)

準的曲線類型，并且是完全集成的。

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

實體之間可有多種方式的操作。

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

-4.能夠提供非拓撲和非幾何數(shù)據(jù)，稱為屬性

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

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

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

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

面幾何、使面成錐形、擺動面、掃描面及刪

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

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

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

?模型實體包括三種：

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

圖3.4.1核心模型的實體

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

?1.拓撲實體

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

或多個體(Bodies)

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

間封閉的邊界

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

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

每一條邊有一個左翼和一個右翼

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

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

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

一個裝配件是一個對其它裝配件或體的指針的集

合。每一個指針被稱為一個實例。

-(8)世界(World)：世界是一個獨特的實體

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

和裝配件(Assemblies)。

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

2.幾何實體（Entities）

-點。主要依附于頂點，它們也依附于體和裝

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

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

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

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

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

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

主要依附于實例。

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

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

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

于體和裝配件。

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

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

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

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

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

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

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

3.7.1.3Parasolid的界面

?Parasolid有兩個界面。

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

通過KL用戶可以造型、操作對象和控制造

型器。

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

Frustrum、GO(GraphicsOutput)和FG

(ForeignGeometry)。

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

-Frustrum：Frust