本博客内容来源于网络以及其他书籍，结合自己学习的心得进行重编辑，因为看了很多文章不便一一标注引用，如图片文字等侵权，请告知删除。
前言
马上就要国庆节了，热祝中华人民共和国成立七十周年，祝祖国繁荣富强，当然还有一个高兴的事情就是，要放假了O(∩_∩)O～
刚刚准备写网格简化近似方法的时候，笔记里面就列了要写顶点聚类算法，由于比较简单吧，也一直没有写，为了庆祝我国生日，还是来写一下子吧。
顶点聚类算法思路
网格简化的目的就是减少面片的数目，或者说减少顶点的数目。顶点聚类的算法的思路就是类似于我们在点云中的体素降采样，我们将网格分成很多小格子，我们称之为体素，每个体素里面都有若干顶点或没有，将含有顶点的体素里面的顶点 合并为一个顶点。 将体素相连的顶点重新连接成三角面片，形成新的网格。
但是从上图看，明天网格的连接结构发生了很大的变化，两个不相连的边被连在了一起，改变了拓补结构。在下一节我们来看看顶点聚类怎么来处理这个问题。
嗯…………，基本的处理方式就是这么简单，好像说完了，我要是理解错了别打我，~~~~ (>_<) ~~~~
顶点聚类算法具体过程
在上面我们简单的描述了顶点聚类的基本原理，但是也表明了其中的问题。下面我们来讲解一下常用的基于顶点聚类的算法。
基于八叉树的顶点聚类网格简化算法，使用八叉树的主要优势可以对原模型包围盒进行自适应划分，即对体素的大小进行自适应的划分，同时利用二次误差度量控制简化模型的变形，类似与QEM误差度量。
我们来描述一下算法的流程：
- 根据模型构建八叉树，保证在每个八叉树体素内顶点和边所构成的图是连通的，如果又不连通则继续拆分八叉树体素。
- 计算每个顶点的Q值（我们在QEM中有描述Q是什么）
- 计算出每个体素点合并后，其新点到之前的面的误差的最小值，以及新点的位置
- 将所有的体素按照误差权值放到一个最小堆里
- 每次合并度量（cost）最小的体素，并且更新连着该体素的所有有效体素的代价
- 如果没有达到阈值则重复5，否则退出
算法的流程基本上和QEM一样，不过qem是针对边，而顶点聚类的话是针对八叉树内的一个体素。
效果展示【代码】
vcg的代码太繁杂了，也比较长，如果有需要的可以联系我微信。
| 原理网格边长2cm | 体素大小5cm |
|---|---|
|
|
| 体素大小10cm | 体素大小20cm |
|
|
总结
在刚开始看顶点聚类算法的时候，貌似好像跟QEM没有什么联系，两种不同的方案。但是最后我们看到，我们使用顶点聚类的基础，采用QEM的策略来优化简化方法，也能使方法有着更优秀的提高。其实学习算法最重要的是发现分析处理事情的思路，让其方法更接近最优解。而且处理不同事情的算法，没有任何联系，但是其解决问题的策略可能能使用很多的事情。所以大家一起努力吧，先从简单的算法开始，慢慢的来，由简入繁，深入浅出，简单的东西往往包含更正确的原理。
重要的事情说三遍：
如果您看到我的文章对您有所帮助，那就点个赞呗 ( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
如果您看到我的文章对您有所帮助，那就点个赞呗( * ^ __ ^ * )
任何人或团体、机构全部转载或者部分转载、摘录，请保留本博客链接或标注来源。博客地址：开飞机的乔巴
作者简介：开飞机的乔巴（WeChat：zhangzheng-thu），现主要从事机器人抓取视觉系统以及三维重建等3D视觉相关方面，另外对slam以及深度学习技术也颇感兴趣，欢迎加我微信或留言交流相关工作。
网友评论