CGAL 6.1 beta1 released

Changelog

General Changes

• The new list of supported compilers is:
  • Visual C++ 15.9, 16.10, 17.0 (from Visual Studio 2017, 2019 and 2022) or later
  • Gnu g++ 12.2.0 or later (on Linux)
  • LLVM Clang version 20.1.6 or later (on Linux)
  • Apple Clang compiler versions 12.0.5 and 12.0.5 (on macOS)
• The minimal supported version of Boost is now 1.74.0.

3D Constrained Triangulations (new package)

• This package implements the construction of a 3D Constrained Delaunay triangulation. This triangulation is a generalization of a 3D Delaunay Triangulation which conforms to the set of faces of a 3D piecewise linear complex (PLC), ensuring that these faces are part of the triangulation. As not all PLCs are tetrahedralizable, the algorithm may insert Steiner points to construct the constrained triangulation. The main entry point is the function CGAL::make_conforming_constrained_Delaunay_triangulation_3().

3D Isosurfacing (new package)

• This package provides algorithms to extract isosurfaces from scalar fields. The algorithms provided in this first version include Marching Cubes, Topologically Correct Marching Cubes, and Dual Contouring. The algorithm is generic with respect to the scalar field representation (implicit function, discrete values, …) and the discretization data structure (Cartesian grid, octree, …). The output is an indexed face set that stores an isosurface in the form of a surface mesh.

dD Fréchet Distance (new package)

• This package provides functions for computing the Fréchet distance of polylines in any dimension under the Euclidean metric.

2D Triangulations on Hyperbolic Surfaces (new package)

• This package enables building and handling triangulations of closed orientable hyperbolic surfaces. It offers functions for the generation of the triangulation from a convex fundamental domain, the Delaunay flip algorithm, and the construction of a portion of the lift of the triangulation in the Poincaré disk. A method is offered that generates such domains in genus two.

  See also the associated news entry.

Polygon Repair

• Added the non-zero rule (areas with non-zero winding number are kept), as well as two functions to compute the conservative inner and outer hull of similar polygons:
  • CGAL::Polygon_repair::join()
  • CGAL::Polygon_repair::intersect()

  See also the associated news entry.

Polygon Mesh Processing

• Added the parameter apply_iterative_snap_rounding to the function CGAL::Polygon_mesh_processing::autorefine_triangle_soup(). When set to true, the coordinates are rounded to fit in double and may perform additional subdivisions to ensure the output is free of self-intersections. See also the associated news entry.
• Added the function CGAL::Polygon_mesh_processing::approximated_centroidal_Voronoi_diagram_remeshing() to remesh triangle meshes. This remeshing algorithm uses clustering on polygonal meshes as to approximate a Centroidal Voronoi Diagram construction, and can move vertices as to recover sharp features and corners. See also the associated news entry.
• New implementation of CGAL::Polygon_mesh_processing::clip() and CGAL::Polygon_mesh_processing::split() with a plane as clipper that is much faster and is now able to handle non-triangulated surface meshes. See also the associated news entry.
• Added the function CGAL::Polygon_mesh_processing::refine_with_plane(), which enables users to refine a mesh with its intersection with a plane.
• Added a function in the visitor of the corefinement based methods to trace faces in the output meshes which correspond to coplanar faces of the input.
• Added the function CGAL::Polygon_mesh_processing::discrete_mean_curvature() and CGAL::Polygon_mesh_processing::discrete_Gaussian_curvature() to evaluate the discrete curvature at a vertex of a mesh.
• Added the function CGAL::Polygon_mesh_processing::angle_sum() to compute the sum of the angles around a vertex.

Point Set Processing

• Added CGAL::poisson_eliminate(), which can be used to downsample a point cloud to a target size while providing Poisson disk property, i.e., a larger minimal distance between points.

CGAL and the Boost Graph Library (BGL)

• Added the function dijkstra_shortest_path(), which can be used to compute the geometrically shortest sequence of halfedges between two vertices.
• Added the function CGAL::Euler::remove_degree_2_vertex(), which enables users to remove vertices which have exactly two incident edges.

2D Arrangements

• Breaking change: Renamed the concept AosApproximateTraits_2 to AosApproximatePointTraits_2 to make room for the new concept AosApproximateTraits_2. This concept requires the provision of a functor called Approximate_2 that has an operator that approximates the coordinates of a point.
• Breaking change: The concept AosApproximateTraits_2 now refines the concept AosApproximatePointTraits_2 and requires the provision of a functor called Approximate_2. In addition to an operator that approximates the coordinates of a point, it also requires the provision of (i) an operator that approximates a points, and (ii) an operator that approximates a curve.
• Renamed the prefix of the names of all concepts in the Arrangement_on_surface_2 package from “Arrangement” to “Aos”.
• Introduced two traits decorators, namely CGAL::Arr_tracing_traits_2 and CGAL::Arr_counting_traits_2, which can be used to extract debugging and informative metadata about the traits in use while a program is being executed.
• Fixed the Landmark point-location strategy so that it can be applied to arrangements on a sphere.
• Fixed a bug in the extensions of vertex and halfedge types of the DCEL when used to instantiate Arrangement_with_history_2 or similar arrangement classes that derive from Arrangement_2.
• Fixed do_intersect() of a 2D Arrangement with a curve.

Triangulations

• All triangulations now offer the functions point(Vertex_handle) and point(Simplex, int), which enables users to access the geometric position of a vertex and of the i-th vertex of a simplex of a triangulation.

Poisson Surface Reconstruction

• Added a new mesh domain Poisson_mesh_domain_3 that integrates some optimizations from the deprecated 3D Surface Mesh Generation package.

2D Triangulations

• Breaking change: In the class template Constrained_triangulation_plus_2, the value type of the range returned by subconstraints() has changed from const std::pair<const Subconstraint, std::list<Context>*> to Subconstraint. The old range type is now returned by a new function named subconstraints_and_contexts().

3D Mesh Generation

• Added two new meshing parameters that enable custom mesh initialization:
• initial_points_generator: enables the user to specify a functor that generates initial points,
• initial_points: enables the user to specify a Range of initial points.
• Added a new meshing parameter surface_only, which can be used to improve performance when only surface mesh generation is sought.
• Added a new mesh domain Poisson_mesh_domain_3, which should be used when generating a mesh from a Poisson surface obtained with the package Poisson Surface Reconstruction. This mesh domain re-integrates some optimizations for Poisson surface mesh generation that were lost when the package 3D Mesh Generation had to be replaced instead of the deprecated package 3D Surface Mesh Generation.

3D Subdivision Methods

• Added a new named parameter for CGAL::Subdivision_method_3::Loop_subdivision() and CGAL::Subdivision_method_3::CatmullClark_subdivision(), which enables users to subdivide a mesh without modifying its geometry.

Algebraic Kernel

• Breaking change: Classes based on the RS Library are no longer provided.