DOI: 10.11817/j.issn.1672-7207.2015.08.038
基于点云数据的采空区三维建模算法
陈鑫1, 2,王李管1, 2,毕林1, 2,陈建宏1,朱忠华1, 2
(1. 中南大学 资源与安全工程学院,湖南 长沙,410083;
2. 中南大学 数字矿山研究中心,湖南 长沙,410083)
摘要:为有效实施对采空区的控制和安全管理,需要准确掌握矿山采空区的体积、空间三维形态和实际边界。通过三维激光扫描技术可获取采空区表面点云数据,结合矿山采空区自身空间几何特点,提出伪极点-Crust建模算法。其基本思路为:在三维Delaunay三角剖分的基础上,给出伪极点的概念,以伪极点代替传统Crust算法中的极点,减小数据存储量;同时结合奇异四面体判别准则,确保采空区模型的准确性;通过使用模型内外检测算法和伪极点-Crust图抽取算法,建立采空区三维模型。用VC++实现该算法,对安徽铜陵冬瓜山铜矿采空区建模进行试验。研究结果表明:采用该算法建模快速,结果准确;该算法同样适用于实测巷道建模、采场验收、计算机几何造型、逆向工程和虚拟现实技术等。
关键词:采空区;激光扫描点云;Delaunay三角剖分;模型内外检测;伪极点-Crust算法
中图分类号:TD672;TP391 文献标志码:A 文章编号:1672-7207(2015)08-3047-07
3D modeling algorithm for goaf based on point cloud data
CHEN Xin1, 2, WANG Liguan1, 2, BI Lin1, 2, CHEN Jianhong1, ZHU Zhonghua1, 2
(1. School of Resources and Safety Engineering, Central South University, Changsha 410083, China;
2. Research Center of Digital Mine, Central South University, Changsha 410083, China)
Abstract: In order to implement the safety control and management of goaf effectively, mines’ accurate knowledge of its size, shape and boundary must be required. With the point cloud data of goaf surface detected through 3D laser scanning technique and the geometric characteristics of mined-area itself, pseudo pole-Crust algorithm was proposed. Firstly, the conception of pseudo pole, which replaces of pole in conventional Crust algorithm, was put forward to reduce data storage based on 3D Delaunay triangulation. Meanwhile criterion of odd tetrahedron was consulted to ensure the accuracy of goaf model. Finally, the 3D modeling of goaf was accomplished with internal-external model detecting algorithm and pseudo pole-Crust extracting algorithm. Pseudo pole-Crust algorithm was actualized with VC++, and experimental tests of Dongguashan copper goaf were conducted. The results show that the algorithm is quick and accurate. The algorithm can also be applied to measuring laneway modeling, stope checking, computer geometry modeling, reverse engineering and virtual reality technology.
Key words: goaf; laser scan point cloud; Delaunay triangulation; internal-external model detection; pseudo pole-Crust algorithm
矿山采空区是矿山安全生产事故发生的一个主要诱因。采空区在高地压、高应力的作用下产生的大面积冒顶、片帮、塌陷和闭合变形等都是重要的地质灾害,严重影响矿山正常生产运作和井下工作人员的生命安全,对其探测已成为矿山必须解决的难题[1-2]。传统的瞬变电磁法[3](TEM)、探地雷达法(GPR)[4]、地震映像法[5]、高密度电阻率法[6]等只能展开对采空区的二维探测,无法准确获取采空区的三维空间形态、体积、顶板面积、实际边界等重要信息。近年来,随着激光测距技术的空前发展,三维激光扫描技术也逐步应用于矿山领域。采空区三维激光精密探测系统(cavity monitoring system,CMS)[7]是一种基于激光测距原理的采空区探测系统,可实现对采空区的精密探测,然而,探测结果只是采空区表面点云数据集合,在实际应用中需要更具有实际意义的采空区三维实体模型,因此,对数据的后处理较困难。解决点云数据模型重构问题的方法可分为3类:基于隐式曲面法、区域生长法和基于Delaunay三角剖分法。Hoppe等[8]提出的零集法属于基于隐式曲面法,该类方法不能在点云中插值点从而使其应用受到限制;Bernardini等[9]提出的Ball-Pivoting法提出的贪婪算法属于区域生长法,该类方法构建的网格质量过分依赖于种子面片的选取和自定义参数的设置,在采样不均匀的情况下还需要后续补孔;具有代表性的基于Delaunay三角剖分的算法有Guo等[10]提出的α-shape法、Dey等[11]提出的Cocone算法,该类算法由于使用了中间数据结构,计算量大,时效性比较差;王青等[12]提出增量快速曲面重建算法、谭建荣等[13]提出基于曲面局平特性的重构算法等,这些算法均尚未成熟。同时,相对于一般的实体模型而言,采空区模型具有其自身的空间几何特点:采空区模型连续且近似封闭。针对上述现象,本文作者总结现有三维曲面重构算法的优点及不足,在三维Delaunay三角剖分原理的基础上,给出伪极点概念及生成方式,结合奇异四面体消除方法,通过模型内外检测算法和伪极点-Crust图抽取算法,以准确、快速地建立采空区三维模型。
1 算法原理及流程
1.1 三维Delaunay三角剖分
已知平面L上n个点的集合S={P1,P2,…,Pn},令,则V(Pi)表示比点集S中其他点更接近点Pi的n-1个半平面的交集,它所确定的范围可以表示为1个不多于n-1条边的凸多边形区域,称V(Pi)为与Pi关联的Voronoi多边形。点集S中所有点的Voronoi多边形将平面L划分为n个区域,称为点集S的Voronoi图,记作V(S),可表示为对平面L的1个凸多边形分割,称Voronoi图中的交点为Voronoi顶点。
若点集S中的2个点Pi和Pj的Voronoi多边形有公共边,则连接点Pi和Pj,依此类推遍历点集S中的所有点,可得到1个连接点{Pi}(i=1,2,…,n)唯一确定的最优三角网格,称为点集S的Delaunay三角剖分,记为D(S)。Delaunay三角剖分形成的三角网格具有一些重要的性质[14]:1) 空外接圆准则;2) 局部性准则;3) 最小内角最大化准则。
Voronoi图和Delaunay三角剖分互为对偶图,如图1所示,其中实心点代表平面点集,细实线代表Voronoi图,空心点代表Voronoi顶点,粗实线代表Delaunay三角剖分形成的三角网格。
图1 Voronoi图与Delaunay三角剖分
Fig. 1 Voronoi diagram and Delaunay triangulation
将Voronoi图和Delaunay三角剖分推广到三维空间仍然适用,对于空间R上的n个点的集合S,V(S)表示对空间R的1个凸多面体分割,D(S)表示空间点集S唯一确定的四面体集合,该四面体集合满足如下条件:1) 空外接球准则;2) 局部性准则。三维空间Delaunay三角剖分并不能绝对地满足最小内角最大化准则。
1.2 Crust算法
设S为1个二维平面点集,SV为S的Voronoi顶点集,并令ST+S∪SV,对点集ST再次进行Delaunay三角剖分,若形成的三角网格的一条边的2个端点都属于S,则此边属于Crust图,即最终由点集S重建的曲面模型的1条边,这就是经典的Crust算法。
平面点集S在一定的取样密度下,有推论[15]可以证明相邻的取样点形成的边必在Crust上,且随着采样点密度的增加,Voronoi顶点集就越逼近中轴。然而,将二维Crust算法推广到三维空间无法保证所有的三维Voronoi顶点都会逼近中轴面,因此,三维Crust算法提出极点的概念,即先对取样点进行1次三维Delaunay三角剖分得到三维Voronoi顶点集,在此基础上选取出各取样点的正负极点,将得到的极点集与采样点集再次进行三维Delaunay三角剖分,遍历形成的各四面体所包含的4个三角网格。若某三角网格的3个端点都属于取样点,则此三角网格属于Crust图。
1.3 获取采空区点云数据与生成伪极点
构建采空区三维模型的点云数据主要是通过三维激光扫描仪得到,通过其内置坐标转换功能[16]即可得到以TXT文件存储的各点空间三维坐标值。设点集S为激光扫描仪获取的n个点,Sm={xmax,xmin,ymax,ymin,zmax,zmin}为点集S中各坐标点在x,y和z方向上的坐标值(其中,xmax,ymax和zmax分别为点集S′中各坐标点在x,y和z方向的最大值;xmin,ymin和zmin分别为点集S′中各坐标点在x,y和z方向的最小值),step为点集S的bounds各边长的最大值,定义有限包络面Lxmax为bounds上经过x轴方向上的点(xmin,0,0)且垂直于x轴的矩形平面。因此,以Sm中的元素为相应各坐标轴上的基点,以step为基距,向外扩展可得到由6个矩形区域构成的有限包络面集Lm={Lxmax+step,Lxmin-step,Lymax+step,Lymin-step,Lzmax-step,Lzmin-step},在包络面Lxmax+step上对各边N等分均匀插值形成点阵{(xmax+step,ymin+(ymax-ymin)·i/N,zmin+(zmax-zmin)·j/N}(i= 1,2,…,N;j=1,2,…,N),即伪极点,依此类推,便可得到采样点集S的6N2个伪极点,记作伪极点集SV′。
1.4 伪极点-Crust算法
Crust算法的时效性主要受制于极点集与采样点集并集的三维Delaunay三角剖分所需的计算量。采空区体积庞大,空间三维形态复杂,采样点数据较多,使得该算法无法有效实现采空区的三维建模。本文紧密结合采空区连续且近似封闭等几何特点,以伪极点代替传统Crust算法的极点,减小建模过程的计算量。直接对伪极点集与采样点集的并集进行三维Delaunay三角剖分,在此基础上即可抽取出Crust图实现曲面重建,将此方法称为伪极点-Crust算法。
1.5 采空区伪极点-Crust建模算法流程
在获取到采空区三维点云数据的基础上,实现如下基于三维Delaunay三角剖分的伪极点-Crust算法的具体步骤。
步骤1 将采样得到的采空区三维点云数据去重并消除不规范点坐标,得到规范采样点集S。
步骤2 按伪极点生成方式得到S的伪极点集 SV′。
步骤3 获取点集ST=S∪SV′,对ST调用三维Delaunay三角剖分,获得初始四面体集合T。
步骤4 依次遍历T中的各元素,根据奇异四面体判别准则,筛选出可用于构建采空区三维模型的合格四面体集合Ts。
步骤5 对Ts中的各个四面体调用模型内外四面体判断算法,提取出模型内的四面体集合Ti。
步骤6 根据伪极点-Crust图抽取方法,提取出Ti中最终用于构建采空区模型的三角面片。
2 采空区三维建模算法关键过程
2.1 奇异四面体判别准则
三维Delaunay三角剖分并不能绝对地满足最小内角最大化准则,同时,由于伪极点与采样点的不规则空间位置关系,对伪极点集与采样点集的并集进行三维Delaunay三角剖分难免会形成奇异四面体,可按下式判别准则消除奇异四面体:
式中:tix,tiy和tiz(i=1,2,3,4)表示各四面体4个顶点的空间三维坐标;eps表示系统能准确表示的浮点数的精度。判别准则表示顶点4与顶点1、顶点2、顶点3构成的向量的混合积[17]理论上等于0的四面体可视为奇异四面体。
2.2 模型内外检测算法
将伪极点集与采样点集的并集进行三维Delaunay三角剖分并消除奇异四面体后所得到的规范四面体可分为2类,即模型内四面体和模型外四面体。采空区伪极点-Crust建模算法的难点和关键技术就是四面体的模型内外正确检测,它直接关系到模型的有效性和准确性。针对伪极点-Crust算法,本文提出的模型内外四面体判断算法流程如图2所示。对模型内外所有规范四面体集合Te,获取Te中各个四面体的4个三角面片形成集合Tr,将Tr去重形成新的三角面片集合Tr′,依次遍历集合Tr′中的各元素tr,判断其与Te中各元素的映射关系:若Te中只有1个元素与tr对应,则属于边界三角面片;否则属于非边界三角面片,即Te中有2个元素与tr对应。对于非边界三角面片,判断与其相关联的2个四面体的空间几何关系,选择出所有构建采空区三维模型的四面体。
图2 模型内外检测算法流程图
Fig. 2 Flow chart of internal-external model detecting algorithm
为了区别对待Te中的各元素,将Te中的各四面体赋予“模型内/外”和是否“已检测”这2种属性,同时将Tr中的各三角面片赋予是否属于“待检测”这一属性加以区别。
模型内外四面体判别的主要因素是2个相邻四面体外接球半径之间夹角的余弦,记为相邻四面体相似度,如图3所示。图3中,点O1和O2分别为四面体ABCD和ABCE外接球的圆心,点O3为2个外接球面相交形成的圆的圆心,根据各四面体的外接球球心坐标和外接球半径可求得2个相邻四面体外接球半径之间夹角的余弦即相似度。为了合理对待相似度的判断标准,设置可变阀值ts进行智能控制。将ts初始值取为0.95严格控制判断标准,将相似度大于ts的2个相邻四面体视为属性相似四面体,将相似度指标小于-ts的2个相邻四面体视为属性相反四面体,1次循环后采取降阀值措施继续进行相邻四面体属性相似相反性检测,直至循环结束,此时,被标记为“模型内”的四面体即为最终用于构建采空区三维模型的四面体集合。
图3 相邻四面体相似度指标图示
Fig. 3 Diagram of similarity index of adjacent tetrahedrons
2.3 伪极点-Crust图抽取算法
传统Crust算法得到的Crust图的三角面片是无序的,彼此之间没有明确的空间拓扑关系和关联性,内部结构复杂,因此,后续的外部面抽取工作量大,常用的最小法失变化法[18]易形成环形空洞区域,且不利于处理变化急剧的细节部位,使得建立的模型难以保证结果的唯一性和准确性。本文算法得到的Crust图并没有破坏三维Delaunay三角剖分产生的初始四面体结构及相互之间的关系,内部结构也是严格意义上的三维Delaunay三角剖分结果,因此,相应地提出伪极点-Crust图特有的抽取算法。
设标记为“模型内”的四面体集合为Tei,获取Tei中各个四面体的4个三角面片形成集合Tri,将Tri去重处理形成新的三角面片集合Tri′,依次遍历集合Tri′中的各元素tri。由于各三角面片或是外部面,或是2个四面体的内部公共面,因此,Tri中有且最多只有2个元素与tri相同。设置1个二维数组Cr存储Tri与Tei的对应关系,将Cr中各元素初始化为-1,具体算法流程图如图4所示。
数组Cr的第1维记录三角面片的序号,第2维记录其与Tei的对应关系,选取出Cri[1]等于初始值-1的三角面片即模型外部面,从而得到采空区三维模型。
图4 伪极点-Crust图抽取算法流程图
Fig. 4 Flow chart of pseudo pole-Crust extracting algorithm
3 算法分析和应用实例
3.1 算法空间及时间复杂度分析
对于具有n个点构成的采空区点云数据,传统Crust算法进行建模的运算主要集中在对初始采样点集的三维Voronoi顶点计算,以及对采样点集和极点集的并集的三维Delaunay三角剖分上。三维Delaunay三角剖分的时间复杂度[19]最理想情况下为O(nlgn),在最坏情况下为O(n2),其余均为线性运算,因此,传统Crust算法的时间复杂度在最理想情况下为O(nlgn)+O(3nlgn),在最坏情况下为O(n2)+O(9n2)。
伪极点-Crust算法使用伪极点代替了传统Crust算法中的极点,建模的运算主要集中在对初始采样点集和伪极点集的三维Delaunay三角剖分上,实践中本文算法伪极点数最大取值为600,三维Delaunay三角剖分通过Qhull[20]实现,其空间复杂度为O(n),时间复杂度为 O(nlgn),因此,伪极点-Crust算法的空间复杂度为 O(n),时间复杂度为 O(nlgn)。由于实际中的采空区点云数据均由上万个点组成,从而使得伪极点-Crust算法的时间复杂度远远比传统Crust算法的小。
3.2 算法实现和应用实例
通过VC++开发工具在数字矿山软件平台Dimine[21]上实现该建模算法,运行环境为Windows XP操作系统,CPU为Intel(R)Core(TM) 2.3 GHz,内存为2 Gbit。图5所示为冬瓜山铜矿某地下采空区的三维建模结果,算法同时支持导入各采空区点云数据1次完成采空区群建模;表1所示为建模结果与实际结果的对比。
在对冬瓜山铜矿采空区建模试验过程中,得到由含不同点数的点云数据完成采空区建模的时间变化如表2和图6所示。
图5 采空区三维建模效果图
Fig. 5 Rendering of goaf 3D modeling
图6 点数-时间曲线
Fig. 6 Relationship between time and different numbers of points
表1 建模参数与实际参数对比
Table 1 Comparison of modeling parameters and actual parameters
表2 不同点数算法耗时
Table 2 Time-consuming of different numbers of points s
该采空区建模方法同时可以应用于采场验收,实测巷道建模等,在逆向工程、计算机几何造型、虚拟现实等技术中也具有重要的参考价值。图7所示为使用本算法实现的相关领域的实体建模。
图7 伪极点-Crust算法在相关领域应用效果图
Fig. 7 Rendering of applications in relative areas using pseudo pole-Crust algorithm
4 结论
1) 伪极点-Crust算法继承了传统Crust算法可插值点、不依赖种子面片和自定义参数的选取、无采样密度限制、无需后续补孔等优点,该算法准确、快速地建立了空间点云数据的拓扑关系,具有很强的系统性和鲁棒性。
2) 由于采用伪极点代替传统Crust算法中的极点,减少了三维Delaunay三角剖分的数据量,同时结合奇异四面体判别准则消除了不必要的四面体,有效地降低了模型建立过程中的数据量,提高了建模速度。
3) 模型内外检测算法中使用可变阀值,合理对待相似度的判断标准,使得检测灵活有效,能够很好地处理各种不同拓扑复杂度的点云数据。
4) 伪极点-Crust算法同时可以应用于采场验收、实测巷道建模、逆向工程、计算机几何造型、虚拟现实等技术中。
参考文献:
[1] 闫长斌, 徐国元. 综合物探方法及其在复杂群采空区探测中的应用[J]. 湖南科技大学学报(自然科学版), 2005, 20(3): 10-14.
YAN Changbin, XU Guoyuan. Research of composite geophysical methods and its application in detection complicated group mined-out areas[J]. Journal of Hunan University of Science & Technology (Natural Science Edition), 2005, 20(3): 10-14.
[2] 李夕兵, 李地元, 赵国彦, 等. 金属矿地下采空区探测、处理与安全评判[J]. 采矿与安全工程学报, 2006, 23(1): 24-29.
LI Xibing, LI Diyuan, ZHAO Guoyan, et al. Detecting, disposal and safety evaluation of the underground goaf in metal mines[J]. Journal of Mining & Safety Engineering, 2006, 23(1): 24-29.
[3] 张开元, 韩自豪, 周韬. 瞬变电磁法在探测煤矿采空区中的应用[J]. 工程地球物理学报, 2007, 4(4): 341-344.
ZHANG Kaiyuan, HAN Zihao, ZHOU Tao. Application of transient electromagnetic method in coal mine gob[J]. Chinese Journal of Engineering Geophysics, 2007, 4(4): 341-344.
[4] 程久龙, 胡克峰, 王玉和, 等. 探地雷达探测地下采空区的研究[J]. 岩土力学, 2004, 25(Z1): 79-82.
CHENG Jiulong, HU Kefeng, WANG Yuhe, et al. Research on detecting of underground mined-out areas by using GPR[J]. Rock and Soil Mechanics, 2004, 25(Z1): 79-82.
[5] Carlsten S, Johansoon S, Warman A. Radar techniques for indicating internal erosion in embankment dams[J]. Journal of Applied Geophysics, 1995, 33(1/2/3): 143-156.
[6] 祝卫东, 钱勇峰, 李建华. 高密度电阻率法在采空区及岩溶探测中的应用研究[J]. 工程勘察, 2006(4): 69-72.
ZHU Weidong, QIAN Yongfeng, LI Jianhua. Application of high density resistivity to exploration of mined area and karst[J]. Journal of Geotechnical Investigation & Surveying, 2006(4): 69-72.
[7] 罗周全, 鹿浩, 袁节平, 等. 金属矿采空区精密探测与三维建模技术[J]. 湖南科技大学学报(自然科学版), 2008, 23(3): 83-86.
LUO Zhouquan, LU Hao, YUAN Jieping, et al. Metal mine's mined-area precise survey and 3D modeling technology[J]. Journal of Hunan University of Science & Technology (Natural Science Edition), 2008, 23(3): 83-86.
[8] Hoppe H, Derose T, Duchamp T, et al. Surface reconstruction from unorganized points[C]//SIGGRAPH. Chicago, USA, 1992: 71-78.
[9] Bernardini F, Mittleman J, Rushmeier H, et al. The ball-pivoting algorithm for surface reconstruction[J]. IEEE Trans Vis Comput Graph, 1999, 5(4): 349-359.
[10] Guo B, Menon J, Willette B. Surface reconstruction using alpha shapes[J]. Computer Graphics Forum, 1997, 16(4): 177-190.
[11] Dey T K, Giesen J, Leekha N, et al. Detecting boundaries for surface reconstruction using co-cons[J]. Int J Comput Graph CAD/CAM, 2001(16): 141-159.
[12] 王青, 王融清, 鲍虎军, 等. 散乱数据点的增量快速曲面重建算法[J]. 软件学报, 2000, 11(9): 1221-1227.
WANG Qing, WANG Rongqing, BAO Hujun, et al. A fast progressive surface reconstruction algorithm for unorganized points[J]. Journal of Software, 2000, 11(9): 1221-1227.
[13] 谭建荣, 李立新. 基于曲面局平特性的散乱数据拓扑重建算法[J]. 软件学报, 2002, 13(11): 2121-2126.
TAN Jianrong, LI Lixin. An algorithm for topology reconstruction from unorganized points based on local flatness of surface[J]. Journal of Software, 2002, 13(11): 2121-2126.
[14] 周培德. 计算几何-算法分析与设计[M]. 北京: 清华大学出版社, 2011: 88-129.
ZHOU Peide. Computational geometry-algorithm analysis and design[M]. Beijing: Tsinghua University Press, 2011: 88-129.
[15] 丁帆. 点云数据三维网格构造方法研究[D]. 武汉: 华中科技大学水电与数字化工程学院, 2007: 27-34.
DING Fan. Study on the 3D reconstruction for point cloud[D]. Wuhan: Huazhong University of Science & Technology. School of Hydropower & Information Engineering, 2007: 27-34.
[16] 陈凯, 杨小聪, 张达. 采空区三维激光扫描变形监测系统[J]. 矿冶, 2012, 21(1): 60-63.
CHEN Kai, YANG Xiaocong, ZHANG Da. 3D laser scanning deformation monitoring system to the cavity[J]. Mining and Metallurgy, 2012, 21(1): 60-63.
[17] 沐国宝. 向量积和混合积在重积分的坐标变换中的应用[J]. 上海应用技术学院学报(自然科学版), 2003, 3(2): 86-89.
MU Guobao. The application of vector products and mixed products to coordinate transformation of double and threefold integral[J]. Journal of Shanghai Institute of Technology (Natural Science), 2003, 3(2): 86-89.
[18] 廖鸿文. 基于Crust图的散乱数据点集的曲面网格重建的算法研究[D]. 长沙: 湖南大学软件学院, 2005: 45-50.
LIAO Hongwen. The research on Crust-based surface reconstruction algorithm[D]. Changsha: Hunan University. School of Software, 2005: 45-50.
[19] 余杰, 吕品, 郑昌文. Delaunay三角网构建方法比较研究[J]. 中国图象图形学报A, 2010, 15(8): 1158-1167.
YU Jie, L Pin, ZHENG Changwen. A comparative research on methods of Delaunay triangulation[J]. Journal of Image and Graphics, 2010, 15(8): 1158-1167.
[20] Bradford B, David P D, Hannu H. The quickhull algorithm for convex hull[J]. ACM Transactions on Mathematical Software, 1996, 22(4): 469-483.
[21] 毕林. 数字采矿软件平台关键技术研究[D]. 长沙: 中南大学资源与安全工程学院, 2010: 38-47.
BI Lin. Study of key technology of platform of digital mining software system[D]. Changsha: Central South University. School of Resources and Safety Engineering, 2010: 38-47.
(编辑 陈灿华)
收稿日期:2014-09-10;修回日期:2014-11-23
基金项目(Foundation item):国家高技术研究发展计划(863计划)项目(2011AA060407);国家自然科学基金资助项目(51374242);湖南省研究生科研创新项目(CX2011B116)(Project (2011AA060407) supported by the National High Technology Research and Development Program (863 Program) of China; Project (51374242) supported by the National Natural Science Foundation of China; Project (CX2011B116) supported by Research and Innovation of Postgraduates of Hunan Province)
通信作者:王李管,教授,从事数字矿山研究;E-mail:liguan_wang@163.com