CGAL 5.0 beta1 released

Changelog

General changes

• CGAL 5.0 is the first release of CGAL that requires a C++ compiler with the support of C++14 or later. The new list of supported compilers is:
  • Visual C++ 14.0 (from Visual Studio 2015 Update 3) or later,
  • Gnu g++ 6.3 or later (on Linux or MacOS),
  • LLVM Clang version 8.0 or later (on Linux or MacOS), and
  • Apple Clang compiler versions 7.0.2 and 10.0.1 (on MacOS).
• Since CGAL 4.9, CGAL can be used as a header-only library, with dependencies. Since CGAL 5.0, that is now the default, unless specified differently in the (optional) CMake configuration.

Polygonal Surface Reconstruction (new package)

• This package provides a method for piecewise planar object reconstruction from point clouds. The method takes as input an unordered point set sampled from a piecewise planar object and outputs a compact and watertight surface mesh interpolating the input point set. The method assumes that all necessary major planes are provided (or can be extracted from the input point set using the shape detection method described in Point Set Shape Detection, or any other alternative methods).The method can handle arbitrary piecewise planar objects and is capable of recovering sharp features and is robust to noise and outliers. See also the associated blog entry.

Shape Detection (major changes)

• Breaking change: The concept ShapeDetectionTraits has been renamed to EfficientRANSACTraits.
• Breaking change: The Shape_detection_3 namespace has been renamed to Shape_detection.
• Added a new, generic implementation of region growing. This enables for example applying region growing to inputs such as 2D and 3D point sets, or models of the FaceGraph concept. Learn more about this new algorithm with this blog entry.

dD Geometry Kernel

• A new exact kernel, Epeck_d, is now available.

2D and 3D Linear Geometry Kernel

• Added ComputeApproximateAngle_3 in the 2D/3D Kernel concepts to compute the approximate angle between 2 vectors. Corresponding functors in the model (Compute_approximate_angle_3) and free function (approximate_angle) are also added.
• The following objects are now hashable and thus trivially usable with std::unordered_set and std::unordered_map: CGAL::Aff_transformation_2, CGAL::Aff_transformation_3, CGAL::Bbox_2, CGAL::Bbox_3, CGAL::Circle_2, CGAL::Iso_cuboid_3, CGAL::Iso_rectangle_2, CGAL::Point_2, CGAL::Point_3, CGAL::Segment_2, CGAL::Segment_3, CGAL::Sphere_3, CGAL::Vector_2, CGAL::Vector_3, CGAL::Weighted_point_2 and CGAL::Weighted_point_3.

Polygon Mesh Processing

• Introduced a wide range of new functions related to location of queries on a triangle mesh, such as CGAL::Polygon_mesh_processing::locate(Point, Mesh). The location of a point on a triangle mesh is expressed as the pair of a face and the barycentric coordinates of the point in this face, enabling robust manipulation of locations (for example, intersections of two 3D segments living within the same face).
• Added the mesh smoothing function smooth_mesh(), which can be used to improve the quality of triangle elements based on various geometric characteristics.
• Added the shape smoothing function smooth_shape(), which can be used to smooth the surface of a triangle mesh, using the mean curvature flow to perform noise removal. (See also the new entry in the User Manual)
• Added the function CGAL::Polygon_mesh_processing::centroid(), which computes the centroid of a closed triangle mesh.
• Added the functions CGAL::Polygon_mesh_processing::stitch_boundary_cycle() and CGAL::Polygon_mesh_processing::stitch_boundary_cycles(), which can be used to try and merge together geometrically compatible but combinatorially different halfedges that belong to the same boundary cycle.
• It is now possible to pass a face-size property map to CGAL::Polygon_mesh_processing::keep_large_connected_components() and CGAL::Polygon_mesh_processing::keep_largest_connected_components(), enabling users to define how the size of a face is computed (the size of the connected component is the sum of the sizes of its faces). If no property map is passed, the behavior is unchanged to previous versions: the size of a connected component is the number of faces it contains.
• Added the function CGAL::Polygon_mesh_processing::non_manifold_vertices(), which can be used to collect all the non-manifold vertices (i.e. pinched vertices, or vertices appearing in multiple umbrellas) of a mesh.

3D Point Set

• The PLY IO functions now take an additional optional parameter to read/write comments from/in the PLY header.

Point Set Processing

• Breaking change: the API using iterators and overloads for optional parameters (deprecated since CGAL 4.12) has been removed. The current (and now only) API uses ranges and Named Parameters.
• Added the possibility to use the named parameter neighbor_radius to use spherical neighbor queries instead of K-nearest neighbors queries for the following functions: CGAL::bilateral_smooth_point_set(), CGAL::jet_estimate_normals(), CGAL::jet_smooth_point_set(), CGAL::mst_orient_normals(), CGAL::pca_estimate_normals() and CGAL::remove_outliers().

2D Triangulations

• Breaking change: Removed the deprecated functions CGAL::Constrained_triangulation_plus_2:: vertices_in_constraint_{begin/end}(Vertex_handle va, Vertex_handle vb) const;, and CGAL::Constrained_triangulation_plus_2::remove_constraint(Vertex_handle va, Vertex_handle vb), that is a pair of vertex handles is no longer a key for a polyline constraint. Users must use a version prior to 5.0 if they need this functionality.
• Breaking change: Removed the deprecated classes CGAL::Regular_triangulation_euclidean_traits_2, CGAL::Regular_triangulation_filtered_traits_2. Users must use a version prior to 5.0 if they need these classes.
• Breaking change: The graph traits enabling CGAL’s 2D triangulations to be used as a parameter for any graph-based algorithm of CGAL (or boost) have been improved to fully model the FaceGraph concept. In addition, only the finite simplicies (those not incident to the infinite vertex) of the 2D triangulations are now visibile through this scope. The complete triangulation can still be accessed as a graph, by using the graph traits of the underlying triangulation data structure (usually, CGAL::Triangulation_data_structure_2).
• Breaking change: The insert() function of CGAL::Triangulation_2 which takes a range of points as argument is now guaranteed to insert the points following the order of InputIterator. Note that this change only affects the base class Triangulation_2 and not any derived class, such as Delaunay_triangulation_2.
• Added a new constructor and insert() function to CGAL::Triangulation_2 that takes a range of points with info.
• Introduced a new face base class, Triangulation_face_base_with_id_2 which enables storing user-defined integer IDs in the face of any 2D triangulation, a precondition to use some BGL algorithms.
• Added range types and functions that return ranges, for example for all vertices, enabling the use of C++11 for-loops. See this new example for a usage demonstration.

3D Triangulations

• Breaking change: The constructor and the insert() function of CGAL::Triangulation_3 which take a range of points as argument are now guaranteed to insert the points following the order of InputIterator. Note that this change only affects the base class Triangulation_3 and not any derived class, such as Delaunay_triangulation_3.
• Added constructor and insert() function to CGAL::Triangulation_3 that takes a range of points with info.
• Added range types and functions that return ranges, for example for all vertices, which enables to use C++11 for-loops. See this new example for a usage demonstration.

Surface Mesh

• Introduced new functions to read and write using the PLY format, CGAL::read_ply() and CGAL::write_ply(), enabling users to save and load additional property maps of the surface mesh.

CGAL and Solvers

• Added concepts and models for solving Mixed Integer Programming (MIP) problems with or without constraints.

3D Boolean Operations on Nef Polyhedra

• Added a function to convert a Nef_polyhedron_3 to a polygon soup: CGAL::convert_nef_polyhedron_to_polygon_soup()

IO Streams

• Breaking change: The API of CGAL::Color has been cleaned up.
• Added new functions to support some parts of the WKT file format:
  • CGAL::read_WKT()
  • CGAL::read_point_WKT()
  • CGAL::read_multi_point_WKT()
  • CGAL::read_linestring_WKT()
  • CGAL::read_multi_linestring_WKT()
  • CGAL::read_polygon_WKT()
  • CGAL::read_multi_polygon_WKT()
  • CGAL::write_point_WKT()
  • CGAL::write_polygon_WKT()
  • CGAL::write_linestring_WKT()
  • CGAL::write_multi_point_WKT()
  • CGAL::write_multi_polygon_WKT()
  • CGAL::write_multi_linestring_WKT()