大规模地形建模一直是飞行仿真、地理信息系统、虚拟现实等领域的热点问题。如何高效率、高质量、高稳定性地实时渲染具有超高细节度的地形，仍是一个难题。近年来，计算机图形处理器（GPU）得到极大的发展，单纯依靠CPU的传统绘制方法已经不能适应现代图形硬件的发展^[1]。几何裁剪图（geometry clipmaps）通过构建视点相关的“金字塔”结构多分辨率规则三角形网格，可简单高效地表示3维地形结构，并能较好地解决渲染帧率不稳定的问题^[2]。Asirvatham等^[3]利用GPU高性能特点，提出几何裁剪图（geometry clipmaps）的优化算法，由CPU构建顶点缓存和索引缓存，交予GPU进行三角形网格生成，大大减少了CPU的工作负担，但是，该算法需要将庞大的顶点及索引数据从CPU向GPU传输，会带来巨大的数据传输负担。此后，Dimitrijević^[4]、Tang^[5]、Feldmann^[6]等在几何裁剪图的基础上进行算法优化，但是，这些方法都没有从根本上解决上述问题。

从DirectX11和OpenGL4.0渲染管线中引入细分着色器以来，在显卡硬件中生成顶点和三角形效率达到了一个新的高度。Yusov等^[7]提出了一种基于硬件细分的地形渲染算法，利用细分着色器，CPU仅需向GPU传输极少的细分控制点，自适应生成顶点及三角形面片。但是，该算法在实时漫游中，会因为地形不同区域的复杂程度不同，导致渲染负载不平衡，引起帧率骤变的问题。张兵强等^[8]提出了一种基于屏幕空间的地形细分着色渲染方法，进一步简化了细分控制点的组织；Kang等^[9]在文献[7]的基础上，增加了对地形局部高精度数据区域的进一步细分的方法；韩敏^[10]和Alderson^[11]等分别从地形数据压缩和网格简化入手，减少了大规模地形数据的存储冗余。Liu^[12]和Mikhaylyuk^[13]等分别针对飞行模拟和航天模拟提出基于细分着色的地形绘制优化算法。但是，这些算法都没有从根本上解决实时渲染中因不同区域地形网格疏密程度不同引起的渲染帧率不稳定问题。Barnard 等^[14]首次将细分着色技术应用于几何裁剪图，但是，该方法只是简单通过细分着色器减少了一定数量的CPU顶点输入，并未充分发挥硬件性能。

针对如今超高分辨率的海量地形数据，如何高效率、帧率平滑地实时渲染，仍是一个十分棘手的问题。针对上述问题，在几何裁剪图的算法框架下，作者提出一种基于细分着色的地形建模方法。引入细分着色器，通过预先指定能够表示几何裁剪图结构的细分控制点，将其由CPU以顶点缓存形式传给GPU，并由GPU细分着色器控制自适应三角形面片的生成和更新，通过增加层间共享边外侧细分层级值消除地形中的“裂缝”现象，在充分利用GPU硬件性能的同时，保证渲染帧率的稳定性。

1 算　法

作者提出的基于细分着色的地形建模方法：首先，根据几何裁剪图结构构建地形各层可复用的细分控制点，这些细分控制点能够表达每层几何裁剪图的结构框架和所有状态。细分控制点可预先生成并存入顶点缓存。其次，根据顶点缓存中的细分控制点生成每层几何裁剪图的索引缓存，GPU在读取索引缓存后通过细分着色器生成自适应三角形面片。在渲染循环的更新阶段，仅需对几何裁剪图的变化区域进行顶点索引的更新，随后更新几何裁剪图的状态。最后，以自内向外的顺序，依次对每层（最内层除外）几何裁剪图的内侧边（与下一层的共享边）进行增加自适应点的操作，从而增加内侧边三角形面片，使其与内层几何裁剪图相对应，消除层间共享边的裂缝。

1.1 细节控制点构建 1.1.1 几何裁剪图的结构框架

几何裁剪图将地形高程当作一张2维灰度图，并对其过滤采样，形成包含L层的mipmap图像^[3]。针对mipmap每一层，构建如图1所示的正方环形结构，由n×n的点阵构成。为了实现可视区域裁剪，将该结构分为若干块，则这些块包括3种类型：12个m×m的正方形（图1的灰色部分，简称为M型块）；4个m×2的矩形（图1的绿色部分，简称R型块）；1个L型区域（图1的蓝色部分，简称为L型块）；其中， $m = (n + 1)/4 - 1$ 。

针对几何裁剪图的每一层，构建如图2所示的嵌套三角形网格。为了方便绘制时的视锥体裁剪，作者将每层几何裁剪图分成18块。其中：第1～12块为规则的正方形网格块（M型块）；第13～16块为规则的矩形网格块（R型块）；第17块为L型的规则网格块（L型块），在实时漫游中，L型区域可能在几何裁剪图该层正方环内侧的4个位置（左上、左下、右上、右下）出现；第18块为视点中心区域的网格，该区域的尺寸刚好为本层网格尺寸的一半。在几何裁剪图中，只有最内层才会渲染第18块，其余层则均由下一层网格所代替（如图2的右下角所示）。由于第18块所在区域需要被下一层网格填充，则每层的网格数必须为偶数，即每层网格边上的顶点必须为奇数。因此，为便于处理，作者将每层网格的顶点数设定为n×n，其中， $n = {2^k} + 1,k = 2,3,4, \cdots $ 。

1.1.2 细分着色器的工作流程

在传统的OpenGL绘制管线中，GPU只能在CPU传来的固定顶点处理过程中对其关联的数据进行更新，而无法实时创建新的几何体，或对图元中其他顶点数据进行访问^[15]。

OpenGL4.0的绘制管线中引入了细分着色器，突破了上述限制，包含细分着色的OpenGL绘制管线如图3所示。

新的绘制管线定义了一种新的几何体图元类型—面片（patch）。面片是在GPU中通过细分着色器生成的线段或三角形。模型的几何图元生成过程被分为顶点着色和细分着色两个阶段。在顶点着色阶段，仅需在CPU中设置能够表达模型基本结构的顶点，这些顶点被称为“细分控制点”，存入顶点缓存供GPU使用；细分阶段的工作由细分控制着色器和细分计算着色器共同完成。细分控制着色器通过设置细分层次因数等参数决定生成面片的数量。细分计算着色器通过设置图元生成域、图元面朝向及细分坐标间隔等参数，控制生成面片的类型、朝向及分布。

1.1.3 细分控制点的创建和分布

与文献[2−3]的方法不同，提出的算法无需在CPU中创建几何裁剪图的每个顶点，仅需在预处理阶段针对几何裁剪图各块的轮廓进行顶点（细分控制点）构建。细分控制点将由CPU以写入顶点缓存的方式传给GPU，并由GPU细分着色器生成面片，形成全部地形可视化的顶点和三角形。

图4给出了细分控制点的具体分布。其中，点 $\{ {n_0},{n_1}, \cdots ,{n_{31}}\} $ 能够覆盖所有M型块和R型块；由于L型块可能出现在4个不同的位置，故创建点 $\{ {n_{32}},{n_{33}}, \cdots ,{n_{43}}\} $ 表示L型区域。

细分控制点存入顶点缓存后，将会被几何裁剪图每层的索引缓存引用，生成后续的三角形面片。

1.2 自适应三角形面片生成更新

每层几何裁剪图都有一个索引缓存，其中，存有对顶点缓存的索引。GPU细分着色器将根据这些索引生成自适应三角形面片并实时进行更新。

1.2.1 自适应三角形面片生成

OpenGL细分控制着色器支持3种不同的图元生成域：四边形、三角形和等值线几何^[15]。由于几何剪裁图的各块均可由矩形组合表示，故提出的算法中细分着色器采用四边形域进行三角形面片生成。因此，索引缓存中的点将以每4个为一组的方式传入细分控制着色器。所有M型块和R型块均可由一组4点进行构建。L型块由3组索引点构建，分别表示L型块的水平部分、垂直部分以及一个长度为1的拐角部分，L型块将根据其在实时漫游中的不同位置分为如图5所示的4种方式构建。

假设几何裁剪图是由n×n的点阵构成，则M型块的边长为：

$m = (n + 1)/4 - 1$

(1)

相应地，R型块的长边长度为m，短边长度则为 $n - 4m - 1 = 2$ 。L型块的宽度为1，水平部分和垂直部分的长度为 $2m + 1$ 。

由此可得到3种块的细分层级设置：

$\left\{ \begin{aligned} & T_{\rm M}^{\rm{I}}(i) = m,i = 0,1;\\ & T_{\rm M}^{\rm{O}}(i) = m,i = 0,1,2,3 \end{aligned} \right.$

(2)

$\left\{ \begin{aligned} & T_{\rm R}^{\rm{I}}(0) = T_{\rm R}^{\rm{O}}(0) = T_{\rm R}^{\rm{O}}(3) = 2,\\ & T_{\rm R}^{\rm{I}}(1) = T_{\rm R}^{\rm{O}}(1) = T_{\rm R}^{\rm{O}}(2) = m \end{aligned} \right.$

(3)

$\left\{ \begin{aligned} & T_{\rm L}^{\rm{I}}(0) = T_{\rm L}^{\rm{O}}(0) = T_{\rm L}^{\rm{O}}(3) = 1,\\ & T_{\rm L}^{\rm{I}}(1) = T_{\rm L}^{\rm{O}}(1) = T_{\rm L}^{\rm{O}}(2) = 2m + 1 \end{aligned} \right.$

(4)

假设 $n = 15$ ，则自适应三角形面片构成如图6所示，其中，黑色圆点表示细分控制点。

由图6可知，无论n取值如何，仅利用4个顶点可以完成M型块和R型块的三角形面片生成，仅利用8个顶点可以完成L型块的三角形面片生成。

1.2.2 自适应三角形面片更新

在地形实时漫游时，由于视点的移动是连续的，因此，几何裁剪图每层每次更新只需要修改L型块的构建方式。

相对于视点移动的距离，较外层发生更新所需步长是成指数增加的。假设最内层（即最精细层） ${l_0}$ 的更新步长为s，则第 ${l_k}$ 层的更新步长为：

${s_k} = s{\text{×}} {2^k}$

(5)

因此，自适应三角形面片很少发生更新，即便发生更新，仅需更改构建L型块的8个细分控制点的内容，相比于经典几何裁剪图算法需对L型块所有顶点进行更新（如n=127，L型块共有252个顶点），效率会有进一步的提升。

1.3 层间裂缝消除 1.3.1 裂缝消除原理

几何裁剪图相邻层间会因分辨率不同导致“裂缝”现象的出现，如图7所示。经典几何裁剪图算法通过渲染一组“退化三角形”来“缝补裂缝”^[3]。这样不仅会造成视觉效果失真，还会带来额外的渲染负担。作者使用细分着色器，通过增加外层几何裁剪图的层间共享边上的外侧细分层级值，简单有效地解决该问题。

式（2）～（4）中，关于内侧和外侧细分层级设置是一致的，即生成的面片是均匀的。而位于几何裁剪图相邻层共享边区域的面片由于分辨率不同，导致共享边上内层的顶点数是外层顶点数的两倍。这是产生“裂缝”现象的根本原因。通过增加外层面片所在几何图元在共享边上的外侧细分层级，可解决这一问题。图8给出了消除“裂缝”的原理，对于任一位于共享边的面片单元，仅需将外层共享边的外侧细分层级值增倍，使得内外层在共享边上的顶点数一致，消除“裂缝”。

1.3.2 裂缝消除方法

几何裁剪图层间共享边分为两部分，一部分位于L型块上，另一部分位于对侧的M型和R型块上，如图9所示。

对于共享边第1部分，仅需在式（4）的基础上，对L型块进行细分控制设置：

$T_{\rm L}^{{\rm{O}}*}(inner) = T_{\rm L}^{\rm{O}}(inner) {\text{×}} 2$

(6)

式中，inner表示L型块的内侧边，即共享边。

对于共享边第2部分，R型块、M型块7和M型块10（如图9所示）可按共享边第1部分的处理方法，根据式（6）进行细分控制设置；而对于M型块5和M型块11，其内侧边有一小部分落在了L型块上。若按式（6）设置，则与之相邻的L型块的边上又会出现新的“裂缝”。为了简便处理，对L型块的相应边同样进行了式（6）的设置，即将该边原有的细分控制值由1设为2，从而消除新的“裂缝”。

经过以上细分控制设置操作，可以完美消除层间裂缝。

图10给出了一个当n=15时的示例，其中，红色粗线框内展示了利用层间共享边外侧细分层级的灵活设置得到的结果。由图10可以看出，位于共享边上的三角形面片能够全部对接，没有图7所示的“裂缝”现象。

1.4 细分着色器的实现细节

细分着色器的实现包括细分控制着色器和细分计算着色器的实现。

由于细分控制着色器主要功能是传递细分控制参数，因此，仅需在细分控制着色器中根据式（2）～（4）、（6）对内外侧细分层级因数进行设置，即可完成实现。

对于细分计算着色器，一个关键的问题在于计算自适应三角形面片的细分坐标。由于本文算法的三角形面片都是均匀规则的，因此采用等间隔的方式进行三角形面片渲染。

设四边形生成域的4个细分控制点分别为 $p_0^{{\rm{I}}}$ 、 $p_1^{{\rm{I}}}$ 、 $p_2^{{\rm{I}}}$ 、 $p_3^{{\rm{I}}}$ ，其类型为OpenGL Shading Language内置向量类型vec4，细分坐标为 $(u,v)$ ，则通过细分计算着色器生成的面片位置坐标计算式为：

$\begin{aligned}[b] {p^{{\rm{O}}}} = & (1 - u) \times (1 - v) \times p_0^{{\rm{I}}} + \\ & u {\text{×}} (1 - v) \times p_1^{{\rm{I}}} + u \times v {\text{×}} p_2^{{\rm{I}}} + \\ & (1 - u) {\text{×}} v \times p_3^{{\rm{I}}} \end{aligned}$

(7)

利用式（7）计算得到的面片位置坐标，可以保证自适应三角形面片均匀规则的分布。

2 实验结果分析 2.1 实验环境及方法

实验硬件配置为：CPU Intel Core i7-2600K 3.4 GHz，8.00 GB RAM，NVIDIA GeForce GTX 590显卡，PHILIPS 241E1显示器（分辨率为1 920×1 080）。软件环境为：Windows 7 64位旗舰版，Visual Studio 2012，OpenGL 4.3，着色器语言为GLSL。实验采用的数据包括一份中国西藏地区的地形数据（包含一套高原机场模型）和一份美国Puget Sound地区的地形数据，高程数据和影像数据大小分别均为16 385×16 385和16 384×16 384。

首先，实验对本文算法和经典几何裁剪图算法进行了CPU向GPU传输顶点数量的比较；其次，针对中国西藏地区数据，实验通过给定的漫游路径（如图11所示），分别用本文算法、文献[3–4,7]算法进行地形实时漫游并记录相关数据进行比较；最后，为了方便观察实验结果，利用Puget Sound影像数据色彩鲜明的特点，进行消除裂缝的实验。

2.2 实验结果及分析

表1给出了本文算法与经典几何裁剪图算法CPU向GPU传输顶点数量的比较。

从表1看出：经典几何裁剪图算法的顶点传输数量非常庞大，且随着几何裁剪图尺寸的增大以平方级速度增长；而本文算法仅需向GPU传输若干个细分控制点，因此，顶点传输数量非常少，且不会受几何裁剪图尺寸增大的影响。

图12给出了地形细节层次（LOD）层数为7层，几何裁剪图尺寸n=255时（文献[7]算法设定可视区域的尺寸大小为255×2⁷），在显示器上以1 920×1 080全屏运行模式下，本文算法、文献[3–4,7]的算法的帧率变化曲线。

由图12可知：本文算法的帧率远远高于文献[3–4]；文献[7]算法的平均帧率虽与本文算法相当，但其帧率变化非常频繁，尤其在第180 s和第350 s时刻附近，帧率出现了大幅度的降低，正好对应图12中漫游路径中的两次转弯——由于视点方向的突然改变，导致可视范围内的地形LOD瞬间变化，从而引起帧率直线下降；本文算法则继承了几何裁剪图的优点，在漫游中保持了平滑的帧率稳定性，同时，充分利用了GPU性能，达到了较高的帧率。

图13给出了层间裂缝消除前后的效果对比。

图13（a）中的几何裁剪图层间未进行共享边细分，则在层间出现了三角形状的“裂缝”；而如图13（b）所示，经过了本文方法的共享边细分处理，可以完美地消除“裂缝”现象。

图14给出了本文算法在某高原机场附近不同角度的渲染结果。从图14中可以看出，地形构造平滑，无“裂缝”现象出现，地形细节展现度较高，渲染效果逼真。

3 结　论

作者利用显卡硬件的最新特性，通过细分着色器自适应生成并渲染地形几何裁剪图的三角形面片，在优化渲染内容更新的同时，最大程度地减少了CPU向GPU传输的顶点数量。实验证明了本文算法能够明显提高地形渲染帧率和帧率稳定性。

然而，本文算法针对地形上特定区域（如河流、海洋等）的特殊效果渲染则比较困难—需通过指定相当多的控制点来划定区域边界。而这将影响特定区域的渲染效率。下一步，将针对此问题对算法进行改进，使算法能够更加完善。