CGAL - Computational Geometry Algorithms Library

Web Page: http://www.cgal.org/project_ideas.html

Mailing List: mailto:cgal-discuss@lists-sop.inria.fr

CGAL is a software library that offers a number of reliable geometric data structures and algorithms. CGAL components operate in 2D and 3D, and sometime in arbitrary dimensions. Examples of components include convex hulls, convex decomposition, Delaunay triangulations, Voronoi diagrams, polygonal surface mesh data-structures, mesh generation, Boolean operations, envelope computations, intersection detection, surface reconstruction, and subdivision surfaces. CGAL is used in a variety of application domains such as CAD/CAM (computer aided design and modeling), GIS (geographic information systems), geophysics, image processing, molecular biology, robotics, motion planning, and graphics. CGAL is written in C++ and rigorously adheres to the generic-programming paradigm. CGAL became an Open Source project in 2003. Most of CGAL is under the QPL license, and some core parts are under the LGPL (v2.1). The semi-annual releases have currently about 10,000 downloads. CGAL is commercially supported by the spin-off company GeometryFactory.

Projects

• Add an Interface for the Eigen Library The goal of this project is to interface CGAL with the Eigen library. This project is about interfacing software, hence beyond C++ programming one has to care about the build system, cross-platform aspects. Depending on the progress of this project, an additional task would be to work on out-of-core functionalily.
• Integrate As-Rigid-As-Possible Surface Modeling in CGAL This project aims at integrating as-rigid-as-possible surface modeling algorithm, which is a widely used for geometric deformation, into CGAL. The algorithm takes a triangular surface mesh and vertex handles as input, then output the deformed mesh satisfying positional constraints. The main tasks concentrate on computing the cotangent Laplacian of mesh, taking singular value decomposition to covariance matrices and solving linear sparse system.
• Local Operators on 3D Triangulations Complex 3D objects are usually represented using tetrahedral meshes. Delaunay triangulation scheme could be used to build such meshes but their "quality" is critical for different numerical algorithms (e.g. the finite element method). Therefore the mesh is usually improved by different local transformations over the vertices and edges. Our goal is to implement some of them (edge removal, edge collapse, multi-face removal) in a reliable manner.
• Parallelizing Divide-And-Conquer This project aims to parallelize some of the algorithms in the 2D Arrangement package and related packages which use a divide-and-conquer approach. The following components are candidates for such an enhancement: (as mentioned in the project description) • Boolean set-operations • Envelope algorithms. • Minkowski sum using convex decomposition.
• Replacing some Basic Non-Geometric Tools in CGAL by Boost/TR1/C++0x Functionality CGAL has accumulated a number of geometry-independent tools which these days offer duplicate functionality with what is (a) in TR1, (b) planned for the next C++ standard C++0x, and/or (c) are in Boost. Doing the replacement would help in the long-term by easing maintenance: (a) less code to maintain, and (b) new people are more likely to know about a standard tool.