Skip to content

GSoC_2023

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 2023. 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 2023 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++14, Geometry Processing, Mesh Processing

Contact: [email protected]

Duration: 175h

Geodesic Distance Computation Improvements

Mentor: Mael Rouxel-Labbé

Project description: There exists within CGAL multiple tools to compute geodesic distances over a mesh such as the Heat Method and the Triangulated Mesh Shortest Path packages. There also exists a prototype implementation of the paper Practical anisotropic geodesy. The goal of this project is to investigate a new method proposed by Trettner. et al, Geodesic Distance Computation via Virtual Source Propagation, implement it and compare it to our existing methods in terms of speed and robustness.

Required Skills: Geometry Processing, C++14

Contact: [email protected]

Duration: 175h

Constraint-based Point Set Denoising

Mentor: Martin Skrodzki and Sven Oesau

Project description: An important part of the geometry processing pipeline consists of cleaning an input geometry. This input geometry usually comes in the form of a 3D point cloud, but also bears noise, i.e., the points have an offset from the surface from which they were acquired. While CGAL does provide two smoothing strategies as part of the Point Set processing package, these are not necessarily designed to denoise geometries with sharp features. In this context, we propose to add to CGAL an implementation of constraint-based point set denoising. A possible extension of the project would be to also implement the corresponding mesh denoising version.

Resources:

Required Skills: C++14, Geometry Processing, Linear Algebra

Contact: [email protected]

Duration: 175h (350h with the extension)

Approximated (Discrete) Centroidal Voronoi Diagrams

Mentors: Sébastien Loriot and Sébastien Valette

Project description: Approximated Centroidal Voronoi Diagrams (ACVD) [1] proposes a robust and efficient approach for mesh simplification. There already exists an implementation of the papers [2,3,4] using the VTK Library [1]. This project aims to implement the same functionalities via the CGAL library. The contribution can be incremental. Coding the simple uniform simplification algorithm [2] should be relatively easy, while more complex metrics (anisotropic, quadric-based) [3], and simplification with guarantees [4] are more demanding.

References:

  • [1] ACVD source code : https://github.com/valette/ACVD
  • [2] S. Valette and J.-M. Chassery, Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening, Computer Graphics Forum (Eurographics 2004 proceedings), Vol. 23, No. 3, September 2004, pp. 381-389. PDF
  • [3] S. Valette,J.-M. Chassery and R. Prost, Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi Diagrams, IEEE Transactions on Visualization and Computer Graphics, Volume 14, no. 2, pages 369-381, 2008. PDF
  • [4] M. Audette, D. Rivière, M. Ewend, A. Enquobahrie, and S. Valette, "Approach-guided controlled resolution brain meshing for FE-based interactive neurosurgery simulation", Workshop on Mesh Processing in Medical Image Analysis, in conjunction with MICCAI 2011., Toronto, Canada, pp. 176--186, 09/2011.

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

Contact: [email protected]

Duration: 350h

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.

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

Contact: [email protected]

Duration: 350h

Demonstrating 2D Arrangements Embedded on the Sphere

Mentor: Efi Fogel

Project description: Recently the "2D Arrangement" package of CGAL has been enhanced with the support of 2D arrangement of geodesic arcs embedded on the sphere. Demonstrating such an arrangement graphically requires rendering in three dimensions, a.k.a. 3D graphics. This project consists of two parts:

  1. Implementing a simple drawing program that displays any given arrangement
  2. Enhancing the 2D Arrangement demo program to display arrangements on the sphere

Required Skills: Qt5, geometry, 3D graphics, code development tools (e.g., git), and C++14 proficiency

Contact: [email protected]

Duration: 350h

Intrinsic Delaunay Triangulations

Mentor: Mael Rouxel-Labbé

Project description: Intrinsic Delaunay triangulations (IDT) are a way to improve the quality of the elements of a mesh through remeshing that preserves geometry. IDTs are employed deep within the CGAL Heat Method package. This project consists in generalizing Heat Method's IDT to a BGL Graph Adapter to make it usable within other types of mesh processing algorithms. IDT have further been improved in more recent papers, which our implementation could be enhanced with.

References:

Required Skills: Geometry Processing, C++14

Contact: [email protected]

Duration: 175h

Octree-based (Screened) Poisson Reconstruction

Mentors: Mael Rouxel-Labbé and Pierre Alliez

Project description: Poisson Surface reconstruction is one of the most classic surface reconstruction algorithms. An implementation exists within CGAL in the package Poisson Surface Reconstruction. Contrary to the seminal paper, our implementation is based on Delaunay triangulations rather than octrees, for historical reasons: at the time of the implementation, there was no octree within CGAL. Improvements have been made to the Poisson reconstruction method in newer papers, specifically the so-called Screened Poisson reconstruction. Unfortunately, this improvement does not translate very well to our triangulation-based implementation. In a very recent release, octrees have finally made it into CGAL. The scope of this project is to re-implement the current Poisson surface reconstruction method but using the CGAL octree as the underlying structure. If the project is progressing well, we will also implement the enhanced "Screened Poisson reconstruction" algorithm.

References:

Required Skills: Geometry Processing, C++14

Contact: [email protected]

Duration: 350h

Upgrading the 3D Demo to Qt6

Mentor: Andreas Fabri

Project description: All CGAL algorithms dealing with 3D objects are integrated in a GUI application, currently named the Polyhedron demo. While it was in the very beginning really only a demo to visualize a polyhedral surface, this software has grown into a powerful tool that is useful for CGAL developers and CGAL users.

By the end of May 2023, the latest version of Qt5 (version 5.15 will no longer be supported by qt.io, and all users should migrate to Qt6 as soon as possible. The goal of this project is to port all Qt code of CGAL from Qt5 to Qt6. A secondary goal will be to migrate our OpenGL code to the new Qt Shader Tools.

In addition, we have a list of small bugs that should be fixed, as well as several feature requests.

Required Skills: Qt6, OpenGL/Vulkan shaders

Contact: [email protected]

Duration: 175h or 350h

Clustering 3D point clouds

Mentors: Pierre Alliez, Mael Rouxel-Labbe

Project description: The CGAL library offers a component for point set processing. We have recently devised a novel algorithm (not yet published) for clustering 3D point clouds, enriched with unoriented normal attributes. Similar to the popular K-means algorithm, the clustering algorithm alternates partitioning and generator updating, where the generators are 3D points representative of the clusters. An optional step can derive a surface triangle mesh connecting the generators to obtain a concise mesh reconstruction algorithm. The objective of this project is to turn our research prototype into a novel component for the CGAL library, with a generic design, modular steps and a documentation for users and developers.

Required Skills: generic C++, 3D point clouds, knowledge of k-means clustering, basic knowledge in linear algebra

Contact: [email protected]

Duration: 175h

Add Curvature Adaptative Remeshing

Mentors: Jane Tournois and Sébastien Loriot

Project description: CGAL provides a way to isotropically remesh a triangle mesh using the function isotropic_remeshing() based on [1] (+ some internal enhancement to handle constrained edges, constrained vertices, ...). The goal of this project is to extend the function to incorporate curvature adaptative edge length as described in [2]. #4891 is the initial step containing the update of the API of the remeshing function to implement the new functionality.

Required Skills: C++14, Geometry Processing

Contact: [email protected]

Duration: 175h

Non-rigid Iterative Closest Point

Mentors: Roberto M. Dyke and Mael Rouxel-Labbe

Project description: Non-rigid Iterative Closest Point, or N-ICP for short, (as described [1]) is a classic method used for the registration of non-rigidly deforming shapes. Non-rigid registration seeks to find a series of transformations that aligns one surface to another. This process is a necessary step prior to performing tasks such as shape analysis, dynamic surface reconstruction, and object retrieval. As well as its simplicity, a key benefit of the N-ICP algorithm is its extensibility, allowing it to be adapted/enhanced for specific applications. Currently, there is no implementation of N-ICP within CGAL. This project seeks to develop a novel component for the CGAL library that follows the common design practices used in Open Source projects. For the novice in linear algebra, this project offers an excellent opportunity to be guided through the process of designing a large-scale linear system, and use linear solver libraries.

  • [1] Sofien Bouaziz, Andrea Tagliasacchi, Hao Li, and Mark Pauly. 2016. "Modern techniques and applications for real-time non-rigid registration," In SIGGRAPH ASIA 2016 Courses, Association for Computing Machinery. doi: 10.1145/2988458.2988490.

Required Skills: C++ proficiency, code development tools (e.g., git), basic knowledge of linear algebra (e.g., matrix multiplication, inner products)

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: 175h

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