GSoC/GCI Archive
Google Summer of Code 2012

CGAL - Computational Geometry Algorithms Library

Web Page:

Mailing List:

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 GPLv3+ license, and some core parts are under the LGPLv3+. The semi-annual releases have currently about 10,000 downloads. CGAL is commercially supported by the spin-off company GeometryFactory.


  • Adding a pose independant 3D mesh surface segmentation algorithm into CGAL The aim of this project is implementing pose independent mesh segmentation into CGAL. Basically, the user provides the mesh and number of cluster-labels as input, and gets segmented mesh as output. In segmentation, both volume-based distances of facets and boundary properties of segments will be considered. While calculating volume-based distances, shape-diameter function (SDF) will be used which is invariant under pose changes that makes whole approach 'pose independant'. Sub-parts of this project also incorporates with ray-casting, expectation maximization, and graph-cut algorithms.
  • Enhancing the Landmarks point-location strategy for 2D arrangements One of the most important query types defined on arrangements is the point-location query: Given a point, find the arrangement cell that contains it. Typically, the result of a point-location query is one of the arrangement faces, but in degenerate situations the query point can be located on an edge or coincide with a vertex. The 2D Arrangements package supports different strategies of point location. The goal of the project to enhance the implementation of a specific strategy called Landmarks.
  • Port and extension of 2D arrangements demo This project will be divided into two parts: (1) port the existing 2D Arrangements demo to Qt4, and (2) enhance it by implementing additional features not already demonstrated by the existing demo. The product to be delivered at the end of this project will be a revamped 2D Arrangements demo, with all of the existing features present in a demo making use of the CGAL Qt Graphics View framework, in addition to some new features that flesh out existing, but yet undocumented, code that handles arrangements on surfaces other than a plane.