CGAL 5.1 released


CGAL 5.1 released

Download CGAL-5.1

CGAL-5.1 documentation

CGAL 5.1 offers the following improvements and new functionality over CGAL 5.0:


Tetrahedral Remeshing (new package)

  • This package implements a tetrahedral isotropic remeshing algorithm, that improves the quality of tetrahedra in terms of dihedral angles, while targeting a given edge length.

    See also the associated blog entry.

Surface Mesh Topology (new package)

  • This package enables the computation of some topological invariants of surfaces, such as:
    • test if two (closed) curves on a combinatorial surface are homotopic. Users can choose between free homotopy and homotopy with fixed endpoints;
    • test is a curve is contractible;
    • compute shortest non-contractible cycles on a surface, with or without weights on edges.

    See also the associated blog entry.

Optimal Bounding Box (new package)

  • This package implements an optimization algorithm that aims to construct a close approximation of the optimal bounding box of a mesh or a point set, which is defined as the smallest (in terms of volume) bounding box that contains a given mesh or point set.

    See also the associated blog entry.


  • The CGAL_Core library no longer requires Boost.Thread, even if the g++ compiler is used.
  • The minimal supported version of Boost is now 1.66.0.


2D and 3D Linear Geometry Kernel

dD Geometry Kernel

Surface Mesh

CGAL and the Boost Graph Library (BGL)

3D Fast Intersection and Distance Computation

2D Arrangements

  • Changed intersection return type from legacy CGAL::Object to modern boost::variant in all traits concepts and models. As there exists an implicit conversion from boost::variant to CGAL::Object, the new code is backward compatible. However, it is recommended that all calls to the intersection functions are fixed to use the new return type.

2D Regularized Boolean Set-Operations

2D Minkowski Sums

  • Changed intersection return type from legacy CGAL::Object to modern boost::variant in the (internally used) model Arr_labeled_traits_2.

dD Spatial Searching

  • The kd-tree can now be built in parallel: CGAL::Kd_tree::build() is given an optional template parameter ConcurrencyTag (default value remains CGAL::Sequential_tag for backward compatibility).
  • Improved the performance of the kd-tree in some cases:
    • Not storing the points coordinates inside the tree usually generates a lot of cache misses, leading to non-optimal performance. This is the case for example when indices are stored inside the tree, or to a lesser extent when the points coordinates are stored in a dynamically allocated array (e.g., Epick_d with dynamic dimension) — we says “to a lesser extent” because the points are re-created by the kd-tree in a cache-friendly order after its construction, so the coordinates are more likely to be stored in a near-optimal order on the heap. In these cases, the new EnablePointsCache template parameter of the CGAL::Kd_tree class can be set to CGAL::Tag_true. The points coordinates will then be cached in an optimal way. This will increase memory consumption but provides better search performance. See the updated GeneralDistance and FuzzyQueryItem concepts for additional requirements when using such a cache.
    • In most cases (e.g., Euclidean distance), the distance computation algorithm knows before its end that the distance will be greater than or equal to some given value. This is used in the (orthogonal) k-NN search to interrupt some distance computations before its end, saving precious milliseconds, in particular in medium-to-high dimension.

Intersecting Sequences of dD Iso-oriented Boxes

Spatial Sorting

  • Added parallel versions of the functions CGAL::hilbert_sort() and CGAL::spatial_sort() in 2D and 3D when the median policy is used. The parallel versions use up to four threads in 2D, and up to eight threads in 3D.

3D Convex Hulls

Polygon Mesh Processing

Point Set Processing

  • Breaking change: CGAL::remove_outliers() has been parallelized and thus has a new template parameter ConcurrencyTag. To update your code simply add as first template parameter CGAL::Sequential_tag or CGAL::Parallel_tag when calling this function.
  • Add a function CGAL::cluster_point_set() that segments a point cloud into connected components based on a distance threshold.
  • Added wrapper functions for registration:

2D Triangulations

  • To fix an inconsistency between code and documentation and to clarify which types of intersections are truly allowed in constrained Delaunay triangulations, the tag CGAL::No_intersection_tag has been deprecated in favor of two new tags: CGAL::No_constraint_intersection_tag and CGAL::No_constraint_intersection_requiring_constructions_tag. The latter is equivalent to the now-deprecated CGAL::No_intersection_tag, and allows constraints to intersect as long as no new point has to be created to represent that intersection (for example, the intersection of two constraint segments in a ‘T’-like junction is an existing point and as such does not require any new construction). The former tag, CGAL::No_constraint_intersection_tag, does not allow any intersection, except for the configuration of two constraints having a single common endpoints, for convience.
  • Added the function CGAL::split_subconstraint_graph_into_constraints() to Constrained_triangulation_plus_2 to initialize the constraints from a soup of disconnected segments that should first be split into polylines.

3D Triangulations

3D Triangulation Data Structure

Surface Mesh Simplification

  • Added a new simplification method based on the quadric error defined by Garland and Heckbert.
  • The concept EdgeProfile has been removed. This concept was not actually in use as the CGAL-provided model CGAL::Edge_profile was imposed to the user. Other concepts have been clarified to reflect the fact that the API uses this particular class.

STL Extensions for CGAL