留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于矿体轮廓线的三维建模新方法

毕林 刘晓明 陈鑫 朱忠华

毕林, 刘晓明, 陈鑫, 朱忠华. 一种基于矿体轮廓线的三维建模新方法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
引用本文: 毕林, 刘晓明, 陈鑫, 朱忠华. 一种基于矿体轮廓线的三维建模新方法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
BI Lin, LIU Xiaoming, CHEN Xin, ZHU Zhonghua. An Automatic 3D Modeling Method Based on Orebody Contours[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
Citation: BI Lin, LIU Xiaoming, CHEN Xin, ZHU Zhonghua. An Automatic 3D Modeling Method Based on Orebody Contours[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405

一种基于矿体轮廓线的三维建模新方法

doi: 10.13203/j.whugis20150405
基金项目: 

国家自然科学基金 Nos. 41572317, 51374242

中南大学创新驱动计划 No. 2015CX005

详细信息
    作者简介:

    毕林,博士,主要从事地质建模、地质统计、数字矿山相关理论与技术研究。Mr.bilin@163.com

  • 中图分类号: P208

An Automatic 3D Modeling Method Based on Orebody Contours

Funds: 

The National Natural Science Foundation of China Nos. 41572317, 51374242

Innovation Driven Plan of Central South University No. 2015CX005

图(9) / 表(1)
计量
  • 文章访问数:  1037
  • HTML全文浏览量:  75
  • PDF下载量:  290
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-04-17
  • 刊出日期:  2016-10-05

一种基于矿体轮廓线的三维建模新方法

doi: 10.13203/j.whugis20150405
    基金项目:

    国家自然科学基金 Nos. 41572317, 51374242

    中南大学创新驱动计划 No. 2015CX005

    作者简介:

    毕林,博士,主要从事地质建模、地质统计、数字矿山相关理论与技术研究。Mr.bilin@163.com

  • 中图分类号: P208

摘要: 结合轮廓线拼接法和体数据等值面法提出了一种新的矿体三维建模方法。该方法将轮廓线空间几何数据通过距离函数转换为距离场,从而将轮廓线间的表面重建问题转化为体数据等值面构造问题,避免了由人工指定轮廓线的对应关系;其次,通过扫描方式进行非欧氏距离变换实现距离场的计算及采用分治法层层建模,有效降低算法的时间和空间复杂度;然后,将非平直四棱柱作为体数据构造单元,以适应矿山实际数据的特殊性。实验证明该方法能够实现基于矿体轮廓线的复杂矿体三维自动建模,结果准确,模型质量高。

English Abstract

毕林, 刘晓明, 陈鑫, 朱忠华. 一种基于矿体轮廓线的三维建模新方法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
引用本文: 毕林, 刘晓明, 陈鑫, 朱忠华. 一种基于矿体轮廓线的三维建模新方法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
BI Lin, LIU Xiaoming, CHEN Xin, ZHU Zhonghua. An Automatic 3D Modeling Method Based on Orebody Contours[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
Citation: BI Lin, LIU Xiaoming, CHEN Xin, ZHU Zhonghua. An Automatic 3D Modeling Method Based on Orebody Contours[J]. Geomatics and Information Science of Wuhan University, 2016, 41(10): 1359-1365. doi: 10.13203/j.whugis20150405
  • 三维矿业软件已在金属资源行业得到了越来越广泛的应用,而矿体三维建模是三维矿业软件应用的基础,其中地质建模是当前学者们研究的热点[1, 2]

    基于矿体轮廓线进行三维重建是目前矿业软件(如国外的Vulcan、Datamine、Surpac、MineSight、Micromine 等;国内的Dimine、QuantyMine 、3DMine等)最常用方法。这些软件大都通过轮廓线拼接法进行建模,该方法所建模型与轮廓线严格吻合,但存在如下问题:① 轮廓线拼接通过人工选择轮廓线重建表面模型,主观随意性大,且难以从整体上把握矿体的形态;② 在处理分支复合等复杂问题时,非常繁琐,结果难以保证;③ 所建模型几何质量不高,存在大量退化三角形[3]

    另一种方法是体数据等值面法[4],相对于显式给出矿体轮廓线的方法,该方法又叫隐式建模法。隐式建模通过空间插值求取等值面的方法来重建三维模型,解决基于轮廓线拼接法遇到的问题。但矿体品位属性属于区域化变量,只存在于一定的空间范围内(区域化变量的几何域),该方法的主要问题是在进行矿化分布空间插值时没有几何域的约束,所建的三维模型与实际的矿体形态差别很大[5],所以在实际应用中隐式建模多用于矿体的属性建模,很少用于矿体的结构建模。

    本文结合轮廓线拼接法和体数据等值面法,将矿体轮廓线空间几何数据通过距离函数转换为场数据,通过体数据提取等值面自动形成三维矿体模型。针对其计算量大、表面重建速度慢的缺点,分析产生这些缺点的原因,通过距离变换(distance transform,DT)构造体数据,采用扫描法及距离传递加快计算速度,采用分治法解决轮廓线间距不一致的问题,采用非平直四棱柱作为体数据单元以满足矿山实际数据的特殊性,通过体数据的等值面构造算法(Marching Cubes,MC)进行等值面构造,实现复杂矿体三维建模。

    • 本文方法是将轮廓线空间信息(代表矿体边界)转化为空间数据场(体数据,如图 1),然后基于体数据提取等值面,从而得到矿体三维模型。需要解决的核心问题是如何将边界线转换为体数据,并保证形成的三维模型与原边界线高度吻合,且产生的矿体模型形态合理。流程如如图 2

      图  1  体数据

      Figure 1.  Schematic Diagram of Volume Data

      图  2  体数据等值面法流程

      Figure 2.  Flowchart of Isosurface from Volume Data

      (1) 每次任取相邻两组矿体轮廓线,选择场函数,形成三维数据场,数据场中的每个体素的8个顶点分别位于两组轮廓线所在的面上。

      (2) 根据所选择的场函数为体素的8个顶点计算函数值形成体数据,并规则体数据场。

      (3) 采用MC算法求取等值面,并形成表面模型。

      体素的每一条楞边上的数值可看作是线性的,即可采用MC算法构造等值面。该等值面就是正确连接轮廓线的可接受面,因为它完全取决于各体素上八个顶点的数值分布,因而不需要预先判断轮廓线之间的对应关系以及是否有分支存在。

      在整个算法过程中,距离场的形成与等值面的提取是关键。其中,距离场的形成过程中距离函数的选择及计算至关重要,距离场计算时间复杂度为O(n4)[11];等值面的提取采用MC算法[6],其时间复杂度为O(n);距离场计算过程是影响整个算法性能的主要因素。

    • 正确构造体数据是体数据等值面法的关键,其中场函数的选择尤为重要。根据体素的顶点与轮廓线的关系,场函数如下:

      (1)

      式中,x,y为体素顶点在轮廓线所在平面的坐标值。通过式(1) 的场函数计算数据场,然后采用MC算法构造值为0的等值面。如对一组轮廓线(长、宽范围约为85 m、35 m,轮廓线间距为20 m),采用2 m×2 m×20 m体素值,构建三维模型,其结果如图 3(a)。可以看出通过该场函数构造的三维模型表面呈锯齿状,轮廓线之间出现明显的台阶,不光滑,与原轮廓线吻合度较差。

      图  3  两种场函数重建结果

      Figure 3.  Reconstruction Results of Two Field Functions

      由距离函数计算形成的数据场叫距离场[7],距离场是个标量场,它反映了空间中任意点到一个给定物体表面的最短符号距离,符号表征该点与物体的内外关系,点位于物体之外时场值为负,反之为正。这样,对于空间中任意封闭曲面S⊂三维空间R3、任意点pR3,可以定义p相对S有符号距离场值hp=distance(p,S),显然h(p)=0表示点p处在物体的表面S上。距离函数的定义如下:

      (2)

      dist(x,y)是由点(x,y)到平面内所有轮廓线上最近点的距离。采用距离函数代替式(1) 对应的简单场函数,体数据中各网格点的数值不再是0、1或-1三个离散的简单数值,而是反映距离的连续函数在各网格点的采样值,从而使轮廓线间表面的构造是基于线性插值的结果,其建模结果如图 3(b)。显然,采用距离函数得到的重建表面没有明显的突变现象,重建表面平滑过渡,与原轮廓线吻合较好。

    • 采用距离函数构造体数据的优点是明显的,但对于每一个网格点需计算它与同一层平面上的各轮廓线的距离,然后通过比较才能求出最小值,其时间复杂度相当高。如果所建模型精度要求越高,则网格的密度越高,时间复杂度和空间复杂度就越高。设Nli是在第i层上轮廓线的数目;Nx、Ny分别为x、y方向上体素的维度,那么计算出该层体数据中全部网格点的距离函数需要Nz i=1 NxNyNli) 的时间复杂度。张勇[8]根据表面投影区比较两相邻切平面上对应像素点的状态函数值,以确定影响等值面生成的像素点,从而只对影响等值面生成的像素点的距离函数进行计算,但是这种方法对表面投影区的构建,以及对每个点的状态函数计算(内外点判断)都需要花费大量时间。

      对此,本文借助图像分析中DT(distance transform)思想来加快计算过程。DT的概念首先是Rosenfeld和Pfaltz[9]于1966年提出,目前已被广泛应用于图像分析、模式识别和计算机视觉等。现有的DT算法主要采用两类距离测度:非欧氏距离和欧氏距离。欧氏距离转换方法方面,许多学者都在研究高效快速的真实EDT(Euclidean distance transformation)算法[10],真实EDT计算具有较高的复杂度,在最坏情形下,当图像中有一半像素是非特征点时,其计算量达O( n4)[11], 效率非常低。而非欧氏DT方法没有指数和开方运算,同时易于通过扫描方式实现,可大大提高运算速度。故本文通过扫描方式进行非欧氏DT实现距离场的计算,其基本过程如下。

      1) 初始化所有网格距离场值为一个很小的值,如-9.99e+15。

      2) 从x=xi(i=0,1,…,n-1) 处平行于y轴发射线Rxi与轮廓线求交点,如图 4(a),用轮廓线线段两个端点的x值(x1,x2)与xi进行比较,如果x1 <xi <x2(不失一般性,假设x1<x2),则有交点,否则无交点则继续执行2) ,图中P0,P1表示射线与轮廓线有两个交点。

      图  4  距离场扫描填充算法示意

      Figure 4.  Filling Algorithm of Distance Fields

      3) 计算交点P坐标中的y值。y=y1+(y2-y1)×((x-x1)/(x2-x1)),其中x1,y1、(x2,y2)是与射线Rxi有交点的轮廓线线段的端点坐标。求出所有轮廓线线段与射线Rxi的交点y值,并将其从小到大排序,假设交点个数为Nc

      4) 计算像素(xi,yj)(j=0,1,…,m-1) )的距离场值。从小到大遍历交点y值序列,找到刚好大于yj的交点yyr(r=0,1,…,Nc-1) ,以此计算距离场值:如果r=0,则距离场值为d=yj-yr;如果r=Nc-1,表示没有找到刚好大于yj的交点,则d=yr-1-yj;否则d=min(yr-yj,yj-yr-1)。如果r为偶数,最终的距离场值d为负,否则为正。

      5) 对y轴方向进行以上相同的操作,如图 4(b)所示。

      x、y轴两个方向进行扫描及距离传递时,如果某像素的距离场值已经填充则保留小者,以满足最小距离的要求。可见只要分别沿x、y方向两次扫描就可以构建整个轮廓线平面的距离场,其时间复杂度为O(2n),远远低于O(n4),且没有指数和开方运算,大大提高了运算速度。

    • 等值面是空间中所有具有某个相同值的点的集合。可以表示为:

      (3)

      式中,c是常数。等值面在一个边界体素内的部分称为该体素内的等值面片,等值面是由许多个等值面片组成的连续曲面,本文在边界体素中生成三角面片,以三角面片拟合等值面,待重建的矿体表面为c=0的等值面。在三维空间规则数据场中构造等值面的方法有很多种,如MC算法、MT(marching tetrahedra)算法[12]、剖分立方体(dividing cubes)方法、立方体(cuberille)方法等,其中最具代表性的是MC算法。但MC算法存在二义性,解决这种面上二义性的算法主要有四面体剖分算法和双曲线渐近线算法。Nielson提出使用双曲线渐近线算法来解决面上的二义性[13]。基本思想是:等值面与立方体某一面的交线是一组双曲线或者其中的一支,当两支双曲线都与立方体表面相交时,就会出现二义性,此时两支双曲线将立方体表面分成三个区域。可以证明,双曲线渐近线的交点总是和其中一对交点落在同一个区域,比较渐近线交点和等值面的标量值,若渐近线交点的标量值大于等值面的标量值,则标量值大于等值面标量值的一对顶点与该交点落在同一个区域,反之亦然。本文采用双曲线渐近线算法来解决面上的二义性问题。基于MC算法求等值面的流程如下。

      1) 构造等值面三角形构型的查找表。查找表结构如下。

      struct Marching Cubes Triangle Cases{

      int edges[16];

      }MARCHING_CUBES_TRICASES[256];

      由于每一立方体共有8个顶点,每个顶点共有2个状态(物体内和物体外),因此查找表包含256个索引项,每一项的数值表示与三角形面片相交的边号;在这256种情况中最多存在5个三角形,则每一项最多需要长度为3×5+1=16的数组表示,最后一项用作结束标志(标记为-1) 。若对体素的边按如图 5(a)所示的方式进行编号,则图 5(b)所示情形(黑点表示顶点属性值≥c)对应的索引项为{0,3,8,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},其中0、3、8表示等值面的一个三角形面片的三个顶点是0、3、8号边与等值面的交点。

      图  5  空间目标体素化

      Figure 5.  Voxelization

      2) 设置体素的8个顶点定义标记位,例如,CASE_MASK[8]={1,2,4,8,16,32,64,128}。将每个顶点的属性值v与预先给定的等值面值c进行比较,将所有满足条件vc的顶点所对应的标记位进行“或”运算的结果即为查找表中的索引号。

      3) 从等值面三角形构型查找表中取出该状态标志项的记录信息,Chernyaev[14]对可能存在二义性的项进行了细分,对存在二义性的项使用双曲线渐近线算法来解决二义性。

      4) 如果体素边界与等值面存在交点,则通过边线两端点的坐标值线性插值计算交点坐标,插值公式如式(4) 所示,并将交点作为等值面三角形的顶点。

      (4)

      式中, x1x 0为相交边两端点坐标; v1、v 0为两端点属性值(此处即为距离值)。

      5) 连接所有体素等值面三角形面片,形成等值曲面。

      对所有体素执行步骤2) ~5) 。等值面提取算法的时间复杂度为O(n),n为体素个数,且针对每一个体素仅通过顶点的属性值与等值面值进行简单的数值比较即可得到查找表的索引号,再由预定的查找表容易判断是否存在交点,有效提高了运算速度。

    • §2的基本方法建立在基于立方体(cubes)规则网格基础上;在实际应用中勘探线不一定严格按照某个固定间距进行布置,经过地质解译后形成的轮廓线层间距并不一定相同;钻孔施工过程中钻孔轨迹线也不可能保证在一个面上,即轮廓线属于非共面曲线。因此不能简单通过规则立方体体素表达需要构建的距离场。根据勘探线剖面的特点,采用顶和底非共面直四棱柱(称之为非平直四棱柱)作为体素。在体素化空间目标时,在轮廓线所在的勘探线平面方向上采用规则网格,在垂直于勘探线平面方向上间距不等。这种数据组织方式降低了数据的结构性,使得扫描方式进行距离场的计算难以实现;同时所需存储空间大大提高。通过研究发现,轮廓线虽然存在不共面的情况,但轮廓线完全可以投影到某个平面上而不会出现自相交,所以将轮廓线进行投影处理后仍然可以通过扫描方式进行距离场的计算。为了保证所创建的三维模型尽可能与轮廓线吻合,在计算体素边界与等值面的交点实际坐标时采用非平直四棱柱。这样,平面投影后既可以很好地利用扫描法及距离传递构建距离场数据,又可以很好地满足矿体轮廓线间距不一致、不共面的具体情况。基于该思想将轮廓线投影到其所在的平均平面上,平均平面通过求取多边形平均法向量得到,其计算公式[15]为:

      (5)

      式中,i、j、kX、Y、Z 轴方向的单位向量;(xi,yi,zi)是点pi的坐标;多边形共有n个点。

      本文提出的矿体建模新方法的本质是将离散化矿体区域形成体数据,然后基于体数据求取等值面,所以体素单元越小所建模型精度越高,但体素单元越小算法的空间复杂度越高。为了解决此问题采用分层构建体数据,分层提取等值面的方法,该分治法很大程度地降低了对内存空间的要求。基于矿体轮廓线三维自动建模方法具体过程如下,同时参见图 6

      图  6  矿体轮廓线三维自动建模流程

      Figure 6.  Flowchart of Orebody 3D Automatic Modeling Based on Contours

      1) 取相邻两个轮廓线集(Si,Si+1),每个轮廓线集包含一个或多个轮廓线(C),即

      SiC0i,C1i,…,Cji,…,Cmi,

      Si+1C0i+1,C1i+1,…,Cki+1,…Cni+1

      2) 对轮廓线集中的轮廓线Cji,j∈(0,m)和Cki+1,k∈(0,n)通过式(4) 求取法向量,并将轮廓线分别投影到由其法向量及轮廓线上任意一点确定的平面Pi和平面Pj上;

      3) 在Pi、Pj平面上根据轮廓线的最小外包及分辨率要求划分为方向相同大小一致的规则网格;

      4) 分别对Pi、Pj平面每一个单个网格的4个顶点通过§2.2所提出的距离场计算方法计算距离值;

      5) 将Pi、Pj平面上的网格单元返投影到轮廓线所在的空间曲面上,并由投影后的对应网格单元组成非平直四棱柱形成体数据Vi

      6) 采用MC算法对Vi求取等值面;

      7) 对所有相邻两个轮廓线集重复步骤1) ~6) ;

      8) 合并所有层的等值面,简化模型,形成最终的矿体三维模型。

    • 实验的运行环境为Windows 7 操作系统,CPU为Intel Core i7-264M 2.80 GHz,内存为4 GB。分别对程潮铁矿(PI)、松树脚矿(PⅡ)、三鑫金铜矿(PⅢ)的部分矿体进行三维建模,其中轮廓线层数分别为5层、4层、7层,网格单元尺寸为1 m×1 m,每个项目耗时如表 1所示,其成果如图 7所示。

      图  7  基于矿体轮廓线三维自动建模成果

      Figure 7.  Results of Automatic 3D Modeling

      表 1  三维重建耗时表

      Table 1.  Time Required for 3D Reconstruction

      项目三角形/个体素/个耗时/s
      PI 390 764 925 160 0.864
      PⅡ 26 948 183 600 0.111
      PⅢ 118 928 292 600 0.206

      本文提出的基于矿体轮廓线三维自动建模的整个过程中,“轮廓线投影到面”及“反投影到轮廓线”等都是基于轮廓线,这些操作的迭代次数都远远小于体素个数,即整个算法的效率主要受基于体素的体数据计算及等值面提取的影响,整个算法的时间复杂为O(n),即耗时t与体素个数n基本成线性关系,如图 8所示。

      图  8  体素个数与耗时关系

      Figure 8.  Relation Ship Between Number of Voxels and Time-Comsuming

      取出某矿体两条轮廓线分别用轮廓线拼接法和本文方法建模,其结果如图 9。两种建模方法都是通过某种算法对轮廓线之间未知部分进行推估,轮廓线拼接法是将两两轮廓线之间直接三角形连接,本文算法是通过MC算法提取等值面形成若干三角形面片组成的曲面。两种方法所建模型在形态上有一定差异:轮廓线拼接法所建模型几何质量不高,存在大量退化、奇异三角形,三角形形态不均匀,但其优点是完全与轮廓线吻合,且三角形个数较少;本文方法所建模型三角形形态均匀,模型质量较高,但在轮廓线尖角处(相邻线段距离小于网格单元尺寸,本实验为1 m×1 m)与轮廓线不吻合,如图 9(b)所示左下角放大部分。由于轮廓线拼接法是通过相邻两轮廓线直接连线框实现三维重建,属于“硬连接”,而本文方法在求取等值面时是通过线性插值实现三维重建,属于“软连接”(即相邻层面间形态变化趋于轮廓线形状的渐变),所以本文方法所建矿体模型形态更自然、合理。

      图  9  轮廓线拼接法与本文方法的比较

      Figure 9.  Comparison of Two Methods

    • 本文结合了轮廓线拼接法和体数据等值面法两种方法的优点,所建模型既与矿体轮廓线充分吻合又可以实现自动重建;同时很好地克服了两种方法的局限性,所建模型质量较高、形态自然。而且实际应用中可以非持久化存储所建模型,而是在需要时自动生成模型,即“即计算”。所谓“即计算”就是在需要时才根据原始基础数据及具体参数通过自动重建算法创建,从而达到“no-Model”的目标。所谓“no-Model”,即没有模型、不仅仅是一个模型。这样可以很好地解决矿体模型动态更新的难题,避免维护大量“数据垃圾”。

      本文方法的主要缺点是,在突变处,模型与轮廓线不能很好吻合;解决方法是通过降低体素的尺寸以增强模型与轮廓线的吻合度,但模型三角形面的个数会急剧增加,导致模型数据增大。

      本文仅仅是基于矿体轮廓线实现了自动建模,先经地质工程师进行地质解译形成的矿体轮廓线是其前提条件。要完全实现矿体的自动建模与动态更新,今后需要重点解决基于人工智能的矿体轮廓线自动解译、虚拟轮廓线插值算法、基于纵横交叉轮廓线体数据的构建以及由此引入的等值面提取二义性问题等。

参考文献 (15)

目录

    /

    返回文章
    返回