三维空间建模方法之LOD模型算法(二)

在上一篇文章中，我简单介绍了LOD模型，以及LOD模型的一些分类，不过由于时间紧凑，所以并没有说下去，这次继续写关于LOD模型的文章。

根据结构的不同我们可以简单的把LOD模型划分为下面三类。

1. 基于TIN的层次结构
2. 基于Grid的树结构
3. 混合结构

如图：

基于TIN的层次结构

层次模型生成算法

用一分三的方法在TIN中移去或增加点，来构造层次TIN模型。该算法的时间复杂度为O(Nn)（N、n分别为层数和节点数）；

自适应层次模型

该算法将三角形的分裂分为5种情况；

渐进模型生成算法

该算法通过一系列的顶点分裂与合并，实现对原始模型的变换，从而构建不同分辨率的LOD模型，能严格控制复杂模型的简化误差，并产生较好的图像效果。

树结构LOD模型算法

四叉树剖分算法

通过递归方法对地形进行自顶向下的四叉树分裂，如下图

二叉树剖分算法

实质是将矩形地形区域按对角线划分成两个直角三角形，判断每个直角三角形的误差是否大于给定的阈值，若不大于，则使用该直角三角形的直角顶点和斜边的中点的连线对该三角形进行再次划分，使其变为两个三角形，重复上述方法直到所有的三角形的误差都小于给定的阈值误差，则剖分操作停止。

如下图，根层(L=0)三角形T=(Va,V0,V1),下一层(L=1)是中点连线劈开的，其余层次都是按此规则递归劈开而成。

混合结构LOD模型算法

基本原理：将原始建模区域M分成n个子块，各子块Mi分别采用TIN模型或Grid模型来独立构建LOD模型Mi’，然后对构造结果进行合并，生成最后的全区域LOD模型M’；