Skip to content

GSoC_2020

Jump to bottom Edit New page
Mael Rouxel-Labbé edited this page Mar 28, 2024 · 1 revision

Table of Contents

GSoC 2020 Accepted Projects

The CGAL Project was a mentoring organization of the Google Summer of Code 2020. Check out the 6 successful projects there.

GSoC 2020 Projects

Below are the project ideas that were proposed during the Google Summer of Code 2020.

More C++11 in CGAL

Mentor: Dmitry Anisimov

Project description: Starting with the latest release we can introduce C++11 and C++14 features such as move semantics into CGAL. We will prioritize on the packages as well on which features to introduce, and it has to be done in a way that avoids breaking backward compatibility. This project does need a fair understanding what geometric algorithms are about, but you must master C++11 already, and experience in geometric computing is only a plus.

Required Skills: C++11, C++14

Contact: [email protected]

Enhancing the 2D Arrangement Demo (1)

Mentor: Efi Fogel

Project description: Currently the demo supports (linear) segments, polylines, conic arcs, linear curves, circular arcs, and algebraic curves to some extent. 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: Computational geometry, C++, generic programming, 3D Graphics.

Contacts: [email protected]

Enhancing the 2D Arrangement Demo (2)

Mentor: Efi Fogel

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: Computational geometry, C++, generic programming

Contacts: [email protected]

Enhancing the 2D Regularized Boolean Set Operations Demo

Mentor: Efi Fogel

Project description: The "2D Regularized Boolean Set Operations" package consists of the implementation of Boolean set-operations on point sets bounded by x-monotone curves in 2-dimensional Euclidean space. In particular, it contains the implementation of regularized Boolean set-operations, intersection predicates, and point containment predicates. The demo program demonstrates all operations of this package and later on of the 2D Minkowski sum package as well.

This project is an excellent project for a brilliant student who wishes to gain experience with developing applications from an early stage using CGAL, Boost, and Qt5 (among the other). The demo was developed as a project of GSoC last year, and it is in its diapers, sort of speaking, so there is plenty of room for forward thinking without to much uprooting.

Required Skills: Computational geometry, C++, generic programming

Contacts: [email protected]

Test of Simplicity for a Cycle on a Surface

Mentor: Guillaume Damiand, Francis Lazarus

Project description: The new package "Surface mesh topology" will be available in the next CGAL release. It is concerned with the computation of topological invariants of curves on surfaces. The goal of this project is to add a new functionality to this package in order to decide if an input cycle on a given surface can be continuously deformed to a simple curve, i.e. a curve without self-intersection. The goal is to implement the algorithm described in this paper https://arxiv.org/pdf/1511.09327 (Computing the Geometric Intersection Number of Curves. Vincent Despré and Francis Lazarus. Journal of the ACM 66(6), Article 45, Nov. 2019.). The implementation will strongly rely on the current package functionality for the homotopy test.

Another interesting possibility could be to add a new functionality to this package in order to repair mesh surfaces that contain undesired non-trivial topology (small handles or tunnels). A first step is to compute a shortest cycle that is essential on a given surface, i.e. that is neither deformable to a point nor to a boundary cycle of the surface. An algorithm for this task in this paper http://people.cs.uchicago.edu/~pworah/essential.pdf (Computing the shortest Essential Cycle. P. Worah and J. Erickson. Discrete and Computational Geometry, 2010.).

See also: Removing excess topology from isosurfaces, Z Wood, H Hoppe, M Desbrun, P Schröder - ACM Transactions on Graphics, Vol. 23, No. 2, April 2004, Pages 190–208.

Required Skills: Computational geometry, C++, generic programming

Contacts: [email protected] [email protected]

Improve CGAL basic viewer

Mentor: Guillaume Damiand

Project description: Since CGAL 4.13, a basic viewer is provided in CGAL in order to visualize different CGAL data structures. For now, this viewer is available for Polyhedral Surface, Surface Mesh, Linear Cell Complex, 2D Triangulations, 3D Triangulations, 3D point set, 2D polygon, 2D polygon with hole, Voronoi Diagram, Periodic 2 Triangulation 2, Nef Polyhedron, Arrangement 2 (only for traits classes segment, linear arc, circular arc and conic).

The goal of this project is to improve this basic viewer and improve its integration in CGAL. For that, the following possibilities are considered:

  • when the viewer is in 3D, add a possibility to add and move a clipping plane in order to visualize the intertior of 3D objets;
  • allow to add transparent faces in the viewer;
  • improve the viewer for Arrangement 2 to deal with all the possible traits classes;
  • improve the documentation of the basic viewer in the user manual and add one example for draw in all (?) cgal packages;
  • start to develop an external basic viewer in a client browser which will communicate to a CGAL server.

Required Skills: C++, generic programming

Contact: [email protected]

New Octree Package

Mentor: Simon Giraudot

Project description: The efficient RANSAC algorithm from the Shape Detection package is internally using an octree. The first goal of this project is to extract this implementation details into its own package. While doing this, the code will have to be extended to handle different kind of primitives, like the AABB-tree package does. In practice, surface meshes and points/segments/triangles soups has to be handled by default. The second part of this project is to identify alternative existing implementation (OpenVDB, PCL, ...) and evaluate them against the new CGAL octree package. Finally, if it make senses, wrappers to the best existing implementation can be written to make it available through a similar API as the package.

Required Skills: C++, generic programming

Contact: [email protected]

SFCGAL Improvements

Mentors: Hugo Mercier and Sébastien Loriot

Project description: SFCGAL is a C++ wrapper library around CGAL with the aim of supporting ISO 19107:2013 and OGC Simple Features Access 1.2 for 3D operations. The purpose of this project is to globally improve the code:

  • improve the compatibility with recent versions of CGAL. This includes updating the cmake script, replacing the usage of deprecated features,...
  • speeding up validity checks, this tests being called before any function call in PostGIS in order to check the validity of input.
  • replace wherever it is possible Exact_predicates_exact_constructions_kernel with Exact_predicates_inexact_constructions_kernel. A first good candidate is triangulations.

The particularity of this project is that it involves two different libraries but the student will mainly contribute to SFCGAL.

Required Skills: C++, PostGIS

Contact: [email protected] and [email protected]

Extend CGAL Point Cloud Registration to Multiple Objects.

Mentor(s): Nicolas Mellado and Simon Giraudot

Project description: Wrappers for global and local registration of point clouds were recently added in the CGAL library (GSoC 2019). In the current version, registration can only be performed between two point-clouds. The goal of this project is to extend the package to multiple point clouds, by implementing into OpenGR the approach described in the following paper: Global Registration of Multiple Point Clouds Using Semidefinite Programming, K. N. Chaudhury, Y. Khoo, and A. Singer, SIAM J. Optim., 25(1), 468–501. (34 pages).

Required Skills: C++, generic programming

Contact: [email protected] and [email protected]

Use Embree for Ray Shooting

Mentor: Andreas Fabri

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

Contact: [email protected]

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 [email protected]:

  • Project:

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

  • Personal data:

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

Previous Project Ideas and Successful Projects

Home

Home

General Information

Developer Resources

Maintainer Resources

Clone this wiki locally