CGAL 4.5 offers the following improvements and new functionality over CGAL 4.4:

## 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 notion of
- 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.