在海底地形数据组织好以后，接下来的问题就是如何依据可视范围的需求高效准确地加载必需的地形数据块、释放不需要的数据块，从而实现整个可视化系统运行过程中内存数据加载量的基本平衡，即所谓的数据动态调度。数据动态调度策略受到数据存储方式的制约，其效率将直接影响系统的I/O效率，从而最终影响场景绘制的效率。数据动态调度过程一般包括如下几个阶段：可视域相交测试、数据预加载、内存优化以及多线程加速等。

1.可视域相交测试

在大地形场景中漫游时，只有落在视锥体内部的地块才被绘制出来。因此，为了确定哪些数据块需要加入或释放，就必须实时测试哪些数据块落在视锥体内部。在计算机图形学中，观察者所能看到的可视域通常被定义成一个跟随观察者的六面视锥体，如图10-12所示。当观察者的位置移动或改变视线方向时，每一帧都需要计算与观察者视锥体相交的地形子块，同时根据上一帧已载入内存的地形子块，判断本帧需要新载入或者载出哪些地形子块数据。

图10-12　视锥体及投影

视锥体与地形子块之间精确相交测试是一个复杂而又耗时的过程。为了简化计算，提高计算效率，通常采用的策略是将视锥体和地形子块向二维平面进行投影，在二维平面内进行二维图形的相交测试。在观察者漫游地形场景时，视线方向可以任意变化，那么视锥体的空间姿态将是任意的，所以视锥体投向水平面的投影形状也就会有很大差别。

2.数据预存取

在地形场景漫游过程中，需要绘制的每一帧都要根据当前观察者的视域范围的变化，通过加载或卸载过程更新视域内的地形子块。由于CPU读取内存中数据的速度要比读取外存中数据的速度快得多，若视域更新时直接从外存来读取地形块来加载数据，必然导致CPU或GPU长时间等待数据的状态，影响地形场景的刷新速度。因此，在数据调度策略中，一般需要利用缓冲区机制进行数据的预存取。预存取原理就是在观察者视域外定义一个稍大的区域，从外存中除了读取视域范围内当前帧要绘制的数据块，还要预先读取视域周边的一些地形子块到内存缓存中。当视点位置移动需要更新数据时，不需要直接从外存读取需要更新的地形子块，直接从内存中读取即可，从而加快绘制效率。

如图10-13所示，矩形单元表示分割的地块，三角形代表视锥体在二维平面的投影，实边三角形代表当前视域范围，虚边三角形代表上一帧的视域范围。若不使用数据预取策略（图10-13（a）），观察三角形位置发生移动时需要实时从硬盘读取加载一个地形子块数据，同时卸载两块地形数据，这个实时加载地形子块的过程就是每一帧造成CPU等待的原因。当采用矩形预取策略后（图10-13（b）），当前帧可视范围内的所有地形子块已经全部在上一帧预取完成，不需要实时加载数据，这将显著提高当前帧的绘制效率，提高系统的刷新率。除了矩形预取区域外，预取策略中常用的还有圆形、三角形及其他自定形状等。由于预取区域范围越大，预加载的地形子块数量就越多，内存的占用与加载时间也会相应增加。因此，预取区域的形状、范围都将直接影响数据调度的时间，综合考虑实时加载和数据预取之间的效率问题，并找到两者之间的平衡点才能更好地提升整个调度策略的性能。这里以九宫格缓冲区预处理方法为例来进行详细说明数据动态预存取原理（图10-14）。

图10-13　数据预存取原理（赵庆，2009）

所谓九宫格，就是把地形块分割为方形格网子块，在判断内存中需要预加载的数据块时遵循如下原则：①当视域三角形完全落入一个地形单元时，那么在内存中需要加载的数据应该包含该地形单元以及该单元对应的八个相邻地形单元（图10-14（a））；②当视域三角形与多个地形单元相交时，则需要将每个地形单元都依照原则①进行加载数据，并注意防止重叠区域地形单元的重复加载。图10-14（b）显示了当视域三角形与四个地形格网单元相交时，需要预加载的地形单元区域。(www.daowen.com)

图10-14　基于九宫格算法的缓冲区预处理策略（赵庆，2009）

通过上述原则，该地形调度策略可以提前把下一步可能要处理的地形块读入缓存，能够确保不管视点向哪个方向进行移动，下一帧所要绘制的地形块都在系统缓存中，从而大大减少卡帧现象。在实际漫游过程中，当视点位置发生移动，视域三角形覆盖的地形块发生变化时，系统就需要在缓冲区中动态加载或卸载地形块。在图10-14（c）所示的视域三角形移动情况下，需要实时添加七个地形块，卸载七个地形块。九宫格策略能够完全覆盖要显示的区域，并且无论视点位置朝哪个方向移动，该处理方法都能保证缓存中存在下个要显示的地形块。

3.多线程加速

多线程是指操作系统支持一个进程中执行多个线程的能力。在某些多任务软件开发时常采用多线程技术，即整个软件进程包含了完成不同功能的多个线程，如数据采集、预处理线程、实时数据显示线程、图形曲线生成线程和用户界面线程等。这样多个线程同时执行，在一段时间内并行完成了更多任务，加快了系统的反应速度，提高了执行效率。

这里要注意区分两个近似的概念：线程和进程。进程常被定义为应用程序的运行实例。线程是指进程内部的可独立执行的单元，是操作系统对系统资源的基本调度单位。每个进程至少拥有一个线程，这个线程也被称为主线程。一个进程也可以拥有多个线程，同属于一个进程的所有线程都共享进程的虚拟地址空间，线程之间可以共享进程的全部数据和资源。

在地形实时绘制过程中，程序既要根据视点等信息对需要或者可能需要参与绘制的地形数据进行调度，同时还要执行具体的绘制操作。为了提升整个地形绘制过程的持续性和效率，通常引入多线程技术在程序中同时运行两个线程：主线程负责地形实时绘制，子线程负责数据调度。具体思路是：首先开辟一个线程池，主线程主要负责可视空间的计算，对需要执行调度的地形块编码的确定，渲染队列的更新以及地形场景的绘制工作；子线程主要负责从外存中调入缺少的地形块数据（图10-15）。

程序首先从主线程开始执行，然后依次执行以下步骤：①获取视点位置，计算当前视锥体范围；②计算可视区域内的地形块和对应的细节层次，将这些地形块的编码加入渲染链表，同时更新预调度地形块链表；③遍历渲染链表，对可视区域内的地形块进行绘制，同时开辟一个子线程进行数据调度更新预调度链表；④判断是否退出程序，若不退出程序则判断是否有视点位置移动，否则退出程序，算法结束。子线程则要根据缓冲池来对子块进行数据加载，当所有子块的数据都加载完成时，子线程的任务结束（曾杰，2012）。主线程将整个场景绘制出来，当前帧的任务结束，进入下一帧。

图10-15　多线程数据调度策略流程图