CGAL - Project Ideas for the Google Summer of Code 2016

CGAL/cgal

Candidacy Status

Our application has been rejected this year.

Project Ideas

The CGAL Project applied as a mentoring organization for the Google Summer of Code 2016.

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.

Summary:

First section to read: Information Candidates Should Supply

  1. Adding a Parallel Version of the Edge Simplification Algorithm
  2. Reworking Intersection Functions
  3. Enhancing the 2D Arrangements Package
  4. Fixing and Enhancing 2D Regularized Boolean Operations
  5. Enhancing 2D Regularized Boolean Operations Demo
  6. Parallel Implementation of a Point Set Reconstruction Algorithm
  7. Create a Bridge Between the Available Github "webhooks", and the Usual Git Hook Scripts
  8. Finalizing a Package for 2D Triangulations on the Sphere
  9. Implementing a Package for the Point Cloud Registration Algorithm Super4PCS
  10. Sparse Eigenvalue Solver and Application to Diffusion Distances
  11. Improving the Point Set Shape Detection Component
  12. Robust Normal estimation for Point Clouds with Sharp Features
  13. Implementing a Package for Computation of Surface Maps.

Adding a Parallel Version of the Edge Simplification Algorithm

Mentor(s): Sebastien Loriot (GeometryFactory) and Clément 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 use a modified version of this algorithm to allow edges of a mesh to be simplified using parallel threads.

Required Skills: C++, Intel TBB

Contact: sebastien.loriot@cgal.org


Reworking Intersection Functions

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


Enhancing the 2D Arrangements Package

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

Project description:
Fix and enhance various small features in the 2D Arrangements package:

Required Skills: C++, templates, Boost

Contact: efifogel@gmail.com


Fixing and Enhancing 2D Regularized Boolean Operations

Mentor(s): Efi Fogel (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.

Contact: efifogel@gmail.com


Enhancing 2D Regularized Boolean Operations Demo

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

Project description:
Enhance the 2D Regularized Boolean Operations Demo with the following

Required Skills: C++, templates, and QT.

Contact: efifogel@gmail.com


Parallel Implementation of a Point Set Reconstruction Algorithm

Mentor(s): Sebastien Loriot and Raphaëlle Chaine

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
 http://liris.cnrs.fr/~rchaine/RECONSTRUCTION/sgp_chaine.pdf

The student will need to finalize the package and propose a way to parallelize this point set reconstruction algorithm following the CGAL's guidelines.


Required Skills: C++, parallel programming, Intel TBB

Contact: sebastien.loriot@cgal.org


Create a Bridge Between the Available Github "webhooks", and the Usual Git Hook Scripts

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


Finalizing a Package for 2D Triangulations on the Sphere

Mentor(s): Sébastien 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, 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/



Implementing a Package for the Point Cloud Registration Algorithm Super4PCS

Mentor(s): Simon Giraudot (GeometryFactory) and Nicolas Mellado (IRIT)

Project description:
This projects aims at integrating the existing Super4PCS implementation (http://github.com/nmellado/Super4PCS) as a CGAL package.

Required Skills: C++

Contact: simon.giraudot@geometryfactory.com, nicolas.mellado@irit.fr

Reference
[1] Nicolas Mellado, Dror Aiger, and Niloy J. Mitra. 2014. Super 4PCS Fast Global Pointcloud Registration via Smart Indexing. Comput. Graph. Forum 33, 5 (August 2014), 205-215. DOI=http://dx.doi.org/10.1111/cgf.12446



Sparse Eigenvalue Solver and Application to Diffusion Distances

Mentor(s): Pierre Alliez (Inria) and Jane Tournois (GeometryFactory)

Project description:
The eigen-structure of linear operators is relevant for a number of geometry processing algorithms on meshes such as pose-invariant shape signatures for shape retrieval, spectral embedding, parameterization of surface meshes, clustering, correspondence, diffusion distances and surface reconstruction. Popular operators include Laplace Beltrami (1st order and higher order) and distance matrices, the most frequent ones being defined as symmetric positive definite operators. In general we need to calculate a specific number of eigenvalues and eigenvectors of a large sparse square matrix A (smallest or largest), smaller than the size of A.

Recent advances on solvers through the Eigen and ARPACK-Eigen [1] C++ libraries makes it possible to add an eigenvalue solver in CGAL with little dependency, as both libraries are header-only. In addition, in ARPACK-Eigen the user only requires to define operations on matrix A such as a matrix-vector product. The library is particularly powerful when the matrix-vector product can be computed efficiently, which is the case when A is sparse.

The objective of this project is to implement a generic design for computing eigenvalues and eigenvectors of linear operators on surface meshes and point sets sampled on surfaces. We will first experiment with the Laplace-Beltrami operator to compute diffusion distance [2]. The heat diffusion kernel, derived from the spectral decomposition of M, provides a means to compute approximate geodesic distances at low computational cost. Such approximation can be leveraged in a wide range of potential applications.

Required Skills: C++. Knowledge of linear algebra and Laplace operators is a plus.

Contact: pierre.alliez@inria.fr

Reference
[1] ARPACK-Eigen is a redesign of the ARPACK software for large scale eigenvalue problems, built on top of Eigen: https://github.com/yixuan/arpack-eigen

[2] Diffusion distances: see https://en.wikipedia.org/wiki/Diffusion_map#Diffusion_distance


Improving the Point Set Shape Detection Component

Mentors: Simon Giraudot (GeometryFactory), Pierre Alliez (Inria) and Laurent Busé (Inria)

Project description:
The Shape Detection component implements an efficient RANSAC-based primitive shape detection algorithm for point sets with unoriented normals. Five types of primitive shapes are detected: plane, sphere, cylinder, cone and torus.

This component can be improved in three ways:

1. Connectivity constraint. To avoid generating shapes with fragmented support we enforce a connectivity constraint by considering only one connected component, referred to as cluster, selected as the one covering the largest number of inliers. While this constraint is efficiently met for developable shapes such as planes or cylinders, it renders the algorithm slow for non-developables shapes such as cones and torii. The objective is to devise a novel data structure and efficient algorithm to enumerate the connected components for cones and torii. This requires devising a parameterization method for these primitives, and dealing with degenerate cases.

2. Random shape generators. The current shape detection algorithm relies upon random generation of primitive shapes, given a small set of points and unoriented normals. Recent findings show that such generator can be made more efficient by requiring less contraints.

3. Other shape types. Other types can be detected through implementing a class deriving from the base shape class. The goal is to demonstrate such genericity by defining composed primitives such as a crease edge formed by two orthogonal planes, a corner formed by three mutually orthogonal planes, and 3D boxes.


Required Skills: C++. Knowledge of linear algebra is a plus.

Contact: pierre.alliez@inria.fr

Reference
[1] Point Set Shape Detection http://doc.cgal.org/latest/Point_set_shape_detection_3/index.html#Chapter_Point_Set_Shape_Detection



Robust Normal estimation for Point Clouds with Sharp Features

Mentors: Simon Giraudot (GeometryFactory), Alexandre Boulch (Onera)

Project description:
Boulch and Marlet devised an algorithm for estimating normals on unorganized point clouds that preserves sharp features [1]. This approach offers an excellent tradeoff between precision, speed, and robustness. In addition, the authors have implemented a prototype algorithm based on CGAL. Starting from this prototype, the goal is to convert it into an algorithm for the point set processing component of CGAL, with examples, tests and plugin for the polyhedron demo of CGAL.

Required Skills: C++.

Contact: simon.giraudot@geometryfactory.com

Reference
[1] https://sites.google.com/site/boulchalexandre/software


Implementing a Package for Computation of Surface Maps.

Mentors: Yaron Lipman(Weizmann Institute of Science), Andreas Fabri (GeometryFactory)

Project description:
Computing high quality mappings between surfaces is a core task in computer graphics, computer vision, medical imaging and related fields. This projects aims at implementing algorithms ([1],[2]) for computing bijective, low distortion mappings between surface-meshes. The implementation will consist of a couple of algorithms which follow the same three steps: i) cutting the meshes into disk topology; ii) embedding the meshes into a canonical domain and reducing the distortion of the embedding via optimization; iii) computing the surface map induced from the embeddings via an overlay procedure and/or lifting.

[1]  AIGERMAN, N., PORANNE, R., AND LIPMAN, Y. 2015. Seamless surface mappings. ACM Transactions on Graphics (TOG) 34, 4.
[2]  AIGERMAN, N., AND LIPMAN, Y. 2015. Orbifold tutte embeddings. ACM Trans. Graph. 34, 6.

Required Skills: C++, Geometry, Optimization


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?