CGAL 5.1 offers the following improvements and new functionality over CGAL 5.0:
Changelog
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.
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 noncontractible 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.
Installation
 The CGAL_Core library no longer requires
Boost.Thread
, even if the g++ compiler is used.
Tutorials
 Two new, detailed tutorials have been added:
 Surface Reconstruction from Point Clouds, which goes over a typical full processing pipeline in a CGAL environment.
 Geographic Information Systems (GIS), which demonstrates usage of CGAL data structures and algorithms in the context of a typical GIS application.
Both tutorials provide complete code.
2D and 3D Linear Geometry Kernel
 Added the functor
CompareSignedDistanceToLine_2
to the 2D/3DKernel
concept to compare the signed distance of two points to a line, or the line passing through two given points. Corresponding functors in the model (Compare_signed_distance_to_line_2
) are also added.
dD Geometry Kernel
 The kernels
Epick_d
andEpeck_d
gain two new functors:Power_side_of_bounded_power_sphere_d
andCompute_squared_radius_smallest_orthogonal_sphere_d
. Those are essential for the computation of weighted alphacomplexes.
Surface Mesh
 Breaking change: The function
CGAL::Surface_mesh::clear()
now removes all nondefault properties instead of just emptying them.
CGAL and the Boost Graph Library (BGL)
 Added the function
CGAL::alpha_expansion_graphcut()
, which regularizes a multilabel partition over a userdefined graph.  Added the function
CGAL::regularize_face_selection_borders()
, which uses this alpha expansion graphcut to regularize the borders of a selected faces on a triangle mesh.  Added the function
CGAL::set_triangulation_ids()
, which must be used to initialize vertex, edge, and face indices of a triangulation meant to be used with BGL algorithms.
3D Fast Intersection and Distance Computation
 The behavior of the internal search tree used to accelerate distance queries has changed:
usage of the internal search tree will now be enabled by default, and its construction
will be triggered by the first distance query. Automatic construction and usage can be disabled
by calling
CGAL::AABB_tree::do_not_accelerate_distance_queries()
before the first distance query, and the tree can be built at any moment by callingCGAL::AABB_tree::accelerate_distance_queries()
.  Breaking change:
CGAL::AABB_tree::accelerate_distance_queries()
andCGAL::AABB_tree::do_not_accelerate_distance_queries()
are no longerconst
functions.
2D Arrangements
 Changed intersection return type from legacy
CGAL::Object
to modernboost::variant
in all traits concepts and models. As there exists an implicit conversion fromboost::variant
toCGAL::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 SetOperations
 Changed intersection return type from legacy
CGAL::Object
to modernboost::variant
in the conceptArrDirectionalTraits::Intersect_2
and its models.
2D Minkowski Sums
 Changed intersection return type from legacy
CGAL::Object
to modernboost::variant
in the (internally used) modelArr_labeled_traits_2
.
dD Spatial Searching
 The kdtree can now be built in parallel:
CGAL::Kd_tree::build()
is given an optional template parameterConcurrencyTag
(default value remainsCGAL::Sequential_tag
for backward compatibility).  Improved the performance of the kdtree in some cases:
 Not storing the points coordinates inside the tree usually
generates a lot of cache misses, leading to nonoptimal
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 recreated by the kdtree in a cachefriendly order after its construction, so the coordinates are more likely to be stored in a nearoptimal order on the heap. In these cases, the newEnablePointsCache
template parameter of theCGAL::Kd_tree
class can be set toCGAL::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 updatedGeneralDistance
andFuzzyQueryItem
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) kNN search to interrupt some distance computations before its end, saving precious milliseconds, in particular in mediumtohigh dimension.
 Not storing the points coordinates inside the tree usually
generates a lot of cache misses, leading to nonoptimal
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.,
Intersecting Sequences of dD Isooriented Boxes
 Added parallel versions of the functions
CGAL::box_intersection_d()
andCGAL::box_self_intersection_d()
.
Spatial Sorting
 Added parallel versions of the functions
CGAL::hilbert_sort()
andCGAL::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
 A new overload for
CGAL::convex_hull_3()
that takes a model ofVertexListGraph
has been added.  The longdeprecated function
CGAL::convex_hull_3_to_polyhedron_3()
has been removed. The functionCGAL::convex_hull_3_to_face_graph()
should be used instead.
Polygon Mesh Processing
 Added the function
CGAL::Polygon_mesh_processing::volume_connected_component()
, which can be used to get information about the nesting of the connected components of a given triangle mesh and about the volumes defined.  Added the function
CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size()
, which can be used to remove connected components whose area or volume is under a certain threshold. Area and volume thresholds are either specified by the user or deduced from the bounding box of the mesh.  Added a new named parameter for
CGAL::Polygon_mesh_processing::keep_large_connected_components()
andCGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size
, which can be used to perform a dry run of the operation, meaning that the function will return the number of connected components that would be removed with the specified threshold, but without actually removing them.  Added the function
CGAL::Polygon_mesh_processing::split()
, which can be used to split meshes along a mesh or a plane.  Added the function
CGAL::Polygon_mesh_processing::split_connected_components()
to split a single mesh containing several connected components into several meshes containing one connected component.  Added the functions
CGAL::Polygon_mesh_processing::merge_reversible_connected_components()
,CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup()
, andCGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh()
, which can be helpful when repairing a polygon soup.  Added the function
CGAL::Polygon_mesh_processing::sample_triangle_soup()
, which generates points on a triangle soup surface.  Added parallel versions of the functions
CGAL::Polygon_mesh_processing::does_self_intersect()
andCGAL::Polygon_mesh_processing::self_intersections()
.  The function
CGAL::Polygon_mesh_processing::stitch_borders()
now returns the number of halfedge pairs that were stitched.  Added the function
CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup()
.  The function
CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh
now allows passing a point map (for the point range) and a vertex point map (for the polygon mesh) via named parameters.
Point Set Processing
 Breaking change:
CGAL::remove_outliers()
has been parallelized and thus has a new template parameterConcurrencyTag
. To update your code simply add as first template parameterCGAL::Sequential_tag
orCGAL::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:
CGAL::OpenGR::compute_registration_transformation()
, which computes the registration transformation for two point sets using the Super4PCS algorithm implemented in the third party library OpenGR.CGAL::OpenGR::register_point_sets()
, which computes the registration transformation for two point sets using the Super4PCS algorithm implemented in the third party library OpenGR, and registers the points sets by transforming the data point set using the computed transformation.CGAL::pointmatcher::compute_registration_transformation()
computes the registration transformation for two point sets using ICP algorithm implemented in the third party library libpointmatcher.CGAL::pointmatcher::register_point_sets()
, which computes the registration transformation for two point sets using ICP algorithm implemented in the third party library libpointmatcher, and registers the points sets by transforming the data point set using the computed transformation.
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
andCGAL::No_constraint_intersection_requiring_constructions_tag
. The latter is equivalent to the nowdeprecatedCGAL::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()
toConstrained_triangulation_plus_2
to initialize the constraints from a soup of disconnected segments that should first be split into polylines.
3D Triangulations
 The member function
CGAL::Triangulation_3::file_input()
have been added. It allows to load aCGAL::Triangulation_3
from an input stream, using functors to create vertices and cells.
3D Triangulation Data Structure
 The member function
CGAL::TDS_3::file_input()
have been added. It allows to load aCGAL::Triangulation_data_structure_3
from an input stream, using functors to create vertices and cells.
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 CGALprovided modelCGAL::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
 Added a new concurrency tag:
CGAL::Parallel_if_available_tag
. This tag is a convenience typedef toCGAL::Parallel_tag
if the third party library TBB has been found and linked with, and toCGAL::Sequential_tag
otherwise.