Mesh Untangling for Problems with Topological Singularities

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 have been proposed in the last decades, this problem still persists. Recently we have proposed a penalty-based numerical optimization scheme [ACM Trans. Graph., 40(4) (2021)] that provably untangles 2D and 3D meshes with inverted elements by partially solving a finite number of unconstrained minimization problems under the efficiency assumption: constant relative reduction of the penalty function for fixed penalty parameters. We have identified key engineering counterexamples that violate the efficiency condition and thus block the untangling process. When topological singularities such as 2-coverings or general k-coverings are present in the mesh or appear during the untangling attempt, the penalty function exhibits sharp parasitic local minima outside the admissible set. This problem is particularly vexing when considering partially constrained mesh deformation problems. We propose an adaptive procedure that adds phantom mesh elements near topological singularities with careful choice of weights and allows to eliminate topological singularities by moving them out of the domain or by mutual annihilation. We demonstrate enhanced stability of the proposed untangling technique, which has the potential to make mesh untangling a routine operation.