CGAL 4.12 beta2 released

Changelog

Important Notice

• The CMake scripts used by CGAL have been changed to use modern patterns introduced by CMake 2.8.12 and CMake 3.0: instead of setting CMake variables, the script now defines imported targets and uses link interfaces.
• That is mostly backward-compatible with existing usages of CGAL CMake scripts. The only non-compatible effect is that the CMAKE_BUILD_TYPE and compilation flags are no longer copied from the CGAL_DIR to the project using it. Note also that the CMAKE_BUILD_TYPE is no longer set to Release by default. For a developer using the Visual Studio IDE or the Xcode IDE, the change should be transparent. Developers using makefiles or the Ninja build-system should set the CMAKE_BUILD_TYPE to Release manually, to avoid using CGAL libraries without any compile-time optimization.

Header-only mode

• Since CGAL-4.9, it has been possible to use CGAL by configuring it using CMake, but without compiling the CGAL libraries. With CGAL-4.12, it is now possible to use CGAL header-only, without even configuring it. CMake is then used only to configure programs using CGAL.

2D Movable Separability of Sets (new package)

• A new package called “2D Movable Separability of Sets” has been introduced. It handles a class of problems that deal with moving sets of objects in the plane; the challenge is to avoid collisions between the objects while considering different kinds of motions and various definitions of separation.
• At this point this package consists of the implementations of various predicates and constructions related to castings of polygonal objects. In particular, it can be used to determine whether a feasible mold for a polygonal object does exist. If a mold exists, the package can also be used to compute all possible orientations of the feasible molds and the corresponding motions needed to remove the casted object from the mold.

Classification (new package)

• This package offers an algorithm that classifies a data set into a user-defined set of labels (such as ground, vegetation, buildings, etc.). A flexible API is provided so that users can classify any type of data, compute their own local features on the input data set, and define their own labels.

Kinetic Data Structures (removed package)

• This package has been removed from CGAL-4.12. Users of the package will have to keep using the source code available in CGAL-4.11 or earlier.

3D Convex Hull

• Breaking change: The header <CGAL/convex_hull_3.h> no longer includes <CGAL/Polyhedron_3.h>, as the convex hull function works with any model of the concept MutableFaceGraph.

2D Arrangements

• When removing an edge from an arrangement and the user has requested to remove the end-vertices in case they become redundant (either isolated or approach infinity), defer the removal of the such end-vertices to occur after the observer is notified that the edge has been removed. This is symmetric (opposite) to the order of notification when an edge is inserted.

  The user can restore old (non-symmetric) behaviour by defining the macro:

  CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY

2D Periodic Triangulations

• Breaking change: The class Periodic_2_triangulation_hierarchy_vertex_base_2 (and its corresponding header) have been removed. Users should directly use the class Triangulation_hierarchy_vertex_base_2, which is identical.
• Breaking change: The functions circumcenter(), side_of_oriented_circle(), and is_extensible_in_1_sheet_h[12]() are related to Delaunay triangulations and have been moved from Periodic_2_triangulation_2 to Periodic_2_Delaunay_triangulation_2.

2D Alpha Shapes

• It is now possible to use CGAL::Periodic_2_triangulation_2 as underlying triangulation for Alpha_shape_2.

3D Surface Mesh Generation

• Add the function facets_in_complex_2_to_triangle_mesh() that exports Surface_mesh_complex_2_in_triangulation_3 facets into a MutableFaceGraph.

3D Mesh Generation

• Add the function facets_in_complex_3_to_triangle_mesh() that exports Mesh_complex_3_in_triangulation_3 facets into a MutableFaceGraph.
• Breaking change: The concept MeshDomainWithFeatures_3 has been modified, to improve the performance and the reliability of the sampling of 1D curves of the domain.
• Add the ability to ensure that the output mesh surface describes a manifold, when the input surface is a manifold. New named parameters manifold(), manifold_with_boundary(), and non_manifold() are added.

Optimal Transportation Curve Reconstruction

• New method run_under_wasserstein_tolerance() which allows the user to perform curve reconstruction by relying on a threshold on the Wasserstein distance. This is useful when the number of edges in the expected output reconstruction is not known.

Polygon Mesh Processing

• Added two functions for orienting connected components :
  • CGAL::Polygon_mesh_processing::orient()
  • CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()
• Added a new function for intersection tests between triangle meshes and/or polylines or range of polylines, and another one to report all the pairs of meshes intersecting from a range of meshes:
  • CGAL::Polygon_mesh_processing::do_intersect()
  • CGAL::Polygon_mesh_processing::intersecting_meshes()
• Added new functions for feature detection and feature-guided segmentation:
  • CGAL::Polygon_mesh_processing::detect_sharp_edges()
  • CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()
  • CGAL::Polygon_mesh_processing::sharp_edges_segmentation()

Point Set Shape Detection

• New algorithm: CGAL::Region_growing. This is a deterministic alternative to RANSAC for plane detection.
• Breaking change: the API of CGAL::regularize_planes() is generalized to accept other types of input than the RANSAC output.
• Added a callback mechanism for both CGAL::Efficient_RANSAC and CGAL::Region_growing.

Point Set Processing

• Breaking change: the API of CGAL::structure_point_set() is generalized to accept other types of input than the RANSAC output.
• Breaking change: the API of all functions of Point Set Processing is modified to use ranges (instead of iterators) and Named Parameters (similarly to the API of Polygon Mesh Processing). The old API is kept as deprecated.

CGAL and the Boost Graph Library (BGL)

• Added helper function CGAL::expand_face_selection_for_removal that expands a face selection to avoid creating a non manifold mesh when removing the selected faces.
• Added support for dynamic property maps.
• Added an interface to the METIS library, which allows to partition any mesh that is a model of FaceListGraph. Wrappers to the METIS functions METIS_PartMeshNodal and METIS_PartMeshDual are offered.