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 (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. See Computing the shortest Essential Cycle. P. Worah and J. Erickson. Discrete and Computational Geometry, 2010.



Shuhao Tan


  • Guillaume Damiand