面向大规模动态地形可视化的LOD组织与调度技术

高 勇，刘 家 骏，郭 潇，邬 伦

(北京大学遥感与地理信息系统研究所，北京 100871)

面向大规模动态地形可视化的LOD组织与调度技术

高 勇，刘 家 骏，郭 潇，邬 伦

(北京大学遥感与地理信息系统研究所，北京 100871)

地貌演化等地表过程的分析模拟实时产生系列地形数据，该动态过程的可视化对性能要求较高，传统基于预处理的方法计算量大、绘制延迟明显。面向大规模动态地形可视化，提出一种LOD预处理与实时更新相结合的混合调度技术，基于场景图对动态地形LOD建模与组织，建立多线程模型实现地形瓦片的动态更新和绘制。对于每次迭代计算产生的新地形，该方法以LOD瓦片的动态调度替代传统的静态预处理方法，与地表过程计算同步更新瓦片，且仅重新计算和渲染当前视域和分辨率下地形发生变化的局部瓦片，通过LOD的局部动态更新避免可视化数据的全局重新生成，显著降低过程模型计算和结果更新对渲染过程的影响，提高整体的可视化性能。

地形可视化;细节层次模型;场景图;多线程;动态调度

0 引言

地形可视化是三维地理信息系统的基础，是地形分析应用中重要的技术环节,而在诸如地貌演化、水土流失等地表过程分析和模拟中，更是对地形可视化产生了新的需求。这类基于过程的地形数值分析和模拟，表现为地形因子，特别是高程h随时间t的动态变化过程[1]，即h=f(t)或Δh=f(Δt)。将该过程通过三维可视化的方法实时动态展现出来，可以更直观有效地探查、分析和检验地形演变过程的规律和特征，特别是在大规模地形分析中尤为如此。

当前大规模地形的三维可视化技术，主要以细节层次模型(Level of Detail，LOD)为基础[2,3]，以到观察点的距离评价地形块的重要程度，距离观察点较远则以粗糙模型显示，反之则显示精细模型。在实现中，首先通过LOD算法从原始的地形数据生成地形模型，然后在可视化中调用生成的模型完成显示。其中比较有代表性的算法有ROAM算法[4]、限制性四叉树算法[5]、Chunked LOD算法[6]等。从原始地形到地形模型，需要一个处理过程，这个过程不能在一帧的时间内完成。因此，大规模地形可视化所用的地形模型，通常通过预处理生成。

从地形可视化到面向过程的动态地形可视化，其技术挑战主要来自于LOD生成。预处理生成的LOD模型是静态的，且生成效率通常较低，尽管目前已经提出了一些LOD动态调度[6,7]、基于GPU的并行模型生成[8-11]等加速技术，但这些方法仍然是先整体预处理再渲染的两阶段过程。而地貌演化等地表过程是高程随时间变化的函数，其最大的特点是随时间演替不断生成新的地形数据，即本文所称的动态地形。当前的可视化方法对每次产生的新地形数据都要重新进行预处理并重新构建LOD，然后交给渲染过程，才能显示新地形的变化。但由于在大数据量下预处理耗时长，很难在地表过程的一个时间步长内完成，这就必然会导致地形实时可视化的停顿、更新不及时等性能问题，难以满足动态地形流畅漫游的需求。因此，对于动态地形，需要结合可视化过程实时生成LOD模型，当前已提出了一些局部地形的实时生成和更新方法，用以支持交互式地形编辑和渲染[1]，如结合体素的混合地形表达[12]、基于时空立方体的地形变形可视化[13]等，但这些方法主要面向局部地形更新，还不能很好处理诸如地貌过程模拟等大规模全局动态地形的可视化。

因此，本文提出一种LOD预处理与实时生成更新相结合的混合调度技术，提高动态地形过程的可视化性能。先通过预处理生成基础的地形模型数据，保证可视化时存在可调用的地形模型。在地形过程计算中，对于新产生的地形数据，根据视点特征，动态查找需要更新的LOD瓦片，实时生成局部的新的地形模型，并完成该局部地形的动态绘制。该方法避免了全局地形模型的重新生成，而只进行少量的局部的必要更新，可以较好地解决大规模动态地形可视化的性能问题。

1 LOD混合调度技术

结合预处理与实时生成更新方法进行LOD的混合调度，在完成地表过程动态计算的同时，实现动态地形的实时可视化和流畅漫游。具体的，先通过传统的预处理过程生成基础的地形瓦片，之后的可视化过程与地表过程计算实时结合，地表过程模型在原始地形数据的基础上不断迭代产生新的地形数据，而在同步的地形可视化漫游中，首先采用与静态模型相同的方法加载预处理生成的地形瓦片，同时动态判断在当前视域和分辨率下新动态地形导致变化的瓦片，系统根据变化后的新地形，实时的为需要更新的地形生成新的瓦片，并替代之前的瓦片进行渲染。在该过程中，仅重新计算和渲染当前视域和LOD层次上受新地形影响的局部瓦片，避免了全局的、所有层次上的瓦片更新，因而可以大幅度降低因数据准备而导致的渲染延迟。

LOD技术控制了同屏渲染的三角形的数量，也使得屏幕中同时出现的地形瓦片不会特别多，即使在大范围漫游的情况下，实际更新的瓦片数量也不会很大。因此，新地形模型的生成并不会消耗太多时间，瓦片更新的延迟也不会很大，而且没有变化的部分仍以基础瓦片显示而无需计算，因此完全可以满足动态地形的可视化需求。

该LOD混合调度技术的实现分为3个步骤：1)动态地形的计算。读取当前地形，应用过程模型Δh=f(Δt)，迭代计算经过一定时间步长后的新地形。这部分工作比较常规，单纯使用原始的地形数据即可完成，不涉及可视化部分。2)瓦片的生成以及可视化前的准备工作。经过过程计算后的新地形，要先更新LOD瓦片才能实施渲染，这可以看作可视化前的准备。准备工作包括但不限于：动态判定并实时生成受新地形影响而需更新的瓦片，从原始数据提取未受影响的瓦片、提前对显示列表进行编译、对纹理作提前编译等。3)可视化。将准备好的数据加入渲染流程。

要实现流畅的可视化效果，一帧的渲染需要在至少1/24 s内完成，而上述3个步骤不可能在一帧之内完成。因此本文使用多线程技术，将LOD实时生成的第1步和第2步在其他线程完成，只有第3步才在渲染线程中完成。具体的，本文的调度技术涉及3个线程：计算线程、渲染准备线程(简称“准备线程”)、渲染线程；3组数据：地形数据、渲染准备任务列表(简称“任务列表”)、渲染准备结果列表(简称“结果列表”)。3个线程与3组数据之间的基本调度关系如图1所示。

图1 动态地形可视化的多线程模型

Fig.1 Multithread model for dynamic terrain visualization

每个线程的具体工作如下：1)计算线程完成第1步动态地形的迭代计算，并负责写入新产生的地形数据。2)渲染线程完成第3步可视化的工作，并负责写入任务列表和读取结果列表。渲染线程在每次渲染中检查是否存在新的地形，当计算线程完成一次迭代计算并生成新的地形后，渲染线程会检测到地形发生了变化，进而根据当前视域和分辨率判断需要更新的瓦片，并生成渲染准备任务，并放入任务列表。渲染线程还将查看提交的任务是否完成，如果任务被处理完，在结果列表就有了新的地形瓦片，渲染线程将用新的瓦片替代原有的瓦片完成渲染工作。这两项工作通过拣选回调和更新回调完成。3)准备线程完成第2步的瓦片生成和准备工作，负责读取地形数据以及任务列表，实时生成需要更新的局部瓦片，并将结果写入结果列表。准备线程会不断地查询任务列表，当任务列表中有待完成的任务时，就取出任务，并将任务生成的新瓦片放入结果列表。

该动态地形可视化的LOD混合调度技术的具体实现细节将在下文详述。

2 基于场景图的LOD组织管理

2.1 动态地形LOD的场景图模型

在动态地形可视化的混合调度技术中，地形LOD基于场景图进行组织管理。场景图是用于组织场景信息的图或树结构。一棵场景树包含一个根节点、多级内部的组节点、多个末端的叶子节点，其中叶子节点记录几何体信息，主要是地形瓦片数据。通过修改组节点上的变换函数，可直接作用于子节点，而无需重复更改子节点的属性，因此可以极大简化修改操作，有利于大规模场景的变换和管理。

为了支持动态地形，将其LOD场景图组织为四叉树结构，如图2所示(以3层为例)。其中LOD节点用于组织外存数据，如果其下一层模型的子节点多于1个(最多4个)，则用一个组节点组织在一起。与传统场景图最大的不同是，该模型扩展了自定义的动态瓦片节点代替原有的几何体节点，负责管理动态地形的LOD瓦片的信息，包括该节点所对应的地形瓦片的地理范围、分辨率等参数，以及上次可视化时的帧数、上次可视化时所用数据的地形迭代计算计数、是否需要更新等过程状态，还需记录地形数据和准备数据的指针等。这部分新增的节点信息用于可视化过程中动态判断该节点瓦片是否需要更新。同时，在动态瓦片节点上添加更新回调和拣选回调，负责响应线程模型的调度，具体完成对应节点在必要条件下的瓦片更新工作。瓦片更新的判断和重新生成工作都在单个节点上完成，可以有效保证其局部性，并且基于场景图的结构，可以实时的适应并匹配当前的视域和分辨率。

图2 动态地形LOD的场景图组织

Fig.2 Scene graph model for dynamic terrain LOD

2.2 更新瓦片的选择

为了实现局部地形模型的实时生成和更新，需要根据视点特征，动态查找需要可视化的地形瓦片，仅仅更新该瓦片的地形模型数据。

依据场景图的四叉树结构，确定瓦片的可视判断策略。具体的，从第0层地形模型开始判断，当进入到第l层时，对该层第x行y列的瓦片tl,x,y，判断视点到该瓦片的距离distancel,x,y。对于给定阈值thresholdl，如果该距离在[thresholdl,∞]内，则该瓦片可视，并停止判断；否则该瓦片不可见，并进入该瓦片的所有子节点，继续判断。但需要注意，可视距离判断的区间是[thresholdl,∞],而非[thresholdl,thresholdl-1]，这是由于tl,x,y与tl-1,x,y的中心并不相同，使用后者进行判断，会造成某些视点下瓦片显示不完全。而当进入最底层瓦片时，则不需要判断，直接显示。

在瓦片的选择中，需要决定如何设置距离阈值thresholdl。本文使用屏幕像素作为确定thresholdl的标准，即thresholdl应使得地形模型中的n个顶点投影在屏幕上时，正好对应屏幕上的n个像素，则：

(1)

式中:fovy为视场在垂直方向的夹角，一般为60°；p为屏幕在fovy相应维度的分辨率，一般为列分辨率；rl为l层地形模型的分辨率。

2.3 回调机制的选择

对于场景图的管理，除了执行绘制，系统还需要响应用户操作，进而实现视角的调整、几何体的更新，并通过拣选优化显示效率。因此，一帧的显示，执行的不只是绘制遍历，而是更新、拣选、绘制3种遍历。其中，更新遍历允许修改场景中的几何体、更改视点，以实现动态场景和场景漫游；拣选遍历从待绘制的大量几何体中挑选出当前视域可见的部分，之后的绘制遍历只需执行这些几何体的绘制，提高绘制效率；绘制遍历使用拣选遍历过程生成的渲染列表，实现几何体的渲染。对于不同的应用场景，三种遍历的行为也有所不同，可以通过图形引擎提供的回调机制，编写自己的回调函数，自定义更新、拣选、绘制遍历的行为。

在渲染线程中，由于节点的可视判断是在更新遍历中完成，这表明在场景的更新遍历完成之前还不能确定所有节点是否可视。所以发现需要更新的节点并生成任务写入任务列表的工作，不能通过更新回调完成。在本文中，这部分工作通过拣选回调实现。而几何体的更改必须在更新遍历中完成，否则后续流程很有可能产生错误，甚至是线程冲突的。因此在本文中，任务完成后查询结果列表并替换渲染几何体的工作，通过更新回调实现。

同时还需注意一个任务组织的问题。由于准备线程会不断查看任务列表，并取出待完成任务。如果任务的发起是由单个节点完成的，那么当单个节点发出任务后，就会马上被准备线程取走，造成任务的碎片化，影响效率。所以本文中，任务的发出以帧为单位，将当前帧的所有任务收集后，再统一放入任务列表。具体方法为，动态瓦片叶节点在其裁剪回调中生成任务，并放入临时任务列表，在下一帧根节点的更新回调中，查看临时任务列表，并将其中的任务放入任务列表。

回调功能添加在LOD节点或叶子节点中都可以实现。考虑到叶子节点的裁减回调可以更方便明确地获取需要可视化的节点，本文选择在叶子节点，即动态地形瓦片节点上添加更新回调和拣选回调。

3 多线程模型

在该多线程模型的实现中，除渲染所用的数据外，还需要地形数据用于记录动态变化的地形，需要准备数据用于记录任务列表和结果列表。

(1)计算线程。计算线程不断调用地形过程模型进行迭代计算。过程模型在外部定义，计算结果一般为新的DEM数据。每次迭代计算完成后，产生新的地形数据，并令迭代计数增加1。渲染线程可以查看对比自身的迭代计数，判断是否需要更新。

(2)渲染线程。渲染线程的工作通过拣选回调和更新回调完成。拣选回调的工作是在当前视域和LOD层次的条件下，判断因新产生的地形数据而需要更新的瓦片，将其生成任务并放入任务列表。具体的，首先记录当前帧数，然后判断当前瓦片节点是否需要更新。在更新判断过程中，首先比较动态地形瓦片节点的范围与当前动态区域的范围是否重合，然后基于迭代计数判断该动态地形瓦片的数据是否是最新的地形。如果既重合又不是最新地形，则该瓦片需要更新，这时将一个更新该瓦片的任务放入准备数据的任务列表，并且设置更新标记为true。拣选回调流程如图3所示。

图3 拣选回调流程

Fig.3 Culling callback flow diagram

更新回调是查看结果列表中是否存在已完成的瓦片更新任务的结果，若存在则用新的瓦片替换旧的瓦片。在判断瓦片是否需要更新的过程中，先查看更新标记，然后比较上次帧数和当前帧数，判断该节点上一次的渲染是否很接近。如果更新标记为true，同时帧数也在一定范围内，则需要更新该节点，否则说明该节点已经不在视野内，则不必更新。当节点需要更新时，查看准备数据的结果列表是否存在当前节点的结果，如果存在则更新该动态地形瓦片节点。更新回调流程如图4所示。

图4 更新回调流程

Fig.4 Updating callback flow diagram

(3)准备线程。准备线程不断查看准备数据的任务列表，如果不为空，则取出其中的任务进行处理，根据任务信息实时生成相应节点的新瓦片数据，并在任务处理完成后，将结果放入结果列表。处理任务时需要读取地形数据，并利用LOD算法生成局部瓦片。在有些情况下，一些节点发出了准备任务，但是在任务完成前就离开了视域，而由此生成的结果则将在结果列表中滞留，不会被取走，因此准备线程还需要负责清除这部分滞留的结果。

4 实验验证

4.1 实验方法

针对本文提出的动态地形可视化的LOD调度技术，开展实验测试并验证其性能。实验硬件环境使用PC机，主板芯片组Intel HM65，中央处理器Intel Core i7-4700MQ，显示适配器NVIDIA GeForce GTX 765 M (2 GB)，内存16 GB (DDR3-1600 SDRAM)，硬盘Hitachi 750 GB 7200RPM。软件环境为操作系统Microsoft Windows 7 Ultimate 64-bit(Service Pack 1)，显示设备驱动版本NVIDIA ForceWare 340.62。图形开发环境为OpenGL 4.40，部分基础功能在OpenSceneGraph 3.2.0基础上扩展实现。OpenSceneGraph是一个基于OpenGL的由C实现的开源图形引擎，以场景图为核心组织三维场景(http://www.openscenegraph.org/)。

实验测试用的原始地形数据是SRTM 90 m中国南方部分区域的格网DEM数据，经纬度范围是102°～113°E，27°～32°N。将上述地形数据重采样为173 MB、690 MB、1.5 GB、3.4 GB的4份DEM数据进行测试。

实验选择一个典型的流域地貌演化模型进行动态过程计算，该模型可简化表示为[14]：

(2)式中:h为地形高程，t为时间，S为地形坡度；Q为单位宽度径流量，基于降水量经过汇流累积计算获得，为简化模型复杂度，实验中将降水量简化为均匀持续降水；β、m、n、k是不随高程和时间变化的模型参数，经率定得到β=0.01，m=1.1，n=0.3，k=0.02 m2/a。为增强测试效果，对模型迭代的时间步长进行了夸大。

4.2 实验结果

使用上述测试数据和过程模型，采用远近两种视点、不同大小的动态地形区域进行测试。测试中关闭垂直同步，以便通过帧速率判断性能。实验的地貌演化动态效果如图5所示。

图5 动态地形可视化效果

Fig.5 Visualization results of dynamic terrain

动态可视化的性能测试结果如表1所示。另外，使用3.4 GB、动态范围为20 000×10 000的DEM数据，测得一个典型可视化漫游过程的帧率变化如图6所示。在各测试环境中都达到了大于60帧/s的显示速率，满足可视化需求。

表1 实验性能

Table 1 Efficiency of the technology

数据量分辨率动态范围视角帧率173MB10085×44702000×2000远1329173MB10085×44702000×2000近324173MB10085×44705000×2000远1329173MB10085×44705000×2000近329690MB20170×89402000×2000远1360690MB20170×89402000×2000近273690MB20170×894010000×5000远1325690MB20170×894010000×5000近2751.5GB30255×134102000×2000远12671.5GB30255×134102000×2000近2521.5GB30255×1341015000×7000远12911.5GB30255×1341015000×7000近2413.4GB45382×201152000×2000远12083.4GB45382×201152000×2000近2103.4GB45382×2011520000×10000远12813.4GB45382×2011520000×10000近208

图6 典型漫游下的帧速率

Fig.6 Frame rate under classical roaming

动态地形的数据调度过程必然会降低渲染效率，因此有必要对本文提出的动态调度技术的性能进行评价。分别在开/关动态地形的情况下，对可视化帧率进行测试对比，其结果如表2所示，其中每行的测试数据和参数与表1对应。在测试环境下，动态过程造成的可视化性能损失均小于10%，证明本文方法具有很好的性能。

对比近年的已有研究，本文方法具有较好的性能。Koca等在2 048×2 048的DEM数据上叠加动态地形要素，其渲染性能平均可达235帧/s[12]。Kang等提出的多分辨率地形渲染方法，在16 000×16 000和32 000×32 000的DEM数据上，平均帧速率达423帧/s[11]。李钦等实现的基于分块LOD的地形实时渲染算法，对于4 097×4 097的DEM数据，在中远视角下漫游的平均帧速率达877帧/s[15]。而本文方法在考虑动态地形的情况下，多组测试数据上的渲染性能(表1、图6)平均可达658帧/s，其中近视角下达225帧/s，中远视角下达875帧/s，可视化性能均达到或高于已有研究成果。

表2 动态地形可视化的性能损失

Table 2 Efficiency loss of dynamic terrain visualization

动态帧率非动态帧率性能损失动态帧率非动态帧率性能损失132913572.06%126713002.54%3243301.82%2522571.95%132913572.06%126713002.54%3293300.30%2332579.34%136013640.29%120812745.18%2732792.15%1912109.05%132513642.86%126312740.86%2752791.43%2082100.95%

5 结论

面向土壤侵蚀、地貌演化等地形过程模拟的应用需求，提出了一种预处理与实时更新相结合的LOD混合调度技术，实现大规模动态地形可视化。基于场景图组织管理大规模地形的LOD模型，支持动态地形瓦片的实时查找、更新和绘制，提出并实现LOD瓦片动态调度和绘制的多线程模型，利用计算线程和准备线程分别负责动态地形的计算和地形瓦片的生成，利用渲染线程发现需更新的地形瓦片并及时更新。该技术以LOD瓦片的动态更新绘制替代静态预处理方法，在地表过程模型迭代计算的同时，同步更新地形瓦片，并且仅更新在当前视域和分辨率下发生变化的局部瓦片，避免了全局更新的大量计算，使得瓦片更新过程不会对渲染速度产生明显的影响，从而大幅度提高可视化性能。对于GB级以上的DEM数据，动态地形可视化帧速率达60帧/s以上，可有效满足地形过程模拟可视化的性能需求。在本文的技术实现中还未加入对纹理的支持，另外在大视野场景下的漫游，会出现轻微的局部新地形的视觉抖动现象，这是下阶段需要解决的问题。

[1] SMELIK R M,TUTENEL T,BIDARRA R,et al.A survey on procedural modeling for virtual worlds[J].Computer Graphics Forum,2014,33(6):31-50.

[2] 汤国安，刘学军，闾国年.数字高程模型及地学分析的原理与方法[M].北京：科学出版社,2005.

[3] 李清泉，杨必胜，史文中，等.三维空间数据的实时获取、建模与可视化[M].武汉：武汉大学出版社,2003.

[4] DUCHAINEAU M,WOLINSKYM,SIGETI D E,et al.ROAMing terrain:Real-time optimally adapting meshes[A].Proceedings of the 8th Conference on Visualization′97[C].Washington,DC:IEEE Computer Society Press,1997.81-88.

[5] RÖTTGER S,HEIDRICH W,SEIDEL H P.Real-time generation of continuous levels of detail for height fields[A].Proceedings WSCG′98[C].Plzen:Union Agency,1998.315-322.

[6] URLICH T.Rendering massive terrains using chunked level of detail control[A].Proceedings of ACM SIGGRAPH′02[C].San Antonio,TX:ACM Press,2002.

[7] CIGNONI P.Planet-sized Batched Dynamic Adaptive Meshes (P-BDAM)[A].Proceedings of the 14th IEEE Conference on Visualization (VIS′03)[C].Washington,DC:IEEE Computer Society,2003.147-154.

[8] ASIRVATHAM A,HOPPE H.Terrain rendering using GPU-based geometry clipmaps[A].PHARR M,FERNANDO R.GPU Gems 2[C].Boston,MA:Addison-Wesley,2005.46-53.

[9] LIVNY Y,KOGAN Z,EL-SANA J.Seamless patches for GPU-based terrain rendering[J].The Visual Computer,2009,25 (3):197-208.

[10] HU L,SANDER P V,HOPPE H.Parallel view-dependent refinement of progressive meshes[A].Proceedings of the Symposium on Interactive 3D Graphics and Games (I3D′09)[C].Boston,MA.New York:ACM,2009.169-176.

[11] JANG H Y,CHO C S,HAN J H.Multi-resolution terrain rendering with GPU tessellation[J].The Visual Computer,2015,31(4):455-469.

[12] KOCA ,G D KBAY U.A hybrid representation for modeling,interactive editing,and real-time visualization of terrains with volumetric features[J].International Journal of Geographical Information Science,2014,28(9):1821-1847.

[13] TATEOSIAN L,MITASOVA H,THAKUR S,et al.Visualizations of coastal terrain time series[J].Information Visualization,2014,13(3):266-282.

[14] 刘光.基于GIS的现代黄土地貌演化过程动态仿真研究[D].北京：北京大学，2003.

[15] 李钦,戴树岭,赵永嘉，等.分块LOD大规模地形实时渲染算法[J].计算机辅助设计与图形学学报， 2013,25(5):708-713.

A LOD Scheduling Method for Massive Dynamic Terrain Visualization

GAO Yong,LIU Jia-jun,GUO Xiao,WU Lun

(Institute of Remote Sensing and Geographical Information System,Peking University,Beijing 100871,China)

The processes modeling and simulation,e.g.geomorphic processes and land processes,will iteratively generate a series of terrain data in real time.This dynamic process needs more efficient visualization technologies.But the traditional preprocessing-based methods cannot fulfill it for the rendering delay caused by huge computation.A hybrid LOD scheduling method is presented integrating preprocessing and real-time update to visualize massive dynamic terrain.The terrain LODs are modeled and managed based on the scene graph,and a multithread model is introduced to update and render the terrain tiles dynamically.Instead of reconstructing the whole visualization data,this method only update and render the necessary local LOD tiles for the new terrain data iteratively.So the visualization efficiency can be improved significantly.

terrain visualization;level of detail model;scene graph;multithread;dynamic scheduling

2015-09-10；

2015-10-16

国家863支持项目(2011AA120301、2011AA120303)

高勇(1974-)，男，博士，副教授，研究方向为高性能地理计算与空间数据挖掘。E-mail:gaoyong@pku.edu.cn

10.3969/j.issn.1672-0504.2016.01.002

P208

A

1672-0504(2016)01-0006-06