The CGAL Project

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

Mailing List: mailto:gsoc-cgal@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 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.

Projects

• 2D AABB Tree The axis-aligned bounding box (AABB) is one of the most common bounding volumes. Given a set of geometric primitives, we can arrange the individual AABBs into a tree hierarchy which will significantly increase the performance to logarithmic complexity. This performance enhancement together with simplicity and less memory requirement compared to hierarchies like OBB Tree has shown great practical usage of AABB in different application areas. In this regard, CGAL has an optimized AABB Tree implementation in 3D. So, we will devote this work to implement the 2D AABB Tree for CGAL understanding the dimentional changes and sharing the existing code, but deducing a different component.
• Adding point set consolidation algorithms into CGAL This blue-sky project is about adding new algorithms for point set processing into CGAL. The new methods can consolidate unorganized raw scans, which are proved to be simple, efficient and robust. Demo video and implementation are available.
• Curve-Skeletonization Algorithm into CGAL For GSoC'13, I am interested in adding the skeletonization algorithm described in the paper ``Mean Curvature Skeletons'' into CGAL. The project is easily decoupled into two major milestones. In the first, I will focus on the implementation of the iterative contraction algorithm; in the second, I will extend it to include the functionalities needed to generate well-centered skeletons. In this document I define the goals for this project and a schedule for their completion. I also provide personal information that hopefully demonstrates that I have the necessary capabilities to bring this project to completion.
• Improved design and new features for the Mesh_2 package The Mesh_2 package implements a 2D isotropic triangle mesh generator. Currently, the domain to be meshed is defined by some constrained edges and a set of seed points. The focus of the project is to add and improve functionality the this package, by adapting it to work as Mesh_3 package, add mesh optimization methods and generalize input type to different mesh representations.
• More point generators in CGAL The project adds some more functionalities to the Generator package in the CGAL library.
• Visibility Polygon Implementation Application for the "Visibility Polygon Implementation" project; proposes a visibility polygon computation using a balanced binary search tree without a preprocessing step
• Visibility Polygon Implementation in CGAL using Algorithm with Arrangement Preprocessing This proposal has five sections. The first is the algorithms and the project result I expect. The second part is my schedule of this project. The third part is some personal information. The fourth part is my commitment of full time involvement on the GSoC project. The last part is a short cv.