cgal

The CGAL Open Source Project is pleased to announce the release 4.12 Beta 1
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.12 Beta 1 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.12 in September.

Important Notice

• The CMake scripts used by CGAL have been changed to use modern patterns
  introduced by CMake 2.8.12 and CMake 3.0: instead of setting CMake
  variables, the script now defines imported targets and uses link
  interfaces.

  That is mostly backward-compatible with existing usages of CGAL CMake
  scripts. The only non-compatible effect is that the CMAKE_BUILD_TYPE
  and compilation flags are no longer copied from the CGAL_DIR to the
  project using it. Note also that the CMAKE_BUILD_TYPE is no longer
  set to Release by default. For a developer using the Visual Studio
  IDE or the Xcode IDE, the change should be transparent. Developers using
  makefiles or the Ninja build-system should set the CMAKE_BUILD_TYPE
  to Release manually, to avoid using CGAL libraries without any
  compile-time optimization.

2D Movable Separability of Sets (new package)

• A new package called "2D Movable Separability of Sets" has been
  introduced. It handles a class of problems that deal with moving
  sets of objects in the plane; the challenge is to avoid collisions
  between the objects while considering different kinds of motions and
  various definitions of separation.

  At this point this package consists of the implementations of
  various predicates and constructions related to castings of
  polygonal objects. In particular, it can be used to determine
  whether a feasible mold for a polygonal object does exist. If a mold
  exists, the package can also be used to compute all possible
  orientations of the feasible molds and the corresponding motions
  needed to remove the casted object from the mold.

Classification (new package)

• This package offers an algorithm that classifies a data set into a
  user-defined set of labels (such as ground, vegetation, buildings,
  etc.). A flexible API is provided so that users can classify any
  type of data, compute their own local features on the input data
  set, and define their own labels.

Kinetic Data Structures (removed package)

• This package has been removed from CGAL-4.12. Users of the package
  will have to keep using the source code available in CGAL-4.11 or
  earlier.

See the full changelog for a complete list of changes.

CGAL-4.11.1 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.11.

CGAL-4.10.2 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.10.1.

The CGAL Open Source Project is pleased to announce the release 4.11
of CGAL, the Computational Geometry Algorithms Library.

This release is pretty special by its number of breaking changes in the
API. In order to have a better feature set, or a better API, several
packages have been reworked in a way that breaks the back-compatibility
with the previous versions of the API.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.10:

3D Periodic Regular Triangulations (new feature)

• Added the class Periodic_3_regular_triangulation_3, which provides
  functionality for 3D periodic weighted Delaunay triangulations. The
  construction is fully dynamic: it provides both point insertion and
  vertex removal.

dD Regular Triangulations (new feature)

• Added the class Regular_triangulation, which provides functionality for
  dD weighted Delaunay triangulations. Note that the removal of points is
  not yet supported.

2D and 3D Linear Geometry Kernel (breaking change)

• Breaking change: The dangerous implicit conversions between weighted
  points and points in the concept Kernel have been
  disabled. Constructors offering to build a weighted point from a point
  (and reversely) are still requested by the concept Kernel but must now
  be marked with the explicit specifier.

• Breaking change: The removal of implicit conversions between points and
  weighted points in the concept Kernel has incidentally created various
  minor breaking changes in the following packages: 2D Alpha Shapes, 2D
  and 3D Triangulations, and 3D Mesh Generation. See the full changelog
  for details.

Triangulated Surface Mesh Parameterization (breaking change)

• Breaking change: The package has been rewritten and can operate on any
  model of the MutableFaceGraph concept. All previous parameterization
  methods are still offered, although with a different, simpler API. The
  documentation has been updated and offers a gentle introduction to the
  new API. Users who wish to use the former API must use a version prior
  to 4.11.

• Breaking change: The adapter to add virtual seams is now the class
  CGAL::Seam_mesh in the package CGAL and the BGL.

• Breaking change: The package has been restructured and most headers
  have been moved. In a general manner, users should replace <CGAL/XXX.h>
  with <CGAL/Surface_mesh_parameterization/XXX.h>

• Add the As Rigid As Possible Parameterization method. This
  parameterization allows the user to prioritize angle preservation,
  shape preservation, or a balance of both.

• Add the Orbifold Tutte Embedding method. This parameterization method
  allows to parameterize meshes that are topological spheres.

3D Surface Subdivision Methods (breaking changes)

• The subdivision algorithms now work on any model of a
  MutableFaceGraph. A new API to the subdivision methods is offered,
  which uses optional named parameters to pass the number of iterations
  and a vertex property map.

• Breaking change: Removed the headers <CGAL/Subdivision_method_3.h> and
  <CGAL/Subdivision_mask_3.h>. The headers <CGAL/Subdivision_method_3/ subdivision_methods_3.h> and <CGAL/Subdivision_method_3/ subdivision_masks_3.h> should respectively be used instead.

• Sqrt3 subdivision can now handle input surfaces with a border.

Scale-Space Surface Reconstruction (breaking change)

• Breaking change: the API was rewritten to separate the smoothing and
  meshing algorithm and making it possible for the user to use different
  ones. The default algorithms used are the same as before this API
  change, but methods are moved to the classes Weighted_PCA_smoother and
  Alpha_shape_mesher.

• Alternative smoothing and meshing methods are provided: Jet_smoother
  and Advancing_front_mesher.

See the full changelog for a complete list of changes.

CGAL-4.10.1 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.10.

The CGAL Open Source Project is pleased to announce the release 4.11 Beta 1
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.11 Beta 1 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.11 in September.

This release is pretty special by its number of breaking changes in the
API. In order to have a better feature set, or a better API, several
packages have been reworked in a way that breaks the back-compatibility
with the previous versions of the API.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.10:

3D Periodic Regular Triangulations (new feature)

• Added the class Periodic_3_regular_triangulation_3, which provides
  functionality for 3D periodic weighted Delaunay triangulations. The
  construction is fully dynamic: it provides both point insertion and
  vertex removal.

dD Regular Triangulations (new feature)

• Added the class Regular_triangulation, which provides functionality for
  dD weighted Delaunay triangulations. Note that the removal of points is
  not yet supported.

2D and 3D Linear Geometry Kernel (breaking change)

• Breaking change: The dangerous implicit conversions between weighted
  points and points in the concept Kernel have been
  disabled. Constructors offering to build a weighted point from a point
  (and reversely) are still requested by the concept Kernel but must now
  be marked with the explicit specifier.

• Breaking change: The removal of implicit conversions between points and
  weighted points in the concept Kernel has incidentally created various
  minor breaking changes in the following packages: 2D Alpha Shapes, 2D
  and 3D Triangulations, and 3D Mesh Generation. See the full changelog
  for details.

Triangulated Surface Mesh Parameterization (breaking change)

• Breaking change: The package has been rewritten and can operate on any
  model of the MutableFaceGraph concept. All previous parameterization
  methods are still offered, although with a different, simpler API. The
  documentation has been updated and offers a gentle introduction to the
  new API. Users who wish to use the former API must use a version prior
  to 4.11.

• Breaking change: The adapter to add virtual seams is now the class
  CGAL::Seam_mesh in the package CGAL and the BGL.

• Breaking change: The package has been restructured and most headers
  have been moved. In a general manner, users should replace <CGAL/XXX.h>
  with <CGAL/Surface_mesh_parameterization/XXX.h>.

• Add the As Rigid As Possible Parameterization method. This
  parameterization allows the user to prioritize angle preservation,
  shape preservation, or a balance of both.

• Add the Orbifold Tutte Embedding method. This parameterization method
  allows to parameterize meshes that are topological spheres.

3D Surface Subdivision Methods (breaking changes)

• The subdivision algorithms now work on any model of a
  MutableFaceGraph. A new API to the subdivision methods is offered,
  which uses optional named parameters to pass the number of iterations
  and a vertex property map.

• Breaking change: Removed the headers <CGAL/Subdivision_method_3.h> and
  <CGAL/Subdivision_mask_3.h>. The headers <CGAL/Subdivision_method_3/ subdivision_methods_3.h> and <CGAL/Subdivision_method_3/ subdivision_masks_3.h> should respectively be used instead.

• Sqrt3 subdivision can now handle input surfaces with a border.

Scale-Space Surface Reconstruction (breaking change)

• Breaking change: the API was rewritten to separate the smoothing and
  meshing algorithm and making it possible for the user to use different
  ones. The default algorithms used are the same as before this API
  change, but methods are moved to the classes Weighted_PCA_smoother and
  Alpha_shape_mesher.

• Alternative smoothing and meshing methods are provided: Jet_smoother
  and Advancing_front_mesher.

See the full changelog for a complete list of changes.

The CGAL Open Source Project is pleased to announce the release 4.10
of CGAL, the Computational Geometry Algorithms Library.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.9:

Installation

• The minimum required version of CMake is now 3.1. All CMake versions up to
  3.7 are supported.

Generalized Maps (new package)

• This package implements Generalized Maps in d dimensions. A generalized map
  is a data structure enabling to represent an orientable or non orientable
  subdivided object by describing all the cells of the subdivision (for
  example in 3D vertices, edges, faces, volumes) and all the incidence and
  adjacency relationships between these cells. This data structure is the
  generalization of the combinatorial maps in order to be able to represent
  non orientable objects.

3D Point Set (new package)

• This package provides a flexible data structure CGAL::Point_set_3 that
  allows the user to easily handle point sets with an arbitrary number of
  attributes (such as normal vectors, colors, labeling, etc.).

Note also that the advanced API of a few CGAL packages have change in an
incompatible way:

• Triangulated Surface Mesh Shortest Paths
• CGAL and the Boost Graph Library (BGL)
• 2D and 3D Linear Geometry Kernel
• 2D Triangulations
• 3D Triangulations

See http://www.cgal.org/2017/05/29/cgal410/ for a complete list of
changes. Breaking changes are highlighted with a bold "Breaking change".

The CGAL Open Source Project is pleased to announce the release 4.10 Beta 1
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.10 Beta 1 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.10 in May.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.9:

Installation

• The minimum required version of CMake is now 3.1. All CMake versions up to
  3.7 are supported.

Generalized Maps (new package)

• This package implements Generalized Maps in d dimensions. A generalized map
  is a data structure enabling to represent an orientable or non orientable
  subdivided object by describing all the cells of the subdivision (for
  example in 3D vertices, edges, faces, volumes) and all the incidence and
  adjacency relationships between these cells. This data structure is the
  generalization of the combinatorial maps in order to be able to represent
  non orientable objects.

3D Point Set (new package)

• This package provides a flexible data structure CGAL::Point_set_3 that
  allows the user to easily handle point sets with an arbitrary number of
  attributes (such as normal vectors, colors, labeling, etc.).

Note also that the advanced API of a few CGAL packages have change in an
incompatible way:

• Triangulated Surface Mesh Shortest Paths
• CGAL and the Boost Graph Library (BGL)
• 2D and 3D Linear Geometry Kernel
• 2D Triangulations
• 3D Triangulations

See http://www.cgal.org/2017/04/20/cgal410-beta1/ for a complete list of
changes. Breaking changes are highlighted with a bold "Breaking change".

CGAL-4.9.1 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.9.

CGAL-4.8.2 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.8.1.

The CGAL Open Source Project is pleased to announce the release 4.9
of CGAL, the Computational Geometry Algorithms Library.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.8:

General

• CGAL can now be used in headers only mode, i.e. without compiling the
  CGAL libraries and linking with these libraries when compiling
  examples, tests and demos. Note that running CMake on CGAL is still
  required in order to generate some configuration files.

Cone Based Spanners (new package)

• This package provides algorithms for constructing two kinds of
  cone-based spanners: Yao graph and Theta graph, given a set of
  vertices on the plane and the directions of cone boundaries.

See http://www.cgal.org/releases.html for a complete list of changes.

The CGAL Open Source Project is pleased to announce the release 4.9 Beta 1
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.9 Beta 1 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.9 in September.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.8:

General

• CGAL can now be used in headers only mode, i.e. without compiling the
  CGAL libraries and linking with these libraries when compiling
  examples, tests and demos. Note that running CMake on CGAL is still
  required in order to generate some configuration files.

Cone Based Spanners (new package)

• This package provides algorithms for constructing two kinds of
  cone-based spanners: Yao graph and Theta graph, given a set of
  vertices on the plane and the directions of cone boundaries.

See http://www.cgal.org/releases.html for a complete list of changes.

CGAL-4.8.1 is a bug-fix release.

See on Github the list of bugs that were solved since CGAL-4.8.

The CGAL Open Source Project is pleased to announce the release 4.8
of CGAL, the Computational Geometry Algorithms Library.

Besides fixes to existing packages, the following has changed since
CGAL 4.7:

General

• The support for Qt3 is dropped and all demos using it got removed.

Installation

• Starting with Visual C++ 2015 we no longer require Boost.Thread as we
  use the C++11 keyword thread_local and the C+11 class std::mutex.
• The same holds for g++ 4.8 or later when the C++11 standard is used.

Optimal Transportation Curve Reconstruction (new package)

• This package implements a method to reconstruct and simplify 2D point
  sets. The input is a set of 2D points with mass attributes, possibly
  hampered by noise and outliers. The output is a set of line segments
  and isolated points which approximate the input points.

3D Mesh Generation

• Add support of 3D gray level images as input for the tetrahedral mesh
  generation.

Polygon Mesh Processing

• Add a new triangle-based isotropic remeshing algorithm for
  triangulated surface meshes.

Point Set Processing

• Add Concurrency_tag to the functions compute_average_spacing(),
  edge_aware_upsample_point_set(), jet_estimate_normals(),
  jet_smooth_point_set(), and pca_estimate_normals().

See http://www.cgal.org/releases.html for a complete list of changes.

The CGAL Open Source Project is pleased to announce the release 4.8 Beta 2
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.8 Beta 2 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.8 later in March.

That is the second "beta" release for CGAL-4.8. The reason is that there
was important bugs in our CMake scripts for some use cases. See the details
on GitHub:

https://github.com/CGAL/cgal/issues?q=milestone%3A4.8-beta2+label%3A%22CMake+scripts%22

You can find the detailed description of all changes since CGAL-4.8-beta1
here on GitHub:

https://github.com/CGAL/cgal/issues?q=milestone%3A4.8-beta2

As a reminder, you can find below the major changes since CGAL 4.7:

General

• The support for Qt3 is dropped and all demos using it got removed.

Installation

• Starting with Visual C++ 2015 we no longer require Boost.Thread as we
  use the C++11 keyword thread_local and the C+11 class std::mutex.
• The same holds for g++ 4.8 or later when the C++11 standard is used.

2D Reconstruction and Simplification from Point Set (new package)

• This package implements a method to reconstruct and simplify 2D point
  sets. The input is a set of 2D points with mass attributes, possibly
  hampered by noise and outliers. The output is a set of line segments
  and isolated points which approximate the input points.

3D Mesh Generation

• Add support of 3D gray level images as input for the tetrahedral mesh
  generation.

Polygon Mesh Processing

• Add a new triangle-based isotropic remeshing algorithm for
  triangulated surface meshes.

Point Set Processing

• Add Concurrency_tag to the functions compute_average_spacing(),
  edge_aware_upsample_point_set(), jet_estimate_normals(),
  jet_smooth_point_set(), and pca_estimate_normals().

See http://www.cgal.org/releases.html for a complete list of changes.

The CGAL Open Source Project is pleased to announce the release 4.8 Beta 1
of CGAL, the Computational Geometry Algorithms Library.

CGAL version 4.8 Beta 1 is a public testing release. It should provide
a solid ground to report bugs that need to be tackled before the
release of the final version of CGAL 4.8 in March.

Besides fixes and general enhancement to existing packages, the following
has changed since CGAL 4.7:

General

• The support for Qt3 is dropped and all demos using it got removed.

Installation

• Starting with Visual C++ 2015 we no longer require Boost.Thread as we
  use the C++11 keyword thread_local and the C+11 class std::mutex.
• The same holds for g++ 4.8 or later when the C++11 standard is used.

2D Reconstruction and Simplification from Point Set (new package)

• This package implements a method to reconstruct and simplify 2D point
  sets. The input is a set of 2D points with mass attributes, possibly
  hampered by noise and outliers. The output is a set of line segments
  and isolated points which approximate the input points.

3D Mesh Generation

• Add support of 3D gray level images as input for the tetrahedral mesh
  generation.

Polygon Mesh Processing

• Add a new triangle-based isotropic remeshing algorithm for
  triangulated surface meshes.

Point Set Processing

• Add Concurrency_tag to the functions compute_average_spacing(),
  edge_aware_upsample_point_set(), jet_estimate_normals(),
  jet_smooth_point_set(), and pca_estimate_normals().

See http://www.cgal.org/releases.html for a complete list of changes.

The CGAL Open Source Project is pleased to announce the release 4.7
of CGAL, the Computational Geometry Algorithms Library.

Besides fixes to existing packages, the following has changed since
CGAL 4.6:

Installation

• The minimum required version of CMake is now 2.8.11. CMake versions
  3.1, 3.2, and 3.3 are supported.
• All Qt4 demos have been updated and now require Qt5 to be
  compiled. Qt5 version 5.3 or higher is required. The support for Qt4
  is dropped. The code of the 3D demos now use modern OpenGL, with
  shaders, instead of the fixed pipeline API of OpenGL-1.
• The Microsoft Windows Visual C++ compiler 2015 (VC14) is now
  supported. However, since this compiler is not officially supported
  by Intel TBB 4.4 and Qt 5.5 (the latest versions available at the
  time of this release), the parallelism features of CGAL and Qt5 demos
  will not work.

Advancing Front Surface Reconstruction (new package)

This package provides a greedy algorithm for surface reconstruction
from an unorganized point set. Starting from a seed facet, a piecewise
linear surface is grown by adding Delaunay triangles one by one. The
most plausible triangles are added first, in a way that avoids the
appearance of topological singularities.

Triangulated Surface Mesh Shortest Paths (new package)

The package provides methods for computing shortest path on
triangulated surface meshes. Given a set of source points on the
surface, this package provides a data structure that can efficiently
provides the shortest path from any point on the surface to the sources
points. There is no restriction on the genus or the number of
connnected components of the mesh.

Triangulated Surface Mesh Skeletonization (new package)

This package provides a (1D) curve skeleton extraction algorithm for a
triangulated polygonal mesh without borders based on the mean curvature
flow. The particularity of this skeleton is that it captures the
topology of the input. For each skeleton vertex one can obtain its
location and its corresponding vertices from the input mesh. The code
is generic and works with any model of the FaceListGraph concept.

Polygon Mesh Processing (new package)

This package implements a collection of methods and classes for polygon
mesh processing, ranging from basic operations on simplices, to complex
geometry processing algorithms. The implementation of this package
mainly follows algorithms and references given in Botsch et al.'s book
on polygon mesh processing.

3D Point-Set Shape Detection (new package)

This package implements the efficient RANSAC method for shape
detection, contributed by Schnabel et al. From an unstructured point
set with unoriented normals, the algorithm detects a set of
shapes. Five types of primitive shapes are provided by this package:
plane, sphere, cylinder, cone and torus. Detecting other types of
shapes is possible by implementing a class derived from a base shape.

L Infinity Segment Delaunay Graphs (new package)

The package provides the geometric traits for constructing the segment
Delaunay graph in the max-norm (L Infinity). The traits also contain
methods to draw the edges of the dual of the segment Delaunay graph in
the max-norm i.e., the segment Voronoi diagram in the max-norm. The
algorithm and traits rely on the segment Delaunay graph algorithm and
traits under the Euclidean distance. The segment Voronoi diagram in the
max-norm has applications in VLSI CAD.

2D Visibility (new package)

This package provides several variants to compute the visibility area
of a point within polygonal regions in two dimensions.

See http://www.cgal.org/releases.html for a complete list of changes.

CGAL-4.6.3 is a bug-fix release.

It fixes warnings in Arrangement_on_surface_2 and Polyline_simplification_2.

See on Github:

• the list of bugs that were solved since CGAL-4.6.2,
• the list of bugs that were solved between CGAL-4.6.1 and CGAL-4.6.2,
• the list of bugs that were solved between CGAL-4.6 and CGAL-4.6.1.