渲染一块很大的地面时候，怎样绘制地形的网格（一）简略综述
几年前的一个简单整理，可能不是很完善。
问题的范围：大规模的、高精度需求的地形绘制。
地形数据（DEM神马的）是以四叉树方式管理的，四叉树的叶子是一个个的数据块，这里讨论怎样绘制地形块的网格。
方案一：规则网格。直接用规则网格绘制整个地形块，地形块以四叉树方式组织。在预处理阶段计算每个地形块的误差，渲染阶段依据地形块和视点的距离选择合适的地形块绘制。
这种方法实现简单，而且LOD选择是在四叉树上进行的，一个地形块仅需要存储很少的误差数据，基本不会增加数据量，但是最大的问题是需要绘制大量的冗余顶点，从而使得绘制效率低，特别是以较高的精度绘制大规模的地形数据集的时候，基本不会这么干。
方案二：简单评价准则的规则网格。这一类算法代表性的方法是Geoclipmapping（Losasso F, Hoppe H. Geometry clipmaps: Terrain rendering using nested regular grids），此类方法最大的特点是不计算不同LOD的误差，而仅仅以地形和视点的距离为依据进行LOD的选择，由于不存储LOD选择信息，也就不会增加数据量，但是这种方法无法保证绘制精度。类似的方法还有文献（Iain C. DirectX 11 Terrain Tessellation. White paper, NVIDIA, January 2011.）描述的以硬件曲面细分实现的方法。
方案三：基于GPU的非规则、半规则网格方法。非规则网格方法的代表性方法是BDAM (Cignoni P, Ganovelli F, Gobbetti E, et al. BDAM - batched dynamic adaptive meshes for high performance terrain visualization )，这种方法需要构建非规则的三角形索引，需要较大的数据量，因此不适合应用于此。半规则网格方法的代表是Chunk LOD（Ulrich T. Rendering Massive Terrains Using Chunked Level of Detail Control ）。尽管Chunk LOD需要的索引要比完全的非规则网格少很多，但是仍然需要很大空间存储；其次，该方法直接把地形数据集成到了简化网格中，尽管绘制效率高，但使得数据只能应用于绘制，在其他应用中，如地形分析，需要将原来的无损数据再复制一次，数据量很多。
方案四：基于GPU的规则/半规则混合方法。代表性的方法有Raster（Bosch J, Goswami P, Pajarola R. RASTeR: Simple and Efficient Terrain Redering on the GPU）和4-8网格（Hwa L M, Duchaineau M A, Joy K I. Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies）的方法等。这些算法本质上沿袭了BDAM算法的思想，即在整个数据的组织上，依然使用半规则方式（二叉三角树）管理，但是二叉三角树的节点不再是单个三角形，而是批量化的三角形，即三角形簇，只是BDAM算法使用非规则网格绘制单个节点，而Raster方法和4-8网格使用规则网格来绘制。使用规则网格优点是实现简单，预处理时间短，而且由于所有不同深度节点的连结方式都相同，仅用很少的参数就可以表示一个节点，因而表示整个数据集所需要的数据也不多。
方案五：光线投射，这个不是网格了。。。光线透投射在这里是一种特别有吸引力的方法，因为有的光线投射算法不需预先计算的辅助就能进行绘制。Maximum mipmap（）是一种比较可靠的方法，它所需要的辅助数据可以在绘制过程中实时计算，因此不会占用数据集的存储空间，同时能够保证绘制精度，不会出现绘制错误。
光线投射的缺点也相当明显，一是效率较低，这又包含两方面原因，首先是相对于网格绘制方法，绘制效率较低，这是因为当前GPU是为光栅化绘制方法而设计的，光栅化方法有很多优化和硬件支持，而光线投射仅仅是利用GPU通用编程能力实现，效率自然要低一些。我测试了一下，光线投射大概和非简化的规则网格的性能差不多。。。其次是构建最大值金字塔（看Maximum mipmap那个文章）的效率也不高，构建过程本身十分迅速，但是GPU的状态转换相当耗时，构建一个2048×2048地形块11级Maximum Mipmap需要5ms。。。。。二是构建Maximum Mipmap要多占用三分之一的显存。
总结下，相对来说，方案4是坠吼的方法
说完了网格还有纹理、遮挡、压缩、调度什么的，以后再说。。
额，发现网格还没说完，网格组织是一方面，不同LOD之间的网格的“缝合”也是一个很麻烦的问题，下次说