三維CSG-BRep拓撲模型的研究

朱春曉,黃 明,倪春迪

(1.黑龍江工程學院 測繪工程學院,黑龍江 哈爾濱 150050；2.北京建筑大學,北京 100044)

三維CSG-BRep拓撲模型的研究

朱春曉1,黃 明2,倪春迪1

(1.黑龍江工程學院 測繪工程學院,黑龍江 哈爾濱 150050；2.北京建筑大學,北京 100044)

針對目前通過離散點云來構建的三角網模型具有數據量大，難以拆分，沒有拓撲關系等缺點，提出一種特殊的CSG-BRep模型數據結構，該數據結構可以全面細致地記錄模型內部的拓撲關系。利用激光雷達點云作為模型的數據來源，結合文中提出的數據結構，構建三維精細CSG-BRep拓撲模型。該模型與普通三角網模型相比，各個構件可以拆分，所占用內存較少，并具備更完善的拓撲關系。

拓撲關系；激光雷達點云；CSG-BRep模型；數據結構

三維空間拓撲關系的研究對GIS數據建模、空間查詢、空間分析過程都具有舉足輕重的意義。目前，很多學者對三維模型拓撲關系的表達和構建進行了研究，如李霖，趙志剛，郭仁忠等提出體對象之間三維拓撲的構建[1]；邵振峰，李德仁，程啟敏提出通過體和影像來實現三維拓撲重建[2]；吳長彬，閭國年分析了現階段空間拓撲關系的若干問題[3]；Patrick Erik Bradley, Norbert Paul提出了一種G映射方法來表達空間的拓撲結構[4]；Simon Daum提出一種基于邊界表示BRep的方法來分析建筑信息模型BIM的拓撲信息[5]；Zhuojun Bao, Hans Grabowski提出一種將BRep轉化為精確二叉樹的方法來處理空間信息[6]等等。

但是，目前對三維空間拓撲的研究還處于初期階段，雖然專家學者提出了各自的拓撲模型，但是還沒有好的方法來實現拓撲結構的訪問[7]。對三維模型內部拓撲結構的研究更是寥寥無幾。上述文獻中存在的問題主要有以下五點：①都是假設模型已經存在，再去探究拓撲關系。②都是只提出各自的拓撲模型，并無探究如何訪問拓撲。③對相鄰空間體拓撲重建雖有較好的方法，但是在處理相交空間體的拓撲關系重建困難。④多數拓撲模型存在數據冗余，拓撲與幾何信息融合不全面的現象。本文針對這些問題，按照面向對象的思想，設計了一套系統的拓撲元素表達，提出一種CSG-BREP拓撲模型來描述模型內部的拓撲關系。

1 基于CSG-BRep建立拓撲模型

1.1 CSG-BRep模型拓撲元素

模型是由基本要素構成的，這些基本要素被抽象為點、邊、面、環、殼、體和復雜體以及復合體，呈現出由簡單到復雜的遞進關系，如表1所示。

表1 拓撲各要素及其意義

1.2 拓撲模型結構

模型之中包含有復雜的拓撲連接關系[8-11]。利用構造實體幾何的方法(CSG)可以方便地處理不同模型之間的拓撲構建，但是，單一的CSG表示方法局限到最小單元僅僅為體模型，并不能體現模型內部拓撲關系。本文提出CSG與BRep結合的方式來建立拓撲模型。實體的邊界是由面的并集來表示，而每個面由它所在的曲面的定義加上其邊界來表示，面的邊界是邊的并集，邊又由點來表示，如圖1所示。

拓撲中，頂點可以組成邊，邊可以組成環，環又可以構成面，面在進一步組成殼或者體。由較低層級的拓撲對象逐級構建成較高層級的拓撲對象，中間不可跨級組建。不可通過拓撲對象邊直接構建面或者殼對象(頂點構環，面構體除外)。同時，由不同的體(solid)可以組建成復雜體(compsolid)，而由上述的所有拓撲對象可以統一組成復合體(compound)。

圖1 基于CSG-BREP的拓撲模型結構

上級的拓撲元素包含對該元素下級拓撲元素的引用。所有的引用都是從復雜的拓撲元素到簡單的拓撲元素。同時，簡單的拓撲元素可以被不同的復雜的拓撲元素共享。以一個復雜體為例，按照本文提出的拓撲模型來描述復雜模型內部的拓撲關系，如圖2所示。

圖2 拓撲模型描述復雜體實例

在拓撲模型中，只有3種拓撲對象與幾何對象直接相關聯：頂點(vertex)、邊(edge)、面(face)，分別為Geo_Vertex、Geo_Edge、Geo_Face。另外，頂點、邊、面分別被分配一個容差(Tolerance)值，用于判定在誤差范圍內頂點、邊和面是否生成。頂點容差T的幾何意義為以頂點為圓心半徑為T的球。這個球必須包含所有與這個頂點相連邊的曲線端點。邊的容差是其三維曲線和其他任何表示方式之間的最大偏差。其幾何意義就是以容差為半徑沿邊的一個包含邊的三維曲線及其他任何形式表示的管子。面的容差的幾何意義是包圍面的一個具有厚度的板。通常情況下，必須滿足以下條件：當邊位于面上，頂點位于邊上時，面的容差≤邊的容差≤頂點的容差。通過幾何點線面基本對象可以進一步關聯到更復雜的幾何對象，那么，拓撲信息和幾何信息就完全直接或間接地關聯起來。與拓撲對象元素相關聯的幾何元素以及容差值的關系如圖3所示。

圖3 拓撲對象元素的幾何信息

拓撲元素中，每一個元素都屬于實體(模型本身)的對象。其位于中間層級的拓撲對象同時具有與其相聯接的父級和子級拓撲對象。因此，拓撲關系的訪問也分為兩種：一種是訪問拓撲對象本身與其父級拓撲對象的連接關系，另一種是訪問拓撲對象本身與其子級拓撲對象的連接關系。本文實現這兩種拓撲關系的訪問。其中任意拓撲對象中包含3個變量，拓撲位置CSGLocation，拓撲朝向CSGOrientation和子集實體CSG_Subshape。如圖4所示，子集實體中記錄和shape相連接的子集拓撲對象，位置記錄拓撲對象相對于世界坐標系的旋轉矩陣，朝向記錄拓撲對象之間的方位。

圖4 shape成員變量組成關系

1.3 拓撲位置及方向

為了跟蹤拓撲元素的位置，每個形狀都定義一個局部坐標系CSGLocation，如圖4所示。局部坐標系可以通過如下兩種方式來表示：①右手法則表示的3個互相垂直的向量；②相對于世界坐標系的變換。位置變量表示了初等矩陣經過一系列變換后得到的坐標系，用于保存累積變換后的結果，這能避免矩陣變換的重新計算。

拓撲方向對于記錄拓撲元素的方位具有極其重要的作用，并且拓撲方向和邊界具有緊密的聯系。本文采用參數方程來設計空間曲線、曲面，需要用到拓撲方向的shape有3種：通過頂點約束的曲線，通過邊約束的曲面和通過面約束的空間。不管是哪一種shape(該shape本身作為維數更高的空間幾何區域的邊界)，都定義兩個局部段，其中一個被指定為默認段。對于一條通過頂點約束的曲線，首先曲線的參數表示必須給出曲線的一個方向(自然方向)，如設a≤u≤b，曲線C(u)方向為從C(a)到C(b)，而該曲線的默認段就是沿著曲線方向的一些列比頂點參數大的點的集合。對于一個通過邊約束的曲面，該曲面的默認段位于邊前進方向的左側。邊的前進方向是指邊的自然方向，即逆時針方向。對于一個通過面約束的空間，該空間的默認段位于曲面法向相反的一側。

1.4 拓撲遍歷

根據以上CSG-BREP拓撲模型的定義，拓撲訪問包括shape的子集拓撲結構及shape的父集拓撲結構的遍歷。

子集遍歷，因為任意一個拓撲對象shape中直接包含了變量CSG_Subshape，而CSG_Subshape中包含了一個shape的列表，該列表中存放的是拓撲對象子集的集合，所以，直接從該集合中遍歷所需要查找的拓撲類型即可。另外，如果一個拓撲元素被多次引用的話，那么可能會遍歷該元素多次。

父集遍歷，CSG-BRep模型的拓撲數據結構中，都是從上向下(從CSG_Shell或CSG_Solid到CSG_Vertex)的引用，不能像訪問子集拓撲結構那樣直接從子集元素來訪問該子集的父級元素。需根據邊，遍歷頂點并對頂點編碼，建立頂點與邊的映射，最后從頂點-邊的映射中提取父集。

2 實驗及結果

本文利用VS2010作為開發環境，利用C++語言進行編程，本實驗的數據源為利用三位激光掃描儀獲取的點云數據，通過對點云數據擬合出基本體素長方體、圓柱體等，構建出具有拓撲關系的故宮太和門大木結構CSG-BRep模型，如圖5所示。為了做比較，同時用第三方軟件Geomagic Studio12生成大木結構的三角網模型，如圖6所示。

圖5 CSG-BRep大木結構模型

圖6 普通三角網大木結構模型

通過拓撲訪問，查詢分析該CSG-BRep大木結構模型，可以獲得該模型共包含81個圓柱體，148個長方體，模型可拆分，具有詳細的拓撲關系，占用內存的大小為336 KB。而根據離散點直接生成的普通三角網大木結構模型，共包含3 991個點，7 475個三角面片，模型不可拆分，只包含三角形3個頂點的連接關系，無完整的拓撲關系。占用內存的大小為1 986 KB。

通過對比可知，本文提出的三維精細CSG-BRep模型，不僅有效地減少了數據量，而且模型可拆分，各部分構件清晰明了，并且具備可查詢分析的拓撲關系。

3 結 論

本文設計了基于CSG-BREP的拓撲數據模型，該數據模型中包含了拓撲元素的組成關系，拓撲元素與幾何元素的結合，并按照面向對象的思想，實現了三維模型生成，取得了較好的效果。基于CSG-BREP的拓撲數據模型，模型元素之間的連接關系清楚，有利于三維空間拓撲關系的查詢分析。該方法解決了目前大部分模型如三角網模型沒有詳細拓撲關系，以及僅具有拓撲模型但不能自由訪問拓撲結構的問題。

[1] 李霖，趙志剛，郭仁忠，等. 空間體對象間三維拓撲構建研究[J].武漢大學學報(信息科學版)，2012，37(6)：719-723.

[2] 邵振峰，李德仁，程起敏. 基于航空立體影像對的復雜房屋三維拓撲重建[J]. 武漢大學學報(信息科學版)，2004，29(11)：999-1003.

[3] 吳長彬，閭國年.空間拓撲關系若干問題研究現狀的評析[J].地球信息科學學報，2010，12(4)：524-531.

[4] BRADLEY P E, PAUL N. Comparing G-maps with other topological data structures[J]. Springer Journal of GeoInformatica，2014(3).

[5] DAUM S, BORRMANN A. Processing of Topological BIM Queries using Boundary Representation Based Methods[J]. Elsevier Journal of Advanced Engineering Informatics, 2014.

[6] BAO Zhuojun, GRABOWSKI H. Converting boundary representations to exact bintrees[J]. Elsevier Journal of Computers in Industry, 1998,37(1).

[7] LIU K,SHI W Z. Extended Model of Topological Relations between Spatial Objects in Geographic Information Systems[J]. International Journal of Applied Earth Observation and Geoinformation, 2007, 9: 264-275.

[8] NONAKA Hideki, OHSAWA Yutaka. A Method of Caching Topology on Implicit Topology Model[J]. J-STAGE Journals of Theory and Applications of GIS, 2003,11(1).

[9] NIAN Rui, HE Bo, LENDASSE A. 3D object recognition based on a geometrical topology model and extreme learning machine[J]. Springer Journal of Neural Computing and Applications, 2013,22(3).

[10] 賀彪,李霖,郭仁忠,等. 顧及外拓撲的異構建筑三維拓撲重建[J]. 武漢大學學報(信息科學版)，2011，36(5)：579-583.

[11] 張海榮,余勁松弟,劉云生,等. 基于空間推理的巷道三維拓撲建立[J]. 地理與地理信息科學，2009，25(4)：53-55.

[責任編輯：劉文霞]

Research on the topological model of three-dimensional CSG-BRep

ZHU Chunxiao1,HUANG Ming2,NI Chundi1

(1.College of Surveying and Mapping Engineering,Heilongjiang Institute of Technology,Harbin 150050,China;2.Beijing University of Civil Engineering and Architbcture,Beijing 100044,China )

Currently ordinary triangular mesh model based on discrete point cloud has a large amount of data. This model is not only difficult to split, but also lacks of topological relations. To solve these problems, this paper presents a CSG-BRep topological model . It can record topological relationship of 3D model in great detail. Finally, LIDAR point cloud is used as a data source to construct 3D CSG-BRep topological model. Compared with the ordinary triangular mesh model, the model components can be split, which can effectively reduce the amount of data. In addition, the CSG-BRep model has the detailed topological relations.

topological relation；LIDAR；CSG-Brep model；data structure

2017-01-09

黑龍江省教育廳科學技術研究資助項目(12531566)

朱春曉(1965-)，女，高級工程師.

著錄：朱春曉,黃明,倪春迪.三維CSG-BRep拓撲模型的研究[J].測繪工程，2017，26(8)：20-23.

10.19349/j.cnki.issn1006-7949.2017.08.005

P208

A

1006-7949(2017)08-0020-04