CGAL users discussion list

[Benjamin Kehlet <>]

Hello CGAL community!

When meshing polyhedral domains, I sometimes experience isolated
vertices, ie. vertices which does not belong to any cell. The attached
file demonstrates the problem. Could someone take a look, and check if
I'm doing anything wrong? The code for reading out the mesh is based
on the code in CGAL for exporting to medit's file format.

I get this result when attempting to mesh the file
demo/Polyhedron/data/rotor.off from CGAL's source tree:

benjamik@benjamik-ThinkPad:~/tmp/cgal-meshing/build$ ./main
~/software/CGAL-4.5/demo/Polyhedron/data/rotor.off

[...]

Number of unconnected vertices:14
0.0693619 0.340288 -0.260398 0
0.148692 0.344385 -0.252795 0
0.11059 0.332426 -0.267569 0
0.0800736 0.308173 -0.290017 0
0.0358875 0.312982 -0.283919 0
0.0739249 0.2902 -0.306196 0
0.100469 0.304801 -0.293518 0
0.0949104 0.318775 -0.276573 0
0.0777684 0.350724 -0.248457 0
0.0909964 0.338994 -0.261008 0
0.0263695 0.298269 -0.299189 0
0.00269295 0.307881 -0.290388 0
0.0496229 0.300013 -0.297675 0
-0.0248875 0.311644 -0.285615 0

Also a few other files (at least cow.off and bones.off and maybe
others) in the same directory reproduces the problem.

Best regards

Benjamin Kehlet
#define CGAL_NO_DEPRECATED_CODE
#define CGAL_MESH_3_VERBOSE

#define CGAL_MESH_3_NO_DEPRECATED_SURFACE_INDEX
#define CGAL_MESH_3_NO_DEPRECATED_C3T3_ITERATORS

//#define CGAL_MESH_3_PROTECTION_DEBUG 1

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Mesh_triangulation_3.h>
#include <CGAL/Mesh_complex_3_in_triangulation_3.h>
#include <CGAL/Mesh_criteria_3.h>
#include <CGAL/Polyhedral_mesh_domain_with_features_3.h>
#include <CGAL/make_mesh_3.h>
#include <set>

// Domain
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polyhedral_mesh_domain_with_features_3<K> Mesh_domain;
typedef CGAL::Mesh_polyhedron_3<K>::type MeshPolyhedron_3;

// Triangulation
typedef CGAL::Mesh_triangulation_3<Mesh_domain>::type Tr;
typedef CGAL::Mesh_complex_3_in_triangulation_3<
Tr,Mesh_domain::Corner_index,Mesh_domain::Curve_segment_index> C3t3;

// Criteria
typedef CGAL::Mesh_criteria_3<Tr> Mesh_criteria;

// To avoid verbose function and named parameters call
using namespace CGAL::parameters;

int main(int argc, char** argv)
{
  // CGAL::default_random = CGAL::Random( atoi(argv[1]) );

  MeshPolyhedron_3 P;
  {
    std::ifstream infile(argv[1]);
    infile >> P;
  }

  CGAL_assertion(P.is_pure_triangle());

  // Create domain
  Mesh_domain domain(P);
  // Get sharp features
  domain.detect_features();
  
  const double cs = 0.071684;

  // Mesh criteria
  Mesh_criteria criteria(edge_size = cs,
                         facet_angle = 30.,
                         facet_size = cs,
                         facet_distance = cs/10.0,
                         cell_radius_edge_ratio = 3.,
                         cell_size = cs);

  // Mesh generation
  C3t3 c3t3 = CGAL::make_mesh_3<C3t3>(domain, criteria,
                                      CGAL::parameters::no_perturb(),
                                      CGAL::parameters::no_exude());

  // Check that all vertices belongs to at least one cell
  typedef typename C3t3::Triangulation::Vertex_handle VH;
  std::set<VH> vertices;

  const C3t3::Triangulation& triangulation = c3t3.triangulation();
  for (C3t3::Triangulation::Finite_vertices_iterator v = triangulation.finite_vertices_begin();
       v != triangulation.finite_vertices_end(); ++v)

  {
    vertices.insert(v);
  }

  for(C3t3::Cells_in_complex_iterator cit = c3t3.cells_in_complex_begin();
      cit != c3t3.cells_in_complex_end(); ++cit)
  {
    for (std::size_t i = 0; i < 4; ++i)
      vertices.erase(cit->vertex(i));
  }

  std::cout << "Number of unconnected vertices:" << vertices.size() << std::endl;
  for (std::set<VH>::iterator it = vertices.begin(); it != vertices.end(); ++it)
    std::cout << (*it)->point() << std::endl;
}