Our application has been rejected this year.
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.
First section to read: Information Candidates Should Supply
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
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:
Fix and enhance various small features in the 2D Arrangements package:
Required Skills: C++, templates, Boost
Contact: efifogel@gmail.com
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
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
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
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): 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/
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
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
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
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
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
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
