Our application has been rejected this year.
The CGAL Project applied as a mentoring organization for the Google Summer of Code 2015.
Previous project ideas of the CGAL project for the Google Summer of Code can be found on the following pages: 2010, 2011, 2012, 2013, 2014.
First section to read: Information Candidates Should Supply
Mentor(s): from GeometryFactory
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
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 GeometryFactory and from Inria Sophia-Antipolis
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 INRIA Nancy - Grand Est - LORIA and from GeometryFactory
The sphere can model atoms (biology) as well as the earth (geography) and the celestial vault (astrophysics), which shows a strong need for computations on the sphere. A method was proposed, a few years ago, to compute triangulations of points on or close to a sphere [1], and a prototype software has been written. The prototype is very efficient, but it duplicates some parts of the CGAL 2D triangulation classes. The project will consist in proposing a new design for those classes in order to avoid duplications, and implementing it. Some work is in progress in CGAL on re-designing the CGAL 3D triangulation packages, which will provide an example for a potential solution.
[1] Manuel Caroli, Pedro M. M. de Castro, Sébastien Loriot, Olivier Rouiller, Monique Teillaud, and Camille Wormser. Robust and Efficient Delaunay triangulations of points on or close to a sphere. In 9th International Symposium on Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 462-473, 2010. Preliminary version available at https://hal.inria.fr/inria-00405478/
Required Skills: C++, design patterns
Mentor(s): from the Applied Computational Geometry Lab, Tel Aviv University
Fix and enhance various small features in the 2D Arrangements package:
Required Skills: C++, templates, Boost
Mentor(s): from GeometryFactory and from GeometryFactory
CGAL provides many 3D algorithms and most of have a corresponding plugin for the Polyhedron demo. The demo frameworks need a few improvements:
Required Skills: OpenGL, C++, QT
Mentor(s): from CNRS/Université de Lyon
Add the dynamic attributes functionality in the combinatorial maps package. The principle of this functionality is to allow users to add/remove attributes associated with cells of a combinatorial map dynamically. The idea is to use boost property maps, similarly to the existing code in the new Surface mesh package.
Required Skills: C++, Boost
Mentor(s): from TU Braunschweig
CGAL currently provides a package for Axis Aligned Bounding Box trees in 3D. However, this package is not generic in the sense that it fixes the dimension and the type of the bounding volume. Moreover, the package does not provide intersection or distance computation of two Hierarchies. Based on a prototype implementation developed in Braunschweig the goal is to provide a new package that provides similar features while leaving the dimension and the bounding volume type unspecified.
Required Skills: C++, templates, Boost
Mentor(s): from TU Braunschweig
The upcoming CGAL package for visibility provides visibility computation within 2D polygons and in 1.5D Terrains. The goal of this project is to provide visibility computation in a 2.5D Terrain, that is, a 2D Triangulation where every vertex is annotated with a height value. A point ''p'' sees another point ''q'' iff the segment ''pq'' is nowhere below the given terrain. The goal is to compute the visible area for a given point ''p''.
Required Skills: C++, templates, Boost
Mentor(s): from GeometryFactory
The release 4.5 of CGAL introduces extensions of the BGL graph concepts for meshes represented as halfedge data structures (http://doc.cgal.org/latest/Property_map/index.html). Some packages of CGAL needs to be updated to use this API:
CGAL::convex_hull_3_to_polyhedron_3() Required Skills: C++, templates, Boost graph library
Mentor(s): from GeometryFactory
The documentation of CGAL is generated using a patched version of doxygen. In order to easily upgrade the version of doxygen used to generate the documentation, we need to check that all the functions, classes and methods are correctly documented, and all elements are correctly linked.
Required Skills: C++, html, doxygen
Mentor(s): from CNRS at Ceremade, Université Paris-Dauphine and from GeometryFactory
In several applications, it is necessary to compute exactly the intersection of a power diagram (a generalization of a Voronoi diagram) with a triangulation of the plane, e.g. implementation of Lloyd's algorithm for meshing, resolution of quadratic optimal transport problems in the plane, etc. The problem we consider is the following: our input is a set of weighted points (x_i,w_i) and a (completely unrelated) triangulation T of a domain of the plane. Denoting P_i the power cells of the ith point and t_j the jth triangles of the triangulation T, the goal is to compute the collection of non-empty intersections (P_i \cap t_j). The goals of the GSoC student are the following:
[1] http://arxiv.org/pdf/1409.1279v1.pdf, Section 2.1[2] https://github.com/mrgt/MongeAmpere, see include/MA/voronoi_triangulation_intersection.cpp
Required Skills: C++, templates, some basic maths
Mentor(s): and Oren Zalsman from the Applied Computational Geometry Lab, Tel Aviv University
Fix and enhance various small features in the 2D Regularized Boolean Operation package:
Required Skills: C++, templates, and some computational geometry.
Mentor(s): from GeometryFactory
The goal of this project is to rewrite all the intersection predicates (do_intersect_2/3) to provide more information, but at the same time staying backward compatible. For example, say you want to know whether two segments intersect but also where lies the intersection, in the interior or at an endpoint of each segment. If the student is fast enough, an extension of the project is to rewrite intersection computation functions to take into account the result of the do-intersect predicate to speed up the computation.
Required Skills: C++, generic programming, basic geometry
Mentor(s): from GeometryFactory and Raphaëlle Chaine from CNRS/Université de Lyon
Starting from the code of the author of A geometric convection approach of 3D reconstruction, Raphaëlle Chaine, ACM International Conference Proceeding Series, Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry processing, SGP2003, pp. 218-229, June 2003
The student will need to propose a way to parallelize this point set reconstruction algorithm following the CGAL's guidelines.
Required Skills: C++, parallel programming, Intel TBB
Mentor(s): and Sébastien Loriot from GeometryFactory
The CGAL project is willing to move from a dedicated Git repository, to the Github service. One of the issue is that Github no-longer support the server Git hooks, but only its own instance named webhook. The student will implement a bridge between Github webhooks and usual Git hook scripts, so that one can for example use [https://github.com/mhagger/git-multimail git-multimail] with Github.
Required Skills: shell programming, web services
Mentor(s): from GeometryFactory and Clément Jamin from Inria Sophia-Antipolis
In this project, the student would have to:
Required Skills: C++, geometry
Mentor(s): from ESPCI and from INRIA Nancy - Grand Est - LORIA
This project spans the bridge from statistical physics to CGAL. In
experiments on colloids, one challenge of our days is to measure, or
at least estimate thermodynamic properties such as pressure and
chemical potential (to finally get the free energy). There is one
special system, the hard-sphere liquid, where theoretical physics can
help to develop algorithms that allow to do that: The thermodynamics
of hard-sphere gases can indeed be measured from snapshots ("photos")
which contain only the positions and radii of the spheres. In the
algorithm, one needs an efficient and robust triangulation of space
that is adapted to the individual radii of the spheres. In order to
validate the algorithm, one wants to avoid the effect of boundaries.
In summary, one needs precisely what is currently being developed in
CGAL: the periodic weighted Delaunay triangulation.
The project will comprise the following steps:
Required Skills: C++
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
