基于實(shí)測(cè)輪廓線的岔道口三維實(shí)體建模方法

譚正華,王烈奇,王李管,陳建宏

(1.湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105; 2.中南大學(xué)資源與安全工程學(xué)院,長(zhǎng)沙410083)

基于實(shí)測(cè)輪廓線的岔道口三維實(shí)體建模方法

譚正華1,王烈奇1,王李管2,陳建宏2

(1.湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105; 2.中南大學(xué)資源與安全工程學(xué)院,長(zhǎng)沙410083)

在數(shù)字礦山系統(tǒng)中,為使錯(cuò)綜復(fù)雜的地下巷道重建效果能達(dá)到礦山的驗(yàn)收標(biāo)準(zhǔn),根據(jù)實(shí)測(cè)巷道交岔口輪廓線,采用分區(qū)(分塊)建模思想,提出一種基于實(shí)測(cè)輪廓線的岔道口三維實(shí)體建模方法。將實(shí)測(cè)的岔道口輪廓數(shù)據(jù)按其特點(diǎn)分為頂?shù)装搴蛡?cè)面輪廓線點(diǎn)集,采用凸包算法構(gòu)造頂?shù)装宓暮?jiǎn)單多邊形,并對(duì)其進(jìn)行三角化。根據(jù)頂?shù)装宥噙呅雾旤c(diǎn)的先后順序關(guān)系,建立側(cè)面輪廓線的相鄰關(guān)系,并采用連線框算法對(duì)相鄰輪廓線進(jìn)行三角化。實(shí)驗(yàn)結(jié)果表明,該方法簡(jiǎn)單有效,可解決任意斷面形狀、多個(gè)岔道口的建模問(wèn)題,并且已經(jīng)應(yīng)用于DIMINE軟件的測(cè)量插件中,效果良好。

地下巷道;岔道口;實(shí)測(cè)輪廓線;分區(qū)建模;三角剖分;凸包

1 概述

地下巷道岔道口的三維建模是指根據(jù)井下開(kāi)拓、采準(zhǔn)等工程驗(yàn)收測(cè)量的數(shù)據(jù)生成三維實(shí)體模型的方法,是礦業(yè)開(kāi)發(fā)過(guò)程中不可缺少的基礎(chǔ)技術(shù)工作。很多學(xué)者在岔道口建模方面做了深入研究。文獻(xiàn)[1]仿照了弧段-節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)思想,利用曲線插值對(duì)巷道間節(jié)點(diǎn)進(jìn)行處理,但其方法重建的岔道口三維模型會(huì)出現(xiàn)扭曲現(xiàn)象。研究者基于斷面中線法實(shí)現(xiàn)了巷道三維實(shí)體建模,但在巷道交岔口的處理上各自存在一定缺點(diǎn):文獻(xiàn)[2]運(yùn)用三維直線求交,但在岔道口處不能圓滑連接;文獻(xiàn)[3]通過(guò)加載巷道斷面,沒(méi)有考慮岔道口各巷道寬度變化、巷道截面形狀的多樣化;文獻(xiàn)[4]則運(yùn)用布爾運(yùn)算,但在巷道接口處沒(méi)有進(jìn)行圓滑處理;文獻(xiàn)[5]通過(guò)提取CAD平面圖的關(guān)鍵點(diǎn),若岔道的寬度或形狀不一樣,則在接口處不能圓滑連接。文獻(xiàn)[6]將巷道分為結(jié)點(diǎn)、節(jié)點(diǎn)和巷道中線三類基本元素,在巷道接口處,刪除相交產(chǎn)生的公共面,添加相交未閉合的部分,實(shí)現(xiàn)了巷道的三維建模,但其處理過(guò)程復(fù)雜。文獻(xiàn)[7]提出了巷道對(duì)稱建模方法,在交岔口處把三岔口輪廓線分成三個(gè)對(duì)稱多邊形,把十字型岔道口輪廓線分為四個(gè)對(duì)稱多邊形,用線框建模原理進(jìn)行重建,但此方法沒(méi)有考慮巷道交岔口處平滑拼接問(wèn)題。

地下礦山中存在許多實(shí)測(cè)的岔道口輪廓數(shù)據(jù),形象描述了巷道間的貫通情況,因此基于實(shí)測(cè)輪廓線的三維建模更接近實(shí)際。本文采用分區(qū)建模思想,設(shè)計(jì)一種基于實(shí)測(cè)巷道交岔口輪廓線,構(gòu)造頂、底板和腰,生成地下巷道岔道口三維實(shí)體模型的方法。

2 算法原理及流程

實(shí)測(cè)岔道口輪廓線,可以看作是由多個(gè)線圈組成,圖1所示的三岔口輪廓線則是由S0,S1,S23個(gè)線圈組成。圖1(a)中點(diǎn)A,B,C為三線圈高程值最大的點(diǎn),點(diǎn)D,Q,T,P,M,N分別為線圈S0,S1,S2高程值最小的點(diǎn)。圖1(b)中S0,S1,S2三線圈高程值最大的點(diǎn)分別為A-B,C-E,F-G之間一系列點(diǎn)。

圖1 岔道口斷面輪廓線示意圖

分區(qū)建模的思想如下:采用三維空間坐標(biāo)點(diǎn)來(lái)表示線圈上的點(diǎn),遍歷各個(gè)線圈找出高程值最小和最大點(diǎn)(集);分別求取頂、底板點(diǎn)集凸多邊形,并對(duì)頂、底板簡(jiǎn)單凸多邊形進(jìn)行快速三角化;根據(jù)頂(底)板簡(jiǎn)單多邊形頂點(diǎn)之間的先后順序關(guān)系,建立側(cè)面輪廓線的相鄰關(guān)系;最后采用連線框方法對(duì)相鄰輪廓線進(jìn)行建模。建模流程如圖2所示。

圖2 三維岔道口建模流程

3 算法過(guò)程

3.1 頂?shù)装鍞?shù)據(jù)的提取

點(diǎn)的類C語(yǔ)言定義如下,其中,m_x,m_y,m_z分別表示該點(diǎn)的x,y,z坐標(biāo)。

遍歷各個(gè)線圈所有數(shù)據(jù),將高程值最小的點(diǎn)集存儲(chǔ)到數(shù)組m_ptDownArray,將高程值最大的點(diǎn)集存儲(chǔ)到數(shù)組 m_ptUpArray。每個(gè)線圈數(shù)據(jù)已分成4個(gè)部分:底板數(shù)據(jù),頂板數(shù)據(jù),以及以頂(底)板點(diǎn)為參考點(diǎn)的左邊、右邊線圈數(shù)據(jù)。表示如下:

3.2 頂?shù)装逋苟噙呅蔚慕?/p>

平面點(diǎn)集S的凸殼CH(S)是包含S的最小凸集[11]。求取凸殼算法已經(jīng)相對(duì)成熟穩(wěn)定。文獻(xiàn)[8]利用排序算法與簡(jiǎn)單多邊形凸包算法相結(jié)合的方法,采用文獻(xiàn)[9]算法棧結(jié)構(gòu)處理結(jié)構(gòu)和文獻(xiàn)[10]算法思想,簡(jiǎn)單而快速地求取平面點(diǎn)集的凸包。借鑒文獻(xiàn)[8]的方法,快速求取頂、底板平面點(diǎn)集的凸包。由于底板與頂板凸殼求取方法類似,以頂板凸殼的求取方法為例:

步驟1 取出ptUPArray中的點(diǎn)集,將其投影到底板平面。

步驟2 將此點(diǎn)集按最優(yōu)排序算法排序。

步驟3 順序連結(jié)相鄰的頂點(diǎn),串連形成簡(jiǎn)單多邊形。

步驟4 利用前瞻回溯法搜索簡(jiǎn)單多邊形,得到平面點(diǎn)集的凸包。

步驟5 最后給頂板平面的點(diǎn)賦相應(yīng)的高程。

生成的頂板凸殼與底板凸殼示意圖見(jiàn)圖3。

圖3 三岔口頂板與底板凸殼

3.3 簡(jiǎn)單多邊形的快速三角化

簡(jiǎn)單多邊形的三角剖分就是在不產(chǎn)生新頂點(diǎn)的條件下將簡(jiǎn)單多邊形分解為一系列不相重疊的三角形[13]。很多學(xué)者對(duì)簡(jiǎn)單多邊的三角剖分算法有深入的研究[13-16]。其中文獻(xiàn)[16]提出的快速三角化算法適合有序的任意簡(jiǎn)單多邊形,時(shí)間復(fù)雜度為O(n),用此文獻(xiàn)的方法,對(duì)岔道口輪廓的頂板與底板簡(jiǎn)單多邊形進(jìn)行三角化,生成結(jié)果示意圖如圖4所示。

圖4 多邊形區(qū)域三角化示意圖

3.4 相鄰輪廓線關(guān)系的確立與建模

3.4.1 輪廓線相鄰關(guān)系的確定

在求取頂、底板凸多邊形的過(guò)程中已經(jīng)對(duì)頂、底板上的點(diǎn)集進(jìn)行了排序,因而可以把頂(底)板凸多邊形上的頂點(diǎn)序列視為線圈序列。

三岔口俯視圖如圖5所示。假設(shè)線圈順序與圖中線圈S0,S1,S2順序一致。對(duì)于實(shí)測(cè)輪廓線圈數(shù)據(jù),利用已經(jīng)提取出來(lái)了的底板數(shù)據(jù)與頂板數(shù)據(jù),根據(jù)線圈上各點(diǎn)的x值或y值的差異生成以頂板頂點(diǎn)為參照點(diǎn)的左邊、右邊輪廓數(shù)據(jù)。

三心拱俯視圖如圖5(a)所示,線圈S0中A-Q所代表的輪廓數(shù)據(jù)與線圈S1中的B-T所代表的輪廓數(shù)據(jù)相鄰,按順時(shí)針?lè)较虮闅v一周,所有線圈的相鄰關(guān)系都已確定。梯形拱側(cè)面輪廓數(shù)據(jù)示意圖如圖5(b)所示,線圈S0中B-Q所代表的輪廓數(shù)據(jù)與線圈S1中的C-T所代表的輪廓數(shù)據(jù)相鄰,按順時(shí)針?lè)较虮闅v一周,可知,線圈S1中E-P所代表的輪廓數(shù)據(jù)與線圈S2中的F-M所代表的輪廓數(shù)據(jù)相鄰,線圈S2中G-N所代表的輪廓數(shù)據(jù)與線圈S0中的A-D所代表的輪廓數(shù)據(jù)相鄰。

圖5 三岔口俯視圖

3.4.2 相鄰輪廓線的建模

在生成了底板與頂板三角化網(wǎng)格之后,基于實(shí)測(cè)輪廓線的岔道口建模問(wèn)題轉(zhuǎn)化為基于底板與頂板輪廓線重建其相鄰輪廓線表面的問(wèn)題?；谖矬w表面輪廓線[17-19]的三維重建方法已經(jīng)很成熟。根據(jù)相鄰截面輪廓曲線一般具有相似這一性質(zhì),文獻(xiàn)[18]首先對(duì)輪廓曲線上的點(diǎn)進(jìn)行預(yù)處理后,采用角點(diǎn)測(cè)法與多邊形法結(jié)合的方法來(lái)計(jì)算控制點(diǎn),再對(duì)其進(jìn)行分塊,然后在分塊后的小曲線段上進(jìn)行三角劃分,實(shí)現(xiàn)了一種對(duì)物體表面進(jìn)行三角劃分的方法。由于此方法沒(méi)有考慮控制點(diǎn)一對(duì)多的情況,文獻(xiàn)[19]對(duì)文獻(xiàn)[18]的方法進(jìn)行了改進(jìn):(1)采用一種改進(jìn)的CSS方法對(duì)輪廓曲線角點(diǎn)進(jìn)行提取。(2)采用了一種新的配對(duì)方法對(duì)角點(diǎn)進(jìn)行配對(duì),根據(jù)曲線間距離設(shè)定動(dòng)態(tài)閾值。(3)輪廓相似性判斷。(4)在相似輪廓線之間根據(jù)配對(duì)的情況來(lái)分塊。在分塊后的小曲線段上進(jìn)行簡(jiǎn)單三角劃分與文獻(xiàn)[17]所用的方法一樣。采用文獻(xiàn)[19]中的方法對(duì)左右輪廓線進(jìn)行連線框操作,生成了三維岔道口實(shí)體表面模型?；诜謱虞喞€的網(wǎng)格三角化如圖6所示。

圖6 基于分層輪廓線的網(wǎng)格三角化

4 算法分析和應(yīng)用

4.1 算法時(shí)間復(fù)雜度分析

該算法的時(shí)間復(fù)雜度分析如下:

(1)凸殼的形成,設(shè)頂板的頂點(diǎn)數(shù)目為k,排序算法的最壞時(shí)間復(fù)雜度為O(klog(k)),將點(diǎn)集按順序連接成簡(jiǎn)單多邊形的時(shí)間復(fù)雜度為O(k),求取簡(jiǎn)單多邊形凸包的時(shí)間復(fù)雜度為O(k),因此,頂板建模的復(fù)雜度為O(klog(k)),同理,設(shè)底板的頂點(diǎn)數(shù)目為m,則底板建模復(fù)雜度為O(mlog(m))。

(2)簡(jiǎn)單多邊形的三角化,頂、底板凸多邊形的頂點(diǎn)數(shù)分別為k、m,三角化的時(shí)間復(fù)雜度為O(k)+O(m)。

(3)提取頂?shù)装鍞?shù)據(jù)、連線框算法,時(shí)間復(fù)雜度與頂點(diǎn)數(shù)目都接近線性,故總的時(shí)間復(fù)雜度為:O(klog(k))+O(mlog(m))。

4.2 應(yīng)用實(shí)例

在Windows XP操作系統(tǒng)上,通過(guò)VC++開(kāi)發(fā)工具和 HOOPS可視化工具包實(shí)現(xiàn)了該算法?！癉IMINE”數(shù)字礦山軟件系統(tǒng)是中南大學(xué)數(shù)字礦山研究中心研發(fā)的一套集礦床地質(zhì)建模、礦山工程測(cè)量和地下、露天礦床開(kāi)采設(shè)等于一體的智能化、可視化軟件系統(tǒng)。該系統(tǒng)的礦山工程測(cè)量和出圖模型采用了該算法。此算法應(yīng)用于某礦山巷道建模實(shí)例如圖7所示,其局部精細(xì)圖如圖7(b)(圖7(a)中①)、圖7(c)(圖7(a)中②)所示。

另外,當(dāng)線圈頂點(diǎn)的數(shù)目為任意多個(gè),此算法能穩(wěn)定地重建出三維岔道口實(shí)體模型;當(dāng)線圈形狀為三角形、圓和不規(guī)則多邊形等極致情況,算法也能穩(wěn)定的重建出三維岔道口實(shí)體模型;當(dāng)線圈數(shù)目為任意多個(gè),算法依然能穩(wěn)定的重建出三維岔道口實(shí)體模型。

圖7 巷道渲染圖

5 結(jié)束語(yǔ)

本文提出一種實(shí)測(cè)地下巷道岔道口三維建模方法。該方法采用分區(qū)建模思想,將實(shí)測(cè)岔道口輪廓數(shù)據(jù)按其特點(diǎn)進(jìn)行分類,采用凸包算法、連線框算法和網(wǎng)格三角化算法,建立了虛擬系統(tǒng)中的三維岔道口實(shí)體,解決了數(shù)字礦山三維實(shí)測(cè)巷道重建的難點(diǎn)問(wèn)題,該方法具有以下優(yōu)點(diǎn):(1)能有效地解決任意斷面形狀的岔道口建模問(wèn)題。(2)能有效解決由任意多個(gè)巷道組成的岔道口建模問(wèn)題。(3)適用于包含2個(gè)線圈的單體實(shí)測(cè)巷道建模問(wèn)題。

［1］ 魏占營(yíng),王寶山,李青元.地下巷道的三維建模及C++實(shí)現(xiàn)［J］.武漢大學(xué)學(xué)報(bào),2005,30(7):650-653.

［2］ 汪云甲,伏永明.礦井巷道三維自動(dòng)建模方法研究［J］.武漢大學(xué)學(xué)報(bào),2006,31(12):1097-1099.

［3］ 葛永慧,王建民.礦井三維巷道建模方法的研究［J］.工程勘察,2006,(10):46-49.

［4］ 徐志強(qiáng),楊邦榮,王李管,等.巷道實(shí)體的三維建模研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用,2008,44(6):202-205.

［5］ 萬(wàn) 金,張 凱,陳建勛.一種三維地下巷道建模的改進(jìn)方法［J］.工業(yè)控制計(jì)算機(jī),2012,25(8):85-87.

［6］ 謝義林,汪云甲.姚連璧.巷道三維構(gòu)模及虛擬交互研究［J］.計(jì)算機(jī)工程與應(yīng)用,2009,45(23):231-235.

［7］ 張志華,侯恩科,趙 洲,等.一種新的3D巷道建模方法——對(duì)稱建模法［J］.金屬礦山,2009,39(5):107-111.

［8］ 金文華,何 濤,劉曉平,等.基于有序簡(jiǎn)單多邊形的平面點(diǎn)集凸包快速求取算法［J］.計(jì)算機(jī)學(xué)報(bào),1998, 21(6):533-539.

［9］ Chen Chern-Lin.Computing the Convex Hull of a Simple Polygon［J］.Pattern Recognition,1989,22(5):561-565.

［10］ Sklansky J.Measuring Concavity on Rectangular Mosaic［J］.IEEE Transactions on Computers,1972,21(12): 1355-1364.

［11］ 周培德.計(jì)算幾何—算法分析與設(shè)計(jì)［M］.北京:清華大學(xué)出版社,2000.

［12］ 程三友,李英杰.一種新的最小凸包算法及其應(yīng)用［J］.地理與地理信息科學(xué),2009,25(5):43-45.

［13］ 馬小虎,潘志庚,石教英.基于凹凸頂點(diǎn)判定的簡(jiǎn)單多邊形Delaunay三角剖分［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),1999,11(1):101-104.

［14］ Gareym R,Johnsond S,Preparata F P.Triangulating a Simple Polygon［J］.Information Proceeding Letters, 1978,7(4):175-179.

［15］ Seidel R.A Simple and fast Incremental Randomized Algorithm Forcomputing Trapezoidal Decompositions and for Triangulating Polygons［J］.Comput Geom Theory Appl,1991,1(1):51-64.

［16］ 畢 林,王李管,陳建宏,等.快速多邊形區(qū)域三角化算法與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用研究,2008,25(10):3030-3033.

［17］ Keppel E.Approximating Complex Surface Interpolation Technique for Reconstruction 3D Objects from Serial Cross-sections［J］.Graphical Models and Image Processing,1989,48(1):124-143.

［18］ 周 焰,李德華,陳振羽,等.三維物體表面三角劃分的快速算法［J］.中國(guó)圖像圖形學(xué)報(bào),2000,5(9):764-768.

［19］ 周 焰,李德榮,徐長(zhǎng)勇.一種基于區(qū)域分割的三角劃分方法［J］.武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2003,28(2): 227-230.

編輯 索書(shū)志

3D Modeling Method for Fork Based on Measured Contour

TAN Zhenghua1,WANG Lieqi1,WANG Liguan2,CHEN Jianhong2
(1.College of Information Engineering,Xiangtan University,Xiangtan 411105,China;
2.School of Resources and Safety Engineering,Central South University,Changsha 410083,China)

In the digital mine system,in order to make intricate underground roadway reconstruction effect reach the acceptance criteria of the mine,a 3D modeling method for fork entity based on measured contour using a partition or block modeling idea is proposed,which is is based on the measured contour of the roadway cross fork.The measured contour data of fork is classified by features into top,bottom and side contour point set.The convex hull algorithm is used to construct the roof and floor of a simple polygon,and triangulation.Based on the order of the top(bottom)plate polygon vertices,the adjacent relationship of the lateral broadside contours is established,and connection box algorithm is used to triangulate for adjacent contours.Experimental results show that,the algorithm is simple and effective and can solve any cross-sectional shape and any multiple fork modeling problems.The algorithm has been applied to the measurement plug-in contained in DIMINE software,and has good results.

underground laneway;fork;measured contour;partition modeling;triangulation;convex hull

1000-3428(2014)11-0233-04

A

TP391.41

10.3969/j.issn.1000-3428.2014.11.046

國(guó)家自然科學(xué)基金資助項(xiàng)目(51374242);湖南省自然科學(xué)基金資助項(xiàng)目(14JJ3077);湖南省教育廳基金資助一般項(xiàng)目(13C917);湘潭大學(xué)科研啟動(dòng)費(fèi)基金資助項(xiàng)目(11QDZ11)。

譚正華(1981-),男,講師、博士,主研方向:計(jì)算機(jī)輔助設(shè)計(jì),數(shù)字礦山理論與技術(shù);王烈奇,碩士研究生、CCF會(huì)員;王李管、陳建宏,教授、博士生導(dǎo)師。

2013-11-06

2013-12-31E-mail:wanlieqi@163.com

中文引用格式:譚正華,王烈奇,王李管,等.基于實(shí)測(cè)輪廓線的岔道口三維實(shí)體建模方法[J].計(jì)算機(jī)工程,2014, 40(11):233-236.

英文引用格式:Tan Zhenghua,Wang Lieqi,Wang Liguan,et al.3D Modeling Method for Fork Based on Measured Contour[J].Computer Engineering,2014,40(11):233-236.