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

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

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

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

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

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

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

1 概述

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

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

2 算法原理及流程

實(shí)測岔道口輪廓線,可以看作是由多個(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)來表示線圈上的點(diǎn),遍歷各個(gè)線圈找出高程值最小和最大點(diǎn)(集);分別求取頂、底板點(diǎn)集凸多邊形,并對頂、底板簡單凸多邊形進(jìn)行快速三角化;根據(jù)頂(底)板簡單多邊形頂點(diǎn)之間的先后順序關(guān)系,建立側(cè)面輪廓線的相鄰關(guān)系;最后采用連線框方法對相鄰輪廓線進(jìn)行建模。建模流程如圖2所示。

圖2 三維岔道口建模流程

3 算法過程

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

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

遍歷各個(gè)線圈所有數(shù)據(jù),將高程值最小的點(diǎn)集存儲到數(shù)組m_ptDownArray,將高程值最大的點(diǎn)集存儲到數(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)相對成熟穩(wěn)定。文獻(xiàn)[8]利用排序算法與簡單多邊形凸包算法相結(jié)合的方法,采用文獻(xiàn)[9]算法棧結(jié)構(gòu)處理結(jié)構(gòu)和文獻(xiàn)[10]算法思想,簡單而快速地求取平面點(diǎn)集的凸包。借鑒文獻(xiàn)[8]的方法,快速求取頂、底板平面點(diǎn)集的凸包。由于底板與頂板凸殼求取方法類似,以頂板凸殼的求取方法為例:

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

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

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

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

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

生成的頂板凸殼與底板凸殼示意圖見圖3。

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

3.3 簡單多邊形的快速三角化

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

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

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

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

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

三岔口俯視圖如圖5所示。假設(shè)線圈順序與圖中線圈S0,S1,S2順序一致。對于實(shí)測輪廓線圈數(shù)據(jù),利用已經(jīng)提取出來了的底板數(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í)針方向遍歷一周,所有線圈的相鄰關(guān)系都已確定。梯形拱側(cè)面輪廓數(shù)據(jù)示意圖如圖5(b)所示,線圈S0中B-Q所代表的輪廓數(shù)據(jù)與線圈S1中的C-T所代表的輪廓數(shù)據(jù)相鄰,按順時(shí)針方向遍歷一周,可知,線圈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í)測輪廓線的岔道口建模問題轉(zhuǎn)化為基于底板與頂板輪廓線重建其相鄰輪廓線表面的問題?；谖矬w表面輪廓線[17-19]的三維重建方法已經(jīng)很成熟。根據(jù)相鄰截面輪廓曲線一般具有相似這一性質(zhì),文獻(xiàn)[18]首先對輪廓曲線上的點(diǎn)進(jìn)行預(yù)處理后,采用角點(diǎn)測法與多邊形法結(jié)合的方法來計(jì)算控制點(diǎn),再對其進(jìn)行分塊,然后在分塊后的小曲線段上進(jìn)行三角劃分,實(shí)現(xiàn)了一種對物體表面進(jìn)行三角劃分的方法。由于此方法沒有考慮控制點(diǎn)一對多的情況,文獻(xiàn)[19]對文獻(xiàn)[18]的方法進(jìn)行了改進(jìn):(1)采用一種改進(jìn)的CSS方法對輪廓曲線角點(diǎn)進(jìn)行提取。(2)采用了一種新的配對方法對角點(diǎn)進(jìn)行配對,根據(jù)曲線間距離設(shè)定動態(tài)閾值。(3)輪廓相似性判斷。(4)在相似輪廓線之間根據(jù)配對的情況來分塊。在分塊后的小曲線段上進(jìn)行簡單三角劃分與文獻(xiàn)[17]所用的方法一樣。采用文獻(xiàn)[19]中的方法對左右輪廓線進(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)集按順序連接成簡單多邊形的時(shí)間復(fù)雜度為O(k),求取簡單多邊形凸包的時(shí)間復(fù)雜度為O(k),因此,頂板建模的復(fù)雜度為O(klog(k)),同理,設(shè)底板的頂點(diǎn)數(shù)目為m,則底板建模復(fù)雜度為O(mlog(m))。

(2)簡單多邊形的三角化,頂、底板凸多邊形的頂點(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)上,通過VC++開發(fā)工具和 HOOPS可視化工具包實(shí)現(xiàn)了該算法?！癉IMINE”數(shù)字礦山軟件系統(tǒng)是中南大學(xué)數(shù)字礦山研究中心研發(fā)的一套集礦床地質(zhì)建模、礦山工程測量和地下、露天礦床開采設(shè)等于一體的智能化、可視化軟件系統(tǒng)。該系統(tǒng)的礦山工程測量和出圖模型采用了該算法。此算法應(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é)束語

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

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

［2］ 汪云甲,伏永明.礦井巷道三維自動建模方法研究［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］ 萬 金,張 凱,陳建勛.一種三維地下巷道建模的改進(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巷道建模方法——對稱建模法［J］.金屬礦山,2009,39(5):107-111.

［8］ 金文華,何 濤,劉曉平,等.基于有序簡單多邊形的平面點(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)判定的簡單多邊形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］.中國圖像圖形學(xué)報(bào),2000,5(9):764-768.

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

編輯 索書志

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

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

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

2013-11-06

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

中文引用格式:譚正華,王烈奇,王李管,等.基于實(shí)測輪廓線的岔道口三維實(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.