三维地图引擎中地形跟踪算法的实现

摘要：作为三维地图引擎中的重要一部分，地形跟踪算法起到了模拟各种不同地形与运动设备的作用。好的地形跟踪算法不仅可以实现水面、沙地、森林等在各种地形上行进的感受，还能模拟出船舶、车辆等各种不同载体的运动感受。在一款三维导航产品中，做好地形跟踪算法，对于用户体验的改善是相当大的。

关键词：三维地图引擎；地形跟踪算法；三维坐标变换

中图分类号：TP391文献标识码：A文章编号：1007-9599 (2012) 03-0000-02

3D Map Engine Terrain Following Algorithm

Xu Xinming

(Global Satellite Navigation Technology Co.,Ltd.(Shanghai),Shanghai200049,China)

Abstract:As an important part in the three-dimensional map engine,terrain following algorithm has played a role of simulation of a variety of different terrain and sports equipment.Good terrain tracking algorithm can not only achieve the feel of the water,sand,forest road in a variety of terrain,can simulate the movement of the various vessels,vehicles and other carrier feelings.In a three-dimensional navigation products,good terrain following algorithm to improve the user experience is considerable.

Keywords:Three-dimensional map of the engine;Terrain following algorithm;Three-dimensional coordinate transformation

一、引言

当前在许多导航类产品中地图引擎的使用已经很多见了，特别是随着近些年硬件技术的发展，加上许多三维的图形绘图软硬件库的支持，使得三维地图引擎的使用也变得比较常见了。对于一款好的产品，三维地图引擎中的地形跟踪算法是一个不可或缺的环节。

本文的目的是想介绍一种三维地形跟踪算法，以及在程序中的具体实现过程。使得人们对地形跟踪算法有深入了解，从而能够更好的掌握三维地图引擎开发的原理和本质。

二、地形跟踪算法分析与设计

（一）三维地形跟踪简介

在现实世界中我们每当观察一个物体时都会有视线的概念存在。我们所处不同的位置，向着不同的方向，看出去的物体景色都是不一样的。比如同是一座山，你在山脚下和坐在飞机上看出去的内容是不同的。所以地点的选择决定了眼中看到的事物。

所谓的地点，在三维的数字化世界中我们可以虚拟成一个坐标，一系列连续坐标的组合便形成了一条跟踪的轨迹，而这个过程也称为是三维地形跟踪的过程。

三维地形跟踪的方式有很多，我们通常用跟踪算法模拟出需要的地形跟踪方式。比如飞机、船只、汽车等等。不同的物理模型实现的地形跟踪算法也是不同的。比如同样是车，卡车和自行车所模拟出的感觉是不一样的；同样是船，快艇和油轮的行驶感觉也有区别。一套完善的物理模型在三维地形跟踪算法中很重要。

（二）三维地形跟踪算法的设计思路

在本文中我们想模拟出的是最基本的地形跟踪方式：贴着地形进行运动。只要不出现视线穿越物体的情况并且尽量贴近地形即可。我们采用山地地形，地形有一定的起伏，但幅度并不是很大。

我们使用相机来表示玩家的视点，相机前面是预先渲染好的地形。玩家驾驶的汽车必须在地表前进，不能穿越地面，因此需要计算相机所在的地形高度，并将视点相应的往上移。如下图：

图1 通用地形跟踪示意图

通常的做法是取当前位置所在单元格内的四个点的高度平均值作为相机的高度，也就有如下的公式：

高度=k*（V0+V1+V2+V3）/4

其中V0到V3代表单元格四个顶点的高度，k代表缩放系数。

乍一看这种方式还是比较理想的。但是细一想就会出现问题：我们所在的单元格其实是由两个三角形组成的，而由于地形的关系这两个三角形可能不是在一个平面上，四个点的高度值也可能相差较大。使用四点高度平均之后的高度值时，当我们从高度低的位置向一个高度比较大的位置移动时，会产生平均高度值小于当前位置的实际高度值的情况，也就会看到穿越地形的现象发生。这在现实中最常见的情况就是当我们从山脚下向一个很陡的山坡上行进时，由于高度的巨大差距造成了我们看到的景象一下子穿越了地形。

在实际的三维地形使用过程中，如果遇到了穿越地形现象的发生肯定是不能允许的。所以我们可以使用一种改进的方法加以改善。上面的算法是将相机所处单元格四点的高度取平均值，改进之后我们可以把单元格中的两个三角形各看成一个平面，因为组成三维地形图最基本的单元便是三角形，至于三角形如何划分可以遵循给出的数据内容。具体的操作流程可以这样：

1.判断相机位置处在单元格的哪个三角形中。

2.将相机所在的三角形组成一个新的矩形平面。

3.求相机所处点在该平面中的高度。

4.将该高度设为当前相机的高度。

其中的难点是如何求相机所在矩形平面的高度。

在三维坐标中，矩形四点的高度并不一致。也就是说矩形平面可能不平行于任意两个坐标轴组成的平面。我们可以先将相机坐标投影到矩形的两条直角边上，然后再求投影坐标的高度。求出两个值之后，我们选择其中较大的一个值作为当前相机点的高度值。平面图是这样的：

图2 地形三维坐标XZ平面投影

其中，V0V1V2V3’就是一个新的矩形平面。V0、V1、V2是单元格的三个顶点。V3’是配合矩形平面生成的一个新的顶点。P是当前相机的位置，而P1和P2是P点对于V0V1和V1V2两条线段的投影。计算出P1和P2两点的高度之后我们取较大的一个作为P点的高度即可。

那么我们如何求得P1和P2的高度哪？其实可以用简单的平面几何的方法解决这一问题。我们假设各点的三维坐标分别为V0(x0,y0,z0)，V1(x1,y1,z1)，V2(x2,y2,z2)，P(xp0,yp0,zp0)，以上都是已知的参数。P1和P2的坐标分别是P1(xp1,yp1,zp1)，P2(xp2,yp2,zp2)，其中xp1=xp0，zp2=zp0我们要求的便是yp1和yp2。对于Z轴的平面投影是这样的：

图3 地形三维坐标XY平面投影

由V0V1Q组成的三角形，我们要求的是P1的y坐标。这下简单了吧。所以可以得出公式：

P1R/V1Q = V0R/V0Q

根据已知参数可得： P1R=（（xp0x0）/（x1x0））*（y1y0）

由此可得： yp1=（（（xp0x0）/（x1x0））*（y1y0）+y0）

这样，一边投影的高度坐标就算出来了。同样的方法，我们可以算出P2的高度坐标yp2。由公式可以得到：

yp2=（（（zp0z1）/（z2z1））*（y2y1）+y1）

然后，比较yp1和yp2的值，取大的一个作为P的高度值yp0便可以了。当然，在求值的过程中还有一些细节问题需要我们注意。比如上面的公式都是在y0y2时情况是不一样的，但是思路是一样的。还有这种计算方式只适用于格网模式的高程数据，对于不规则三角形的高程数据(TIN)还需要进行进一步的处理。所以通过这一套运算我们便能求出当前相机的高度了。然后再配合一系列的投影变换，我们最简单的三维地形跟踪便算初步完成了。

三、地形跟踪算法实现效果

在具体源码的实现过程中，我们采用了OpenGL的三维图形库，使用VC++6.0作为开发平台。

程序实现之后的效果截图是这样的：

图4 地形跟踪算法实现效果图

四、结语

随着三维地图引擎技术在国内的迅猛发展，地图引擎市场逐渐成为一个新兴的增值亮点，掌握地形引擎跟踪算法的设计和开发技术将是广大开发人员的必修课，希望本文对三维地图引擎的跟踪算法软件设计构架和对应算法的研究能够起到一定的抛砖引玉的作用。

参考文献：

[1]Andre LaMothe.3D游戏编程大师技巧[M].李瑞祥,陈武.北京:人民邮电出版社

[2]徐青.地形三维可视化技术[M].北京:测绘出版社。

[3]廖朵朵,张华军.OpenGL三维图形程序设计[M].北京:星球地图出版社。

[4]OpenGL体系结构审核委员会,Dave shereiner,Mason Woo,Jackie Neider,Tom Davis.OpenGL编程指南（第四版）[M].邓郑祥.北京:人民邮电出版社