网格简化之VSA学习笔记
本博客内容来源于网络以及其他书籍，结合自己学习的心得进行重编辑，因为看了很多文章不便一一标注引用，如图片文字等侵权，请告知删除。
前言
准备写的四篇网格简化文章，这是最后一篇，也是最复杂的一篇。工作中也是先实现的这篇，用了我大概一周左右。CGAL里面虽然有实现，但是整体的效果不太好，有很多问题，改起来也费劲，就重新实现了一下。重新实现效果呢，加了一些优化，最后的效果较论文有一定的改善。下面我们一起来看看学习vsa算法。
本文较长
VSA算法简介
VSA 全名：Variational Shape Approximation，变分形状逼近。VSA是一种形状逼近方法，在形状逼近的过程中简化了大量的网格。较其他的简化方法，其在挑选简化的面的时候使用了全局优化，其更不易产生较大的形变。从下面这张图，我们就可以大概解释其过程的原理。
关于背景就说这么多，接下来我们来看其具体的算法流程。
VSA算法过程
VSA算法我们可以将其分为5个部分，论文中着重的贡献就是第2、3步，在此文章只直接是论文中的思路，个人在自己的实现方案中，有一些优化：
- 初始化区域种子
- 区域划分
- 代理平面拟合
- 锚点选择
- 网格生成
下面我们逐一解释每一部分
1. 初始化区域种子
在进行区域划分之前，我们需要初始化区域的种子。我们在这一步需要确定两个东西：我们需要确定用多少个区域来代替原模型，以及每个区域在初次迭代时的出发点。
-
确定区域数量
目前我实现的有两个方式，论文出只给出方式1- 一个是直接给出区域的数目
- 二是我们对网格根据法线进行分割，分割产生区域的数目当做区域的数量，需要给出相邻法线相差容忍阈值。这样也可以给出一个模糊的数目，控制法线较直接。
-
确定区域的区域增长种子
我们在第二步的区域划分阶段，需要区域增长来确定区域划分，所以需要确定区域增长的种子三角面，主要有两种方式。- 一是随机产生区域数目的种子面片，速度较快
- 二是在区域划分，代理平面拟合的迭代过程中，不断地插入新的区域，直到达到目的区域数，速度较慢。
建议采取第一种，在一定的迭代次数的前提下，实验效果上，并没有太大差异。
2. 区域划分
在区域划分阶段，第一次迭代，我们选取我们选择的种子节点三角面作为我们的代理平面，其他时候采用下一步拟合出的代理平面。
在这一步，代理平面被固定。
xi为代理平面Pi上的一点，ni是代理平面Pi的法线
区域
算法会通过遍历选择区域Ri的每一个三角形并分别计算E(t,Pi)的值，然后找到该值最小的三角形ti。第一次迭代，每个区域只有种子面片，最小的三角形也是种子面片。
然后开始以ti为种子进行区域增长，对于三角形ti周围的三角形r，我们以E(r, Pi)为优先级，插入一个优先队列中。
之后，取出队头元素，如果该三角形r没有被加入集合Ri则将其加入集合Ri。然后我们选择该三角形r周围的三角形并插入优先队列中。算法重复上述过程直到整个队列为空。
在这里需要着重解释一下三角形的度量误差E的计算方法。首先这个三角形的度量误差E指的是三角形与代理平面直接的误差。论文中有两种方式,两种方式产生的效果不同，但都可以接受：
x为三角面上一点
3. 代理平面拟合
在这个阶段中，区域划分R会被固定，代理平面P会被调整以最小化全局形变量E
全局变量是对每个区域的度量误差进行积分，每个区域的度量误差根于每个面片的计算也有两种方式，当然要对应：
A当然指的是三角片的面积。
我们的这一步的目的就是最小化E（R，P） 来调整代理平面。最小的优化的直接方式如下：
我们对所有的区域进行拟合出一个新的代理平面。然后找到一个与新的代理平面的度量误差最小的三角面，作为新的代理平面的种子。
如果达到迭代次数则进行第4步，否则再进行第二部进行迭代。
4. 锚点选择
在经过多次2,3步的迭代之后，我们得到了一个最优的区域划分。
这一步我们要选取锚点，锚点指的是，在一下步中网格生成中的顶点。我们来看怎么来选择确定锚点。
-
两个区域以上相交的部分，我们选择为锚点，仅是一个顶点，如下图
-
针对环状没有相交区域的我们随机选择一个边界点当做锚点，然后再选择一个距离此锚点最远的边界点作为锚点。
-
我们遍历边界上连续的两个锚点之间的所有点，如果有边界点距离两个锚点的直线距离大于一定阈值，我们选择该边界点作为锚点。然后再继续遍历新锚点两次存不存在潜在锚点。如下图：
-
现在可以保证每个区域至少有两个个锚点了，要想形成面至少有三个锚点，针对只有两个秒点的情况，我们选择边界点上距离两个锚点直线距离最远的边界点作为锚点。
至此我们选择好了，并且保证了所有区域至少有三个锚点。
5. 网格生成
在我们选择好每个区域的锚点，并且知道锚点在边界中的连接关系，但是多空间多边形，要想生成三角网格，论文中，采用的一种伪德劳内三角形的方式。
首先沿着区域的边界，将锚点的标记进行区域延伸，只在边界上。然后在使锚点的标记在所有的未标记的区域进行区域增长。
查找区域的三角面，如果有三角面的三个顶点分别是三个不同的锚点的标记，则连接这三个锚点作为一个三角形。
论文中的这种方法，有很多问题，在特别简单规则化的网格模型上可以，对于比较复杂的模型这种方法会产生空洞，三角面片方向反向等，导致非流形。
我个人在实现算法部分，这部分用的时间最长，基本上解决了上述问题。大概思路就是优先采用上述方式因为速度快。当发现有生成三角面反向的情况，将锚点投影到2d平面，采用CDT约束德劳内三角形的方式。这种方式也会出错，比如由于空间关系，导致倒影的锚点连接线有交叉的情况。上述两种方式都不行的情况下，我采用对原区域的边界进行边缘坍塌，是边界只有锚点的连接线，在对区域进行保存边界的QEM网格简化。
至此，解释完了我对VSA的理解，其中还有很多优化的方案，再次没有提到。
效果展示【代码】
代码较长，就不在此展示，如果有需求，请联系我的微信。同时cgal中有实现，简单模型可以作为尝试。
| 原始网格 | 简化后，顶点数量为原来1.25% |
|---|---|
|
|
可见在细节处的形变还是很小的，比如桌子腿，都被保留下来了。但是三角面片的面积一致性较差。
总结
总体来说VSA是一种技术方案，较其他简化算法，VSA在全局上控制了简化的程度，产生的形变较少，在较平的地方有着最优化的方案。VSA产生具有各向异性的网格，并且质量较好，而且VSA不需要输入模型的全局参数化信息和局部的微分量。算法整体的参数较少。
VSA的缺点也是有的，就是生成的网格的形状，不是很好，但是可以通过与其他方案结合进行优化。
重要的事情说三遍：
如果您看到我的文章对您有所帮助，那就点个赞呗 ( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
任何人或团体、机构全部转载或者部分转载、摘录，请保留本博客链接或标注来源。博客地址：开飞机的乔巴
作者简介：开飞机的乔巴（WeChat：zhangzheng-thu），现主要从事机器人抓取视觉系统以及三维重建等3D视觉相关方面，另外对slam以及深度学习技术也颇感兴趣，欢迎加我微信或留言交流相关工作。
