三維CSG-BRep拓?fù)淠Ｐ偷难芯?/h1>
2017-07-01 19:15:19朱春曉倪春迪
測(cè)繪工程 2017年8期
朱春曉,黃 明,倪春迪
(1.黑龍江工程學(xué)院 測(cè)繪工程學(xué)院,黑龍江 哈爾濱 150050；2.北京建筑大學(xué),北京 100044)
三維CSG-BRep拓?fù)淠Ｐ偷难芯?/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ù)淠Ｐ?。該模型與普通三角網(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ù)淠Ｐ停沁€沒(méi)有好的方法來(lái)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)的訪問(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ù)淠Ｐ?，并無(wú)探究如何訪問(wèn)拓?fù)洹＂蹖?duì)相鄰空間體拓?fù)渲亟m有較好的方法，但是在處理相交空間體的拓?fù)潢P(guān)系重建困難。④多數(shù)拓?fù)淠Ｐ痛嬖跀?shù)據(jù)冗余，拓?fù)渑c幾何信息融合不全面的現(xiàn)象。本文針對(duì)這些問(wèn)題，按照面向?qū)ο蟮乃枷耄O(shè)計(jì)了一套系統(tǒng)的拓?fù)湓乇磉_(dá)，提出一種CSG-BREP拓?fù)淠Ｐ蛠?lái)描述模型內(nèi)部的拓?fù)潢P(guān)系。
1 基于CSG-BRep建立拓?fù)淠Ｐ?/h2>
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ù)淠Ｐ徒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ù)淠Ｐ?。?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ù)淠Ｐ徒Y(jié)構(gòu)
上級(jí)的拓?fù)湓匕瑢?duì)該元素下級(jí)拓?fù)湓氐囊谩Ｋ械囊枚际菑膹?fù)雜的拓?fù)湓氐胶?jiǎn)單的拓?fù)湓?。同時(shí)，簡(jiǎn)單的拓?fù)湓乜梢员徊煌膹?fù)雜的拓?fù)湓毓蚕怼Ｒ砸粋€(gè)復(fù)雜體為例，按照本文提出的拓?fù)淠Ｐ蛠?lái)描述復(fù)雜模型內(nèi)部的拓?fù)潢P(guān)系，如圖2所示。
圖2 拓?fù)淠Ｐ兔枋鰪?fù)雜體實(shí)例
在拓?fù)淠Ｐ椭?，只?種拓?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)相連邊的曲線端點(diǎn)。邊的容差是其三維曲線和其他任何表示方式之間的最大偏差。其幾何意義就是以容差為半徑沿邊的一個(gè)包含邊的三維曲線及其他任何形式表示的管子。面的容差的幾何意義是包圍面的一個(gè)具有厚度的板。通常情況下，必須滿(mǎn)足以下條件：當(dāng)邊位于面上，頂點(diǎn)位于邊上時(shí)，面的容差≤邊的容差≤頂點(diǎn)的容差。通過(guò)幾何點(diǎ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)系的訪問(wèn)也分為兩種：一種是訪問(wèn)拓?fù)鋵?duì)象本身與其父級(jí)拓?fù)鋵?duì)象的連接關(guān)系，另一種是訪問(wèn)拓?fù)鋵?duì)象本身與其子級(jí)拓?fù)鋵?duì)象的連接關(guān)系。本文實(shí)現(xiàn)這兩種拓?fù)潢P(guān)系的訪問(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ì)空間曲線、曲面，需要用到拓?fù)浞较虻膕hape有3種：通過(guò)頂點(diǎn)約束的曲線，通過(guò)邊約束的曲面和通過(guò)面約束的空間。不管是哪一種shape(該shape本身作為維數(shù)更高的空間幾何區(qū)域的邊界)，都定義兩個(gè)局部段，其中一個(gè)被指定為默認(rèn)段。對(duì)于一條通過(guò)頂點(diǎn)約束的曲線，首先曲線的參數(shù)表示必須給出曲線的一個(gè)方向(自然方向)，如設(shè)a≤u≤b，曲線C(u)方向?yàn)閺腃(a)到C(b)，而該曲線的默認(rè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ù)淠Ｐ偷亩x，拓?fù)湓L問(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ì)遍歷該元素多次。
父集遍歷，CSG-BRep模型的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)中，都是從上向下(從CSG_Shell或CSG_Solid到CSG_Vertex)的引用，不能像訪問(wèn)子集拓?fù)浣Y(jié)構(gòu)那樣直接從子集元素來(lái)訪問(wèn)該子集的父級(jí)元素。需根據(jù)邊，遍歷頂點(diǎn)并對(duì)頂點(diǎn)編碼，建立頂點(diǎn)與邊的映射，最后從頂點(diǎn)-邊的映射中提取父集。
2 實(shí)驗(yàn)及結(jié)果
本文利用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問(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)系。
3 結(jié) 論
本文設(shè)計(jì)了基于CSG-BREP的拓?fù)鋽?shù)據(jù)模型，該數(shù)據(jù)模型中包含了拓?fù)湓氐慕M成關(guān)系，拓?fù)湓嘏c幾何元素的結(jié)合，并按照面向?qū)ο蟮乃枷耄瑢?shí)現(xiàn)了三維模型生成，取得了較好的效果?；贑SG-BREP的拓?fù)鋽?shù)據(jù)模型，模型元素之間的連接關(guān)系清楚，有利于三維空間拓?fù)潢P(guān)系的查詢(xún)分析。該方法解決了目前大部分模型如三角網(wǎng)模型沒(méi)有詳細(xì)拓?fù)潢P(guān)系，以及僅具有拓?fù)淠Ｐ偷荒茏杂稍L問(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ù)淠Ｐ偷难芯縖J].測(cè)繪工程，2017，26(8)：20-23.
10.19349/j.cnki.issn1006-7949.2017.08.005
P208
A
1006-7949(2017)08-0020-04
猜你喜歡
由一道有關(guān)集合的子集個(gè)數(shù)題引發(fā)的思考語(yǔ)數(shù)外學(xué)習(xí)·高中版下旬(2023年7期)2023-09-25 00:45:13 拓?fù)淇臻g中緊致子集的性質(zhì)研究安慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2021年1期)2021-11-28 11:06:20 過(guò)非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58 關(guān)于奇數(shù)階二元子集的分離序列南京大學(xué)學(xué)報(bào)(數(shù)學(xué)半年刊)(2020年1期)2020-03-19 02:24:44 關(guān)于頂點(diǎn)染色的一個(gè)猜想山東科學(xué)(2018年6期)2018-12-20 11:08:58 針對(duì)路面建模的Delaunay三角網(wǎng)格分治算法智能計(jì)算機(jī)與應(yīng)用(2017年2期)2017-05-04 00:45:34 每一次愛(ài)情都只是愛(ài)情的子集都市麗人(2015年4期)2015-03-20 13:33:22 清華山維在地形圖等高線自動(dòng)生成中的應(yīng)用長(zhǎng)江工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)(2014年4期)2014-11-30 02:41:40 在AutoCAD環(huán)境下不規(guī)則三角網(wǎng)構(gòu)建及等高線生成地理空間信息(2011年2期)2011-09-27 10:43:24 基于合成算法的Delaunay三角網(wǎng)生成改進(jìn)算法長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)(2011年1期)2011-02-10 01:56:52
朱春曉,黃 明,倪春迪
(1.黑龍江工程學(xué)院 測(cè)繪工程學(xué)院,黑龍江 哈爾濱 150050；2.北京建筑大學(xué),北京 100044)
三維CSG-BRep拓?fù)淠Ｐ偷难芯?/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ù)淠Ｐ?。該模型與普通三角網(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ù)淠Ｐ停沁€沒(méi)有好的方法來(lái)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)的訪問(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ù)淠Ｐ?，并無(wú)探究如何訪問(wèn)拓?fù)洹＂蹖?duì)相鄰空間體拓?fù)渲亟m有較好的方法，但是在處理相交空間體的拓?fù)潢P(guān)系重建困難。④多數(shù)拓?fù)淠Ｐ痛嬖跀?shù)據(jù)冗余，拓?fù)渑c幾何信息融合不全面的現(xiàn)象。本文針對(duì)這些問(wèn)題，按照面向?qū)ο蟮乃枷耄O(shè)計(jì)了一套系統(tǒng)的拓?fù)湓乇磉_(dá)，提出一種CSG-BREP拓?fù)淠Ｐ蛠?lái)描述模型內(nèi)部的拓?fù)潢P(guān)系。
1 基于CSG-BRep建立拓?fù)淠Ｐ?/h2>
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ù)淠Ｐ徒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ù)淠Ｐ?。?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ù)淠Ｐ徒Y(jié)構(gòu)
上級(jí)的拓?fù)湓匕瑢?duì)該元素下級(jí)拓?fù)湓氐囊谩Ｋ械囊枚际菑膹?fù)雜的拓?fù)湓氐胶?jiǎn)單的拓?fù)湓?。同時(shí)，簡(jiǎn)單的拓?fù)湓乜梢员徊煌膹?fù)雜的拓?fù)湓毓蚕怼Ｒ砸粋€(gè)復(fù)雜體為例，按照本文提出的拓?fù)淠Ｐ蛠?lái)描述復(fù)雜模型內(nèi)部的拓?fù)潢P(guān)系，如圖2所示。
圖2 拓?fù)淠Ｐ兔枋鰪?fù)雜體實(shí)例
在拓?fù)淠Ｐ椭?，只?種拓?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)相連邊的曲線端點(diǎn)。邊的容差是其三維曲線和其他任何表示方式之間的最大偏差。其幾何意義就是以容差為半徑沿邊的一個(gè)包含邊的三維曲線及其他任何形式表示的管子。面的容差的幾何意義是包圍面的一個(gè)具有厚度的板。通常情況下，必須滿(mǎn)足以下條件：當(dāng)邊位于面上，頂點(diǎn)位于邊上時(shí)，面的容差≤邊的容差≤頂點(diǎn)的容差。通過(guò)幾何點(diǎ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)系的訪問(wèn)也分為兩種：一種是訪問(wèn)拓?fù)鋵?duì)象本身與其父級(jí)拓?fù)鋵?duì)象的連接關(guān)系，另一種是訪問(wèn)拓?fù)鋵?duì)象本身與其子級(jí)拓?fù)鋵?duì)象的連接關(guān)系。本文實(shí)現(xiàn)這兩種拓?fù)潢P(guān)系的訪問(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ì)空間曲線、曲面，需要用到拓?fù)浞较虻膕hape有3種：通過(guò)頂點(diǎn)約束的曲線，通過(guò)邊約束的曲面和通過(guò)面約束的空間。不管是哪一種shape(該shape本身作為維數(shù)更高的空間幾何區(qū)域的邊界)，都定義兩個(gè)局部段，其中一個(gè)被指定為默認(rèn)段。對(duì)于一條通過(guò)頂點(diǎn)約束的曲線，首先曲線的參數(shù)表示必須給出曲線的一個(gè)方向(自然方向)，如設(shè)a≤u≤b，曲線C(u)方向?yàn)閺腃(a)到C(b)，而該曲線的默認(rè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ù)淠Ｐ偷亩x，拓?fù)湓L問(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ì)遍歷該元素多次。
父集遍歷，CSG-BRep模型的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)中，都是從上向下(從CSG_Shell或CSG_Solid到CSG_Vertex)的引用，不能像訪問(wèn)子集拓?fù)浣Y(jié)構(gòu)那樣直接從子集元素來(lái)訪問(wèn)該子集的父級(jí)元素。需根據(jù)邊，遍歷頂點(diǎn)并對(duì)頂點(diǎn)編碼，建立頂點(diǎn)與邊的映射，最后從頂點(diǎn)-邊的映射中提取父集。
2 實(shí)驗(yàn)及結(jié)果
本文利用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問(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)系。
3 結(jié) 論
本文設(shè)計(jì)了基于CSG-BREP的拓?fù)鋽?shù)據(jù)模型，該數(shù)據(jù)模型中包含了拓?fù)湓氐慕M成關(guān)系，拓?fù)湓嘏c幾何元素的結(jié)合，并按照面向?qū)ο蟮乃枷耄瑢?shí)現(xiàn)了三維模型生成，取得了較好的效果?；贑SG-BREP的拓?fù)鋽?shù)據(jù)模型，模型元素之間的連接關(guān)系清楚，有利于三維空間拓?fù)潢P(guān)系的查詢(xún)分析。該方法解決了目前大部分模型如三角網(wǎng)模型沒(méi)有詳細(xì)拓?fù)潢P(guān)系，以及僅具有拓?fù)淠Ｐ偷荒茏杂稍L問(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ù)淠Ｐ偷难芯縖J].測(cè)繪工程，2017，26(8)：20-23.
10.19349/j.cnki.issn1006-7949.2017.08.005
P208
A
1006-7949(2017)08-0020-04
猜你喜歡
語(yǔ)數(shù)外學(xué)習(xí)·高中版下旬(2023年7期)2023-09-25 00:45:13
安慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2021年1期)2021-11-28 11:06:20
中等數(shù)學(xué)(2021年9期)2021-11-22 08:06:58
南京大學(xué)學(xué)報(bào)(數(shù)學(xué)半年刊)(2020年1期)2020-03-19 02:24:44
山東科學(xué)(2018年6期)2018-12-20 11:08:58
智能計(jì)算機(jī)與應(yīng)用(2017年2期)2017-05-04 00:45:34
都市麗人(2015年4期)2015-03-20 13:33:22
長(zhǎng)江工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)(2014年4期)2014-11-30 02:41:40
地理空間信息(2011年2期)2011-09-27 10:43:24
長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)(2011年1期)2011-02-10 01:56:52
