Our overall goal is to extend to curved objects the definitions of the classical geometric structures and the algorithms to compute them.
The goal is also implementation in the
CGAL Library. Historically, the CGAL
kernels provided the user mainly with linear objects (points,
line segments, lines...) and predicates on them.
Curves were present in the traits classes of certain specific packages: arrangement with a traits class for conic arcs, optimization with conics, Apollonius graph with circles.
The effort consists first of all on defining general
The declaration is the following:
Arrangement computed with the CGAL Circular kernel and Arrangement packages, on industrial VLSI data. The zooms show the complexity of the data.
(Thanks to GeometryFactory for the data and to Pierre Alliez for the picture)
. compare on algebraic numbers and roots of polynomial systems,
. solve on systems of bivariate polynomials,
. critical_points on bivariate polynomials,
. sign_at that computes the sign of a bivariate polynomial evaluated at roots of polynomial systems.
Concepts for univariate and bivariate polynomials were reviewed and accepted by the CGAL editorial board.
Models for univariate polynomials, based on the RS software package, should be released soon in CGAL 3.6.
Other models, for both univariate and bivariate polynomials, are expected in the future.
2D Circular kernel
3D Spherical kernel
Algebraic Kernel specifications, in collaboration with Eric Berberich and Michael Hemmer
Pedro M. M. de Castro (internship, summer 2006, now PhD student)
Ioannis Z. Emiris
Julien Hazebrouk and Damien Leroy (project, winter 2006)
Athanasios V. Kakargias (internship, summer 2003)
Ilya Suslov (internship, winter 2006)
Constantinos Tsirogiannis and Julien Hazebrouk (internships, summer 2005)
Introduction to CGAL
Introduction to the curved kernel (Arcadia meeting, 2005)
CGAL news (Dagstuhl Seminar, 2005)
From triangles to curves (invited talk - European Workshop on Computational Geometry, Delphi, March 27-29, 2006)
Design of the CGAL 3D Spherical Kernel (Dagstuhl Seminar, 2007)
Design of the Spherical Kernel (Workshop WRSO, 2007)
This work was partially supported by the IST Programme of the 6th Framework Programme of the EU as a STREP (FET Open Scheme) Project under Contract No IST-006413 (ACS - Algorithms for Complex Shapes)
This work was partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG - Effective Computational Geometry for Curves and Surfaces)
Preliminary work was done partially within the INRIA Associate Team CALAMATA.