1 引言
“将地球搬进电脑”是一个复杂的科学命题，其中的一个子问题是：怎样对地面进行细致、平滑、不失真实感的表达。人们最初的研究是集中在栅格或者说体元方面(龚健雅，1997)。随着计算机硬件水平的提升，地形表达趋向于开发适应CPU和GPU协作模式的算法(HyeongYeop Kang et al. 2014)。针对地形研究的科学问题主要分为两个：地形模型的数据组织与实时渲染。
三维地形的组织方式主要有两种——规则格网(Grid)和不规则三角网(TIN)，二者各具优势与缺陷(B.YANG et al. 2005)。Grid具有结构简单、计算方便等特点，更加适宜于表达大面积平坦地区。TIN则使用三角面片来表达地形表面，更适合于表达起伏较大的地区。通过地形复杂度阈值来划分两种模型界限的思想产生了最简单的混合地形模型，但仍需改进。不同数据源的瓦片在重合边的插值上可能出现在不匹配，产生间隙;判定TIN与Grid哪个更适宜也是难题;多分辨率混合地形数据具有不同的LOD方案，在构造不同地块LOD的过程中误差在所难免。
2 基于瓦片融合的混合模型表达
B.YANG等人于2005年提出集成TIN和Grid的地形模型：根据不同分辨率对不同数据源分别建立了不同的LOD规则，在分割与合并时消除了裂缝，达到了真正意义上的数据融合。研究区域中，道路采用TIN来表达而其他的地形区域采用Grid。实验表明，算法提高了地形可视化效率，做到了既精细表达复杂的地表，又减少了数据规模，大幅提高了三维地形场景的渲染速度。B.YANG等人在之后的研究中提出了若干拓扑修正方法，进一步完善了算法。
2.1 GRID与TIN的边缘融合
对于Grid瓦片，算法备选LOD方案有四叉树分割方案(Roettger et al. 1998)和最长边的三角二分法分割方案(Lindstrom et al. 2002)。其中，三角二分法表达地形起伏变化时更为合适，因为三角二分法的基本单元同TIN一样为三角面片，这就给之后的融合带来方便。三角二分法就是在细分网格的时候连接三角形最长边的中点并剖分成两个新的三角形。而对于TIN瓦片的LOD方案采用边缘收缩迭代算法(Hoppe et al. 1996)，该算法的就是在细分时始终处理最邻近的两个点。算法可以保留原始数据拓扑关系的层次结构，在分辨率更新时快速构造出三角网。
图 1. 基于Grid和TIN的细分方案——四叉剖分(左);三角二分(中);边缘收缩迭代(右)
因为邻近两个瓦片公共边的LOD层级不同，在两个以不同数据组织方式构造出的地形瓦片之间，会出现明显的缝隙。可将对应瓦片构造点设置为活动的，在索引到该点时，为其插值出一个与邻边LOD层级相同的控制点来保证不产生裂缝。
2.2 构造索引二叉树并为其编码
地形数据分块存储的关键步骤是为整个分块LOD建立索引。根据一个瓦片可能具有的两种结构的特点，二叉树是最好的索引选择。根节点代表整个地块的数据组织形式，两个子节点分别代表细化后瓦片的组织形式。这一步对数据的存取效率至关重要，二叉树的一般存储方式为链表，算法提出了一种新的二叉树编码方法：基于括号的二叉树编码，将二叉树存储为二进制数列，索引时只需寻找与左括号相对的右括号，节省了存储空间，增加了读取速度。
3 基于凸包处理的混合模型表达
基于瓦片融合的地形表达，实际应用不广泛，因为确定地形需要用TIN还是Grid瓦片不好界定。更多的情况是，TIN和规则格网已经准备好了，如何把二者融合起来。M. Bóo等人于2007年提出了一种思路：将TIN镶嵌进规则格网中，在建立LOD时对TIN边界凸包集合进行细分与合并。该方法在后续研究中进行了改进，包括提出凸包限制的HM模型(Montserrat Bóo et al. 2009)、动态修正地形的EHM模型(E.G. Paredes et al. 2012)等。
该方法创建了自适应的TIN镶嵌规则进行无缝结合，使用简单的数据结构表示混合模型TIN边界，对不同类型的瓦片放在不同的GPU流水线内，提高实时渲染效率。算法适合表达局部精细的地形，对不同精度的数据有良好的集成性，应用更为广泛。
3.1 GPU与CPU的协作模式
这个算法产生的时间节点在2007年，图形处理单元的迅速发展刚刚开始，GPU对于图形的计算能力以及多核并行处理的特点被世人所认知，业界开始关注GPU对于地形渲染和三维渲染方面性能的增强。作者提出GPU与CPU的协作渲染思路，即由CPU完成数据层次分类与预处理，由GPU进行分块的图元并行渲染，大大提高了渲染效率。
在地形分块的时候，镶嵌的TIN所覆盖到的格网与未覆盖到的格网在处理方式上有较大不同，只有与TIN相交的格网才需要对其进行凸包处理。进一步，与TIN相交的格网又分成部分相交与全部覆盖。根据TIN与格网的空间逻辑关系，将格网单元分成NC(无相交)、PC(部分相交)、CC(全部覆盖)三种，分别制定不同的渲染策略。
3.2 TIN凸包镶嵌策略
对于CC瓦片，不需要改变TIN，在构建LOD策略时只需要将TIN策略应用在这些瓦片上即可。对于NC，只需要对其构建基于规则格网的LOD策略即可。重点是：对于PC瓦片，需要将TIN边界与格网边界进行“镶嵌”操作。“凸包”的定义是凸多边形形成的点集。对于TIN本身就是是凸包的PC瓦片，只需要将TIN上每一个点连接到与其最接近的格网边界点上即可。
图 3. 纯凸包TIN镶嵌过程(左)、1/4尺度凸化过程(中)、当前尺度凸化过程(右)(By M.Bóo 2007)
而部分TIN并不是凸包，那么需要对这部分TIN进行凸化后再实行最邻近连接的原则，进行镶嵌。具体凸化过程就是在凹巢中建立符合TIN规则的三角网。当凸化好的2*2瓦片在LOD构建时需要合并成一个瓦片单元格，需要对上一步已经凸化好的四个瓦片组合再凸化。在计算机存储时，需要构建合适的编码规则，具体过程见参考文献[1]。
4 基于GPU细分的混合模型表达
GPU/CPU异构混合并行系统以其强劲计算能力、高性价比和低能耗等特点成为新型高性能计算平台，但其复杂体系结构为并行计算研究提出了巨大挑战(卢风顺，2011)。 2014年，HyeongYeop Kang等人提出使用GPU 细分进行多分辨率地形渲染方法。随着近年来 GPU 处理水平的迅速上升，CPU 需要处理的网格将越来越粗化，精细处理将更多地移交GPU。
该算法是混合地形模型研究领域的最新成果。作者利用LOD因子唯一标识瓦片信息，通过扩大单瓦片的点数处理量，增加了GPU单图元处理器的处理量。算法基本上解决了混合模型边界问题，带来了性能的大幅度提升，引领了处理运算与动态渲染日趋GPU化的时代潮流。
4.1 以GPU为主的协作模式
考虑到GPU计算性能越来越强，把基础图元传输进独立的GPU单元，允许一个单元处理更大量的数据，减少CPU预处理部分的工作量，达到指数性的性能提升。该算法只利用CPU对地形进行大致的划分(513*513的实验区域被仅被划分成4层)。
4.2 细分因子与LOD策略
对于一个独立四边形块(patch)，需要一组变量唯一标识其内部信息。作者提出使用Edge值与Inner值来标识。其中Edge值有4个，代表四边形补丁每一条边的细分度，用来无缝连接相邻补丁;而Inner值只有两个，代表该四边形补丁自身水平与竖直方向的细分度。整个原始地形数据将由CPU分割成粗四叉树，对每一个叶节点建立细分因子来唯一标识，放到独立的GPU处理管线渲染。每个节点内部的 LOD —X(Inner)相互独立;每个节点的边缘 LOD —X(Edge)必须和相邻节点相匹配。相比传统的纯四叉树策略来说，这种LOD策略细节表现要更强。
(1)Inner LODs：每一个瓦片的 Inner LOD 层级取决于该瓦片到视点距离最近的点。单瓦片被细分到 64 层以上时，GPU 将该瓦片剖分成四个瓦片放在四个不同的管线渲染。
(2)Edge LODs：一旦叶节点的 Inner LOD 确定下来，Edge LOD 将自动生成，原则是尽量减少三角形的数量;使用广度优先算法遍历整个四叉树，使每一条边缘上的 Edge 值都相等。
图 4. 细分因子图示
5 结论与讨论
本文从基础的Grid与TIN两种基础模型的比较开始论述，归纳出三种具有代表性的混合地形模型——基于瓦片融合的混合模型、基于凸包处理的混合模型及基于GPU细分的混合模型。
基于瓦片融合的方法思路简单，编码巧妙，但难以直观区分TIN与规则格网应用范围，对大规模的数据融合比较困难;基于凸包处理的方法牢牢抓住镶嵌的思想，融合了不同类、不同分辨率的数据源，但在过渡区域会产生条带状三角形，有损真实感;基于GPU细分的混合模型解决了精度统一问题，减少了CPU处理量，提升了地形协作渲染的效率，紧紧跟随计算机硬件迅猛发展的时代潮流，是一套相对成熟的地形模型数据组织与渲染体系。
三种不同的混合地形模型在应用方面各具优势，寻找出待建模地形数据的特点和最需要表达的内容，是选择哪种最适宜地形模型来表达的最关键问题。
参考文献：
[1]. 李德仁, 李清泉. 一种三维GIS混合数据结构研究. 测绘学报. 1997.5. Vol.26(2)
[2]. 龚健雅, 夏宗国. 矢量与栅格集成的三维数据模型. 武汉测绘科技大学学报. 1997.3. Vol.22(1)
[3]. 卢风顺, 宋君强, 银福康, 张理论. CPU/GPU协同并行计算研究综述. 计算机科学. 2011.3. Vol.38(3)
[4]. M. Bóo • M. Amor• J. Döllner. Unified Hybrid Terrain Representation Based on Local Convexifications. Geoinformatica (2007) 11:331–357.
[5]. E.G. Paredes , M. Bóo , M. Amor, J.D. Bruguera & J. Döllner. (2009) Extended hybrid meshing algorithm for multiresolution terrain models. International Journal of Geographical Information Science, 26:5, 771-793.
[6]. B. Yang , W. Shi & Q. Li (2005) An integrated TIN and Grid method for constructing multi‐resolution digital terrain models, International Journal of Geographical Information Science, 19:10, 1019-1038.
[7]. Montserrat Bóo & Margarita Amor (2009) Dynamic hybrid terrain representation based on convexity limits identification, International Journal of Geographical Information Science, 23:4, 417-439
[8]. Uwe Weidner , W. Forstner. (1995) ISPRS Journal of Photogrammetty and Remote Sensing, 50(4): 38-49.
[9]. HyeongYeop Kang • Hanyoung Jang • Chang-Sik Cho • JungHyun Han. (2014) Multi-resolution terrain rendering with GPU tessellation. Vis Comput. Published Online May 2014.
[10].Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: Bdam batched dynamic adaptive meshes for high performance terrain visualization. Comput. Graph. Forum 22(3), 505–514 (2003).
[11].Evans,W.,Kirkpatrick, D., Townsend, G.: Right-triangulated irregular networks. Algorithmica 30(2), 264–286 (2001).
[12].Eric Bruneton and Fabrice Neyret.: Real-time rendering and editing of vector-based terrains. EuroGraphics 2008. Volume 27 (2008), Number 2.
[13].Feng, W.W., Kim, B.U., Yu, Y., Peng, L., Hart, J.: Featurepreserving triangular geometry images for level-of-detail representation of static and skinned meshes. ACM Trans. Graph. 29(2), 11:1–11:13 (2010).
[14].Jang, H., Han, J.: Feature-preserving displacement mapping with graphics processing unit (GPU) tessellation. Comp. Graph. Forum 31(6), 1880–1894 (201).
[15].Pajarola, R., Gobbetti, E.: Survey of semi-regular multiresolution models for interactive terrain rendering. Vis. Comput. 23(8), 583–605 (2007).
[16].Schneider, J., Westermann, R.: GPU-friendly high-quality terrain rendering. WSCG 14, 49–56 (2006).
[17].Tatarchuk, N.: Dynamic terrain rendering on gpus using real-time tessellation. In: Engel W. (ed.) ShaderX 7: Advanced Rendering Techniques. Charles River Media (2009).
[18].Wagner, D.: Terrain geomorphing in the vertex shader. In: ShaderX2: Shader Programming Tips and Tricks with DirectX 9.0, pp. 18–32. Wordware Publishing, Inc., Texas (2003)
[19].Losasso, F., Hoppe,H.: Geometry clipmaps: terrain rendering using nested regular grids. ACM Trans. Graph. 23(3), 769–776 (2004).
[20].Pajarola, R.: Large scale terrain visualization using the restricted quadtree triangulation. In: Proceedings of the conference on Visualization 98, pp. 19–26. IEEE Computer Society Press, LosAlamitos (1998).
作者简介：谈心，南京大学地理与海洋科学学院
声明：中国勘测联合网登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述，文章内容仅供参考。
