基于VRML的虚拟城市导航系统的研究
摘 要：虽然虚拟现实技术最先是用于美国军方的，但是现在它已经应用于社会生活的各个方面。如CAD，医学，教育，城市规划，远程控制，游戏，娱乐等等。虚拟城市就是研究热点之一。虚拟城市可以帮助人们通过网络等媒介就可以了解一个城市。但是对于在虚拟城市中导航的研究并不多。所以本文提出了一个在基于VRML的虚拟城市中使用带有路径规划器导航的思想。
关键词：虚拟现实；虚拟城市；路径规划；导航
中图分类号：U675.73；TP391.9 文献标志码：A
Research of Navigation System for Virtual City base on VRML
WANG Wei, TONG Jia-ying, WANG Li-fen, CHEN Xiao-dan
(College of Computer and Information Management,Hei Longjiang Institute of
Science and Technology, Harbin 50027, China)
Abstract:Virtual Reality technology has been used in various fields of social life, such as medicine, education, city planning, long-distance control, games and amusement and so on. Virtual city is one of the pop studies. Virtual city can help people to know the city via network etc. But the study of navigation in the virtual city is less. So this paper proposes a model that the navigation uses the random roadmap path planning in virtual city base on VRML.
Key words:virtual reality; virtual city; path planning; navigation
虚拟现实技术(Virtual Reality简称ＶＲ)是20世纪80年代末兴起的一门崭新的综合性信息技术，它融合了数字图像处理、计算机图形学、多媒体技术、传感器技术等多个信息技术分支，大大推进了计算机技术的发展。它以模拟方式为使用者创造了一个实时反映实体对象变化与相互作用的三维图像世界，在视、听、触、嗅等感知行为的逼真体验中，使参与者可直接参与和探索虚拟对象所处环境的作用和变化，仿佛置身于现实世界中，产生多感知(multi-sensory)、沉浸感(immersive)、实时感(real-time)和交互感(interactive)。这正是虚拟现实的最突出的特征［1］。例如，当你进入了一个虚拟城市中，你就会像真的进入了这座城市一样，看到高楼林立，车辆穿行等等，如同身入其中。
在如今的信息化时代，人们通过网络已经可以足不出户就了解全世界。虚拟城市就可以让人们不必亲临城市就可以了解这座城市的格局建筑等，因为它是真实城市的映射。很多人已经开始了虚拟城市的工作［2-4］。 但是如果你想了解一个陌生的城市，想找到这个城市中的某个位置，你在这个城市中漫无目的地去寻找，可能会费很大的劲才能找到，可能没等找到就已经没有了耐心，这时如果有个导航系统帮助的话就不会有这样的烦恼了。所以本文提出了运用路径规划在虚拟城市中导航的思想。
1 VRML概述
1.1 VRML简介
虚拟现实建模语言VRML (Virtual Reality Modeling Language)是一种描述三维境界的语言，可以直接构造虚拟环境。通过VRML语言直接构造的三维物体具有代码简单、执行速度快等优点。可以直接用写字板编辑VRML文件，也可用一些支持VRML的编辑器编辑(如VrmlPad)编写VRML文件。它的应用平台是因特网、内部网和本地客户系统，与具体的设备(如:数据手套、数据衣)无关。VRML是一种ASCII码格式的文本文件，其文件长度有限，同样一个场景文件的长度远小于其它格式的文件，所以在网络带宽有限的条件下，它更加适合于在计算机网络上进行传播［5］。
1.2 利用支持VRML的开发工具构造虚拟环境
使用VRML编写复杂场景时较为繁琐，可以利用目前国际上较为流行的、能较好的为VRML提供可视化的工具来对复杂三维物体建模，从而可以大大提高了开发效率。目前支持VRML的工具有很多，而且它们大多提供可视化的操作，如3DS MAX、Maya、LightScape等。这些软件都可以导出*. wrl文件，与VRML之间都提供了格式转换接口，从而为几种工具结合起来使用提供了可能［6］。
1.3 VRML的交互功能
VRML提供用户与虚拟环境的交互功能，用户可以根据需要感知VRML场景、改变场景中的造型状态、触发一个事件或开始一段VRML动画。VRML提供了接触传感器、环境传感器、感知传感器及碰撞编组四类交互传感器来完成VRML中的交互工作。
由于某些复杂的虚拟环境及交互VRML本身不能实现，但VRML提供了Script节点用以实现脚本语句的编程以方便对事件的高层处理和动画的扩展控制。通过VRML提供的Script节点与JAVASCRIPT、JAVA进行数据通信，借助JAVASCRIPT、JAVA语言来实现对复杂动画和交互的设计与实现。其方法有以下几种：
1）Script→EventOut模式(间接的节点访问方式)。传感器通过路由到达Script节点，浏览器自动将到达的EventIn事件传送到Url字段所致的脚本程序中，同时，浏览器用一种方法将程序运行所返回的结果写入Script节点的EventOut字段，由EventOut发送事件通过路由将返回结果更新所控制的目标节点。
2）非Script→EventOut模式(直接的节点访问方式)。不需要在Script节点中设置EventOut，由路径显示的将Java程序数据传送到它想要产生影响的地方。首先要给出指向景中的目标的任意一个节点的指针，并且该指针类型SFNode类型还要被Script节点接受。这样，当场景中的事件传送到事件入口点时，由时间操纵类自动引导，Java程序便获得了读写SFNode指针所指节点类型的字段。
3）VRML类包。是与相应的浏览器插件捆绑在一起，其作用是提供用于VRML编程的Java类，主要包含VRMLVrml.node和Vrml.field，还有一个可以操纵浏览器状态的browser类。主要提供了EvenIn，Node接口和为每个VRML数据类型提供一个类扩展。Java程序之所以能够通过Script节点访问VRML场景是因为在Java的Vrml.node包中定义了一个Script类Script类是一个公共类，只要其他的对象可以看到这个类，就可以使用其中的变量、调用其中的方法；同时，它又是一个抽象类，只能供别的类继承，而自己不能直接产生对象。常常用到的是Initialize和ProcessEvent方法，Initialize方法用于脚本程序在第一次运行时初始化内部数据；ProcessEvent方法是脚本接收到一个事件时被调用，处理脚本程序获取的VRML场景数据并反馈给VRML场景。
4）利用VRML与Java编程技术扩展VRML节点(扩展VRML语言参数)。构成现实世界的宏观对象是复杂多变的。在计算机中构成的虚拟场景在精度要求不高的情况下VRML的原始节点就可以满足要求，可是在虚拟场景的精度较高时，VRML的原始节点就不能够体现现实世界的精度要求。为了达到不同的精度要求，需要利用VRML的原型节点PROTO与Java(JavaScript)编程技术，构造符合要求的复杂的体现现实世界中对象的新节点(扩展VRML节点接口)。
2 路径规划问题
路径规划问题是机器人学中很重要的一个方面，是机器人导航中最重要的任务之一。根据对环境信息掌握的程度不同将移动机器人路径规划分为2种类型，1个是基于环境先验完全信息的全局路径规划，另1个是基于传感器信息的局部路径规划［7-8］。
2.1 全局路径规划
全局路径规划是指根据先验环境模型找出从起始点到目标点的符合一定性能的可行或最优路径，包括环境建模和路径搜索策略2个子问题，其中局域路径规划按世界模型表达方法的不同存在3种比较典型的环境建模方法：构型空间法、自由空间法（free space approach）和栅格法（grids）等。
自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形构造自由空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划。
基于C空间的自由空间法的一般步骤是:1)建立C空间，构造自由空间； 2)确定单元的连通性，将自由空间表示为连通图；3)建立搜索树，确定搜索策略；4)进行路径优化。自由空间法的优势在于，构形空间能够用清晰了然，然后通过这些几何描述定义一些搜索方法。如果在已知的自由空间中存在避碰路径，那么这些搜索方法可以保证找到这样的路径，而且是最短路径，所以可以按其性能指标来搜索和优化路径，且具有完备解。另外，该法比较灵活，初始点和目标点的改变不会造成连通图的重构。
2.2 局部路径规划
局部路径规划的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。其主要方法有：人工势场法（artificial potential field)、遗传算法（genetic algorithm）和模糊逻辑算法（fuzzy logic algorithm）等。人工势场法是由Khatib提出的一种虚拟力法，其基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动，其中障碍物对机器人产生斥力，而目标点对机器人产生引力，引力和斥力的合力作为机器人的加速力来控制机器人的运动方向和计算机器人的位置。该法结构简单，便于低层的实时控制，在实时避障和平滑轨迹控制，得到了广泛应用。
2.3 随机路标规划器
一些为全局路径规划的实际算法都是基于在机器人构型空间的随机采样方法。
许多有效的规划器可以在一个合理的环境中用很短的时间计算出一条无碰撞的路径。他们可以分成两个主要的类别：单次查询方法和多次查询方法。单次查询方法不需要预测环境，只在运行阶段对环境进行简单的描述。多次查询方法在对构型空间进行预处理的时候可能要花费一些时间以便为以后的路径规划查询。多次查询规划器通常假设环境是不经常变化的，否则，每当环境改变，规划器都会重新进行一次预处理。
带有随机路标方法的路径规划器属于多次查询规划器方法。它包括两个阶段：预处理阶段和查询阶段。
在预处理阶段，规划器从虚拟环境中抽取集合信息，采样C-空间并为自由空间（无碰撞构型集合）建立一个连通图。规划器会在自由空间中的各个方向采集构型，采集足够的构型后，规划器会通过局部规划器用一个简单的路径计算连接附近的构型，从而形成一个自由空间的拓扑结构的连通图。
在查询阶段，给规划器一对构型（初始构型和目标构型，分别qi和qg来表示），规划器会找到一条连接它们的无碰撞路径。路标规划器会先试着将qi和qg分别与连通图中的其它节点连接，分别用qi’和qg’表示，并在图中找到一条连接qi’和qg’的路径。连接qi和qg的路径可以通过局部规划器建立。
2.4 带有随机路标规划器的虚拟城市中导航
虚拟城市的特点：道路固定，也就是环境静态。这样对于城市中的自由空间就很好确定，并且由于导航是在与路面这样一个二维平面上，不像机器人的空间是三维的，所以对于虚拟城市中自由空间的信息量相对会少些。基于这些特点选择基于自由空间的随即路标规划方法。可以多次查询任意两点之间的路径，而不必对空间进行重构。
在预处理阶段，规划器在自由空间（所有的道路）中采样路标。如果是有公交站台的道路，那么公交站点就作为路标，如果是没有公交站台的道路，规划器可以沿着道路每隔一段距离采样一个路标。连接两个相邻的路标。直到所有的道路都采集了路标，采样结束，并为查询阶段建立一个连通图。因为不是像机器人学中任意方向都进行采样，所以路标数量并不会很大。
在查询阶段，向规划器输入一个初始地址qi和一个目标地址qg，这些地址可以是建筑名也可以是道路名。然后规划器回在连通图中找到一条连接qi和qg的路径。
在本文中，我们提出一个将随机路标规划器用于虚拟城市导航系统中的思想。目的是让用户在虚拟城市中很容易找到一个指定位置。当然，用户也可以不沿着导航行走，自己自由行走，毕竟导航只是一个辅助工具。
3 结论
随着虚拟现实技术的发展，对虚拟城市的研究也越来越多，这就出现了在虚拟城市中的导航问题，本文介绍了机器人学中的导航方法，并提出将机器人中的基于自由空间的随机路标规划方法引用到虚拟城市导航系统的思想，由于VRML具有与JAVA语言通信的能力，所以可以将用JAVA语言编写的导航系统应用于基于VRML的虚拟城市中。但由于现在还处于研究阶段，以后在付诸实践的过程中可能会出现实际问题，有待进一步解决。
参考文献
［1］Maurizio Piaggio,Renato Zaccaria. Using roadmaps to classify regions of space for autonomous robot navigation［J］.Robotics andAutonomous Systems 1998,25:209-217.
［2］万 刚,陈 刚,游 雄.虚拟城市中地物几何建模技术的研究［J］.测绘学报,2002,(1):60-65.
［3］万剑华,潘正风,李清泉.基于VRML的虚拟城市的建立［J］.测绘通报.2002(5):17-19.
［4］段学军.虚拟城市:技术方案与应用［J］.测绘通报.2001(12):1-3.
［5］王汝传,姚旭敏,王海艳,刘 丽.基于Java和VRML虚拟场景通信方式的研究［J］.系统仿真学报,2003,15 (7):986-990.
［6］朱 凤,王汝传,王海艳,刘 丽.基于VRML室内虚拟环境构建的研究与实现［J］.南京邮电学院学报.2004(4):80-85.
［7］柏艺琴,贺怀清.移动机器人路径规划方法简介［J］.中国民航学院学报.2003,增刊:206-209.
［8］祝奎臣.基于几何和图像的机舱漫游场景建模技术［J］.船海工程,2006(3):62-65.