The CGAL Project is a mentoring organization of the Google Summer of Code 2017. 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. For new project proposals, contact us at gsoc-cgal@inria.fr.

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, 2015,
2016.

First section to read: Information Candidates Should Supply

- Adding a Parallel Version of the Edge Simplification Algorithm
- Reworking Intersection Functions
- Enhancing the 2D Arrangement Demo (1)
- Enhancing the 2D Arrangement Demo (2)
- Create a Bridge Between the Available Github "webhooks", and the Usual Git Hook Scripts
- Finalizing a Package for 2D Triangulations on the Sphere
- Improving Poisson Surface Reconstruction
- Improving Normal Orientation
- Hexahedral Mesh Extraction
- Mesh Smoothing and Shape Smoothing
- Integrating PinMesh in CGAL
- Interfacing
`NearptD`

with Point Set Processing algorithms of CGAL

**Mentor(s):** Sebastien Loriot (GeometryFactory) and Clement Jamin (INRIA)

**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 be able to run the edge simplification algorithm in parallel.
There are several ways to achieve it:

- modify the current algorithm so that several thread can work on the simplification.
- implement a method to decompose the meshes into submeshes and run the algorithm sequentially on each part + special care for the stitches.
- implement another method that is better and designed for parallel computing.

**Required Skills:** C++, Intel TBB

**Contact:** sebastien.loriot@cgal.org

**Mentor(s):** Sebastien Loriot

**Project description:**

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

**Contact:** sebastien.loriot@cgal.org

**Mentor(s)**: Efi Fogel (Tel Aviv University)

**Project description:**

Currently the demo supports (linear) segments, polylines, conic arcs, linear curves, and circular arcs. The goal of this project is to enhance the 2D arrangement demo to support additional types of curves, namely, Bezier curves and algebraic curves.

This is a perfect project for GSoC. A developer that commits to pursue the goals of this project will learn to use the 2D arrangement package, other components of CGAL, and other libraries, such as QT. The purpose of the CGAL demos is to demonstrate the potential of the various components of CGAL using visual effects. The excitement and satisfaction, a developer of an application experience, are always enhances when visual effects are exploited. Demo programs of CGAL show the capabilities of the library and help the community evaluating it. A potential user can quickly determine whether a specific component of CGAL can be used to solve a problem she or he may have and how to go about it.

**Required Skills:** C++, generic programming, basic geometry

**Contact:** efifogel@gmail.com

**Mentor(s)**: Efi Fogel (Tel Aviv University)

**Project description:**

Currently the demo supports only arrangements in the plane. The goal of this project is to enhance the 2D arrangement demo to support 2D arrangements not only embedded in the plane, but also embedded in certain surfaces in space, e.g., arrangements of arcs of great circles embedded in the sphere. This is an upcoming feature of the "2D Arrangements" package.

Like the project above, this is also a perfect project for GSoC. A developer that commits to pursue the goals of this project will learn to use a significant upcoming feature of the "2D Arrangements" package that supports 2D arrangements on 3D surfaces. Similar to the project above, the developer will learn to use other components of CGAL, and other libraries, such as QT. The purpose of the CGAL demos is to demonstrate the potential of the various components of CGAL using visual effects---an enjoyable side effect of developing such applications especially when 3D graphics is involved. Demo programs of CGAL show the capabilities of the library and help the community evaluating it. A potential user can quickly determine whether a specific component of CGAL can be used to solve a problem she or he may have and perhaps how to go about it.

**Required Skills:** C++, generic programming, basic geometry, basic 3D graphics

**Contact:** efifogel@gmail.com

**Mentor(s):** Laurent Rineau

**Project description:**

The CGAL project has moved from a dedicated Git repository to the Github service. One 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 git-multimail with Github.

**Required Skills:** shell programming, web services

**Contact:**: laurent.rineau@cgal.org

**Mentor(s):** Sebastien Loriot (GeometryFactory) and Monique Teillaud (INRIA)

**Project description:**

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.

**Required Skills:** C++, design patterns

**Contact:** Sebastien.Loriot@cgal.org, Monique.Teillaud@inria.fr

**Reference**

[1] Manuel Caroli, Pedro M. M. de Castro, Sebastien 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/

**Mentor(s):** Pierre Alliez (Inria), Gael Guennebaud (Inria) and Simon Giraudot (GeometryFactory)

**Project description:**

The current implementation from CGAL: http://doc.cgal.org/latest/Poisson_surface_reconstruction_3 can be improved along two axes: scalability and smoothness of the reconstructed surfaces.
The scalability is hampered by the fact that the Poisson solver requires a space discretization: a Delaunay triangulation generated via Delaunay refinement, and a matrix assembly. A first direction is to reduce the complexity of the triangulation. A second direction is a hash data structure inspired by [1]. A third direction is to investigate a matrix-free approach where the implicit function is computed in closed form using a far field approximation.
On smoothness of the output surfaces, the current issue is that the current implicit surface is piecewise linear as computed on a piecewise linear 3D function. We will investigate local smooth interpolation approaches that yield smooth surfaces at all scales. Another issue arises on surfaces with boundaries. We will devise an approach that generate smooth curves as boundaries.

**Required Skills:** C++, geometric data structures, applied maths.

**Contact:** pierre.alliez@inria.fr, gael.guennebaud@inria.fr and simon.giraudot@geometryfactory.com

**References**

[1] http://mesh.brown.edu/ssd/software.html

**Mentor(s):** Pierre Alliez (Inria), Gael Guennebaud (Inria) and Simon Giraudot (GeometryFactory)

**Project description:**

The current CGAL approach for normal orientation http://doc.cgal.org/latest/Point_set_processing_3 proceeds by propagation along a minimum spanning tree. While this approach is satisfactory for noise-free connected point sets, it fails on disconnected point sets with high noise. The first objective is to evaluate two more recent approaches on a wide range of point sets [1,2]. The second objective is to implement the best approach as a CGAL algorithm. The third objective is to investigate the use of an existing approach [3] based on the construction of an signed implicit function from unoriented points, in order to deduce the normal orientation.

**Required Skills:** C++, geometric data structures, applied maths.

**Contact:** pierre.alliez@inria.fr, gael.guennebaud@inria.fr and simon.giraudot@geometryfactory.com

**References**

[1] Consolidation of Unorganized Point Clouds for Surface Reconstruction. H. Huang, D. Li, H. Zhang, U. Ascher, D. Cohen-Or. ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA) 2009.

[2] Towards Globally Optimal Normal Orientations for Large Point Clouds. N. Schertler, B. Savchynskyy, S. Gumhold, In Computer Graphics Forum, 2016.

[3] Voronoi-based Variational Reconstruction of Unoriented Point Sets. P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. In Proc. 4th Annu. Sympos. Geometry Processing, pages 39-48, 2007.

**Mentor(s):** Guillaume Damiand (CNRS/LIRIS)

**Project description:**

Implement the method given in the paper "HexEx: Robust Hexahedral Mesh Extraction", Max Lyon, David Bommes, Leif Kobbelt, SIGGRAPH 2016. In this paper, authors defined a method to extract an hexahedral mesh from 2D surfacic mesh. This methods uses 3D generalized map which are now available in CGAL. Authors paper and code are available here [1]. The goal of this project is to implement the method in CGAL based on the 3D generalized map package.

**Required Skills:** C++, geometric data structures.

**Contact:** guillaume.damiand@liris.cnrs.fr

**References**

**Mentor(s):** Jane Tournois (GeometryFactory), Pierre Alliez (Inria)

**Project description:**

Mesh Smoothing and Shape Smoothing (or Geometric Smoothing) are often needed to improve the quality of a surface mesh. The choice of quality criterion (angles, edge lengths, smoothness, noise,...) leads the choice of the optimizer. Many algorithms that provide solutions for geometric smoothing
and mesh smoothing are available in the literature. The goal of this project is to implement and publish some of the State-of-the-Art algorithms in the
CGAL Polygon Mesh Processing package.

- Geometric Smoothing includes the
*Mean Curvature Flow*[1] and its volume preserving and feature preserving variants. - Mesh Smoothing includes the
*High Quality Compatible Triangulations*[2] and methods that are angle-based or area-based.

This work can be extended by providing a generic framework to optimize a user-defined criterion such as normals, colors,...

**Required Skills:** C++, geometric data structures, generic programming.

**Contact:** jane.tournois@geometryfactory.com

**References**

- [1] Implicit fairing of irregular meshes using diffusion and curvature flow Desbrun, Meyer, Schroder, and Barr (1999).
- [2] High quality compatible triangulations Surazhsky and Gotsman (2004)

**Mentor(s):** Salles Viana Gomes de Magalhaes (Universidade Federal de Viçosa), Andrade Marcus (Universidade Federal de Viçosa), W. Randolph Franklin(Rensselaer Polytechnic Institute), Andreas Fabri(GeometryFactory)

PinMesh is a very fast algorithm with implementation to preprocess a
polyhedral mesh, also known as a multi-material mesh, in order to
perform 3D point location queries. PinMesh combines several innovative
components to efficiently handle the largest available meshes. CGAL also have a class for answering such queries, but it is not optimized for large meshes. The goal of this project is to integrate the code of PinMesh into CGAL so that it can be used
as an alternative implementation of `Side_of_triangle_mesh`

.

**Required Skills:** C++, generic programming.

**Contact:** andreas.fabri@cgal.org

**Mentor(s):** W. Randolph Franklin(Rensselaer Polytechnic Institute), Andreas Fabri(GeometryFactory)

*NearptD* is a nearest neighbor search
software that is using a uniform grid to enable the use of the GPU for doing faster queries.
CGAL provides a k-nearest neighbor data structure running only on the CPU. The goal of this project is
to replace in point set processing algorithm of CGAL the nearest neighbor implementation by the one of NearptD.
Benchmark will them be done to see if the replacement could be useful in practice. If so, a proper integration
should be done.

**Required Skills:** C++, generic programming, GPU.

**Contact:** andreas.fabri@cgal.org

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