Project Ideas

The CGAL Project is applying as a mentoring organization of the Google Summer of Code 2025. 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. For new project proposals, contact us at [email protected].

GSoC 2025 Projects

Enhancing the 2D Regularized Boolean Operation Demo

Mentor: Efi Fogel

Project description: The new demonstration program of the "2D Regularized Boolean Operations" package demonstrates various operations on polygons, such as, union, intersection, and Minkowski sum. It also demonstrates the application of several operations in a pipeline fashion. The demo has not been published yet; it requires a few enhancements, such as the support of Boolean operations on general polygons bounded by non-linear curves and a port to Qt6 (from Qt5).

Required Skills: Qt6, geometry, code development tools (e.g., git), and C++14 proficiency

Contact: [email protected]

Duration: 350h

Manifold Meshing with Guaranteed Smallest Edge Length

Mentor: Martin Skrodzki, Sven Oesau

Project description: Point cloud meshing is an important topic present in different fields of research and various applications such as reverse engineering, rapid prototyping, or architecture. While CGAL currently provides different meshing options via a Poisson approach, an Advancing Front algorithm, or a scale-space technique, the implemented solutions do not come with a guarantee on the output. Therefore, we propose the implementation of an algorithm that provides a guarantee for the output mesh to be both manifold and adhere to a minimum edge length. The latter contributes to triangle quality as it prevents slivers and other malformed triangles.

We propose to implement the algorithm as an additional option for meshing point sets with CGAL. The project can be extended to use the algorithm also for remeshing of existing meshes to improve their quality. Further, a preliminary feature detection step can be implemented to make the algorithm feature-preserving. These additional steps would make the algorithm a 350h project.

Resources:

The paper to be implemented: "Isotropic Point Cloud Meshing using unit Spheres (IPCMS)" (ArXiv Version, will be presented at the International Meshing Round Table 2024)
Supplementary Material to the paper
Already existing CGAL Reconstruction from Point Clouds using Poisson, Advancing Front, and Scale Space and the CGAL Polygonal Surface Reconstruction

Required Skills: C++17, Geometry Processing, Mesh Processing, Point Cloud Processing

Contact: [email protected], [email protected]

Duration: 175h (or 350h when also doing remeshing)

Tetrahedral Isotropic Remeshing Parallelization

Mentor: Jane Tournois

Project description:

The goal of this project is to parallelize the code of the Tetrahedral Remeshing algorithm available in CGAL. This multi-material tetrahedral remeshing algorithm [2] is based on local and atomic operations such as edge collapse, edge split and edge flip, that could be performed in parallel to improve the performances of the code. The 3D Triangulations [3] and Tetrahedral Mesh Generation package [4] provide a framework to implement mesh operations concurrently. The same framework will be used to parallelize the remeshing algorithm, with the Intel TBB library [5].

Resources:

[1] CGAL Tetrahedral Remeshing package
[2] The original publication Multi-Material Adaptive Volume Remesher
[3] CGAL 3D Triangulations
[4] CGAL Tetrahedral Mesh Generation package
[5] Intel Threading Building Blocks

Required Skills: C++17, Mesh Processing, Computational Geometry, Parallelism with TBB

Contact: [email protected]

Duration: 350h

Homotopy and homology loops on surfaces

Mentor: Enrico Puppo, Sébastien Loriot

Project description:

The project consists in implementing in CGAL algorithms for extracting homotopy and homology loops from triangle meshes representing surfaces of genus higher than zero. The implementation is based on known algorithms (see references); some (non-CGAL) code is available for these algorithms. A first algorithm extracts a minimal system of independent homotopy loops, each consisting of a polyline crossing the mesh, and all passing through a common vertex, called the source: this provides a basis for the homotopy. A second algorithm takes in input the system of loops and relaxes each loop independently, by freeing it from the source and contracting to a homotopic locally shortest loop; this provides a basis for the homology. The final API shall consist of a function in the CGAL library, which takes in input a mesh and provides either a system of either homotopy or homology loops in the form of polylines on the mesh.

Resources:

[1] [J. Erickson and K. Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proc. 16th ACM-SIAM Symp. Disc. Alg., Vol. 5. 1038–1046] (https://jeffe.cs.illinois.edu/pubs/pdf/gohog.pdf)
[2] S.-Q. Xin, Y. He, and C.-W. Fu. 2012. Efficiently Computing Exact Geodesic Loops within Finite Steps. IEEE Trans. Vis. Comp. Graphi. 18, 6 (2012), 879–889.
[3] C. Mancinelli, G. Nazzaro, F. Pellacini, and E. Puppo. 2022. b/Surf: Interactive Bézier Splines on Surfaces.IEEETrans.VIs.Comp.Graph(2022). (only Sec.5.1)
[4] BoolSurf: Boolean Operations on Surfaces M Riso, G Nazzaro, E Puppo, A Jacobson, Q Zhou, F Pellacini ACM Transactions on Graphics (TOG) 41 (6), 1-13 (only Sec.4.4 - Fig.16)

Required Skills: C++17, Geometry Processing, notions of Algebraic Topology

Contact: [email protected]

Duration: 175h

Robust surface networks discretization

Mentor: Simon Lopez, Sébastien Loriot

Project description:

The efficient discretization of implicit surface networks is of importance for many applications ranging from traditional CAD to medical imagery or geological modeling. Though CGAL provide the Mesh_3 package to approximate generic implicit surfaces, the algorithm requires the detection of all surfaces intersections beforehand to provide good quality results. Nevertheless, in many practical situations, it is perfectly acceptable to approximate implicit functors by piecewise linear functions on a given mesh. Consequently, the first goal of the project will be to implement the algorithm of the paper "Robust computation of implicit surface networks for piecewise linear functions" by Du et al. [1] to discretize implicit surface networks. The implementation will rely on the CGAL 3D linear cell complex structure [2] to keep track of discretization and of the splitting of some simplicial cells into smaller parts. The existing algorithm will be adapted to take into account boolean relations between surfaces and otpimizing out the evaluation of some functors. The second part of the project will be devoted to taking into account the discontinuities of a subset of implicit functors along specific network surfaces.

Resources:

Required Skills: C++17, Geometry Processing, Mesh Processing

Contact: [email protected], [email protected]

Duration: 350h

Enhanced Dual Contouring

Mentor: Mael Rouxel-Labbé, Pierre Alliez

Project description:

A previous GSoC launched the process of adding classic contouring methods to CGAL: Marching Cubes and Dual Contouring. This packaged is about to be finalized and will be integrated soon into CGAL (https://github.com/CGAL/cgal/pull/6849). Many enhancements exist for the Dual Contouring method to improve its robustness: placement of the dual point, improved conditioning of the SVD matrices, or on-the-fly refinement of the underlying grid [1]. Another aspect is speed, as a grid structure is well adapted to GPU computation.

The project will first focus on manifold contouring methods and robustness in standard C++. If there is time and the candidate has the required skills, we can also explore runtime aspects and the conversion to a GPU implementation. If there is time and the candidate does not have the required skills, we shall explore the implementation of other contouring methods such as Dual Marching Cubes [2].

Resources:

Required Skills: C++17, Dual Contouring, linear algebra / quadric error metrics, possibly GPU algorithms

Contact: [email protected]

Duration: 350h

Information Candidates Should Supply

The application process has several steps. Before contacting anybody verify that you are eligible (Check section 7.1 of the official rules). 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.
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?