Skip to content

Project Ideas

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

Table of Contents

The CGAL Project is a mentoring organization of the Google Summer of Code 2024. 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 2024 Projects

Point Sampling of Triangle Meshes with Poisson Disc Sampling

Mentor: Sébastien Loriot

Project description: For various applications, a good sampling of triangle meshes is required. While CGAL provides different sampling strategies in the Polygon Mesh Processing package, blue noise sampling is a sampling strategy providing a uniform distribution, especially interesting if coupled with geodesic properties. In this context, we propose to add to CGAL an implementation of the classical Poisson disk sampling on a triangle mesh. A warm up exercise could be to implementing such a function on a 2D and 3D triangle. Various resources are provided below.

Resources:

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

Contact: [email protected]

Duration: 175h

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

CGAL Python Bindings: type annotations and examples

Mentor: Efi Fogel

Project description: Recently we have developed a system that can be used to generate Python bindings for almost every function and class template in CGAL. The system can automatically generate, what is commonly referred to as stub files, which provides type-annotations for the Python wrappers. The type annotation stubs are generated by a script that is fed by files that describe the model-concept and concept-refinement relations. This project consists of two parts:

  1. Adding Python bindings that are currently missing.
  2. Completing the type annotation generation. (Populating the input data for the stub-file generation and enhancing the generation script if necessary.
  3. Porting of CGAL examples to Python.

Required Skills: code development tools (e.g., git), C++17 proficiency, cmake, and Python

Contact: [email protected]

Duration: 350h

Intrinsic Mollification Schemes for Enhancing the Heat Method Geodesics

Mentors: Hossam Saeed, Sébastien Loriot

Project description: CGAL's Heat Method package provides geodesic distance computation methods on triangle meshes, as well as the option of using an Intrinsic Delaunay Triangulation (IDT) of the mesh, which generally improves the quality and stability of the results. While this optional pre-processing step has recently been updated to include the basic intrinsic mollification scheme described in [1], the results in [2] show that: a. this scheme can be used independently from IDT to improve the computation and b. more-advanced schemes can be used to further improve the results. It is worth noting that Intrinsic Mollification is a general pre-processing step that can potentially improve the stability of other algorithms that use the cotangent Laplacian when computed on near-degenerate triangles, more details are found in [2].

Specifically, the goals of this project include:

  • Primarily:
    • Exposing Intrinsic Mollification as a separate option for the Heat Method Computation (Independent from IDT).
    • Implementing the more-advanced schemes described in [2] and carefully comparing them to the basic scheme (Both on IDT and independently).
  • Secondarily:
    • Investigating the possibility of using Intrinsic Mollification to improve the results of other CGAL packages and algorithms, and implementing it if possible.

References & Resources:

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

Contact: [email protected], [email protected]

Duration: 175h or 350h (if including secondary goals)

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:

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

Contact: [email protected], [email protected]

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

Hexahedral mesh generation

Mentor: Guillaume Damiand

Project description:

The goal of this project is to implement the method of the paper [1] "A template-based approach for parallel hexahedral two-refinement", Steven J. Owen, Ryan M. Shih, Corey D. Ernst; in CGAL. This method allows to generate a locally refined hexahedral mesh, starting from a coarse grid, and using different templates for refinement. It will be implemented using a 3D linear cell complex [2] as underlying data-structure. To implement the different templates, we can use the volumic Query-replace operation [3].

Resources:

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

Contact: [email protected]

Duration: 350h

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:

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

Contact: [email protected]

Duration: 350h

Vector graphics on surfaces

Mentor: Claudio Mancinelli, Sébastien Loriot

Project description:

The project consists in creating a Graphical User Interface (GUI) in CGAL supporting the algorithms proposed in [1],[2],and [3]. These algorithms allow the user to trace basic geometric primitives such as geodesics, Bézier and B-Spline curves (including rational ones) and geodesic polygons. Some of these algorithms are already implemented in CGAL (i.e, [1] and few constructions of [2]), the first goal of this project is to design a framework in which all these operations are supported and that they can be combined to decorate a surface. The GUI should mimic the behavior of classical drawing systems in 2D (e.g., Inkscape or Adobe Illustrator), i.e., it should allow editing operations on the geometric primitives via an intuitive click-and-drag procedure. The second goal consists in allow the user to extrude/carve the mesh using these geometric primitives as strokes. For example, it should be possible to carve the mesh along a given Bézier spline.

Resources:

Required Skills: C++17, Geometry Processing, Discrete Differential Geometry

Contact: [email protected], [email protected]

Duration: 175h

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:

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

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

Previous Project Ideas and Successful Projects

Home

Home

General Information

Developer Resources

Maintainer Resources

Clone this wiki locally