The CGAL Project

License: GNU General Public License version 3.0 (GPLv3)

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

Mailing List: mailto:gsoc-cgal@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 GPL v3+ license, and some core parts are under the LGPL v3+. The semi-annual releases have currently about 10,000 downloads (see https://gforge.inria.fr/frs/?group_id=52). CGAL is commercially supported by the spin-off company GeometryFactory. A relatively well maintained list of projects using CGAL is available here: http://www.cgal.org/projects.html .

Projects

• Enhance Visitiblity Package The aim of this proposal is to enhance the upcoming package about visibility in polygonal domain in the CGAL library. The package will compute all points in a polygonal domain visible from a query point, with respect to different inputs. The development will be mentored by Michael Hemmer, and may be released as a part of the new CGAL library.
• Extend 2D Arrangements visualization and the Qt Graphics View framework This is a proposal to extend the work on the 2D Arrangements visualization in Qt4 from GSoC 2012. We'll add code for visualizing and interacting with 2D polyline, Bezier, and algebraic curve types, as well as 3D spherical geodesic curves. In addition, this project will contribute Arrangement-specific components to the Qt Graphics View framework and general design changes to provide dual support for Qt4 and Qt5.
• Finalization of the implementation of a 2D Reconstruction and Simplifica... This project consists in going to the submission of a new package to CGAL. The student will start from the prototype code of the following paper by De Goes and Cohen-Steiner and Alliez and Desbrun: An optimal transport approach to robust reconstruction and simplification of 2D shapes, in Computer Graphics Forum (proceedings of EUROGRAPHICS Symposium on Geometry Processing), 30, 5, 1593-1602, 2011
• Implementing a Shortest Path on Polyhedron Algorithm Implement Chen and Han's single-source shortest paths on a polyhedron algorithm, possibly augmented with the improvements given by Xin and Wang (2009), and also augmented to give shortest paths from a geodesic curve on the surface, rather than just a single point.
• Intersection of Half-Spaces and Computation of the VCM This projects consist in implementing a function for computing an intersection of half-spaces, and use it in the point set processing package for normal and sharp edge estimation through the Voronoi covariance measure. In order to have a robust yet efficient implementation, the computation of the intersection of half-spaces will rely on CGAL's convex_hull_3 with a set of specific filtered predicates.
• Reduced Convolutions for CGAL's 2D Minkowski Sum package Goal of this project is to improve CGAL's minkowski_sum_2 package regarding run time and memory consumption. This will be achived by implementing the "Reduced Convolution Algorithm" as described by Behar's and Lienc, which is robust and handles low dimensional boundary features. The package's documentation and examples will be improved. A new Qt demo application will be designed to provide an interactive demonstratation of the package's capabilities.
• Support for Qt5 This proposal expounds the personal data about me asked by the CGAL organization as well as the methodology I provide for the CGAL project “Support for Qt5”, what I have imagined for the porting of CGAL and all its demonstrations to Qt5 technology.