CGAL 4.3 released

Changelog

The CGAL Manual

• The documentation of CGAL is now generated with Doxygen.

2D Periodic Triangulations (new package)

• This package allows to build and handle triangulations of point sets in the two-dimensional flat torus. Triangulations are built incrementally and can be modified by insertion or removal of vertices. They offer point location facilities. The package provides Delaunay triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams.

API Changes

2D and 3D Geometry Kernel

• The intersection functions and functors used to return a CGAL::Object in order to deal with the different possible return types. However, depending on the arguments it is possible to reduce the possible return types to a small set. For this reason and to take advantage of the type safety, we decided to use boost::variant instead of CGAL::Object. The result_of protocol is now even more useful to determine the return type of the intersection functions and functors. The change should be relatively transparent to the user thanks to the implicit constructor added to CGAL::Object. However, it is recommended to upgrade your code. The previous behavior can be restored by defining the macro CGAL_INTERSECTION_VERSION to 1.

2D Arrangements

• The type of the result of point location queries changed to boost::variant (from CGAL::Object). For convenience, the previous behavior can be restored by defining the macro CGAL_ARR_POINT_LOCATION_VERSION to 1.
• Introduced an optimization for operations on large and dense arrangements.

3D Fast Intersection and Distance Computation

• Following the intersection API change, Object_and_primitive_id has been replaced by a template class Intersection_and_primitive_id<Query> to determine the type depending on the query object type.

CGAL and Boost Property Maps

• The key_type of the property maps provided by CGAL used to be an iterator. In order to be more easily re-used, the key_type has been changed to be the value_type of the iterator. The packages that have been updated to match these changes are Point Set Processing and Surface Reconstruction from Point Sets. However, for most users this change should be transparent if the default property maps were used. For convenience, the former behavior can be enabled by defining the macro CGAL_USE_PROPERTY_MAPS_API_V1.

Algebraic Foundations

• For convenience, added an overload of make_rational() taking a pair of numbers.

2D and 3D Geometry Kernel

• A Iso_rectangle_2 can now be constructed from a Bbox_2 and an Iso_cuboid_3 from a Bbox_3.
• The implementation of CGAL::Object has been updated and now uses boost::shared_ptr and boost::any. This implementation is faster.
• Added to Bbox_2 and Bbox_3 a += operator as well as free functions to get the bounding box of a range of geometric objects.

Combinatorial Maps

• Two bug fixes: do not use the 2 least significant bits for cell attribute without dart support; share the mark when copying a CMap_cell_iterator.
• Added a constructor taking a given combinatorial map as argument, possibly with different dimension and/or different attributes. This allows to transform a combinatorial map.
• Added operator= and swap method.
• Added dynamic onmerge/onsplit functions that can be associated dynamically to i-attributes and which are automatically called when i-cells are split/merged.
• Added a function allowing to reverse the orientation of a combinatorial map, and another one to reverse one connected component of a combinatorial map.

3D Boolean Operations on Nef Polyhedra

• Bug-fix in IO when using Lazy_exact_nt as number type or Exact_predicates_exact_constructions_kernel as kernel.

2D Triangulations

• Extended the concept TriangulationDataStructure_2 to require a more general copy_tds function that allows a copy between TDS of different types. The CGAL model has been updated.
• Added a way to efficiently insert a range of points with information into the 2D constrained Delaunay triangulations.

3D Triangulations

• Extended the concept TriangulationDataStructure_3 to require a more general copy_tds function that allows a copy between TDS of different types. The CGAL model has been updated.
• Added an advanced function to set the infinite vertex of the triangulation for low level operations
• Fixed a bug in the function inserting a range of points with info when the Fast_location tag is used

2D Segment Delaunay Graph

• Added functions insert_points and insert_segments to insert a range of points and segments. These functions uses the spatial sorting in order to speed up the time needed for the insertion. The function insert(Input_iterator first, Input_iterator beyond, Tag_true) has been updated to dispatch the input when possible to these functions.

2D Apollonius Graphs

• Modified insertion algorithm so that the code can handle pseudo-circles as well.
• Updated implementation of the vertex conflict predicate by a faster version.

3D Mesh Generation

• Sped-up Mesh_3 and in particular the global optimizers (Lloyd and ODT) by introducing a parameter do_freeze to prevent from moving vertices which would move of very small displacements.
• Introduce new data structures and options for speed-up and compacity. Note that Compact_mesh_cell_base_3 and Mesh_vertex_base_3 are now our favoured implementations of the concepts MeshCellBase_3 and MeshVertexBase_3.
• Introduced a new constructor for Polyhedral_mesh_domain_3 that takes a bounding polyhedron to be meshed along with a polyhedral surface entirely included in it. This allows the user to mesh a polyhedral domain with internal surface(s) which can be non-watertight and even non-manifold.
• Several documentation bug fixes.
• Provided the ability to plug in custom cell_base/vertex_base classes into the Mesh_triangulation_3 class.

Triangulated Surface Mesh Simplification

• Fixed a segmentation fault that was happening when some edges of length 0 were in the input mesh.

3D Fast Intersection and Distance Computation

• Following the intersection API change, Object_and_primitive_id has been replaced by a template class Intersection_and_primitive_id<Query> to determine the type depending on the query object type.
• Introduced the class AABB_halfedge_graph_segment_primitive, which replaces the class AABB_polyhedron_segment_primitive (which is now deprecated). The new class is more general and can be used with any model of HalfedgeGraph.
• Introduced the class AABB_face_graph_triangle_primitive which replaces the class AABB_polyhedron_triangle_primitive (which is now deprecated).
• Documented the classes AABB_segment_primitive and AABB_triangle_primitive that were already used in some examples.
• Add a generic primitive class AABB_primitive that allows to define a primitive type by defining only two property maps.
• Introduced a new concept of primitive AABBPrimitiveWithSharedData. It allows to have some data shared between the primitives stored in a AABB_tree. With this you can, for example have a primitive wrapping an integer which refers to the position of a geometric object in a std::vector. Only one reference to this vector will be stored in the traits of the tree. The concept AABBTraits, its model AABB_traits and the class AABB_tree have been updated accordingly. However, everything is backward compatible.
• Fixed a memory leak in the destructor of the class AABB-tree

STL Extensions for CGAL

• Added to Dispatch_output_iterator and Dispatch_or_drop_output_iterator an operator to accept and dispatch a tuple of values.

Concurrency in CGAL

• Added a FindTBB CMake module so that one can easily link with TBB to write shared-memory parallel code.
• Introduce two new tags: Sequential_tag and Parallel_tag.