As in 2010, 2011, 2012 and 2013 the CGAL Project is a mentoring organization of the Google Summer of Code. On this page we present some project ideas as well the information applicants have to provide us. GSoC applicants are welcome to propose other ideas and check if a mentor is interested in supervising it.

Previous project ideas of the CGAL project for the **Google Summer of Code** can be found on the following pages:
2010, 2011,
2012, 2013.

**Before sending an email to anybody, please carefully read this section.**

First section to read: Information Candidates Should Supply

- Use Embree for Ray Shooting
- Adding Better I/O for the CGAL Library
- Fixes to the 2D Arrangements Package
- Support for Qt5
- Adding a Parallel Version of the Edge Simplification Algorithm
- Enhancing the Upcoming Visibility Package
- Implementing a Shortest Path on Polyhedron Algorithm
- Intersection of Half-Spaces and Computation of the Voronoi-covariance Measure of a Point Set
- Finalization of the Implementation of a 2D Reconstruction and Simplification Algorithm from Point Set
- BGL for Combinatorial Maps and Linear Cell Complex
- Enhancing the Plane-Sweep Framework for Arrangements
- Adding a package for constructing exact Yao graphs to CGAL

**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 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 class.
- Fix the demo to support polylines and enhance it to support the algebraic traits.
- Replace CGAL::Object with boost::variant
- Augment the polyline traits.

**Required Skills:** Qt4, C++ templates

** Mentor(s)**:
from GeometryFactory
and
from (CNRS/Université de Lyon)

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

CGAL has a triangulated surface mesh edge simplification package based on the paper

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

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

The goal of this project is to implement the following shortest path algorithm into CGAL:

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

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:

- An optimal transport approach to robust reconstruction and simplification of 2D shapes, in Computer Graphics Forum (proceedings of EUROGRAPHICS Symposium on Geometry Processing), 30, 5, 1593-1602, 2011

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.

**Mentor(s)**:
from (CNRS/Université de Lyon)
and
from GeometryFactory

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

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

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

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

This anchor is a mailto: with a mail body containing the above items.