一种基于线性四叉树的LOD模型生成方法

摘要

本发明提供一种基于线性四叉树的LOD模型生成方法，包括：对待绘制地形进行线性四叉树分割；待绘制地形的数据存储在二维数组中，线性四叉树中每一个节点信息通过索引从该二维数组中读取；对线性四叉树的叶结点信息进行存储；组织地形节点，使线性四叉树中的地形节点存储进一个一维数组中；在考虑静态误差和动态误差的基础上建立地形节点评价机制；对不同分割层级的相邻地形节点进行裂缝消除，得到基于线性四叉树的LOD模型。本发明是应用在计算机图形图像学领域中的地形简化方面，利用线性四叉树存储模型并结合使用二维填充曲线来组织地形节点，在充分考虑误差因素的基础上建立节点评价机制消除地形裂缝问题，能明显的提高地形绘制效率。

说明书

技术领域

本发明属于计算机图形图像学技术领域，特别涉及一种基于线性四叉树的LOD模型生成 方法。

背景技术

大规模地形场景的绘制以及三维真实感绘制技术一直是国内外计算机图形学领域关注的 热点。在目前的渲染方法中，渲染的速度由地形模型中纹理面数量的多少决定，并且为渲染 提供的光、质等渲染因子也受到模型中纹理面数量的限制，在此两种因素的影响下对地形的 绘制效果和渲染质感的影响进一步加深。而LOD(LevelofDetail，细节层次模型)技术正式 为了解决此类问题而提出，LOD简化技术在场景中的应用主要可分为两类：一类是直接利用 满足误差条件的顶点生成网格的细节层次模型；另一类是从DEM(DigitalElevationModel高 程数据模型)栅格数据出发按四叉分割或者二叉分割的方式生成规整的三角形网格的基于规 则网格的细节层次模型。现阶段对基于规则网格的LOD算法绝大部分是从这两个算法发展演 变而来。

在大规模地形场景的渲染过程中，当视点距某一物体较近时，物体绘制所使用的像素较 多，当视点距某一物体较远时，物体绘制所使用的像素较少。基于此种情况，在地形的绘制 过程中就没有必要使用大量的多边形片面去精确表示所占像素较少的物体细节。多细节层次 技术可以更好的实现三维复杂模型的实时动态显示效果，通过将三维物体通过用不同精度的 模型进行表示，并在此过程中根据视点位置的变化而选择不同精度的模型绘制成像，此种技 术可以大大提高渲染的速度和效率。判断通过三维可视化技术所绘制的场景是否能够达到实 时变化的效果主要着重于两点：一是所采用的计算机本身硬件的性能高低；二是绘制物体的 几何目标是否简单，这将直接决定实时可视化中的计算量。在目前的技术条件下受限于对计 算机硬件依赖度比较大的计算机图形制作系统的制图能力还比较有限，在这种情况的影响下， 对场景绘制渲染成像的过程中每帧所能绘制的原始几何模型即三角形数量也变得十分有限。 综上所述情况，实时复杂场景特别是大规模地形绘制的关键所在就是探索如何有效的降低几 何模型的复杂度。

发明内容

针对现有技术存在的问题，本发明提供一种基于线性四叉树的LOD模型生成方法。

本发明的技术方案是：

一种基于线性四叉树的LOD模型生成方法，包括以下步骤：

步骤1、对待绘制地形进行线性四叉树分割，每一个线性四叉树节点代表一个分割的地 形块即地形节点，其中距视点近的地形区域分辨率较高且分割层级越大，而远离视点的地形 区域分辨率较低，分割层级越小；

步骤2、待绘制地形的数据存储在二维数组中，线性四叉树中每一个节点信息通过索引 从该二维数组中读取；同时建立一个和所述二维数组大小相同的标志数组，此标志数组指示 线性四叉树节点的状态，如果一个线性四叉树节点需要被继续分割，则把相应的位置标记为 1，否则标记为0；

步骤3、对线性四叉树的叶结点信息进行存储：将叶结点位置通过基于十进制的Morton 编码表示形成十进制矩阵，叶结点的大小用该叶结点的深度表示；

步骤4、引入希尔伯特填充曲线来组织地形节点，使线性四叉树中的地形节点按照由顶 向下、分辨率低到高的顺序存储进一个一维数组中；

步骤5、在考虑静态误差和动态误差的基础上建立地形节点评价机制：若当前地形节点 的投影误差大于设定的屏幕误差阈值，则当前地形节点需要进一步分割，返回步骤1；否则， 当前地形节点满足投影误差要求，停止分割；

步骤6、对不同分割层级的相邻地形节点进行裂缝消除，得到基于线性四叉树的LOD模 型。

步骤3所述对线性四叉树的叶结点信息进行存储，具体如下：

步骤3-1、将叶结点位置通过基于十进制的Morton编码表示形成十进制矩阵；

步骤3-2、将十进制矩阵的行号和列号分别转换成伪码；

步骤3-3、计算地形Morton编码；

步骤3-4、使用Morton编码进行统一编码，每个叶结点都具有唯一识别的索引，将二维 的地形数据转化成一维，进而基于Morton编码生成线性四叉树。

所述步骤3-4的具体步骤如下：

步骤3-4-1、依次检查分割后的四个地形块的灰度值，若有一个地形块的灰度值与其他不 同，将这四个地形块的灰度值暂时赋以一个标志值，否则，直接移动到下四个地形块检查；

步骤3-4-2、第一轮完成以后再依次检查四个地形块的灰度值，直至最后，分割的所有地 形块的左上角的灰度值都相同，然后将带有标志的灰度值依次序统一保存，即生成线性四叉 树，并记录叶结点的地址码和对应的灰度值，遍历地形节点的计算量仅与地形区域大小呈线 性关系，叶结点的地址码即灰度值数组的序号。

所述地形节点评价机制的建立方法如下：

步骤5-1、根据人眼的可见角度、投影平面的高度、世界坐标系的单位长度与屏幕坐标系 的单位长度之比值、地形节点的几何误差、地形块的中心点到视点的距离确定地形节点的投 影误差；

步骤5-2、利用地形节点的投影向量与视线方向的夹角对地形节点的投影误差进行修正；

步骤5-3、根据地形节点的投影误差的修正值，确定线性四叉树分割准则即地形节点评价 机制：若当前地形节点的投影误差大于设定的屏幕误差阈值，则当前地形节点需要进一步分 割，返回步骤1；否则，当前地形节点满足投影误差要求，停止分割。

有益效果：

本发明不仅是对以往的经典LOD模型生成方法的一个有效改进和优化，在利用树型结构 存储数据节点方面提出一个高效的可避免重复存储的便利方式，并且利用视点相关评价系统 进行节点分割，能够有效实现地形的简化，此外还给出一个高效可行的裂缝消除方法，能快 速的消除细化分割所产生的裂缝。

采用LOD场景简化技术，对虚拟场景地形进行大幅优化，并将其应用到3D漫游系统中， 能够有效解决虚拟大规模场景渲染中的三角形数目问题，并加快地形场景的绘制速度，从而 提高场景漫游的逼真程度。

线性四叉树相对于传统四叉树存储模型只存储最后叶结点信息，包括叶结点的位置、大 小和灰度。叶结点位置通过使用Morton编码表示，目前最常用的是基于四进制的Morton编 码，但由于大部分编程语言并不支持四进制编码，所以在实际使用时还需要进一步转化为十 进制编码，这无形之中就影响了算法的运行效率，因此在此提出一种基于十进制的Morton编 码，此种编码规则可以保证在各种开发语言平台上顺利运行，保证算法的整体运行效率。

在分析误差因素的基础上建立决策评价机制。误差因素考虑静态误差和动态误差两个方 面。通过合理选取四叉树中的节点集合可以实现地形多分辨率的正确表达，节点评价体系是 地形多分辨率表达的天平，用以确定在实时动态显示过程中应该采用哪一级的分辨率标准。

在运用树型数据结构对地形进行多分辨率表示时，由于相邻数据节点的分割层级不同， 就会产生裂缝问题。在此采用去点法来解决裂缝问题，通过遍历分析相邻地形块间的层级等 级将细节层级高的一侧的分割点去掉，消除分割层级的差异从而消除裂缝问题。

本发明是应用在计算机图形图像学领域中的地形简化方面，利用线性四叉树存储模型并 结合使用二维填充曲线来组织地形节点，在充分考虑误差因素的基础上建立节点评价机制消 除地形裂缝问题，能明显的提高地形绘制效率。

附图说明

图1为本发明具体实施方式的对待绘制地形进行线性四叉树分割过程示意图；

图2为本发明具体实施方式的地形标记数组示意图；

图3为本发明具体实施方式的基于十进制的Morton码四叉树分解；

图4为本发明具体实施方式的Hilbert填充曲线填充示意图，其中(a)为第一步遍历，(b) 为第二步遍历，(c)为第三步遍历；

图5为本发明具体实施方式的透视原理示意图；

图6为本发明具体实施方式的裂缝产生原因示意图；

图7为本发明具体实施方式的裂缝消除原理示意图；

图8为本发明具体实施方式的基于线性四叉树的LOD模型生成方法流程图；

图9为本发明具体实施方式的对线性四叉树的叶结点信息进行存储流程图；

图10为本发明具体实施方式的地形节点评价机制的建立流程图。

具体实施方式

下面结合附图对本发明的具体实施方式做详细说明。

一种基于线性四叉树的LOD模型生成方法，如图8所示，包括以下步骤：

步骤1、对待绘制地形进行线性四叉树分割，每一个线性四叉树节点代表一个分割的地 形块即地形节点，其中距视点近的地形区域分辨率较高且分割层级越大，而远离视点的地形 区域分辨率较低，分割层级越小；

从整个完整的地形出发，递归的把地形不断的分割成相等的四个区域，分割的深度越大， 则得到的分辨率越高。即分割深度每提高一层，采样密度提高一倍。由于四叉树分割是个严 格递归的过程，父节点完全包含子节点。分割的过程是一个不断精细的过程，直至最后一步 时，视点所处的地形块被分割的最精细，显示质量也最好，而远离视点的部分分割的较粗糙。 通过这种方法，在不损失图像质量的前提下，渲染的三角形数量明显减少。对待绘制地形进 行线性四叉树分割过程如图1所示。

步骤2、待绘制地形的数据存储在二维数组中，线性四叉树中每一个节点信息通过索引 从该二维数组中读取；同时建立一个和所述二维数组大小相同的标志数组即地形标记数组， 此标志数组指示线性四叉树节点的状态，如果一个线性四叉树节点需要被继续分割，则把相 应的位置标记为1，否则标记为0，如图2所示。

在图2中，黑点表示节点需要继续分割，空心点表示不需要继续分割。地形大小尽量满 足(2ⁿ+1)×(2ⁿ+1)，这样可以保证最多可分割成2ⁿ×2ⁿ个网格。

步骤3、对线性四叉树的叶结点信息进行存储：将叶结点位置通过基于十进制的Morton 编码表示形成十进制矩阵，叶结点的大小用该叶结点的深度表示；

如图9所示，具体步骤如下：

步骤3-1、将叶结点位置通过基于十进制的Morton编码表示形成十进制矩阵，如图3所 示；

叶结点位置通过Morton编码表示，叶结点块的大小亦可用该结点的深度表示。由于传统 的Morton编码是四进制数编码，而目前大多数语言不支持四进制变量只能用十进制的长整型 表示，这就造成了资源的浪费。另外基于四进制的Morton编码算法在实现时还要开辟深度的 内存和外储空间，这就很大程度上限制了四叉树方法在计算机上的应用。所以在本实施方式 采用基于十进制的Morton编码进行四叉树节点的存储。

步骤3-2、将十进制矩阵的行号和列号分别转换成伪码；所述伪码的计算公式如下：

式中，MOD为取余函数，II为十进制表示的行号，I_j为行号的伪码，I_k为中间变量且初始 值为十进制行号II，k是判断变量，通过式(1)不断取余运算的迭代过程，得到行号的伪码 I_j，同理可计算列号的伪码J_t；

步骤3-3、计算地形Morton编码M；

M＝2×I_j+J_j(2)

步骤3-4、使用Morton编码进行统一编码，每个叶结点都具有唯一识别的索引，将二维 的地形数据转化成一维，进而基于Morton编码生成线性四叉树。

具体步骤如下：

步骤3-4-1、依次检查分割后的四个地形块的灰度值，若有一个地形块的灰度值与其他不 同，将这四个地形块的灰度值暂时赋以一个标志值，否则，直接移动到下四个地形块检查；

步骤3-4-2、第一轮完成以后再依次检查四个地形块的灰度值，直至最后，分割的所有地 形块的左上角的灰度值都相同，然后将带有标志的灰度值依次序统一保存，即生成线性四叉 树，并记录叶结点的地址码(此时为灰度值数组的序号)和对应的灰度值，遍历地形节点的 计算量仅与地形区域大小呈线性关系，叶结点的地址码即灰度值数组的序号。

步骤4、引入希尔伯特填充曲线来组织地形节点，使线性四叉树中的地形节点按照由顶 向下、分辨率低到高的顺序存储进一个一维数组中；

为了消除节点遍历的不连续性问题且为了提高效率，在此引入希尔伯特填充曲线来组织 地形节点，使四叉树中的地形节点具有一个特定的顺序。在未经处理之前的四叉树结点是以 二维数组的形式存在的，在经过使用Morton码进行统一编码后，每个结点都具有了唯一识别 的索引，这就将二维的地形数据转化成了一维的方式。图4示出了用Hilbert空间填充曲线组 织地形数据的初始几步网格顶点的索引号，(a)为第一步遍历，(b)为第二步遍历，(c)为 第三步遍历。地形数据经过Hilbert空间填充曲线组织后，它自顶向下，由粗到细地将各个分 辨率的四叉树结点存储到了一个一维数组中，这种方法实际上是把单一分辨率的数据变换到 多分辨率数据后再进行排序，保证了访问四叉树结点数据的速度。

步骤5、在考虑静态误差(地形起伏程度因素)和动态误差(视距变化因素)的基础上 建立地形节点评价机制：若当前地形节点的投影误差大于设定的屏幕误差阈值，则当前地形 节点需要进一步分割，返回步骤1；否则，当前地形节点满足投影误差要求，停止分割；

如图10所示，地形节点评价机制的建立方法如下：

步骤5-1、根据人眼的可见角度、投影平面的高度、世界坐标系的单位长度与屏幕坐标系 的单位长度之比值、地形节点的几何误差、地形块的中心点到视点的距离确定地形节点的投 影误差；

如图5所示的透视原理，离视点越远的物体在屏幕上的投影越小，反之越大。

地形节点的投影误差如下：

$e_{screen}=\frac{h·{\mathrm{\lambda e}}_{node}}{2d·tan\left(\frac{\alpha }{2}\right)}---\left(3\right)$

其中，人眼的可见角度为α，投影平面的高度为h，世界坐标系的单位长度与屏幕坐标系的 单位长度之比值为λ；对于几何误差为e_node的四叉树节点，地形块的中心点到视点的距离为 d，且中心点在视线向量上，e_screen为按照空间几何关系，e_node投影到屏幕上的像素误差，即 地形节点的投影误差；

步骤5-2、利用地形节点的投影向量与视线方向的夹角对地形节点的投影误差进行修正；

上述公式(3)并没有考虑投影向量与视线方向的夹角(即角度因素)，远离视线方向的结 点的几何误差相对于在视线方向上的几何误差更不容易被人眼察觉，因此，假设地形结点的 投影向量与视线方向的夹角为β，修正公式(3)后，可以得到：

${e^{\prime }}_{screen}=\frac{h·{\mathrm{\lambda e}}_{node}·cos\beta }{2d·\tan \left(\frac{\alpha }{2}\right)}---\left(4\right)$

其中，β为地形节点的投影向量与视线方向的夹角，e'_screen对e_node投影到屏幕上的像素误 差e_screen即地形节点的投影误差的修正值；

步骤5-3、根据地形节点的投影误差的修正值，确定线性四叉树分割准则即地形节点评价 机制：若当前地形节点的投影误差大于设定的屏幕误差阈值，则当前地形节点需要进一步分 割，返回步骤1；否则，当前地形节点满足投影误差要求，停止分割。

对于某一地形节点，其分割准则为：

即时需要细分，由于ε取决于地形块中心点到视点的距离d，变换该式，可 以得到：

$\frac{d}{cos\beta }<\frac{h·{\mathrm{\lambda e}}_{node}·cos\beta }{2d·tan\left(\frac{\alpha }{2}\right)}---\left(5\right)$

其中，在投形块的中心点到视点的距离d和屏幕误差阈值ε一定的情况下，地形节点的投影 误差的修正值是固定不变的；

设为ε条件下每个分辨率层次的最小允许视距，该值可以在预处理中按照自下 而上的顺序提前计算出来，因此在实时绘制时仅需要计算地形块的中心点到当前视点的距离 d以及地形节点的投影向量与视线方向的夹角β，即确定当前地形节点是否需要细分，得到 决策评价机制：

步骤6、对不同分割层级的相邻地形节点进行裂缝消除，得到基于线性四叉树的LOD模 型。

在运用树型数据结构对地形进行多分辨率表示时，由于相邻地形节点的分割层级不同， 就会产生裂缝问题。如果不加以处理，势必影响渲染效果的平滑度。

图6显示了裂缝产生的具体原因，由于左边的地形块精度高于右边的地形块，所以A、B 两点在绘制右边地形块时被忽略掉，导致两个地形片出现裂缝。

消除A、B两点处的裂缝的方法是将左边高精度地形块中的A、B两点去掉。即在渲染 左边地形块的时候，如果与A相邻的右边地形细节层次小于左边，则在生成渲染列表的时候 抛弃点A。其裂缝消除原理如图7所示。