CGAL Projects page for the Google Summer of Code 2015

Since 2010, the CGAL Project was 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 2014.

Summary:

First section to read: Information Candidates Should Supply

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

Use Embree for Ray Shooting

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

Adding Better I/O for the CGAL Library

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:

• 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

Adding a Parallel Version of the Edge Simplification Algorithm

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

Finalizing a Package for 2D Triangulations on the Sphere

Mentor(s): from INRIA Nancy - Grand Est - LORIA and from GeometryFactory

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

Enhancing the 2D Arrangements Package

Mentor(s): from the Applied Computational Geometry Lab, Tel Aviv University

Project description:

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

Improving the Polyhedron Demo

Mentor(s): from GeometryFactory and from GeometryFactory

Project description:

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

Dynamic Attributes for Combinatorial Maps

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

Project description:

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

Implementation of a Generic Bounding Volume Hierarchy (BVH)

Mentor(s): from TU Braunschweig

Project description:

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

Visibility Computation in 2.5D Terrains

Mentor(s): from TU Braunschweig

Project description:

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

Update Packages to Use the BGL API

Mentor(s): from GeometryFactory

Project description:

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

Tool to Compare the Output of Two Runs of Doxygen

Mentor(s): from GeometryFactory

Project description:

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

Intersection of a Power diagram with a triangulation in 2D

Mentor(s): from CNRS at Ceremade, Université Paris-Dauphine and from GeometryFactory

Project description:

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.

Required Skills: C++, templates, some basic maths

Fixing and Enhancing 2D Regularized Boolean Operations

Mentor(s): and Oren Zalsman from the Applied Computational Geometry Lab, Tel Aviv University

Project description:

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.

Reworking Intersection Functions

Mentor(s): from GeometryFactory

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

Parallel Implementation of a Point Set Reconstruction Algorithm

Mentor(s): from GeometryFactory and Raphaëlle Chaine from CNRS/Université de Lyon

Project description:

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

Create a bridge between the available Github "webhooks", and the usual Git hook scripts

Mentor(s): and Sébastien Loriot from GeometryFactory

Project description:

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

3D Mesh Generation - Detect and handle small geometric features

Mentor(s): from GeometryFactory and Clément Jamin from Inria Sophia-Antipolis

Project description:

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

Statistical mechanics of hard spheres

Mentor(s): from ESPCI and from INRIA Nancy - Grand Est - LORIA

Project description:

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

Information Candidates Should Supply

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

Project

1. 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.
2. Provide a proposal of a technical solution with your envisioned methodology. The more detailed the better.
3. Explain how the solution will be available to the user, in which form. Do not forget the documentation, unitary tests and cross-platform aspects.
4. 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.
5. Provide a formal commitment that you will be involved full time on the GSoC. This is absolutely mandatory.

Personal data

1. First name, last name, affiliation and geographical location.
2. A brief list of the main studies and programming courses attended, with ranking.
3. List of the most important software projects contributed and success.
4. Which are your best skills in terms of programming and scientific computing?
5. In general what is your taste in terms of programming? language, methodology, team work, etc.
6. Is there anything that prevents you from working full time on the project during the program period?
7. 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?
8. Are you more interested in the theory/scientific aspect of CGAL, or do you feel more like a hacker?
9. What are your long-term wishes in terms of job?

A mailto:

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