As since 2010, the CGAL Project was a mentoring organization of the Google Summer of Code in 2014. 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, 2013.
First section to read: Information Candidates Should Supply
Mentor(s): from GeometryFactory
Project description:The Embree project has a low level API for ray shooting queries. First benchmarks show that Embree is faster than the CGAL AABB Tree. This is partially due to the use of vector operations. The goal of this GSoC project is twofold. First, we want to allow to use Embree, for example in the mesh generator. Second the student should introduce vector operations in the AABB Tree.
Required Skills: parallel vector operations, C++ templates
Mentor(s): from GeometryFactory
Project description:The goal of this project is to add some wrapper to allow CGAL to read/write different classical input files.
The obvious things we see that is missing are:
The goal is not necessarily to re-implement these readers/writers but rely on existing software with a license compatible with CGAL
Required Skills: vtk, C++ templates, cmake
Mentor(s): from the Applied Computational Geometry Lab, Tel Aviv University
Project description:Fix and enhance various small features in the 2D Arrangements package:
Required Skills: Qt4, C++ templates
Mentor(s): from GeometryFactory and from (CNRS/Université de Lyon)
Project description:In short: Add support for Qt5 and keep the support for Qt4 in CGAL demos.
CGAL has a support for Qt4, and all its demos are written using Qt4 (without the Qt3Support module). Now that Qt5 is released (and even at version 5.2), it is time to support that new version. The objective of this project is to design the code of the CGAL Graphics View package, and CGAL demos, so that they can be compiled both with Qt4 and Qt5. The CMake scripts will also have to be adapted so that they can use either Qt4 or Qt5.
Required Skills: C++, Qt4, Qt5, CMake
Mentor(s): from GeometryFactory and from Inria Sophia-Antipolis
Project description:CGAL has a triangulated surface mesh edge simplification package based on the paper
Peter Lindstrom and Greg Turk. Fast and memory efficient polygonal simplification. In IEEE Visualization, pages 279-286, 1998.The goal of this project is to use a modified version of this algorithm to allow edges of a mesh to be simplified using parallel threads.
Required Skills: C++, Intel TBB
Mentor(s): from TU Braunschweig
Project description:
During GSoC 2013 we started a package for visibility computation within 2D polygons. The goal of this project is to enhance the currently implemented algorithms (see Efficient Computation of Visibility Polygons; EuroCG'14; Francisc Bungiu, Michael Hemmer, John Hershberger, Kan Huang and Alexander Kröller. Specifically, the triangular expansion algorithm should be parallelized.
Required Skills: C++, Intel TBB
Mentor(s): from GeometryFactory and Éric Colin de Verdière from ENS
Project description:The goal of this project is to implement the following shortest path algorithm into CGAL:
Chen, J., & Han, Y. (1996). Shortest paths on a polyhedron, Part I: Computing shortest paths. International Journal of Computational Geometry & Applications, 6(02), 127-144.The implementation can be limited to manifold surface and must use the Boost Graph Library extension of CGAL. If time allows an extension of this work could be the implementation of the intrinsic Voronoi diagram.
Required Skills: Computational Geometry, C++, Template programming
Mentor(s): from CNRS/University of Grenoble and from GeometryFactory
Project description:The first goal of this project is to implement a robust intersection of a set of half-space. Several methods might be implemented as efficiency is very important.
The second goal is to use this primitive to implement the Voronoi-covariance measure of a point set,
which can be used for robust estimation of geometric quantities from point clouds (eg. normal, sharp features, etc.).
More details are provided in the following paper:
Required Skills: Notions of Computational Geometry, C++, Generic Programming
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:
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.Mentor(s): from (CNRS/Université de Lyon) and from GeometryFactory
Project description:This project consists in developing the traits class allowing to use Combinatorial map and Linear cell complex data structures as model of Boost Graph Concept.
The new traits class will be developed by taking the similar existing class for Halfedge_data_structure and Polyhedron_3 (which are very similar than Combinatorial map and Linear cell complex of dimension 2). Validation of the class will be done through tests using existing geometrical algorithms in CGAL defined on the Boost Graph Concept, such as the Triangulated Surface Mesh Simplification package for example.
Required Skills: Generic Programming, C++, Boost.
Mentor(s): from the Applied Computational Geometry Lab, Tel Aviv University and from TU Braunschweig
Project description:Expose the plane-sweep class-template of the 2D Arrangements package to the public, so that other users can implement their own concrete algorithms. This requires revisiting the visitor concept, improving the code so that there is a clear distinction between code that requires exact construction and code that does not, implementing tests, developing additional examples, and writing the appropriate documentation.
Required Skills: Generic Programming, C++, Sweep-line framework.
Mentor(s): from TU Braunschweig and from University of Western Sydney
Project description:The goal of this project is to add a package for constructing exact Yao graphs to CGAL. The definition of the Yao graph is simple: given a set of points S on the plane and an integer k, each point in S divides the plane into k equally-angled cones of angle 2Pi/k and establishes an edge to its closest neighbor in each cone. The algorithm used to construct Yao graph in this project will be a sweep-line algorithm similar to the famous Fortune's algorithm for constructing Voronoi Diagrams. The challenging part is that the code should be written such that it is optional whether the constructed graph is the exact one, that is, without mistakes due to rounding errors. This is not trivial since the rays subdividing the cones are defined over algebraic extension fields what depend on the chosen k.
Required Skills: Generic Programming, C++, Sweep-line framework.
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 containing the above items.
