基于CGAL 3D Delaunay三角剖分从点集生成表面网格的技术问询

Hey there! Let's tackle your problem step by step—you want to extract a surface mesh from your CGAL 3D Delaunay triangulation that includes all your input points (since Poisson reconstruction doesn't satisfy this requirement). Here's exactly how to do it, depending on what kind of surface you need:

Option 1: Extract the Convex Hull Surface (Simplest Case) #

If your input point set forms a convex shape, or you just need the convex hull, you can directly pull the boundary faces from your existing Delaunay triangulation. These boundary faces are exactly the ones that belong to only one tetrahedron (CGAL marks them with is_boundary()).

Here's a code snippet to turn those faces into a Surface_mesh:

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

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_3<K> Delaunay;
typedef CGAL::Surface_mesh<K::Point_3> SurfaceMesh;

int main() {
  // Assume you already have your input points stored in a vector<K::Point_3> points
  // And your Delaunay triangulation is built as:
  Delaunay dt(points.begin(), points.end());

  SurfaceMesh sm;
  std::map<Delaunay::Vertex_handle, SurfaceMesh::Vertex_index> vertex_map;

  // First, add all finite Delaunay vertices (your input points) to the surface mesh
  for (auto vh : dt.finite_vertex_handles()) {
    vertex_map[vh] = sm.add_vertex(vh->point());
  }

  // Then, add all boundary faces to the surface mesh
  for (auto fh : dt.finite_face_handles()) {
    for (int i = 0; i < 4; ++i) {
      if (dt.is_boundary(fh, i)) {
        // Grab the three vertices of the boundary face (ensuring consistent winding order)
        auto v0 = fh->vertex((i+1)%4);
        auto v1 = fh->vertex((i+2)%4);
        auto v2 = fh->vertex((i+3)%4);
        sm.add_face(vertex_map[v0], vertex_map[v1], vertex_map[v2]);
      }
    }
  }

  // Now you can use sm for further processing (save to file, etc.)
  return 0;
}

Notes for Option 1: #

• The vertices in the resulting Surface_mesh are exactly your input points—no extra vertices added.
• If you need consistent face normals, you can use CGAL's polygon mesh processing tools like CGAL::Polygon_mesh_processing::orient() after building the mesh.

Option 2: Extract a Non-Convex Surface (Using Alpha Shapes) #

If your input points are from a non-convex object surface, the convex hull from Option 1 won't be useful. Instead, use 3D Alpha Shapes—a CGAL tool built on top of Delaunay triangulation that extracts a tight, non-convex surface while retaining all your input points as vertices.

Here's how to implement this:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/Alpha_shape_3.h>
#include <CGAL/Surface_mesh.h>
#include <map>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
// Define specialized vertex/cell bases for Alpha Shape
typedef CGAL::Alpha_shape_vertex_base_3<K> Vb;
typedef CGAL::Alpha_shape_cell_base_3<K> Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb> Tds;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef CGAL::Alpha_shape_3<DT> Alpha_shape_3;
typedef CGAL::Surface_mesh<K::Point_3> SurfaceMesh;

int main() {
  std::vector<K::Point_3> points;
  // Populate points with your input data...

  DT dt(points.begin(), points.end());
  Alpha_shape_3 alpha_shape(dt);

  // Find an optimal alpha value to get a single connected surface
  // Adjust the parameter (1 here) if you need multiple components
  alpha_shape.set_alpha(alpha_shape.find_optimal_alpha(1));

  SurfaceMesh sm;
  std::map<Alpha_shape_3::Vertex_handle, SurfaceMesh::Vertex_index> vertex_map;
  std::vector<Alpha_shape_3::Facet> facets;

  // Extract only the "regular" facets that form the surface
  alpha_shape.get_alpha_shape_facets(std::back_inserter(facets), Alpha_shape_3::REGULAR);

  // Build the surface mesh from the facets
  for (auto& facet : facets) {
    auto cell = facet.first;
    int idx = facet.second;

    // Get the three vertices of the facet
    auto v0 = cell->vertex((idx+1)%4);
    auto v1 = cell->vertex((idx+2)%4);
    auto v2 = cell->vertex((idx+3)%4);

    // Add vertices to the mesh if they aren't already present
    if (vertex_map.find(v0) == vertex_map.end()) {
      vertex_map[v0] = sm.add_vertex(v0->point());
    }
    if (vertex_map.find(v1) == vertex_map.end()) {
      vertex_map[v1] = sm.add_vertex(v1->point());
    }
    if (vertex_map.find(v2) == vertex_map.end()) {
      vertex_map[v2] = sm.add_vertex(v2->point());
    }

    // Add the face to the surface mesh
    sm.add_face(vertex_map[v0], vertex_map[v1], vertex_map[v2]);
  }

  // Use the surface mesh as needed
  return 0;
}

Notes for Option 2: #

• The find_optimal_alpha() function calculates an alpha value that results in a single connected surface (adjust the parameter if you need separate components).
• All vertices in the resulting mesh are your original input points—no additional vertices are introduced, which meets your requirement perfectly.
• You can tweak the alpha value manually if the optimal one doesn't give you the exact surface you want (higher alpha = more "relaxed" surface, lower alpha = tighter to the input points).

Key Takeaway #

Both methods leverage your existing Delaunay triangulation and produce a Surface_mesh with all your input points. Choose Option 1 for convex shapes, Option 2 for non-convex surfaces.

内容的提问来源于stack exchange，提问作者Dariuszz