网格简化技术研究报告
网格简化技术研究报告
lvweiwolf
问题及场景
在超大规模场景环境中，为了生成高精度的塔型结构，在设计团队的努力下，采用了分阶段简化铁塔与绝缘子串模型的技术手段，并根据不同的应用场景需求，在各个层次上提供相应的细节刻画。
简化模型要求速度快、质量高、文件体积小等特点。
网格简化的算法分类
删减法
删减法是目前算法中应用广泛的一种模型简化操作。该方法通过反复依次筛选作用相对较小的几何元素并进行重新三角化处理，最终实现对模型结构的优化。根据所涉及几何元素的不同类型，通常将其划分为顶点删除法、边折叠法以及三角面片折叠法等多种具体实施方式。
采样法
采样法第一步将节点或单元放置于模型表面或其三维网格中；接着通过物理或几何误差评估标准进行位置优化；最后在特定约束条件下产出尽可能与原始节点和单元相匹配的简化版本。该方法特别适用于无折痕、锐利边缘和非连续区域的光滑曲面建模，在处理非光滑表面时效果欠佳
自适应子分法
基于构建最简化的基准网格模型（Base Model），该算法遵循特定规则对三角面片进行持续执行三角面片的细分操作，并通过不断重复此过程而生成一系列细节层次递进的细分网格。直至生成的新旧网格间误差降至设定阈值。该算法具有结构简单且易于实现的特点，并且主要应用于那些便于获得基准网格的情形（例如地形建模等场景）。然而，在处理包含尖锐角和复杂折线边界特征的对象时表现欠佳。
顶点聚类法
该算法基于特定的准则对原始网格模型中的多个相邻顶点进行整合处理，在去除了由此产生的退化三角形后实现了对原始面片数量的有效缩减，并使整体网格结构得到优化以达到最佳效果的目的。如图所示，在实际操作中将四个被聚类的顶点整合为一个新的代表节点并去除相应退化的三角形结构后能够显著降低整个模型的数据规模同时又能较好地保持其几何特性。进一步而言边折叠法可视为一种特殊的两步式节点融合操作其核心思想与传统的节点聚类方法具有相似之处。值得注意的是该算法不仅可以处理任意拓扑类型下的网格数据而且其计算流程相对简洁运行效率较高但同时也面临着如何有效控制因节点融合所带来的几何畸变这一关键挑战因此在实际应用中往往需要结合特定场景来权衡精度与性能之间的关系。
多边形合并(Polygon merging)
该几何处理方法通过将近似共面的三角网格单元聚合成一个平面区域后进行重新三元化处理, 以减少顶点数量及面片数量为目标, 并可称为面向聚类（Face Cluster）及超级表面（Superfaces）的方法. 此方法在聚合和平面上再三元化的过程中可能会导致孔洞结构的变化, 因而无法确保简化前后模型的拓扑关系保持不变.
简化算法的误差测度（度量质量和误差）
该指标用于量化模型精简过程中的质量与偏差程度，并对整个精简流程及其最终结果发挥着关键作用。大多数精简策略基于基于Object\text{-}space的一维或多维几何偏差（Geometric errors）来衡量其效果。而部分视图相关的策略则会将Object\text{-}space中的偏差转化为Screen\text{-}space中的数值作为评估标准。此外，还有些方法会同时考虑模型的颜色、法线向量以及纹理参数等因素带来的偏差（Attribute errors）。
几何误差
几何误差测度常用欧氏空间的距离来衡量。常见的形式包括两点之间的距离、点与面之间的最短距离以及两平面间的垂直距离等多种形式。
在现有算法中常被用来度量顶点与表面之间、两个表面之间的最小距离作为几何误差测度，在这种情况下该测度即为两个模型所有顶点对中最小间距的最大值。
给定欧式空间的两点集
，
，Haousdorff距离就是用来衡量这两个点集间的距离。
算法过程：
该算法的时间复杂度是O(n，m)，其中n和m分别为集合A和集合B中的点数。
屏幕空间误差计算
主要依赖于将对象空间中的几何误差通过特定变换映射至屏幕空间中以评估视觉效果
属性误差（材质、纹理）
网格模型上的三角面片及其相关的法向量、纹理坐标以及顶点颜色被视为重要的属性参数。在网格建模中，默认情况下会使用RGB三元组（r,g,b）的形式来描述表面颜色，并规定每个分量的取值范围在[0.0, 1.0]之间。其中一种常用的方法是通过欧氏空间中的几何距离计算不同颜色之间的差异程度。假设经过简化处理后的两个几何体M₁和M₂各自具有RGB颜色特征（r₁,g₁,b₁）与（r₂,g₂,b₂），那么两个简化模型之间的颜色差异度d_c可用下式计算：
两个法向量的误差距离dn通常采用角度值进行度量：
实体表面的纹理坐标由(u, v)坐标参数对代表三维空间中的顶点与二维纹理平面之间的映射关系。其数值范围通常限定在[0, 1]区间内。主要采用基于欧氏空间的距离计算方法来评估纹理坐标的差异程度。
简化算法的约束条件或运行条件
在模型简化过程中或当简化算法运行时，常常会涉及一些限制条件；这些限制条件进而影响着所采用的技术、算法运行效果以及模型的简化结构等。
细节层次（LOD）
对于各种简化细节层级的LOD模型管理技术可划分为离散LOD、连续LOD以及视点相关LOD技术。
参考文献
连续LOD技术相较于传统离散LOD技术是一种改进和发展。不同于离散LOD技术的特点在于其各层次简化模型并非预先构建而是通过构建特定的数据结构来进行编码存储，并在实时显示运行过程中动态生成相应的细节层次。因此该方法能够实现更高的LOD粒度表示占用的空间相对较小并且能够在较短的时间内完成相关计算操作这使得运行过程中的画面呈现较为连贯但同时也导致实时渲染速度会受到一定程度的影响
简化模型的拓扑结构保持
如何在简化过程中保持网格模型的拓扑结构不变？这成为区分不同简化算法的关键标准之一。
主要成熟算法
删减算法
最早的删减算法是由Schroeder及其团队于1992年提出的一种基于顶点删除的方法。随后Hoppe提出了基于能量法的边折叠简化算法，在这一框架下确定了最优的折叠顺序并计算出各顶点的新位置。Schroeder等进一步发展了该类方法，并考虑了非邻接顶点对的删减问题。在此基础上他们还提出了基于虚边的概念——即所谓的"双线"——来实现更为复杂的删减操作。此外Hamann及其团队与Gieng等人共同开发了一种三角形折叠算法，在理论上相当于进行了两次连续进行的边折叠操作。该方法因其较高的效率而受到关注但其细分粒度相对较大。
QEM
基于QEM的简化算法是一种兼具高效执行与模型质量保障的技术方案
下图为两种类型的顶点对：
模型试验结果：
二次误差测度
QEM algorithm's fundamental operation is based on edge folding, utilizing quadratic error metrics for its error measurement. These quadratic error metrics were first introduced by Garland, employing the squared distance from a point to a plane as its basis. This approach offers notable advantages, including high computational efficiency and low memory consumption, resulting in simplified meshes of superior quality. It effectively balances the trade-off between methods that prioritize speed but may compromise mesh quality and those that focus on maintaining high-quality meshes at the expense of computational efficiency, providing an optimal solution for applications requiring both performance and accuracy.
在三维欧氏空间中，一个平面可以表示为：
其中
时平面的单位法向量，d时常量。点
到该平面的距离就可以表示为：
可以定义三元组
来表示
,
其中Q被称为二次型测度或矩阵变量，在这种情况下Q(v)则被定义为对应的二次型误差函数。通过使用二次型测度能够有效地进行累加运算。
，其中
。
二次误差测度从几何角度来看，则可理解为：由Q(v)=ε所确定的等值面是一个椭球面（也可能退化为平面或更低维的空间）；而矩阵A作为一个对称半正定矩阵，则通过其特征值与特征向量直接决定了该椭球面的主要轴线方向及其大小。
表面属性
在计算机图形学领域中, 其最常用的表面属性包括颜色、纹理以及法线等特性。为了实现简化后模型与原始模型之间良好的相似性, 需同时保留这些关键特征。考虑到简化操作对周围区域的属性值变化的影响, 则使得局部误差描述更为精确, 并且相比其他距离计算方法如点到表面或表面间的距离计算更为便捷高效。基于此考虑, 在计算过程中采用点到平面的距离作为主要测度指标, 并将二次误差测度应用其中以提高精度和效率
每个顶点不仅标示着空间坐标的位置信息，在其结构中还嵌入了表征特定属性的数据；对于网格模型中的每一个三角形面片而言，在其表面分布着由几何位置决定的 attribute 值；由此可知，在该 triangle 面片上各处所对应的 attribute 值呈现出连续变化的特点；相邻区域间的数值差异则采用欧几里得距离作为量化标准。
例如，在处理颜色属性时，我们可以采用三维向量表示法 r, g, b_T （其中 0 \leq r, g, b \leq 1 ），这些颜色向量共同构成了RGB色空间。在该色空间中，点到平面的距离平方同样采用了二次误差 Q(v) 的方法进行计算。边折叠后的新顶点，则采用了基于子集的筛选方法，并无需重新计算顶点的空间位置及属性值。在误差计算过程中无需考虑空间坐标与属性值之间的相关性关系。随后分别构建了几何二次误差测度与独立的属性二次误差测度，并对两者分别进行了求解。
边折叠操作的代价
通过带有颜色属性的模型应用算法设计，在具有其他属性特征的基础上进行三角网格模型构建时，则同样可推导出相应的结果。对于一个三角网格模型而言，在每个顶点处定义其三维坐标位置vg=x,y,z_T以及色彩信息向量vc=r,g,b_T（其中0≤r,g,b≤1），用于表征该顶点处几何特征与色彩特性之间的关系。在此基础上为每个三角面片分别构建几何二次误差测度Q_fg与色彩二次误差测度Q_fc；所有顶点处计算得到的所有二次误差测度之总和：
当边折叠(v 1 , v 2 )到顶点v的时候，总的二次误差测度为：
因而边折叠所引发的几何误差_Eg_=Qg·vg ，由颜色属性引发的误差Ec= Qc·vc 。则其总边折叠代价即为：
以色彩属性误差在总代价中的权重因子α为基础，在实际应用中可以通过调整参数来优化性能。
顶点或面片的合并聚类算法
基于顶点聚类的网格简化算法最早优Rossignac提出， 基本思想是：用一个包围盒把原网格模型包围起来，通过等分包围盒的各棱边将包围盒等分成若干个小的长方体，这样原模型的所有顶点就分别落在这些长方体类；扫描这些长方体，如果某个长方体内有顶点，则把该长方体内的所有顶点删除并生成一个新顶点，这个新顶点是被删除的原顶点的平均加权。这种方法存在着三个局限性：首先，由于原网格模型上的点在空间的分布是未知的，这种方法对包围盒进行等分，可能导致等分后某些区域的长方体内包含很多的顶点，而某些区域的长方体内没有或只有很少的顶点，这一方面造成空间和时间的浪费，另一方面造成模型的某些部分过分简化；其次，生成某个长方体内新顶点时，这种方法只是取简单的加权平均而并没有给出一种较好的误差控制方法；再次，当原网格模型比较特殊时，落在某些长方体内的顶点可能属于原模型差别较大的部分，如果这些顶点聚类成一个顶点就会造成很大的变形。如下图：
基于上述算法思路，在此基础上能够构建一种新型的顶点聚类网格简化方法。该方法的主要创新点在于采用八叉树技术对模型包围盒进行自适应细分，并结合二次误差评估来约束简化后的模型变形程度。
算法描述
基本概念
在空间中的一组三角形通过共享公共边并在顶点处相连被命名为或称为一种三角网格TM TM则可由其顶点集V = (v₁ v₂ …… vₙ)与之对应的三角集合T=(t₁,t₂,t₃,…tm)共同构成的有序对(V,T)来表示
在TM中任取一条边e，则如果e仅被一个三角形拥有，则称e为TM中的边界边；其两个端点即为TM中的边界顶点；而位于其中的那个三角形则被称作TM中的边界三角形。
对于TM中的任意一个顶点vi来说，所有包含vi作为其一顶点的三角形Tik所组成的集合被称为与该顶点相关联的三角形集Pi
定义4. 对应于TM中的一个顶点集V = (v_1, v_2, \dots, v_n)，将与V中每个顶点相关联的所有三角形集合进行合并所形成的集合族被称为该顶点集合V相关的三角形族T(V)。
顶点聚类的新顶点的生成和误差的度量
首先需要考虑的是，在某些情况下当某些顶点位于一个长方体内部时如何创建一个新的顶点并用这个新顶点来替代被删除的旧顶点以及这种替代操作所导致的误差具体是多少。这实际上涉及到选择一种合适的误差标准的问题这里采用的是将点到平面距离作为误差标准进行计算和评估
假设落在每个长方体顶点和边所构成的图是连通的，考虑一个顶点集合V落在一个长方体内时，如何求新点和简化误差。我们可以先得到与顶点集合V相关的三角形集合T(V)，由前面的假设不难发现，这个三角形集合构成了原网格模型上的一个区域。下图是一个简单的例子，顶点集合为{v1, v2, v3, v4}，聚类为v0。如果顶点集合V聚类为顶点vi0=x,y,z,1 T ，定义这个聚类带来的误差 ε v s 为vi0 到三角形集合T(V)中每个三角形所在平面的距离平方之和 ε i,1 加上V中的顶点到每个与vi0 相关的三角形所在平面的距离平方之和 ε i,2 ，即
ε v s _=_ε i,1 _+_ε i,2
为了使 ε v s 尽可能的小，可以对上式的x, y, z求偏导，使其等于零，即
∂ε v s ∕∂x=∂ε v s ∕∂y=∂ε V s ∕∂z
定义_P=a b c d 和由顶点集合V生成的三角形集合_T(V)_中每一个三角形所在的平面方程为ax+by+cz+d=0，并满足系数平方和_a² + b² + c² = 1。该计算策略等同于QEM算法中的二次误差测度。
改进后效果
算法选型
在阐述上述算法原理的过程中，基于OpenSceneGraph采用分页加载数据库机制，在该系统中我们采取离线LOD方式进行模型预处理以实现对网格模型呈现的有效优化。考虑到多种因素的影响，我们在进行网格模型预处理时主要针对的是降低复杂度这一目标。
- 离线LOD数据具有结构清晰的特点；
- 通过数据预处理简化模型信息实现资源管理目标；
- 在地球三维呈现过程中, 不同层次网格模型的变化差异不大, 影响微乎其微;
- 为了确保能够有效支持场景操作性能提升, 离线LOD方案更为适宜。
VTK的网格简化算法
VTK（ Visualization Toolkit ）开发包中集成了基于传统的二次误差衡量方法的QEM（Quadratic Error Metric）算法以及顶点聚类方法。针对VTK中的QEM算法，在代码实现方面及其性能表现方面进行了详细阐述：该算法通过...公式实现了高效的几何处理，并在运行效率和稳定性方面表现出色。
按上图顺序，简化程度数据如下：
| 简化目标**(%)** | 100% | 50% | 25% | 12.5% |
|---|---|---|---|---|
| 三角面数 | 675460 | 337730 | 168864 | 84431 |
| 顶点数 | 380869 | 212013 | 128587 | 85527 |
| 时间**(ms)** | 0ms | 2051ms | 1950ms | 1842ms |
VCG的网格简化算法
VCGLib( Visualization and Computer Graphics Library ) 是一套免费提供、轻量级的 C++ 模板库，并支持三维图形和网格操作功能。在 VCG 中提供的系列网格简化算法中主要有两种实现方式可供选择：一种是基于 QEM 的网格简化方法，在这种方案下通过逐步优化减少数据量的同时保证几何特性；另一种则是采用基于 CLIQUE 的顶点聚类方法，在这种方案下通过动态调整顶点分布以实现更好的压缩效果。基于 QEM 的这一系列简化的具体效果包括以下几个方面：
按上图顺序，简化程度数据如下：
| 简化目标**(%)** | 100% | 50% | 12.5% | 1.5% |
|---|---|---|---|---|
| 三角面数 | 675460 | 337730 | 84432 | 6739 |
| 顶点数 | 380869 | 212031 | 64033 | 10554 |
| 时间**(ms)** | 0ms | 2252ms | 1530ms | 920ms |
顶点聚类算法简化效果如下:
按上图顺序，简化程度数据如下：
| 简化目标**(%)** | 100% | 16% | 5% | 3% |
|---|---|---|---|---|
| 三角面数 | 675460 | 112058 | 35271 | 21081 |
| 顶点数 | 380869 | 65488 | 21690 | 13042 |
| 时间**(ms)** | 0ms | 910ms | 431ms | 389ms |
基于QEM的改进算法
来自GitHub仓库https://github.com/lvweiwolf/Fast-Quadric-Mesh-Simplification.git发布的一个优化版本算法用于进行三维网格简化，在其基础之上对现有技术进行了创新性提升。该算法的整体思路与经典的QEM方法保持一致，在实现过程中进行了优化工作。经过测试显示该方法能够使运行效率提升至原本水平的四倍左右（具体效果数据待后续实验验证）。
