室内外无缝导航定位移动三维客户端设计

李 赟，李 冻，左志权，刘正军，毕京学,3

(1.中国测绘科学研究院，北京 100830；2.兰州交通大学，兰州 730070；3.山东科技大学，山东 青岛 266590)

1 引言

随着社会的快速发展和信息时代的到来，移动定位导航应用服务正逐渐影响人们的日常生活。网络地理信息系统(web geographic information system，WebGIS)的广泛应用以及移动智能终端的普及，使得人们在陌生环境中寻找特定的地点或目标时，利用定位导航服务可以用最短的时间达到目的地[1]。室外环境中的导航技术近年来发展较快，截至目前已经形成了较为成熟的商业体系，比如室外车载导航系统、手机导航系统等[2]。室外环境下的定位导航系统主要采用全球定位系统(global positioning system，GPS)卫星信号或蜂窝信号来进行定位，将GPS和电子地图配合使用，并结合相关的导航软件，在电子地图上显示实时位置及路线信息，完成导航服务[3]。室内环境下的定位导航研究主要集中在以下两类[4-5]：一是研发室内定位系统，比较突出的研究包括室内感知系统、上下文感知环境等；二是用移动机器人控制和实现导航服务，这种类型注重系统硬件的实现，对导航系统本身关注不多。

目前广泛采用的导航地图都是二维的，随着移动终端设备计算能力的突飞猛进，使得在移动端进行高效的三维渲染成为可能[6]。虚拟现实技术近年来在计算机领域也引起了广泛的关注。它能够利用计算机生成较为真实的模拟环境，使用户沉浸在虚拟环境中，同时通过人机交互接口，实现用户与虚拟环境的直接交互[7]。

Unity3D作为一种三维虚拟现实游戏平台，对DirectX和OpenGL拥有高度优化的图形渲染管道，支持常见的文件格式，并能和大部分相关应用程序协同工作，可以充分、实时的处理大量的三维模型[8]。值得关注的是，Unity3D是一个跨平台性非常好的三维引擎，从桌面系统到移动平台和游戏主机，几乎涵盖了所有平台。利用Unity3D进行三维应用程序的开发，便可以实现“开发一次，多处使用”的理想目标。因此，本文在系统实现中选用Unity3D作为开发工具。

随着网络带宽和移动终端性能的大幅提升，云技术和移动网络技术的快速普及，以及大型建筑内部导航和定位的需求与日俱增，基于三维的导航定位服务应运而生。合理整合现有的各种硬件资源，软件资源和信息资源，设计一套满足当前应用环境下的系统成为本文以及今后继续研究的重点。

2 客户端设计框架

2.1 客户端需求分析

移动客户端程序是运行在移动终端设备(如智能手机)上的应用程序，是用户与室内外导航定位系统进行交互的唯一接口。良好的导航定位移动客户端程序需要具备以下要素：

(1)提供良好的交互界面方便用户使用；

(2)与后台位置服务通信，实时获取用户位置数据；

(3)管理和调度本地或远程服务器上的三维模型数据，优化三维场景渲染，使客户端程序在移动终端设备上能同时满足流畅、美观和低能耗的要求；

(4)具备三维场景中路径规划的能力，能满足用户在室内外进行定位、导航的需求。

2.2 客户端的组成模块

本文根据室内外导航定位系统的功能需求，采用模块化设计方法，将移动客户端应用程序分解为四大组成模块，分别是：客户端用户接口、导航与空间查询模块、定位模块和三维模型调度模块(见图1)。

图1 客户端结构框图

2.2.1 客户端用户接口

用户接口(user interface，UI)是为人机交互提供帮助的功能集合。作为运行在移动终端上的定位导航系统，UI主要应为用户提供基于触摸屏的常用手势操作，定位与空间查询、路径规划等功能。在三维场景浏览方式方面，可以提供两种不同的视角，即第一人称视角(见图2(a))和鸟瞰视角(第三人称视角，见图2(b))。两种视角用于不同场合，第一人称视角适合作为导航视角，为用户带来“沉浸式”导航体验；鸟瞰视角用于大面积场景浏览，查看生成路径的全貌等。另外，第一人称视角也更适合于室内导航的应用。

图2 客户端程序的两种视角

2.2.2 导航与空间查询模块

导航与空间查询模块负责处理用户的输入，通过位置服务模块获取用户位置，然后利用空间数据库和空间数据服务器进行查询和计算最优化路径，并将结果作为导航路径可视化和三维数据调度模块的依据。

2.2.3 定位模块

定位模块包含室内定位和室外定位两个组成部分。其中室外定位主要依靠GPS卫星或蜂窝数据、位置服务器和移动终端操作系统提供的定位应用程序接口(application programming interface，API)来实现。室内定位利用室内场景中布设的无线保真(wireless fidelity，WiFi)热点和预先采集的WiFi指纹库，采用指纹库匹配和内插技术得到室内位置信息。难点在于定位方式是室内还是室外的判别，因此需要设计一个智能化的判别器来判别当前的定位方式。判别器的判别结果将作为导航模块，三维模型调度模块的输入。

2.2.4 三维模型调度模块

三维模型调度模块作为可视化的核心需要精心的设计[6，9-12]。衡量三维应用程序性能的一个重要指标是帧率(每秒钟生成的画面数)，需要绘制的数据量越大，消耗的时间也越多。对于复杂场景的三维模型，通常包含大量数据，如果将数据全部加载，即使有足够的内存容纳它们，也没有办法流畅的绘制画面[9]。精细模型的真实感渲染可以给人带来愉悦的视觉享受，但提高渲染画面效果的同时给硬件系统带来了过量的计算负荷，使得渲染达到满足交互需要的帧率成为奢望。因此，需要对模型数据进行合理的组织，创建空间索引[10]，利用相机位置和视椎体对模型数据进行视椎体裁剪、遮挡剔除和细节层次模型(level of detail，LOD)[13]等技术的调度，合理的控制内存中的数据量和送入图形处理单元(graphic processing unit，GPU)渲染的数据量。该模块接收位置模块和导航模块的输出结果以及用户的操作，控制相机的运动。

3 关键技术

3.1 室内模型组织和管理

室内模型主要分为两类，一类是建筑物本身，另一类是其附属物。具体分类原则为：将楼体建筑物(包括楼板、框架、外墙、楼梯)作为建筑物模型；剩余的都属于附属物(如商场建筑物中的单个小商铺、卫生间、服务台、仓库等等，以及它们的分隔物如内墙、隔板等)。模型采用面向对象的方法管理和调度，每个单独的物体都作为单一模型，保存为单独的模型文件，它们同时具有3种以上不同分辨率。

用大型商场的室内模型来举例，模型文件的目录按图3所示的层级结构组织。

图3 楼层及附属物模型示意图

模型的存放位置应符合以上层级结构，如：整个建筑的外框模型应存放在“建筑名称或编号”文件夹中，每个楼层的整体建筑模型应放在“楼层编号i”(i表示楼层数)文件夹中，楼层的附属物包括商铺、电梯(楼梯)、洗手间、服务台、仓库等每一个存放在一个单独的“商铺编号i”文件夹中，该文件夹中只存放某一个楼层附属设施不同分辨率的模型文件。纹理文件放在对应模型所在文件夹中，单独存放在名为“Texture”的文件夹中。

全部商铺信息汇总为一个文件(.xls 或 .txt)，该文件存放在“建筑名称或编号”文件夹中。每一条商铺记录包括：建筑编号、楼层编号、商铺编号、商铺属性(包括商铺名称，在该建筑局部坐标系中的起始坐标，分类，如：餐饮、服装、家居、楼梯、服务台、洗手间等，商铺属性分类后续再做详细分类)。

在Unity3D中将每一个模型文件单独打包成Asset Bundle文件(一种Unity3D支持的可在本地或远程动态加载的文件格式)，将打包后的文件按原来的层级保存在数据模型服务器上供远程下载。

这样的模型组织方式便于调度和管理，程序只需读取模型的属性信息，然后生成空间索引用于调度。

3.2 室内环境下三维路径的生成

二维地图上采用基于图论的最短路径算法生成需要查找的路径。将地图上的关键点作为节点，根据地图上点的连通性将相应的节点连接成边，并辅以权值就形成了二维问题的图。

室内导航有个明显的特征，即在某个楼层内的导航问题仍属于二维问题。如果将相邻楼层通过某种途径连接就能够使得楼层之间的图连通，而楼层之间的物理连接楼梯或电梯刚好提供了这样的途径。因此，将楼梯和电梯作为节点加入图中就可以构造整个建筑室内环境的三维图，然后采用传统的最短路生成算法即可生成室内环境下的三维路径[14]。

3.3 基于四叉树的室外模型调度

每一个区域的室外模型都有一个属性描述文件，该文件记录了每个建筑模型的ID，参考点坐标，包围盒等信息。读取该文件可以构建一颗四叉树：①将所有模型的参考点作为点群，计算该点群在x-z平面(Unity3D中y轴向上)的包围盒；②将得到的包围盒各边向外扩展距离d，该距离可以取包围盒边长平均值的0.1倍，得到一个包含所有点的矩形区域；③将该矩形作为根节点，设四叉树节点能保存点数的最大值为N，设根节点为当前节点。比较当前节点包围盒中的点数n0与N的大小，若n0>N，则将当前节点进行四叉剖分，再将每个子节点作为当前节点重复步骤③；④经过几步递归后，全部叶子节点的包围盒中点数都小于N，得到一颗四叉树。

四叉树的节点中应保存位于该节点中的建筑模型文件路径，模型ID，叶子节点包含节点包围盒。节点包围盒指包含节点内所有建筑模型的最小包围立方体。

模型调度过程是在每一次画面更新前，判断相机视椎体和四叉树叶子节点包围盒的拓扑关系，若包围盒与视椎体相交或位于视椎体内部，则从缓存池读取该节点所包含的全部建筑模型，将它们添加到要渲染的模型数组中；否则若该节点包含的模型在渲染模型数组中，则将他们从数组中删除。

4 结束语

本文提出了室内外无缝定位与导航的移动客户端设计思路，详细探讨了移动客户端的实现框架、功能模块，阐述了设计过程中的关键技术并且提供了可行的解决思路。城市空间信息化，无线网络和移动智能终端日益普及，基于位置服务和室内外定位信息可视化由二维转向三维，在这样的背景下，逐步实现和丰富模块功能是今后的研究重点。室内外无缝定位中的内、外环境的识别与切换是难点，也是今后系统设计中要解决的主要问题。

[1] 干建松.基于Unity3d的室内漫游仿真系统[J].淮阴师范学院学报：自然科学版，2011，10(6)：515-518.

[2] 李德仁，刘强，朱庆.数码城市GIS中建筑物室外与室内三维一体化表示与漫游[J].武汉大学学报：信息科学版，2003，25(3)：253-258.

[3] 李慧.室内外融合导航系统的设计与实现[D].北京：北京邮电大学，2011.

[4] 张红平.楼宇三维寻径分析研究[D].南京：南京师范大学，2011.

[5] 杜建庚.楼宇三维路径的生成、规划及表达[D].北京：北京交通大学，2008.

[6] 闫金金，尚建嘎，余芳文，等.一种面向室内定位的3D建筑模型构建方法[J].计算机应用与软件，2013，30(10)：16-20.

[7] 卞锋，江漫清，桑永英.虚拟现实及其应用进展[J].计算机仿真，2007(6)：1-4+12.

[8] 龙艳军，俞佳曦.Unity3D游戏开发中的版本控制研究[J].软件导刊，2012，11(11)：12-14.

[9] 杨卫军.海量三维城市模型的调度与场景管理[D].武汉：武汉大学，2005.

[10] 傅由甲.动态八叉树在复杂场景设计中的应用[J].系统仿真学报，2006，18(S2)：408-410.

[11] 唐桂文，张庆娟，王功明，等.基于三维GIS的海量地形数据存储和调度的研究[J].测绘科学，2008，33(3)：110-112+120.

[12] 王冬，王晓华.三维GIS中海量模型调度与存储[J].地理空间信息，2012，10(1)：109-111+4.

[13] HOLLIMAN N.Review of "Level of Detail for 3D Graphics" by David Luebke，Martin Reddy，Jonathan D.Cohen，Amitabh Varshney，Benjamin Watson，and Robert Heubner.Morgan Kaufmann[J].Presence：Teleoperators and Virtual Environments，2003，12(4)：441-442.

[14] 艾海舟，张钱.移动机器人路径规划算法的实验研究[C]//第一届人工智能联合会学术会议论文集.长春：吉林大学出版社，1990：400-405.