CGAL 4.5 released

Changelog

Installation

• Changes in the set of supported platforms:
  • The Microsoft Windows Visual C++ compiler 2008 (VC9) is no longer supported since CGAL-4.5.
• Since CGAL version 4.0, Eigen was the recommended third-party library to use with Planar Parameterization of Triangulated Surface Meshes, Surface Reconstruction from Point Sets, Approximation of Ridges and Umbilics on Triangulated Surface Meshes, and Estimation of Local Differential Properties of Point-Sampled Surfaces packages. From CGAL version 4.5, Taucs, Blas and Lapack are no longer supported.
• CGAL is now compatible with the new CMake version 3.0.

Triangulated Surface Mesh Deformation (new package)

• This package allows to deform a triangulated surface mesh under positional constraints of some of its vertices without requiring any additional structure other than the surface mesh itself. The methods provided implements an as-rigid-as-possible deformation. Note that the main class name has changed between the 4.5-beta1 and the 4.5 releases to better match the CGAL naming conventions (from CGAL::Deform_mesh to CGAL::Surface_mesh_deformation).

CGAL and the Boost Graph Library (major changes)

• Cleanup of the HalfedgeGraph concept. In particular:
  • Introduction of the notion of halfedge_descriptor in the specialization of the class boost::graph_traits.
  • Deprecation of halfedge_graph_traits.
  • A model of HalfedgeGraph is considered as an undirected graph. Thus any call to edges() should be replaced by halfedges() and num_edges() now returns the number of (undirected) edges.
  • Breaking change: is_border_edge and is_border_halfedge properties are removed. The free functions is_border() and is_border_edge() should be used instead.
  • Renaming of HalfedgeGraph specific free functions.
• Introduction of the FaceGraph concept.
• Adaptation of the package Triangulated Surface Mesh Simplification and of the class AABB_halfedge_graph_segment_primitive from the package 3D Fast Intersection and Distance Computation to the API change.
• Update of the package Triangulated Surface Mesh Segmentation and of the class AABB_face_graph_triangle_primitive from the package 3D Fast Intersection and Distance Computation to accept model of the newly introduced concepts.
• Offer Euler operations as free functions for models of the graph concepts provided by CGAL.
• Specialization of boost::graph_traits for OpenMesh::PolyMesh_ArrayKernelT as proof of concept. A OpenMesh::PolyMesh_ArrayKernelT becomes a model of the aforementioned concepts when including CGAL/boost/graph/graph_traits_PolyMesh_ArrayKernelT.h.

dD Geometry Kernel

• A new model Epick_d of the Kernel_d concept is introduced. It provides better performance through arithmetic filtering and specializations for fixed dimensions. It may not work with compilers as old as gcc-4.2, but was tested with gcc-4.4.

3D Convex Hulls

• Clean up the documentation of the concepts

2D Arrangements

• Fixed a bug in removing an unbounded curve (e.g., a ray) from an arrangement induced by unbounded curves.

2D Snap Rounding

• Replaced use of private kd_tree with CGAL’s official Kd_tree from Spatial_searching package; results in a small performance gain. Removed the private kd_tree package.

3D Triangulations

• Added an experimental parallel version of the Delaunay triangulation and the regular triangulation algorithms, which allows parallel insertion and removal of point ranges.
• Added caching of circumcenters to Regular_triangulation_cell_base_3. The cache value is computed when cell->circumcenter() or rt.dual(cell) functions are called.

3D Periodic Triangulations

• Added a method to locate point with inexact predicates.

3D Mesh Generation

• Added a new constructor for the class Labeled_mesh_domain_3 which takes an Iso_cuboid_3.
• Added a new labeling function wrapper for meshing multi-domain.
• The meshing functionality in the Qt demos in demo/Polyhedron/ and demo/Mesh_3/ can now use the handling of 1d-features, that exists in CGAL since version 3.8.
• Added an experimental parallel version of the 3D mesh refinement and mesh optimization methods.

Point Set Processing and Surface Reconstruction from Point Sets

• The former demo has been removed and is fully merge in the Polyhedron demo.

Point Set Processing

• Workaround a bug in dijsktra shortest path of boost 1.54 by shipping and using the boost header from the 1.55 release. This header will be used only if you are using the version 1.54 of boost.

Triangulated Surface Mesh Simplification

• Breaking change: Due to the cleanup of the concepts of the package CGAL and the Boost Graph Library, the named parameter edge_is_border_map has been removed, and the named parameter edge_is_constrained_map now expects a property map with an edge descriptor as key type (vs. halfedge descriptor before).
• Added some optimization in the code making the implementation faster (depending on the cost and the placement chosen). However, for an edge which collapse is not topologically valid, the vector of vertices of the link provided by its profile might contains duplicates, thus also breaking the orientation guarantee in the vector. This must not be a problem for users as the edge is not collapsible anyway but if it is a absolute requirement for user defined cost/placement, defining the macro CGAL_SMS_EDGE_PROFILE_ALWAYS_NEED_UNIQUE_VERTEX_IN_LINK will restore the former behavior.

dD Spatial Searching

• Added methods reserve(size_t size) and size_t capacity() to class Kd_tree to allocate memory to store size points and to report that number (STL compliance).

STL Extensions for CGAL

• Added Compact_container::operator[], allowing a direct access to the ith element of a compact container.
• Added Concurrent_compact_container, a compact container which allows concurrent insertion and removal.