第7章幾何造型技術(shù)7.1線框模型

7.2表面模型

7.3構(gòu)造實(shí)體

7.4空間劃分表示法

習(xí)題7 7.1線框模型

線框模型是用頂點(diǎn)和棱邊來表示三維物體的模型。為了確切地表示清楚物體的形狀和位置，必須給出頂點(diǎn)集的位置和它們之間的連邊規(guī)則。線框模型具有模型簡單、實(shí)現(xiàn)方便、運(yùn)算量小、顯示迅速等優(yōu)點(diǎn)。對于平面多面體(表面由平面多邊形構(gòu)成的三維體)而言，用線框模型表示是很自然的。但是對于非平面體，用線框模型表示就存在一些問題。

如表示長方體，首先給出其8個頂點(diǎn)V1,V2,…,V8的坐標(biāo)，則此長方體的形狀和位置在幾何上就被確定了。但在圖形顯示時，只有頂點(diǎn)還不能清楚地表示此長方體，還必須將棱邊e1,e2,…,e12表示出來，則長方體的頂點(diǎn)和棱邊的關(guān)系就可以被確定下來。圖7-1三維形體的二義性線框模型是表面模型和實(shí)體模型的基礎(chǔ)，但用線框模型表示曲面體比較困難，也不能形成明暗和色彩，不能進(jìn)行立體的物性計(jì)算等。線框模型存在以下幾個缺陷：

(1)用三維線框模型表示三維形體常常具有二義性，如圖7-1所示。

(2)由于不存在面的信息，三維線框模型容易構(gòu)造出無效形體。

圖7-2中的(a)圖是有效形體，(b)圖的構(gòu)造方法雖然與(a)圖完全類似，但由于頂點(diǎn)選擇不恰當(dāng)，造成同一物體各面之間的相互穿透。

(3)三維線框模型不能表示出曲面的輪廓線，因此，不能正確表示曲面信息。

(4)由于線框模型包含的信息有限，因此，無法進(jìn)行圖形的線面消隱。

通過以上敘述可以看出，線框模型比較簡單，但應(yīng)用并不廣泛，主要用于機(jī)械制圖。圖7-2三維形體 7.2表面模型

表面模型用有向棱邊圍成的部分來定義形體的表面，再用面的集合來定義形體。表面模型在線框模型的基礎(chǔ)上，增加了面邊信息以及表面特性、棱邊的連接方向等內(nèi)容。表面模型可以滿足面面求交線、形成明暗色彩等要求，但對于立體的物性計(jì)算和工程分析仍有困難(如有限元分析)。

7.2.1三維物體的邊界表示

在多邊形的表面模型中最普遍采用的是邊界表示(BoundaryRepresentation)，也稱為BR表示或BRep表示。它是幾何造型中最成熟、無二義的表示法。實(shí)體的邊界通常由面的并集來表示，而每個面又由它所在的曲面的定義加上其邊界來表示，面的邊界是邊的并集，而邊又是由點(diǎn)來表示的。邊界表示法與傳統(tǒng)的工程繪圖有密切的聯(lián)系。輸入兩個點(diǎn)，通過這兩個點(diǎn)可以連接一條線。若干條首尾相接的線段可形成一個閉合環(huán)。一個或多個環(huán)給出一個面的邊界。若干個表面閉合后圍成一個“體”。例如要表示一個四面體，可以分別表示出組成該四面體的點(diǎn)、邊、面等信息，如圖7-3所示。圖7-3四面體的點(diǎn)、邊、面之間的關(guān)系邊界表示的一個重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何(Geometry)信息和拓?fù)?Topology)信息兩個方面。拓?fù)湫畔⒚枋鲂误w上的頂點(diǎn)、邊、面的連接關(guān)系，它形成物體邊界表示的“骨架”，形體的幾何信息猶如附著在“骨架”上的肌肉。例如形體的某個表面位于某一個曲面上，定義這一曲面方程的數(shù)據(jù)就是幾何信息。此外，邊的形狀、頂點(diǎn)在三維空間中的位置(點(diǎn)的坐標(biāo))等都是幾何信息。一般來說，幾何信息描述形體的大小、尺寸、位置、形狀等。拓?fù)湫畔⑴c幾何信息分開表示具有許多優(yōu)點(diǎn)，如便于具體查詢物體中各元素，獲取它們的相關(guān)信息；容易支持對物體的各種局部操作；對于具有相同拓?fù)浣Y(jié)構(gòu)而只是大小、尺寸不同的一類物體可以用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)加以表示；便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息。

在邊界表示法中，邊界表示就按照體—面—環(huán)—邊—點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。在進(jìn)行各種運(yùn)算和操作時，就可以直接取得這些信息。

(1)頂點(diǎn)。頂點(diǎn)(Vertex)的位置用(幾何)點(diǎn)(Point)來表示。一維空間的點(diǎn)用一元組{t}表示；二維空間中的點(diǎn)用二元組{x,y}或{x(t),y(t)}表示；三維空間中的點(diǎn)用三元組{x,y,z}或{x(t),y(t),z(t)}表示；n維空間中的點(diǎn)在齊次坐標(biāo)下用n+1維表示。點(diǎn)是幾何造型中最基本的元素，自由曲線、曲面或其他形體均可用有序的點(diǎn)集表示。用計(jì)算機(jī)存儲、管理、輸出形體的實(shí)質(zhì)就是對點(diǎn)集及其連接關(guān)系的處理。在正則形體定義中，不允許孤立點(diǎn)存在。

(2)邊。邊(Edge)是兩個鄰面(對正則形體而言)或多個鄰面(對非正則形體而言)的交集。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來界定。邊的形狀(Curve)由邊的幾何信息來表示，可以是直線或曲線。曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來描述，也可用顯式、隱式或參數(shù)方程來描述。

(3)環(huán)。環(huán)(Loop)是由有序、有向邊(Edge)組成的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點(diǎn)。環(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)。根據(jù)環(huán)的定義，在面上沿環(huán)的方向前進(jìn)，左側(cè)總在面內(nèi)，右側(cè)總在面外。面有方向性，一般用其外法矢方向作為該面的正向。若一個面的外法矢向外，則稱該面為正向面；反之，稱為反向面。面的形狀(Surface)由面的幾何信息來表示，可以是平面或曲面。平面可用平面方程來描述；曲面可用控制多邊形或型值點(diǎn)來描述，也可用曲面方程(隱式、顯式或參數(shù)形式)來描述。對于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)。集合運(yùn)算中對面的分割也可在二維參數(shù)域上進(jìn)行。

(5)體。體(Body)是面的并集。在正則幾何造型系統(tǒng)中，要求體是正則的。非正則形體的造型技術(shù)將線框、表面和實(shí)體模型統(tǒng)一起來，可以存取維數(shù)不一致的幾何元素，并可對維數(shù)不一致的幾何元素進(jìn)行求交分類，從而擴(kuò)大了幾何造型的形體覆蓋域。

邊界表示的拓?fù)湫畔⒖梢圆捎靡磉吔Y(jié)構(gòu)表示，如圖7-4所示。這種存儲平面物體數(shù)據(jù)模型的方法主要供物體的集合運(yùn)算調(diào)度使用。圖7-4翼邊結(jié)構(gòu)翼邊結(jié)構(gòu)的定義方法如下：當(dāng)從物體外部觀察該物體的一條棱邊時，該有向邊有左右兩個相鄰的有界平面以及兩個鄰面中與該有向邊相鄰的四條有向邊(圖7-4中的左上邊、左下邊、右上邊、右下邊)，這兩個相鄰面與四條有向邊就好像有向邊PSPE的雙翼，因而取名為翼邊結(jié)構(gòu)。

用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體。圖7-5是一長方體的邊界表示方法。圖7-5長方體的邊界表示翼邊結(jié)構(gòu)對于在明暗處理時，實(shí)現(xiàn)跨越一邊的兩多邊形之間的平滑光順特別有利。另外，還可以在幾何表中附加信息，如每條邊的斜率等。這樣一旦輸入頂點(diǎn)，就可以很快計(jì)算出邊斜率，通過掃描坐標(biāo)值還可以很快計(jì)算出每個多邊形x,y,z的最大值和最小值。

根據(jù)翼邊結(jié)構(gòu)的約定，可以寫出該長方體每條有向邊的左右相鄰面以及左上邊、左下邊、右上邊、右下邊。翼邊結(jié)構(gòu)的數(shù)據(jù)存儲方式見圖7-6。圖7-6翼邊結(jié)構(gòu)的數(shù)據(jù)存儲方式在圖7-6中，每個平面物體的有關(guān)信息可以分五個層次來存儲，即物體的殼表、面表、環(huán)表、邊表及頂點(diǎn)表。

邊界表示覆蓋域大，原則上能表示所有的形體，而且易于支持形體的特征表示等。邊界表示已成為當(dāng)前CAD/CAM系統(tǒng)的主要表示方法。邊界表示法的優(yōu)點(diǎn)是：表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的；比較容易確定幾何元素間

的連接關(guān)系；有關(guān)形體的操作運(yùn)算可以直接用面、邊、頂點(diǎn)的數(shù)據(jù)來實(shí)現(xiàn)，使得繪制形體的速度較快。邊界表示法的缺點(diǎn)是：數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間；修改形體的操作比較難以實(shí)現(xiàn)；對實(shí)體的整體描述能力弱；邊界表示不一定對應(yīng)一個有效形體，通常需運(yùn)用歐拉操作來保證邊界表示形體的有效性、正則性等。7.2.2三維物體的掃描表示

三維物體的掃描表示法可以利用簡單的運(yùn)動規(guī)則生成有效實(shí)體，是一種得到廣泛應(yīng)用的表示三維物體的方法。它的基本原理簡單，即當(dāng)空間中的一個點(diǎn)、一條邊或一塊面沿著某一路徑掃描時，所形成的軌跡將定義一個一維的線、二維的面或三維的物體。其中包含兩個要素：一是做掃描運(yùn)動的基本圖形，可以是圓、矩形、封閉樣條曲線和實(shí)體剖面片等；二是掃描運(yùn)動的方式，通常的掃描運(yùn)動方式包括平移、旋轉(zhuǎn)及其他對稱變換。在三維物體的表示中，應(yīng)用最多的是平移掃描體和旋轉(zhuǎn)掃描體。如果在掃描表示法中，允許掃描

體的截面隨著掃描過程而變化，就可得到不等截面的平移掃描體與非軸對稱的旋轉(zhuǎn)掃描體，這種方法可統(tǒng)稱為廣義掃描法。掃描運(yùn)算的基本思想是：沿著某種軌跡移動點(diǎn)、曲線或曲面，所產(chǎn)生的軌跡定義為一維、二維或三維物體。掃描運(yùn)算要求定義要移動的物體和移動的軌跡：物體可以是曲線、曲面或?qū)嶓w；軌跡則是可分析的、可定義的軌跡。掃描運(yùn)算分為三種：平移掃描、旋轉(zhuǎn)掃描和廣義掃描。圖7-7表示了掃描面、平移掃描體和旋轉(zhuǎn)掃描體的形成原理。圖7-7掃描表示所形成的掃描面與掃描體

(1)平移掃描。若一個二維區(qū)域(圖形)沿著軌跡作直線移動而形成空間區(qū)域(三維圖形)，這種方法稱為平移掃描。常用的長方體和圓柱體等基本體素即可用此法生成，如圖7-8所示。圖7-8平移掃描

(2)旋轉(zhuǎn)掃描。若將一平面區(qū)域沿某一軸線旋轉(zhuǎn)某一角度(0°到360°)，即為旋轉(zhuǎn)掃描。旋轉(zhuǎn)掃描的特點(diǎn)是生成軸對稱的物體，如圖7-9所示。圖7-9旋轉(zhuǎn)掃描

(3)廣義掃描。若將一平面區(qū)域(該區(qū)域可以在移動過程中按一定的規(guī)則變化)沿任意的空間軌跡線移動，生成一個三維物體，即為廣義掃描。如圖7-10所示為用不等截面的圓盤沿任意軌跡移動構(gòu)成的三維物體。圖7-10廣義掃描廣義掃描的造型能力很強(qiáng)，包含平移式和旋轉(zhuǎn)式掃描。但由于廣義掃描的幾何構(gòu)造算法十分復(fù)雜，因此將它從平移式和旋轉(zhuǎn)式掃描中獨(dú)立出來，單獨(dú)處理。經(jīng)過推廣后的掃描運(yùn)算還可用于物體外形的局部修改，例如生成物體表面的局部凹腔或凸臺等。

掃描表示把復(fù)雜物體看成是簡單物體運(yùn)動的結(jié)果，這對于許多領(lǐng)域的工程設(shè)計(jì)人員來說都是很方便的。例如，建筑設(shè)計(jì)師們可以先設(shè)計(jì)建筑物的平面圖，然后通過平移掃描來構(gòu)造建筑物的模型。 7.3構(gòu)造實(shí)體

目前得到廣泛應(yīng)用的三維形體模型是實(shí)體模型表示，也稱為實(shí)體造型技術(shù)。實(shí)體模型可以很容易地產(chǎn)生具有真實(shí)感的實(shí)體圖像，便于自動生成數(shù)控加工數(shù)據(jù)和自動進(jìn)行干涉

檢查，支持剖切、物性分析以及有限元分析等。

7.3.1正則形體及正則運(yùn)算

早期的實(shí)體造型系統(tǒng)的一個共同的特點(diǎn)是用多面體表示形體，不支持精確的曲面表示。其優(yōu)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)相對簡單，集合運(yùn)算、明暗圖的生成和顯示速度快；缺點(diǎn)是同一系統(tǒng)表示不唯一，違背了幾何定義唯一性原則，而且只是近似表示，存在誤差，若要提高表示精度就要增加離散平面片的數(shù)量，而龐大的數(shù)據(jù)量會影響計(jì)算速度和計(jì)算機(jī)的存儲管理。幾何造型系統(tǒng)還有一個特點(diǎn)，就是支持正則的形體造型。正則形體集(R-Set)的概念為幾何造型奠定了初步的理論基礎(chǔ)。若任一形體具有三維歐氏空間R3中非空、有界的封閉子集，且其邊界是二維流形(即該形體是連通的)，我們稱該形體為正則形體，否則稱其為非正則形體。圖7-11給出了一些非正則形體的實(shí)例。所謂二維流形(2-manifold)，是指這樣一些面，其上任一點(diǎn)都存在一個充分小的鄰域，該鄰域與平面的圓盤是同構(gòu)的，即在該鄰域與圓盤之間存在連續(xù)的一一映射。圖7-11非正則形體集合運(yùn)算(并、交、差)是構(gòu)造形體的基本方法。正則形體經(jīng)過集合運(yùn)算后，可能會產(chǎn)生懸邊、懸面等低于三維的形體。Requicha在引入正則形體概念的同時，還定義了正則集合運(yùn)算的概念。正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面等。集合論與正則集合的求交運(yùn)算如圖7-12所示。

在實(shí)體模型的表示中，基本上可以分為構(gòu)造表示、分解表示和邊界表示三大類。圖7-12集合論與正則集合的求交運(yùn)算7.3.2構(gòu)造實(shí)體的幾何表示

構(gòu)造實(shí)體的幾何表示(CSG)是通過對體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正則集合運(yùn)算并、交、差。圖7-13表示了基本體素的集合運(yùn)算。圖7-13構(gòu)造實(shí)體幾何法的基本體素運(yùn)算從圖7-13中可以看出，基本體素通過集合運(yùn)算可以生成新的物體。不斷地通過集合運(yùn)算可以生成復(fù)雜的三維物體，如圖7-14所示。圖7-14構(gòu)造實(shí)體的幾何法表示的三維物體在構(gòu)造實(shí)體幾何法中，集合運(yùn)算的實(shí)現(xiàn)過程可以用一棵二叉樹(稱為CSG樹)來描述。該樹包括樹的葉子、樹的非終端節(jié)點(diǎn)和二叉樹根節(jié)點(diǎn)。CSG法的基本思想是任何復(fù)雜的形體都可以通過簡單形體(體素)的組合來表示。CSG樹是一棵有序的二叉樹。其終端節(jié)點(diǎn)或是體素，或是形體變換參數(shù)。非終端節(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換(平移和/或旋轉(zhuǎn))操作，這種運(yùn)算或變換只對其緊接著的子節(jié)點(diǎn)(子形體)起作用。

CSG樹的數(shù)據(jù)結(jié)構(gòu)可以定義為

〈CSG樹〉∷=〈OPCode,坐標(biāo)變換，基本體素，左子樹，右子樹〉通過上述數(shù)據(jù)結(jié)構(gòu)可以看出，CSG樹是無二義性的，但不是唯一的。在CSG樹中，除操作碼外，其余均以指針形式存儲。操作碼為0，表示基本體素節(jié)點(diǎn)，左、右子樹為NULL。對于樹的非終端節(jié)點(diǎn)，操作碼為集合運(yùn)算符，基本體素節(jié)點(diǎn)為NULL。CSG樹定義中的坐標(biāo)變換是指進(jìn)行變化前，所作坐標(biāo)變換的信息。

采用CSG表示三維物體的優(yōu)點(diǎn)是：

(1)可以構(gòu)造出多種不同的符合需要的實(shí)體。

(2)數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易。

(3)CSG表示可方便地轉(zhuǎn)換成邊界表示。

(4)以CSG方法表示的形體的形狀比較容易修改。

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

(1)對形體的表示受體素的種類和對體素操作的種類的限制，即CSG方法表示形體的覆蓋域有較大的局限性。

(2)對形體的局部操作不易實(shí)現(xiàn)，例如不能對基本體素的交線倒圓角。

(3)由于形體的邊界幾何元素(點(diǎn)、邊、面)是隱含地表示在CSG中的，故顯示與繪制CSG表示的形體需要較長的時間。7.3.3光線投射算法

構(gòu)造實(shí)體幾何法存在的主要問題是求交困難，因此，CSG樹不能直觀地表示形體的邊界。解決該問題的主要方法是采用光線投射(Ray-casting)算法。該算法的核心思想是從顯示屏(投影平面)的每一個像素位置發(fā)射一根光線(射線)，如圖7-15所示，求出射線與距離投影平面最近的可見表面的交點(diǎn)和交點(diǎn)處的表面法矢量，然后根據(jù)光照模型計(jì)算出表面可見點(diǎn)的色彩和亮度，生成實(shí)體的光柵圖形。該算法的關(guān)鍵之處在于確定光線與距離投影平面最近的可見表面的交點(diǎn)，這可以通過集合成員分類算法實(shí)現(xiàn)。圖7-15光線投射算法(實(shí)體A并B則取ad，實(shí)體A交B則取bc,實(shí)體A-B則取ab)具體算法是：

(1)將射線與CSG樹中的所有基本體素求交，求出所有的交點(diǎn)。

(2)將所有交點(diǎn)相對于CSG樹表示的物體進(jìn)行分類，確定位于物體邊界上的那部分交點(diǎn)。

(3)對所有位于物體邊界上的交點(diǎn)計(jì)算它們在射線上的參數(shù)值并進(jìn)行排序，確定距離最近的交點(diǎn)，得到其所在基本體素表面的法矢量。

光線投射算法用一維集合運(yùn)算代替了CSG實(shí)體的邊界生成算法所需的三維集合運(yùn)算，簡單可靠。但光線投射算法是近似的，其精度取決于顯示屏幕的分辨率。另外，光線投射

算法還可用來求CSG實(shí)體的物理性質(zhì)，如體積和質(zhì)量等。 7.4空間劃分表示法

在空間劃分表示中，物體被分割表示為互不相交的“黏合”在一起的基本體素?；倔w素的大小、位置、類型可以多種多樣，但它們的形狀比較簡單?？臻g劃分表示法對形體分解到何種程度依賴于實(shí)體需要怎樣的基本實(shí)體，以便于完成感興趣的運(yùn)算。兩種常用的空間劃分表示方法是空間位置枚舉表示和八叉樹表示。7.4.1空間位置枚舉表示

空間位置枚舉表示法將包含實(shí)體的空間分割為大小相同、形狀規(guī)則(正方形或立方體)的體素，然后，以體素的集合來表示圖形對象。用空間位置枚舉法表示形體時，只要控制網(wǎng)格上的每一位置單元是否為空，即在表示一個形體時，只需判斷形體包含哪些單元，不包含哪些單元即可。因此，形體可以用唯一且可以明確表示單元是否為空的方法進(jìn)行表示。一般情況下，如是二維形體，常用二維數(shù)組表示；如是三維形體，則用三維數(shù)組來表示。采用數(shù)組表示形體可以很方便地判斷一個單元是在實(shí)體的內(nèi)部還是外部，也很容易判斷兩個實(shí)體是否鄰接?？臻g位置枚舉表示法通常應(yīng)用于生物醫(yī)學(xué)領(lǐng)域，用來表示體數(shù)據(jù)，這些數(shù)據(jù)來自X射線、軸向分層造影(CAT)掃描等。

空間位置枚舉表示是一種窮舉表示法，它可以用來表示任何實(shí)體。采用這種表示法很容易實(shí)現(xiàn)實(shí)體的集合運(yùn)算以及體積計(jì)算等。但這種方法沒有明確給出實(shí)體的邊界信息，不適于圖形顯示；另外更困難的是要存儲全部有關(guān)的信息需要大量的存儲空間，若還要考慮其他因素，如圖形質(zhì)量、數(shù)據(jù)之間的關(guān)聯(lián)等，則還要求更多的存儲空間；而且空間位置枚舉表示沒有“部分”充滿的概念。因此，使用空間位置枚舉表示時許多實(shí)體只能近似表示，雖然單元可以被分割成預(yù)定的大小，以增加表示精度，但是空間開銷成了一個難以解決的問題。在三維空間中，當(dāng)體素分辨率為n時，用空間位置枚舉法表示一個形體就需要占用高達(dá)n3個單元。7.4.2八叉樹表示

空間劃分表示法是將形體按某種規(guī)則分解為小的、更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止?？臻g位置枚舉表示中，每一個小的部分都是一種固定形狀(正方形、立方體等)的單元，形體被分解成這些分布在空間網(wǎng)格位置上的具有鄰接關(guān)系的固定形狀單元的集合，單元的大小決定了單元分解形式的精度。空間位置枚舉表示法在計(jì)算機(jī)內(nèi)存中開辟一個三維數(shù)組。凡是形體占有的空間，存儲單元中記為1；其余空間記為0。這種表示方法的優(yōu)點(diǎn)是簡單，容易實(shí)現(xiàn)形體的交、并、差計(jì)算，但是占用的存儲量太大，物體的邊界面沒有顯式的解析表達(dá)式，不便于運(yùn)算，因此實(shí)際上并未被采用。八叉樹表示對空間位置枚舉表示的空間分割方法作了改進(jìn),它并不是將實(shí)體所在的空間均勻劃分成單位立方體,而是對空間進(jìn)行自適應(yīng)劃分,采用具有層次結(jié)構(gòu)的八叉樹來表示實(shí)體。對于三維實(shí)體采用八叉樹進(jìn)行表示，而對于二維實(shí)體則采用四叉樹進(jìn)行表示。圖7-16是對一個二維物體進(jìn)行的四叉樹表示，方法是把一個平面圖形用一個矩形包圍起來，這個矩形就是四叉樹的根節(jié)點(diǎn)。對于每一次劃分，可能處于三種狀態(tài)：完全被圖形

覆蓋F(Full)、部分被覆蓋B(Boundary)和完全沒有被覆蓋E(Empty)。若根節(jié)點(diǎn)處于狀態(tài)F或E，則四叉樹建立完畢；否則，將其等分為4個象限，分別編碼為1、2、3、4，這4個象限成為第1層子節(jié)點(diǎn)。繼續(xù)考察這4個象限的狀態(tài)是E、F還是B，對于狀態(tài)為E和F的象限不再細(xì)分，而對于狀態(tài)為B的象限又再細(xì)分為4個小象限，形成第2層子節(jié)點(diǎn)，直至給定精度下不出現(xiàn)B型象限為止。這樣就得到一棵四叉樹，這是一個遞歸分割的過程。圖7-16二維實(shí)體的四叉樹表示八叉樹表示形體的過程與四叉樹基本類似。首先在空間中定義一個能夠包含所表示物體的立方體。立方體的三條棱邊分別與x、y、z軸平行，邊長為2n。若立方體內(nèi)空間完全由所表示的物體占據(jù)，則物體可用這個立方體予以表示，否則，將立方體等分為八個小塊，每塊仍為一個小立方體，其邊長為原立方體邊長的1/2。將這八個小立方體依次編號為1,2,3,…，8。如果子立方體單元已經(jīng)一致，即為滿(該立方體充滿形體)或?yàn)榭?沒有形體在其中)，則該子立方體可停止分解；否則，需要對該立方體作進(jìn)一步分解，再一分為八個子立方體。在八叉樹中，非葉節(jié)點(diǎn)的每個節(jié)點(diǎn)都有八個分支。圖7-17表示將三維空間劃分為8個象限。圖7-17三維空間分成8個象限及其節(jié)點(diǎn)表示按照上述方法，將三維物體在計(jì)算機(jī)內(nèi)可表示為一棵八叉樹。凡是標(biāo)識為“Full”或“Empty”的立方體均為終端節(jié)點(diǎn)，而標(biāo)識為“Boundary”的立方體為非終端節(jié)點(diǎn)。當(dāng)分割生成的每一個小立方體的邊長為單位長時，分割即告終止。此時，應(yīng)將每一標(biāo)識為“Boundary”的小立方體重新標(biāo)識為“Full”或“Empty”。圖7-18表示采用八叉樹，對一個三維物體進(jìn)行劃分。圖7-18三維物體的八叉樹表示八叉樹表示法有一些優(yōu)點(diǎn)，近年來受到人們的注意。這些優(yōu)點(diǎn)主要是：

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

(2)簡化了形體的集合運(yùn)算。對形體執(zhí)行交、并、差運(yùn)算時，只需同時遍歷參加集合運(yùn)算的兩形體相應(yīng)的八叉樹，無需進(jìn)行復(fù)雜的求交運(yùn)算。

(3)簡化了隱藏線(或面)的消除。消除隱藏線和隱藏面的關(guān)鍵是對物體(及其不同部分)按其距視點(diǎn)的遠(yuǎn)近排序。在八叉樹表示中，各節(jié)點(diǎn)之間的序的關(guān)系是簡單且固定的，這使得計(jì)算比較容易。

(4)易計(jì)算物體的整體性質(zhì)，如體積、質(zhì)量等。在計(jì)算物體的體積或質(zhì)量時，只需從物體的八叉樹的根節(jié)點(diǎn)開始，逐層計(jì)算所表示物體的最大和最小體積(質(zhì)量)。當(dāng)標(biāo)識為“Boundary”的體元以“Full”計(jì)入時，得最大體積(質(zhì)量)，若不計(jì)入時得最小體積(質(zhì)量)。由于樹的每一層都是在一定精度下對所表示物體的一種近似，因此，若所得的最大、最小體積(質(zhì)量)之差小于給定的允許誤差，計(jì)算即結(jié)束。

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

八叉樹表示的缺點(diǎn)也是明顯的，它通常不能精確地表示一個物體，并且對八叉樹表示的物體作任意的幾何變換也比較困難。它占用的存儲空間很多，這是因?yàn)槊恳惑w素都是立方體，且體素各表面分別與三個坐標(biāo)平面平行。只有當(dāng)所表示的物體具有相似的形狀和位置時，才會獲得簡潔的八叉樹表示。在每一個八叉樹節(jié)點(diǎn)中，除去一個描述該節(jié)點(diǎn)性質(zhì)(Full或Empty等)的域外，還要存儲它指向父節(jié)點(diǎn)及八個子節(jié)點(diǎn)地址的指針，從而使物體的八叉樹表示在空間花費(fèi)上十分昂貴。實(shí)際上，八叉樹表示是以存儲空間換取了算法的效率。7.4.3八叉樹節(jié)點(diǎn)的編碼方式

將立方體中垂直于x軸、y軸和z軸的三個中分面分別稱為x中分面、y中分面和z中分面。位于x中分面右側(cè)的子節(jié)點(diǎn)編碼均比左側(cè)的相鄰節(jié)點(diǎn)編碼增加1；位于y中分面后的