CGAL - Project Ideas for the Google Summer of Code 2015

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.

In 2015 our application has been rejected.

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:

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:

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:

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:

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.

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:

[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

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:

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:

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:

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?