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

- Use Embree for Ray Shooting
- Adding Better I/O for the CGAL Library
- Adding a Parallel Version of the Edge Simplification Algorithm
- Finalizing a Package for 2D Triangulations on the Sphere
- Enhancing the 2D Arrangements Package
- Improving the Polyhedron Demo
- Dynamic Attributes for Combinatorial Maps
- Implementation of a Generic Bounding Volume Hierarchy (BVH)
- Visibility Computation in 2.5D Terrains
- Update Packages to Use the BGL API
- Tool to Compare the Output of Two Runs of Doxygen
- Intersection of a Power diagram with a triangulation in 2D
- Fixing and Enhancing 2D Regularized Boolean Operations
- Reworking Intersection Functions
- Parallel Implementation of a Point Set Reconstruction Algorithm
- Create a bridge between the available Github "webhooks", and the usual Git hook scripts
- 3D Mesh Generation - Detect and handle small geometric features
- Statistical mechanics of hard spheres

**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:

- vtk data structures (unstructured grids, poly data, ...)
- MRI file formats for the meshing algorithms: Nifti (.nifti), Gis (.img, .hdr), vtk
- GIS file formats (WKT, GML, GeoJSON, ...)

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:

- Implement Naive Ray Shooting.
- Fix all point location strategies to work with all traits classes.
- Replace CGAL::Object with boost::variant.
- Use smart pointers instead of allocation and deletion.
- Add CGAL::insert(arr, curves_begin, curves_end, points_begin, points_end).
- Fix the zone() free function (it's not according to the formal definition).
- Implement missing (documented) functions.
- Add a default traits parameter for free functions that do not have it yet.

**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:

- Use modern OpenGL API
- Categories for plugins
- Reorganization of the code per plugin
- Add more plugins
- Port a selection tool for point set

**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:

- Polyhedral oracle for
*3D Mesh Generation* -
*Planar Parameterization of Triangulated Surface Meshes* -
*Approximation of Ridges and Umbilics on Triangulated Surface Meshes* -
*Estimation of Local Differential Properties of Point-Sampled Surfaces* -
*3D Surface Subdivision Methods* -
`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.

- The first goal of this project is to write a tool that can compare the html output directly or to add a new functionality in doxygen to help doing the comparison.
- The second goal is to enable the latest doxygen release to generate the documentation of CGAL.

**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:

- Implement an algorithm of [1] to perform this computation into CGAL. A preliminary implementation using CGAL [2] (but not included in CGAL yet) is available as a starting point, but there is room for improvement for the computation of the predicates and the API design.
- Extend this implementation, so as to be able to compute the intersection of a 3D power diagram with an embedded 2D triangulation. This has application in surface remeshing.

`[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:

- Add namespace.
- Introduce an implementation of intersection testing for convex polygons.
- Optimize union and intersection of many polygons.

**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:

- Develop an algorithm to detect holes in a domain (polyhedral domain, image).
- Improve the existing algorithm that detects sharp polyline features in a polyhedral domain.
- Improve the API of Mesh_3 to let the user insert some initial points to start the meshing process. Those can either be automatically chosen on the detected holes, or simply given by the user.
- Develop an algorithm to detect polyline features in 3D images, and integrate it in the public API.

**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:

- Extend an existing 2D prototype to 3D, using the CGAL periodic regular triangulation.
- Running the program on hard-sphere configurations that are generated by an existing molecular-dynamics code, to validate the thermodynamic properties.

**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

- Select a project in the list and provide your personal and detailed description. If you wish to work on another idea of your own, we are pretty open as long as this serves the goal of consolidating CGAL as a whole.
- Provide a proposal of a technical solution with your envisioned methodology. The more detailed the better.
- Explain how the solution will be available to the user, in which form. Do not forget the documentation, unitary tests and cross-platform aspects.
- Provide a realistic schedule with objectives (one every two weeks for example) and deadlines. Focus on mid-term objectives as well as on the final evaluation.
- Provide a formal commitment that you will be involved full time on the GSoC. This is absolutely mandatory.

- First name, last name, affiliation and geographical location.
- A brief list of the main studies and programming courses attended, with ranking.
- List of the most important software projects contributed and success.
- Which are your best skills in terms of programming and scientific computing?
- In general what is your taste in terms of programming? language, methodology, team work, etc.
- Is there anything that prevents you from working full time on the project during the program period?
- How do you see your involvement after the program ends? Do you see yourself pushing the project further, or do you see yourself contributing to other CGAL projects?
- Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
- What are your long-term wishes in terms of job?