一種表示流形形體和非流形形體的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)研究

張成林，朱 琳，文珊珊，王 卓，王聯(lián)鳳

(1.中國科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院,安徽 合肥 230026； 2.上海交通大學(xué) 機(jī)械與動力工程學(xué)院,上海 200240；3.上海航天設(shè)備制造總廠,上海 200245)

一種表示流形形體和非流形形體的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)研究

張成林1，朱 琳2，文珊珊3，王 卓3，王聯(lián)鳳3

(1.中國科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院,安徽 合肥 230026； 2.上海交通大學(xué) 機(jī)械與動力工程學(xué)院,上海 200240；3.上海航天設(shè)備制造總廠,上海 200245)

為彌補(bǔ)3D打印中非流形拓?fù)鋽?shù)據(jù)結(jié)構(gòu)的存儲空間大、運(yùn)算效率低，流行拓?fù)鋽?shù)據(jù)結(jié)構(gòu)形體表示的局限性，研究了一種可表示流形形體(正則形體)和非流形形體(非正則形體)的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)。分析了半邊數(shù)據(jù)結(jié)構(gòu)、放射邊數(shù)據(jù)結(jié)構(gòu)、混合邊數(shù)據(jù)結(jié)構(gòu)、單元復(fù)形和粘合邊數(shù)據(jù)結(jié)構(gòu)等非流形形體的邊界表示法，發(fā)現(xiàn)現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)未能綜合考慮幾何模型、存儲數(shù)據(jù)和效率。提出了一種基于復(fù)形的非流形數(shù)據(jù)結(jié)構(gòu)：利用引用面、邊及點(diǎn)結(jié)構(gòu)完整地表示非流形幾何模型，實(shí)現(xiàn)線框、表面、實(shí)體和自由曲面模型的統(tǒng)一；采用面向?qū)ο蟮脑O(shè)計(jì)方法，使用類的繼承與派生，以減少數(shù)據(jù)存儲量，提高存儲和運(yùn)算效率；擴(kuò)展歐拉算子可為更高級的歐拉操作和布爾操作提供基礎(chǔ)。設(shè)計(jì)的方法在模型的面、邊和點(diǎn)的數(shù)據(jù)設(shè)計(jì)中，以指針的形式管理和組織拓?fù)浣Y(jié)構(gòu)，避免信息的重復(fù)存儲，既滿足了豐富的形體表示需求，擴(kuò)大了傳統(tǒng)3D打印模型的覆蓋域，又有效減少了存儲空間，提高了運(yùn)算效率。

3D打?。?幾何模型； 流形形體； 非流形形體； 數(shù)據(jù)結(jié)構(gòu)； 拓?fù)浣Y(jié)構(gòu)； 運(yùn)算效率； 存儲空間

0 引言

工程應(yīng)用對3D打印的幾何模型提出高要求，而拓?fù)鋽?shù)據(jù)結(jié)構(gòu)作為關(guān)鍵部分，其運(yùn)算效率及存儲空間優(yōu)化嚴(yán)重制約3D打印模型處理的功能和效率。目前，幾何模型主要有流形拓?fù)鋽?shù)據(jù)結(jié)構(gòu)和非流形拓?fù)鋽?shù)據(jù)結(jié)構(gòu)兩種表示方法。非流形拓?fù)鋽?shù)據(jù)結(jié)構(gòu)可表示更豐富的形體，代價(jià)是存儲空間的增長和運(yùn)算效率的降低；流形拓?fù)鋽?shù)據(jù)結(jié)構(gòu)存儲空間相對較小，運(yùn)算效率相對較高，但其形體表示有一定的局限性。非流形模型的提出，雖然是源于幾何模型理論的需要，但更主要的是3D打印技術(shù)對模型顯示提出更高要求，必然會混合使用線框、曲面、實(shí)體模型，非流形模型能很好地滿足其要求[1]。以表面拓?fù)涞挠^點(diǎn)，非流形形體是一個由0，1，2，3維幾何元素組成的混合維形體，可有懸邊、懸面和孤點(diǎn)。以點(diǎn)集的觀點(diǎn)，非流形形體可能具有內(nèi)部邊界或不封閉的邊界，也可以是開的點(diǎn)集。目前已出現(xiàn)了4種形體表示方法：基于s集的表示方法、邊界表示方法(B-rep)、SGC表示方法和CNRG表示方法。其中：以邊界表示方法為主流的實(shí)體造型技術(shù)支撐了一代CAD/CAM系統(tǒng)，并在各應(yīng)用領(lǐng)域發(fā)揮了巨大作用[2-3]。但目前現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)均未有效結(jié)合完整表示非流形幾何模型及減少存儲數(shù)據(jù)、提高運(yùn)算效率，因此研究一種滿足上述目標(biāo)的非流形數(shù)據(jù)結(jié)構(gòu)十分迫切。為此，本文對一種表示流形形體和非流形形體的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)進(jìn)行了研究。

1 邊界表示法

邊界表示方法能提供形體完整的邊界信息，以翼邊數(shù)據(jù)結(jié)構(gòu)為代表的邊界表示方法在傳統(tǒng)實(shí)體造型技術(shù)中有重要的地位。對非流形形體的邊界表示，大量研究是在翼邊數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上進(jìn)行擴(kuò)充和完善[4]。

1.1半邊數(shù)據(jù)結(jié)構(gòu)

半邊數(shù)據(jù)結(jié)構(gòu)是MANTYLA基于翼邊數(shù)據(jù)結(jié)構(gòu)創(chuàng)建的[2]。半邊數(shù)據(jù)結(jié)構(gòu)將翼邊數(shù)據(jù)結(jié)構(gòu)中的一條整邊拆成兩條半邊，每條半邊各帶1個頂點(diǎn)作為起點(diǎn)，通過體(solid)-面(face)-環(huán)(loop)-半邊(halfedge)-頂點(diǎn)(vertex)五層拓?fù)涿枋鲂误w。此外，為表示面與面間的相互聯(lián)系，又引入了一個邊(edge)附加拓?fù)湓芈?lián)系一對半邊，通過邊對鄰接面進(jìn)行描述。這樣，半邊、邊和頂點(diǎn)三個拓?fù)湓鼐蜆?gòu)成了半邊數(shù)據(jù)結(jié)構(gòu)的最核心部分。半邊數(shù)據(jù)結(jié)構(gòu)對表面流形表示進(jìn)行了擴(kuò)展，將非流形按特殊情況或偽流形進(jìn)行處理，使非流形表示變得自然。但半邊數(shù)據(jù)結(jié)構(gòu)的提出并非是為建立一種表示非流形形體的數(shù)據(jù)結(jié)構(gòu)，其表示的形體是具非流形邊界的正則形體。

1.2放射邊數(shù)據(jù)結(jié)構(gòu)

文獻(xiàn)[5]對非流形形體的表示進(jìn)行了開創(chuàng)性研究，其研究目標(biāo)是用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)表示線框、表面和實(shí)體模型，允許在產(chǎn)品模型中存儲任何幾何信息。針對非流形形體中一條邊可有多個鄰面的情況，提出了放射邊數(shù)據(jù)結(jié)構(gòu)的構(gòu)想：在放射邊數(shù)據(jù)結(jié)構(gòu)中，使用的幾何信息是面、環(huán)、邊、頂點(diǎn)，其拓?fù)鋵哟问怯赡Ｐ?model)、區(qū)域(region)、殼(shell)、面引用(faceuse)、環(huán)引用(loopuse)、邊引用(edgeuse)、點(diǎn)引用(vertexuse)組成。放射邊數(shù)據(jù)結(jié)構(gòu)將面、環(huán)、邊、點(diǎn)的幾何定義與其引用分離，使模型中的不同拓?fù)湓乜晒蚕硐嗤膸缀涡畔ⅲ瑥亩ＷC非流形形體數(shù)據(jù)的一致性。放射邊數(shù)據(jù)結(jié)構(gòu)是第一種面向非流形形體表示而提出的數(shù)據(jù)結(jié)構(gòu)，全面考慮了一般非流形形體的情況，實(shí)現(xiàn)了用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)表示非流形形體的目標(biāo)，提供了較正則形體更強(qiáng)的形體定義功能，為實(shí)現(xiàn)更簡單而統(tǒng)一的算法奠定了基礎(chǔ)。

1.3混合邊數(shù)據(jù)結(jié)構(gòu)

文獻(xiàn)[6]提出的混合邊數(shù)據(jù)結(jié)構(gòu)的基本思想是利用拓?fù)湓氐膶哟涡裕瑢⒁粋€復(fù)雜幾何形狀表示為多個簡單幾何元素的組合。在混合邊數(shù)據(jù)結(jié)構(gòu)中，每條邊的表示通過3個記錄實(shí)現(xiàn)：線段(segment)記錄2個和邊記錄1個，其算子被分為低層、中層、高層3個層次，高層算子根據(jù)低層算子構(gòu)造，使其不涉及特定的實(shí)現(xiàn)細(xì)節(jié)，低層算子完成特定的工作。從概念上來說，混合邊數(shù)據(jù)結(jié)構(gòu)是翼邊數(shù)據(jù)結(jié)構(gòu)和半邊數(shù)據(jù)結(jié)構(gòu)的組合，它在線段的層次維護(hù)多邊形(面)和實(shí)體的方向信息，在邊的層次處理面的鄰接信息，線框、表面和實(shí)體的混合表示在形狀(shape)的層次統(tǒng)一。算子的層次性構(gòu)造避免了操作的冗余并增強(qiáng)了模型的語義集成。混合邊數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了線框、表面、實(shí)體三種模型的統(tǒng)一與集成，但其表示的實(shí)體限于正則形體。

上述的邊界表示方法均建立在直觀的概念基礎(chǔ)上，但一個完整的非流形形體的數(shù)學(xué)定義對無二義地描述非流形形體至關(guān)重要。傳統(tǒng)的邊界表示是以流形作為其數(shù)學(xué)基礎(chǔ)，作為流形概念的自然擴(kuò)展，非流形形體的邊界表示是以復(fù)形(complex)作為其數(shù)學(xué)基礎(chǔ)。

1.4單元復(fù)形

文獻(xiàn)[7]將非流形形體定義為數(shù)學(xué)上滿足三個條件的n維單元復(fù)形(n-cell complex)的集合。其中：第一個條件是三維單元復(fù)形能用0，1，2，3維單元的集合表示，即非流形模型可包含分離的頂點(diǎn)、邊、面和體；第二個條件是每個單元邊界必須由低維單元構(gòu)成，因而非流形模型總是封閉的；第三個條件是要求所有拓?fù)湓夭荒艹霈F(xiàn)自相交。此模型被稱為基于復(fù)形的非流形幾何模型，其拓?fù)鋵哟谓Y(jié)構(gòu)如圖1所示。根據(jù)有限單元復(fù)形的Euler-Poincare公式，理論上只需9個獨(dú)立的歐拉算子及其逆算子就可構(gòu)造所有的基于復(fù)形的非流形形體，但為有效描述高層運(yùn)算，文獻(xiàn)[7]使用了17個擴(kuò)展歐拉算子，用其描述局部操作和布爾運(yùn)算。這種表示方法在幾何拓?fù)鋵哟闻c放射邊數(shù)據(jù)結(jié)構(gòu)相同，將線框、表面、實(shí)體模型在復(fù)形層次統(tǒng)一，在殼和環(huán)層次描述各維幾何元素出現(xiàn)的非流形形狀。

圖1 基于復(fù)形的層次結(jié)構(gòu)Fig.1 Architecture based on complex

1.5粘合邊數(shù)據(jù)結(jié)構(gòu)

文獻(xiàn)[8]將代數(shù)拓?fù)渲袕?fù)形的概念和方法引入非流形表示，給出了非流形的一個嚴(yán)格的數(shù)學(xué)定義，說明復(fù)形統(tǒng)一了三種模型，即零維骨架為全部頂點(diǎn)，一維骨架為棱集合+懸點(diǎn)(線框模型)，二維骨架為面集合+懸邊+懸點(diǎn)(表面模型)，三維骨架為三維實(shí)體(實(shí)體模型)。文獻(xiàn)[8]擴(kuò)展了放射邊數(shù)據(jù)結(jié)構(gòu)，提出了一種粘合邊數(shù)據(jù)結(jié)構(gòu)，其中每條邊有多個粘合邊，每個粘合邊由2條有向邊組成。操作分為基本操作和高級操作兩種：基本操作包括生成單形、粘合及分離操作、擴(kuò)展的歐拉操作等；高級操作包括掃描操作、驅(qū)動操作、分裂操作、布爾操作等。這種表示方法將非流形形體按復(fù)形進(jìn)行描述，使非流形形體的表示有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。

上述各種非流形形體的邊界表示方法中，除半邊數(shù)據(jù)結(jié)構(gòu)外，其余表示方法都實(shí)現(xiàn)了線框、表面、實(shí)體模型的統(tǒng)一。就該意義來說，它們是一致的，但其各自能表示的非流形形體和處理方法卻存在差異。放射邊數(shù)據(jù)結(jié)構(gòu)及其變形的非流形形體覆蓋域最廣，是以面邊和點(diǎn)邊對作為其核心，重點(diǎn)是點(diǎn)邊，目的是為了表示一般的非流形形體。半邊數(shù)據(jù)結(jié)構(gòu)是將有限的非流形形體按特殊情況或偽流形表示，目標(biāo)是為實(shí)現(xiàn)操作的便利?；旌线厰?shù)據(jù)結(jié)構(gòu)主要是為統(tǒng)一3種模型，形體的表示限于正則形體，以代數(shù)拓?fù)渲械膹?fù)形概念為基礎(chǔ)，構(gòu)造非流形模型，能在確定的表示域上統(tǒng)一線框、表面和實(shí)體模型，又使之具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。此外，拓?fù)鋽?shù)據(jù)結(jié)構(gòu)作為幾何造型的關(guān)鍵部分，其運(yùn)算效率及存儲空間嚴(yán)重制約造型系統(tǒng)的功能和效率。

2 非流形結(jié)構(gòu)

2.1拓?fù)浣Y(jié)構(gòu)

圖2 拓?fù)浣Y(jié)構(gòu)Fig.2 Topological structure

將代數(shù)拓?fù)渲械膯渭儚?fù)形和CW復(fù)形的概念和方法引入幾何造型系統(tǒng)中，建立以復(fù)形為基礎(chǔ)的統(tǒng)一的產(chǎn)品模型[9-11]。該模型的拓?fù)潢P(guān)系由復(fù)形中的鄰接關(guān)系決定，復(fù)形的定向決定模型中拓?fù)湓氐姆较?，如圖2所示。模型的表示域?yàn)閺?fù)形的伴隨多面體，此處多面體的概念與傳統(tǒng)的不同，根據(jù)代數(shù)拓?fù)鋵W(xué)中復(fù)形理論可知：其表面可為復(fù)雜曲面。模型中的邊界采用以邊為基礎(chǔ)的B-rep表示，定義一個引用邊結(jié)構(gòu)存儲邊的一個或若干個副本，并存儲方向，這樣就可表示出多個面共享一條邊的非流形結(jié)構(gòu)，本文稱該結(jié)構(gòu)為引用邊結(jié)構(gòu)。引用邊結(jié)構(gòu)能表示物體的懸面、懸邊、懸點(diǎn)等情況，以及物體的內(nèi)部結(jié)構(gòu)，它將一條邊的拓?fù)浣Y(jié)構(gòu)刻畫成2個層次，表示的拓?fù)湓亻g的邏輯關(guān)系簡潔、自然、直觀，人為因素少。同理定義引用面與引用點(diǎn)，將復(fù)形作為基本結(jié)構(gòu)，有效而無二義性地表示了非流形結(jié)構(gòu)。

2.2數(shù)據(jù)結(jié)構(gòu)

形體在計(jì)算機(jī)內(nèi)部的表示就是幾何造型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是幾何建模的關(guān)鍵，直接影響整個CAD系統(tǒng)的功能效率。好的拓?fù)潢P(guān)系的數(shù)據(jù)結(jié)構(gòu)應(yīng)能完整無二義性地定義幾何實(shí)體；能方便快捷地訪問相關(guān)數(shù)據(jù)；作為CAD系統(tǒng)的底層支持，應(yīng)為用戶提供功能強(qiáng)大而完備的技術(shù)支持和完善的產(chǎn)品信息。現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)都未有效結(jié)合完整表示非流形幾何模型及減少存儲數(shù)據(jù)、提高運(yùn)算效率，為此本文提出了一種基于復(fù)形的改進(jìn)非流形數(shù)據(jù)結(jié)構(gòu)，如圖3所示。圖3中：虛線框中的結(jié)構(gòu)體是從其上實(shí)線表示的結(jié)構(gòu)體派生出的。在數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中，盡量避免信息的重復(fù)存儲以求實(shí)現(xiàn)優(yōu)化。在拓?fù)浣Y(jié)構(gòu)的面、邊、點(diǎn)結(jié)構(gòu)中均存儲了該拓?fù)浣Y(jié)構(gòu)的幾何指針，使拓?fù)湫畔⑴c幾何信息建立起關(guān)聯(lián)。

本文數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)如下。

a)拓?fù)湫畔⑴c幾何信息分離，便于具體查詢各元素，獲取其信息；便于支持各種局部操作。

b)采用代數(shù)拓?fù)鋵W(xué)中的復(fù)形結(jié)構(gòu)，使非流形的表示有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，可統(tǒng)一表示線框、表面和實(shí)體。

c)由于采用復(fù)形為基礎(chǔ)的結(jié)構(gòu)，既允許標(biāo)準(zhǔn)的集合運(yùn)算，又允許正則的集合運(yùn)算。

d)采用面向?qū)ο蟮脑O(shè)計(jì)方法，使用類的繼承與派生，減少了數(shù)據(jù)存儲量，便于運(yùn)算。

圖3 非流形數(shù)據(jù)結(jié)構(gòu)Fig.3 Non-manifold data structure

e)結(jié)構(gòu)中的各元素鏈表均采用雙鏈表的存儲結(jié)構(gòu)，適應(yīng)了面表、邊表等信息頻繁修改的需要。

在圖形軟件中顯示的四種典型非流形形體如圖4所示，該軟件的圖形拓?fù)浣Y(jié)構(gòu)采用了本文的數(shù)據(jù)結(jié)構(gòu)。

在不同軟件中，四組流形形體應(yīng)用程序內(nèi)存占用如圖5所示。圖5中：軟件1采用本文提出的數(shù)據(jù)結(jié)構(gòu)；軟件2為金屬3D打印專用軟件AutoFab。

圖4 典型非流形形體顯示Fig.4 Typical non-manifold modeling view

圖5 不同軟件流形形體應(yīng)用程序內(nèi)存占用

3 支持非流形結(jié)構(gòu)的歐拉算子

3.1歐拉運(yùn)算理論基礎(chǔ)

傳統(tǒng)的Euler算子不適于非流形物體，在代數(shù)拓?fù)渲幸霐U(kuò)展的Eule-Poincare公式

v-e+(f-r)-(V-Vh+Vc)=

C-Ch+Cc

(1)

式中：v，e，f，V，C分別為點(diǎn)數(shù)、邊數(shù)、面數(shù)、體數(shù)和復(fù)形數(shù)；r為環(huán)數(shù)；Vh，Vc，Ch，Cc分別為體的通孔數(shù)、體的穴數(shù)、復(fù)形的通孔數(shù)和復(fù)形的穴數(shù)。非流形幾何造型的拓?fù)渌阕蛹捌淠嫠阕訛閿U(kuò)展的Euler算子，式(1)也成為檢驗(yàn)非流形合法性的依據(jù)。

3.2擴(kuò)展歐拉運(yùn)算

理論上，只需9種歐拉運(yùn)算和其逆運(yùn)算就可定義所有基于復(fù)形的非流形模型。但在實(shí)際應(yīng)用中，為描述更高級的運(yùn)算，常需要更多的歐拉運(yùn)算。非流形模型的15種擴(kuò)展歐拉算子，如圖6所示[3]。圖6中：體中的穴(cavity)和通孔(hole)分別定義為Vcavity，Vhole，同理復(fù)形中的穴和通孔被定義Ccavity，Chole。對更高級的歐拉運(yùn)算，可用一系列圖6的基本運(yùn)算完成。

圖6中箭頭表示運(yùn)算方向，括號中為逆運(yùn)算標(biāo)。Make，kill均為一種操作，下劃線后的vertex，edge，……等拓?fù)湓厥遣僮鞯膶ο蟆Ｈ绲?種歐拉運(yùn)算的正運(yùn)算表示的是生成一條邊，刪除一個環(huán)。其他運(yùn)算類似。

4 結(jié)束語

拓?fù)鋽?shù)據(jù)結(jié)構(gòu)是3D打印技術(shù)中幾何建模的關(guān)鍵部分，其優(yōu)劣直接影響整個打印系統(tǒng)的功能和效率，因此功能、效率、存儲空間間構(gòu)造最優(yōu)的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)尤為關(guān)鍵。本文對一種表示流形形體和非流形形體的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)進(jìn)行了研究，提出了基于復(fù)形的改進(jìn)非流形模型數(shù)據(jù)結(jié)構(gòu)，利用引用面、邊及點(diǎn)結(jié)構(gòu)可完整地表示非流形幾何模型，實(shí)現(xiàn)線框、表面、實(shí)體和自由曲面模型的統(tǒng)一，同時采用面向?qū)ο蟮脑O(shè)計(jì)方法，使用類的繼承與派生，減少了數(shù)據(jù)存儲量，提高了存儲和運(yùn)算效率。給出的歐拉算子可為更高級的歐拉操作和布爾操作提供基礎(chǔ)，對3D打印模型發(fā)展有一定參考意義。后續(xù)可考慮數(shù)據(jù)結(jié)構(gòu)的融合，提高數(shù)據(jù)存儲效率，減少內(nèi)存用量。

圖6 擴(kuò)展的支持非流形結(jié)構(gòu)的歐拉運(yùn)算Fig.6 Extended Euler algorithm supporting non-manifold structure

[1] MANTYLA M. An introduction to solid modeling[M]. New York: Computer Science Press, 1988.

[2] REQUICHA A A G, ROSSIG NAC J R. Solid modelling and beyond[J]. IEEE CG & A, 1992, 12(5): 31-44.

[3] GUéZIEC A, TAUBIN G, LAZARUS F. Cutting and stitching: converting sets of polygons to manifold surfaces[J]. IEEE Transactions on Visualization and Computer Graphics, 2001, 7(2): 136-150.

[4] 孫家廣, 楊長貴. 計(jì)算機(jī)圖形學(xué)[M]. 3版. 北京: 清華大學(xué)出版社, 1998.

[5] WEILER K J. Topological structures for geometric modeling[D]. New York: Rensselaer Polytechnic Institute, 1986.

[6] KALAY Y E. The hybrid edge: a topological data structure for vertically integrated geometric modeling[J]. CAD, 1989, 21(3): 130-140.

[7] MASUDA H. Topological operators and boolean operations for complex—— based on manifold geometric models[J]. CAD, 1993, 25(2): 119-129.

[8] 武仲科, 吳駿恒. 用復(fù)形方法建立統(tǒng)一的產(chǎn)品模型——關(guān)于下一代造型系統(tǒng)的研究[J]. 航空學(xué)報(bào), 1995, 16(6): 662-670.

[9] 聶靈沼, 丁石孫. 代數(shù)學(xué)引論[M]. 北京: 高等教育出版社, 1998.

[10] 李元熹, 張國棟. 拓?fù)鋵W(xué)[M]. 上海: 上海科學(xué)技術(shù)出版社, 1986.

[11] 蘇競存. 流形的拓?fù)鋵W(xué)[M]. 武漢: 武漢大學(xué)出版社, 2005.

AnUniformDataStructureSupportingManifoldandNon-ManifoldModeling

ZHANGCheng-lin1，ZHULin2，WENShan-shan3，WANGZhuo3，WANGLian-feng3

(1. School of Engineering Science, University of Science and Technology of China, Hefei230026, Anhui, China;2. School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai200240, China;3. Shanghai Aerospace Equipments Manufacturer, Shanghai200245, China)

To solve the large storage space and low computation efficiency in non-manifold modeling data structure and the limitation in manifold modeling in3D printing, an uniform data structure supporting manifold (regularized) and non-manifold (non-regularized) modeling was studied in this paper. Some boundary representation methods which were half edge data structure, radial data structure, hybrid edge data structure, cell complex and adjunction edge data structure for non-manifold modeling were analyzed. It found that the present data structures did not put effectively expressing non-manifold model, reducing data storage and improving operational efficiency together. So the data structure for non-manifold modeling based on complex was put forward. The geometrical model of non-manifold is represented completely through face, edge and vertex by reference, which realizes the uniform models of the wireframe, surface, solid and free curved surface. The object-oriented design is used and successiveness and derivation of class are applied also to reduce the data storage and improve the efficiency of the storage and computation. The extended Euler operator can provide the base for higher level Euler operation and Boolean operation. The unified data structure proposed uses pointer format in data structures of face, edge and vertex to avoid duplicated information. Tests have shown that it can represent the manifold and non-manifold modeling with enlarging domain of traditional3d model and effectively reducing the storage space.

3D printing; geometry model; manifold modeling; non manifold modeling; data structure; topological structure; calculating efficiency; storage space

1006-1630(2017)04-0158-06

2016-09-05；

：2016-10-25

航天先進(jìn)技術(shù)聯(lián)合研究中心技術(shù)創(chuàng)新項(xiàng)目資助(USCAST2015-23)

張成林(1983—)，男，碩士，主要研究方向?yàn)樵霾闹圃旒夹g(shù)、高端智能裝備研制。

TP391.73

：ADOI:10.19328/j.cnki.1006-1630.2017.04.019