幾何造型

1、計算機圖形學,武漢大學電子信息學院 王泉德qdwang@sohu.com,第六章 幾何造型,一、引言二、形體在計算機內的表示三、常用的形體表示方法,一、引言,三維圖形在科學研究和工程技術中有著廣泛的應用。在CAD中，需要對所設計的作品從不同的角度進行審視。計算機幾何造型就是用計算機系統(tǒng)來表示、控制、分析和輸出三維形體。是通過對點、線、面、體等圖形元素進行幾何變換和并、交、差等集合運算，在計算機內表示、構造三維形體的技術，即為幾何

2、造型技術。 。所以幾何造型是計算機圖形學中一個十分重要的應用領域，它是CAD/CAM和CIMS(計算機集成制造系統(tǒng))的核心技術，也是用來實現(xiàn)計算機輔助設計的基本手段。幾何造型的功能：形體輸入，即把形體從用戶格式轉換成計算機內部格式；圖形數(shù)據(jù)的存儲和管理；圖形控制，如對形體進行平移、縮放、旋轉等幾何變換；圖形修改，如應用集合運算、歐拉運算、有理B樣條操作及其交互手段實現(xiàn)對形體局部或整體修改；圖形分析，如形體的容差分析，物質特性

3、分析等；圖形顯示輸出，如消隱、光照、顏色的控制等；查詢形體的屬性及其有關參數(shù),三維幾何造型分為兩個分支：三維曲面造型(surface modeling)和三維實體造型(solid Modeling)；曲面造型技術研究在計算機內如何描述一張曲面，如何對它的形狀進行交互式的顯式和控制；實體造型技術著重研究如何在計算機內定義、表示一個三維物體。實體造型技術是隨著CAD、CAM的需要而發(fā)展起來的，其核心內容是三維物體的數(shù)學模型和計算機表

4、示方法；曲面造型和實體造型是相互支持、相互補充的，在發(fā)展上也是相互獨立，平行發(fā)展的。光有曲面造型，我們的目光就只能停留在組成物體的一張張表面上，無法分析物體的整體性質；反之，光有實體造型，我們將無法準確描述和控制物體的外部形狀；曲面造形所涉及到的基礎內容諸如自由曲線和曲面的表示已經(jīng)討論過。下面將介紹有關實體造型的基礎知識。,清華大學GEMS系統(tǒng)的數(shù)據(jù)結構,,,體組,特征表示,單體(零件),面組,面,線框,環(huán),環(huán)邊,邊,頂點,曲 面

5、,曲 線,點,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,實體幾何數(shù)據(jù),實體拓撲數(shù)據(jù),,參數(shù)域曲線,,,Parasolid的模型結構,Parasolid是一個嚴格的邊界表示的實體建模內核；Parasolid被設計用于機械CAD/CAM/CAE、建筑工程和結構(AEC)、虛擬現(xiàn)實中；Parasolid可以被C等編程語言調用；Parasolid是由Unigraphics Solutions Inc 在

6、Cambridge, England開發(fā)的， 用于它的Unigraphics和Solid Edge 產品中；,二、形體在計算機內的表示,1、表示形體的坐標系,2、幾何元素的定義,在計算機中，形體主要由幾何信息和拓撲信息定義，通常采用六層結構，如右所示：,形體－體體是三維幾何元素，由封閉表面圍成的空間， 其邊界是有限面的并集。定義：由封閉表面圍成的有效空間稱為體；一個形體Q是R3空間中非空、有界的封閉子集。其邊界（記為?Q）

7、 是有限個面的并集，而外殼是形體的最大邊界。一個單位立方體可定義為：{(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}其中一個表面可表示為：{(1,y,z)∈R3|0≤y≤1,0≤z≤1} 注意：這里沒有規(guī)定形體必須是一個連續(xù)的封閉集合，目的是用這樣的定義來擴大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅由某些相交的形體組成。,為了保證幾何造型的可靠性和可加工性，要求形體上任何一點的足

8、夠小的領域在拓撲上應是一個等價的封閉圈，即圍繞該點的形體鄰域在二維空間中可構成一個單連通域，我們把滿足這個定義的形體成為正則形體。,形體－面 面是二維幾何元素 ，是形體上一個有限、非空的區(qū)域，由一個外環(huán)和若干個內環(huán)界定其范圍。一個面可以無內環(huán)，但必須有一個且只有一個外環(huán)。面有方向性，一般用其外法向量方向作為該面的正向。 面F的邊界(記為?F)是有限條線段的并集，P(F)表示含有F的唯一平面。,形體－環(huán) 由有序、有向邊組成的面的封閉

9、邊界稱為環(huán)，環(huán)中任意邊都不能自交，相鄰兩條邊共享一個端點 環(huán)又分為內環(huán)和外環(huán)。內環(huán)是在已知面中的內孔或凸臺面邊界的環(huán)，其邊按順時針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按逆時針方向按上述方式定義，在面上沿著邊的方向前進，面的內部始終在走向的左側。,單環(huán)在R3中具有下列性質的共面線段{e1,e2,…,en}的集合：兩條不同線段ei,ej的交，或是空集，或是一個點，該點即為兩條線段的端點；環(huán)中每個端點的度都是非負偶數(shù)，即為偶數(shù)條線

10、段的交點。,假設F是一個面，其中包含有單環(huán){c0,c1,…,cn}(n≥0),且c0是外環(huán)，則具有下列性質：F的邊界：?F=c0∪c1∪…∪cn；單環(huán)ci(0≤i≤n)均不相交； F是由在c0內部的點，在c1(i≥1)外部的點和∪ci(0≤i≤n)邊界上的點所組成。,形體－邊形體內兩個相鄰面的交界稱為邊，一條邊有且僅有兩個相鄰面。兩個端點確定一條邊，這兩個端點分別稱為該邊的起點和終點。假設Q是一個形體，E(Q)是形

11、體邊的集合，則在?Q中E(Q)是滿足下列條件的所有線段的集合：邊e的兩個端點屬于V(Q)(形體頂點的集合)；邊e中沒有一個內部點屬于V(Q)邊e上每個點，都有兩個不同的面，即存在兩個面fi，fj ∈ ?Q使得邊e∈fi∩fj；形體Q的邊框線WF(Q)是由有序對(V(Q),E(Q))所組成。,形體－點邊的端點稱為點點不能出現(xiàn)在邊的內部，也不能孤立地位于物體內、物體外或面內頂點又是?F中兩條不共線的線段的交點。假設Q是一個形

12、體，V(Q)是所有頂點P的集合，P(f)是含面f的唯一平面，則存在3個面f1,f2,f3 ∈ ?Q，一點P∈V(Q)，使得P=f1∩f2∩f3=P(f1)∩P(f2)∩P(f3),形體－體素、半空間體素 簡單的連續(xù)封閉的形體，可以用有限個尺寸參數(shù)定位和定形體素，如長方體、圓柱體、圓錐、球、環(huán)等；也可以用半空間定義；半空間集合{P|F(P)≤0}成為半空間，其中P為R3中的一點，F(xiàn)為一個平面，當F=0時，表示一個平面，這

13、個平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側的所有點組成。顯然一個長方體可以看成是6個平面半空間的交；,,形體－幾何信息和拓撲信息幾何信息：幾何信息描述物體的大小、尺寸、位置、形狀等；拓撲信息：描述幾何元素之間的連接關系，指物體上所有的頂點、棱邊、表面間的連接關系；拓撲信息和幾何信息分開表示有下述優(yōu)點；便于具體查詢物體中各元素，獲取它們的有關信息；容易提取物體的局部信息，方便的進行物體的各種局

14、部操作；對于具有相同拓撲結構而只是大小、尺寸不同的一類物體，可用統(tǒng)一的數(shù)據(jù)結構加以表示；便于在數(shù)據(jù)結構上附加各種非幾何信息，如物體某表面的光潔度等等；,形體－頂點、棱邊、表面之間的拓撲關系,,,,,,,,,,f,f,f,f,f,v,v,v,v,f,e,e,e,e,f,f,f,f,v,v,v,v,v,e,e,e,v,f,f,e,v,v,e,e,e,e,e,e,3、三維形體表示的三種模型：線框、表面、實體,1） 線框模型線框模型是最早

15、用來表示形體的模型，并且至今仍在廣泛地應用。線框模型由頂點表示幾何位置，相鄰頂點連接構成棱邊表示幾何形狀特征。下圖是一個長方體的例子，8個頂點和12條棱邊表示出這一形體。,線框模型是表面模型和實體模型的基礎。它具有結構簡單、易于理解、數(shù)據(jù)量少的特點，因此計算機處理速度快。,線框模型的局限性：,線框模型包含的信息有限，無法實現(xiàn)圖形的自動消隱；同一數(shù)據(jù)結構可能對應多個圖形，產生不定性；線框數(shù)據(jù)結構無法處理曲面物體的側影輪廓線；當生

16、成復雜的圖形時，處理的數(shù)據(jù)量過于龐大；,,,圖形的不定性,曲面物體的側影輪廓線,,,,,2）表面模型表面模型是用有向棱邊圍成的部分來定義形體表面，由面的集合來定義形體。表面模型是在線框模型的基礎上，通過增加由哪些棱邊按何種順序連接等內容定義出表面，從而可以滿足面面求交、線面消隱、明暗處理、數(shù)控加工等應用需要。表面模型通常用于構造復雜的曲面形體。表面模型完整地定義了形體的邊界，但是形體的實心部分在邊界哪一側并不明確。,3） 實體模

17、型如果要處理完整的三維形體，最終必須使用實體模型，實體模型明確定義了表面的哪一側存在實體。以下是實體在表面某一側的4種定義方法：,1：除了定義一個表面外，還定義實體存在于表面一側的一點P；2：以法線指向定義實體存在的一側；3：定義表面邊界線為有限邊界，并設右螺旋前進的方向指向實體外側；4：將形體分割成幾個區(qū)域，由于每一條邊界線兩側的箭頭方向相反，則表明表面一側存在實體。,實體模型在表面模型的基礎上，使用表面的外法線矢量方向來指明

18、實體存在的一側，例如規(guī)定正向指向體外。通常用有向棱邊隱含地表示表面的外法線矢量方向。在定義表面時，有向棱邊按右手法則取向，沿著閉合的棱邊所得的方向與表面外法線矢量方向一致。,下圖是在表面模型的基礎上增加定義了表面外環(huán)的棱邊方向。據(jù)此還可檢查形體的拓撲一致性，拓樸合法的形體在相鄰兩個面的公共邊界上，棱邊的方向正好相反。,4） 三種模型的數(shù)據(jù)結構線框模型的數(shù)據(jù)結構：線框模型的數(shù)據(jù)信息是頂點和棱邊，其數(shù)據(jù)結構一般使用兩組數(shù)據(jù)，或稱兩表結

19、構。一張表表示頂點，一張表表示棱邊。以下圖為例，假定長方體的長是2，寬是1，高是1，則數(shù)據(jù)組織如表1和表2所示。,,,表面模型的數(shù)據(jù)結構：表面模型是在線框模型的基礎上增加定義表面信息，所以其數(shù)據(jù)結構也是在線框模型兩表結構的基礎上增加面表，如表3所示。,實體模型是在表面模型的基礎上定義了表面的哪一側存在實體,即按右手法則取向安排組成表面的邊順序。表3中邊的順序已經(jīng)符合這一要求，也可以作為實體模型的面表。三個表中除了所列的基本幾何數(shù)據(jù)外，

20、還可以擴充增加屬性信息。比如邊表和面表中可以包括顏色屬性，面表中還可包括透明度、紋理特征等。對上述三表還可以進行數(shù)據(jù)的一致性和完整性檢驗，內容諸如每個頂點至少是二條邊的端點；每條邊至少是一個面的組成部分；每個面的邊界都是封閉的；每個面至少有一條同其它面的公共邊等。,二、常用的形體表示方法,前面介紹的形體表示的線框模型、表面模型和實體模型是一種廣義的概念，并不反映形體在計算機內部、或對最終用戶而言所用的具體的表示方式。從用戶的角度看，

21、形體表示以特征表示法和體素構造表示法(CSG樹)較為方便從計算機對形體的存儲管理和操作運算角度看，以邊界表示法(BRep)最為實用為了適合某些特定的要求，還有一些輔助的形體表示方式，如單元分解表示法、掃描表示法和基于參數(shù)的實體造型法；,對于一個幾何造型系統(tǒng)，一般根據(jù)應用的要求，采用混合的造型表示方法：70年代初，美國Rochester大學推出了以CSG表示為基礎的PADL-1系統(tǒng)；日本北海道大學推出了以Coons曲面為邊界的TIPS

22、系統(tǒng)；美國MIT推出了以線框邊界為基礎的ADAM系統(tǒng)；美國Stanford大學推出了以歐拉操作為基礎的Geomod系統(tǒng)；英國劍橋大學推出了以邊界表示為基礎的Build-1系統(tǒng)。,1、體素構造表示(CSG樹表示),1） 物體的正則集合運算物體之間的并、交、差運算是幾何造型系統(tǒng)中構造物體的最基本的手段之一。在現(xiàn)實生活中，它們也并非陌生。在機械加工中，將兩個零件焊接在一起可以看作是物體的“求并”過程；在物體上鉆開一個孔，實際上是從這個物

23、體上移去了相應于孔的那部分材料。物體間的求交過程在動態(tài)干涉問題中經(jīng)常應用到。,物體間的正則集合運算,形體：可定義為一個具有邊界子集和內部子集的封閉點集，因而執(zhí)行幾何運算的結果也應為具有邊界子集和內部子集的封閉點集，且保持形狀的初始維數(shù)。按照常規(guī)的集合運算，不能保持點集的正則性質，如：通常的兩個立方體的交集運算可能產生的結構有：,為了保持維數(shù)上的一致，引入正則集和正則集合運算的概念。正則集: 是定義在三維空間中的有界，封閉，半解析的區(qū)域

24、。有界：集合的占有空間是有限的封閉：集合的邊界元素也屬于集合中的元素半解析：由有限個解析半空間經(jīng)集合運算所得的集合。解析半空間定義為{(x,y,z)|F(x,y,z)≥0}由正則集合組成的形體稱為正則形體，由非正則集合組成的形體稱為非正則形體。判斷正則形體的方法：假設Q是三維空間R3中一幾何形體, 則Q={Qb,Qi}，其中Qb為Q的邊界或表面,為Qi為Q的內部, Qc為Q的外部. 若Q的邊界滿足下列性質,則稱形體為正則形體：

25、Qb將Qi和Qc分割成兩個不連通的子空間；去掉Qb上的任意一點,Qi和Qc變成為連通的空間；對于任意一點P∈Qb,如果在P處存在切平面, 則其法向量Np指向Qc子空間。,下列圖均不是正則體該圖表示一個邊界有 懸邊和懸面的集合。該圖表示一個非解析 半空間的集合該圖表示一個立方體中減去一個直徑與立方體邊長相等的圓柱體其結果是一個非

26、正則集合。,根據(jù)正則集合的性質，將傳統(tǒng)的點集運算進行修改，得到點集的正則集合運算如下所示：,A ∪* B = r ( A ∪ B) A ∩* B = r ( A ∩ B) A -* B = r ( A - B),,其中， ∪* ∩* -* 分別表示正則化的點集并、交、差運算，而∪,∩, - 則表示傳統(tǒng)的點的集合運算，r表示點集正則化算子；,

27、在許多情況下，一個復雜物體可以由一些比較簡單、規(guī)則的物體經(jīng)過集合運算而得到。因此，這個復雜的物體可描述為一棵樹。這棵樹的終端結點為基本體素(如立方體、圓柱、圓錐)，而中間結點為正則集合的運算結點。這棵樹叫做CSG (Constructive Solid Geometry)樹;,,,,,U*,,,,,,_*,,,CSG樹造型過程示例,CSG樹結點的數(shù)據(jù)結構,左圖是CSG樹結點數(shù)據(jù)結構的一種組織方式。每一結點由操作碼、坐標變換域、基本體素指

28、針、左子樹、右子樹等五個域組成。操作碼按照約定方式取值。當操作碼為零時表示該結點為一基本體素結點。,,,,,,Op_Code 操作碼,transform坐標變換,Left_subtree 左子樹,right_subtree 右子樹,primitive 基本體,從CSG樹結點的數(shù)據(jù)結構可以看出，CSG樹只定義了它所表示的物體的構造方式，它既不存儲頂點，棱邊，表面等邊界信息，也不顯式定義三維點集與所表示物體在空間的一一對應

29、的關系。因此，用CSG樹表示又稱為物體的隱式模型或算法模型；用CSG樹表示一個復雜形體十分簡潔，同時提供了足夠的信息，支持對物體的一切幾何性質的計算；,CSG樹表示的分治算法,CSG樹的表示方法最適合采用分治算法(divide-and-conquer)；設F是關于一個CSG樹所定義物體的幾何性質的函數(shù)，則計算F的分治算法的大致輪廓如下： F(tree, data) = if (tree is a leaf)

30、 then PRIM-F(tree, data); else COMBINE(F(left-subtree, data), F(right-subtree,data),

31、 node(tree)); 其中，PRIM-F為計算基本體素的幾何性質F的函數(shù)，COMBINE為依 據(jù)CSG樹非終結點處所實施的集合運算對左、右子樹的F進行合成的函數(shù)，算法的效率取決于合成函數(shù)；,CSG樹光線投射算法,問題的提出：由于CSG樹不顯示表示物體的邊界，因此無法直接顯示CSG樹表示的物體，而如果要通過求出CSG樹表示物體的精確邊

32、界進行物體顯示，則代價太大，效率不高。對于這個問題，光線投射算法提供了圓滿的解決方案。,左圖為光線投射示意圖，算法的核心思想是從視點出發(fā)向顯示屏幕的每一象素投射光線，求出光線與距離視點最近的可見表面的交點和交點處的表面法向量，然后根據(jù)光照模型計算出該點的色彩和亮度；,CSG樹表示法是三維物體的最有效的表示方法之一，它有以下幾個方面的優(yōu)點；記錄了物體的構造過程；表示的有效性由基本體素的有效性和集合運算的正則性而自動得到保證；表示十分

33、簡潔；,CSG樹表示法并非適用于一切場合，在生成工程設計中常用的線畫圖形時效率較低，這時，需要將物體的CSG樹表示轉換成為邊界表示，以便獲取邊界信息；,2 、邊界表示法,邊界表示模型是一種采用描述形體邊界的方法來描述的幾何表示模型。所謂邊界就是物體內部點和外部點的分界面。顯然，定義了物體的邊界，該物體也就被唯一的定義了；邊界可以拆分成一些有界的“面”和“小片”，而每一個面都可以通過其邊界的邊和頂點來表示；,v1,四棱柱,面節(jié)點,邊節(jié)點,

34、頂點坐標,f1,f2,f3,….,e1,e2,e3,e4,….,v1,v2,v3,….,(x1,y1,z1),,,組合結構,坐標信息,,,,,,,,,,,,,,,,,,,,….,邊界表示法示例,,,U,,,,,,邊界表示法中的數(shù)據(jù)存儲結構 — 翼邊結構,翼邊結構是邊界表示法中典型的一種數(shù)據(jù)結構，是1972年由B.G. Baumgart作為多面體的表示模式最先提出來的。在頂點、棱邊、表面等組成物體的三要素當中，翼邊結構以邊為中心來組織

35、數(shù)據(jù)；,P2,P1,Loop 左,Loop 右,elcc,elcw,ercw,ercc,e,翼邊結構如左圖，棱邊e的數(shù)據(jù)結構中包含兩個指針，指向頂點P1和P2(P1為起點，P2為終點)；同時，e中還設置兩個環(huán)指針，分別指向棱邊e所鄰接的兩表面上的環(huán)Loop左和Loop右。這樣就確定了棱邊和相鄰表面之間的拓撲關系。同時，為了能從棱邊e出發(fā)找到任一閉合環(huán)上的其它棱邊，在e中增設了四個指針Ercc,Ercw,Elcw,Elcc ;,邊e的翼邊

36、數(shù)據(jù)結構如下所示：,（1） 邊界表示中的歐拉運算,歐拉運算是三維物體邊界表示數(shù)據(jù)結構的生成操作，運用歐拉運算，可以正確、有效的構建三維物體邊界表示中的所有拓撲元素和拓撲關系；,歐拉公式： V-E+F=2（V為頂點數(shù)，E為棱線數(shù)，F(xiàn)為面數(shù)）；凡是滿足歐拉公式的形體均稱為歐拉形體；,,擴展的歐拉公式,擴展的歐拉公式：V-E+F-H=2(B-P) 其中，H為物體表面邊界的內環(huán)數(shù)；B為不相連接的物體個數(shù)；P為

37、物體上的通孔數(shù)目；,V=16,E=24,F=11,H=1,B=1,P=0,V=16,E=24,F=10,H=2,B=1,P=1,,,,歐拉運算,滿足歐拉公式的歐拉運算多種多樣，但存在著5個基本的歐拉運算，它們能夠有效的構造出任意物體的拓撲結構；Mvsf(v,f)： 輸入一初始點v作為構造物體的開始；Mev(v1,v2,e)：輸入一點v2，并構造一條連接v1，v2的新邊e；Mef(v1,v2,e,f1,f2)：構造一條連接v1，

38、v2的新邊e，同時構造一張新面f2，f2和f1通過e鄰接；Kemr(v1,v2,e)：刪除v1，v2之間的橋邊e，同時構造一個新的內環(huán)；Kfmrh(f1,f2)：將表面f1的內環(huán)面f2刪除，同時構造f1的一個新內環(huán)，生成物體的一個通孔；,歐拉運算一般不作為直接面向用戶的高級操作，而是放在系統(tǒng)的低層為集合操作、Sweep操作、局部操作等高級操作服務，作為生成邊界表示數(shù)據(jù)結構的工具；,（2）邊界表示中的Sweep運算,Sweep運算將一

39、個二維的平面區(qū)域轉化為三維立體。常用的Sweep運算有平移式、旋轉式和廣義式三種。,,平移式Sweep,旋轉式Sweep,（3） 邊界表示中的集合運算,當物體采用邊界表示法時，它們之間的集合運算可分為以下四個步驟：采用包圍盒技術，檢查兩物體是否相交；計算兩物體各表面之間的交線，該步驟是整個集合運算的核心，直接影響到集合運算的效率和速度；對兩物體表面進行判定分類：兩物體之間的交線將它們的表面分割成兩部分，其中一部分落在拼合體的表面上

40、，形成新的邊界，另一部分落在拼合體內或拼合體外，則在集合運算的最后給予刪除；在集合運算的過程中，不斷的建立新的拼合體的數(shù)據(jù)結構；,3 、單位分解表示法,集合運算是十分有效的造型手段，但在邊界表示法中，物體各個面之間的巨大的求交運算量影響了集合運算的效率和可靠性；解決問題的兩個途徑：改進已有的邊界表示法中的集合運算算法( 特別是其中的求交算法)；探索物體在計算機內的新的表示模式；單位分解表示法便是這種新的探索的結果；,單位分解表示

41、法 — 八叉樹表示,物體的單元分解表示法是一種層次數(shù)據(jù)結構，首先在空間中定義一個能夠包含所表示物體的立方體。立方體的棱和坐標軸平行。若立方體內的空間完全由所表示的物體占據(jù)，則物體可用這個立方體予以表示，否則，將立方體等分成八個小塊，每塊仍為一個小立方體。若某一小立方體的體內空間完全被所表示的物體占據(jù)，則將此立方體標志為“FULL”，若它與所表示的物體無交，則該立方體被標記為“EMPTY”，否則將它標志為“PARTIAL”，并繼續(xù)分

42、割下去，依此方式，物體在計算機內可表示成為一棵八叉樹，凡是標記為“FULL”和“EMPTY”的立方體均為終端結點，而標記為“PARTIAL”的立方體為非終端結點。最后，當分割生成的小立方體為單位長時，分割即告終止。,,三維物體的八叉樹表示,,,,,,,,2,3,6,7,2,0,1,3,1,3,7,5,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,具有子孫的節(jié)點,空節(jié)點,實節(jié)點,

43、八叉樹表示法的性能分析,物體之間的集合運算在八叉樹表示中具有十分簡單的形式，可轉換為對參加集合運算的兩物體的相應八叉樹的遍歷問題；八叉數(shù)的數(shù)據(jù)結構大大簡化了隱藏線和隱藏面的消除問題；在八叉樹表示中，物體上的各元素已按空間位置排列成一定的順序，降低了消隱過程中排序的時間復雜度；物體的整體性能的計算（體積、質量等）更為簡單；采用八叉樹表示物體的最大缺點是占用過多的存儲空間。線性八叉樹方法是對傳統(tǒng)的八叉樹方法的改進，可降低對存儲的要求；

44、,4 、 ACIS三維造型系統(tǒng),ACIS是由美國Spatial Technology于1990年首次推出。ACIS的重要特點是支持線框、曲面、實體統(tǒng)一表示的非正則形體造型技術，能夠處理非流形形體。ACIS產品采用了組件技術，其核心是幾何造型器（Geometric Modeler），還包括一些可與核心集成的組件，稱為外殼（Husk）。,ACIS的結構,ACIS的結構,核心只提供一些基本的幾何造型功能，其它高級功能在外殼中提供。外殼

45、可以是Spatial Technology公司提供的，如高級渲染（Advanced Rendering）外殼、三維工具箱（3D Toolkit）外殼等，也可以是用戶開發(fā)的。,ACIS的模型表示,ACIS模型表示由各種屬性（Attributes）、幾何（Geometries）和拓撲（Topologies）成。幾何是指模型的物理描述，如點、曲線、曲面、直線、橢圓等；拓撲是指各種幾何實體在空間的關聯(lián)，如體、殼、面、環(huán)、邊和頂點等；屬性依