The CGAL Project was a mentoring organization of the Google Summer of Code in 2017. Successful projects can be found here.
On this page we presented some project ideas for the Google Summer of Code 2017.
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
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:
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.
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
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
