基于全路径网络与有限状态机的井巷漫游

熊书敏^{1, 2}，王李管^{1, 2}，陈忠强^{1, 2}

(1. 中南大学 资源与安全工程学院，湖南 长沙，410083；

2. 中南大学 数字矿山研究中心，湖南 长沙，410083)

摘要：针对当前井巷漫游方式在灵活性和易用性方面的不足，提出一种将全路径网络作为漫游相机运动轨道的交互式漫游方式。全路径网络由原始结点、虚拟结点、原始边和虚拟边组成，具有2个特征：交岔口处存在全路径和结点边表的有序性。运用有限状态机的原理对漫游器的交互式行为进行建模，从地下矿可视化生产管控系统对漫游器的功能需求出发，采用面向对象的思想和State模式设计漫游器相关对象的类结构，并在可视化生产管控平台上实现一个漫游器实例。研究结果表明：此漫游方式可供用户交互式地在网状的地下巷道内快速巡视，且拐弯处画面流畅，在功能的灵活性和操作的易用性方面取得较好的平衡，增强井巷漫游功能的可操作性。

关键词：虚拟矿山；数字矿山；井巷漫游；虚拟全路径漫游网络；管控系统

中图分类号：TP391.9          文献标志码：A         文章编号：1672-7207(2013)08-3267-06

Roadway roaming based on full path network and finite state machine

XIONG Shumin^{1, 2}, WANG Liguan^{1, 2}, CHEN Zhongqiang^{1, 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: Aimed at the challenges that the traditional roadway roaming mode confronted in improving flexibility and easy use, a interactive roadway roaming mode based on the virtual full path roaming network (VFPRN) was proposed. VFPRN is composed of node, edge, virtual node and virtual edge. It has two outstanding characteristics, one is the full path at the intersection, another is the orderliness of edges. The behaviors of roaming module were modeled based on the finite state machine theory. According to the functional requirement of roadway roaming in the underground mine 3D visual production management and control system (UMPMCS), the correlative classes were designed by adopting the object-oriented idea and state pattern, and implemented based on UMPMCS. The results show that users can roam quickly in the underground roadway network by this roaming mode, and the frames are displayed smoothly at the intersection. This roaming mode realizes the balance of flexibility and easy use, and improves the operability of roaming function.

Key words: virtual mine; digital mine; roadway roaming; virtual full path roaming network; management and control system

漫游是地下矿可视化生产管控系统的一项重要功能^[1-4]。目前，三维场景中的漫游方式主要有3种^[5]：第一种是无碰撞检测的交互式漫游，就是通过鼠标或者键盘来旋转、平移和缩放场景；第二种是基于碰撞检测的交互式漫游(第一人称和第三人称漫游方式)^[6-8]；第三种是沿着固定路径的飞行漫游(也称为自动漫游)^[9-11]。由于要提供井巷内部快速巡视的功能，管控系统对漫游方式的易用性与灵活性提出更高的要求，现有的漫游方式应用于管控系统存在2点不足^[11]：(1) 交互方式虽灵活但是需要不断地调整方向和位置，影响用户注意力，进而影响漫游的效果和速度；(2) 自动漫游方式可减轻用户的操作负担，实现快速漫游，但漫游时不能改变漫游路径，缺乏灵活性。因此，本文作者提出一种基于虚拟全路径漫游网络的交互式漫游方式，并利用有限状态机的原理建立漫游器的行为模型，在可视化生产管控平台的基础上实现一个具备前进、后退、转向、调头、升降、加速、减速等功能的漫游器。

1  虚拟全路径漫游网络

井巷是矿山生产的重要通道，井巷之间相互连通，形成一个具有网络特征的三维空间。相应地，井巷中线也形成一个中线几何网络。但是如果直接用中线几何网络作为漫游路径，相机在边上移动时帧与帧之间不够平滑^[11]，在交岔口处也无法表现出转弯的效果。因此，对该网络的边和结点进行改造：(1) 在结点处引入虚拟边和虚拟结点，保证其中任意2个虚拟结点之间都有虚拟边连通，虚拟边是三维直线或者圆弧线。(2) 对所有保留下来的边进行光滑处理。经过这2步改造，将原始的中线网络变成1个用于漫游功能的三维几何网络，将此网络称之为虚拟全路径漫游网络(VFPRN)，简称全路径网络，如图1所示。VFPRN各组成元素的定义如下：

图1  虚拟全路径漫游网络

Fig. 1  Virtual full path roaming network

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

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

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

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

VFPRN具有2个特征：

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

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

图2  结点的边序

Fig. 2  Order of edges attached to node

2  有限状态机

有限状态机(FSM)常用来对反应式系统建模^[12-13]，反应式系统对外部和内部事件产生反应，属于事件驱动的系统。FSM在任何时候只能处于1个特定的状态。当接收到1个输入事件时，FSM产生1个输出，同时也可能伴随状态的转换。FSM具有如下特征：(1) 系统的状态和状态转换的条件是有限的；(2) 转换是系统对事件的反应，转换所用时间近似为零；(3) 系统总是处于某一确定的状态上，且其行为是确定的。

FSM的形式化定义是1个五元组M=[I，O，S，D，L]。其中：M表示状态机，I是输入集合，O是输出集合，S是状态集，均为非空有穷集；D是状态转换函数，定义为D：S×X→S；L是输出函数，定义为L：I×S→O。FSM的确切描述方法是状态转换表和状态转换图。

3  基于FSM的漫游器行为模型

3.1  漫游器的行为建模方法

基于全路径网络的漫游器根据键盘输入信息(菜单、方向键、字符键和控制键)控制场景中的相机在网络上移动，实现在三维井巷内部的漫游动作(前进、后退、选择前方边、调头、加速、减速、升高、降低、开始和结束漫游等等)。其行为和状态是可以预见的，是典型的基于事件的反应式系统。因此，以用户的输入信息作为FSM的输入事件，将漫游时计算和调正相机在全路径网络中的位置和方向或者发出内部事件的行为作为FSM的动作，采用FSM建立漫游器的行为模型。建立FSM的方法如下^[14]：

(1) 考察对象的生命周期，将其中满足某种条件、执行某些动作或等待某些事件发生的1个阶段，抽象为FSM的1个状态。

(2) 考察所有引起对象状态变化过程，探究状态变化的原因，将其抽象为事件；确定状态转移时是否产生一些反应(抽象为动作)或者产生一些内部的输出(抽象为内部事件)，从而确定转移，转移=(源状态，输入事件，动作或输出事件，目标状态)，其中目标状态可以和源状态相同。

3.2  漫游器的行为建模

漫游器的状态由相机状态来决定，相机沿着全路径网络运动时，根据它在边上的位置(后结点上、中间和前结点上)和运动状态(前进、停止前进、后退和停止后退)将它的状态归纳为如下9种：

S0(Waiting_State)：空状态；

S1(BackNode_Go_State)：相机位于后结点处，处于前进状态；

S2(Edge_Go_State)：相机位于边内，处于前进状态；

S3(FrontNode_Go_State)：相机位于前结点处，处于前进状态；

S4(FrontNode_StopGo_State)：相机位于悬挂结点，处于停止前进状态；

S5(FrontNode_Back_State)：相机位于前结点处，处于后退状态；

S6(Edge_Back_State)：相机位于边内，处于后退状态；

S7(BackNode_Back_State)：相机位于后结点处，处于后退状态；

S8(BackNode_StopBack_State)：相机位于悬挂结点处，处于停止后退状态。

漫游器的输入事件分为外部事件和内部事件。外部事件是用户通过菜单和键盘发出的命令，包括开始(E0)、结束(E1)、前进(E2)、后退(E3)、调头(E4)、左转(E5)、右转(E6)、升高(E7)、降低(E8)；内部事件是漫游器在某些状态转移过程中自身输出的事件，包括到达结点(E10)、到达悬挂结点(E11)和换边(E12)。

为实现漫游功能，漫游器在状态转换时执行相应的动作，控制相机的位置和方向，或者输出内部事件。动作的编码及其意义如下：

A1：结点检测并前移相机，若到达结点，则触发E10事件；

A2：结点检测并后移相机，若到达结点，则触发E10事件；

A3：按顺时针顺序确定并记录下一条边；

A4：按逆时针顺序确定并记录下一条边；

A5：更换前后结点；

A6：换边，改变前后结点；

A7：换边，改变前后结点，并改变相机移动方向为前进；

A8：换边，改变前后结点，并改变相机移动方向为后退；

A9：结点检测，并发出E11或者E12；

A10：改变相机移动方向为前进；

A11：改变相机移动方向为后腿；

A12：升高相机；

A13：降低相机；

A14：加速；

A15：减速；

A16：设置漫游器的漫游参数，设置相机到漫游网络的起始边上；

A17：重置漫游器状态，清除漫游网络数据，恢复相机到漫游前的位置和方向。

漫游器的工作原理是：当用户点击菜单“开始井巷漫游”时，系统向漫游器发出E0(开始)事件，漫游器如果处于状态S0(空状态)就执行动作A16，设置漫游器的漫游参数(漫游网络，起始边和起始结点，漫游速度和高度)，将相机设置到漫游网络的起始边上，同时进入漫游状态S1；随后用户可以通过键盘的方向键和字符键发出E0-E6的系列事件，漫游器响应事件迁移自身的状态，执行对应的动作，控制相机沿着网络的边移动；一旦用户点击菜单“结束井巷漫游”，系统向漫游器发出E1事件，漫游器执行动作A17，将相机恢复到漫游前的状态，漫游器的状态切换到S0。表示漫游器的行为逻辑的状态迁移表如表1所示。

4  漫游器的实现

基于全路径漫游网络的漫游功能的实现包括漫游路径数据结构的设计与实现和漫游器的设计与实现。漫游路径是1个三维几何网络，基于面向对象的软件设计思想，用网络类、结点类和边类来描述。漫游器作为1个FSM，常见的实现方式有过程模式和State模式^[15]。其中，过程模式是一种常见的FSM的结构化实现方法，它利用全局状态变量和嵌套的条件分支语句来实现，外层分支语句判断选择当前的状态，里层分支语句判断在相应状态下发生的事件，从而确定执行相应的动作并切换状态。过程模式对于简单的FSM来讲是一种很简洁的实现方式。State模式是一种FSM的面向对象的实现方法，它将所有与1个特定的状态相关的行为都封装到1个State对象中，实现状态行为的分离和局部化，在实现复杂的FSM时具有优势。本文采用State模式实现漫游器，设计类图如图3所示，图3中只给出主要类及其主要的成员变量和成员函数，其中，CLaneRoamManager是漫游器类，CGeoNetwork是几何网络类，CCamera是相机类，KeyEvent是键盘消息封装类，CRoamState是漫游器状态基类，其他的类是描述S0到S8的9个状态类。据此设计，在中南大学数字矿山研究中心的地下矿三维可视化生产管控平台的基础上，实现一个井巷漫游器，利用该漫游器进行巷道漫游时的效果如图4所示。

表1  漫游器状态迁移表

Table 1  State transition table of roaming module

图3  漫游器类图

Fig. 3  Class diagram of roaming module

图4  漫游效果

Fig. 4  Roadway roaming

本文作者提出的漫游方式与传统漫游方式的优缺点可以从控制方式、漫游速度和灵活性和易用性等4个方面进行比较，如表2所示，可以看出本文提出的方式具备快速交互式漫游的特点。

表2  漫游方式比较

Table 2  Comparision of roaming mothods

5  结论

(1) 提出的基于全路径漫游网络的漫游方式操作简便，可在井巷网络内部快速漫游，且画面平滑。

(2) 基于有限状态机的漫游器实现方式使得软件结构清晰，便于编码、测试和维护，在实践中收到良好的效果。

参考文献：

[1] ZHOU Keping, GUO Mingming. Virtual reality simulation system for underground mining project[C]//Proceedings of 2009 4th International Conference Computer Science & Education. Piscataway: IEEE Press, 2009: 615-632.

[2] 熊书敏, 王李管, 黄俊歆, 等. 地下矿可视化生产管控系统参数化数据模型[J]. 中南大学学报: 自然科学版, 2012, 43(1): 272-277.

XIONG Shumin, WANG Liguan, HUANG Junxin, et al. Parametric data model for underground mine 3D visual production management and control system[J]. Journal of Central South University: Science and Technology, 2012, 43(1): 272-277.

[3] 李建忠, 陈鸿章, 隋刚, 等. 基于虚拟现实的综采工作面仿真系统研究[J]. 系统仿真学报, 2007, 19(18): 4164-4167.

LI Jianzhong, CHEN Hongzhang, SUI Gang, et al. Study on simulation system of fully mechanized mining face based on virtual reality[J]. Journal of System Simulation, 2007, 19(18): 4164-4167.

[4] 施发伍, 段宗银, 张良贵, 等. 基于VRML技术的虚拟现实矿山漫游[J]. 金属矿山, 2008(8): 78-81.

SHI Fawu,DUAN Zongyin,ZHANG Lianggui, et al. Realization of virtual mine cruise based on VRML technique[J]. Metal Mine, 2008(8): 78-81.

[5] 尚建嘎, 刘修国, 郑坤. 三维场景交互漫游的研究与实现[J]. 计算机工程, 2003, 29(2): 61-62.

SHANG Jianga, LIU Xiuguo, ZHENG Kun. Research and implementation of interactive Walkthrough in 3D scene[J]. Computer Engineering, 2003, 29(2): 61-62.

[6] 董晶晶, 夏青, 游雄, 等. 利用拾取技术实现虚拟场景漫游中的碰撞检测[J]. 测绘科学, 2009, 34(4): 74-76.

DONG Jingjing, XIA Qing, YOU Xiong, et al. Using pick method to realize the collision detection in virtual environment walkthrough[J]. Science of Surveying and Mapping, 2009, 34(4): 74-76.

[7] 章玉文, 戴青, 郭方达. 虚拟漫游环境中基于矢量的快速碰撞检测算法[J]. 计算机工程, 2011, 37(21): 270-272.

ZHANG Yuwen, DAI Qing, GUO Fangda. Fast collision detection algorithm based on vector in virtual roaming environment[J]. Computer Engineering, 2011, 37(21): 270-272.

[8] 邹益胜, 丁国富, 许明恒, 等. 实时碰撞检测算法综述[J]. 计算机应用研究, 2008, 25(1): 8-12.

ZOU Yisheng, DING Guofu, XU Mingheng, et al. Survey on real-time collision detection algorithms[J]. Application Research of Computers, 2008, 25(1): 8-12.

[9] 吴玲达, 赵健, 杨冰, 等. 一种虚拟场景的自动漫游方法[J]. 小型微型计算机系统, 2010, 31(8): 1563-1566.

WU Lingda, ZHAO Jian, YANG Bing, et al. Method for virtual scene automatic exploration[J]. Journal of Chinese Computer Systems, 2010, 31(8): 1563-1566.

[10] 史红兵, 张毅彬, 童若锋, 等. 虚拟场景自动漫游的路径规划算法[J]. 计算机辅助设计与图形学学报, 2006, 18(4): 592-597.

SHI Hongbing, ZHANG Yibin, TONG Ruofeng, et al. Path planning for automated navigation in virtual[J]. Journal of Computer-Aided Design & Computer Graphics, 2006, 18(4): 592-597.

[11] 续爱民, 金烨, 鲍劲松. 虚拟场景中自动漫游路径的多分辨率规划[J]. 系统仿真学报, 2005, 17(8): 1912-1915.

XU Aimin, JIN Ye, BAO Jinsong. Navigation path multi-resolution planning in virtual environment[J]. Journal of System Simulation, 2005, 17(8): 1912-1915.

[12] 徐小良, 汪乐宇, 周泓. 有限状态机的一种实现框架[J]. 工程设计学报, 2003, 10(5): 251-255.

XU Xiaoliang, WANG Leyu, ZHOU Hong. Implementation framework of finite state machines[J]. Journal of Engineering Design, 2003, 10(5): 251-255.

[13] Drumea A, Popescu C. Finite state machines and their applications in software for industrial control[C]//Electronics Technology: Meeting the Challenges of Electronics Technology Progress, 2004. 27th International Spring Seminar. Bankya, Bulgaria: IEEE, 2004: 25-29.

[14] 武楠, 房立金, 姜春英, 等. 基于有限状态机的空间对接仿真平台控制系统设计[J]. 机器人, 2007, 29(4): 378-383.

WU Nan, FANG Lijin, JIANG Chunying, et al. Control system design of a space docking simulation platform based on finite state machine[J]. Robot, 2007, 29(4): 378-383.

[15] Gamma E, Helm R, Johnson R, et al. Design patterns: Elements of reusable object-oriented software[M]. Boston: Addison Wesley, 1995: 338-348.

(编辑  邓履翔)

收稿日期：2012-06-04；修回日期：2012-09-05

基金项目：国家高技术研究发展计划“863”计划项目(2011AA060407)；湖南省研究生科研创新项目(CX2011B116)

通信作者：熊书敏(1976-)，男，湖北麻城人，博士研究生，工程师，从事数字矿山研究；电话：18071129095；E-mail：xsm_126@126.com