基于细节层次模型的多面体优化探讨

赵迪　陈哲夫　莫操湖　金古月

摘要：细节层次模型（Levels of Detail.LOD）可以缓解优化大规模空间数据的实时可视化渲染问题。本文基于LOD技术的基本原理，对优化过程中的模型简化、测量近似误差、视觉误差估计等方面进行了深入探讨，并针对各种算法在多面体简化方面的效率进行比较，阐明了各自的优缺点及应用环境。

关键词：多面体简化 LOD 可视化

1简介

大规模空间数据的实时可视化渲染计算和存储需要大量的多面体显示。1976年，Clark认为较远地方的不清楚视觉效果可以用简化的几何图形代替，即细节层次模型（LOD）。也就是说，在观察者视野边缘地区的或者处于运动状态中的物体可以用简化后的多面体描述。因此，目前主流软件引入此种理念支持LOD技术的管理行为，一般是在多面体集合中归纳统计的几何共性然后建模。本文主要針对3种支持LOD技术的最新算法进行比较，对执行过程和效率进行直观判断，阐述每种算法的优势和缺点，并指明每种算法最适宜的运行环境。

2 LOD

多面体简化的前提是不改变原始目标的基本外观特征，理想结果是一个整体的系列简化在此环境下的LOD称为Geomorphe模式，据此生成的数据结构能够增强LOD显示的连续性，不易察觉相邻简化物体的不同。但是，如果LOD的数量较少，则相邻LOD间的转换就会明显停顿，破坏LOD显示的连续流畅性。此外，为保持框架比例的完整性，需要寻找完善模型和显示时间间的最佳平衡点。

多面体的简化结果必须保留原物体的基本外观形状特征，因此相关算法的研究重点在于目标物体的共面、棱边、共点等方面。测试共面时，算法对于两法线间的夹角有一个临界值，若两平面法线间的夹角大于该值则认为此两面不共面。该值越高，则认为有更多面共面并被简化。该值一般通过观察者的视觉特征估计，但误差较大且没有统一模型支持。

为优化控制简化效果，应考虑测量局部近似误差的使用。一些算法用局部误差或用到原始网格的直线距离来估算误差，以在几何结构上保证简化不超过某一限值。此外，算法执行过程中允许用户自主设定简化数量的极值和保留多面体的数量，该值的设定需要实际经验支持。一些算法为保留某一关注区域而大幅度简化其余部分，即简化数量随网格大小的不同而随之变化，也就是说，这些算法主要从视觉语义上考虑并可由用户控制。总而言之，离观测者近的区域选取低层次结点，离观测者远的区域采用高层次结点。

3算法分析

3.1任意网格的多重决定分析

该算法构造一种网格的多重选择表示法，包含简单的基本网格和一系列描述网格细节系数的地貌图形。算法要求输入网格通过递归细分构造，即每个三角形用4-to-l模式细分，直至达到所设定的限值。

该算法比较适用于顾及拓扑性质的环境，可以利用到原始网格的距离估计近似测量误差，过程主要有四步：（1）划分：在原始网格中用多种子线条构造Voronoi曲线图，然后在网格的对偶曲线中寻找算法结构，曲线被Delaunay三角化;（2）生成基本网格：采用Harmonic maps法拉直边缘线做出基本网格，保证网格沿每个面连续，使网格细节系数最小;（3）重采样：再次用4-to-l模式对基本网格重采样，直到基本网格与原始网格相似为止;（4）多重决定分析：将连续网格编码为多重决定分析算法。

该算法的简化范围广泛，并且一些细节可以被加入到指定区域，但操作复杂，尤其是提炼一个有效网格的进程。

3.2进化网格

该算法的简化是通过运用消除边缘线算子，生成一个简化的基本网格和一系列分开的顶点。该算法主要考虑目标的颜色、结构、网格表面法线等不连续信息，目标是（1）保证简化网格与原始网格相似;（2）在边缘线上可以设置零剩余长度和用合适比例三角化;（3）不支持颜色和结构的不连续简化;（4）不支持拓扑和法线的不连续简化。

主要步骤如下：（1）缘线分类将简化过程的图形损失降到最小;（2）在简化开始处对边缘线应用消除算子，记录不相连顶点;（3）在两个初始顶点和边的中心点里选取新顶点位置，取离原始网格最近的点为新顶点;（4）重新确定整理边缘线损失清单;（5）如果清单是空的或者下一个简化损失超过某限值，则终止算法并返回最终简化网格（6）否则跳到第二步，重复。

该算法执行效率较高，并且由于考虑目标物体的颜色和结构，一般效果也较好。

3.3包络线简化

该算法保留平面区域和棱边，仅用几何结构控制简化，不用误差测量，偏移量由用户设定且保证相邻平面相交。然后在这两个表面间再做一个新的表面，唯一约束条件是与之前两个表面都不相交。相交的表面必须移向原始网格直到证实有足够的空间，则在棱边附近两个表面间的空间越小做出的简化越少。

主要步骤如下：（1）沿法线向顶点偏移外部表面，偏移量假定最终偏移量的一部分;（2）若顶点和表面相交则取消向顶点的移动;（3）重复（1）和（2），直到若表面不相交偏移量就不会再增或者偏移量到达理想值为止;（4）对内表面重复（1）和（3），对边界区域建立包络线。

该算法的优点是没有测量误差，可以用包络线来控制简化，但计算过程复杂，尤其是合适包络线的构建。

4结论

综上所述，大部分算法都有各自的简化方式，但基本过程相同，即寻找共面区，然后简化，寻找棱边并保留。但无论使用哪种算法，在预测简化的数量和设定各个参数的真值前都需要做大量实验。并且，到目前为止，尚未有一种算法用人的视觉来设置参数，LOD的生成在很大程度上是一种保留行为模型。另一方面，物体的复杂性不断增加如果把结构和光的信息添加进去会产生更加切合实际的透视图，但执行速度势必受到影响，所以在二者间如何寻求一个平衡点是需要进一步考虑的问题。最后，LOD的创建和选择应结合渲染背景管理技术，对特殊背景选择简化数量时，背景的分布和可视化关系对简化过程可能有较大帮助。

参考文献

[1]张毅，吕秀琴.大规模点云内外存调度绘制技术[J].计算机工程，2014，40（1）： 49-54.

[2]林继承，万旺根，崔滨等，一种超大规模地形场景的实时渲染算法[J].计算机仿真，2009，26（11）：224-227.

[3]郑顺义.基于三角网无缝拼接的三维重建[J]，武汉大学学报（信息科学版），2009，34（1）： 15-19.

[4]王芳，丛文静，祝海涛，基于顶点法向量重要度的模型简化算法研究[J]计算机与数字工程，2011（7）：6-8.