CGAL Project

Mentors: Student: Yury Elkin

This project investigates GPU-accelerated approaches for spatial searching and mesh intersection in CGAL, a widely used computational geometry library. These operations are fundamental to applications such as collision detection, mesh processing, and geometric querying, but are currently limited by CPU-based performance, especially for large or dense datasets. The core idea is to leverage the massive parallelism of GPUs to accelerate the broad-phase of spatial queries, where potential interacting primitive pairs are identified. These candidate pairs are then refined using CGAL’s exact geometric predicates to preserve robustness and correctness. The project will explore multiple architectural designs, including hybrid GPU–CPU pipelines, fully GPU-based approaches, and alternative spatial data structures such as bounding volume hierarchies and spatial grids. An initial exploration phase will compare these approaches across diverse input configurations (e.g., overlapping vs non-overlapping meshes) to identify the most effective design. The final outcome will be a modular and reusable GPU-accelerated spatial searching framework integrated with CGAL. Deliverables include a prototype implementation of selected GPU-based spatial data structures, a candidate pair generation system, integration with CGAL’s exact predicates, and a comprehensive benchmarking suite evaluating performance, scalability, and robustness across different workloads.

Mentors: Student: Iason Manolas

Iteratively reshaping the cells of a 3D mesh to improve quality for simulations like finite element analysis — is computationally expensive: large meshes can take hours on a single CPU core. CGAL provides a widely used implementation, and GSoC 2025 built the infrastructure to run it in parallel, achieving a ~28% speedup on large meshes. Two problems remained: threads spent most of their time waiting to access the mesh rather than doing useful work, and the parallel version produced lower mesh quality than the sequential one. The 2025 code also never made it into the official CGAL repository. This project fixes both problems and introduces a new scheduling strategy: instead of rigidly applying all splits, then all collapses, then all flips, then all smooths, a unified priority queue ranks every candidate operation by its estimated quality improvement and always applies the most beneficial one first. This has the potential to reach the same final quality in fewer operations and has not previously been applied to tetrahedral remeshing.

Mentors: Student: Rajdeep Singh Kushwaha

CGAL's Basic Viewer provides one-call visualization of any CGAL data structure via draw(), but its OpenGL shader system has concrete user-facing bugs: edges disappear at certain zoom levels due to a numerically unstable inverse(u_Mvp) call in the geometry shader (#9292); edge width and vertex size are computed from the bounding box diagonal, producing hair-thin or geometry-obscuring results depending on object scale (#9327); 2D/3D camera transitions miscompute orthoCoef, breaking orthographic display (#5334); and the OpenGL < 4.3 compatibility path renders solid black (#6754, already fixed in my PR #9399). I will redesign the edge rendering pipeline to operate entirely in clip/NDC space, replace the bounding-box-based sizing with a viewport-relative pixel metric, fix camera transitions, add optional fragment-shader anti-aliasing, and produce a comparison report analyzing how MeshLab (VCGlib) and ParaView (VTK) solve wide-line rendering. I have already shipped three PRs into the Basic Viewer shader system and have 16 PRs on CGAL overall. Deliverables: robust clip-space edge shader, correct initial sizing, depth-correct edges, anti-aliased edges, updated OpenGL < 4.0 fallback path, MeshLab/ParaView comparison report, and regression tests. All changes backward-compatible with the existing draw() API.

Mentors: Student: Utkarsh Khajuria

The current CGAL Python bindings expose powerful computational geometry algorithms, but they've accumulated real usability problems: method parameters show up as arg0, arg1, arg2 rather than meaningful names, docstrings are either absent or embedded so deeply inside binding code that they obscure the logic itself, CGAL's Named Parameters system isn't available from Python at all, and the CI pipeline isn't running. More critically, I found and documented 7 crash scenarios where Python objects outlive freed C++ DCEL memory → situations that kill the interpreter with a segfault instead of raising a Python exception. Over the past three months I've been working directly in the codebase building the foundation for this project. I've added nb::arg() parameter names to AOS2 binding methods, written inline docstrings following CGAL's own documentation style, built a 7-flag CMake check system aligned 1:1 with CGAL's macro structure, and validated a working 8-kernel CI pipeline before this proposal was even submitted. I've also worked through the Named Parameters challenge far enough to identify the property map type-bridge problem → the part that makes Weeks 7–8 genuinely hard. The deliverables for the 12-week program are: complete named parameter coverage across AOS2 binding files, full docstring coverage for AOS2 methods, 7 CGAL-aligned CMake precondition flags with fixes contributed upstream to CGAL C++, Python-accessible Named Parameters for key PMP functions (compute_vertex_normals, smooth_mesh, triangulate_faces), bindings for at least one currently unbounded package, and a production-ready 8-kernel CI pipeline with integrated test coverage.

Mentors: Student: Théo Tyburn

Some packages in CGAL need to compute the intersections of segments, rays, or lines with an implicit function. This is generally done through naive bisection algorithms. For some configurations however, we know that the implicit function is a signed distance field (offset meshing, alpha wrapping, ...), or an harmonic function (Poisson reconstruction). In these configurations, we can do better than bisection algorithms. The goal of this project is to implement these marching algorithms for the 3D Mesh Generation, Poisson Surface Reconstruction, and Alpha Wrapping packages, and identify other relevant packages, and possible improvements on these algorithms.