譚正華 ，王李管，熊書敏，劉任任

(1. 湘潭大學(xué) 湖南省高等學(xué)校智能制造重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭，411105；2. 中南大學(xué) 數(shù)字礦山研究中心，湖南 長沙，410083)

巷道系統(tǒng)是礦山三維虛擬場景的重要組成部分,是構(gòu)建數(shù)字礦山的基礎(chǔ)。已有的三維巷道實(shí)體建模研究依據(jù)其數(shù)據(jù)來源可分為兩大類：基于中心線(或?qū)Ь€)的巷道實(shí)體三維建模和基于實(shí)測底板邊界線的巷道實(shí)體三維建模?；谥行木€的巷道建模已發(fā)展一些較成熟的算法[1?4]，但多數(shù)金屬礦山存在大量實(shí)測的巷道底板邊界數(shù)據(jù)，這些數(shù)據(jù)形象地描述了各中段巷道底板寬度信息和巷道間的貫通情況。因此，基于實(shí)測底板邊界線的巷道三維建模更接近實(shí)際情況，建模相對復(fù)雜且更具一般性。孫卡等[5]提出了采用約束三角剖分的方法生成巷道模型的上下底盤面，利用兩段成面法生成巷道模型的側(cè)面，最后將這些面組合成巷道模型。但該方法難以解決常見的圓弧拱、三心拱等斷面的巷道建模問題。分層建模方法[1]是生成連通巷道實(shí)體的有效方法，可用于群體工程連通精細(xì)建模。本文借鑒文獻(xiàn)[1]中分層輪廓線的概念，設(shè)計(jì)一種基于實(shí)測底板邊界線和斷面參數(shù)，構(gòu)造巷道實(shí)體的分層輪廓線，生成地下巷道三維實(shí)體模型的方法。

1 算法原理及流程

實(shí)測的邊界線將其所在的平面劃分為1個(gè)或多個(gè)封閉區(qū)域(內(nèi)含孔洞)。本文采用區(qū)域樹[6]表達(dá)邊界線所劃分的區(qū)域，1個(gè)區(qū)域?qū)?yīng)1個(gè)區(qū)域樹。樹的層次結(jié)構(gòu)表達(dá)了邊界線之間的空間拓?fù)潢P(guān)系；然后采用約束三角剖分的方法將各區(qū)域網(wǎng)格三角化，同時(shí)提取三角形中表示“出口”和斷面底板的邊；根據(jù)斷面生成斷面輪廓線，然后均勻離散化各斷面輪廓線，生成表示實(shí)體巷道的特征點(diǎn)；根據(jù)區(qū)域樹表示的邊界拓?fù)潢P(guān)系，分層提取特征點(diǎn)，生成分層輪廓線；最后，對相鄰輪廓線采用“基于輪廓線的三維重構(gòu)”算法和對頂、底輪廓線采用“多邊形區(qū)域三角化”算法，從而實(shí)現(xiàn)巷道體的網(wǎng)格三角化。

基于邊界線的巷道建模主要分為2個(gè)主要部分：(1) 數(shù)據(jù)的前期處理。由于礦山實(shí)測數(shù)據(jù)多存在重復(fù)點(diǎn)、重復(fù)線，而且以DWG和DXF格式保存的數(shù)據(jù)為二維平面數(shù)據(jù)，故必須進(jìn)行刪除重復(fù)點(diǎn)、重復(fù)線操作，同時(shí)必須調(diào)整邊界線的高程。(2) 根據(jù)邊界線和斷面構(gòu)造三維井巷實(shí)體。需要注意的是：構(gòu)成巷道內(nèi)外邊界線必須閉合。三維巷道建模流程圖見圖1。

圖1 三維巷道建模流程Fig.1 Process of 3D modeling for laneway

2 算法的關(guān)鍵過程

2.1 構(gòu)造區(qū)域樹

基本原理是采用樹結(jié)構(gòu)來表達(dá)邊界線劃分的區(qū)域，區(qū)域樹具有如下特點(diǎn)：

(1) 1個(gè)封閉區(qū)域映射1個(gè)區(qū)域樹。

(2) 區(qū)域樹的結(jié)點(diǎn)表示區(qū)域的內(nèi)、外邊界(即巷道的底板邊界)，其根結(jié)點(diǎn)表示該區(qū)域的最外圍邊界，子結(jié)點(diǎn)表示區(qū)域內(nèi)部的孔、島邊界。

(3) 結(jié)點(diǎn)之間的上下層次關(guān)系表示邊界的包含關(guān)系，同層結(jié)點(diǎn)表示邊界的并列關(guān)系。

(4) 邊界是有方向性的，并對邊界方向作如下規(guī)定：區(qū)域最外圍邊界的走向?yàn)槟鏁r(shí)針方向，內(nèi)部孔洞邊界沿順時(shí)針方向，島邊界沿逆時(shí)針方向。

如圖2(a)所示，某實(shí)測的巷道底板邊界線a，b，c，d和e將該中段劃分為1個(gè)封閉區(qū)域，見圖2(b)；陰影部分表示劃分的封閉區(qū)域，該區(qū)域內(nèi)含4孔洞，其對應(yīng)的區(qū)域樹表示見圖2(c)。

區(qū)域的提取方法有多種[6?8]，其中文獻(xiàn)[6]給出了定向極大、極小閉環(huán)的概念，通過建立結(jié)點(diǎn)?路徑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，采用內(nèi)層路徑優(yōu)先查找算法，提取所有定向閉環(huán)，最后建立定向極小閉環(huán)和定向極大閉環(huán)的隸屬關(guān)系，建立區(qū)域樹，有效地實(shí)現(xiàn)了復(fù)雜區(qū)域的識別、提取，具有普遍適用性。本文采用文獻(xiàn)[6]中的算法提取中段平面的所有復(fù)雜區(qū)域。

圖2 區(qū)域和對應(yīng)的樹結(jié)構(gòu)Fig.2 Region and its representation using tree structure

采用區(qū)域樹形式化表達(dá)了巷道底板邊界間的空間拓?fù)潢P(guān)系，為區(qū)域的三角化提供了數(shù)據(jù)來源。

2.2 多邊形區(qū)域的三角化

多邊形的三角剖分就是在不產(chǎn)生新頂點(diǎn)的條件下將平面多邊形劃分成一系列不相重疊的三角形[9]。多邊形三角剖分算法有多種[10?13]，其中，畢林等[13]提出的三角化算法適用帶洞、島的任意簡單多邊形，時(shí)間復(fù)雜度近似O(n)，采用該算法，對巷道底板邊界線多邊形網(wǎng)格三角化，生成結(jié)果局部示意圖見圖3。

圖3 多邊形區(qū)域三角化示意圖Fig.3 Schematic diagram of polygon triangulation

2.3 提取表示“出口”位置和斷面底板的邊

根據(jù)網(wǎng)格三角形和底板邊界共邊的數(shù)目，將三角形分為3類：(1) 不共邊的三角形；(2) 共1條邊的三角形；(3) 共2條邊的三角形。見圖3中的三角形f，j和k，三角形中的實(shí)粗線部分表示該邊和原邊界線共邊，虛粗線表示不共邊。

“出口”位置的邊只存在于第3類三角形中。表示“出口”位置的邊和其前后的邊有明顯角度變化，根據(jù)這一特征對其進(jìn)行識別和提??；第1和2類三角形中不與邊界重合的邊中最短的邊作為斷面底板的邊。

2.4 斷面輪廓線和特征點(diǎn)的構(gòu)造

設(shè)計(jì)的巷道斷面有固定的底邊寬度、墻高、拱高，形狀比較規(guī)則，反映了設(shè)計(jì)圖中垂直于巷道中線處的斷面形狀和尺寸，見圖4。提取的斷面底邊和巷道中線往往是不垂直的，故需要根據(jù)垂直中線處的斷面輪廓線，通過投影變換建立斷面底板處的斷面輪廓線。

以圖5為例，當(dāng)斷面形狀為三心拱時(shí)，構(gòu)造底板AC處的斷面輪廓線算法如下。

步驟 1：構(gòu)造垂直于巷道中線的直線段 AB。AB的長度表示斷面的底寬。根據(jù)設(shè)計(jì)斷面中的“拱高/底寬”(一般為1/3，1/4或1/5)確定該處的實(shí)際拱高。

步驟 2：根據(jù)斷面參數(shù)中的墻高、巷道底寬和拱高，擬合AB處的斷面輪廓線。

圖4 2種常見的巷道斷面Fig.4 Two laneway cross-sections

圖5 建立斷面輪廓線Fig.5 Reconstruct cross-section contour

步驟 3：通過投影變換，建立 AC處的斷面輪廓線。

離散化斷面輪廓線，獲取巷道斷面的特征點(diǎn)。以梯形斷面和三心拱斷面為例(見圖6)，梯形斷面存在2組特征點(diǎn)：(p0?p1)和(p2?p3)，三心拱斷面有 5組特征點(diǎn)：(p0?p1)，(p2?p3)，(p4?p5) ，(p6?p7)，(p8?p9)。

圖6 提取斷面輪廓線特征點(diǎn)Fig.6 Laneway section data acquiring

2.5 構(gòu)造巷道實(shí)體的分層輪廓線

區(qū)域樹結(jié)構(gòu)表達(dá)了底板邊界的空間拓?fù)潢P(guān)系，通過獲取斷面輪廓線的特征點(diǎn)，建立巷道實(shí)體的分層輪廓線。當(dāng)斷面形狀分別為梯形和三心拱時(shí)，構(gòu)造的分層輪廓線示意圖見圖7。

圖7 巷道實(shí)體的分層輪廓線Fig.7 Hierarchical contours of laneway

2.6 基于分層輪廓線的三維重建

在生成巷道實(shí)體分層輪廓線的基礎(chǔ)上，巷道實(shí)體表面的重建問題轉(zhuǎn)化為基于一組輪廓線重建其三維表面。許多學(xué)者在三維重建方面進(jìn)行了很多研究[14?18]。對于 2條連續(xù)的截面輪廓曲線之間的三角劃分的問題，周焰等[15]提出了一種利用物體2個(gè)截面輪廓曲線

一般有較大的相似性這一事實(shí)，首先進(jìn)行粗略分塊，然后在塊內(nèi)進(jìn)行三角劃分，從而實(shí)現(xiàn)了一種三維物體表面重建的多尺度算法。文獻(xiàn)[16]對文獻(xiàn)[15]的方法進(jìn)行了改進(jìn)，首先采用一種改進(jìn)的CSS方法提取輪廓曲線的角點(diǎn)，其次進(jìn)行角點(diǎn)配對，采用一種新的配對方法，根據(jù)曲線間距離設(shè)定動態(tài)閾值，根據(jù)配對情況進(jìn)行輪廓相似性判斷；在相似的輪廓曲線之間根據(jù)配對情況進(jìn)行分塊。每個(gè)塊內(nèi)部進(jìn)行的簡單的三角劃分與文獻(xiàn)[14]中的方法一樣。由于巷道實(shí)體的分層輪廓線之間存在相似性，本文采用文獻(xiàn)[16]中方法實(shí)現(xiàn)對所有相鄰的分層輪廓線網(wǎng)格三角化(見圖8)。巷道實(shí)體是封閉的，因此，還必須分別對頂、底輪廓線實(shí)現(xiàn)多邊形的區(qū)域三角化。本文采用文獻(xiàn)[13]中算法實(shí)現(xiàn)了頂、底輪廓線的網(wǎng)格三角化。最后，對所有的三角化網(wǎng)格合并，最終生成封閉的三維巷道實(shí)體表面模型。

圖8 基于分層輪廓線的網(wǎng)格三角化Fig.8 Triangulation based on hierarchical contours

3 算法分析和應(yīng)用實(shí)例

3.1 算法復(fù)雜度分析

該算法時(shí)間復(fù)雜度主要由以下幾部分確定：(1)基于邊界輪廓線的區(qū)域樹構(gòu)造，當(dāng)存在l個(gè)極大閉環(huán)和k個(gè)極小閉環(huán)時(shí)，該算法時(shí)間復(fù)雜度為O(lk)[6]；(2)多邊形的區(qū)域三角化，定義多邊形的頂點(diǎn)數(shù)目為 n，三角化時(shí)間復(fù)雜度近似線性，即O(n)；(3)網(wǎng)格的生成，包括分層輪廓線的曲面重建[17]和頂、底輪廓線的三角化[13]，時(shí)間復(fù)雜度與頂點(diǎn)數(shù)均近似線性。故總的時(shí)間復(fù)雜度為：O(lk)+O(n)。

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

通過VC+開發(fā)工具和HOOPS可視化工具包實(shí)現(xiàn)了該算法，運(yùn)行環(huán)境為Windows 2000操作系統(tǒng)，CPU為Inter Pentium4 3.00 GHz，內(nèi)存為512 MB。對圖3(a)所示底板邊界線生成巷道實(shí)體(三心拱斷面、梯形斷面)，局部渲染效果見圖9。

實(shí)驗(yàn) 1：當(dāng)邊界線數(shù)為8，13，17，30和42時(shí)，分別生成巷道(三心拱斷面)，耗時(shí)如表 1所示，邊界數(shù)與時(shí)間關(guān)系如圖10所示。

實(shí)驗(yàn) 2：對圖3(a)中邊界線的頂點(diǎn)坐標(biāo)進(jìn)行線性插值加密，分別得到頂點(diǎn)個(gè)數(shù)為678，1 662，3 074，5 419和7 830，生成巷道(三心拱斷面)耗時(shí)結(jié)果如表2所示，其頂點(diǎn)數(shù)?時(shí)間曲線如圖11所示。從圖11可見：當(dāng)邊界數(shù)一定時(shí)，算法耗時(shí)與頂點(diǎn)數(shù)呈近似線性關(guān)系。

圖9 局部渲染效果圖Fig.9 3D rendering for laneway model

表1 不同邊界線數(shù)算法耗時(shí)Table 1 Consuming times for different numbers of boundary

圖10 邊界數(shù)?時(shí)間曲線Fig.10 Time changes with different numbers of boundary

表2 不同頂點(diǎn)個(gè)數(shù)算法耗時(shí)Table 2 Consuming time for different numbers of vertex

圖11 頂點(diǎn)數(shù)?時(shí)間曲線Fig.11 Time changes with different numbers of vertex

4 結(jié)論

提出了一種有效的實(shí)測巷道三維建模方法。根據(jù)實(shí)測巷道底板邊界線和斷面形狀，生成巷道實(shí)體的特征點(diǎn)，構(gòu)造分層輪廓線，采用連線框和網(wǎng)格三角化方法，建立虛擬環(huán)境下的三維巷道實(shí)體，為下一步虛擬漫游以及采掘量的估算提供數(shù)據(jù)來源。該方法具有以下優(yōu)點(diǎn)：

(1) 能有效地解決任意復(fù)雜不等寬實(shí)測底板邊界線和不同斷面形狀下的巷道實(shí)體建模問題。

(2) 當(dāng)斷面形狀為三心拱時(shí)，建模過程中斷面輪廓線的拱高根據(jù)工程設(shè)計(jì)中的拱高和底寬的比(1/3，1/4或1/5)計(jì)算得出，要構(gòu)造更符合實(shí)際的巷道三維模型，須進(jìn)一步探討和驗(yàn)證。

(3) 邊界(多邊形)數(shù)是影響算法時(shí)間復(fù)雜度的主要方面，需要進(jìn)一步降低構(gòu)造區(qū)域樹的時(shí)間復(fù)雜度，如考慮采用 OBB樹的碰撞檢測算法確定定向閉環(huán)之間的隸屬關(guān)系。

[1]譚正華, 王李管, 畢林, 等. 平面連通巷道三維實(shí)體分層建模方法[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2010, 35(3): 360?363.TAN Zheng-hua, WANG Li-guan, BI Lin. et al. A hierarchicl modeling method for plane connected three-dimensional laneway entity based on media curves[J]. Geomatics and Information Science of Wuhan University, 2010, 35(3):360?363.

[2]徐志強(qiáng), 楊邦榮, 王李管, 等. 巷道實(shí)體的三維建模研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(6): 202?205.XU Zhi-qiang, YANG Bang-rong, WANG Li-guan, et al.Laneway entity three-dimensional modeling study and realiza-tion[J]. Computer Engineering and Applications, 2008,44(6): 202?205.

[3]汪云甲, 伏永民. 礦井巷道三維自動建模方法研究[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2006, 31(12): 1097?1100.WANG Yun-jia, FU Yong-min. On 3D automatic modeling method of mine roadway[J]. Geomatics and Information Science of Wuhan University, 2006, 31(12): 1097?1100.

[4]葛永慧, 王建民. 礦井三維巷道建模方法的研究[J]. 工程勘察, 2006(10): 46?49.GE Yong-hui, WANG Jian-min. 3D modeling method for lane way[J]. Journal of Geotechnical Investigation & Surveying,2006(10): 46?49.

[5]孫卡, 翁正平, 張志庭, 等. 基于帶約束三角剖分的三維巷道建模方法[J]. 礦業(yè)研究與開發(fā), 2007, 27(5): 64?66.SUN Ka, WENG Zheng-ping, ZHANG Zhi-ting, et al. 3D roadway modeling method based on restrained triangulation[J].Mining Research and Development, 2007, 27(5): 64?65.

[6]譚正華, 王李管, 畢林, 等. 參數(shù)曲線集復(fù)雜區(qū)域的全自動識別算法[J]. 計(jì)算機(jī)工程, 2010, 36(8): 23?26.TAN Zheng-hua, WANG Li-guan, BI Lin, et al. Automatic identification algorithm for complicated regions of parameterized curve set[J]. Computer Engineering, 2010, 36(8):23?26.

[7]宋懷波, 路長厚, 王富春. 一種新的復(fù)雜區(qū)域孔洞填充算法[J]. 桂林電子科技大學(xué)學(xué)報(bào), 2006, 26(6): 451?454.SONG Huai-bo, LU Chang-hou, WANG Fu-chun. A new hole-filling algorithm for complicated connecting regions[J].Journal of Guilin University of Electronic Technology, 2006,26(6): 451?454.

[8]何亞彬, 楊恢先, 代秋芳. 參數(shù)曲線集最小閉環(huán)提取算法[J].計(jì)算機(jī)工程與應(yīng)用, 2005, 41(32): 109?111.HE Ya-bin, YANG Hui-xian, DAI Qiu-fang. An algorithm for picking up minimum closed loops from parameterized curve set[J]. Computer Engineering and Applications, 2005, 41(32):109?111.

[9]馬小虎, 潘志庚, 石教英. 基于凹凸頂點(diǎn)判定的簡單多邊形Delaunay三角剖分[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1999,11(1): 1?3.MA Xiao-hu, PAN Zhi-geng, SHI Jiao-ying. Delaunay triangulation of simple polygon based on determination of convex concave vertices[J]. Journal of Computer Aided Design& Computer Graphics, 1999, 11(1): 1?3

[10]Gareym R, Johnsond S, Preparata F P, et al. Triangulating a simple polygon[J]. Information Proceeding Letters, 1978, 7(4):175?179.

[11]Seidel R. A simple and fast incremental randomized algorithm forcomputing trapezoidal decompositions and for triangulating polygons[J]. ComputGeom Theory Appl, 1991, 1(1): 51?64.

[12]Chazelle B. Triangulating a simple polygon in linear time[J].Discrete Comp Geom, 1991, 6(5): 485?524.

[13]畢林, 王李管, 陳建宏, 等. 快速多邊形區(qū)域三角化算法與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(10): 3030?3033.BI Lin, WANG Li-guan, CHEN Jian-hong, et al. Fast triangulation algorithm for polygon regions and implementation[J]. Application Research of Computers, 2008,25(10): 3030?3033.

[14]Keppel E. Approximating complex surface interpolation technique for reconstruction 3D objects from serial crosssections[J]. Computer Vision, Graphics, and Image Processing,1989, 48(1): 124?143.

[15]周焰, 李德華, 陳振羽, 等. 三維物體表面三角劃分的快速算法[J]. 中國圖像圖形學(xué)報(bào), 2000, 5(9): 764?768.ZHOU Yan, LI De-hua, CHEN Zhen-yu. A fast algorithm of triangulation on 3D surface[J]. Journal of Image and Graphics,2000, 5(9): 764?768

[16]周焰, 李德榮, 徐長勇. 一種基于區(qū)域分割的三角劃分方法[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2003, 28(2): 227?231.ZHOU Yan, LI De-rong, XU Chang-yong. A blocking based triangulation of surface between planar contours[J]. Geomatics and Information Science of Wuhan University, 2003, 28(2):227?230.

[17]王強(qiáng), 馬利莊, 鮑虎軍. 基于骨架的斷層間復(fù)雜輪廓線的三角片曲面重構(gòu)[J]. 計(jì)算機(jī)學(xué)報(bào), 2000, 28(8): 842?846.WANG Qiang, MA Li-zhuang, BAO Hu-jun. Skeleton-based triangular surface reconstruction from complex contour lines[J].Chinese Journal of Computers, 2000, 23(8): 842?846.

[18]Congy G, Parvin B. An algebraic solution to surface recovery from cross-sectional contours[J]. Graphical Models and Image Processing, 1999, 61(3): 222?243.