Not so HOT Triangulations. (May 2023)

• Record Type: Journal Article
• Authors: Mitchell, Scott A.; Knupp, Patrick; Mackay, Sarah; Deakin, Michael F.
• Is Part Of: Computer aided design. Volume 158(2023)
• Publication Date: 2023-05
• Subjects: Mesh quality -- Optimization -- HOT Hodge-Optimized Triangulations; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2023.103497
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We propose primal–dual mesh optimization algorithms that overcome shortcomings of the standard algorithm while retaining some of its desirable features. "Hodge-Optimized Triangulations" defines the "HOT energy" as a bound on the discretization error of the diagonalized Delaunay Hodge star operator. HOT energy is a natural choice for an objective function, but unstable for both mathematical and algorithmic reasons: it has minima for collapsed edges, and its extrapolation to non-regular triangulations is inaccurate and has unbounded minima. We propose a different extrapolation with a stronger theoretical foundation, and avoid extrapolation by recalculating the objective just beyond the flip threshold. We propose new objectives, based on normalizations of the HOT energy, with barriers to edge collapses and other undesirable configurations. We propose mesh improvement algorithms coupling these. When HOT optimization nearly collapses an edge, we actually collapse the edge. Otherwise, we use the barrier objective to update positions and weights and remove vertices. By combining discrete connectivity changes with continuous optimization, we more fully explore the space of possible meshes and obtain higher quality solutions. Graphical abstract: Highlights: HOT (Hodge Optimized Triangulations) energy bounds the discretization error, but optimization using it as the objective function behaves badly. Our new metrics that normalize the energy, and have barriers to inversion, are better behaved. Extrapolating HOT to non-regular meshes is continuous, but can miss local minima and lead to oscillations. Our optimization framework combines continuous position and weight optimization with discrete connectivity changes.