CGAL 3.3 released

Changelog

Supported Platforms

• GNU g++ 4.1 and 4.2
• Intel C++ compiler 9
• Microsoft Visual C++ compiler 8.0

No longer supported

• Intel 8

General

• CGAL now supports Visual C++ “Checked iterators” as well as the debug mode of GNU g++’s STL (-D_GLIBCXX_DEBUG).
• CGAL now works around the preprocessor macros ‘min’ and ‘max’ defined in <windows.h> which were clashing with min/max functions.

Installation

• On Windows the libraries built in Developer Studio now have names which encode the compiler version, the runtime and whether it was built in release or debug mode. The libraries to link against are chosen with linker pragmas in header files.
• On all platforms but Windows shared and static versions of the libraries are generated.

Manuals

• The Package Overview page now also hosts the precompiled demos.

Algebraic Foundations (new package)

• This package defines what algebra means for CGAL, in terms of concepts, classes and functions. The main features are:
  • explicit concepts for interoperability of types
  • separation between algebraic types (not necessarily embeddable into the reals), and number types (embeddable into the reals).

Surface Mesh Simplification (new package)

• This package provides a mesh simplification framework using edge collapse operations, and provides the Turk/Lindstrom simplification algorithm.

Skin Surface Meshing (new package)

• This package allows to build a triangular mesh of a skin surface. Skin surfaces are used for modeling large molecules in biological computing. The surface is defined by a set of balls, representing the atoms of the molecule, and a shrink factor that determines the size of the smooth patches gluing the balls together.

Estimation of Local Differential Properties (new package)

• This package allows to compute local differential quantities of a surface from a point sample.

Approximation of Ridges and Umbilics on Triangulated Surface Meshes (new package)

• This package enables the approximation of differential features on triangulated surface meshes. Such curvature related features are lines: ridges or crests, and points: umbilics.

Envelopes of Curves in 2D (new package)

• This package contains two sets of functions that construct the lower and upper envelope diagram for a given range of bounded or unbounded curves.

Envelopes of Surfaces in 3D (new package)

• This package contains two sets of functions that construct the lower and upper envelope diagram for a given range of bounded or unbounded surfaces. The envelope diagram is realized as a 2D arrangement.

Minkowski Sums in 2D (new package)

• This package contains functions for computing planar Minkowski sums of two closed polygons, and for a polygon and a disc (an operation also known as offsetting or dilating a polygon). The package also contains an efficient approximation algorithm for the offset computation, which provides a guaranteed approximation bound while significantly expediting the running times w.r.t. the exact computation procedure.

Surface Mesh Parametrization

• Added Jacobi and SSOR preconditioners to OpenNL solver, which makes it much faster and more stable.

2D Arrangements

• Added support for unbounded curves.
• Added a traits class that supports bounded and unbounded linear objects, namely lines, rays and line segments.
• Added traits classes that handle circular arcs based on the circular kernel.
• Added a traits class that supports Bezier curves.
• Enhanced the traits class that supports rational functions to handle unbounded (as well as bounded) arcs
• Added a free function called decompose() that produces the symbolic vertical decomposition of a given arrangement, performing a batched vertical ray-shooting query from all arrangement vertices.
• Fixed a memory leak in the sweep-line code.
• Fixed a bug in computing the minor axis of non-degenerate hyperbolas.

Boolean Set Operations

• Added the DCEL as a default template parameter to the General_polygon_set_2 and Polygon_set_2 classes. This allows users to extend the DCEL of the underlying arrangement.
• Added a function template called connect_holes() that connects the holes in a given polygon with holes, turning it into a sequence of points, where the holes are connceted to the outer boundary using zero-width passages.
• Added a non-const function member to General_polygon_set_2 that obtains the underlying arrangement.

2D and 3D Triangulations

• The constructors and insert member functions which take an iterator range perform spatial sorting in order to speed up the insertion.

Optimal Distances

• Polytope_distance_d: has support for homogeneous points; bugfix in fast exact version.

Bounding Volumes

• Min_annulus_d has support for homogeneous points; bugfix in fast exact version.

Number Types

• Fixed_precision_nt and Filtered_exact number types have been removed.

2D Circular Kernel

• Efficiency improved through geometric filtering of predicates, introduced with the filtered kernel Filtered_bbox_circular_kernel_2, and also chosen for the predefined kernel Exact_circular_kernel_2.

Linear Kernel

• Exact_predicates_exact_constructions_kernel memory and run-time improvements through usage of lazy geometric constructions instead of lazy arithmetic.

CGAL and the Boost Graph Library (BGL) (new package)

• This package provides the glue layer for several CGAL data structures such that they become models of the BGL graph concept.

Spatial Sorting (new package)

• This package allows to sort points and other objects along a Hilbert curve which can improve the performance of algorithms like triangulations. It is used by the constructors of the triangulation package which have an iterator range of points as argument.

Linear and Quadratic Programming Solver (new package)

• This package contains algorithms for minimizing linear and convex quadratic functions over polyhedral domains, described by linear equations and inequalities.