嵌入式系统中地图快速漫游算法的实现

3 利用双缓存技术实现地图快速漫游  

3．1 双缓存技术实现地图平滑漫游的基本原理  

双缓存技术实现地图平滑漫游是在缓存法的基础上提出的一种为解决嵌入式系统下，使用遥控器连续移动地图，地图漫游速度慢或不连续的问题的新方法。双缓存的方法解决了缓存法实现地图漫游中遗留下来的问题：移动过程中的停顿问题。它的实现基础在于：即使是连续发送移动命令，在遥控器的两个命令脉冲之间，仍然存在一定的时间间隔，根据地图移动的方向趋势，利用命令脉冲之间的时间间隔进行数据组织和图像拷贝工作是双缓存法的实现依据。图2是遥控器连续移动命令脉冲的时序和单缓存实现地图移动过程的对应。

  
图１ 移动命令时序  

从上图我们可以看出：  

（1）两次连续的移动命令之间的时间至少为190ms, 实际显示图像在虚拟屏幕的范围之内时，图像的移动是显示缓存指针移动的过程，处理器在这段时间内空闲。  

（2）实际显示图像达到虚拟屏幕的边界时，如果连续接收到移动的命令，则只能在以新的显示中心重新组织虚拟屏幕上的地图并将虚拟屏幕上的图像拷贝到显示缓存之后，才能继续移动显示缓存的指针，在此过程中，起码有三个移动命令没有及时处理。  

从以上两点可以得出，在单缓存法实现地图移动的过程中，处理器的并不总处于忙状态，而是时忙时闲，因此如果将虚拟屏幕数据的组织和图像的拷贝工作平均分配到各个移动命令脉冲之间的处理器空闲时段，就能解决达到移动边界时，要长时间等待数据处理的问题。  

3．2 双缓存实现地图平滑移动的方法及实现  

利用双缓存技术实现地图平滑移动的内存空间分配图如下：  


图２ 双缓存实现地图平滑移动  

如上图所示，双缓存实现地图漫游的方法是：将显示缓存划分为两个和虚拟屏幕显示范围相同的缓存空间，我们称之为缓存A，和缓存B。定义预处理边界为范围小于虚拟屏幕范围的一个内边界。当显示屏幕的图像移动到预处理边界时，如果仍然接受到同一方向的连续移动命令，则开始在虚拟屏幕组织移动方向上的新图像，并拷贝该图像到缓存B；同时，在缓存A上，屏幕指针移动的过程仍在进行，当显示屏幕移动到缓存A的实际边界时，缓存B上已经准备好了显示方向上的新地图，此时将屏幕指针跳到缓存B相应位置的地址，就可以保证地图移动动作的连续性。  

双缓存法实现地图平滑移动的过程流程图描述如图4所示。  

  
图３双缓存法实现地图移动过程示意图  

在采用双缓存法实现地图的平滑漫游的处理过程中，预处理边界的选取是一个决定其效果的重要因素，预处理边界如果和实际边界离得太近，则预留的时间不足以完成所有的预处理任务，无法满足平滑移动的要求，而如果预处理边界范围太小，则使得预测方向可信度降低，有可能使预处理过程无效。该边界的选取和系统读写屏幕的速度以及遥控器的灵敏度都是相关的，选取方法同时和预测方向的算法也有一定的联系，因此仁者见仁智者见智，可以根据各自系统设计的不同进行选择。  

4 实验与结论  

笔者在开发嵌入式环境下车载导航系统的软件中使用了双缓存法实现地图漫游，在使用该方法之前，对开窗法、缓存法和双缓存法实现的地图移动的速度的进行了比较试验，表1是试验结果。该试验是在同一幅地图数据，同样的数据量下，移动同样的距离得出的：

表1几种漫游方法显示速度试验

移动距离（地图距离）  

2KM  

5KM  

开窗法  

11.3S  

25.5S  

缓存法  

4.6S  

9.9S  

双缓存法  

1.2S  

2.8S   

在我们的地图漫游软件采用了这种双缓存法来实现地图的平滑移动后，人们从视觉上几乎感觉不到地图移动的停顿，因此系统的整体性能得以提高。  

双缓存法是在嵌入式系统中实现地图平滑显示的一种实用方法，但用此法是以牺牲内存为代价提高地图的漫游速度，因此采用这种算法的系统必须有足够的内存（包括系统内存和显示缓存），预处理边界也需要根据系统要求科学选取。同时这个算法的实现代码也比前两种复杂，因此，大家可以根据自己系统的实际情况进行算法的选择。