朱春曉,黃 明,倪春迪
(1.黑龍江工程學(xué)院 測(cè)繪工程學(xué)院,黑龍江 哈爾濱 150050;2.北京建筑大學(xué),北京 100044)
三維CSG-BRep拓?fù)淠P偷难芯?/p>
朱春曉1,黃 明2,倪春迪1
(1.黑龍江工程學(xué)院 測(cè)繪工程學(xué)院,黑龍江 哈爾濱 150050;2.北京建筑大學(xué),北京 100044)
針對(duì)目前通過(guò)離散點(diǎn)云來(lái)構(gòu)建的三角網(wǎng)模型具有數(shù)據(jù)量大,難以拆分,沒(méi)有拓?fù)潢P(guān)系等缺點(diǎn),提出一種特殊的CSG-BRep模型數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)可以全面細(xì)致地記錄模型內(nèi)部的拓?fù)潢P(guān)系。利用激光雷達(dá)點(diǎn)云作為模型的數(shù)據(jù)來(lái)源,結(jié)合文中提出的數(shù)據(jù)結(jié)構(gòu),構(gòu)建三維精細(xì)CSG-BRep拓?fù)淠P汀T撃P团c普通三角網(wǎng)模型相比,各個(gè)構(gòu)件可以拆分,所占用內(nèi)存較少,并具備更完善的拓?fù)潢P(guān)系。
拓?fù)潢P(guān)系;激光雷達(dá)點(diǎn)云;CSG-BRep模型;數(shù)據(jù)結(jié)構(gòu)
三維空間拓?fù)潢P(guān)系的研究對(duì)GIS數(shù)據(jù)建模、空間查詢(xún)、空間分析過(guò)程都具有舉足輕重的意義。目前,很多學(xué)者對(duì)三維模型拓?fù)潢P(guān)系的表達(dá)和構(gòu)建進(jìn)行了研究,如李霖,趙志剛,郭仁忠等提出體對(duì)象之間三維拓?fù)涞臉?gòu)建[1];邵振峰,李德仁,程啟敏提出通過(guò)體和影像來(lái)實(shí)現(xiàn)三維拓?fù)渲亟╗2];吳長(zhǎng)彬,閭國(guó)年分析了現(xiàn)階段空間拓?fù)潢P(guān)系的若干問(wèn)題[3];Patrick Erik Bradley, Norbert Paul提出了一種G映射方法來(lái)表達(dá)空間的拓?fù)浣Y(jié)構(gòu)[4];Simon Daum提出一種基于邊界表示BRep的方法來(lái)分析建筑信息模型BIM的拓?fù)湫畔5];Zhuojun Bao, Hans Grabowski提出一種將BRep轉(zhuǎn)化為精確二叉樹(shù)的方法來(lái)處理空間信息[6]等等。
但是,目前對(duì)三維空間拓?fù)涞难芯窟€處于初期階段,雖然專(zhuān)家學(xué)者提出了各自的拓?fù)淠P停沁€沒(méi)有好的方法來(lái)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)的訪(fǎng)問(wèn)[7]。對(duì)三維模型內(nèi)部拓?fù)浣Y(jié)構(gòu)的研究更是寥寥無(wú)幾。上述文獻(xiàn)中存在的問(wèn)題主要有以下五點(diǎn):①都是假設(shè)模型已經(jīng)存在,再去探究拓?fù)潢P(guān)系。②都是只提出各自的拓?fù)淠P?,并無(wú)探究如何訪(fǎng)問(wèn)拓?fù)?。③?duì)相鄰空間體拓?fù)渲亟m有較好的方法,但是在處理相交空間體的拓?fù)潢P(guān)系重建困難。④多數(shù)拓?fù)淠P痛嬖跀?shù)據(jù)冗余,拓?fù)渑c幾何信息融合不全面的現(xiàn)象。本文針對(duì)這些問(wèn)題,按照面向?qū)ο蟮乃枷耄O(shè)計(jì)了一套系統(tǒng)的拓?fù)湓乇磉_(dá),提出一種CSG-BREP拓?fù)淠P蛠?lái)描述模型內(nèi)部的拓?fù)潢P(guān)系。
1.1 CSG-BRep模型拓?fù)湓?/p>
模型是由基本要素構(gòu)成的,這些基本要素被抽象為點(diǎn)、邊、面、環(huán)、殼、體和復(fù)雜體以及復(fù)合體,呈現(xiàn)出由簡(jiǎn)單到復(fù)雜的遞進(jìn)關(guān)系,如表1所示。
表1 拓?fù)涓饕丶捌湟饬x
1.2 拓?fù)淠P徒Y(jié)構(gòu)
模型之中包含有復(fù)雜的拓?fù)溥B接關(guān)系[8-11]。利用構(gòu)造實(shí)體幾何的方法(CSG)可以方便地處理不同模型之間的拓?fù)錁?gòu)建,但是,單一的CSG表示方法局限到最小單元僅僅為體模型,并不能體現(xiàn)模型內(nèi)部拓?fù)潢P(guān)系。本文提出CSG與BRep結(jié)合的方式來(lái)建立拓?fù)淠P?。?shí)體的邊界是由面的并集來(lái)表示,而每個(gè)面由它所在的曲面的定義加上其邊界來(lái)表示,面的邊界是邊的并集,邊又由點(diǎn)來(lái)表示,如圖1所示。
拓?fù)渲?,頂點(diǎn)可以組成邊,邊可以組成環(huán),環(huán)又可以構(gòu)成面,面在進(jìn)一步組成殼或者體。由較低層級(jí)的拓?fù)鋵?duì)象逐級(jí)構(gòu)建成較高層級(jí)的拓?fù)鋵?duì)象,中間不可跨級(jí)組建。不可通過(guò)拓?fù)鋵?duì)象邊直接構(gòu)建面或者殼對(duì)象(頂點(diǎn)構(gòu)環(huán),面構(gòu)體除外)。同時(shí),由不同的體(solid)可以組建成復(fù)雜體(compsolid),而由上述的所有拓?fù)鋵?duì)象可以統(tǒng)一組成復(fù)合體(compound)。
圖1 基于CSG-BREP的拓?fù)淠P徒Y(jié)構(gòu)
上級(jí)的拓?fù)湓匕瑢?duì)該元素下級(jí)拓?fù)湓氐囊?。所有的引用都是從?fù)雜的拓?fù)湓氐胶?jiǎn)單的拓?fù)湓?。同時(shí),簡(jiǎn)單的拓?fù)湓乜梢员徊煌膹?fù)雜的拓?fù)湓毓蚕?。以一個(gè)復(fù)雜體為例,按照本文提出的拓?fù)淠P蛠?lái)描述復(fù)雜模型內(nèi)部的拓?fù)潢P(guān)系,如圖2所示。
圖2 拓?fù)淠P兔枋鰪?fù)雜體實(shí)例
在拓?fù)淠P椭校挥?種拓?fù)鋵?duì)象與幾何對(duì)象直接相關(guān)聯(lián):頂點(diǎn)(vertex)、邊(edge)、面(face),分別為Geo_Vertex、Geo_Edge、Geo_Face。另外,頂點(diǎn)、邊、面分別被分配一個(gè)容差(Tolerance)值,用于判定在誤差范圍內(nèi)頂點(diǎn)、邊和面是否生成。頂點(diǎn)容差T的幾何意義為以頂點(diǎn)為圓心半徑為T(mén)的球。這個(gè)球必須包含所有與這個(gè)頂點(diǎn)相連邊的曲線(xiàn)端點(diǎn)。邊的容差是其三維曲線(xiàn)和其他任何表示方式之間的最大偏差。其幾何意義就是以容差為半徑沿邊的一個(gè)包含邊的三維曲線(xiàn)及其他任何形式表示的管子。面的容差的幾何意義是包圍面的一個(gè)具有厚度的板。通常情況下,必須滿(mǎn)足以下條件:當(dāng)邊位于面上,頂點(diǎn)位于邊上時(shí),面的容差≤邊的容差≤頂點(diǎn)的容差。通過(guò)幾何點(diǎn)線(xiàn)面基本對(duì)象可以進(jìn)一步關(guān)聯(lián)到更復(fù)雜的幾何對(duì)象,那么,拓?fù)湫畔⒑蛶缀涡畔⒕屯耆苯踊蜷g接地關(guān)聯(lián)起來(lái)。與拓?fù)鋵?duì)象元素相關(guān)聯(lián)的幾何元素以及容差值的關(guān)系如圖3所示。
圖3 拓?fù)鋵?duì)象元素的幾何信息
拓?fù)湓刂校恳粋€(gè)元素都屬于實(shí)體(模型本身)的對(duì)象。其位于中間層級(jí)的拓?fù)鋵?duì)象同時(shí)具有與其相聯(lián)接的父級(jí)和子級(jí)拓?fù)鋵?duì)象。因此,拓?fù)潢P(guān)系的訪(fǎng)問(wèn)也分為兩種:一種是訪(fǎng)問(wèn)拓?fù)鋵?duì)象本身與其父級(jí)拓?fù)鋵?duì)象的連接關(guān)系,另一種是訪(fǎng)問(wèn)拓?fù)鋵?duì)象本身與其子級(jí)拓?fù)鋵?duì)象的連接關(guān)系。本文實(shí)現(xiàn)這兩種拓?fù)潢P(guān)系的訪(fǎng)問(wèn)。其中任意拓?fù)鋵?duì)象中包含3個(gè)變量,拓?fù)湮恢肅SGLocation,拓?fù)涑駽SGOrientation和子集實(shí)體CSG_Subshape。如圖4所示,子集實(shí)體中記錄和shape相連接的子集拓?fù)鋵?duì)象,位置記錄拓?fù)鋵?duì)象相對(duì)于世界坐標(biāo)系的旋轉(zhuǎn)矩陣,朝向記錄拓?fù)鋵?duì)象之間的方位。
圖4 shape成員變量組成關(guān)系
1.3 拓?fù)湮恢眉胺较?/p>
為了跟蹤拓?fù)湓氐奈恢?,每個(gè)形狀都定義一個(gè)局部坐標(biāo)系CSGLocation,如圖4所示。局部坐標(biāo)系可以通過(guò)如下兩種方式來(lái)表示:①右手法則表示的3個(gè)互相垂直的向量;②相對(duì)于世界坐標(biāo)系的變換。位置變量表示了初等矩陣經(jīng)過(guò)一系列變換后得到的坐標(biāo)系,用于保存累積變換后的結(jié)果,這能避免矩陣變換的重新計(jì)算。
拓?fù)浞较驅(qū)τ谟涗浲負(fù)湓氐姆轿痪哂袠O其重要的作用,并且拓?fù)浞较蚝瓦吔缇哂芯o密的聯(lián)系。本文采用參數(shù)方程來(lái)設(shè)計(jì)空間曲線(xiàn)、曲面,需要用到拓?fù)浞较虻膕hape有3種:通過(guò)頂點(diǎn)約束的曲線(xiàn),通過(guò)邊約束的曲面和通過(guò)面約束的空間。不管是哪一種shape(該shape本身作為維數(shù)更高的空間幾何區(qū)域的邊界),都定義兩個(gè)局部段,其中一個(gè)被指定為默認(rèn)段。對(duì)于一條通過(guò)頂點(diǎn)約束的曲線(xiàn),首先曲線(xiàn)的參數(shù)表示必須給出曲線(xiàn)的一個(gè)方向(自然方向),如設(shè)a≤u≤b,曲線(xiàn)C(u)方向?yàn)閺腃(a)到C(b),而該曲線(xiàn)的默認(rèn)段就是沿著曲線(xiàn)方向的一些列比頂點(diǎn)參數(shù)大的點(diǎn)的集合。對(duì)于一個(gè)通過(guò)邊約束的曲面,該曲面的默認(rèn)段位于邊前進(jìn)方向的左側(cè)。邊的前進(jìn)方向是指邊的自然方向,即逆時(shí)針?lè)较颉?duì)于一個(gè)通過(guò)面約束的空間,該空間的默認(rèn)段位于曲面法向相反的一側(cè)。
1.4 拓?fù)浔闅v
根據(jù)以上CSG-BREP拓?fù)淠P偷亩x,拓?fù)湓L(fǎng)問(wèn)包括shape的子集拓?fù)浣Y(jié)構(gòu)及shape的父集拓?fù)浣Y(jié)構(gòu)的遍歷。
子集遍歷,因?yàn)槿我庖粋€(gè)拓?fù)鋵?duì)象shape中直接包含了變量CSG_Subshape,而CSG_Subshape中包含了一個(gè)shape的列表,該列表中存放的是拓?fù)鋵?duì)象子集的集合,所以,直接從該集合中遍歷所需要查找的拓?fù)漕?lèi)型即可。另外,如果一個(gè)拓?fù)湓乇欢啻我玫脑?huà),那么可能會(huì)遍歷該元素多次。
父集遍歷,CSG-BRep模型的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)中,都是從上向下(從CSG_Shell或CSG_Solid到CSG_Vertex)的引用,不能像訪(fǎng)問(wèn)子集拓?fù)浣Y(jié)構(gòu)那樣直接從子集元素來(lái)訪(fǎng)問(wèn)該子集的父級(jí)元素。需根據(jù)邊,遍歷頂點(diǎn)并對(duì)頂點(diǎn)編碼,建立頂點(diǎn)與邊的映射,最后從頂點(diǎn)-邊的映射中提取父集。
本文利用VS2010作為開(kāi)發(fā)環(huán)境,利用C++語(yǔ)言進(jìn)行編程,本實(shí)驗(yàn)的數(shù)據(jù)源為利用三位激光掃描儀獲取的點(diǎn)云數(shù)據(jù),通過(guò)對(duì)點(diǎn)云數(shù)據(jù)擬合出基本體素長(zhǎng)方體、圓柱體等,構(gòu)建出具有拓?fù)潢P(guān)系的故宮太和門(mén)大木結(jié)構(gòu)CSG-BRep模型,如圖5所示。為了做比較,同時(shí)用第三方軟件Geomagic Studio12生成大木結(jié)構(gòu)的三角網(wǎng)模型,如圖6所示。
圖5 CSG-BRep大木結(jié)構(gòu)模型
圖6 普通三角網(wǎng)大木結(jié)構(gòu)模型
通過(guò)拓?fù)湓L(fǎng)問(wèn),查詢(xún)分析該CSG-BRep大木結(jié)構(gòu)模型,可以獲得該模型共包含81個(gè)圓柱體,148個(gè)長(zhǎng)方體,模型可拆分,具有詳細(xì)的拓?fù)潢P(guān)系,占用內(nèi)存的大小為336 KB。而根據(jù)離散點(diǎn)直接生成的普通三角網(wǎng)大木結(jié)構(gòu)模型,共包含3 991個(gè)點(diǎn),7 475個(gè)三角面片,模型不可拆分,只包含三角形3個(gè)頂點(diǎn)的連接關(guān)系,無(wú)完整的拓?fù)潢P(guān)系。占用內(nèi)存的大小為1 986 KB。
通過(guò)對(duì)比可知,本文提出的三維精細(xì)CSG-BRep模型,不僅有效地減少了數(shù)據(jù)量,而且模型可拆分,各部分構(gòu)件清晰明了,并且具備可查詢(xún)分析的拓?fù)潢P(guān)系。
本文設(shè)計(jì)了基于CSG-BREP的拓?fù)鋽?shù)據(jù)模型,該數(shù)據(jù)模型中包含了拓?fù)湓氐慕M成關(guān)系,拓?fù)湓嘏c幾何元素的結(jié)合,并按照面向?qū)ο蟮乃枷?,?shí)現(xiàn)了三維模型生成,取得了較好的效果。基于CSG-BREP的拓?fù)鋽?shù)據(jù)模型,模型元素之間的連接關(guān)系清楚,有利于三維空間拓?fù)潢P(guān)系的查詢(xún)分析。該方法解決了目前大部分模型如三角網(wǎng)模型沒(méi)有詳細(xì)拓?fù)潢P(guān)系,以及僅具有拓?fù)淠P偷荒茏杂稍L(fǎng)問(wèn)拓?fù)浣Y(jié)構(gòu)的問(wèn)題。
[1] 李霖,趙志剛,郭仁忠,等. 空間體對(duì)象間三維拓?fù)錁?gòu)建研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2012,37(6):719-723.
[2] 邵振峰,李德仁,程起敏. 基于航空立體影像對(duì)的復(fù)雜房屋三維拓?fù)渲亟╗J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2004,29(11):999-1003.
[3] 吳長(zhǎng)彬,閭國(guó)年.空間拓?fù)潢P(guān)系若干問(wèn)題研究現(xiàn)狀的評(píng)析[J].地球信息科學(xué)學(xué)報(bào),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] 賀彪,李霖,郭仁忠,等. 顧及外拓?fù)涞漠悩?gòu)建筑三維拓?fù)渲亟╗J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2011,36(5):579-583.
[11] 張海榮,余勁松弟,劉云生,等. 基于空間推理的巷道三維拓?fù)浣J]. 地理與地理信息科學(xué),2009,25(4):53-55.
[責(zé)任編輯:劉文霞]
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
黑龍江省教育廳科學(xué)技術(shù)研究資助項(xiàng)目(12531566)
朱春曉(1965-),女,高級(jí)工程師.
著錄:朱春曉,黃明,倪春迪.三維CSG-BRep拓?fù)淠P偷难芯縖J].測(cè)繪工程,2017,26(8):20-23.
10.19349/j.cnki.issn1006-7949.2017.08.005
P208
A
1006-7949(2017)08-0020-04