# 网格合并原理
出于性能的考虑，我们有时需要将高模转化为低模，大概有两种常用方法。
## 顶点聚类(vertex clustering)
基本思想：合并相邻点
1. 创建空间网格(树形结构，比如八叉树）对模型中的点进行聚类
2. 合并聚类点，对于聚类中心有多种策略(平均值，中位数，[error quadric](https://users.csc.calpoly.edu/~zwood/teaching/csc570/final06/jseeba/#:~:text=Quadric%20Error%20Metrics%20are%20a%20measurement%20of%20error,the%20triangle%20is%20used%20to%20find%20the%20offset.)等)
error quadric的效果好一些。
缺点：容易造成网格的退化
## 边坍缩(edge collapse)
基本原理：使用三角边坍缩的方法来进行网格简化，将两个顶点合并成一个顶点(而不是像顶点聚类那样合并单元格内的所有顶点），如图所示。
选择哪一条边来进行坍缩？这是最主要的问题。
其基本策略是：1.边越短越好 2.合并后曲率变化越小越好
在此基础上有这么一些算法：
> [Garland et al. 1997]提出了一种基于二次误差(Quadric Error Metrics)作为度量代价的边收缩算法，其计算速度快并且简化质量较高
>
> [Mesh Saliency](https://www.cs.umd.edu/gvil/projects/mesh_saliency.shtml)[*ACM SIGGRAPH 2005*]是其改进版本，考虑了模型特征点的权重。
边坍缩算法有个优点，边坍缩后权重更新范围不大。并且可以用最小堆来进行排序，逐步减少到所需面数。
## 应用
1. 游戏中常常采用LOD技术，即Levels of Detail的简称，意为多细节层次。
> LOD技术指根据物体模型的节点在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重要物体的面数和细节度，从而获得高效率的渲染运算。
一般的地图模型会有两套模型，高模和低模，在玩家距离远时替换为低模，节省计算开销。
2. 而笔者研究网格合并是为了解决，**模型布尔运算时，其边界偶尔会出现小面片法向错误的问题**
如图所示：用球体和圆柱合并为胶囊时，边界有奇怪的朝向
把相机放到胶囊内部，拉近一看原来是有一些小面片的朝向不对
一般碰到法向错误，都是手动翻转，而我想偷个懒，直接把小面合并掉算了。
但是发现在blender中即使把精度调到很低，也没把这小面给合并咯。
这是因为blender采用的是边坍缩算法，类似[Mesh Saliency](https://www.cs.umd.edu/gvil/projects/mesh_saliency.shtml)，考虑了曲率变化的影响。
本例子中的小面差不多垂直于柱面，所以权重很高，一直没有被优化。
因此通过blender自动化简合并来解决的尝试失败了
对于本问题，更合适的算法是**顶点聚类**，不过blender好像没有集成，只得留待日后自己实现。
## 参考
> [1] Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 209-216.
>
> [2]https://zhuanlan.zhihu.com/p/51944864
>
> [3]边坍缩https://blog.csdn.net/qq_31804159/article/details/111769328
>
> [4]Mesh Saliencyhttps://www.cs.umd.edu/gvil/projects/mesh_saliency.shtml
>
> [5]在unity上实现https://blog.csdn.net/chqj_163/article/details/107522038
>
> [6]减面步骤https://blog.csdn.net/qq_40999248/article/details/123446160
>
> [7]blender中不同的减面算法https://create3dart.com/how-to-use-decimate-modifier-in-blender/
>
> [8]https://docs.blender.org/manual/zh-hans/2.79/modeling/meshes/editing/normals.html#recalculate-normals
模型化简
