一種表示流形形體和非流形形體的統一數據結構研究

張成林，朱 琳，文珊珊，王 卓，王聯鳳

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

一種表示流形形體和非流形形體的統一數據結構研究

張成林1，朱 琳2，文珊珊3，王 卓3，王聯鳳3

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

為彌補3D打印中非流形拓撲數據結構的存儲空間大、運算效率低，流行拓撲數據結構形體表示的局限性，研究了一種可表示流形形體(正則形體)和非流形形體(非正則形體)的統一數據結構。分析了半邊數據結構、放射邊數據結構、混合邊數據結構、單元復形和粘合邊數據結構等非流形形體的邊界表示法，發現現有的數據結構未能綜合考慮幾何模型、存儲數據和效率。提出了一種基于復形的非流形數據結構：利用引用面、邊及點結構完整地表示非流形幾何模型，實現線框、表面、實體和自由曲面模型的統一；采用面向對象的設計方法，使用類的繼承與派生，以減少數據存儲量，提高存儲和運算效率；擴展歐拉算子可為更高級的歐拉操作和布爾操作提供基礎。設計的方法在模型的面、邊和點的數據設計中，以指針的形式管理和組織拓撲結構，避免信息的重復存儲，既滿足了豐富的形體表示需求，擴大了傳統3D打印模型的覆蓋域，又有效減少了存儲空間，提高了運算效率。

3D打?。?幾何模型； 流形形體； 非流形形體； 數據結構； 拓撲結構； 運算效率； 存儲空間

0 引言

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

1 邊界表示法

邊界表示方法能提供形體完整的邊界信息，以翼邊數據結構為代表的邊界表示方法在傳統實體造型技術中有重要的地位。對非流形形體的邊界表示，大量研究是在翼邊數據結構基礎上進行擴充和完善[4]。

1.1半邊數據結構

半邊數據結構是MANTYLA基于翼邊數據結構創建的[2]。半邊數據結構將翼邊數據結構中的一條整邊拆成兩條半邊，每條半邊各帶1個頂點作為起點，通過體(solid)-面(face)-環(loop)-半邊(halfedge)-頂點(vertex)五層拓撲描述形體。此外，為表示面與面間的相互聯系，又引入了一個邊(edge)附加拓撲元素聯系一對半邊，通過邊對鄰接面進行描述。這樣，半邊、邊和頂點三個拓撲元素就構成了半邊數據結構的最核心部分。半邊數據結構對表面流形表示進行了擴展，將非流形按特殊情況或偽流形進行處理，使非流形表示變得自然。但半邊數據結構的提出并非是為建立一種表示非流形形體的數據結構，其表示的形體是具非流形邊界的正則形體。

1.2放射邊數據結構

文獻[5]對非流形形體的表示進行了開創性研究，其研究目標是用統一的數據結構表示線框、表面和實體模型，允許在產品模型中存儲任何幾何信息。針對非流形形體中一條邊可有多個鄰面的情況，提出了放射邊數據結構的構想：在放射邊數據結構中，使用的幾何信息是面、環、邊、頂點，其拓撲層次是由模型(model)、區域(region)、殼(shell)、面引用(faceuse)、環引用(loopuse)、邊引用(edgeuse)、點引用(vertexuse)組成。放射邊數據結構將面、環、邊、點的幾何定義與其引用分離，使模型中的不同拓撲元素可共享相同的幾何信息，從而保證非流形形體數據的一致性。放射邊數據結構是第一種面向非流形形體表示而提出的數據結構，全面考慮了一般非流形形體的情況，實現了用統一的數據結構表示非流形形體的目標，提供了較正則形體更強的形體定義功能，為實現更簡單而統一的算法奠定了基礎。

1.3混合邊數據結構

文獻[6]提出的混合邊數據結構的基本思想是利用拓撲元素的層次性，將一個復雜幾何形狀表示為多個簡單幾何元素的組合。在混合邊數據結構中，每條邊的表示通過3個記錄實現：線段(segment)記錄2個和邊記錄1個，其算子被分為低層、中層、高層3個層次，高層算子根據低層算子構造，使其不涉及特定的實現細節，低層算子完成特定的工作。從概念上來說，混合邊數據結構是翼邊數據結構和半邊數據結構的組合，它在線段的層次維護多邊形(面)和實體的方向信息，在邊的層次處理面的鄰接信息，線框、表面和實體的混合表示在形狀(shape)的層次統一。算子的層次性構造避免了操作的冗余并增強了模型的語義集成?；旌线厰祿Y構實現了線框、表面、實體三種模型的統一與集成，但其表示的實體限于正則形體。

上述的邊界表示方法均建立在直觀的概念基礎上，但一個完整的非流形形體的數學定義對無二義地描述非流形形體至關重要。傳統的邊界表示是以流形作為其數學基礎，作為流形概念的自然擴展，非流形形體的邊界表示是以復形(complex)作為其數學基礎。

1.4單元復形

文獻[7]將非流形形體定義為數學上滿足三個條件的n維單元復形(n-cell complex)的集合。其中：第一個條件是三維單元復形能用0，1，2，3維單元的集合表示，即非流形模型可包含分離的頂點、邊、面和體；第二個條件是每個單元邊界必須由低維單元構成，因而非流形模型總是封閉的；第三個條件是要求所有拓撲元素不能出現自相交。此模型被稱為基于復形的非流形幾何模型，其拓撲層次結構如圖1所示。根據有限單元復形的Euler-Poincare公式，理論上只需9個獨立的歐拉算子及其逆算子就可構造所有的基于復形的非流形形體，但為有效描述高層運算，文獻[7]使用了17個擴展歐拉算子，用其描述局部操作和布爾運算。這種表示方法在幾何拓撲層次與放射邊數據結構相同，將線框、表面、實體模型在復形層次統一，在殼和環層次描述各維幾何元素出現的非流形形狀。

圖1 基于復形的層次結構Fig.1 Architecture based on complex

1.5粘合邊數據結構

文獻[8]將代數拓撲中復形的概念和方法引入非流形表示，給出了非流形的一個嚴格的數學定義，說明復形統一了三種模型，即零維骨架為全部頂點，一維骨架為棱集合+懸點(線框模型)，二維骨架為面集合+懸邊+懸點(表面模型)，三維骨架為三維實體(實體模型)。文獻[8]擴展了放射邊數據結構，提出了一種粘合邊數據結構，其中每條邊有多個粘合邊，每個粘合邊由2條有向邊組成。操作分為基本操作和高級操作兩種：基本操作包括生成單形、粘合及分離操作、擴展的歐拉操作等；高級操作包括掃描操作、驅動操作、分裂操作、布爾操作等。這種表示方法將非流形形體按復形進行描述，使非流形形體的表示有堅實的數學基礎。

上述各種非流形形體的邊界表示方法中，除半邊數據結構外，其余表示方法都實現了線框、表面、實體模型的統一。就該意義來說，它們是一致的，但其各自能表示的非流形形體和處理方法卻存在差異。放射邊數據結構及其變形的非流形形體覆蓋域最廣，是以面邊和點邊對作為其核心，重點是點邊，目的是為了表示一般的非流形形體。半邊數據結構是將有限的非流形形體按特殊情況或偽流形表示，目標是為實現操作的便利。混合邊數據結構主要是為統一3種模型，形體的表示限于正則形體，以代數拓撲中的復形概念為基礎，構造非流形模型，能在確定的表示域上統一線框、表面和實體模型，又使之具有堅實的數學基礎。此外，拓撲數據結構作為幾何造型的關鍵部分，其運算效率及存儲空間嚴重制約造型系統的功能和效率。

2 非流形結構

2.1拓撲結構

圖2 拓撲結構Fig.2 Topological structure

將代數拓撲中的單純復形和CW復形的概念和方法引入幾何造型系統中，建立以復形為基礎的統一的產品模型[9-11]。該模型的拓撲關系由復形中的鄰接關系決定，復形的定向決定模型中拓撲元素的方向，如圖2所示。模型的表示域為復形的伴隨多面體，此處多面體的概念與傳統的不同，根據代數拓撲學中復形理論可知：其表面可為復雜曲面。模型中的邊界采用以邊為基礎的B-rep表示，定義一個引用邊結構存儲邊的一個或若干個副本，并存儲方向，這樣就可表示出多個面共享一條邊的非流形結構，本文稱該結構為引用邊結構。引用邊結構能表示物體的懸面、懸邊、懸點等情況，以及物體的內部結構，它將一條邊的拓撲結構刻畫成2個層次，表示的拓撲元素間的邏輯關系簡潔、自然、直觀，人為因素少。同理定義引用面與引用點，將復形作為基本結構，有效而無二義性地表示了非流形結構。

2.2數據結構

形體在計算機內部的表示就是幾何造型的數據結構。數據結構是幾何建模的關鍵，直接影響整個CAD系統的功能效率。好的拓撲關系的數據結構應能完整無二義性地定義幾何實體；能方便快捷地訪問相關數據；作為CAD系統的底層支持，應為用戶提供功能強大而完備的技術支持和完善的產品信息?，F有的數據結構都未有效結合完整表示非流形幾何模型及減少存儲數據、提高運算效率，為此本文提出了一種基于復形的改進非流形數據結構，如圖3所示。圖3中：虛線框中的結構體是從其上實線表示的結構體派生出的。在數據結構設計中，盡量避免信息的重復存儲以求實現優化。在拓撲結構的面、邊、點結構中均存儲了該拓撲結構的幾何指針，使拓撲信息與幾何信息建立起關聯。

本文數據結構的特點如下。

a)拓撲信息與幾何信息分離，便于具體查詢各元素，獲取其信息；便于支持各種局部操作。

b)采用代數拓撲學中的復形結構，使非流形的表示有堅實的數學基礎，可統一表示線框、表面和實體。

c)由于采用復形為基礎的結構，既允許標準的集合運算，又允許正則的集合運算。

d)采用面向對象的設計方法，使用類的繼承與派生，減少了數據存儲量，便于運算。

圖3 非流形數據結構Fig.3 Non-manifold data structure

e)結構中的各元素鏈表均采用雙鏈表的存儲結構，適應了面表、邊表等信息頻繁修改的需要。

在圖形軟件中顯示的四種典型非流形形體如圖4所示，該軟件的圖形拓撲結構采用了本文的數據結構。

在不同軟件中，四組流形形體應用程序內存占用如圖5所示。圖5中：軟件1采用本文提出的數據結構；軟件2為金屬3D打印專用軟件AutoFab。

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

圖5 不同軟件流形形體應用程序內存占用

3 支持非流形結構的歐拉算子

3.1歐拉運算理論基礎

傳統的Euler算子不適于非流形物體，在代數拓撲中引入擴展的Eule-Poincare公式

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

C-Ch+Cc

(1)

式中：v，e，f，V，C分別為點數、邊數、面數、體數和復形數；r為環數；Vh，Vc，Ch，Cc分別為體的通孔數、體的穴數、復形的通孔數和復形的穴數。非流形幾何造型的拓撲算子及其逆算子為擴展的Euler算子，式(1)也成為檢驗非流形合法性的依據。

3.2擴展歐拉運算

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

圖6中箭頭表示運算方向，括號中為逆運算標。Make，kill均為一種操作，下劃線后的vertex，edge，……等拓撲元素是操作的對象。如第6種歐拉運算的正運算表示的是生成一條邊，刪除一個環。其他運算類似。

4 結束語

拓撲數據結構是3D打印技術中幾何建模的關鍵部分，其優劣直接影響整個打印系統的功能和效率，因此功能、效率、存儲空間間構造最優的拓撲數據結構尤為關鍵。本文對一種表示流形形體和非流形形體的統一數據結構進行了研究，提出了基于復形的改進非流形模型數據結構，利用引用面、邊及點結構可完整地表示非流形幾何模型，實現線框、表面、實體和自由曲面模型的統一，同時采用面向對象的設計方法，使用類的繼承與派生，減少了數據存儲量，提高了存儲和運算效率。給出的歐拉算子可為更高級的歐拉操作和布爾操作提供基礎，對3D打印模型發展有一定參考意義。后續可考慮數據結構的融合，提高數據存儲效率，減少內存用量。

圖6 擴展的支持非流形結構的歐拉運算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] 孫家廣, 楊長貴. 計算機圖形學[M]. 3版. 北京: 清華大學出版社, 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] 武仲科, 吳駿恒. 用復形方法建立統一的產品模型——關于下一代造型系統的研究[J]. 航空學報, 1995, 16(6): 662-670.

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

[10] 李元熹, 張國棟. 拓撲學[M]. 上海: 上?？茖W技術出版社, 1986.

[11] 蘇競存. 流形的拓撲學[M]. 武漢: 武漢大學出版社, 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

航天先進技術聯合研究中心技術創新項目資助(USCAST2015-23)

張成林(1983—)，男，碩士，主要研究方向為增材制造技術、高端智能裝備研制。

TP391.73

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