【CGAL系列】---Mesh修复

很高兴在雪易的CSDN遇见你?

VTK技术爱好者 QQ：870202403

---

前言

本文分享CGAL中关于Mesh修复问题，希望对各位小伙伴有所帮助！

感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！

你的点赞就是我的动力(＾Ｕ＾)ノ~ＹＯ

---

目录

前言

1. 多边形集合（Polygon Soup）修复

2. Stitch（拼接）

3. 多边形网格（Polygon Mesh）流形

4. 边界循环中的重复顶点

5. 几何修复

结论：

---

1. 多边形集合（Polygon Soup）修复

????????多边形集合（Polygon Soup）是一个多边形网格（Polygon Mesh）中的所有面已知，但连接性未知的面集合。多边形集合（Polygon Soup）在执行任何算法之前必须确保多边形的方向一致（CGAL::Polygon_mesh_processing::orient_polygon_soup()实现）。

????????多边形集合（Polygon Soup）和多边形网格（Polygon Mesh）之间的转化为：

????????CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh()

????????CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup()

参考样例为：Polygon_mesh_processing_Examples中的repair_polygon_soup_example.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>
#include <CGAL/Polygon_mesh_processing/orient_polygon_soup.h>
#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel     K;
typedef K::FT                                                   FT;
typedef K::Point_3                                              Point_3;

typedef CGAL::Surface_mesh<Point_3>                             Mesh;

typedef std::array<FT, 3>                                       Custom_point;
typedef std::vector<std::size_t>                                CGAL_Polygon;

namespace PMP = CGAL::Polygon_mesh_processing;

struct Array_traits
{
  struct Equal_3
  {
    bool operator()(const Custom_point& p, const Custom_point& q) const {
      return (p == q);
    }
  };

  struct Less_xyz_3
  {
    bool operator()(const Custom_point& p, const Custom_point& q) const {
      return std::lexicographical_compare(p.begin(), p.end(), q.begin(), q.end());
    }
  };

  Equal_3 equal_3_object() const { return Equal_3(); }
  Less_xyz_3 less_xyz_3_object() const { return Less_xyz_3(); }
};

int main(int, char**)
{
  // First, construct a polygon soup with some problems
  std::vector<std::array<FT, 3> > points;
  std::vector<CGAL_Polygon> polygons;

  points.push_back(CGAL::make_array<FT>(0,0,0));
  points.push_back(CGAL::make_array<FT>(1,0,0));
  points.push_back(CGAL::make_array<FT>(0,1,0));
  points.push_back(CGAL::make_array<FT>(-1,0,0));
  points.push_back(CGAL::make_array<FT>(0,-1,0));
  points.push_back(CGAL::make_array<FT>(0,1,0)); // duplicate point
  points.push_back(CGAL::make_array<FT>(0,-2,0)); // unused point

  CGAL_Polygon p;
  p.push_back(0); p.push_back(1); p.push_back(2);
  polygons.push_back(p);

  // degenerate face
  p.clear();
  p.push_back(0); p.push_back(0); p.push_back(0);
  polygons.push_back(p);

  p.clear();
  p.push_back(0); p.push_back(1); p.push_back(4);
  polygons.push_back(p);

  // duplicate face with different orientation
  p.clear();
  p.push_back(0); p.push_back(4); p.push_back(1);
  polygons.push_back(p);

  p.clear();
  p.push_back(0); p.push_back(3); p.push_back(5);
  polygons.push_back(p);

  // degenerate face
  p.clear();
  p.push_back(0); p.push_back(3); p.push_back(0);
  polygons.push_back(p);

  p.clear();
  p.push_back(0); p.push_back(3); p.push_back(4);
  polygons.push_back(p);

  // pinched and degenerate face
  p.clear();
  p.push_back(0); p.push_back(1); p.push_back(2); p.push_back(3);
  p.push_back(4); p.push_back(3); p.push_back(2); p.push_back(1);
  polygons.push_back(p);

  std::cout << "Before reparation, the soup has " << points.size() << " vertices and " << polygons.size() << " faces" << std::endl;
  PMP::repair_polygon_soup(points, polygons, CGAL::parameters::geom_traits(Array_traits()));
  std::cout << "After reparation, the soup has " << points.size() << " vertices and " << polygons.size() << " faces" << std::endl;

  Mesh mesh;
  PMP::orient_polygon_soup(points, polygons);
  PMP::polygon_soup_to_polygon_mesh(points, polygons, mesh);

  std::cout << "Mesh has " << num_vertices(mesh) << " vertices and " << num_faces(mesh) << " faces" << std::endl;

  assert(num_vertices(mesh) == 5);
  assert(num_faces(mesh) == 4);

  return 0;
}

?

2. Stitch（拼接）

? ? ? ? 在处理多边形网格（Polygon Mesh）时，网格可能会出现多个重复的边和顶点的情况。对于这些边和顶点，网格的连通性是不完整的。可以通过Stitch（拼接）多边形网格的边界来修复一些重复数据。主要包括两个主要步骤：首先检测并配对几何上相同但重复的边界边缘。然后将它们“拼接”在一起，以便从网格中删除重复的边和顶点，并且这些剩余的边中每一个都恰好入射到两个面上。

? ? ? ? 注：输入网格应该是流形的，否则不能保证拼接成功。

参考样例为：Polygon_mesh_processing_Examples中的stitch_borders_example。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>

#include <CGAL/Polygon_mesh_processing/stitch_borders.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>

#include <iostream>
#include <string>

typedef CGAL::Exact_predicates_inexact_constructions_kernel   K;
typedef CGAL::Polyhedron_3<K>                                 Polyhedron;

namespace PMP = CGAL::Polygon_mesh_processing;

int main(int argc, char* argv[])
{
  const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/quads_to_stitch.off");

  Polyhedron mesh;
  if(!PMP::IO::read_polygon_mesh(filename, mesh))
  {
    std::cerr << "Invalid input." << std::endl;
    return 1;
  }

  std::cout << "Before stitching : " << std::endl;
  std::cout << "\t Number of vertices  :\t" << mesh.size_of_vertices() << std::endl;
  std::cout << "\t Number of halfedges :\t" << mesh.size_of_halfedges() << std::endl;
  std::cout << "\t Number of facets    :\t" << mesh.size_of_facets() << std::endl;

  PMP::stitch_borders(mesh);

  std::cout << "Stitching done : " << std::endl;
  std::cout << "\t Number of vertices  :\t" << mesh.size_of_vertices() << std::endl;
  std::cout << "\t Number of halfedges :\t" << mesh.size_of_halfedges() << std::endl;
  std::cout << "\t Number of facets    :\t" << mesh.size_of_facets() << std::endl;

  CGAL::IO::write_polygon_mesh("mesh_stitched.off", mesh, CGAL::parameters::stream_precision(17));

  return 0;
}

3. 多边形网格（Polygon Mesh）流形

????????可以使用函数 检测非流形顶点。该函数可用于尝试通过将任何非流形顶点拆分为与此几何位置处的流形片数量相同的顶点来创建组合流形曲面网格。但请注意，从几何角度来看，网格仍然不是流形的，因为在非流形顶点处引入的新顶点的位置与输入的非流形顶点相同。CGAL::Polygon_mesh_processing::is_non_manifold_vertex()CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices()

????????参考样例为：Polygon_mesh_processing_Examples中的manifoldness_repair_example。

?

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/repair.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>

#include <CGAL/boost/graph/iterator.h>

#include <iostream>
#include <iterator>
#include <string>
#include <vector>

namespace PMP = CGAL::Polygon_mesh_processing;
namespace NP = CGAL::parameters;

typedef CGAL::Exact_predicates_inexact_constructions_kernel          K;
typedef CGAL::Surface_mesh<K::Point_3>                               Mesh;

typedef boost::graph_traits<Mesh>::vertex_descriptor                 vertex_descriptor;
typedef boost::graph_traits<Mesh>::halfedge_descriptor               halfedge_descriptor;

void merge_vertices(vertex_descriptor v_keep, vertex_descriptor v_rm, Mesh& mesh)
{
  std::cout << "merging vertices " << v_keep << " and " << v_rm << std::endl;

  for(halfedge_descriptor h : CGAL::halfedges_around_target(v_rm, mesh))
    set_target(h, v_keep, mesh); // to ensure that no halfedge points at the deleted vertex

  remove_vertex(v_rm, mesh);
}

int main(int argc, char* argv[])
{
  const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/blobby.off");

  Mesh mesh;
  if(!PMP::IO::read_polygon_mesh(filename, mesh) || CGAL::is_empty(mesh))
  {
    std::cerr << "Invalid input." << std::endl;
    return 1;
  }

  // Artificially create non-manifoldness for the sake of the example by merging some vertices
  vertex_descriptor v0 = *(vertices(mesh).begin());
  vertex_descriptor v1 = *(--(vertices(mesh).end()));
  merge_vertices(v0, v1, mesh);

  // Count non manifold vertices
  int counter = 0;
  for(vertex_descriptor v : vertices(mesh))
  {
    if(PMP::is_non_manifold_vertex(v, mesh))
    {
      std::cout << "vertex " << v << " is non-manifold" << std::endl;
      ++counter;
    }
  }

  std::cout << counter << " non-manifold occurrence(s)" << std::endl;

  // Fix manifoldness by splitting non-manifold vertices
  std::vector<std::vector<vertex_descriptor> > duplicated_vertices;
  std::size_t new_vertices_nb = PMP::duplicate_non_manifold_vertices(mesh,
                                                                     NP::output_iterator(
                                                                       std::back_inserter(duplicated_vertices)));

  std::cout << new_vertices_nb << " vertices have been added to fix mesh manifoldness" << std::endl;

  for(std::size_t i=0; i<duplicated_vertices.size(); ++i)
  {
    std::cout << "Non-manifold vertex " << duplicated_vertices[i].front() << " was fixed by creating";
    for(std::size_t j=1; j<duplicated_vertices[i].size(); ++j)
      std::cout << " " << duplicated_vertices[i][j];
    std::cout << std::endl;
  }

  return EXIT_SUCCESS;
}

4. 边界循环中的重复顶点

?????????多边形网格（Polygon Mesh）中可能存在的另一个问题是出现“捏”孔，即当从边界半边开始并沿该边界的半边行走时，几何位置在再次到达初始边界半边之前出现不止一次（尽管具有不同的顶点）。合并相同位置顶点的函数 和 可用于修复此配置。CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()

5. 几何修复

????????由几乎共线点组成的网格的三角形面是形状不好的元素，在网格中可能不希望有。该函数允许删除此类元素，并使用用户定义的参数来限定几乎意味着什么 （ 和 ）。由于一些形状不好的元素是不可避免的（例如，在顶部和底部圆上只有顶点的长圆柱体的三角测量），因此可以传递额外的参数来防止删除此类元素 （ 和 ）。CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces()cap_thresholdneedle_thresholdcollapse_length_thresholdflip_triangle_height_threshold

?

结论：

感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！

你的赞赏是我的最最最最大的动力(＾Ｕ＾)ノ~ＹＯ