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

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

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

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

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

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

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

1 概述

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

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

2 算法原理及流程

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

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

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

圖2 三維岔道口建模流程

3 算法過程

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

點的類C語言定義如下,其中,m_x,m_y,m_z分別表示該點的x,y,z坐標。

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

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

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

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

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

步驟3 順序連結相鄰的頂點,串連形成簡單多邊形。

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

步驟5 最后給頂板平面的點賦相應的高程。

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

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

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

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

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

3.4 相鄰輪廓線關系的確立與建模

3.4.1 輪廓線相鄰關系的確定

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

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

三心拱俯視圖如圖5(a)所示,線圈S0中A-Q所代表的輪廓數(shù)據(jù)與線圈S1中的B-T所代表的輪廓數(shù)據(jù)相鄰,按順時針方向遍歷一周,所有線圈的相鄰關系都已確定。梯形拱側面輪廓數(shù)據(jù)示意圖如圖5(b)所示,線圈S0中B-Q所代表的輪廓數(shù)據(jù)與線圈S1中的C-T所代表的輪廓數(shù)據(jù)相鄰,按順時針方向遍歷一周,可知,線圈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)格之后,基于實測輪廓線的岔道口建模問題轉(zhuǎn)化為基于底板與頂板輪廓線重建其相鄰輪廓線表面的問題?；谖矬w表面輪廓線[17-19]的三維重建方法已經(jīng)很成熟。根據(jù)相鄰截面輪廓曲線一般具有相似這一性質(zhì),文獻[18]首先對輪廓曲線上的點進行預處理后,采用角點測法與多邊形法結合的方法來計算控制點,再對其進行分塊,然后在分塊后的小曲線段上進行三角劃分,實現(xiàn)了一種對物體表面進行三角劃分的方法。由于此方法沒有考慮控制點一對多的情況,文獻[19]對文獻[18]的方法進行了改進:(1)采用一種改進的CSS方法對輪廓曲線角點進行提取。(2)采用了一種新的配對方法對角點進行配對,根據(jù)曲線間距離設定動態(tài)閾值。(3)輪廓相似性判斷。(4)在相似輪廓線之間根據(jù)配對的情況來分塊。在分塊后的小曲線段上進行簡單三角劃分與文獻[17]所用的方法一樣。采用文獻[19]中的方法對左右輪廓線進行連線框操作,生成了三維岔道口實體表面模型?；诜謱虞喞€的網(wǎng)格三角化如圖6所示。

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

4 算法分析和應用

4.1 算法時間復雜度分析

該算法的時間復雜度分析如下:

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

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

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

4.2 應用實例

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

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

圖7 巷道渲染圖

5 結束語

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

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

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

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

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

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

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

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

［8］ 金文華,何 濤,劉曉平,等.基于有序簡單多邊形的平面點集凸包快速求取算法［J］.計算機學報,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］ 周培德.計算幾何—算法分析與設計［M］.北京:清華大學出版社,2000.

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

［13］ 馬小虎,潘志庚,石教英.基于凹凸頂點判定的簡單多邊形Delaunay三角剖分［J］.計算機輔助設計與圖形學學報,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ū)域三角化算法與實現(xiàn)［J］.計算機應用研究,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］.中國圖像圖形學報,2000,5(9):764-768.

［19］ 周 焰,李德榮,徐長勇.一種基于區(qū)域分割的三角劃分方法［J］.武漢大學學報:信息科學版,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

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

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

2013-11-06

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

中文引用格式:譚正華,王烈奇,王李管,等.基于實測輪廓線的岔道口三維實體建模方法[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.