最近开始做网格重建与优化方面的工作，这里就不得不提到Isotropic Remeshing. 部分内容参考自：https://zhuanlan.zhihu.com/p/104107745#ref_3

在之前的博客中，我们已经提到了一种非常好的Isotropic Remeshing方法，即基于CVT(Centroidal Voronoi Tessellation)的网格重建方法，链接：https://blog.csdn.net/aliexken/article/details/106746560。该方法能够基于点云得到一个非常好的isotopic mesh。但是，该方法存在两个问题，第一，基于劳埃德优化与Delaunay三角化的点位置更新速度太慢；第二，在曲率变化比较显著的区域，可能会产生错误的三角化结果。

为了解决该问题，可以把网格重建分成两步：第一步，获取一个几何正确的三角网格，但是不保证网格内部三角形的质量，第二步，对网格的三角形进行优化，在保持几何一致的前提下，优化三角网格的质量。这里，我们就来介绍一下如何对三角网格进行优化，即isotropic remeshing.

1. 优化步骤

Botsch [Botsch 2004] 在2004年的文章中介绍了一种实现简单，结果优秀的优化方法。其具体的思路就是设定一个目标边长，并优化网格中所有的边长向目标边长靠近，并最终得到优化结果。那么，这里主要分为三个步骤，来实现向目标边长的优化，即分割Split，塌缩Collapse和翻转Flip，如下图:

Split:

Flip：

Collapse:

算法的步骤可以归纳为：

第四步具体步骤：

获取目标优化边长L。

1. Split所有长度大于4/3L的边。

2. Collapse所有长度效益4/5L的边。

3. 对所有边进行Flip，以优化度数，内点为6，边界为4. 一个点的度数为连接该点的边的总数。

4. 映射所有新加入的点到切平面。

在进行各种操作的时候，需要注意一点，那就是不能产生二度点和重边的情况，如图所示：

2. 优化实现

CGAL库封装了该方法：https://doc.cgal.org/latest/Polygon_mesh_processing/index.html#title7

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Surface_mesh.h> #include <CGAL/Polygon_mesh_processing/remesh.h> #include <CGAL/Polygon_mesh_processing/border.h> #include <boost/function_output_iterator.hpp> #include <fstream> #include <vector> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Surface_mesh<K::Point_3> Mesh; typedef boost::graph_traits<Mesh>::halfedge_descriptor halfedge_descriptor; typedef boost::graph_traits<Mesh>::edge_descriptor edge_descriptor; namespace PMP = CGAL::Polygon_mesh_processing; struct halfedge2edge { halfedge2edge(const Mesh& m, std::vector<edge_descriptor>& edges) : m_mesh(m), m_edges(edges) {} void operator()(const halfedge_descriptor& h) const { m_edges.push_back(edge(h, m_mesh)); } const Mesh& m_mesh; std::vector<edge_descriptor>& m_edges; }; int main(int argc, char* argv[]) { const char* filename = (argc > 1) ? argv[1] : "data/pig.off"; std::ifstream input(filename); Mesh mesh; if (!input || !(input >> mesh) || !CGAL::is_triangle_mesh(mesh)) { std::cerr << "Not a valid input file." << std::endl; return 1; } double target_edge_length = 0.04; unsigned int nb_iter = 3; std::cout << "Split border..."; std::vector<edge_descriptor> border; PMP::border_halfedges(faces(mesh), mesh, boost::make_function_output_iterator(halfedge2edge(mesh, border))); PMP::split_long_edges(border, target_edge_length, mesh); std::cout << "done." << std::endl; std::cout << "Start remeshing of " << filename << " (" << num_faces(mesh) << " faces)..." << std::endl; PMP::isotropic_remeshing( faces(mesh), target_edge_length, mesh, PMP::parameters::number_of_iterations(nb_iter) .protect_constraints(true)//i.e. protect border, here ); std::cout << "Remeshing done." << std::endl; return 0; }

为了将来对该方法进行进一步优化，我也在尝试自己重建全部的代码，包括维护一个近似半边结构，以及对应的优化操作（在完成后，我将更新该帖子，发布代码）。

3. 优化结果

参考文献：

[Botsch 2004] A Remeshing Approach to Multiresolution Modeling.

[Botsch 2013] Adaptive Remeshing for Real-Time Mesh Deformation.