Installation/CHANGES.md
Release date: July 2026
#include <CGAL/Polygon_mesh_processing/XXX.h> do not need to be changed and will include
the appropriate header from the new packages.do_intersect() can be reproduced with:!Has_on_unbounded_side_2::operator(Circle_2, Segment_2) or!Has_on_unbounded_side_2::operator(Circle_2, Iso_rectangle_2) or!Has_on_unbounded_side_3::operator(Sphere_3, Iso_cuboid_3)Arr_linear_traits_2 a model of the new concept.draw(Arrangement_on_surface_2& arr, Bbox& bbox, ...) that enable the drawing of arrangements induced by unbounded curves.DelaunayMeshTraits_2 now requires the functor Construct_bbox_2.CGAL::IO::read_VTK<LCC>() and CGAL::IO::write_VTK<LCC>() adding the ability to read and write .vtk files (legacy ASCII) for 3D Linear_cell_complex (dimension 3, ambient dimension 3). These functions support per-vertex and per-volume scalar fields and handle various VTK cell types.import_from_plane_graph() → read_plane_graph_in_lcc()import_from_polyhedron_3() → polyhedron_3_to_lcc()import_from_triangulation_3() → triangulation_3_to_lcc()intersected_nodes() with an intersection functor and a convenience overload for a ball query.CGAL::Shape_detection::Polygon_mesh::Plane_face_region that extends the support plane of the seed face without refitting the plane to the regionCGAL::Shape_detection::Polygon_mesh::Line_segment_region that extends the support line of the seed segment without refitting the line to the regionCGAL::Shape_detection::Polygon_mesh::Face_area_sorting that provides a sorting of faces in descending order of areaCGAL::Shape_detection::Polygon_mesh::Segment_length_sorting that provides a sorting of segments in descending order of lengthface_normal_map to CGAL::Shape_detection::Polygon_mesh::Linear_least_squares_fit_region ,CGAL::Shape_detection::Polygon_mesh::Plane_face_region and CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces to allow the use of face normal property maps instead of calculating the face normals.CGAL::Shape_detection::Polygon_mesh::Plane_face_region and CGAL::Shape_detection::Polygon_mesh::Face_area_sorting are now used as the default in CGAL::Polygon_mesh_processing::region_growing_of_planes_on_facesCGAL::Surface_mesh_simplification::GarlandHeckbert_plane_and_line_policies, which provides improved output for CGAL::Surface_mesh_simplification::edge_collapse().
That class works the same as previous GarlandHeckbert_policies.
Its constructor accepts a Mesh and optional named parameters to set the weight of the line policy relative to the plane policy, set the boundary cost multiplier or provide vertex normals.CGAL::Surface_mesh_simplification::GarlandHeckbert_policies.h is now an alias of CGAL::Surface_mesh_simplification::GarlandHeckbert_plane_and_line_policies.h and is no longer deprecated.do_intersect(): (i) made it robust even with an inexact-predicate kernel, and (ii) made it quit
once an intersection is detected. (In the past, the intersection was computed in one phase and examined in a
subsequent phase.) This optimization somehow breaks backward compatibility as follows.
The variants of the free function do_intersect() that accept a third optional parameter, namely UsePolylines,
which determines whether the boundaries of the input polygons are treated as cyclic sequences of
(x-monotone) segments or as a cyclic sequences of (x-monotone) polylines, do not accept this third
parameter any longer. (This third optional parameter was introduced a few years ago, and now abandoned only for
do_intersect().)CGAL/Polygon_mesh_processing/border.h has been deprecated and its content
(CGAL::border_halfedges() and CGAL::extract_boundary_cycles()) have been moved to
the new header CGAL/boost/graph/border.h.CGAL::Polygon_mesh_processing::kernel(), to compute the kernel of a polygon mesh.CGAL::Polygon_mesh_processing::is_empty_kernel(), to indicate if the kernel of a polygon mesh is empty.CGAL::Polygon_mesh_processing::kernel_point(), to compute a single point inside the kernel of a polygon mesh.use_convex_specialization parameter to CGAL::Polygon_mesh_processing::clip() and CGAL::Polygon_mesh_processing::refine_with_plane().CGAL::Polygon_mesh_processing::kernel(), to compute the kernel of a polygon mesh.CGAL::Polygon_mesh_processing::is_empty_kernel(), to indicate if the kernel of a polygon mesh is empty.CGAL::Polygon_mesh_processing::kernel_point(), to compute a single point inside the kernel of a polygon mesh.use_convex_specialization parameter to CGAL::Polygon_mesh_processing::clip() and CGAL::Polygon_mesh_processing::refine_with_plane().CGAL::Polygon_mesh_processing::surface_intersection(), which can be used to
compute the polylines that represent the intersection between two polyhedral surfaces has been
renamed to CGAL::Polygon_mesh_processing::intersection_polylines().CGAL::Implicit_vector_to_labeling_function_wrapper as well as
the constructor of CGAL::Polyhedral_mesh_domain_with_features_3 that has a filename as parameter,
which were deprecated since CGAL-4.5.Iso_cuboid_3 to the concept BisectionGeometricTraits_3.insert_unique_constraints() to the class CGAL::Constrained_Delaunay_triangulation_2 identical to the function insert_constraints() except that it removes duplicated constraints before inserting them in the triangulation.CGAL::bisect_failures
template function that uses bisection to isolate minimal failing subsets from complex input dataCGAL::IO::Basic_indenting_streambuf
and CGAL::IO::Basic_indenting_stream_guard
for automatic indentation of output streamsCGAL::IO::Basic_color_streambuf
and CGAL::IO::Basic_color_stream_guard
for ANSI color support in terminal outputCGAL::box_intersection_d() now accepts ranges with different box types.CGAL::Box_with_info<FT, dim, Info>, which stores a variable of type Info accessible via info().Convex_hull::do_intersect() to the package Convex_hull_3, which enable testing the intersection of two convex hulls.extreme_point_3() to the package Convex_hull_3, which return the farthest point of a convex hull in a given direction.Convex_hull_hierarchy to the package Convex_hull_3, which represents a convex hull and is optimized for use with the above functions.point_and_support() to several generators to get the last point generated point and the support element containing it. Affected generators are Random_points_in_triangles_2, Random_points_in_triangles_3, Random_points_in_triangle_mesh_3, Random_points_in_tetrahedral_mesh_boundary_3, Random_points_in_tetrahedral_mesh_3, Random_points_in_triangle_soup_3, and Random_points_on_graph_edges_3.Release date: Sept 2025
CGAL::make_conforming_constrained_Delaunay_triangulation_3().This package enables building and handling triangulations of closed orientable hyperbolic surfaces. It offers functions for the generation of the triangulation from a convex fundamental domain, the Delaunay flip algorithm, and the construction of a portion of the lift of the triangulation in the Poincaré disk. A method is offered that generates such domains in genus two.
See also the associated news entry.
Added the non-zero rule (areas with non-zero winding number are kept), as well as two functions to compute the conservative inner and outer hull of similar polygons:
See also the associated news entry.
apply_iterative_snap_rounding to the function
CGAL::Polygon_mesh_processing::autorefine_triangle_soup().
When set to true, the coordinates are rounded to fit in double and may perform additional
subdivisions to ensure the output is free of self-intersections.
See also the associated news entry.CGAL::Polygon_mesh_processing::approximated_centroidal_Voronoi_diagram_remeshing()
to remesh triangle meshes. This remeshing algorithm uses clustering on polygonal meshes as to
approximate a Centroidal Voronoi Diagram construction, and can move vertices as to recover
sharp features and corners.
See also the associated news entry.CGAL::Polygon_mesh_processing::clip()
and CGAL::Polygon_mesh_processing::split()
with a plane as clipper that is much faster and is now able to handle non-triangulated surface meshes.
See also the associated news entry.CGAL::Polygon_mesh_processing::refine_with_plane(),
which enables users to refine a mesh with its intersection with a plane.CGAL::Polygon_mesh_processing::discrete_mean_curvature()
and CGAL::Polygon_mesh_processing::discrete_Gaussian_curvature()
to evaluate the discrete curvature at a vertex of a mesh.CGAL::Polygon_mesh_processing::angle_sum()
to compute the sum of the angles around a vertex.CGAL::poisson_eliminate(),
which can be used to downsample a point cloud to a target size while providing Poisson disk property,
i.e., a larger minimal distance between points.dijkstra_shortest_path(),
which can be used to compute the geometrically shortest sequence of halfedges between two vertices.CGAL::Euler::remove_degree_2_vertex(),
which enables users to remove vertices which have exactly two incident edges.AosApproximateTraits_2 to AosApproximatePointTraits_2
to make room for the new concept AosApproximateTraits_2.
This concept requires the provision of a functor called Approximate_2 that has an operator
that approximates the coordinates of a point.AosApproximateTraits_2
now refines the concept AosApproximatePointTraits_2
and requires the provision of a functor called Approximate_2. In addition to an operator
that approximates the coordinates of a point, it also requires the provision of (i) an operator
that approximates a points, and (ii) an operator that approximates a curve.CGAL::Arr_tracing_traits_2
and CGAL::Arr_counting_traits_2,
which can be used to extract debugging and informative metadata about the traits in use
while a program is being executed.do_intersect() of a 2D Arrangement with a curve.point(Vertex_handle) and point(Simplex, int),
which enables users to access the geometric position of a vertex and of the i-th vertex
of a simplex of a triangulation.Poisson_mesh_domain_3 that integrates some optimizations from the deprecated 3D Surface Mesh Generation package.Constrained_triangulation_plus_2,
the value type of the range returned by subconstraints()
has changed from const std::pair<const Subconstraint, std::list<Context>*> to Subconstraint.
The old range type is now returned by a new function named subconstraints_and_contexts().initial_points_generator:
enables the user to specify a functor that generates initial points,initial_points:
enables the user to specify a Range of initial points.surface_only,
which can be used to improve performance when only surface mesh generation is sought.Poisson_mesh_domain_3,
which should be used when generating a mesh from a Poisson surface
obtained with the package Poisson Surface Reconstruction.
This mesh domain re-integrates some optimizations for Poisson surface mesh generation that were lost
when the package 3D Mesh Generation had to be replaced instead of the deprecated package 3D Surface Mesh Generation.CGAL::Subdivision_method_3::Loop_subdivision()
and CGAL::Subdivision_method_3::CatmullClark_subdivision(),
which enables users to subdivide a mesh without modifying its geometry.Release date: October 2024
CGAL::make_mesh_3()
can be used.Release date: September 2024
Core library is no longer based on GMP, but on
Boost.Multiprecision.
Either GMP backend or Boost backend can be used.UseCGAL.cmake has been removed from CGAL.
Usages of the CMake variables ${CGAL_USE_FILE} and ${CGAL_LIBRARIES} must be replaced
by a link to the imported target CGAL::CGAL, for example:
target_link_library(your_target PRIVATE CGAL::CGAL).CGAL::draw() function.
There is one such draw() function for each CGAL package that has a basic viewer. Such a call opens
an interactive window showing the given model and allowing to navigate in the scene,
show or hide some specific cells, show the interior of the model if any, etc.
The Basic_viewer is based on Qt6.boost::variant with std::variant
in the intersection functions.boost::optional with std::optional
in the intersection functions.AABBGeomTraits and AABBRayIntersectionGeomTraits
have been replaced by AABBGeomTraits_3
and by AABBRayIntersectionGeomTraits_3,
respectively.AABBGeomTraits_2
and AABBRayIntersectionGeomTraits_2
have been introduced, as the 2D counterparts.CGAL::AABB_traits
is deprecated and replaced by CGAL::AABB_traits_3.CGAL::AABB_traits_2 is introduced as the 2D counterpart.CGAL::AABB_segment_primitive
has been deprecated and replaced by the class CGAL::AABB_segment_primitive_3.CGAL::AABB_triangle_primitive
has been deprecated and replaced by the class CGAL::AABB_triangle_primitive_3.CGAL::AABB_segment_primitive_2,
CGAL::AABB_polyline_segment_primitive_2,
CGAL::AABB_triangle_primitive_2,
CGAL::AABB_indexed_triangle_primitive_2.AABBTraits
now refines the concept SearchTraits.boost::optional with std::optional.boost::variant with std::variant.std::variant. Support for the old macro CGAL_ARR_POINT_LOCATION_VERSION
has been removed.CGAL::Arr_observer
has been replaced by an alias template. (The class CGAL::Arr_observer
was renamed to CGAL::Aos_observer).Arr_dcel,
which essentially replaces the former CGAL::Arr_default_dcel.
Backward compatibility was maintained by the introduction of the alias template
CGAL::Arr_default_dcel.
CGAL::Arr_dcel, as opposed to the former CGAL::Arr_default_dcel is templated
(in addition to the geometry traits) by Vertex, Halfedge, and Face template parameters,
and they have default type values. All this enables the layered extension of DCEL records.earth. The program (i) reads a database of all administrative boundaries of the countries
in the world, (ii) displays the globe with all countries and land covered by water (which is land
not covered by countries) on a window, and (ii) enables interaction with the user.Construct_projected_boundary_2
in EnvelopeTraits_3
now uses std::variant instead of CGAL::Object.CGAL::Env_plane_traits_3
as a template parameter with a default value (being the 2D arrangement linear traits).
Similarly, passed the base class of CGAL::Env_triangle_traits_3 as a template parameter
with a default value (being the 2D arrangement segment traits).insert_cell_1_between_two_cells_2()
to the GenericMap
concept, which enables users to insert an edge between two different faces in order to create faces with holes.CGAL::remove_all_elements(),
which removes vertices, halfedges, and faces without collecting garbage and without removing properties.CGAL::Face_filtered_graph
now supports patch IDs of any type and not just faces_size_type. The only requirement is that
the type is hashable.CGAL::Polygon_mesh_processing::autorefine_triangle_soup(),
which can be used to refine a soup of triangles such that no pair of triangles intersects
in their interiors. Also added, the function CGAL::Polygon_mesh_processing::autorefine()
operating directly on a triangle mesh and updating it using the aforementioned function on a triangle soup.CGAL::Corefinement::Non_manifold_output_visitor,
which can be used in corefinement based functions to deal with non-manifold outputs.CGAL::Polygon_mesh_processing::isotropic_remeshing(),
and a sizing function based on a measure of local curvature for adaptive remeshing.CGAL::Polygon_mesh_processing::interpolated_corrected_curvatures()
which can be used to compute the mean and Gaussian curvatures, as well as the principal curvature
and directions.CGAL::Polygon_mesh_processing::refine_mesh_at_isolevel()
which can be used to refine a polygon mesh along an isocurve.CGAL::Polygon_mesh_processing::add_bbox(),
which enables adding a tight or extended, triangulated or not, bounding box to a face graph.TriangulationTraits_2 now requires an additional functor Compare_xy_2.vertices()
to the class CGAL::Triangulation_3.
Each of them returns an array containing the vertices of the given triangulation simplex.CGAL::TDS_full_cell_mirror_storage_policy is now unsupported in dimension larger than 127.CGAL::tetrahedral_isotropic_remeshing(),
which can be used to perform non-uniform and adaptive remeshing.CGAL::Tetrahedral_remeshing::Remeshing_cell_base_3
have been modified, reverting changes introduced in CGAL 5.6.CGAL::Tetrahedral_remeshing::Remeshing_vertex_base_3
must now be a model of the concept
SimplicialMeshVertexBase_3
(and not only TriangulationVertexBase_3).CGAL::Simplicial_mesh_cell_base_3
have been modified to enable passing a geometric traits and a custom cell base class.TriangleAccessor, the template parameter TriangleAccessor,
as well as the class Triangle_accessor. These were no longer used for several releases.CGAL::Gray_image_mesh_domain_3, CGAL::Implicit_mesh_domain_3,
and CGAL::Labeled_image_mesh_domain_3, which were deprecated since CGAL-4.13.edge_distance, an upper bound for the distance from the edge to the 1D feature.MeshEdgeCriteria_3 was modified to include the new meshing criterion edge_distance.CGAL::Surface_mesh_parameterization::LSCM_parameterizer_3
now requires the Eigen library.CGAL::Surface_mesh::property_map()
has been changed to std::optional.CGAL::Point_set_3::property_map()
has been changed to std::optional.boost::shared_ptr with std::shared_ptr.boost::shared_ptr with std::shared_ptr.boost::optional with std::optional.Release date: July 2023
CGAL_triangulation_assertion) have been removed. Corresponding CGAL-wide versions (such as
CGAL_assertion) should be used instead.FaceGraph models. In particular, the notion of Item
has been introduced to reference an element in the input range of elements. Region maps now
operates on Item and no longer on the value type of the input range.update() in the concept RegionType now returns a Boolean
instead of void, that is used inside the class Region_growing for detecting if the input
conditions for the new region are satisfied. This change affects only user-defined types of regions.RegionType for getting linear regions in a set of 2D and 3D
segments and on 2D and 3D polylines.Polyline_graph for extracting a set of polylines from a face graph, which splits
this graph into a set of user-defined regions.Added weighted straight skeletons: weighted straight skeletons are a generalization of straight skeletons. Contour edges are assigned a positive weight, which can be understood as assigning a speed to the wavefront spawned from the contour edge.
Added straight skeleton extrusion: this CGAL package now implements the extrusion of weighted straight skeletons of polygons with holes. The output is a closed, combinatorially 2-manifold surface triangle mesh.
See also the news entry.
CompareAngle_3
to the concept
Kernel to compare
an angle defined by three points to the cosinus of another angle.std::size_t, they can be used as index
into vectors which store properties. To use the index version, Use_index must be defined
and be equal to CGAL::Tag_true in the item class.Linear_cell_complex_incremental_builder_3.draw(arr), that renders arrangements based
on the Basic_viewer_qt class template. As of now, only 2D arrangements on the plane induced
by (i) segments, (ii) conics, and (iii) circular arcs or (linear) segments are supported.Arr_conic_traits_2.
This includes the following:
Added functions
CGAL::Polygon_mesh_processing::region_growing_of_planes_on_faces()
and
CGAL::Polygon_mesh_processing::detect_corners_of_regions(),
which enable partitioning a mesh into planar regions using the region growing algorithm
from the Shape Detection package.
Added the functions
CGAL::Polygon_mesh_processing::remesh_planar_patches()
and
CGAL::Polygon_mesh_processing::remesh_almost_planar_patches(),
which can be used to remesh patches of coplanar faces in a mesh.
Added the function
CGAL::Polygon_mesh_processing::surface_Delaunay_remeshing(),
which can be used to remesh a surface triangle mesh using the Delaunay refinement algorithm
from the 3D Mesh Generation package.
Added the function
CGAL::Polygon_mesh_processing::remove_almost_degenerate_faces(),
which can be used to remove badly shaped triangles faces in a mesh.
Added the functions
CGAL::Polygon_mesh_processing::does_triangle_soup_self_intersect()
and
CGAL::Polygon_mesh_processing::triangle_soup_self_intersections()
to identify and report self-intersections in a triangle soup, similarly to existing functions on triangle meshes.
Added the function
CGAL::Polygon_mesh_processing::triangulate_polygons(),
which allows users to triangulate polygon soups.
Added a named parameter to
CGAL::Polygon_mesh_processing::smooth_shape()
to disable the scaling, which otherwise aims to compensate volume loss during smoothing.
Deprecated the overloads of functions
CGAL::Polygon_mesh_processing::triangulate_hole(),
CGAL::Polygon_mesh_processing::triangulate_and_refine_hole(),
and
CGAL::Polygon_mesh_processing::triangulate_refine_and_fair_hole()
which have output iterators for vertices and faces as parameter. They are replaced by overloads
with two additional named parameters.
ConvexHullTraits_2
no longer requires the functor Less_signed_distance_to_line_2, but requires the functor
Compare_signed_distance_to_line_2
instead.Convex_hull_projective_xy_traits_2, Convex_hull_projective_xz_traits_2,
and Convex_hull_projective_yz_traits_2 have been removed. Users should use
Projection_traits_xy_3,
Projection_traits_xz_3,
and
Projection_traits_yz_3
instead.CGAL::mark_domain_in_triangulation()
to mark faces connected with non-constrained edges as inside of the domain based on the nesting level.write_VTU(),
with property maps for specifying the domain.CGAL::lloyd_optimize_mesh_2().refine_Delaunay_mesh(),
and replaced them with versions using function named parameters.HyperbolicTriangulationFaceBase_2
has been modified to
better reflect the triangulation's requirements and avoid a conflict with the requirements
described by the concept TriangulationDataStructure_2::Face. The model
CGAL::Hyperbolic_triangulation_face_base_2
has been adapted correspondingly.MeshComplex_3InTriangulation_3
to describe 3D simplicial meshes, and makes the data structure independent
from the tetrahedral mesh generation package.CGAL::Tetrahedral_remeshing::Remeshing_vertex_base_3
and
CGAL::Tetrahedral_remeshing::Remeshing_cell_base_3
have been modified.CGAL::create_labeled_image_mesh_domain()
for automatic detection and protection of 1D-curves that lie at the intersection of
three or more subdomains extracted from labeled images.CGAL::Sizing_field_with_aabb_tree,
a geometry-aware sizing field for feature edges in polyhedral domains.edge_min_size
to avoid subdividing sharp edges that are shorter than a prescribed size bound.facet_min_size
and
cell_min_size
to prevent Delaunay refinement from creating simplices smaller than a prescribed bound.Count_stop_predicate
and
Count_ratio_stop_predicate
are renamed to
Edge_count_stop_predicate
and
Edge_count_ratio_stop_predicate.
Older versions have been deprecated.Face_count_stop_predicate
and
Face_count_ratio_stop_predicate,
which can be used to stop the simplification algorithm based on a desired number of faces in the output, or a ratio between input and output face numbers.GeneralPolygonWithHoles_2
concept (e.g.,
clear_outer_boundary(),
clear_holes(),
and
clear()
).Release date: June 2022
This component takes a 3D triangle mesh, soup, or point set as input, and generates a valid (watertight, intersection-free, and combinatorially 2-manifold) surface triangle mesh that contains the input. The algorithm proceeds by shrink-wrapping and refining a 3D Delaunay triangulation, starting from a loose bounding box of the input. Two user-defined parameters, alpha and offset, offer control over the maximum size of cavities where the shrink-wrapping process can enter, and the tightness of the final surface mesh to the input, respectively. Once combined, these parameters provide a means to trade fidelity to the input for complexity of the output.
See also the announcement page.
CGAL::create_exterior_skeleton_and_offset_polygons_with_holes_2()
to not take into account the offset of the outer frame.CGAL::convex_hull_3(), which writes the result in an indexed triangle set.GeneralPolygonWithHoles_2 now requires the nested type Polygon_2 instead of General_polygon_2.GeneralPolygonSetTraits_2 now requires the nested type Construct_polygon_with_holes_2 instead of Construct_general_polygon_with_holes_2.intersect_2, compare_y_at_x_right, and compare_y_at_x_left function objects of the traits class template Arr_geodesic_arc_on_sphere_traits_2 that handles geodesic arcs on sphere and applied a small syntactical fix to the tracing traits.remove_isolated_vertices()
as a post-processing step for the tetrahedral mesh generation.CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_soup(), which enables re-orienting the faces of a triangle soup based on the orientation of the nearest face in a reference triangle soup.CGAL::Polygon_mesh_processing::compatible_orientations(), which enables to retrieve the (in)compatibility of orientations of faces from different connected components.CGAL::Polygon_mesh_processing::tangential_relaxation(), which applies an area-based tangential mesh smoothing to the vertices of a surface triangle mesh.visitor to the function triangulate_hole(), which enables to track progress with callbacks.GarlandHeckbert_plane_policies, GarlandHeckbert_probabilistic_plane_policies, GarlandHeckbert_triangle_policies, and GarlandHeckbert_probabilistic_triangle_policies.GarlandHeckbert_policies has been deprecated, GarlandHeckbert_plane_policies replaces it.min_points_per_cell has been added to grid_simplify_point_set(). By adding a minimal number of points in a cell such that a point is retained, one can also filter out low density areas and outliers: in the case of densely sampled point clouds, this yields better results than using grid simplification and then outlier removal, while being very vast. The default value is 1 to keep the previous behavior as default.write_graphviz() to the class Kd_tree that writes the tree in a stream in the Graphviz format.invert_selection() in the class Face_filtered_graph, which toggles the selected status of a graph: selected faces are deselected, and unselected faces are selected.Release date: January 2022
Added the cmake target CGAL::CGAL_Basic_viewer to ease the compilation of programs using
the basic viewer-based function CGAL::draw(). This target will define the macro and link with
CGAL_Qt5 target when linked with it.
The kernel providing exact constructions and exact predicates
(CGAL::Exact_predicates_exact_constructions_kernel)
is now thread-safe.
See changes in 2D and 3D Linear Geometry Kernel for more details.
The class Geomview_stream and all the dependent features have
been removed from CGAL. Those features were actually no longer
supported since CGAL-5.3 but it was not properly announced.
Segment_coordinates_2.h and Triangle_coordinates_2.h are
renamed to segment_coordinates_2.h and triangle_coordinates_2.h.Segment_coordinates_2
and Triangle_coordinates_2
are deprecated. The free functions compute_segment_coordinates_2()
and compute_triangle_coordinates_2()
are deprecated as well. Instead, the free functions segment_coordinates_2()
and triangle_coordinates_2()
should be used.Query_point_location
and Type_of_algorithm
are deprecated. Instead, the enum Computation_policy_2
should be used.Wachspress_2,
Discrete_harmonic_2,
Mean_value_2,
and Generalized_barycentric_coordinates_2
are deprecated. As consequence, the concept BarycentricCoordinates_2
is deprecated as well. Instead, the classes Wachspress_coordinates_2,
Discrete_harmonic_coordinates_2,
and Mean_value_coordinates_2
should be used.Harmonic_coordinates_2
to compute approximate harmonic coordinates in 2D.
These coordinates satisfy all properties of barycentric coordinates inside any simple polygon.DiscretizedDomain_2
and a model of this concept called Delaunay_domain_2,
which is based on the Mesh 2 package.
A model of this concept is required to use Harmonic_coordinates_2.Most operations on CGAL::Exact_predicates_exact_constructions_kernel
objects are now thread-safe if CGAL::Exact_rational
is mpq_class (from GMPXX),
boost::multiprecision::mpq_rational
or CGAL::Quotient<CGAL::MP_Float>.
The objects are not atomic though, so the usual restrictions on avoiding race conditions apply.
For users who do not use threads, this can be disabled with CGAL_HAS_NO_THREADS.
Added documentation for the class Projection_traits_3,
which enables the use of 2D algorithms on the projections of 3D data onto an arbitrary plane.
Added construct_centroid_2_object() and compute_determinant_2_object()
in Projection_traits_xy_3,
Projection_traits_xz_3,
and Projection_traits_yz_3
classes.
Added the functor
NonZeroCoordinateIndex_3
to the concept Kernel with int operator()(Vector_3)
which returns the index of any coordinate of the vector different from zero, or -1.
Epeck_d
objects are now thread-safe, see 2D and 3D Linear Geometry Kernel for details.Breaking Change: The traits function objects Compare_x_at_limit_2 and Compare_x_near_limit_2
are renamed to Compare_x_on_boundary_2 and Compare_x_near_boundary_2, respectively.
A new hierarchy of traits concepts has been introduced. It captures all the valid combinations of boundary conditions for the 4 boundary sides of the parameter space. The 4 boundaries are Bottom, Top, Left, and Right. Each boundary side can be either contracted, identified, close, open, or oblivious. Not all possible combinations are valid. If one side is identified then the other must be as well. Two adjacent sides cannot be contracted.
A new geometric traits, Arr_geodesic_arc_on_sphere_traits_2
has been introduced. It handles arcs of great circles embedded on the unit sphere.
UsePolylines) to all free functions (
complement(),
do_intersect(),
intersection(),
join(),
difference(),
symmetric_difference(),
and oriented_side)
to control whether to use Arr_polyline_traits_2 as default traits. It is the new default as it provides better performances in general.CGAL::Mesh_3::generate_label_weights()
to generate the weights.Added the function CGAL::Polygon_mesh_processing::match_faces(),
which, given two polygon meshes, identifies their common faces as well as faces present in only either of them.
Added the functions: CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance()
that computes an estimate of the one-sided Hausdorff distance between two triangle meshes which
is bounded by a user-specified error bound; CGAL::Polygon_mesh_processing::bounded_error_symmetric_Hausdorff_distance()
that computes an estimate of the symmetric Hausdorff distance bounded by a user-specified error bound;
and CGAL::Polygon_mesh_processing::is_Hausdorff_distance_larger()
that returns true if the bounded-error Hausdorff distance between two meshes is larger than the user-specified
max distance.
Added the functions CGAL::Polygon_mesh_processing::squared_edge_length()
and CGAL::Polygon_mesh_processing::squared_face_area(),
which, compared to CGAL::Polygon_mesh_processing::edge_length()
and CGAL::Polygon_mesh_processing::face_area(),
enable avoiding square-root operations.
Added more functions in the visitor of the corefinement based methods to track all vertex creations.
Added an option to CGAL::Polygon_mesh_processing::self_intersections()
to report only a limited number of intersections (maximum_number()).
Compute_squared_length_3 providing operator(const Vector_3& v),
which computes the squared length of v, to the HeatMethodTraits_3
concept.libpointmatcher::GenericDescriptorOutlierFilter
that enables providing a map from a point to a weight associated with this point.Release date: July 2021
The support for the compiled version of CGAL is dropped. Only the header-only version is supported.
On Windows, the type used for CGAL::Exact_rational,
in Epick and indirectly (through Lazy_exact_nt)
Epeck may now be boost::multiprecision::mpq_rational, as has been the case on other platforms
for several releases. This depends on various options and is added to a list that includes
mpq_class,
CGAL::Gmpq,
leda_rational
and CGAL::Quotient<CGAL::MP_Float>.
A comprehensive list of the supported file formats is available in the Stream_support package here; inversely, the following page can be used to find out which CGAL data structures can be used given a specific file format.
3.14.is_translation(), is_scaling(), is_reflection(), and is_rotation() to the classes
Aff_transformation_2
and Aff_transformation_3,
which enable determining if the transformations use a specialized representation internally.oriented_side(const Point_2& p, ....)
that accept a point and a polygon.CGAL::Polyhedral_envelope,
providing a way to quickly check if a primitive (point, segment, or triangle)
is within a polyhedral envelope around a set of triangles. It is based on the work of
Bolun Wang, Teseo Schneider, Yixin Hu, Marco Attene, and Daniele Panozzo.
"Exact and efficient polyhedral envelope containment check." (ACM Trans. Graph., 39-4, July 2020).CGAL::Surface_mesh_topology::Curves_on_surface_topology::is_homotopic_to_simple_cycle(),
which can be used to determine whether a closed path on a surface mesh can be continuously
transformed to a cycle without self intersection.Polyhedral_envelope_filter,
which enables to perform mesh simplification inside a polyhedral envelope of the input mesh.insert_if_in_star()
to the class CGAL::Regular_triangulation,
which enables users to insert a point p in a regular triangulation on the condition that p
appears post-insertion in the star of a user-specified, existing vertex.Alpha_shape_euclidean_traits_2,
Weighted_alpha_shape_euclidean_traits_2, Alpha_shape_euclidean_traits_3, and
Weighted_alpha_shape_euclidean_traits_3. All CGAL kernel can be used directly as models
of the concepts of the 2D and 3D Alpha Shape packages.CGAL::TensorFlow::Neural_network_classifier has been removed.Release date: December 2020
Epick_d
and Epeck_d gain two new functors:
Compute_power_product_d
and Construct_power_sphere_d,
to deal with weighted points.CGAL/boost/graph/graph_traits_inheritance_macros.h,
which enables easily making any class inheriting from a model of a face graph concept, a model of the same concept.can_add_face(),
which tests whether a new face defined by a range of vertices can be added.CGAL::Object
to modern boost::variant.CGAL::Object
to boost::variant in all traits concepts and models.
As there exists an implicit conversion from boost::variant to CGAL::Object,
the new code is backward compatible. However, it is recommended that all calls
to the make-x-monotone functions are fixed to use the new return type.decompose()
interface to use boost::variant instead of legacy
CGAL::Object
As explained above, the code is backward compatible. However, it is recommended
that all calls to decompose() are fixed to use the new interface.clear_without_removing_property_maps()
to clear a mesh but keep all the created property maps added.remove_property_maps<Index_type>()
and remove_all_property_maps()
to remove all added property maps by index type or all of them respectively.set_recycle_garbage()
and does_recycle_garbage()
to the class Surface_mesh.CGAL::Polygon_mesh_processing::triangulate_face()
and CGAL::Polygon_mesh_processing::triangulate_faces(),
that enables the user to keep track of the newly created faces through the triangulation process.CGAL::Polygon_mesh_processing::corefine(),
CGAL::Polygon_mesh_processing::split()
and CGAL::Polygon_mesh_processing::clip()
functions, which enable the operations to be performed on a mesh with
self-intersections present in the intersection area.CGAL::Polygon_mesh_processing::stitch_borders(),
which can be used to specify which boundary cycles are eligible for stitching.Breaking change: new IO format for the ETHZ::Random_Forest classifier:
a conversion function from the outdated format to the new one is provided.
Added new functions to the class CGAL::Classification::Evaluation:
append()
to enrich the evaluation with additional results;
confusion()
to access the confusion matrix;
output functions to save the evaluation to and ASCII or HTML stream.
Added a new operator, CGAL::Classification::feature_cast<>,
for easy conversions.
The classes CGAL::Classification::Feature_set
and CGAL::Classification::Label_set
are now models of the concept Range.
The class CGAL::Classification::Label
now has attributes index, standard_index and color,
with automatic selection if the ASPRS standard names are used.
Added new functions in CGAL::Classification::Point_set_feature_iterator,
to enable users to select which features should be generated.
Added a new function, CGAL::Classification::Label_set::is_valid_ground_truth(),
to help users check if a ground truth matches a given label set.
CGAL::scanline_orient_normals(),
which orients a point cloud by estimating a line of sight.CGAL::halfspace_intersection_interior_point_3(),
which can be used to retrieve the point that is the most interior a convex closed volume
defined by the intersection of a set of halfspaces.Release date: September 2020
This package implements a tetrahedral isotropic remeshing algorithm, that improves the quality of tetrahedra in terms of dihedral angles, while targeting a given edge length.
See also the associated blog entry.
This package enables the computation of some topological invariants of surfaces, such as:
See also the associated blog entry.
This package implements an optimization algorithm that aims to construct a close approximation of the optimal bounding box of a mesh or a point set, which is defined as the smallest (in terms of volume) bounding box that contains a given mesh or point set.
See also the associated blog entry.
CGAL_Core library no longer requires Boost.Thread, even if the g++ compiler is used.Two new, detailed tutorials have been added:
Both tutorials provide complete code.
CompareSignedDistanceToLine_2
to the 2D/3D Kernel concept to compare
the signed distance of two points to a line, or the line passing through two given points.
Corresponding functors in the model (Compare_signed_distance_to_line_2) are also added.Epick_d
and Epeck_d gain two new functors:
Power_side_of_bounded_power_sphere_d
and Compute_squared_radius_smallest_orthogonal_sphere_d.
Those are essential for the computation of weighted alpha-complexes.CGAL::Surface_mesh::clear()
now removes all non-default properties instead of just emptying them.CGAL::alpha_expansion_graphcut(),
which regularizes a multi-label partition over a user-defined graph.CGAL::regularize_face_selection_borders(),
which uses this alpha expansion graphcut to regularize the borders of a selected faces on a triangle mesh.CGAL::set_triangulation_ids(),
which must be used to initialize vertex, edge, and face indices of a triangulation meant to be used with BGL algorithms.CGAL::AABB_tree::do_not_accelerate_distance_queries()
before the first distance query, and the tree can be built at any moment by calling
CGAL::AABB_tree::accelerate_distance_queries().CGAL::AABB_tree::accelerate_distance_queries()
and CGAL::AABB_tree::do_not_accelerate_distance_queries()
are no longer const functions.CGAL::Object
to modern boost::variant in all traits concepts and models.
As there exists an implicit conversion from boost::variant to CGAL::Object, the
new code is backward compatible. However, it is recommended that all calls
to the intersection functions are fixed to use the new return type.CGAL::Object
to modern boost::variant in the concept ArrDirectionalTraits::Intersect_2
and its models.CGAL::Object
to modern boost::variant in the (internally used) model Arr_labeled_traits_2.CGAL::Kd_tree::build()
is given an optional template parameter ConcurrencyTag (default
value remains CGAL::Sequential_tag
for backward compatibility).Epick_d
with dynamic dimension) — we says "to a lesser extent" because the points
are re-created by the kd-tree in a cache-friendly order after its construction,
so the coordinates are more likely to be stored in a near-optimal order
on the heap.
In these cases, the new EnablePointsCache template parameter of the
CGAL::Kd_tree
class can be set to CGAL::Tag_true. The points coordinates
will then be cached in an optimal way. This will increase memory
consumption but provides better search performance. See the updated
GeneralDistance
and FuzzyQueryItem
concepts for additional requirements when using such a cache.CGAL::box_intersection_d()
and CGAL::box_self_intersection_d().CGAL::hilbert_sort()
and CGAL::spatial_sort()
in 2D and 3D when the median policy is used.
The parallel versions use up to four threads in 2D, and up to eight threads in 3D.CGAL::convex_hull_3()
that takes a model of VertexListGraph has been added.CGAL::convex_hull_3_to_polyhedron_3() has been removed.
The function CGAL::convex_hull_3_to_face_graph()
should be used instead.CGAL::Polygon_mesh_processing::volume_connected_component(),
which can be used to get information about the nesting of the connected components of a given triangle mesh and about
the volumes defined.CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size(),
which can be used to remove connected components whose area or volume is under a certain threshold.
Area and volume thresholds are either specified by the user or deduced from the bounding box of the mesh.CGAL::Polygon_mesh_processing::keep_large_connected_components()
and CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size,
which can be used to perform a dry run of the operation, meaning that the function will return the number of connected
components that would be removed with the specified threshold, but without actually removing them.CGAL::Polygon_mesh_processing::split(),
which can be used to split meshes along a mesh or a plane.CGAL::Polygon_mesh_processing::split_connected_components()
to split a single mesh containing several connected components into several meshes containing one connected component.CGAL::Polygon_mesh_processing::merge_reversible_connected_components(),
CGAL::Polygon_mesh_processing::duplicate_non_manifold_edges_in_polygon_soup(),
and CGAL::Polygon_mesh_processing::orient_triangle_soup_with_reference_triangle_mesh(),
which can be helpful when repairing a polygon soup.CGAL::Polygon_mesh_processing::sample_triangle_soup(),
which generates points on a triangle soup surface.CGAL::Polygon_mesh_processing::does_self_intersect()
and CGAL::Polygon_mesh_processing::self_intersections().CGAL::Polygon_mesh_processing::stitch_borders()
now returns the number of halfedge pairs that were stitched.CGAL::Polygon_mesh_processing::polygon_mesh_to_polygon_soup().CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh
now allows passing a point map (for the point range) and a vertex point map (for the polygon mesh) via named parameters.CGAL::remove_outliers()
has been parallelized and thus has a new template parameter ConcurrencyTag.
To update your code simply add as first template parameter CGAL::Sequential_tag or CGAL::Parallel_tag
when calling this function.CGAL::cluster_point_set()
that segments a point cloud into connected components based on a distance threshold.CGAL::OpenGR::compute_registration_transformation(),
which computes the registration transformation for two point sets using the Super4PCS algorithm
implemented in the third party library OpenGR.CGAL::OpenGR::register_point_sets(),
which computes the registration transformation for two point sets using the Super4PCS algorithm
implemented in the third party library OpenGR,
and registers the points sets by transforming the data point set using the computed transformation.CGAL::pointmatcher::compute_registration_transformation()
computes the registration transformation for two point sets using ICP algorithm implemented
in the third party library libpointmatcher.CGAL::pointmatcher::register_point_sets(),
which computes the registration transformation for two point sets using ICP algorithm implemented
in the third party library libpointmatcher, and registers
the points sets by transforming the data point set using the computed transformation.CGAL::No_intersection_tag
has been deprecated in favor of two new tags: CGAL::No_constraint_intersection_tag
and CGAL::No_constraint_intersection_requiring_constructions_tag.
The latter is equivalent to the now-deprecated CGAL::No_intersection_tag, and allows constraints
to intersect as long as no new point has to be created to represent that intersection (for example,
the intersection of two constraint segments in a 'T'-like junction is an existing point
and as such does not require any new construction). The former tag, CGAL::No_constraint_intersection_tag,
does not allow any intersection, except for the configuration of two constraints having a single
common endpoints, for convenience.CGAL::split_subconstraint_graph_into_constraints()
to Constrained_triangulation_plus_2 to initialize the constraints
from a soup of disconnected segments that should first be split into polylines.CGAL::Triangulation_3::file_input()
have been added. It allows to load a CGAL::Triangulation_3
from an input stream, using functors to create vertices and cells.CGAL::TDS_3::file_input()
have been added. It allows to load a CGAL::Triangulation_data_structure_3
from an input stream, using functors to create vertices and cells.EdgeProfile has been removed. This concept was not actually in use as the CGAL-provided model CGAL::Edge_profile
was imposed to the user. Other concepts have been clarified to reflect the fact that the API uses this particular class.CGAL::Parallel_if_available_tag.
This tag is a convenience typedef to CGAL::Parallel_tag
if the third party library TBB has been found and linked with, and to
CGAL::Sequential_tag otherwise.Release date: November 2019
ShapeDetectionTraits has been renamed to EfficientRANSACTraits.Shape_detection_3 namespace has been renamed to Shape_detection.FaceGraph concept. Learn more about this new algorithm with this blog entry.Epeck_d, is now available.ComputeApproximateAngle_3,
to the 3D Kernel concepts to compute the approximate angle between two 3D vectors. Corresponding functors
in the model (Compute_approximate_angle_3)
and free function (approximate_angle)
have also been added.std::unordered_set
and std::unordered_map:
CGAL::Aff_transformation_2, CGAL::Aff_transformation_3,
CGAL::Bbox_2, CGAL::Bbox_3, CGAL::Circle_2,
CGAL::Iso_cuboid_3, CGAL::Iso_rectangle_2, CGAL::Point_2,
CGAL::Point_3, CGAL::Segment_2, CGAL::Segment_3,
CGAL::Sphere_3, CGAL::Vector_2, CGAL::Vector_3,
CGAL::Weighted_point_2 and CGAL::Weighted_point_3.CGAL::Polygon_mesh_processing::locate(Point, Mesh).
The location of a point on a triangle mesh is expressed as the pair of a face and the barycentric
coordinates of the point in this face, enabling robust manipulation of locations
(for example, intersections of two 3D segments living within the same face).smooth_mesh(),
which can be used to improve the quality of triangle elements based on various geometric characteristics.smooth_shape(),
which can be used to smooth the surface of a triangle mesh, using the mean curvature flow to perform noise removal.
(See also the new entry in the User Manual)CGAL::Polygon_mesh_processing::centroid(),
which computes the centroid of a closed triangle mesh.CGAL::Polygon_mesh_processing::stitch_boundary_cycle()
and CGAL::Polygon_mesh_processing::stitch_boundary_cycles(),
which can be used to try and merge together geometrically compatible but combinatorially different halfedges
that belong to the same boundary cycle.CGAL::Polygon_mesh_processing::keep_large_connected_components()
and CGAL::Polygon_mesh_processing::keep_largest_connected_components(), enabling users to define
how the size of a face is computed (the size of the connected component is the sum of the sizes of its faces).
If no property map is passed, the behavior is unchanged to previous versions: the size
of a connected component is the number of faces it contains.CGAL::Polygon_mesh_processing::non_manifold_vertices(),
which can be used to collect all the non-manifold vertices (i.e. pinched vertices,
or vertices appearing in multiple umbrellas) of a mesh.neighbor_radius
to use spherical neighbor queries instead of K-nearest neighbors queries for the following functions:
CGAL::bilateral_smooth_point_set(),
CGAL::jet_estimate_normals(),
CGAL::jet_smooth_point_set(),
CGAL::mst_orient_normals(),
CGAL::pca_estimate_normals() and
CGAL::remove_outliers().CGAL::Constrained_triangulation_plus_2::vertices_in_constraint_{begin/end}(Vertex_handle va, Vertex_handle vb) const;,
and CGAL::Constrained_triangulation_plus_2::remove_constraint(Vertex_handle va, Vertex_handle vb),
that is a pair of vertex handles is no longer a key for a polyline constraint.
Users must use a version prior to 5.0 if they need this functionality.CGAL::Regular_triangulation_euclidean_traits_2,
CGAL::Regular_triangulation_filtered_traits_2. Users must use a version prior to 5.0 if they need these classes.FaceGraph concept.
In addition, only the finite simplicies (those not incident to the infinite vertex) of the 2D triangulations
are now visible through this scope. The complete triangulation can still be accessed as a graph,
by using the graph traits of the underlying triangulation data structure (usually,
CGAL::Triangulation_data_structure_2).insert() function
of
CGAL::Triangulation_2
which takes a range of points as argument is now guaranteed to
insert the points following the order of InputIterator. Note
that this change only affects the base class Triangulation_2
and not any derived class, such as Delaunay_triangulation_2.insert()
function to CGAL::Triangulation_2
that takes a range of points with info.Triangulation_face_base_with_id_2
which enables storing user-defined integer IDs in the face of any 2D triangulation, a precondition to use some
BGL algorithms.insert()
function of CGAL::Triangulation_3
which take a range of points as argument are now guaranteed to
insert the points following the order of InputIterator. Note
that this change only affects the base class Triangulation_3
and not any derived class, such as Delaunay_triangulation_3.insert()
function to CGAL::Triangulation_3 that takes a range of points with info.CGAL::read_ply()
and CGAL::write_ply(),
enabling users to save and load additional property maps of the surface mesh.CGAL::convert_nef_polyhedron_to_polygon_soup()CGAL::Color has been cleaned up.CGAL::read_WKT()CGAL::read_point_WKT()CGAL::read_multi_point_WKT()CGAL::read_linestring_WKT()CGAL::read_multi_linestring_WKT()CGAL::read_polygon_WKT()CGAL::read_multi_polygon_WKT()CGAL::write_point_WKT()CGAL::write_polygon_WKT()CGAL::write_linestring_WKT()CGAL::write_multi_point_WKT()CGAL::write_multi_polygon_WKT()CGAL::write_multi_linestring_WKT()Release date: March 2019
Added the following new functions to detect and repair issues in polygon soups:
CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup(),
which detects and removes points that are not used in any
polygon of the soup.CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup(),
which detects and merges points that share the same geometric
position.CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup(),
which detects and merges polygons that are identical.CGAL::Polygon_mesh_processing::repair_polygon_soup(), which
applies a number of repairing steps (a subset of which are the
functions above) to clean and repair a polygon soup.Added the following new functions to detect and repair degeneracies in polygon meshes:
CGAL::Polygon_mesh_processing::degenerate_edges()CGAL::Polygon_mesh_processing::degenerate_faces()CGAL::Polygon_mesh_processing::is_non_manifold_vertex()CGAL::Polygon_mesh_processing::is_degenerate_triangle_face()CGAL::Polygon_mesh_processing::is_degenerate_edge()CGAL::Polygon_mesh_processing::is_needle_triangle_face()CGAL::Polygon_mesh_processing::is_cap_triangle_face()CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices()CGAL::Polygon_mesh_processing::extract_boundary_cycles()CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle()CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycles()Added the class CGAL::Rigid_triangle_mesh_collision_detection to
detect intersections between meshes and volumes undergoing affine
transformations.
CGAL::mst_orient_normals() can now be called with a set of
user-selected seed points that are known to be already oriented. A
new optional named parameter point_is_constrained_map is added
for this purpose. The original behavior (using one unique and
automatically selected seed) is kept if this parameter is not
used.Added a new experimental classifier
TensorFlow::Neural_network_classifier.
For uniformity, ETHZ_random_forest_classifier is renamed
ETHZ::Random_forest_classifier and
OpenCV_random_forest_classifier is renamed
OpenCV::Random_forest_classifier.
The training algorithm of ETHZ::Random_forest_classifier was
parallelized.
Added a constructor to copy a ETHZ::Random_forest_classifier
using a different data set as input.
Added 3 new geometric features, Height_above, Height_below and
Vertical_range.
AABB_face_graph_triangle_primitive and
AABB_halfedge_graph_segment_primitive now use as Id a pair of
descriptor and graph pointer in the case they are configured to
deal with a possible different graph per primitive (configuration
set using a template tag).Fixed a bug in the surface-sweep framework (Surface_sweep_2)
that ensures that an event is never left without (left or right)
curves.
Fixed a constructor of Arr_counting_traits.h. (In particular,
added missing const of a parameter).
Fixed zone computation of a curve in cases where the lexicographic smallest end of the curve lies on the parameter space.
Implemented missing function object Compare_x_near_boundary of
Arr_polyline_traits_2, Arr_polycurve_traits_2, and
Arr_polycurve_basic_traits_2.
CGAL::write_vtu(), that writes a 2D mesh in a .vtu file,CGAL::output_to_vtu(), that writes a 3D mesh in a .vtu file.Added a method copy_properties() that allows to copy the
properties from a point set to another one (without copying the
content);
Added a method insert(const Point_set&, const Index&) to copy a
point along with all its associated properties from another point
set;
remove() methods now only invalidate the end() iterator
instead of invalidating all iterators;
Added a method is_removed() that takes an index as argument;
Added a method cancel_removals() to restore removed points (if
no point was inserted since then an garbage was not collected);
Breaking change: unified API of method add_normal_map() with
add_property_map(): it now returns a pair of property map + bool
(that tells if the property was added) instead of just the
property map;
Added a method properties_and_types() in addition to
properties(): this new one returns pairs of std::string +
std::type_info in order to also know the type of each property.
write_wrl() for writing into VRML 2.0 format.CGAL::write_vtp() for writing a triangulated
face graph in a .vtp file (XML VTK format).Release date: October 2018
CGAL_Qt5 now contains a fork of the version 2.7.0 of
libQGLViewer. The corresponding code is in the package
GraphicsView. The dependency for the external library
libQGLViewer is therefore dropped for all demos.CGAL::draw() is added in the packages Polyhedral
Surface, Surface Mesh, Linear Cell Complex, 2D Triangulations, and
3D Triangulations, enabling to draw the corresponding data
structures.operator() that takes a Ray_3 has been added to the concept
ConstructProjectedPoint_3.Added the function extreme_points_3() computing the points on
the convex hull without underlying connectivity.
Added a traits adapter called Extreme_points_traits_adapter_3
that enables the use of the function extreme_points_3() on a
range of keys, each key being associated to 3D point using a
property map. This can be used to get the vertices of a mesh that
are on it convex hull, or the indices of points in a range that
are on it convex hull.
Fix a bug in the computation of the 3D convex hull that was leaving extra points within subset of coplanar points that do not belong to the minimal convex hull.
Added a new type of intersection to handle the insertion of
intersecting constraints in a Constrained_triangulation_2.
Breaking change: The long-deprecated class
Triangulation_cell_base_with_circumcenter_3 and its associated
concept have been removed. Users should use the classes
Delaunay_cell_base_with_circumcenter_3 or
Regular_cell_base_with_circumcenter_3, depending on which type
of triangulation they are using.
Breaking change: The deprecated functions mirror_index and
mirror_vertex of the class Triangulation_face_base_2 have been
removed. Users should use the equivalent functions from the class
Triangulation_2.
Breaking change: The template parameters of the class template
Labeled_mesh_domain_3 have been simplified. The three
constructors of that class template have been replaced by a new
unique constructor using Boost named parameters. Three new static
template member functions that act as named constructors have been
added:
create_gray_image_mesh_domain(), to create a domain from a 3D
gray image,create_labeled_image_mesh_domain(), to create a domain from a 3D
labeled image, andcreate_implicit_mesh_domain(), to create a domain from an
implicit function.The class templates Implicit_mesh_domain_3,
Gray_image_mesh_domain_3, and Labeled_image_mesh_domain_3 are
now deprecated.
Breaking change: The headers
<CGAL/Mesh_3/Implicit_to_labeled_function_wrapper.h> and
<CGAL/Mesh_3/Labeled_mesh_domain_3.h>, that were deprecated
since CGAL 4.5, have been removed.
Breaking change: the concepts MeshCellCriteria_3 and
MeshFacetCriteria_3 now require the triangulation to be passed
in their operator(). Models of these concepts that are provided
by CGAL have been modified accordingly.
Breaking change: It is no longer possible to use the
deprecated, pre-CGAL 3.8 specifications in MeshCellCriteria_3
and MeshFacetCriteria_3 (that is, using Facet_badness and
Cell_badness instead of Is_facet_bad and Is_cell_bad).
The concept MeshFacetCriteria_3 no longer requires the function
operator()(Cell_handle c, int i).
The concept MeshEdgeCriteria_3 no longer requires the function
operator()(const Edge& e).
The concept MeshComplexWithFeatures_3InTriangulation_3 no longer
requires the functions number_of_edges(Curve_index index) and
number_of_corners(Corner_index index).
Introduced the concept MeshTriangulationTraits_3, which covers
the needs of the traits class used in Mesh_3 (and
Periodic_3_mesh_3). The traits class used as template parameter
of Mesh_triangulation_3 and Periodic_3_mesh_triangulation_3
must be a model of this concept.
Added the function
Mesh_domain_with_polyline_features_3::add_corner(), which allows
users to add a single corner (that is not incident to any
polyline) to the mesh complex.
Breaking change: CGAL::lloyd_optimize_mesh_3 now depends on
the Eigen library.
Added a named parameter in stitching functions that allows to choose whether the operation should be performed per connected component or globally.
Added a function, CGAL::Polygon_mesh_processing::transform(), to
apply a transformation to a mesh.
Added a named parameter visitor in corefinement-related
functions that makes it possible to pass a visitor to the function
in order to track the creation of new faces.
Added a named parameter throw_on_self_intersection in all
corefinement-related functions, which enables to check for
self-intersecting faces involved in the intersection before trying
to corefine the input meshes. This new parameter replaces the
bool parameter in corefine().
Added the function corefine_and_compute_boolean_operations(),
which can be used to compute the result of several Boolean
operations between two volumes at the same time.
Added the function clip(), which can be used to clip a
triangulated surface mesh by a plane or a clipping volume.
Constrained vertices are now guaranteed to be kept in the mesh
after calling isotropic_remeshing() (and not only the points
associated to constrained vertices, as it was before).
Added a function, CGAL::Polygon_mesh_processing::extrude_mesh(),
to perform an extrusion of an open polygon mesh.
CGAL::Monge_via_jet_fitting now depends on
the Eigen library.CGAL::bilateral_smooth_point_set(),
CGAL::compute_average_spacing(),
CGAL::grid_simplify_point_set(),
CGAL::hierarchy_simplify_point_set(),
CGAL::jet_estimate_normals(), CGAL::jet_smooth_point_set(),
CGAL::pca_estimate_normals(), CGAL::remove_outliers() and
CGAL::wlop_simplify_and_regularize_point_set().Added data structures to handle classification of Surface Meshes and of Clusters.
Added public API to compute features in parallel.
Breaking change: features based on products/divisions of eigenvalues are replaced by simple eigenvalue features. Features based on statistics on the HSV color channels are replaced by simple HSV color channel features.
Breaking change: the API of
CGAL::Classification::Point_set_feature_generator has been
simplified.
CGAL::Approximate_min_ellipsoid_d now
depends on the Eigen library.The output of the natural and regular neighbor functions (resp. the gradient fitting functions) is no longer restricted to a Point/Coordinate pair (resp. Point/Vector pair). Instead, users can provide their own functor to format the output as they desire.
The interpolation functions can now operate on any combination of Type/Coordinate, provided that the values and gradients functors can also be evaluated using 'Type'.
The combination of these two changes allow, for example, to operate with Vertex/Coordinate pairs, which enables a more efficient access to values and gradients by storing information directly in the vertex.
The concepts InterpolationTraits and GradientFittingTraits
have been updated to reflect the real needs of the code (some
types and operators were used in the code but did not appear in
the concepts).
Added a helper function, CGAL::is_valid_polygon_mesh, that
checks the validity of a polygon mesh using BGL functions.
Improved the function CGAL::Euler::collapse_edge such that the
target vertex of the collapsed edge is now always kept after the
collapse.
The function copy_face_graph() now uses named parameters, some
allowing it to use property maps instead of output iterators.
Addition of the following named parameters :
CGAL::Diagonalize_traits is now deprecated
and should not be used. The class CGAL::Eigen_diagonalize_traits
(along with the Eigen library) should be used instead.Refracted and fixed the graph_traits for the dual of an arrangement of the
following types:
Arrangement_on_surface_2,
Arrangement_2,
Arrangement_on_surface_with_history_2, and
Arrangement_with_history_2.
Breaking change: The old <CGAL/graph_traits_Dual_Arrangement_2.h>
header file has been replaced by the four header files below; each defines
the graph_traits for dual of the corresponding arrangement type.
<CGAL/graph_traits_dual_arrangement_on_surface_2.h>,
<CGAL/graph_traits_dual_arrangement_2.h>,
<CGAL/graph_traits_dual_arrangement_on_surface_with_history_2.h>, and
<CGAL/graph_traits_dual_arrangement_with_history_2.h.
Release date: April 2018
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.
The Microsoft Visual C++ 2017 version 15.3 has introduced support for
C++17, with the compilation flag /std:c++17. CGAL 4.12 has an initial
support for that flag: the code will compile, but a lot of deprecation
warnings will remain. Note that Boost version 1.67 is the first version
of Boost supporting /std:c++17.
The compilation flag /permissive- of Visual C++ is now supported.
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.
<CGAL/convex_hull_3.h> no longer
includes <CGAL/Polyhedron_3.h>, as the convex hull function works
with any model of the concept MutableFaceGraph.When removing an edge from an arrangement and the user has requested to remove the end-vertices in case they become redundant (either isolated or approach infinity), defer the removal of the such end-vertices to occur after the observer is notified that the edge has been removed. This is symmetric (opposite) to the order of notification when an edge is inserted.
The user can restore old (non-symmetric) behavior by defining the macro:
CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
Periodic_2_triangulation_hierarchy_vertex_base_2 (and its
corresponding header) have been removed. Users should directly use
the class Triangulation_hierarchy_vertex_base_2, which is
identical.circumcenter(),
side_of_oriented_circle(), and is_extensible_in_1_sheet_h[12]()
are related to Delaunay triangulations and have been moved from
Periodic_2_triangulation_2 to
Periodic_2_Delaunay_triangulation_2.CGAL::Periodic_2_triangulation_2 as
underlying triangulation for Alpha_shape_2.facets_in_complex_2_to_triangle_mesh() that
exports Surface_mesh_complex_2_in_triangulation_3 facets into
a MutableFaceGraph.facets_in_complex_3_to_triangle_mesh() that
exports Mesh_complex_3_in_triangulation_3 facets into a
MutableFaceGraph.MeshDomainWithFeatures_3 has been
modified, to improve the performance and the reliability of the
sampling of 1D curves of the domain.manifold(), manifold_with_boundary(), and non_manifold() are
added.run_under_wasserstein_tolerance() which allows the
user to perform curve reconstruction by relying on a threshold on
the Wasserstein distance. This is useful when the number of edges
in the expected output reconstruction is not known.Added two functions for orienting connected components :
CGAL::Polygon_mesh_processing::orient()CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()Added a new function for intersection tests between triangle meshes and/or polylines or range of polylines, and another one to report all the pairs of meshes intersecting from a range of meshes:
CGAL::Polygon_mesh_processing::do_intersect()CGAL::Polygon_mesh_processing::intersecting_meshes()Added new functions for feature detection and feature-guided segmentation:
CGAL::Polygon_mesh_processing::detect_sharp_edges()CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()CGAL::Polygon_mesh_processing::sharp_edges_segmentation()CGAL::Shape_detection_3::Efficient_RANSAC_traits is now called
CGAL::Shape_detection_3::Shape_detection_traits.CGAL::Region_growing. This is a deterministic
alternative to RANSAC for plane detection.CGAL::regularize_planes() is
generalized to accept other types of input than the RANSAC output.CGAL::Efficient_RANSAC and
CGAL::Region_growing.CGAL::structure_point_set() is
generalized to accept other types of input than the RANSAC output.Add helper function CGAL::expand_face_selection_for_removal that
expands a face selection to avoid creating a non manifold mesh when
removing the selected faces.
Added support for dynamic property maps.
Added an interface to the METIS library, which allows to partition
any mesh that is a model of FaceListGraph. Wrappers to the
METIS functions METIS_PartMeshNodal and METIS_PartMeshDual are
offered.
Release date: September 2017
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.Regular_triangulation, which provides
functionality for dD weighted Delaunay triangulations. Note that the
removal of points is not yet supported.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.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.operator >>(std::istream&, Surface_mesh&) no longer clears
the surface mesh.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.CGAL::Seam_mesh in the package CGAL and the BGL.<CGAL/XXX.h> with <CGAL/Surface_mesh_parameterization/XXX.h>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.<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.Weighted_PCA_smoother and Alpha_shape_mesher.Jet_smoother and Advancing_front_mesher.WeightedAlphaShapeTraits_2, is introduced to provide
requirements on the traits class for 2D weighted alpha shapes. All
models of the concept Kernel are models of this new concept.AlphaShapeTraits_2 now provides requirements on the
traits class for 2D basic alpha shapes, and refines
DelaunayTriangulationTraits_2.GradientFittingTraits now
additionally requests a weighted point type Weighted_point_d and a
functor Construct_point_d. The model
CGAL::Interpolation_gradient_fitting_traits_2 has been
appropriately modified to still be a model of the concept
GradientFittingTraits.Construct_point_2, to the concepts TriangulationTraits_2 and
RegularTriangulationTraits_2 and a new functor requirement,
Construct_point_3, to the concepts TriangulationTraits_3 and
RegularTriangulationTraits_3. All models of the concept Kernel
already provide these functors.RegularTriangulationVertexBase_2 and
RegularTriangulationVertexBase_3. These concepts describe the
requirements on classes meant to represent a vertex of a regular
triangulation. Concepts that previously refined
TriangulationVertexBase_2 or TriangulationVertexBase_3 but
described in fact a vertex class used in a regular triangulation,
such as the concept MeshVertexBase_3 in the 3D mesh generation
package, now refine the corresponding new regular vertex concept.Point. Note that this does not change the requirements but only
the name: Point is still expected to be equal to
Traits::Point_[23] for basic and Delaunay triangulations or to
Traits::Weighted_point_[23] for regular triangulations.
Consequently:
RegularTriangulationVertexBase_2 now requests a
Point type (equal to Traits::Weighted_point_2)RegularTriangulationCellBase_3 now requests a
Point type instead of a Weighted_point type (but still equal
to Traits::Weighted_point_3)DelaunayTriangulationCellBase_3 now requests a
Point type instead of a Point_3 type (but still equal to
Traits::Point_3).RegularTriangulationCellBaseWithWeightedCircumcenter_3, which
describes the requirements on a cell of a regular triangulation that
caches its circumcenter. The existing class
Regular_triangulation_cell_base_with_weighted_circumcenter_3 is
the default model of this concept.Robust_weighted_circumcenter_filtered_traits_3 which provides
robust versions of the kernel functors
Construct_weighted_circumcenter_3, Compute_squared_radius_3, and
Compute_squared_radius_smallest_orthogonal_sphere_3. This class
can be used as traits class in the Mesh_3 package to
efficiently yet robustly generate 3D meshes.Polyhedral_complex_mesh_domain_3. The domain is defined by a
collection of triangulated surfaces, forming a complex.Periodic_3_Delaunay_triangulation_traits_3 now inherits
Periodic_3_triangulation_traits_3.Periodic_3_triangulation_3 were renamed. The introduction of
Periodic_3_regular_triangulation_3 required to distinguish between
functions such as segment() returning a segment of weightless
points, or a segment of weighted points. As a general rule, previous
geometrical access functions will return objects with point type
that of the triangulation (thus, weighted objects when using
weighted triangulations) and functions containing construct in the
name will always return weightless geometrical objects.Periodic_3TriangulationTraits_3
now requests a domain getter: get_domain().RegularTriangulationCellBaseWithWeightedCircumcenter_3, which
describes the requirements on a cell of a regular triangulation that
caches its circumcenter. The existing class
Regular_triangulation_cell_base_with_weighted_circumcenter_3 is
the default model of this concept.MeshCellBase_3 has been changed from Triangulation::Point to
TriangulationTraits::Point_3 to reflect that it is a weightless
point.invalidate_circumcenter() of the
concept MeshCellBase_3 is renamed to
invalidate_weighted_circumcenter_cache() and moved to the new
concept RegularTriangulationCellBaseWithWeightedCircumcenter_3,
which the concept MeshCellBase_3 now refines.CGAL::poisson_surface_reconstruction_delaunay() is provided in
addition to the current class-based API in order to make it easier
to use.CGAL::read_ply_points_with_properties()). A new function to write
PLY with properties is provided
(CGAL::write_ply_points_with_properties()).Kd_tree::remove(Point).AABB_traits for a property map that
associates a bounding box to a primitiveCGAL::Linear_cell_complex_for_combinatorial_map so that it is a
model of the graph concepts BidirectionalGraph and
EdgeAndVertexListGraph and of the concept MutableFaceGraph. This
class can thus now be used in all BGL functions and algorithms.CGAL::Face_filtered_graph that wraps an existing graph
and hide all simplices that are not in the selected connected
components.CGAL::Seam_mesh. The Seam_mesh is a graph
adaptor which allows to create virtual borders when marking edges as
seam edges.read_off() and write_off().Release date: May 2017
cgal_create_cmake_script now enables C++14 by
default.thread_local, the CGAL_Core library now always requires
Boost.Thread if the g++ compiler is used.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.).CGAL_CMAP_DART_DEPRECATED macro to keep the old behavior.reserve() in the
concept MutableFaceGraph. Models provided by CGAL have been
updated.compare_slopes() was renamed
compare_slope.l_infinity_distance() for 2D and 3D.Compare_slope_3, and the free function compare_slope()
is available.Angle_3 to qualify the
angle between the normal of the triangle given by three points, and
a vector.Surface_mesh, and
generally speaking any model of the concept MutableFaceGraphconvex_hull_3_to_polyhedron_3() is deprecated and
convex_hull_3_to_face_graph.h should be used instead.Convex_hull_traits_3 now documents a nested type
Polygon_mesh instead of Polyhedron_3. The other nested type is
kept for backward compatibility.CGAL::convex_hull_incremental_3() deprecated
since CGAL 4.6.Linear_cell_complex which is now renamed
Linear_cell_complex_for_combinatorial_map_dart.insert_in_hole.Regular_triangulation_filtered_traits_2 deprecated since
CGAL 3.6 has been removed.Regular_triangulation_euclidean_traits_2, as
the weighted point and the function objects for weighted points are
part of the concept Kernel/Regular_triangulation_2 can take a kernel as template
argument, that is one no longer has to use
Regular_triangulation_euclidea_traits_2, although this still
works.Regular_triangulation_filtered_traits_3 deprecated since
CGAL 3.6 has been removed.Regular_triangulation_euclidean_traits_3, as
the weighted point and the function objects for weighted points are
part of the concept Kernel/Regular_triangulation_3 can take a kernel as template
argument, that is one no longer has to use
Regular_triangulation_euclidean_traits_3, although this still
works.link_to_face_graph() to copy the set of faces
incident to a vertex into a model of FaceGraph.CGAL::Polyhedral_mesh_domain_with_features_3(std::string) is
deprecated.CGAL::Polygon_mesh_processing::corefine_and_compute_union()CGAL::Polygon_mesh_processing::corefine_and_compute_difference()CGAL::Polygon_mesh_processing::corefine_and_compute_intersection()CGAL::Polygon_mesh_processing::corefine()CGAL::Polygon_mesh_processing::does_bound_a_volume()CGAL::Polygon_mesh_processing::surface_intersection()sample_triangle_mesh(), approximated_Hausdorff_distance(),
approximated_symmetric_Hausdorff_distance(),
max_distance_to_triangle_mesh(), max_distance_to_point_set().CGAL::Polygon_mesh_processing::bbox_3() has been
renamed CGAL::Polygon_mesh_processing::bbox().CGAL::remove_outliers() has an additional parameter based
on a distance threshold to make it easier and more intuitive to use.CGAL::convert_nef_polyhedron_to_polygon_mesh() to
convert a Nef_polyhedron_3 to any model of the MutableFaceGraph
concept.CGAL::Graph_with_descriptor_with_graph that wraps an
existing graph and provides a reference to the said graph to all of
its descriptors.FaceListGraph
(CGAL::Random_points_in_triangle_mesh_3),CGAL::Random_points_in_tetrahedral_mesh_boundary_3),CGAL::Random_points_in_tetrahedral_mesh_3),CGAL::Random_points_in_triangle_mesh_2),CGAL::Random_points_in_triangles_3 and
CGAL::Random_points_in_triangles_2).CGAL::Random_points_on_segment_3).Release date: Sept 2016
Polygon_nop_decomposition_2, that merely passed the input polygon
to the list of output polygons.minkowski_sum_2(), which
accepts 2 decomposition strategies.minkowski_sum_by_decomposition_2(P, Q, decom_no_holes, decomp_with_holes),
which computes the 2D Minkowski sum using optimal choices of
decomposition strategies.make_combinatorial_hexahedron(),
make_combinatorial_polygon(), make_combinatorial_tetrahedron(),
make_edge(), insert_cell_0_in_cell_1(),
insert_cell_0_in_cell_2(), insert_cell_1_in_cell_2(),
insert_cell_2_in_cell_3(), insert_dangling_cell_1_in_cell_2(),
is_insertable_cell_1_in_cell_2(),
is_insertable_cell_2_in_cell_3(), is_removable(),
remove_cell()) which are now member functions in the
CombinatorialMap concept.CGAL_CMAP_DEPRECATED. This API was deprecated since CGAL
4.4.CGAL::read_ply_custom_points() that allows the user
to read any additional point attribute from a PLY input point set.CGAL::structure_point_set(): new algorithm that takes advantage of
detected planes to produce a structured point set (with flat
regions, sharp edges and vertices).CGAL::regularize_planes(). This
allows the user to favor parallelism, orthogonality, coplanarity
and/or axial symmetry between detected planes.CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh() to
check whether a polygon soup is a polygon mesh.CGAL::isotropic_remeshing():
CGAL::Polygon_mesh_processing::triangulate_face()
and CGAL::Polygon_mesh_processing::triangulate_faces() now
indicate whether some faces have not been triangulated.SRE_ARAP to use the Smoothed Rotation Enhanced
As-Rigid-As-Possible deformation algorithm.AABB_tree::first_intersection() and
AABB_tree::first_intersected_primitive() that compute the
intersection which is closest to the source of a rayCGAL::copy_face_graph() to copy a source
FaceListGraph into another FaceListGraph of different type.CGAL::Dual that creates the dual view of a FaceGraph
and a creation function CGAL::dual(primal).CGAL_USE_PROPERTY_MAPS_API_V1. This API was deprecated since CGAL
4.3.Release date: April 2016
Boost.Thread as
we use the C++11 keyword thread_local and the C+11 class
std::mutex .GeneralPolygonSetDcelHalfedge and
GeneralPolygonSetDcelFace for more details. If you use a different
simplex types, inheriting your simplices from CGAL::Gps_face_base
and CGAL::Gps_halfedge_base is sufficient to accommodate for the
update.size_type. If no more mark is available,
get_new_mark throws an exception, instead of returning -1.MeshDomain_3 must
now provide a member function bbox().Filter is replaced by another optional
template functor Priority. This allows to change the way facets
are prioritized by the algorithm instead of having a simple option
to reject some facets.
Breaking change: Programs using the old Filter API will not
compile anymore as it must be replaced with the Priority API as
described in the manual. Codes using the default behavior are not
impacted.CGAL::Polygon_mesh_processing::isotropic_remeshing() and a helper
function for isotropic remeshing :
CGAL::Polygon_mesh_processing::split_long_edges()CGAL::Polygon_mesh_processing::border_halfedges()
to collect the border of a given face rangeCGAL::Polygon_mesh_processing::remove_isolated_vertices() to be
used on any polygon meshCGAL::Polygon_mesh_processing::triangulate_face()
to triangulate a single face of a polygon meshCGAL::Polygon_mesh_processing::triangulate_faces() to triangulate
a range of faces of a polygon meshkeep_large_connected_components()bbox_3() to compute the bounding box of a polygon
mesh.Concurrency_tag for
the functions compute_average_spacing(),
edge_aware_upsample_point_set(), jet_estimate_normals(),
jet_smooth_point_set(), and pca_estimate_normals(). To update
your code simply add as first template parameter
CGAL::Sequential_tag or CGAL::Parallel_tag when calling one of
these functions.CGAL::Parallel_tag can no longer be used in Point Set Processing
algorithms if TBB is not available.CGAL::hierarchy_simplify_point_set(). It allows either to
uniformly simplify the point set or to automatically adapt the local
density of points to the local variation of the input computed by
principal component analysis.CGAL::read_ply_points(), CGAL::read_ply_points_and_normals(),
CGAL::write_ply_points() and
CGAL::write_ply_points_and_normals().LSCM_parameterizer_3 now uses by default Eigen instead of OpenNL
as a model of SparseLinearAlgebraTraits_d.DiagonalizeTraits for functions
CGAL::linear_least_squares_fitting_2() and
CGAL::linear_least_squares_fitting_3(). This allows to either
choose the legacy internal diagonalization code from CGAL or the
Eigen implementation (or any class that is a model of
DiagonalizeTraits). Variants of the function that automatically
deduce the kernel also automatically select the diagonalizer, so the
API is mostly preserved.CGAL::split_graph_into_polylines() that allows to
extract from a soup of segments given as a graph, polylines with
nodes of degree at most 2. In addition a functor can be passed to
the function to specify additional polyline endpoints.CGAL::expand_face_selection(),
CGAL::reduce_face_selection(), CGAL::expand_edge_selection(),
CGAL::reduce_edge_selection() CGAL::expand_vertex_selection(),
CGAL::reduce_vertex_selection() and
CGAL::select_incident_faces().CGAL::clear which clears a MutableFaceGraph
efficiently and generically.Release date: October 2015
libCGAL_Qt5 and demos, you must set the cmake
or environment variable Qt5_DIR to point to the path to the
directory containing the file Qt5Config.cmake created by your Qt5
installation. If you are using the open source edition it should be
/path-to/qt-everywhere-opensource-src-<version>/qtbase/lib/cmake/Qt5.FaceGraph.TriangulatedSurfaceMesh which are not at the same time models of
the concept FaceGraph.Epick_d gains 3 new functors: Construct_circumcenter_d,
Compute_squared_radius_d, Side_of_bounded_sphere_d. Those are
essential for the computation of alpha-shapes.Arr_polycurve_traits_2<SubcurveTraits>, which handles general
piece-wise (polycurve) curves. The pieces do not necessarily have to
be linear.ArrangementApproximateTraits_2
and ArrangementConstructXMonotoneCurveTraits_2.
ArrangementLandmarkTraits_2 concept, which has
two requirements, now refines the two respective concepts above.Arr_polyline_traits_2<SegmentTraits> template must be
substituted with a traits class that is a model of the
ArrangementConstructXMonotoneTraits_2 concept among the other
when Arr_polyline_traits_2 is instantiated.PolygonConvexDecomposition_2 concept)
based on vertical decomposition and constrained Delaunay
triangulation, respectively. These new models also support the
convex decomposition of polygons with holes.Periodic_3_triangulation_traits_3 to
Periodic_3_Delaunay_triangulation_traits_3.Periodic_3TriangulationTraits_3 to
Periodic_3DelaunayTriangulationTraits_3.Periodic_3_triangulation_traits_3 and the concept
Periodic_3TriangulationTraits_3.CGAL::lloyd_optimize_mesh_2() that
implements the Lloyd (or Centroidal Voronoi Tessellation)
optimization algorithm in a Constrained Delaunay Triangulation. For
optimization, the triangulation data structure on which the mesher
relies needs its VertexBase template parameter to be a model of
the new concept DelaunayMeshVertexBase_2.CGAL::compute_vcm() for computing the Voronoi
Covariance Measure (VCM) of a point set. The output of this function
can be used with the function CGAL::vcm_is_on_feature_edge() to
determine whether a point is on or close to a feature edge. The
former function is also internally used by
CGAL::vcm_estimate_normals() to estimate the normals of a point
set and it is particularly suited to point sets with noise.CGAL::hilbert_sort_on_sphere and
CGAL::spatial_sort_on_sphere.CGAL::Random_points_in_triangle_2,
CGAL::Random_points_in_triangle_3,
CGAL::Random_points_in_tetrahedron_3).Release date: August 2015
This release only fixes bugs. See the list of fixed bugs on Github:
https://github.com/CGAL/cgal/issues?q=milestone%3A4.6.2
Release date: June 2015
This release only fixes bugs. See the list of fixed bugs on Github:
https://github.com/CGAL/cgal/issues?q=milestone%3A4.6.1+-label%3Ainvalid
Release date: April 2015
CGAL::Polyhedron_3
and CGAL::HalfedgeDS.Epick_d kernel
may not work with Intel C++ Compiler prior to version 15.
Documentation has been updated.halfspace_intersection_3 and
halfspace_intersection_with_constructions_3 to compute the
intersection of halfspaces defining a closed polyhedron.Convex_hull_traits_3. This traits is
used by default with the kernel
Exact_predicates_inexact_constructions_kernel.CGAL::convex_hull_incremental_3 is deprecated and the
function convex_hull_3 should be used instead.correct_invalid_attributes,
set_automatic_attributes_management and
are_attributes_automatically_managed methods in CombinatorialMap
concept. This allows high level operations to not update non void
attributes during massive calls of these operations, but only after
the end of their executions.Constrained_triangulation_plus_2 now can handle
polylines as constraints.Constraint_id has been introduced which
replaces pair<Vertex_handle,Vertex_handle> as identifier of a
constraint.output_boundary_to_off and
output_facets_in_complex_to_off in the class
CGAL::Mesh_complex_3_in_triangulation_3 to export the boundary of
a domain or a subdomain.AABB_halfedge_graph_segment_primitive and
AABB_face_graph_triangle_primitive in order to be able to build
primitives one by one.CGAL::Splitters.h sliding midpoint rule, where
degenerated point sets (e.g.,points on segment) caused the kd-tree
to get linear.Orthogonal_k_neighbor_search. Note that VC
2013 does not compile boost::container::deque of Boost 1_55 and
does hence have a workaround which does not have the improvement.OrthogonalDistance has new
function overloads for min_distance_to_rectangle and
max_distance_to_rectangle with an additional reference parameter
std::vector.[tree.begin(),tree.end()] is not the order of insertion of the
points into the tree. This was not guaranteed before but might have
been observed and exploited by users.kd_tree_leaf_node and kd_tree_internal_node from
kd_tree_node to save memory.random_convex_hull_in_disc_2 that efficiently
generates a random polygon as the convex hull of uniform random
points chosen in a disc.Release date: February 2015
Release date: December 2014
Release date: October 2014
CGAL::Deform_mesh to CGAL::Surface_mesh_deformation).HalfedgeGraph concept. In particular:
halfedge_descriptor in the
specialization of the class boost::graph_traits.halfedge_graph_traits.HalfedgeGraph is considered as an undirected graph.
Thus any call to edges() should be replaced by halfedges()
and num_edges() now returns the number of (undirected) edges.is_border_edge and is_border_halfedge
properties are removed. The free functions is_border() and
is_border_edge() should be used instead.HalfedgeGraph specific free functions.FaceGraph concept.AABB_halfedge_graph_segment_primitive from the
package 3D Fast Intersection and Distance Computation to the API
change.AABB_face_graph_triangle_primitive from the package
3D Fast Intersection and Distance Computation to accept model of
the newly introduced concepts.boost::graph_traits for
OpenMesh::PolyMesh_ArrayKernelT as proof of concept. A
OpenMesh::PolyMesh_ArrayKernelT becomes a model of the
aforementioned concepts when including
CGAL/boost/graph/graph_traits_PolyMesh_ArrayKernelT.h.Epick_d of the Kernel_d concept is introduced. It
provides better performance through arithmetic filtering and
specializations for fixed dimensions. It may not work with compilers
as old as gcc-4.2, but was tested with gcc-4.4.kd_tree with CGAL's official Kd_tree
from Spatial_searching package; results in a small performance
gain. Removed the private kd_tree package.Regular_triangulation_cell_base_3.
The cache value is computed when cell->circumcenter() or
rt.dual(cell) functions are called.Labeled_mesh_domain_3 which
takes an Iso_cuboid_3.demo/Polyhedron/ and
demo/Mesh_3/ can now use the handling of 1d-features, that exists
in CGAL since version 3.8.edge_is_border_map has been removed, and the named parameter
edge_is_constrained_map now expects a property map with an edge
descriptor as key type (vs. halfedge descriptor before).CGAL_SMS_EDGE_PROFILE_ALWAYS_NEED_UNIQUE_VERTEX_IN_LINK will
restore the former behavior.reserve(size_t size) and size_t capacity()
to class Kd_tree to allocate memory to store size points and to
report that number (STL compliance).Compact_container::operator[], allowing a direct access to the
ith element of a compact container.Concurrent_compact_container, a compact container which allows
concurrent insertion and removal.Release date: April 2014
CGAL::Mpzf is introduced on some platforms for exact
ring operations. It is used to improve the speed of the evaluation
of predicates in degenerate situations.Exact_predicates_exact_constructions_kernel.CGAL::General_polygon_set_2.null_dart_handle is no longer a static data member in the
CombinatorialMap concept. This implies to move the following
methods of Dart concept into CombinatorialMap concept:
is_free, highest_nonfree_dimension, opposite and
other_extremity. We also transform the static methods
vertex_attribute and point of Linear_cell_complex class into
non static methods. You can define the CGAL_CMAP_DEPRECATED macro
to keep the old behavior.insert_constraints that
inserts a range of points and segments, or a range of segments.
These functions uses the spatial sorting in order to speed up the
time needed for the insertion.CGAL::Alpha_shape_3 to give access to the
alpha status of edges and facets (get_alpha_status()).filtration_with_alpha_values())
that reports the alpha value at which each face appears in the
filtration.number_of_facets and number_of_cells
in Mesh_complex_3_in_triangulation_3.Mesh_cell_base_3 to (re)compute
circumcenters and sliver criterion values only when needed.edge_is_constrained_map to the function
edge_collapseSearch_traits_adapter and
Distance_adapter must be a lvalue property map. To avoid incorrect
usage, a static assertion has been added in the CGAL code to prevent
the user from instantiating these classes with an incorrect property
map type.Release date: October 2013
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.boost::variant (from CGAL::Object). For convenience, the
previous behavior can be restored by defining the macro
CGAL_ARR_POINT_LOCATION_VERSION to 1.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.key_type of the property maps provided by CGAL used to be an
iterator. In order to be more easily reused, 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.make_rational() taking a pair
of numbers.Iso_rectangle_2 can now be constructed from a Bbox_2 and an
Iso_cuboid_3 from a Bbox_3.CGAL::Object has been updated and now uses
boost::shared_ptr and boost::any. This implementation is faster.Bbox_2 and Bbox_3 a += operator as well as free
functions to get the bounding box of a range of geometric objects.CMap_cell_iterator.Lazy_exact_nt as number type or
Exact_predicates_exact_constructions_kernel as kernel.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.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.Fast_location tag is usedinsert_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.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.Compact_mesh_cell_base_3 and
Mesh_vertex_base_3 are now our favored implementations of the
concepts MeshCellBase_3 and MeshVertexBase_3.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.cell_base/vertex_base
classes into the Mesh_triangulation_3 class.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.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.AABB_face_graph_triangle_primitive which
replaces the class AABB_polyhedron_triangle_primitive (which is
now deprecated).AABB_segment_primitive and
AABB_triangle_primitive that were already used in some examples.AABB_primitive that allows to define
a primitive type by defining only two property maps.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.AABB-treeDispatch_output_iterator and
Dispatch_or_drop_output_iterator an operator to accept and
dispatch a tuple of values.FindTBB CMake module so that one can easily link with TBB to
write shared-memory parallel code.Sequential_tag and Parallel_tagRelease date: March 2013
Additional supported platforms:
With Microsoft Visual C++ (all supported versions), the compiler
flags /bigobj and /wd4503 are added by CGAL CMake scripts.
This is the last release whose "UseCGAL.cmake" file (if using CGAL
in a CMake build environment) contains the line
link_libraries(${CGAL_LIBRARIES_DIR} ${CGAL_3RD_PARTY_LIBRARIES_DIRS})
as this is a deprecated CMake command. The correct way to link with
CGAL's libraries (as for required 3rd party libraries) is to use
'target_link_libraries' which specifies for each build target
which libraries should be linked. The following serves as example:
find_package(CGAL)
include(${CGAL_USE_FILE})
add_executable(myexe main.cpp)
target_link_libraries(myexe ${CGAL_LIBRARIES}
${CGAL_3RD_PARTY_LIBRARIES})
We also expect further changes in CGAL's CMake setup (change of
variable names, consistency of filename and output, removing
essential libraries, building executables, removal of
'${CGAL_3RD_PARTY_LIBRARIES}').
Delaunay_triangulation_2 and
Constrained_Delaunay_triangulation_2.Regular_triangulation_2 and
Delaunay_triangulation_2 from a range of points or a range of
points with info.ccb() method in face type as documented.AABBTraits and
AABBGeomTraits to match the implementation of the package.Combination_enumeratorCGAL::cpp11::result_of as an alias to the tr1
implementation from boost of the result_of mechanism. When all
compilers supported by CGAL will have a Standard compliant
implementation of the C++11 decltype feature, it will become an
alias to std::result_of.Release date: October 2012
CMakeLists.txt files:
cgal_create_CMakeListsconvex_hull_2 when forward iterators
are provided as input).result_of protocol.STL_Extensions for CGALcpp0x has been renamed cpp11. The old name is
still available for backward compatibility.Release date: Jul 2012
This is a bug fix release. It fixes a bug in the CMakeLists.txt for
CGAL-4.0.1, that prevented even building the libraries.
Release date: Jul 2012
This is a bug fix release. Apart various minor fixes in the documentation, the following has been changed since CGAL-4.0:
Segment_3-Triangle_3 intersection function in the
case the segment is collinear with a triangle edge.Projection_traits_.._3 class in the case a
segment was parallel to the x-axis.boost::any. This also influences the packages 2D
Boolean Operations on Nef Polygons, 3D Boolean Operations on Nef
Polyhedra, Convex Decomposition of Polyhedra, and 3D Minkowski Sum
of Polyhedra.<CGAL/Mesh_2/Do_not_refine_edges.h> when g++ version 4.7 is used.CGAL_ImageIO library, that could lead
to wrong result when meshing from a 3D image.demo/Surface_mesher, when Boost
version 1.48 or 1.49 is used.Eigen_solver_traits.
This fix also affects the usage of that class in the package
Surface Reconstruction from Point Sets.Release date: March 2012
CGAL 4.0 offers the following improvements and new functionality :
The whole CGAL-3.x series was released under a combination of LGPLv2 (for the foundations of CGAL), and QPL (for the high-level packages). QPL was the former license of the graphical toolkit Qt, but that license is not supported by any major free software project. Furthermore, the terms of the LGPLv2 license are ambiguous for a library of C++ templates, like CGAL.
The CGAL project, driven by the CGAL Editorial Board, has decided to change the license scheme of CGAL. We increased the major number of the CGAL version to '4' in order to reflect this license change. The CGAL-4.x series is released under:
Polyhedron_3.AABB_tree class.AABB_tree is now guaranteed to be read-only thread-safe.
As usual in CGAL, this small overhead introduced for thread-safety
can be deactivated by defining CGAL_HAS_NO_THREADS.Alpha_shape_2 that
allows a certified construction using a traits class with exact
predicates and inexact constructions.Alpha_shape_2 can now be constructed from a
triangulation.Alpha_shape_3 that
allows a certified construction using a traits class with exact
predicates and inexact constructions.Random_points_in_iso_box_d (deprecated since 3.8) has been
removed. Use Random_points_in_cube_d instead.Kd_tree is now guaranteed to be read-only thread-safe.
As usual in CGAL, this small overhead introduced for thread-safety
can be deactivated by defining CGAL_HAS_NO_THREADS.Orthogonal_incremental_neighbor_search and
Incremental_neighbor_search classes. Several calls to begin()
now allow to make several nearest neighbor search queries
independently.CGAL::copy_n is now deprecated for CGAL::cpp0x::copy_n which
uses std::copy_n, if available on the platform.CGAL::successor and CGAL::predecessor are now deprecated for
CGAL::cpp0x::next and CGAL::cpp0x::prev. These functions use the
standard versions if available on the platform. Otherwise,
boost::next and boost::prior are used.Triangulation_2Delaunay_triangulation_2 remove
functions. As usual in CGAL, the small overhead introduced for
thread-safety can be deactivated by defining CGAL_HAS_NO_THREADS.Constrained_triangulation_2
(and thus to all inheriting classes).Release date: September 2011
CGAL 3.9 offers the following improvements and new functionality :
Root_of_2 is now deprecated. It is recommended to use
the class Sqrt_extension instead.Sqrt_extension is now used everywhere in CGAL where an
algebraic number of degree 2 is needed. This change has been done in
the Root_of_traits mechanism (indirectly packages 2D Circular
kernel and 3D Spherical kernel) and the packages 2D Segment Delaunay
Graphs and 2D Arrangements.CGAL::convex_hull_3) has
been worked out to provide very better performances.CGAL::convex_hull_3 no longer computes the plane
equations of the facets of the output polyhedron. However an example
is provided to show how to compute them easily.convex_hull_3_to_polyhedron_3 is now provided to
extract the convex hull of a 3D points set from a triangulation of
these points.RangeSearchTraits and SearchTraits). Most
other changes concerns only classes documented as advanced. One
issue that user can encounter is due to an additional requirement on
the nested class Construct_cartesian_const_iterator_d defined in
the concept SearchTraits that must provide a nested type
result_type.Less_coordinate_d and
Point_dimension_d.A new geometry-traits class that handles rational arcs, namely
Arr_rational_function_traits_2, has been introduced. It replaced
an old traits class, which handled the same family of curves, but it
was less efficient. The new traits exploits CGAL algebraic kernels
and polynomials, which were not available at the time the old traits
class was developed.
A new geometry traits concept called
ArrangementOpenBoundaryTraits_2 has been introduced. A model of
this concept supports curves that approach the open boundary of an
iso-rectangular area called parameter space, which can be unbounded
or bounded. The general code of the package, however, supports only
the unbounded parameter space. We intend to enhance the general code
to support also bounded parameter spaces in a future release.
The deprecated member function is_at_infinity() of
Arrangement_2::Vertex has been removed. It has been previously
replaced new function is_at_open_boundary().
The tags in the geometry traits that indicate the type of boundary of the embedding surface were replaced by the following new tags:
Left_side_category
Bottom_side_category
Top_side_category
Right_side_category
It is still possible not to indicate the tags at all. Default values are assumed. This however will produce warning messages, and should be avoided.
Release date: April 2011
CGAL 3.8 offers the following improvements and new functionality :
mirror_edge taking an edge as parameter.vertices_in_conflict is renamed
vertices_on_conflict_zone_boundary for Delaunay and regular
triangulation. Function vertices_inside_conflict_zone is added to
regular triangulation.Fixed_alpha_shape_3 provides a robust and faster
way to compute one alpha shape (with a fixed value of alpha).Projection_traits_xy_3,
Projection_traits_yz_3,Projection_traits_yz_3) are provided to
work with triangulations, algorithms on polygons, alpha-shapes,
convex hull algorithm... Usage of former equivalent traits classes
in different packages is now deprecated.Exact_predicates_exact_constructions_kernel now better use the
static filters which leads to performance improvements.Has_filtered_predicates is now deprecated. It is now required to
use Has_filtered_predicates_tag (being either Tag_true or
Tag_false).Compare_distance_2 and Compare_distance_3 provide additional
operators for 3 and 4 elements.Ray_3 and either an object of type
Line_3, Segment_3 or Ray_3.Bbox_3 and an object of type Plane_3 or Triangle_3 by avoiding
arithmetic filter failures.Env_default_diagram_1 is deprecated, Envelope_diagram_1 should
be used instead.L1_Voronoi_diagram_2 has been
introduced. It demonstrates how 2D Voronoi diagrams of points under
the L1 metric are constructed using lower envelopes.Compute_coordinate_d to Kernel_d concept.CGAL::Random uses boost::rand48 instead of std::rand.CGAL::Random a way to generate random integers.Algebraic_structure_traits now provides an Inverse functor for
Fields. There is also a new global function inverse.insert_at_vertices of the Arrangement_2
class.Arr_Bezier_curve_traits_2
for arrangement of Bezier curves.Release date: October 2010
CGAL 3.7 offers the following improvements and new functionality :
Nef_3), "Convex Decomposition of
Polyhedra" (Convex_decomposition_3), and "3D Minkowski Sum of
Polyhedra" (Minkowski_sum_3) are known to still fail to
compile with that compiler flag.CGAL_PDB is no longer provided with CGAL. An alternative solution
for people interested in reading PDB files is to use ESBTL
(https://esbtl.sourceforge.net/).Algebraic_kernel_d_1 and Algebraic_kernel_d_2 for
the corresponding concepts. They provide generic support for various
coefficient typesArr_algebraic_segment_traits_2 of
ArrangementTraits_2 that supports algebraic curves of arbitrary
degree in the planestd::ptrdiff_t.Triangulation_euclidean_traits_xy_3,
Triangulation_euclidean_traits_yz_3 and
Triangulation_euclidean_traits_xz_3 are now model of the concept
ConstrainedTriangulationTraits_2. They can be used with and without
intersection of constraints.move_if_no_collision. The methods are also available for the
hierarchy (Triangulation_hierarchy_2).std::ptrdiff_t.move_if_no_collision. This
works in both Compact_policy and Fast_policy.std::size_t so that
CGAL can deal with large data sets (64 bit addresses).CGAL_MESH_3_USE_OLD_SURFACE_RESTRICTED_DELAUNAY_UPDATE
switches back to the old behavior.std::size_t so that
CGAL can deal with large data sets (64 bit addresses).Release date: June 2010
This is a bug fix release. The following has been changed since CGAL-3.6:
qglobal.h of Qt4 on MacOS X,texture.cpp, if TAUCS is used,WITH_demos=ONis_in_domain()
of the Face type.<CGAL/refine_mesh_3.h> is included in different compilation units.<CGAL/Orthogonal_k_neighbor_search.h> when several
nearest neighbors are at the same distance from the query point.<CGAL/IO/VRML_2_ostream.h> that generated VRML 2
files with an invalid syntax for IndexedFaceSet nodes.Triangulation_2Compare_distance_2 functor in trait classes
Triangulation_euclidean_traits_xy_3
Triangulation_euclidean_traits_yz_3 and
Triangulation_euclidean_traits_xz_3. This was preventing calling
member function nearest_vertex of Delaunay_triangulation_2
instantiated with one of these traits.Release date: March 2010
CGAL 3.6 offers the following improvements and new functionality :
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)General_polygon_set_2::arrangement() to return the proper
type of object.Arrangement_2.Arrangement_2::fictitious_face(), which returns the
fictitious face in case of an unbounded arrangement.number_of_holes(), holes_begin(), and
holes_end() to the default DCEL for backward compatibility.overlay() function. It employs
the default overlay-traits, which practically does nothing.qglobal.h of Qt4 on MacOS X,texture.cpp, if TAUCS is used,WITH_demos=ONtest_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.Weighted_point now has a constructor from Cartesian coordinates.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.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.remove() (enabled with
CGAL_DELAUNAY_3_OLD_REMOVE) has been deleted.Weighted_alpha_shape_euclidean_traits_3 is
deprecated, the class Regular_triangulation_euclidean_traits_3
must be used instead.Constrained_triangulation_plus_2).Release date: December 2009
This is a bug fix release.
do_intersect(Bbox_3, Bbox_3).do_intersect(Bbox_3, Ray_3) when using
the parameters in this order.Release date: October 2009
CGAL releases will now be published about every six months. As a transition release, CGAL-3.5 has been developed during 9 months from the release CGAL-3.4.
Version 3.5 differs from version 3.4 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
-D_SECURE_SCL=0 is not longer use in Debug mode).is_at_infinity() of Arrangement_2::Vertex was
replaced by the new function is_at_open_boundary(). The former is
deprecated. While still supported in version 3.5, It will not be
supported in future releases. The member functions
boundary_type_in_x() and boundary_type_in_y() were permanently
replaced by the functions parameter_space_in_x() and
parameter_space_in_y(), respectively. The 2 new functions return
an enumeration of a new type, namely Arr_parameter_space.Arr_left_side_tag Arr_bottom_side_tag Arr_top_side_tag
Arr_right_side_tag In addition, the code was change, and now it
is possible not to indicate the tags at all. Default values are
assumed. This however will produce warning messages, and should be
avoided.link_condition testCGAL_ipelets (new package)Release date: January 2009
Version 3.4 differs from version 3.3.1 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
CGAL_NO_DEPRECATED_CODE can be defined to disable
deprecated code, helping users discover if they rely on code that
may be removed in subsequent releases.<CGAL/assertions_behaviour.h>.CGAL::Qt_Widget will be deprecated.install_cgal has been replaced by CMake.Polynomial_d, a concept for
multivariate polynomials in d variables.Interval_nt::number_of_failures() has been removed,
replaced by a profiling counter enabled with CGAL_PROFILE.CORE/Expr.h; as a consequence, the arrangement demo
works properly when handling arrangements of conics, for example,
when defining an arc with 5 points.object_cast() function instead of
assign() to extract an object from a CGAL::Object, for efficiency
reasons.Construct_supporting_line_2
and Construct_supporting_line_3 have been removed.Ambiant_dimension and Feature_dimension have been added to
retrieve the potentially compile-time dimension of a space or of an
object.barycenter() functions have been added.Circle_3 as well as predicates and
constructions have been added to the kernelintersection/do_intersect between Line_3 and Line_3
has been added as well.Cell::mirror_index() and
Cell::mirror_vertex().bind_*,
compose, compose_shared, swap_*, negate, along with the helper
functions set_arity_* and Arity class and Arity_tag typedefs)
which were provided by <CGAL/functional.h> have been removed.
Please use the better boost::bind mechanism instead. The concept
AdaptableFunctor has been changed accordingly such that only a
nested result_type is required.Twotuple, Threetuple, Fourtuple and Sixtuple
are also deprecated (use CGAL::array instead).CGAL::Triple and CGAL::Quadruple are in the process of being
replaced by boost::tuple. As a first step, we strongly recommend
that you replace the direct access to the data members (.first,
.second, .third, .fourth), by the get<i>() member function;
and replace the make_triple and make_quadruple maker functions by
make_tuple.
This way, in a further release, we will be able to switch to
boost::tuple more easily.CGAL::Uncertain<> has been documented. It is
typically used to report uncertain results for predicates using
interval arithmetic, and other filtering techniques.Arrangement_2 to
Arrangement_on_surface_2 to reflect the potential capabilities of
the package to construct and maintain arrangements induced by curves
embedded on two dimensional surfaces in three space. Most of these
capabilities will become available only in future releases though.Boundary_category' tag.Arr_polyline_traits_2.h, where the operator that
compares two curves failed to evaluate the correct result (true)
when the curves are different, but their graphs are identical.IO/Arr_postscript_file_stream.h and
IO/Polyline_2_postscript_file_stream.h, as they depend on
obsolete features and LEDA.CGAL::insert_curve(), CGAL::insert_curves(),
CGAL::insert_x_monotone_curve(), and
CGAL::insert_x_monotone_curves() with a single overloaded
function CGAL::insert(). The former 4 functions are now deprecated,
and may no longer be supported in future releases.connect_holes() that caused failures when connecting
holes touching the outer boundary.GeneralPolygonSetTraits_2. Introduced two new
concepts GpsTraitsGeneralPolygon_2 and
GpsTraitsGeneralPolygonWithHoles_2. Fixed the definition of the two
nested required types Polygon_2 and Polygon_with_holes_2 of the
GeneralPolygonSetTraits_2 concept. They must model now the two new
concepts above.General_polygon_set_2' to
allow users to pass their specialized DCEL used to instantiate the
underlying arrangement.Polygon_with_holes_2 (and not just of a Polygon_2).Release date: August 2007
This is a bug fix release.
install_cgal.Memory_sizer when using more than 4GB of memory
(64bit).MP_Float constructor from double for some particular
values.to_double(Lazy_exact_nt) sometimes returning NaN.Circular_kernel_2::Has_on_2Bbox_3 compared to Bbox_2.Arrangement_2 package in dual arrangement
representation for Boost graphs when reporting all halfedges of a
face.Arrangement_2 in walk along a line point location for
unbounded curves.Arrangement_2.Arrangement_2 class when inserting an unbounded curve
from an existing vertex.Arr_conic_traits_2 of the Arrangement package, meaning a line
segment which is part of a degenerate parabola/hyperbola.Polygon_2::is_convex() for equal
points.Regular_triangulation_2.circumcenter() function in the default Cell type parameter
Triangulation_ds_cell_base_3, so that the .dual() member
function of Delaunay still work as before, without requiring the
explicit use of Triangulation_cell_base.operator->() to Facet_circulator.Nef_polyhedron_3 from off-file. Now,
always the inner volume is selected.Nef_polyhedron_3 to Polyhedron_3.
Polyhedron_3 was not cleared at the beginning.Nef_polyhedron_3 in update of indexes for
construction of external structure.Release date: May 2007
Version 3.3 differs from version 3.2.1 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
Additional supported platforms
The following platforms are no longer supported:
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.
Fixed_precision_nt and Filtered_exact number types have been
removed.Filtered_bbox_circular_kernel_2<.>, and also chosen for
the predefined kernel Exact_circular_kernel_2.Exact_predicates_exact_constructions_kernel memory and run-time
improvements through usage of lazy geometric constructions instead
of lazy arithmetic.decompose() that produces the
symbolic vertical decomposition of a given arrangement,
performing a batched vertical ray-shooting query from all
arrangement vertices.General_polygon_set_2 and Polygon_set_2 classes. This
allows users to extend the DCEL of the underlying arrangement.connect_holes() that connects
the holes in a given polygon with holes, turning it into a
sequence of points, where the holes are connected to the outer
boundary using zero-width passages.General_polygon_set_2
that obtains the underlying arrangement.Polytope_distance_d: has support for homogeneous points;
bugfix in fast exact version.Min_annulus_d has support for homogeneous points; bugfix in
fast exact version.Release date: July 2006
This is a bug fix release
MP_Float constructor which crashed for some values.Arr_segment_traits_2 Arrangement_2 traits class from
the parameterized Kernel. This allows the use of this traits class
in an extended range of applications that require kernel objects and
operations on these objects beyond the ones required by the
Arrangement_2 class itself.filter_iterator with CGAL:: to avoid overload
ambiguities with Boost's filter_iterator.Surface_mesh_complex_2_in_triangulation_3operator! and operator int()Active_objects_vectorRelease date: May 2006
Version 3.2 differs from version 3.1 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
The following platforms are no longer supported:
For Visual C++ the installation scripts choose the multi-threaded
dynamically linked runtime (/MD). Before it was the single-threaded
static runtime (/ML).
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 information 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 behavior. 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 address 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 Optimization.
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 Optimization (major revision) The underlying QP solver which is the foundation for several algorithms in the Geometric Optimization chapter has been completely rewritten.
3D Triangulation (new functionality)
Regular_triangulation_3 now offers vertex removal.
Release date: December 2004
Version 3.1 differs from version 3.0 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
Additional supported platforms:
The following platforms are no longer supported:
The following functionality has been added or changed:
Nef_polyhedron_3) representing 3D Nef polyhedra, a
boundary representation for cell-complexes bounded by halfspaces
that supports boolean operations and topological operations in full
generality including unbounded cells, mixed dimensional cells (e.g.,
isolated vertices and antennas). Nef polyhedra distinguish between
open and closed sets and can represent non-manifold geometry.Nef_polyhedron_S2) designed and supported mainly to
represent sphere neighborhoods around vertices of the three-
dimensional Nef polyhedra.Box_intersection_d (new package)
A new efficient algorithm for finding all intersecting pairs for
large numbers of iso-oriented boxes, i.e., typically these will be
bounding boxes of more complicated geometries. Useful for (self-)
intersection tests of surfaces etc.Triangulation_3: added operator==(), removed push_back() and
copy_triangulation().Delaunay_3 : added nearest_vertex(), move_point(),
vertices_in_conflict().Regular_3 : added filtered traits class, and
nearest_power_vertex().Planar_map and Arrangement_2
nearest_intersection_to_right() and
nearest_intersection_to_left() return an object of type
CGAL::Object that represents either an empty intersection, a
point, or an overlapping subcurve.Planar_map as follows:Has_left_category -
indicates whether the functions
curves_compare_y_at_x_left() and
nearest_intersection_to_left() are implemented in the traits
model. Has_reflect_category - indicates whether the
functions point_reflect_in_x_and_y() and
curve_reflect_in_x_and_y() are implemented in the traits
model. They can be used as an alternative to the two function in
the previous item.Segment_cached_2 type that represents
a segment in the Arr_segment_cached_traits_2 traits class
was introduced. The new constructor accepts the segment
endpoints as well as the coefficients of the underlying line.rootOf() operator to compute the intersection points in the
arrangement, making its code much simpler and more elegant than
the previous version. In addition, new constructors for conic
arcs are provided. The new traits class usually performs about
30% faster than the version included in CGAL 3.0Arr_polyline_traits_2, was rewritten. The new
class is parametrized with a traits class that handles segments,
say Segment_traits. The polyline curve defined within the
Arr_polyline_traits_2 class is implemented as a vector of
segments of type Segment_traits::Curve_2.Arr_curve_data_traits_2, that
extends the curve type of the planar-map with arbitrary
additional data was introduced. It should be instantiated with a
regular traits-class and a class that contains all extraneous
data associated with a curve.Pm_trapezoid_ric_point_location.Triangulation_2
Alpha_shapes_3
Alpha_shapes_3.Min_ellipse_2
is_circle() methodMin_sphere_of_spheres_d:
Min_sphere_of_spheres_d_traits_2<K,FT,UseSqrt,Algorithm>,
Min_sphere_of_spheres_d_traits_3<K,FT,UseSqrt,Algorithm>, and
Min_sphere_of_spheres_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>
of concept MinSphereOfSpheresTraits now represent a sphere as
a std::pair<Point,Radius> (and not any more as a
CGAL::Weighted_point<Point,Weight>)Polyhedron_3
vertex_degree,
facet_degree, edge_flip, and is_closed.Release date: February 2004
This is a bug-fix release. No new features have been added in 3.0.1. Here is the list of bug-fixes.
Planar_mapLine_face_circulator_2.h:
Fixed changes made to support handles with a typedef to iterator.
The fix concerns operator== and !=.Alpha_shapes_3Lazy_exact_nt:
to_double() (by default 1e-5). This should fix reports that
some circumcenters computations have poor coordinates, e.g.
nan).to_interval(Quotient<MP_Float>): avoid spurious overflows.intersection() documentation.Release date: October 2003
Version 3.0 differs from version 2.4 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
The license has been changed to either the LGPL (GNU Lesser General Public License v2.1) or the QPL (Q Public License v1.0) depending on each package. So CGAL remains free of use for you, if your usage meets the criteria of these licenses, otherwise, a commercial license has to be purchased from GeometryFactory.
Additional supported platforms:
The following platforms are no longer supported:
The following functionality has been added or changed:
Exact_predicates_inexact_constructions_kernelExact_predicates_exact_constructions_kernelExact_predicates_exact_constructions_kernel_with_sqrtTriangle_3 intersection test routines.
(see Erratum)2D Apollonius Graph (new package) Algorithms for computing the Apollonius graph in two dimensions. The Apollonius graph is the dual of the Apollonius diagram, also known as the additively weighted Voronoi diagram. The latter can be thought of as the Voronoi diagram of a set of circles under the Euclidean metric, and it is a generalization of the standard Voronoi diagram for points. The algorithms provided are dynamic.
dD Min Sphere of Spheres (new package) Algorithms to compute the smallest enclosing sphere of a given set of spheres in R<sup>d</sup>. The package provides an algorithm with maximal expected running time O(2<sup>O(d)</sup> n) and a fast and robust heuristic (for dimension less than 30).
Spatial Searching (new package) Provides exact and approximate distance browsing in a set of points in d-dimensional space using implementations of algorithms supporting:
Kd-tree this package is deprecated, its documentation is removed. It is replaced by the Spatial Searching package.
Largest_empty_rectangle_2
Given a set of points P in the plane, the class
Largest_empty_iso_rectangle_2 is a data structure that maintains
an iso-rectangle with the largest area among all iso-rectangles that
are inside a given iso-rectangle bounding box, and that do not
contain any point of the point set P.
2D Triangulation and 3D Triangulation
Triangulation_data_structure_2 (and 3), which
implements the data structure for 2D triangulation class, now
makes use of CGAL::Compact_container (see Support Library
section below).Face_handle or Vertex_handle.Triangulation_vertex_base_with_info_2 (and 3)
and Triangulation_face_base_with_info_2 (and 3) to make
easier the customization of base classes in most cases.2D Triangulation
Triangulation_hierarchy_2, which provide an efficient
location data structure, can now be used with any 2D
triangulation class plugged in (including Regular
triangulations).3D Triangulation
Delaunay_triangulation_3.Delaunay_triangulation_3 is now independent of the order of
insertions of the points (in case of degenerate cosphericity).Regular_triangulation_3 now hides vertices (and updates
itself) when inserting a coinciding point with greater weight.
This required a new predicate.copy_triangulation(), push_back(),
set_number_of_vertices().Triangulation_3 now gives non-const access to the data
structure.Interval Skip List (new package) An interval skip list is a data structure for finding all intervals that contain a point, and for stabbing queries, that is for answering the question whether a given point is contained in an interval or not.
Planar Maps and Arrangements The changes concern mainly the traits classes.
New traits hierarchy and interface: The set of requirements was
made sound and complete. A couple of requirements were
eliminated, few others were redefined, and some were renamed. A
hierarchy of three traits classes for the Planar_map_2,
Planar_map_with_intersections_2, and Arrangement_2 types
was established to include only the necessary requirements at
each level. It was determined that for the aggregate insertion-
operation based on a sweep-line algorithm only a subset of the
requirements is needed. Preconditions were added where
appropriate to tighten the requirements further.
The following functions have been renamed:
point_is_same() renamed to point_equal()curve_is_same() renamed to curve_equal()curve_is_in_x_range() renamed to point_in_x_range()curve_compare_at_x() renamed to
curves_compare_y_at_x() Furthermore, a precondition has
been added that the reference point is in the x-range of
both curves.curve_compare_at_x_right() renamed to
curves_compare_y_at_x_to_right(). Furthermore, a
precondition has been added that both curves are equal at
the reference point and defined to its right.curve_compare_at_x_left() renamed to
curves_compare_y_at_x_to_left(). Furthermore, a
precondition has been added that both curves are equal at
the reference point and defined to its right.curve_get_point_status() renamed to
curve_compare_y_at_x(). Furthermore, a precondition has
been added that the point is in the x-range of the curve.
Consequently, the function now returns a Comparison_result
(instead of a special enum).make_x_monotone() renamed to curve_make_x_monotone()
See more details below.curve_flip() renamed to curve_opposite()The following functions have been removed:
curve_is_between_cw()point_to_left()point_to_right()is_x_monotone()point_reflect_in_x_and_y()curve_reflect_in_x_and_y()do_intersect_to_right()do_intersect_to_left()Most functions, are required by the PlanarMapTraits_2 concept,
except for the make_x_monotone(),
nearest_intersection_to_right(),
nearest_intersection_to_left(), curves_overlap() and
curve_opposite(). PlanarMapWithIntersectionsTraits_2 requires
all these functions, except curve_opposite(), needed only by
the ArrangementTraits_2 concept.
Furthermore, the two functions curve_compare_at_x_left() and
nearest_intersection_to_left() can be omitted, if the two
functions point_reflect_in_x() and curve_reflect_in_x()
are implemented. Reflection can be avoided, if the two _left
functions are supplied.
The type X_curve_2 of the PlanarMapWithIntersectionsTraits_2
concept was renamed to X_monotone_curve_2, and the
distinction between this type and the Curve_2 type was made
firm. The method is_x_monotone() of the
PlanarMapWithIntersectionsTraits_2 concept was removed. The
related method curve_make_x_monotone() is now called for each
input curve of type Curve_2 when curves are inserted into a
Planar_map_with_intersections_2 to subdivide the input curve
into x-monotone sub-curves (and in case the curve is already
x-monotone, this function is responsible for casting it to an
x-monotone curve).
New and improved traits classes:
Conic traits - Arr_conic_traits_2 Support finite segments of
ellipses, hyperbolas and parabolas, as well as line segments.
The traits require an exact real number- type, such as
leda_real or CORE::Expr.
Segment cached traits - Arr_segment_cached_traits_2 This
class uses an improved representation for segments that helps
avoiding cascaded computations, thus achieving faster running
times. To work properly, an exact rational number-type should be
used.
Polyline traits - Arr_polyline_traits_2 The polyline traits
class has been reimplemented to work in a more efficient,
generic manner. The new class replaces the obsolete
Arr_polyline_traits class. It is parameterized with a segment
traits class.
Hyperbola and segment traits - Arr_hyper_segment_traits_2
Supports line segments and segments of canonical hyperbolas.
This is the type of curves that arise when projecting segments
in three-space rotationally around a line onto a plane
containing the line. Such projections are often useful in
CAD/CAM problems.
Removed old traits class:
The models of the PlanarMapWithIntersectionsTraits_2
concept below became obsolete, as the new conic traits,
namely Arr_conic_traits_2, supports the same
functionality and is much more efficient.
Arr_circles_real_traitsArr_segment_circle_traitsThe segment traits class and the new polyline traits class were reimplemented using standard CGAL-kernel calls. This essentially eliminated the corresponding leda traits classes, namely:
Pm_leda_segment_traits_2Arr_leda_segment_traits_2Arr_leda_polyline_traitsWith the use of the Leda_rat_kernel new external package
the same functionality can be achieved with less overhead
and more efficiency.
Sweep Line
Sweep_line_2 package was reimplemented. As a
consequence it is much more efficient, its traits is tighter
(namely neither the two _left nor the reflection functions
are required), and its interface has changed a bit.
The following global functions have been removed:
sweep_to_produce_subcurves_2()sweep_to_produce_points_2()sweep_to_construct_planar_map_2()Instead, the public methods of the Sweep_line_2 class
listed below were introduced:
get_subcurves() - Given a container of curves, this
function returns a list of curves that are created
by intersecting the input curves.get_intersection_points() - Given a range of
curves, this function returns a list of points that
are the intersection points of the curves.get_intersecting_curves() - Given a range of
curves, this function returns an iterator to the
beginning of a range that contains the list of
curves for each intersection point between any two
curves in the specified range.It is possible to construct a planar map with intersections (or an arrangement) by inserting a range of curves into an empty map. This will invoke the sweep-line process to construct the map more efficiently.
Planar_map_with_intersections_2 class. The
Planar_map_with_intersections_2 class maintains a planar
map of input curves that possibly intersect each other and
are not necessarily x-monotone. If an input curve, or a set
of input curves, are known to be x-monotone and pairwise
disjoint, the new functions below can be used to insert them
into the map efficiently.Polyhedral Surface
Polyhedron_incremental_builder_3:
ABSOLUTE to ABSOLUTE_INDEXING, and
RELATIVE to RELATIVE_INDEXING to avoid conflicts with
similarly named macros of another library.add_vertex(), begin_facet(),
and end_facet() to return useful handles.test_facet() to check facets for validity before
adding them.vertex( size_t i) to return Vertex_handle for
index i.Halfedge Data Structure
Compact_container, which (roughly) provides the
flexibility of std::list, with the memory compactness of
std::vector.Geomview_stream: added a function gv.draw_triangles(InputIterator begin, InputIterator end)
which draws a set of triangles much more quickly than one by one.std::pair<double, double> to_interval(const NT &).square() for MP_Float.Gmp_q.Qt_widget:
Qt_help_window: provides a simple way to show some helpful
information about a demo as an HTML page.Qt_widget_history: provides basic functionality to
manipulate intervals of Qt_widget class. The current
visible area of Qt_widget is mapped to an interval. Each
interval could be stored in the Qt_widget_history object.
So you can use this object to navigate in history. It is
mostly used by Qt_widget_standard_toolbar.Qt_widget_standard_toolbar: is derived from QToolBar
class, so pay attention to modify your code, if you used
this class. Some public methods were introduced to control
the history object that the toolbar use to navigate.Qt_widget:
add_to_history(), clear_history(), back(), forth(): use
forward(), back() and clear_history() of the
Qt_widget_standard_toolbar instead.custom_redraw(): use redraw_on_back() and
redraw_on_front() instead.CGAL::Segment_2 (now tests for intersection with the
drawing area)CGAL::Triangle_2 (now tests for intersection with the
drawing area)CGAL::Triangulation_2 (is optimized for faster display on
zooming)Intersection test routines
The documentation of CGAL::do_intersect should mention, for the 3D
case:
Also, in three-dimensional space Type1 can be
either Plane_3<Kernel>
or Triangle_3<Kernel>
and Type2 any of
Plane_3<Kernel>
Line_3<Kernel>
Ray_3<Kernel>
Segment_3<Kernel>
Triangle_3<Kernel>
In the same way, for Kernel::DoIntersect_3:
for all pairs Type1 and Type2, where the type Type1 is
either Kernel::Plane_3
or Kernel::Triangle_3
and Type2 can be any of the following:
Kernel::Plane_3
Kernel::Line_3
Kernel::Ray_3
Kernel::Segment_3
Kernel::Triangle_3
Philippe Guigue (INRIA Sophia-Antipolis) should be mentioned as one of the authors.
Release date: May 2002
Version 2.4 differs from version 2.3 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
Additional supported platforms:
The following functionality has been added or changed:
Point_d has been removed from the 2D and 3D kernels. This type is
now available from the d-dimensional kernel only.2D Polygon Partitioning Traits requirements for optimal partitioning have been changed slightly.
2D Sweep line A new package that implements a sweep-line algorithm to compute arrangements of curves for different families of curves, which are not necessarily line segments (e.g., it also works for circular arcs). The resulting output can be the list of vertex points, the resulting subcurves or a planar map.
Planar Maps and Arrangements
Planar_map_2 for cases
where more precomputed information is available regarding the
position of the inserted curve in the map.Polyhedral Surface
Polyhedron_incremental_builder:
absolute indexing allows one to add new surfaces to existing
ones.2D Triangulation
Constrained_triangulation_plus offers a
constrained hierarchy on top of a constrained triangulations.
This additional data structure describes the subdivision of the
original constraints into edges of the triangulations.3D Triangulation
Triangulation_3<GT,Tds>::triangle() returns a
triangle oriented towards the outside of the cell c for
facet (c,i)insert(Point, Locate_type, Cell_handle, int, int) which avoids the location step.find_conflicts() and
insert_in_hole()TDS::delete_cells(begin, end).degree(v), reorient(),
remove_decrease_dimension(), remove_from_simplex().Vertex_handle (resp
Cell_handle) instead of Vertex* (resp Cell*).incident_cells() and incident_vertices() are templated by
output iterators->handle() anymore.Vertex_iterator split into All_vertices_iterator and
Finite_vertices_iterator (and similar for cells...).operator->.2D Search structures Additional range search operations taking a predicate functor have been added
Qt_widget
Qt_widgetTimer Fixed Timer class (for user process time) to have no wrap-around anymore on Posix-compliant systems.
The following functionality is no longer supported:
Bugs in the following packages have been fixed: 3D Convex hull, 2D Polygon partition, simple polygon generator
Also attempts have been made to assure compatibility with the upcoming LEDA release that introduces the leda namespace.
Arr_segment_circle_traits_2) traits does not compile for
either of the above packages.Release date: August 2001
Version 2.3 differs from version 2.2 in the platforms that are supported and in functionality.
Additional supported platform:
The following functionality has been added:
Simple_homogeneous is available. It is
equivalent to Homogeneous but without reference-counted objects.Filtered_kernel is available that allows one
to build kernel traits classes that use exact and efficient
predicates.Cartesian_converter and
Homogeneous_converter that allows one to convert objects between
different Cartesian and homogeneous kernels, respectively.Kernel_d is available. It provides
diverse kernel objects, predicates and constructions in d dimensions
with two representations based on the kernel families Cartesean_d
and Homogeneous_dAlmost all packages in the basic library have been adapted to the new kernel design to realize the flexibility this design makes possible. In several packages, this means that the traits class requirements have changed to conform to the function objects offered in the kernels so the kernels themselves can be used as traits classes in many instances.
2D Convex Hull The traits requirements have changed slightly to bring them in line with the CGAL kernels.
3D Convex Hull
convex_hull_3 now uses a new implementation of
the quickhull algorithm and no longer requires LEDA.convex_hull_incremental_3 function based on the new
d-dimensional convex hull class is available for comparison
purposes.Convex_hull_d, Delaunay_d
Two new application classes offering the calculation of
d-dimensional convex hulls and delaunay triangulations
Polygons and Polygon Operations
Planar Nef Polyhedra
A new class (Nef_polyhedron_2) representing planar Nef polyhedra =
rectilinearly bounded points sets that are the result of binary and
topological operations starting from halfplanes.
A new package offering functions to partition planar polygons into convex and y-monotone pieces is available.
Planar Maps and Arrangements
Planar_map_with_intersections_2<Planar_map> for
planar maps of possibly intersecting, possibly non-x-monotone,
possibly overlapping curves (like Arrangement_2 but without
the hierarchy tree).Arr_segment_circle_traits<NT>).Arr_leda_polylines_traits). The LEDA traits
for segments was also made faster.Pm_simple_point_location<Planar_map>).Halfedge Data Structure
The halfedge data structure has been completely revised. The new design is more in line with the STL naming scheme and it provides a safe and coherent type system throughout the whole design (no void* pointers anymore), which allows for better extendibility. A user can add new incidences in the mesh easily. The new design also uses standard allocators with a new template parameter that has a suitable default.
The old design is still available, but its use is deprecated, see
the manual of deprecated packages for its documentation. Reported
bugs in copying the halfedge data structure (and therefore also
polyhedral surfaces) have been fixed in both designs. Copying a
list-based representation is now based on hash maps instead of
std::map and is therefore considerably faster.
Polyhedral Surface
The polyhedral surface has been rewritten to work with the new
halfedge data structure design. The user level interface of the
CGAL::Polyhedron_3 class is almost backwards compatible with the
previous class. The exceptions are the template parameter list,
everything that relies on the flexibility of the underlying halfedge
data structure, such as a self-written facet class, and that the
distinction between supported normals and supported planes has been
removed. Only planes are supported. See the manuals for suggestions
how to handle normals instead of planes.
More example programs are provided with polyhedral surfaces, for example, one about Euler operator and one computing a subdivision surface given a control mesh as input.
The old design is still available for backwards compatibility and to
support older compiler, such as MSVC++6.0. For the polyhedral
surface, old and new design cannot be used simultaneously (they have
identical include file names and class names). The include files
select automatically the old design for MSVC++6.0 and the new design
otherwise. This automatism can be overwritten by defining
appropriate macros before the include files. The old design is
selected with the CGAL_USE_POLYHEDRON_DESIGN_ONE macro. The new
design is selected with the CGAL_USE_POLYHEDRON_DESIGN_TWO
macro.
2D Triangulation
find_conflicts()"
member functions in Delaunay and constrained Delaunay
triangulation.insert() member function,
insertion of points in those triangulation can be performed
using the combination of find_conflicts() and star_hole()
which eventually allows the user to keep track of deleted
faces.3D Triangulation
Triangulation_hierarchy_3 that allows a faster
point location, and thus construction of the Delaunay
triangulationTriangulation_data_structure have a new
interfaceA new class (Alpha_shapes_3) that computes Alpha shapes of point
sets in 3D is available.
The traits requirements for matrix search and minimum quadrilaterals have been changed to bring them in line with the CGAL kernels.
Point_set_2
Lazy_exact_nt<NT> is a new number type wrapper to speed up
exact number types.MP_Float is a new multiprecision floating point number type.
It can do exact additions, subtractions and multiplications over
floating point values.In_place_list has a new third template parameter (with a suitable
default) for an STL-compliant allocator.Unique_hash_map is a new support class.Union_find is a new support class.Geomview_stream :
~/.geomview file anymore.Ray_2, Line_2, Ray_3, Line_3,
Sphere_3.Release date: October 2000
Version 2.2 differs from version 2.1 in the platforms that are supported and in functionality.
Additional supported platforms:
The following functionality has been added:
Simple_cartesian.
Because reference counting is not used, and thus coordinates are
stored within a class, debugging is easier using this kernel. This
kernel can also be faster in some cases than the reference-counted
Cartesian kernel.Min_annulus_d - Algorithm for computing the smallest enclosing
annulus of points in arbitrary dimensionPolytope_distance_d - Algorithm for computing the (squared)
distance between two convex polytopes in arbitrary dimensionWidth_3 - Algorithm for computing the (squared) width of points
sets in three dimensionsThe following functionality has been removed:
Release date: January 2000
Version 2.1 differs from version 2.0 in the platforms that are supported and in functionality.
Supported platforms:
Support for the old g++ compiler (2.8) and for mips CC 7.2 has been dropped.
The following functionality has been added:
Min_quadrilateral optimizations have been added. These are
algorithms to compute the minimum enclosing rectangle/parallelogram
(arbitrary orientation) and the minimum enclosing strip of a convex
point set.Point_set is a package for 2d range search operations, Delaunay
triangulation, nearest neighbor queries. This package works only if
LEDA is installed.Release date: June 1999
The main difference from release 1.2 is the introduction of namespaces
-- namespace std for code from the standard library and namespace
CGAL for the CGAL library.
Release date: January 1999
Additions to release 1.1 include:
Release date: July 1998
Additions to release 1.0 include:
Release date: April 1998
Additions to release 0.9 include:
Release date: June 1997
Initial (beta) release of the CGAL library.