LOD技术和最短路径算法在交通三维地理信息系统中的应用研究

张训虎，章磊

（国家测绘产品质量检验测试中心，北京 100830）

1 引 言

可视化理论与技术用于地图学与GIS始于90年代初，GIS研究者开始把计算机图形学的理论和技术引入到空间数据可视化研究中，二维GIS的可视化技术目前已经基本成熟。

可视化是三维GIS的重要研究内容。主要集中在地形表面的重构、房屋建筑几何模型建立等方面，特别是在地形表达方面尤为突出。早期的多分辨率多采用基于TIN的层次结构三角剖分来生成。

近年来，随着对三维GIS需求的增加，国内外众多GIS软件公司投入研发。如ESRI公司的ArcView 3DAnalyst扩展、Intergarph公司的GeoMedia Terrain模块、吉奥公司的CCGIS等。它们的功能主要集中在地形和建筑的表达、属性查询、可视化观察、可视化分析、空间量算等方面。在小区域、适当数据量条件下具有较好的应用效果，但对于大范围、复杂环境及海量数据的逼真、实时可视化还显得不足。国内外有些学者着手研究大场景、多维度的三维地理信息虚拟现实研究，包括数据存储、数据显示，而LOD技术是众多研究中最为关键的技术之一。最短路径算法是三维地理信息网络分析的关键技术，在路径分析、选址分析、成本分析中都有广泛的应用。在交通信息系统中实现LOD技术和最短路径算法的结合应用是比较新的研究领域之一。

本文依据的软件平台是北京英特图原信息技术有限责任公司三维地理信息系统平台。具有大数据量空间信息处理能力、仿真效果、数据库驱动、跨平台通信、二次开发支持等方面的技术能力，可以提供较好的三维地理信息和虚拟现实解决方案。目前，已经在数字城市、数字社区、小城镇信息管理、城市综合管网管理、战场环境仿真等系统中得到了较为广泛的应用。

2 关键技术分析

LOD技术即Levels of Detail的简称，意为多细节层次。LOD技术指根据物体模型的结点在显示环境中所处的位置和重要度，在不影响画面视觉效果的条件下，通过逐级简化细节决定物体渲染的资源分配，减少场景的几何复杂性，从而提高绘制算法的效率获得高效率的渲染运算。

2.1 地形LOD技术

2.1.1 LOD技术

LOD技术是通过对场景的多尺度表达，达到数据减少与真实感减损之间的平衡［1］。它依据场景对象模型和视点的距离，选择合适尺度模型表示来进行绘制。如果模型离视点较远，且在屏幕空间的投影区域覆盖较少像素，则用尺度小（粗糙）的模型来进行表示；相反，模型离视点较近，则采用尺度大（精细）的模型来进行表达。

基于地图知识，设定不同比例尺下的模型是对真实对象的近似，比例尺越大，越接近真实对象。用函数S来表示近似，则S＝f（obj，d）。其中obj为真实对象，d为对象到视点距离。即是S为关于obj与d的函数。显然，S是距离d的连续减函数。

因为S只是一种对真实对象的近似，所以与真实对象之间存在着误差δ，用数学模型表示，则有：

其中，f（x）代表真实对象，y代表视点与对象的距离，视域变化范围为0～D。显然，δ越小，说明函数S表达下的模型比例尺越接近真实对象，差距越小，反之，则越大。

在实际计算过程中，需要将连续的S离散化。将视域变化范围划分为n段，如果距离视点处表示为di，（i＝0，1，…n），即每一段范围Δdi为：Δdi＝di－di－1（i＝1，2，…n）。在 Δdi上则有对应的Si，且有S0＞S1＞…＞Sn。即距离越远，相似程度越小。则有：

则误差函数δ转化为：

于是LOD问题就转化为求使得δ＝min的Si和Δdi。由于δ函数是一个广义上的泛函，求解是十分困难的。通常要结合具体的要求和条件来进行处理［2］。

2.1.2 基于地理特征的地形LOD

如上所述，LOD是对真实对象在不同比例尺上的近似。生成多分辨率的过程是一个简化和综合的过程。这种简化过程不是为了从初始模型中移去粗糙的部分，而是为了保留重要的视觉特征，其理想结果是一个初始模型的简化序列。因此选择简化算法是关键。

在地形多尺度模型生成方面，当前应用主要基于3种方法［3-4］：①Hoppe的“Progressive Meshes”法则；②Lindstrom的四叉树方法；③Duchaineau的ROAM（实时优化自适应网格）法则。

2.2 最短路径分析

最短路径问题在计算机中有着广泛的应用，例如网络通信中最短路由的选择，人工智能中搜索算法的研究等。

A＊算法［5］是到目前为止最快的一种计算最短路径的算法，但它一种“较优”算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛［6］。A＊算法结合了启发式方法和形式化方法。它通过一个估价函数（Heuristic Function）来估计图中的当前点到终点的距离（带权值），并由此决定它的搜索方向，当这条路径失败时，尝试其他路径。

f（n）是结点n从初始点到目标点的估价函数，g（n）是在状态空间中从初始结点到n结点的实际代价，h（n）是从n到目标结点最佳路径的估计代价。其中h（n）主导着A＊算法的表现方式。有以下几种情形：

（1）h（n）＝0：A＊算法这时等同Dijkstra算法，并且保证能找到最优路径；

（2）h（n）＜目前结点到终点的距离：A＊算法保证找到最优路径，h（n）越小，搜寻深度越深；

（3）h（n）＝目前结点到终点的距离：A＊算法仅会寻找最佳路径，并且能快速找到结果；

（4）h（n）＞ 目前结点到终点的距离：不保证能找到最优路径，但计算比较快；

（5）h（n）与g（n）高度相关：A＊ 演算法此时成为BFS（Best First Search）。

本模块取两结点间直线距离为估价值，即

这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，结点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

3 交通领域应用

本文主要探讨通过LOD技术实现三维地理信息及路网的生成和实时显示；利用最短路径算法确保车辆行驶最优路径的准确计算，实现车辆导航功能；利用模拟驾驶模块检测实时路况，计算车辆行驶状态，结合导航功能实现模拟驾驶，并将模拟驾驶路线在三维交通信息系统中显示出来。

3.1 三维路网生成

基于规则格网（GRID）的地形模型构造，结合最短路径算法并加入人工干预，设定三维路网中的道路、路口及道路周边建筑及附属设施的三维模型与显示（图1）。

图1 基于GRID技术的三维路网生成效果图

通过格网构建三维场景的方法，在实现场景时［7］，需要构建大量的格网，但是当构建大范围场景时，需要耗费大量的计算机资源。而在实际应用中，并不需要全部显示整体的三维场景，而是根据漫游的需要，仅仅显示部分场景。因此采用分批调用场景的技术，把整个场景分成不同的小场景块，根据漫游者视点的运动变化对这些场景块进行读取调用，保证漫游者的视点始终位于读取场景的中心。具体实现时，将漫游者视觉中心所在的场景块及周边相邻的场景块调入内存，再根据视线及视点来确定需要显示的区域，并进行显示。

要实现以上功能，首先对场景数据按照分块进行组织，采用规则格网对整个场景按照不同的层次结构进行组织、存储、管理。通过这种方式解决了数据调用中的分级管理，减少数据的访问量和调用量。采用结点树的方式组织数据，自上而下的对分块数据进行简化。

图2 四叉树结构表示的地形

如图2所示，将地形模型中的结点数指定为（2n＋1）2，并划分成不同的层次，使树中每一结点对应着由四块格网单元组成的面片。相邻的子场景，位于相邻的结点上。在结点树的叶结点上，包括最终小区域的纹理信息、颜色信息和位置信息等。这种方式每一个结点都表示一块地形，结点的层次不同，对应的地形面积不同，叶结点的层次最高。其次采用边删除、边插入以及布尔矩阵［8］方式解决因四叉树结构带来的相邻地块变化时引起的裂缝问题。

在调用的过程中通过考虑视距与地形的粗糙程度作为指标依据实现地形及各项信息的一并调用，并根据需要显示。三维路网生成功能的实现，为车辆导航可视化提供了技术支持和保障。

在数据库的支持下结合数据精度分级管理和空间索引技术，对三维场景数据进行动态组织、三维地形数据的动态简化，从而具备大区域大数据量空间信息的处理能力。系统开发过程中注重对开放数据格式的支持，能够支持大型的金字塔数据（32层）、融合不同精度的地形数据（图3）以及对地形进行自动平滑与动态平滑，突破了大数据量的空间信息处理瓶颈问题。

3.2 车辆导航

车辆导航功能是交通地理信息系统的主要功能之一。导航分为静态导航和动态实时导航。静态导航是通过输入出发地和目的地，系统结合A＊算法［9］自动计算出路径信息。系统实现过程中按照改进的A＊算法［10］，按照临时标记结点的估值函数：

其中，g（j）是从起点到标记结点的实际距离，h＊（j）是从标记结点到终点的最小距离，h＊（j－1）是从标记结点前一点到目标结点的最小距离，通过这种算法，减少结点的遍历个数，提高搜索速度，完成路径计算。然后通知车辆行驶前方应注意事件及抵达目的地的最佳路线和距离。动态导航是利用GPS实时或定时获取车辆的位置及三维姿态和行驶方向，并根据道路的实际情况，如道路施工、堵塞、走错路（车辆偏离原计算路径200m以上时）等，舍去施工、堵塞或原计算路线并计算出新的最短路径，在显示屏上进行刷新更正，确保导航功能连续、快速、便捷地实现。同时配合语音提示，使驾驶员耳、目并用，轻松驾驶。

车辆导航，实现了车辆在道路行驶中的位置、路线的准确计算与模拟，为模拟驾驶实现了系统保障。

3.3 模拟驾驶

基于LOD技术实现虚拟三维空间数据的管理和组织，可以便利地实现对现实交通路网的模拟，并在GIS系统中实现视觉特效，完成对真实路况的虚拟实现。模拟驾驶是用电子技术控制汽车进行的仿人驾驶。车辆的行使过程是一个复杂的变加速过程（包括速度的大小和方向），在车辆行使过程中需要考虑的因素很多，其中最主要的是车辆的动力学模型（包括车辆速度模型、方向控制模型［11］、制动力模型、阻力模型［12］），除以上模型之外，还需要一些其他相关技术的支持，如车辆调度系统、通讯系统和人机交互系统等。

采用LOD技术、动力学模型和汽车碰撞模型来实现的模拟驾驶，在设计过程中采用构建线性车辆模型，通过键盘、方向盘、手柄等进行车辆控制，调整视角、跟踪场景等方式实现对车辆的模拟驾驶。模拟过程中提供后视镜、鹰眼视图等。碰撞检测按照包围盒法实现。该方法用几何特征简单但体积略大的包围盒来描述复杂的几何对象，通过构造树状层次结构逼近模型，在遍历模型树的过程中，快速测试包围盒的相交情况，尽早排除不相交的元素，仅仅对包围盒的重叠部分元素进行进一步的相交测试，完成碰撞检测［13］，计算出行驶所需要的相关动力学参数。

模拟驾驶在实际操作上主要表现在加（减）速、并线、转弯等方面，实现上首先利用LOD技术，实现车辆所在道路的信息加载和显示，然后根据驾驶车辆的汽车碰撞模型检测路况并发出相关操作指令进行模拟，一定程度上可实现车辆的无人驾驶。

（1）加（减）速行驶，首先调整视角，利用LOD技术扩大道路信息显示范围，然后用碰撞检测技术判断车辆与周遍车辆、道路及道路附属设施的相交测试，依据碰撞检测得到的距离参数计算加（减）速度，调用速度模型，实现加油、加挡提速（或制动、减挡，减速度），并完成操作。

（2）车辆并线，首先利用LOD技术实现车辆左右车道的详细信息载入及显示，利用碰撞检测技术检测欲并车道及本车道的相交检测，计算出本车道安全距离，欲并车道的安全距离，然后根据动力学模型计算车辆并判断车辆可否并线及并线速度，若在安全阀值内可以实施操作，若不适合并线则等待并重新检测判定，直至完成并线操作。

（3）车辆转弯，根据导航模块系统提示，若需要转弯时，系统首先利用LOD技术调入相关道路信息，完成碰撞检测。判断车辆是否在转弯车道，计算车辆转弯半径和转弯速度，调用速度模型和方向控制模型，利用碰撞检测得到的参数，进行减速，控制转向灯指示转向，实施转向操作。

结合模拟驾驶功能，LOD技术和最短路径技术在交通部公路科学研究所的《基于虚拟现实的道路交通标志标线设计及评价系统》中的实现了相关功能及应用。

4 结束语

LOD技术和最短路径技术在交通三维地理信息系统中的应用，为解决三维建模、显示、可视化提供了技术支撑，基于此技术的GIS可以清晰直观地显示道路及其附属设施和周边环境。结合导航技术以及模拟驾驶技术实现智能车辆交通信息系统可以解决因驾驶员人为因素引起的道路交通安全问题；通过有效的缩短行车间距可以增加道路容量、提高道路的运行效率；可以在特殊情况下替代驾驶员，完成诸如有毒、抢险情况下的车辆安全通行问题。因此随着LOD技术和最短路径算法的不断改进和应用，能够为智能交通提供更为广阔的技术保证，从而方便生活。

［1]CLARK J.Hierarchical geometric models for visible surface algorithms［J］.Communications of the ACM，1976，19（10）：547－554.

［2]淮永建，郝重阳.基于LOD实时图形绘制和加速技术［J］.中国图像图形学报，2002，7A（1）：97－101.

［3]谭兵，徐青，周杨.大区域地形可视化技术的研究［J］.中国图像图形学报，2003，8A（5）：578－585.

［4]李志林，朱庆.数字高程模型［M］.武汉：武汉大学出版社，2001（7）：3－7.

［5]卢开澄，卢华明.图论及其应用（第二版）［M］.北京：清华大学出版社，1982.

［6]Tanenbaum A S.Computer networks［M］.3rd ed.Prentice Hall International，Inc，1998.

［7]陈磊.三维模拟车载导航系统的设计与实现［D］.成都：电子科技大学，学位论文，2010.

［8]雷军环，曾凡喜，吴名星.基于四叉树的视点相关LOD地形仿真算法研究［J］.制造业自动化，2010（08）：211－214＋228.

［9]白巧霞.基于eSuperMap的车辆导航系统的设计与实现［D］.西安：西北大学，2007.

［10]段莉琼，朱建军，王庆社，等.改进的最短路径搜索 A＊算法的高效实现［J］.海洋测绘，2004（05）：20－22.

［11]蔡忠法.章安元.汽车模拟驾驶模型与仿真的研究［J］.浙江大学学报（工学版），2002，36（3）：327－330.

［12]李安定，尹念东.汽车驾驶模拟器的运动模型研究［J］.黄石理工学院学报，2008，24（2）：26－30.

［13]申玉斌.虚拟环境中的碰撞检测技术的研究与应用［J］.交通与计算机，2005，23（1）：74－78.