As since 2010, the CGAL Project was a mentoring organization of the Google Summer of Code in 2013. Successful projects can be found here.
On this page we presented some project ideas for the Google Summer of Code 2014.
Previous project ideas of the CGAL project for the Google Summer of Code can be found on the following pages: 2010, 2011, 2012.
First section to read: Information Candidates Should Supply
CGAL is a C++ template library which heavily relies on concepts. In order to increase the quality of the library we would like to introduce a mechanism to check that all the requirements of a concept are exactly those needed (a concept might be missing some requirements and might also ask requirements that are not used). A solution might be using the Boost Concept Checking Library. This task does not require any particular notion of computational geometry.
Required skills: C++, Generic programmingCGAL provides a variant of the Poisson algorithm. Main differences are that it uses a tetrahedrization instead of an octree, and performs two passes to avoid artifacts where the algorithm has to fill big gaps. We would like to incorporated the new ideas of Misha Kazhdan's last paper into CGAL. These improvements would allow to explicitly incorporate the points as interpolation constraints, and would reduce time complexity.
Required skills: C++, Generic programming, Computational geometryThis project consists in implementing the following paper of Pooran Memari and Jean-Daniel Boissonnat:
This algorithm is able to reconstruct a 2D shape described by a set of segments, each representing the intersection of the shape with a line. The implementation will be based on existing components from the CGAL library (2D Constrained Delaunay Triangulation, Voronoi diagram of segments, Intersection primitives, ...). The motivation for implementing this algorithm is to use it as a preprocessing step in the 3D generalization currently under development.
Required skills: Computational geometry, C++, CGALThis 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:
The purpose of this project is to understand the code written for this research paper, propose a suitable API and update the code accordingly, write a demo, write the documentation into CGAL style, and submit the package to the Editorial Board for review. Of course, the student is invited to perform an extra optimization of the code and to propose new ideas to improve the algorithm. This project is particularly interesting to show what we usually call ''the extra mile'' to turn a code written for a research paper into a documented and publicly distributable code.
Required skills: Generic Programming, C++, QT4 (GraphicsView Framework), Computational Geometry is a plus.The purpose of this project is to provide the same functionalities as the ones provided by the 3D AABB package but in 2D. Instead of duplicating of the code, the student will have to devise a solution that shares as much as possible source code from the 3D implementation, without breaking backward compatibility. Once completed, a testsuite carefully checking the correctness and performances of the implementation must be devised. The performance of such a core component being important, code profiling and optimization is a key aspect of the project.
Time permitting, the student will propose a solution to the point-inside-polygon test using the 2D AABB-tree and will to participate to the ACM GISCUP 2013.
Required skills: Generic Programming, C++, Data Structures and AlgorithmsWhen you construct an arrangement induced by a set A of arbitrary planar curves, you end up with a collection C of x-monotone subcurves of A that
are pairwise disjoint in their interior. These subcurves are associated with the arrangement edges (more precisely, with pairs of DCEL halfedges).
The Arrangement_with_history_2<Traits,Dcel> class-template offered by the
2D Arrangement
package extends the Arrangement_2<Traits,Dcel> class template with an additional layer that represents A and a cross mapping
between the curves of A and the arrangement edges they induce. Let B denote the set of maximal x-monotone subcurves of the curves in A.
In this project you are asked to augment the Arrangement_with_history_2 class-template with an additional layer that represents B,
and cross mappings between the curves of the three layers, i.e., A, B, and C. If time permits, the last part of this project is to develop a generic
function that repairs corrupted general polygons exploiting the augmented arrangement-with-history class-template.
An object of the class template Arrangement_2<Traits,Dcel> offered by the
2D Arrangement package represents
the planar subdivision induced by a set of x-monotone curves and isolated points into maximally connected cells. The arrangement is
represented as a doubly-connected edge-list (Dcel) such that each Dcel vertex is associated with a point of the plane and each edge is
associated with an x-monotone curve whose interior is disjoint from all other edges and vertices. The Dcel template parameter must be substituted
by a model of the concept ArrangementDcel. The 2D Arrangement
package offers a model of this concept called Arr_dcel_base<V,H,F>.
In this project you are asked to develop another model of this concept using the Combinatorial Map data structure offered by the
Combinatorial Maps package.
CGAL is a C++ library of algorithm and library providing various modules (packages) that do not necessarily depend on each other. A criticism that we often hear about CGAL is that it's a too large library, people would be happy to have only a small portion of the library to use only what they need. The purpose of this project is to find the best approach to achieve this goal. Internally, CGAL is already decomposed into packages and the release tarball consists in a flatten view of this structure. This project implies to detect the real dependencies amongst packages (that is headers included and used), encode this dependencies at the level of cmake, identifies core component that are required by all the packages, find a way for users to download the modules they are interested in, etc.
If time allows it, the student will try to find a way to reduce the size of the core component, make optional the compilation of the lib, etc.
Required skills: C++, Generic Programming, cmakeCGAL is a high quality generic C++ library on Computational Geometry. Amongst its features, CGAL offers random point generators in disks, squares, balls, cubes, hypercubes, to mention a few. Point generation is quite useful for several things, e.g., testing algorithms, obtaining initial values for optimization schemes, and more. In this work, we will concentrate efforts on implementing new point generators. Some of the useful point generators that are missing in CGAL include random points inside a triangle, simplex, triangulation, on a surface mesh, on a pure complex, ...
Required skills: C++, Generic programmingSage is one of the leading and fastest growing open source mathematics software systems. It combines the features of nearly a hundred open source projects and provides a clean high-level Python-based shell and programming environment to easily access their functionality. In particular, Sage offers a wide range of symbolical and algebraic computations. However, Sage currently lacks advanced algorithms for geometric computing. Vice versa, the development of geometric-algebraic algorithms in CGAL can be tedious, and while CGAL provides highly efficient filtered algebraic predicates for its current use cases, more complicated applications would benefit from the large range of algebraic operations accessible via Sage.
The goal of this project is to provide a clean way to call CGAL functions from Sage. The existing CGAL bindings for Python can serve as a guide, but have to be extended by interfaces supporting arbitrary precision number types. For efficiency reasons, it seems that Cython is the method of choice and should be preferred over SWIG or Boost wrappers.
If time allows, a second goal is to access Sage functionality within CGAL.
Required skills: C++, Python, CythonThis project consists in implementing a curve-skeletonization algorithm for a watertight surface mesh. The algorithm consists of two main phases. In the first step, a mass-spring system is solved, resulting in a progressive contraction of the model into a skeleton. In the final step, the watertight surface is converted into a network of curves by shortest-edge collapse. The basic algorithm can also be extended to guarantee that the curves are centered within the object.
A visual demo of the algorithm is available here and the algorithm is explained in the following paper (a reference implementation is also available at this page):
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 constrained edges divide the plane into several connected components. The mesh domain is either the union of the bounded connected components including at least one seed, or the union of the bounded connected components that do no contain any seed. The project can be split into three phases:
or additionnal details, here is the documentation of the current Mesh_2 package and of the Mesh_3 package.
Required skills: Advanced C++, generic programming, background in Computational Geometry or Geometry Processing.Given a planar polygonal domain (which can be given as a polygon or as an arrangement) and a query point, compute the polygon of all points that can see the query point. Efficient algorithm implementations for this problem are still missing in CGAL. This project will therefore join forces with people at TU Braunschweig, with the purpose of developing a new package for visibility. Together we will work on implementing several different algorithm types (with vs. without preprocesing) for different problem inputs (simple polygons vs. polygons with holes vs. arrangements); including limited vision ranges would be a welcome extra.
Specifically, the project consists of the following steps:
The application process has several steps. Before contacting anybody verify that you are eligible, that is that you are enrolled as student, don't get a tuition fee, etc. The next step is to contact the mentor of the project you are interested in. You have to convince him that you are the right person to get the job done. The next step is to work out more details and to contact the mentoring organization by providing the following information by email to gsoc-cgal@lists-sop.inria.fr
This anchor is a mailto: with a mail body containg the above items.
