一种用于地下矿可视化生产管控系统的全路径漫游网络设计

熊书敏，郭小先，王李管，黄俊歆, ，陈建宏

(1. 中南大学 资源与安全工程学院，湖南 长沙，410083；2. 西部矿业股份有限公司, 青海 西宁，810001；3. 湖南工学院 安全与环境工程系，湖南 衡阳，421001)

基于视景仿真技术的地下矿可视化生产管控系统是数字矿山和智能矿山的基础软件平台，它可以直观地展示矿山开采环境、井巷工程和各种生产辅助系统的布局，关键设备的实时位置、姿态和工况，以及实时环境监测数据，对矿山生产、调度和安全管理具有重要意义，其特征与关键技术是近期的研究热点[1-6]。漫游作为一种重要的人机交互方式，成为管控系统的一项重要功能。目前，在管控系统中采用的漫游方式是所有视景仿真系统通用的漫游方式。视景仿真系统通用的漫游方式主要有3种[7]：第1种是无碰撞检测的交互式漫游，就是通过鼠标或者键盘来旋转、平移和缩放场景。第2种是基于碰撞检测的交互式漫游(第1人称和第 3人称漫游方式)[8-9]。在相机移动的过程中，利用碰撞检测技术对可视锥的后视面及视点组成的四棱锥或者人物化身与前方物体进行碰撞检测，避免视点或者人物化身穿过物体。第3种是沿着固定路径的飞行漫游(也称为自动漫游)[10-11]。在场景中指定或自动生成一条最佳路径，然后控制视点自动以一定的速度沿着这条路线移动，实现飞行效果。由于要提供井巷内部快速巡视的功能，管控系统对漫游方式的快捷与灵活性提出了更高的要求，现有的漫游方式应用于井巷漫游存在 2点不足[11]：(1)交互方式虽灵活但是需要不断地调整方向和位置，影响了用户的注意力，进而影响了漫游的效果和速度；(2)自动漫游方式由于有漫游路径，减轻了用户的操作负担，可以实现快速漫游，但是路径是事先制定的固定路径，漫游时不能改变，缺乏灵活性。因此，本文作者提出了一种基于复杂路径的交互式漫游方式，由于有路径的支持，这种方式既保留了自动漫游的快捷性和交互式漫游的灵活性，又简化了交互式漫游的操作过程。复杂路径的设计是这种漫游方式的关键，因此，提出了一种虚拟全路径漫游网络，以此网络作为视点的运动路径。给出了该网络的定义、数据结构、构建算法及其在井巷漫游功能中的使用方式。

1 虚拟全路径漫游网络及其数据结构

1.1 虚拟全路径漫游网络

井巷是矿山生产的重要通道，井巷之间相互连通，形成了一个具有网络特征的三维空间。相应地，井巷中线也形成了一个中线几何网络，如图1所示。

如果直接以原始的三维井巷中线几何网络作为漫游路径，相机在边上移动时帧与帧之间不够平滑[11]，在交岔口处也无法表现出转弯的效果。因此对该网络的边和结点进行改造：(1)在结点处引入虚拟边和虚拟结点，保证其中任意两个虚拟结点之间都有虚拟边连通，虚拟边是三维直线或者圆弧线。(2)对所有保留下来的边进行光滑。经过改造后，将原始的中线网络变成一个用于漫游功能的三维几何网络，将此网络称之为虚拟全路径漫游网络(Virtual full path roaming network，VFPRN)，如图2所示。

图1 三维井巷中线网络Fig.1 3D roadway midline network

图2 虚拟全路径漫游网络Fig.2 Virtual full path roaming network

VFPRN各组成元素的定义如下。

(1)原始结点。若干条井巷中线在交岔口处的交点，或者一条井巷的端头处的中线点，称之为原始结点。在VFPRN中不存在交岔口处的原始结点，这种结点在插入虚拟结点和虚拟边之后被删除了。端头处的原始结点则保留了下来，如主井、斜井和平硐的入口处和掘进头处。

(2)虚拟结点。在交岔口原始结点附近的中线上插入一个新的中线点，此中线点即为虚拟结点。虚拟结点不具有实际意义，只作为交岔口处视点转弯的起点或终点。

(3)原始边。原始边是结点(虚拟结点和原始结点)之间保留下来的原始中线段经过三维光滑插值后得到的线段。原始边与巷道实体之间有对应关系。

(4)虚拟边。在交叉口处，连接任意两个虚拟结点的一段三维圆弧或直线称之为虚拟边。虚拟边是在交叉口处从一条巷道进入另一条巷道的漫游轨道，类似如交通网络中的弯道。

VFPRN具有2个特征：

(1)交岔口处存在全路径。所谓全路径，即是在交岔口处任意两个虚拟结点之间都是直接联通的。如图2所示，视点从一条巷道进入如其他3条巷道均有路径(虚拟边)可走。

(2)结点边表的有序性。将依附于结点的所有边依据边的走向按顺时针方向进行排序，形成有序边表。如图3所示。视点在交岔口处转弯时，这种有序边表很容易实现前方边的选择。

图3 结点的边序Fig.3 Order of edges attached to node

1.2 虚拟全路径漫游网络的数据结构

几何网络的存储结构有数组、邻接表、邻接多重表和十字链表等方式[12]。其中，数组用于存储稀疏的无向图会浪费大量的内存空间，邻接表每条边记录了2次，不便于某些图的操作，也不便于在数据库中存储，邻接多重表是无向图的一种存储结构，操作便捷，改造后既可以用于内存数据组织，又适合于数据库中关系表的组织形式。虚拟全路径漫游网络不需要考虑边的方向性，属于一种稀疏无向图，故采用邻接多重表来存储。传统的邻接多重表是一种链式存储结构，每条边用1个结点表示，包含标志域、2个顶点域、2个边指针域和1个边信息域。每个顶点也用1个结点表示，包含顶点信息域和边指针域。所有依附于同一顶点的边串联在同一链表中，由于每条边依附于2个顶点，则每个边结点同时链接在2个链表中。使用指针容易出现安全性问题，同时指针只有在内存中才有意义，不适应外存的数据组织。因此对邻接多重表进行改造：用结点(边)唯一整型标识(ID)代替指向结点(边)的指针；用边的ID列表代替边链表[13]。并将内存数据结构和数据库记录结构分开设计。

内存数据结构由结点类、边类和网络类组成：

(1)边类的主要数据成员为：

class CEdge

{

long nID; //边的唯一整型标识

string strName; //边的名称

long nFID; //边对应的巷道实体ID

long fromID,toID;//边的两个结点的唯一整型标识

CCoord *pCoord;//边包含的点的坐标串,

// CCoord包含(x,y,z)

}

(2)结点类的主要数据成员为：

class CNode

{

long nID; //结点的唯一整型标识

string strName; //结点的名称

vector＜long＞ IDList;//边 ID 列表

}

(3)网络类的主要数据成员为：

class CGeoNetwork

{

vector＜long＞ nodeIDList;//所有结点 ID 列表

vector＜long＞ edgeIDList;//所有边 ID 列表

}

VFPRN在数据库中存储时，分为结点表和边表。结点表的记录结构如表1所示。边表的记录结构如表2所示。

表1 结点记录结构Table 1 Node record structure

表2 边记录结构Table 2 Edge record structure

2 虚拟全路径漫游网络的构建

在地下矿三维可视化管控系统中，以参数化实体与网络复合数据模型(Parametric entity-network data model，PENDM)来表达井巷工程的实体和网络拓扑特征。PENDM以抽象实体模型(点和线)为基础，兼顾网络模型，由实体元素、网络元素和参数元素等3种元素组成。井巷实体可以分为位置、分段井巷中心线、分段井巷、井巷、井巷组、井巷模型等6个层次。其中，井巷模型包含矿山的所有井巷工程，井巷组是人为划分的若干个井巷的集合体，分段井巷是井巷被断面变化处和交叉口打断后的实体。其中所有的分段井巷连通形成一个空间几何网络。PENDM 模型及其与井巷实体的映射关系如图4所示。

图4 PENDM模型及其映射图Fig.4 A map between PENDM and Roadways

井巷PENDM模型是构建VFPRN的基础，首先取出PENDM中包含的分段中线网络，经过原始结点虚拟化、原始边光滑和结点的边排序3个步骤即生成了虚拟全路径漫游网络：

步骤1：原始结点虚拟化。基本思路是：在分段中线网络中有2条边以上的结点处，插入若干个虚拟结点代替原始结点，同时用若干条虚拟边连接虚拟结点。为了消除漫游时场景的“跳变”现象，虚拟边必须是光滑的。常用光滑插值方法主要有样条插值[11]和圆弧插值[14]。用圆弧法插值能较好地保持虚拟边与巷道的一致性，因此本文使用基于三维旋转矢量的圆弧插值算法。以一个原始结点的处理为例说明该算法的原理(如图5所示)，其中，E1，E2和E3是原始边，N2是原始结点，N1，N3和N4是需要插入的虚拟结点，也是虚拟边与原始边的切点，E4，E5和E6是需要插入的虚拟边。O是∠N1N2N3的内切圆的圆心点。

图5 原始结点的处理Fig.5 Original node process

对原始结点N2进行虚拟化的步骤如下：

(1)确定虚拟结点和N2的距离。根据巷道宽度确定一个常数S，此常数过小影响转弯效果，过大会使得虚拟边穿过巷道两帮，因此需要根据实际情况来考虑，可取结点处最窄巷道宽度的一半，此时可以保证不会“穿帮”。

(2)根据插值距离S计算出N1，N3和N43个虚拟结点的三维坐标。

(3)根据∠N1N2N3与直角的近似程度判断由N1，N2和N3组成的边是否需要光滑，需要光滑则进一步处理，否则用N1，N2和N33点生成1条虚拟边，转至(6)。

(4)求∠N1N2N3的内切圆的圆心点O的坐标(Xo，Yo，Zo)：

其中，(X2，Y2，Z2)为点N2的坐标；I为向量单位向量，

先确定虚拟边上的点数N，计算角度∠N1ON3(φ)：

求出单次旋转的旋转角度θ：

计算旋转轴矢量A(Ax，Ay，Az)，并单位化：

计算旋转矩阵R[15]：

计算虚拟边E4上的点Pi(Xi，Yi，Zi)：

(6)重复(3)～(5)步，即可求出N3和N4之间的虚拟边E5，N1和N4之间的虚拟边E6。

(7)修改网络。去掉网络中的原始结点N2，删除原始边E1，E2和E3中的虚线部分(如图5所示)；加入虚拟结点N1，N3和N4，加入虚拟边E4，E5和E6。

遍历分段中线网络中的原始结点，对有2条以上邻边的原始结点进行上述的虚拟化处理，最后得到的网络就是一个在交岔口处具有全路径的漫游网络。

该算法采用三维矢量运算，能处理具有任意空间形态的两段井巷(包括平巷、斜巷与竖井)之间的插值问题。图6所示为某铜矿部分井巷的虚拟全路径漫游网络。

图6 虚拟全路径漫游网络(局部)Fig.6 Part of virtual full path roaming network

步骤2：原始边的光滑。对虚拟全路径漫游网络中保留下来的真实边采用分段圆弧法在三维空间中进行光滑。光滑前后对比如图7所示。分段圆弧法光滑边的算法思想是：从边的一端开始搜索，找到第1个需要光滑的顶点(如图7中的a点)，在该顶点两边一定距离上插入2个新顶点(如图7中的a1，a2)，在这3点(a1，a，a2)之间插入1段圆弧，该圆弧与边相切于a1和a2。插入圆弧的算法采用求解虚拟边的算法。重复这个过程，处理完边上余下的需要光滑的顶点。原始边光滑后，原始边中的虚线部分被实线圆弧取代。

图7 原始边光滑前后对比图Fig.7 Contrast graph between pre- and post-smoothing

步骤3：结点的边表排序。遍历图中所有结点，对每个结点的边表中的边，根据边的方位角按顺时针的顺序排序，对于竖井中的边，由于其方位角为0°，则直接插入有序边表的尾部。

3 在井巷漫游中的应用

虚拟全路径漫游网络专为交互式漫游方式而设计，但同时也可以作为自动漫游方式的路径集。

在交互式井巷漫游功能中，虚拟全路径漫游网络作为视点运动的“轨道”使用，用户通过键盘控制视点在网络中快速“行驶”。具体做法如下：开始井巷漫游功能时，提取整个网络，然后将相机定位到起始边的一个端点上，并将相机对准边上的下一个点。当用户按键移动相机时，它沿着网络中的边运动。在交岔口处，通过方向键从前方虚拟结点的有序边表中沿顺时针或者逆时针方向选择要经过的下一条虚拟边。这样不仅漫游操作简便，而且在交岔口处经过虚拟边时实现了平滑的转弯效果。通过漫游网络中的边与井巷实体之间的关联信息，在漫游时可以实时提取并显示当前井巷实体的属性信息(静态属性和动态属性)。在交叉口处虚拟边上的漫游效果如图8所示。

图8 基于虚拟边的转弯过程Fig.8 Turning on a virtual edge

自动漫游时，有2种方式从网络中提取飞行路径：一种是通过交互式指定若干条连通的井巷实体组成一条“路线”后，根据井巷实体与网络中边的关联信息，可以从虚拟全路径漫游网络里提取一条由若干条边组成的光滑的飞行路径。另一种是交互式指定几个必经巷道或者硐室，然后采用分段路径寻优算法[16]自动求解一条飞行路径。算法的基本思想是：取用户指定的所有必经巷道(边)两端的结点，插入到起点(vs)和终点(ve)之间形成一个必经结点列表(vs，n1，n2，…，ni，nj，ve)，然后将整个路径分成若干段：(vs，n1)，(n1，n2)，…，(ni，vj)，(nj，ve)，利用网络拓扑关系，采用基于启发式搜索的Dijkstra算法分别求解每段的最短路径，最后将各段的最短路径组合起来得到最终的最短路径。

图9所示粗线部分为从某铜矿漫游网络中提取的一条自动漫游路径，其中E1和E2是2条必须经过的边。

图9 自动漫游路径Fig.9 Navigation path

4 结论

(1)对于具有复杂井巷工程的大型地下矿山三维场景来说，以虚拟全路径漫游网络作为视点的运动路径可以在井巷内部实现快速而灵活的交互式巡检功能。

(2)以虚拟全路径漫游网络作为原始路径集，能自动提取自动漫游所需的光滑路径。

[1]王李管, 曾庆田, 贾明涛. 数字矿山整体实施方案及其关键技术[J]. 采矿技术, 2006(3): 494-498.WANG Li-guan, ZENG Qing-tian, JIA Ming-tao. The implementing scheme and key technologies of digital mine[J].Mining Technology, 2006(3): 494-498.

[2]ZHOU Ke-ping, GUO Ming-ming. Virtual reality simulation system for underground mining project[C]//Proceedings of 2009 4th International Conference Computer Science & Education Nanning: IEEE Press, 2009: 615-632.

[3]Wei Y, Wu X, Soole P. Reconstruction and simulation of 3D open pits: A critical path towards practical virtual mine[J].Mineral Resources Engineering, 1998, 7(3): 221-231.

[4]Boulanger P, Lapointe J F, Wong W. Virtualized reality: an application to open-pit mine monitoring[C]//Archives of the 19th Congress of the International Society for Photogrammetry and Remote Sensing (ISPRS), Amsterdam: IEEE Press, 2000: 92-98.

[5]毛善君, 熊伟. 煤矿虚拟环境系统的总体设计及初步实现[J].煤炭学报, 2005, 30(5): 571-575.MAO Shan-jun, XIONG Wei. Design and primary implementation of coal mine virtual environment system[J].Journal of China Coal Society, 2005, 30(5): 571-575.

[6]周智勇, 陈建宏, 杨立兵. 大型矿山地矿工程三维可视化模型的构建[J]. 中南大学学报: 自然科学版, 2008, 39(3):423-428.ZHOU Zhi-yong, CHEN Jian-hong, YANG Li-bing. 3D visualization modeling on geological and mining engineering in a large-sized mine[J]. Journal of Central South University:Science and Technology, 2008, 39(3): 423-428.

[7]尚建嘎, 刘修国, 郑坤. 三维场景交互漫游的研究与实现[J].计算机工程, 2003, 29(2): 61-62.SHANG Jian-ga, LIU Xiu-guo, ZHENG Kun. Research and implementation of interactive walkthrough in 3D scene[J].Computer Engineering, 2003, 29(2): 61-62.

[8]王志强, 洪嘉振, 杨辉. 碰撞检测问题研究综述[J]. 软件学报,1999, 10(5): 545-551.WANG Zhi-qiang, HONG Jia-zhen, YANG Hui. A Survey of collision detection problem[J]. Journal of Software, 1999, 10(5):545-551.

[9]常明, 罗自荣, 李丹, 等. 面向虚拟环境漫游的快速碰撞检测算法[J]. 华中科技大学学报: 自然科学版, 2006, 34(11): 7-10.CHANG Ming, LUO Zi-rong, LI Dan, et al. Fast collision detection algorithm for virtual environment walkthrough[J].Journal Huazhong University of Science and Technology: Nature Science Edition, 2006, 34(11): 7-10.

[10]吴玲达, 赵健, 杨冰, 等. 一种虚拟场景的自动漫游方法[J].小型微型计算机系统, 2010, 31(8): 1563-1566.WU Ling-da, ZHAO Jian, YANG Bing, et al. Method for virtual scene automatic exploration[J]. Journal of Chinese Computer Systems, 2010, 31(8): 1563-1566.

[11]续爱民, 金烨, 鲍劲松. 虚拟场景中自动漫游路径的多分辨率规划[J]. 系统仿真学报, 2005, 17(8): 1912-1915.XU Ai-min, JIN Ye, BAO Jin-song. Navigation path multi-resolution planning in virtual environment[J]. Journal of System Simulation, 2005, 17(8): 1912-1915.

[12]严蔚敏, 吴伟民. 数据结构[J]. 北京: 清华大学出版社, 1997:160-166.YAN Wei-min, WU Wei-min. Data structures[M]. Beijing:Tsinghua University Press, 1997: 160-166.

[13]熊书敏, 郑坤, 吴信才. 基于实体模型的三维GIS矢量数据管理[J]. 地理空间信息, 2006, 4(1): 18-20.XIONG Shu-min, ZHENG Kun, WU Xin-cai. Management of 3D GIS vector data based on feature-oriented model[J].Geospatial Information, 2006, 4(1): 18-20.

[14]王秀梅, 曹秋霞, 赵建敏. 用三坐标数控铣床加工空间曲面时的圆弧插值算法[J]. 工程图学学报, 2007(4): 145-149.WANG Xiu-mei, CAO Qiu-xia, ZHAO Jian-min. Algorithm of circular interpolation in machining space curved face by three-coordinate NC milling machine[J]. Journal of Engineering Graphics, 2007(4): 145-149.

[15]Dunn F, Parberry O. 3D math primer for graphics and game development[M]. Texas: Wordware Publishing Inc, 2002:106-111.

[16]周鹏, 张骏, 史忠科. 分段路径寻优算法研究及实现[J]. 计算机应用研究, 2005(12): 241-243.ZHOU Peng, ZHANG Jun, SHI Zhong-ke. Algorithm for searching shortest path piecewise and its implementation[J].Application Research of Computers, 2005(12): 241-243.