网格简化近似方法学习笔记
本博客内容来源于网络以及其他书籍，结合自己学习的心得进行重编辑，因为看了很多文章不便一一标注引用，如图片文字等侵权，请告知删除。
前言
前些天，发现简书暂停一个月的文章发布，这一周多也就没写什么，正好公司需要优化一下当前正在使用的网格简化，加之之前确实了解了一些网格简化的方法，但是一直没有整理。要是突然被问用什么方法，有什么优缺点还真说不上来，所以在此成文记录一下我所了解的网格简化以及网格近似的方法，并与大家分享。（终于可以发存货了）
网格简化近似
首先我们来说明一下什么是网格简化？
所谓网格简化，就是将大量的三角形网格简化为少量的三角形或者将大量的多边形简化为少量的多边形来近似表达模型的空间形状。如下图：
大量网格原图
简化后少量网格图
上图用了几十万个三角型来表达一个沙发，而下图只用了几百个三角形，这个简化是有点夸张，但也基本上表达出了一个沙发，当然细节不如大量的三角面。
那么为什么要进行网格简化呢？
进行网格简化的原因大概有几个方面：
- 节省存储空间
每个三角面在空间储存的大小是一样的，减少三角面的数目，就减少了模型保存的文件大小，如果进行网络传输则大大缩短网络传输时间。 - 简化后续处理步骤
如果后续要对模型进行一些计算，例如贴纹理，在最终效果基本上不变的情况下，计算时间会大量的缩短。 - 节省渲染时间
当我们想要显示模型的时候，需要对模型的每个三角面进行空间渲染，需要大量的计算，三角面的数目减少，在不影响显示效果的情况下，会大大的减少渲染计算的负担。对于一个500MB的模型，一般4G内存的显卡就已经能感觉到卡顿了。所以如果玩高逼真的主机游戏还是需要非常厉害的显卡的。 - 去除不需要不关心的细节部分
比如对于一面墙，墙上有一些小凹凸，但是对用使用者来说并不关系，更希望能够删除掉这些部分，来优化视觉效果，网格简化通常能够达到这些效果。
在了解到什么是网格简化以及为什么要进行网格简化后，那么什么时候一个好的网格简化算法呢？
一个好的网格简化算法，需要在这几个方面进行度量：
- 简化后网格与初始网格的相似度，越高越好
- 简化到同等网格数，时间越短越好
- 在同等相似度下，网格数目越少越好
这几个度量方式相互牵制，总体来说，就是在最短的时间内简化到网格数最少，并且模型相似度可以接受。每种方法都有自己的优劣，下面我们来看看常见的网格简化算法有什么。
常见网格简化近似方法
常见的网格简化近似方法，大概分为以下四类：
-
顶点聚类算法
顶点聚类的基本思想就是，将模型顶点，无论按照晶格划分还是相近关系，将顶点进行聚类，属于同一类的顶点，由一个新的顶点进行替换。顶点聚类算法拥有很高的效率和鲁棒性(Robust)，算法的复杂度是线性的。其缺点在于生成网格的质量不是特别令人满意。
-
增量式删除算法
典型的就是QEM(Quadric Error Mactrics，二次误差测度)模型简化算法（后续单独文章描述）
具体的操作方法：顶点删除(Vertex removal)法、边坍塌(Edge Collapse)法和三角面片坍塌(Triangle collapse)法 -
重采样算法
重采样算法也是一个比较常用的算法。基本方法就是，在网格曲面上选择新的采样顶点，通过连接这些顶点，能够构建出一个新的网格。
使用重采样算法的主要目的是在于，通过重采样我们能够获得想要的网格连接结构。不过其主要的缺点在于，如果采样模式与网格区域没有对齐，那么就会出现走样，拓扑结构可能发生变化。对这个方法进行优化，可以提前将网格根据其特征将其分割为不同的区域，比如区域都是凸包，不含有环状的结构等。
-
模型逼近算法
常见算法如：Variational Shape Approximation (VSA) （后续单独文章介绍）
以上各种方法各有自己的优缺点，比如VSA从全局进行优化，得到的模型较好，但是时间较长，不能用于在线系统。
上面几种具体的算法基本上都需要一篇文章才能讲明白，接下来，来解释一下增量式删除的三种基本删除方法
基本删除方法详解
-
顶点删除法
删除网格中的一个顶点，然后对它相邻三角形形成的空洞，进行三角刨分
-
边坍塌（折叠）法
将网格里面的一条边压缩为一个顶点，退化了该边相邻的两个三角形
-
三角面片坍塌（折叠）法
如图，将网格内的一个面片收缩为一个顶点，退化了该面片以及临边的三个面片
总结
本文简单的介绍了有关网格简化的概念，以及列举了网格简化近似的一些方法。网格简化作为计算机图形学中一个重要的部分，免不了大量的数学计算，并且因为涉及到图的拓扑结构，代码也较为复杂。
接下来，会独立来详细的描述每一种网格简化的方法，希望自己能把这些解释清楚。
重要的事情说三遍：
如果您看到我的文章对您有所帮助，那就点个赞呗 ( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
任何人或团体、机构全部转载或者部分转载、摘录，请保留本博客链接或标注来源。博客地址：开飞机的乔巴
作者简介：开飞机的乔巴（WeChat：zhangzheng-thu），现主要从事机器人抓取视觉系统以及三维重建等3D视觉相关方面，另外对slam以及深度学习技术也颇感兴趣，欢迎加我微信或留言交流相关工作。
