Mesh Untangling for Problems with Topological Singularities

Overview & Synopsis

Mesh untangling is still a hot topic in applied mathematics. Tangled or folded meshes appear in many applications involving mappings or deformations. Despite the fact that a large number of mesh untangling strategies was proposed during the last decades, this problem still persists. Recently we have proposed a penalty-based numerical optimization scheme [GKK + 21] that provably untangles 2d and 3d meshes with inverted elements by partially solving a finite number of unconstrained minimization problems using efficiency assumption: constant relative reduction of penalty function for fixed penalty parameter. We have identified key engineering counterexamples which violate the efficiency condition and thus block untangling process. When such topological singularities as 2-coverings or general k-coverings are present in the mesh or appear during untangling attempt the penalty function reveals sharp parasitic local minima outside admissible set. This problem is particularly vexing when partially constrained mesh deformation problems are considered. We suggest adaptive procedure which adds phantom mesh elements near topological singularities with careful choice of weights and allows to eliminate topological singularities by moving them outside the domain or by mutual annihilation. We demonstrate enhanced stability of suggested untangling technique which has a potential to make untangling a routine operation over meshes.