CGAL 3.2 released

Changelog

Supported platforms

• For Visual C++, the installation scripts choose the multi-threaded dynamically linked runtime (/MD). Before it was the single-threaded static runtime (/ML).

No longer supported

• SunPro CC versions 5.4 and 5.5 on Solaris
• SGI Mips Pro

Installation

• The install tool tries to find third party libraries at “standard” locations.
• Installers for Apple, Windows, and rpms.

Manuals

• User and Reference manual pages of a package are now in the same chapter.

2D Circular Kernel (new package)

• This package is an extension of the linear CGAL Kernel. It offers functionalities on circles, circular arcs and line segments in the plane.

2D Regularized Boolean Set-Operations (new package)

• This package consists of the implementation of Boolean set-operations on point sets bounded by weakly x-monotone curves in 2-dimensional Euclidean space. In particular, it contains the implementation of regularized Boolean set-operations, intersection predicates, and point containment predicates.

2D Straight Skeleton and Polygon Offsetting (new package)

• This package implements an algorithm to construct a halfedge data structure representing the straight skeleton in the interior of 2D polygons with holes and an algorithm to construct inward offset polygons at any offset distance given a straight skeleton.

2D Voronoi Diagram Adaptor (new package)

• This package provides an adaptor that adapts a 2-dimensional triangulated Delaunay graph to the corresponding Voronoi diagram, represented as a doubly connected edge list (DCEL) data structure. The adaptor has the ability to automatically eliminate, in a consistent manner, degenerate features of the Voronoi diagram, that are artifacts of the requirement that Delaunay graphs should be triangulated even in degenerate configurations. Depending on the type of operations that the underlying Delaunay graph supports, the adaptor allows for the incremental or dynamic construction of Voronoi diagrams and can support point location queries.

3D Surface Mesher (new package)

• This package provides functions to generate surface meshes that interpolate smooth surfaces. The meshing algorithm is based on Delaunay refinement and provides some guarantees on the resulting mesh: the user is able to control the size and shape of the mesh elements and the accuracy of the surface approximation. There is no restriction on the topology and number of components of input surfaces. The surface mesher may also be used for non smooth surfaces but without guarantee.
• Currently, implementations are provided for implicit surfaces described as the zero level set of some function and surfaces described as a gray level set in a three-dimensional image.

3D Surface Subdivision Methods (new package)

• Subdivision methods recursively refine a control mesh and generate points approximating the limit surface. This package consists of four popular subdivision methods and their refinement hosts. Supported subdivision methods include Catmull-Clark, Loop, Doo-Sabin and sqrt(3) subdivisions. Their respective refinement hosts are PQQ, PTQ, DQQ and sqrt(3) refinements. Variations of those methods can be easily extended by substituting the geometry computation of the refinement host.

Planar Parameterization of Triangulated Surface Meshes (new package)

• Parameterizing a surface amounts to finding a one-to-one mapping from a suitable domain to the surface. In this package, we focus on triangulated surfaces that are homeomorphic to a disk and on piecewise linear mappings into a planar domain. This package implements some of the state-of-the-art surface mesh parameterization methods, such as least squares conformal maps, discrete conformal map, discrete authalic parameterization, Floater mean value coordinates or Tutte barycentric mapping.

Principal Component Analysis (new package)

• This package provides functions to compute global informations on the shape of a set of 2D or 3D objects such as points. It provides the computation of axis-aligned bounding boxes, centroids of point sets, barycenters of weighted point sets, as well as linear least squares fitting for point sets in 2D, and point sets as well as triangle sets in 3D.

2D Placement of Streamlines (new package)

• Visualizing vector fields is important for many application domains. A good way to do it is to generate streamlines that describe the flow behaviour. This package implements the “Farthest Point Seeding” algorithm for placing streamlines in 2D vector fields. It generates a list of streamlines corresponding to an input flow using a specified separating distance. The algorithm uses a Delaunay triangulation to model objects and adress different queries, and relies on choosing the centers of the biggest empty circles to start the integration of the streamlines.

Kinetic Data Structures (new package)

• Kinetic data structures allow combinatorial structures to be maintained as the primitives move. The package provides implementations of kinetic data structures for Delaunay triangulations in two and three dimensions, sorting of points in one dimension and regular triangulations in three dimensions. The package supports exact or inexact operations on primitives which move along polynomial trajectories.

Kinetic Framework (new package)

• Kinetic data structures allow combinatorial geometric structures to be maintained as the primitives move. The package provides a framework to ease implementing and debugging kinetic data structures. The package supports exact or inexact operations on primitives which move along polynomial trajectories.

Smallest Enclosing Ellipsoid (new package)

• This algorithm is new in the chapter Geometric Optimisation.

2D Arrangement (major revision)

• This package can be used to construct, maintain, alter, and display arrangements in the plane. Once an arrangement is constructed, the package can be used to obtain results of various queries on the arrangement, such as point location. The package also includes generic implementations of two algorithmic frameworks, that are, computing the zone of an arrangement, and line-sweeping the plane, the arrangements is embedded on.
• Arrangements and arrangement components can also be extended to store additional data. An important extension stores the construction history of the arrangement, such that it is possible to obtain the originating curve of an arrangement subcurve.

Geometric Optimisation (major revision)

• The underlying QP solver which is the foundation for several algorithms in the Geometric Optimisation chapter has been completely rewritten.

3D Triangulation (new functionality)

• Regular_triangulation_3 now offers vertex removal.