随着GPU (graphic processing unit) 图形处理器处理能力的飞速发展和可编程图形管线的出现，基于GPU的海量地形LoD绘制算法已逐渐替代传统的CPU构网算法，成为进一步提高大规模地形绘制效率的新手段^{[1, 2]}。其中，利用Tessellation技术的地形渲染方法^[3-8]可以对粗糙的地形网格进行插值产生新的顶点，在显著提升地形模型几何精度的同时减少了数据传输的压力，已成为目前基于GPU地形渲染方法的主要研究热点。现有的GPU Tessellation地形绘制算法，是通过屏幕空间投影误差进行原始粗糙网格和细分图元细节层次选择，完成多分辨率地形构建，实现了地形的高效绘制。在多分辨率地形可视化表达中，相邻不同分辨率网格之间不可避免地产生了裂缝。而上述算法是在原始粗糙网格间采用最简单的“垂直边缘法”^[9]消除裂缝，即通过在地形块边界处人为填充垂面，从视觉上掩盖了裂缝。而相邻不同分辨率地形块共享顶点仍然位于不同高度，地形块邻接处具有不同的边界，裂缝问题未从本质上得到解决，导致地形块边缘处边或三角形空间关系难以表达，空间分析难以实现。该算法仅能满足海量地形在视觉上的可视化表达，很难为城乡规划、大型工程设计、军事模拟等领域，提供可视化分析和决策支持^[10]；同时，该算法在预处理阶段，必须提前计算好不同格网层次间的最大空间误差，这样在数据实时更新时CPU需要负担较重的预处理任务，直接影响了地形实时渲染效率。

本文在GPU Tessellation技术基础上，提出了一种GPU构网的地形无缝绘制算法。结合CPU和GPU各自的特点，通过合理控制相邻不同分辨率网格的细分等级，确保地形块间连续过渡。在保证地形高效绘制的同时，实现多分辨率地形的无缝可视化表达，为基于海量地形的可视化分析与决策提供保障。

1 GPU Tessellation渲染原理

Tessellation是一种利用GPU硬件加速，将多边形分解成更加细小的碎片以提升几何逼真度的方法^[11-14]。细分的基本图元可以是四边形、三角形或者线段。置换纹理映射技术^[15]通过对高度图进行顶点采样，将高程纹理映射到网格顶点上，实现平面网格到真实地形网格的转变。图 1为基于GPU Tessellation的地形渲染流程。其中，曲面细分控制阶段接收网格的控制点作为输入数据，输出必要的细分因子和控制点信息；曲面细分阶段根据细分因子将图元细分成更小的对象，输出细分后新生顶点的标准化纹理uv坐标；曲面细分计算阶段根据控制点信息和新生顶点的uv坐标计算出细分后网格各点的位置信息，利用置换纹理映射技术，对高度图进行采样，将网格各点位置信息中的高程值调整为真实世界中的高程。通过上述3个阶段，CPU中一个简单的四边形网格通过GPU Tessellation细分成为一张复杂的地形格网。最后，在像素着色器中采样贴图纹理。

图  1  GPU Tessellation地形渲染流程

Figure  1.  Terrain Rendering Procedure with GPU Tessellation

下载: 全尺寸图片 幻灯片

本文以四边形作为曲面细分的基本单元，细分因子需要4个边细分因子 (Edge) 和两个内部细分因子 (Inner)，分别对应于四边形4条边和水平、竖直方向的细分程度。图 2为在不同细分因子作用下，四边形最终的细分效果。从原理上看，基于GPU Tessellation的地形渲染算法能够在输入低分辨率网格的基础上，绘制出传统地形渲染算法输入高分辨率地形网格时输出的渲染效果，并且大幅度节约内存开销，提升地形渲染效率。

图  2  不同细分因子细分效果

Figure  2.  Effects of Different Tessellation Factors

下载: 全尺寸图片 幻灯片

2 地形数据组织结构

由于当前计算机硬件条件的限制，对于大规模的栅格数据，在实际应用中不可能一次性将所有数据载入计算机内存。因此，需要采用数据分割技术将高程和纹理数据分层分块，构建数据金字塔^[16]和地形块四叉树结构^[17]如图 3所示。为了确保地形块间无缝链接，同一层次相邻数据块间共享边界纹理数据。规定每一个满足绘制条件的叶子节点称为一个Tile，Tile中存储着4个顶点的位置信息和对应的高度图、纹理图，地形渲染时将这些数据一同传入GPU中。本文将高程数据存储为16位浮点精度的DDS^[18]格式高度图，有效地降低了纹理实时传输对地形渲染效率的影响。

图  3  数据金字塔模型和地形四叉树结构

Figure  3.  Pyramid Model and Terrain Quad-tree

下载: 全尺寸图片 幻灯片

当前，GPU绘制函数DrawPrimitive的调用次数仍然是限制地形绘制效率的重要因素，每个Tile需要调用一次绘制函数。本文将Tile均匀分割为2^m×2^m个Patch (图 3)，Patch是曲面细分的基本图元。每个Patch仅需要存储其在Tile中的行列号，就可以精确定位其位置。细分因子的取值受限于1~64，Patch最大细分程度下会形成65×65个顶点的网格。一个Patch对应的高度图像素个数如果超过65×65将会产生数据冗余，如果少于65×65，将不足以表达最高的细分层次。本文将Patch对应的高度图像素个数取固定值65×65，Tile对应的高度图分辨率相应取值 (2^m+6+1)×(2^m+6+1)。m值越大，Tile分辨率越高，地形渲染时需要的Tile个数越少，传至GPU中的高度图个数也会相应减少。文献[19]对纹理大小对地形绘制效率的影响进行了深入研究，本文将m取经验值3，既有效减少了屏幕中Tile的个数，又避免了m值过大时实时传输大纹理导致的帧率震荡现象。因此，Tile以8×8个Patch的平面网格进行组织，高度图数据金字塔中每块数据的分辨率是513像素×513像素。

3 基于Tessellation的LoD地形无缝绘制

3.1   Tile LoD选择标准

为了尽可能降低CPU的负担，本文算法中CPU阶段不涉及任何高程数据的操作。所有Tile均以平面网格的形式传入GPU，高程数据的获取全部在GPU中通过纹理采样方式获得。因此，传统的基于细分前后屏幕空间投影误差标准不适用于本文算法的CPU阶段。Tile的LoD选择属于粗粒度的层次选择，本文使用简单的基于视距的细节层次模型，距离视点越近，地形细节越丰富。其标准如式 (1) 所示：

式中，参数l表示世界坐标系下地形块的边长；d表示视点到Tile平面网格中心点的距离；C是一个可调控的阈值，C值越小，Tile的LoD层次越高，屏幕中实时渲染的Tile个数越多。

地形渲染时，从根节点开始依次进行判断。如果Tile满足式 (1) 且该节点位于视锥体内，则将该节点加入渲染列表；如果节点位于视锥体外，则舍去该节点；如果节点位于视锥体内且不满足式 (1)，则细分该节点，并依次对4个子节点进行递归判断。最终，所有需要绘制的Tile共同构成了一个渲染列表。为了解决相邻Tile之间LoD不一致产生的裂缝问题，每个Tile除了存储着本块需要的数据，还存储着与之相邻的地形块和当前块LoD层次的最大差值。本文用4个整数来表示地形块上、下、左、右4个方向的邻接信息，正值表示相邻地形块LoD层次高于当前地形块，负值表示相邻地形块LoD层次低于当前地形块，0表示相邻地形块和当前地形块LoD层次相同或相邻地形块不存在。以图 4中地形块A为例，{0，1，2，-1}即为A上、下、左、右四个方向需要存储的邻接信息。对于相邻地形块LoD层次低于当前块的情况 (如B)，还要额外存储B的高度图纹理信息，以确保GPU纹理采样时A、B相邻边界各点采样的高程数据相同。本文Tile LoD层次选择标准构建的粗粒度网格邻接关系简单，Tile LoD层次随着视点到Tile距离的增大逐渐降低，相邻Tile LoD层次差一般不超过2，邻接关系处理并不会对地形绘制效率产生明显影响。

图  4  Tile邻接关系示意图

Figure  4.  Adjacency Relationship Between Tiles

下载: 全尺寸图片 幻灯片

3.2   Patch多分辨率无缝表达

Patch的处理是地形多分辨率无缝表达的核心阶段，Patch细分因子的不同实现了地形的多分辨率，Patch相邻边具有相同的细分因子，确保了地形的无缝表达。在多分辨率地形的绘制过程中，仅以视距来确定细分等级是不完善的，还要综合考虑地形粗糙度的影响，地形越崎岖，分辨率应该越高。地形粗糙度的衡量标准有很多种，本文以块内所有顶点的最大高程差表示Patch块空间误差的最大值，并将其投影到屏幕上，将屏幕空间投影误差作为Patch的细分标准。

3.2.1   Patch最大高程差

每个Patch对应于高度图中的65像素×65像素，在曲面细分控制阶段对其按 (2ⁿ+1)×(2ⁿ+1) 个像素进行均等采样。n值越大，最大高程差结果越精确，GPU采样时间也会相应增加。将Patch的4条边和内部分开计算，边的空间误差最大值取边上采样点的高程最大差值，内部空间误差最大值取内部采样点的高程最大差值，最大高程差ξ_max=h_max-h_min。表 1给出n取不同值时，对1 024个Patch进行采样GPU需要消耗的时间。可以看出，n取6时，GPU仅需要0.9 ms就可以求出Patch的4条边和内部的最大高程差，不会对地形渲染效率产生明显影响。因此，将n取值为6，Patch对65像素×65像素全部进行了采样。

表  1  GPU采样效率

Table  1.  GPU Sampling Efficiency

n值	1	2	3	4	5	6
耗时/ms	0.001	0.002	0.003	0.021	0.185	0.905

下载: 导出CSV 

| 显示表格

3.2.2   Patch屏幕空间投影误差

最大高程差能够反映地形的粗糙程度，但是由于视角的可变性，实际映射到屏幕上的范围却可能很小。因此，本文将最大高程差投影到屏幕上，求得其在屏幕上投影的像素个数。Patch块屏幕空间投影误差的计算参考文献[20]中的方法：

式中，, R_vctg (φ_v/2))，R_h和R_v是视窗的水平和垂直分辨率，φ_h和φ_v是视锥体的方位角和俯仰角；ξ_max是Patch的最大空间误差；d是视点到Patch包围盒的最近距离。本文将Patch的4条边和内部分开计算，各参数需要进行相应调整。计算边屏幕空间投影误差时，ξ_max取相应边最大高程差，d取视点到该边包围盒的最近距离。计算内部屏幕空间投影误差时，和原始公式保持一致。

3.2.3   Patch细分因子计算

为了实现Patch的自适应Tessellation，需要在曲面细分控制阶段计算Patch的6个细分因子，还要确保相邻Patch的邻接边细分程度相同，实现Patch间无缝链接。式 (2) 分别求出了Patch的4条边和内部屏幕空间投影误差，通过如下公式建立细分因子F和屏幕空间投影误差的关系：

式中，ceil () 为向上取整函数；clamp () 为夹紧限制函数；K是自定义的参数，K值越大，细分因子越大；x_min、x_max分别是细分因子需要限制的最小值和最大值，一般取值1和64。细分因子以整数形式均匀变化，避免了文献[3]由于细分因子两倍关系变换引起的顶点突变问题。通过上述方法，可以求得Patch四条边的细分因子。水平和竖直方向细分因子由块内屏幕空间投影误差求得，数值相同。

3.2.4   Patch裂缝处理

本文将Patch的邻接关系分为以下3种：① Tile内部Patch的邻接关系；②相同LoD层次Tile间Patch的邻接关系；③不同LoD层次Tile间Patch的邻接关系。为了便于说明，将Tile以2×2的形式分割成Patch，图 5为部分Patch间的邻接关系。第一种情况，如P₁和P₂，邻接边计算得到的细分因子相同，且高程数据来至同一块高度图，不存在裂缝。第二种情况，如P₃和P₉，邻接边共享一列高度图纹理数据，计算得到的细分因子相同，不存在裂缝。第三种情况，如P ₂和P₅，T₁和T₂LoD层次不同，且高度图位于金字塔不同层次，存在裂缝。本文以P₂和P₅为例介绍第三种情况裂缝消除方法。

图  5  Patch邻接关系示意图

Figure  5.  Adjacency Relationship Between Patchs

下载: 全尺寸图片 幻灯片

T₁和T₂中存储着4个代表邻接关系的整型参数，以i、j分别表示T₁右侧和T₂左侧的参数值。计算P₅左侧边细分因子时，在原有计算方法的基础上，添加两个限制条件：①细分因子仅能取值为2ⁿ，即只能在{1，2，4，8，16，32，64}中取值，比如通过计算得到的细分因子为14，实际取值16，依次向上取值；②式 (3) 中，x_min取值2^j，避免计算P₂右侧边细分因子时出现小于1的情况。本文算法采用GPU构网，P₂无法直接访问到P₅的细分因子。但是，T₁中存储着T₂的高程纹理信息，可以再次对该纹理进行采样求得P₅左侧边细分因子2ⁿ，则P₂右侧边的细分因子为2ⁿ⁺ⁱ。通过上述方法，P₂和P₅相邻边细分顶点刚好重合在一起。此时，只要保证重合顶点在置换纹理映射时获取的高程值相同，就可以实现P₂和P₅无缝链接。T₁和T₂对应的高度图位于金字塔不同层次，纹理重合部分的采样值可能会出现不同的情况。因此，在对P₂右侧边上各细分顶点进行纹理映射时，采样纹理不再是T₁所在的高度图，而是T₂所在的高度图。实验部分给出了最终的绘制效果，可以看出，最终绘制的地形不存在裂缝，网格连续。

4 实验结果和分析

为了验证本文算法，在Windows7操作系统下，使用VS2010开发平台和DirectX 11工具以及HLSL着色语言设计开发了原型系统，实现了大规模地形实时绘制。硬件环境如下：Intel (R) Core (TM) i5-2380P CPU，8GB RAM，NVIDIA GeForce GTS 450显卡，屏幕分辨率为1 280像素×1 024像素。实验数据为Puget Sound高度图和纹理图，分辨率为16 385像素×16 385像素，四叉树自顶向下分为6层，每个节点纹理的分辨率为513像素×513像素。

为了验证本文算法的地形绘制效率，在相同的硬件环境下，将其与传统的CPU四叉树算法、Geometry Clipmap算法和文献[3]中的算法在绘制同等数量三角形下的平均帧率进行了比较 (图 6)。相比CPU四叉树算法，虽然本文算法需要额外向GPU传入高度图和地形块邻接信息，但却大量减少了CPU需要创建的顶点个数，有效降低了高程数据实时获取时间，平衡了CPU-GPU负担，显著提升了地形渲染效率。相比Geometry Clipmap算法，本文算法也具有较大优势。相比文献[3]的算法虽然渲染帧率略有下降，但文献[3]算法构建的地形网格只是从视觉上消除了裂缝，并未从本质上解决该问题，而本文算法构建的多分辨率地形网格自适应连续，不存在裂缝。

图  6  帧率对比图

Figure  6.  Comparison Chart of Frame Rates

下载: 全尺寸图片 幻灯片

当参数C取1.5，K取2时，本文算法整体和局部网格图以及叠加纹理以后的效果如图 7所示。可以看出，地形网格绘制效果满足视距和地形粗糙度规则，距离视点越近，地形越粗糙，地形细节层次越高。相邻Patch网格链续，不存在裂缝。局部地形平滑过渡，完全满足可视化分析的应用需求。

图  7  地形显示效果图

Figure  7.  Display of Terrain Surface

下载: 全尺寸图片 幻灯片