网格简化之VSA学习笔记

作者: 开飞机的乔巴 | 来源:发表于2019-09-29 10:30 被阅读0次

    本博客内容来源于网络以及其他书籍,结合自己学习的心得进行重编辑,因为看了很多文章不便一一标注引用,如图片文字等侵权,请告知删除。

    传统2D计算机视觉学习笔记目录------->传送门
    传统3D计算机视觉学习笔记目录------->传送门

    前言

    准备写的四篇网格简化文章,这是最后一篇,也是最复杂的一篇。工作中也是先实现的这篇,用了我大概一周左右。CGAL里面虽然有实现,但是整体的效果不太好,有很多问题,改起来也费劲,就重新实现了一下。重新实现效果呢,加了一些优化,最后的效果较论文有一定的改善。下面我们一起来看看学习vsa算法。

    本文较长

    VSA算法简介

    VSA 全名:Variational Shape Approximation,变分形状逼近。VSA是一种形状逼近方法,在形状逼近的过程中简化了大量的网格。较其他的简化方法,其在挑选简化的面的时候使用了全局优化,其更不易产生较大的形变。从下面这张图,我们就可以大概解释其过程的原理。

    关于背景就说这么多,接下来我们来看其具体的算法流程。

    VSA算法过程

    VSA算法我们可以将其分为5个部分,论文中着重的贡献就是第2、3步,在此文章只直接是论文中的思路,个人在自己的实现方案中,有一些优化:

    1. 初始化区域种子
    2. 区域划分
    3. 代理平面拟合
    4. 锚点选择
    5. 网格生成

    下面我们逐一解释每一部分

    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步的迭代之后,我们得到了一个最优的区域划分。
    这一步我们要选取锚点,锚点指的是,在一下步中网格生成中的顶点。我们来看怎么来选择确定锚点。

    1. 两个区域以上相交的部分,我们选择为锚点,仅是一个顶点,如下图
    2. 针对环状没有相交区域的我们随机选择一个边界点当做锚点,然后再选择一个距离此锚点最远的边界点作为锚点。

    3. 我们遍历边界上连续的两个锚点之间的所有点,如果有边界点距离两个锚点的直线距离大于一定阈值,我们选择该边界点作为锚点。然后再继续遍历新锚点两次存不存在潜在锚点。如下图:
    4. 现在可以保证每个区域至少有两个个锚点了,要想形成面至少有三个锚点,针对只有两个秒点的情况,我们选择边界点上距离两个锚点直线距离最远的边界点作为锚点。

    至此我们选择好了,并且保证了所有区域至少有三个锚点。

    5. 网格生成

    在我们选择好每个区域的锚点,并且知道锚点在边界中的连接关系,但是多空间多边形,要想生成三角网格,论文中,采用的一种伪德劳内三角形的方式。

    首先沿着区域的边界,将锚点的标记进行区域延伸,只在边界上。然后在使锚点的标记在所有的未标记的区域进行区域增长。

    查找区域的三角面,如果有三角面的三个顶点分别是三个不同的锚点的标记,则连接这三个锚点作为一个三角形。

    论文中的这种方法,有很多问题,在特别简单规则化的网格模型上可以,对于比较复杂的模型这种方法会产生空洞,三角面片方向反向等,导致非流形。

    我个人在实现算法部分,这部分用的时间最长,基本上解决了上述问题。大概思路就是优先采用上述方式因为速度快。当发现有生成三角面反向的情况,将锚点投影到2d平面,采用CDT约束德劳内三角形的方式。这种方式也会出错,比如由于空间关系,导致倒影的锚点连接线有交叉的情况。上述两种方式都不行的情况下,我采用对原区域的边界进行边缘坍塌,是边界只有锚点的连接线,在对区域进行保存边界的QEM网格简化。

    至此,解释完了我对VSA的理解,其中还有很多优化的方案,再次没有提到。

    效果展示【代码】

    代码较长,就不在此展示,如果有需求,请联系我的微信。同时cgal中有实现,简单模型可以作为尝试。
    
    原始网格 简化后,顶点数量为原来1.25%

    可见在细节处的形变还是很小的,比如桌子腿,都被保留下来了。但是三角面片的面积一致性较差。

    总结

    总体来说VSA是一种技术方案,较其他简化算法,VSA在全局上控制了简化的程度,产生的形变较少,在较平的地方有着最优化的方案。VSA产生具有各向异性的网格,并且质量较好,而且VSA不需要输入模型的全局参数化信息和局部的微分量。算法整体的参数较少。

    VSA的缺点也是有的,就是生成的网格的形状,不是很好,但是可以通过与其他方案结合进行优化。


    重要的事情说三遍:

    如果您看到我的文章对您有所帮助,那就点个赞呗 ( * ^ __ ^ * )

    如果您看到我的文章对您有所帮助,那就点个赞呗( * ^ __ ^ * )

    如果您看到我的文章对您有所帮助,那就点个赞呗( * ^ __ ^ * )

    传统2D计算机视觉学习笔记目录------->传送门
    传统3D计算机视觉学习笔记目录------->传送门

    任何人或团体、机构全部转载或者部分转载、摘录,请保留本博客链接或标注来源。博客地址:开飞机的乔巴

    作者简介:开飞机的乔巴(WeChat:zhangzheng-thu),现主要从事机器人抓取视觉系统以及三维重建等3D视觉相关方面,另外对slam以及深度学习技术也颇感兴趣,欢迎加我微信或留言交流相关工作。

    相关文章

      网友评论

        本文标题:网格简化之VSA学习笔记

        本文链接:https://www.haomeiwen.com/subject/utbhyctx.html