CGAL 3.6 released

Changelog

General

• Boost version 1.34.1 (or later) is now required.

Arithmetic and Algebra

Algebraic Kernel (new package)

• This new package is targeted to provide black-box implementations of state-of-the-art algorithms to determine, compare and approximate real roots of univariate polynomials and bivariate polynomial systems. It includes models of the univariate algebraic kernel concept, based on the library RS.

Number Types

• Two new arbitrary fixed-precision floating-point number types have been added: the scalar type Gmpfr and the interval type Gmpfi, based on the MPFR and MPFI libraries respectively.

Geometry Kernels

2D and 3D Geometry Kernel

• Add new do_intersect() and intersection() overloads:
  • do_intersect(Bbox_3, Bbox_3/Line_3/Ray_3/Segment_3)
  • intersection(Triangle_3, Line_3/Ray_3/Segment_3)

Polygons

2D Regularized Boolean Set-Operations

• Fixed General_polygon_set_2::arrangement() to return the proper type of object.

Arrangement

2D Arrangements

• Fixed passing a (const) traits object to the constructor of Arrangement_2.
• Introduced Arrangement_2::fictitious_face(), which returns the fictitious face in case of an unbounded arrangement.
• Fixed a bug in Bezier-curve handling.
• Added (back) iterator, number_of_holes(), holes_begin(), and holes_end() to the default DCEL for backward compatibility.
• Added (simple) versions of the free overlay() function. It employs the default overlay-traits, which practically does nothing.

Polyhedron

• Fixed a compilation errors in demo/Polyhedron/:
  • issue with the location of qglobal.h of Qt4 on MacOS X,
  • missing texture.cpp, if TAUCS is used,
• Fixed the location of built plugins of demo/Polyhedron/, when CGAL is configured with WITH_demos=ON
• Fixed a bug in test_facet function of the incremental builder: the function did not test if while a new facet makes a vertex manifold, no other facet incident to that vertex breaks the manifold property.

Triangulations and Delaunay Triangulations

2D/3D Regular Triangulations

• Weighted_point now has a constructor from Cartesian coordinates.

3D Triangulations

• Regular_triangulation_3: semi-static floating-point filters are now used in its predicates, which can speed up its construction by a factor of about 3 when Exact_predicates_inexact_constructions_kernel is used.
• The class Regular_triangulation_filtered_traits_3 is deprecated, the class Regular_triangulation_euclidean_traits_3 must be used instead. The predicates of that traits will be filtered if the kernel given as template parameter of that traits is itself a filtered kernel.
• Triangulation_hierarchy_3 is now deprecated, and replaced by a simpler CGAL::Fast_location policy template parameter of Delaunay_triangulation_3.
• The old version of remove() (enabled with CGAL_DELAUNAY_3_OLD_REMOVE) has been deleted.

3D Periodic Triangulations

• New demo: 3D periodic Lloyd algorithm.
• New functionality for Voronoi diagrams: dual of an edge and of a vertex, volume and centroid of the dual of a vertex.
• The package can now be used with the 3D Alpha Shapes package to compute periodic alpha shapes.

3D Alpha shapes

• The class Weighted_alpha_shape_euclidean_traits_3 is deprecated, the class Regular_triangulation_euclidean_traits_3 must be used instead.
• The package can now be used together with the 3D Periodic Triangulation package to compute periodic alpha shapes.

2D/3D Triangulations, 2D Segment Delaunay Graph, 2D Apollonius Graph, and 3D Periodic Triangulations

• The constructor and insert function taking ranges now produce structures whose iterator orders is now deterministic (same at each run).

Mesh Generation

2D Mesh Generation

• The 2D mesh generator can now be used with a constrained Delaunay triangulation with constraints hierarchy (Constrained_triangulation_plus_2).
• In some cases (refinement of a constrained edge that is on the convex hull), the 2D mesh generator from CGAL-3.4 and CGAL-3.5 could create invalid triangulations. This bug is now fixed.

3D Mesh Generation

• The mesh generator has been enriched with an optimization phase to provide 3D meshes with well shaped tetrahedra (and in particular no slivers). The optimization phase involves four different optimization processes: two global optimization processes (ODT and Lloyd), a perturber and an exuder. Each of these processes can be activated or not, and tuned to the users needs and to available computer resources.

Support library

CGAL ipelets

• Add support for version 7 of Ipe.