Convex Quadratic Programming for Computing Geodesic Distances on Triangle Meshes

Shuangmin Chen (), Nailei Hei, Shun Hu, Zijia Yue and Ying He
Additional contact information
Shuangmin Chen: Qingdao University of Science and Technology, Qingdao 260061, China
Nailei Hei: Fudan University, Shanghai 200437, China
Shun Hu: Qingdao University of Science and Technology, Qingdao 260061, China
Zijia Yue: Qingdao University of Science and Technology, Qingdao 260061, China
Ying He: Nanyang Technologtical University, Singapore 639798, Singapore

Mathematics, 2024, vol. 12, issue 7, 1-19

Abstract: Querying the geodesic distance field on a given smooth surface is a fundamental research pursuit in computer graphics. Both accuracy and smoothness serve as common indicators for evaluating geodesic algorithms. In this study, we argue that ensuring that the norm of the triangle-wise estimated gradients is not larger than 1 is preferable compared to the widely used eikonal condition. Inspired by this, we formulate the geodesic distance field problem as a Quadratically Constrained Linear Programming (QCLP) problem. This formulation can be further adapted into a Quadratically Constrained Quadratic Programming (QCQP) problem by incorporating considerations for smoothness requirements. Specifically, when enforcing a Hessian-energy-based smoothing term, our formulation, named QCQP-Hessian, effectively mitigates the cusps in the geodesic isolines within the near-ridge area while maintaining accuracy in the off-ridge area. We conducted extensive experiments to demonstrate the accuracy and smoothness advantages of QCQP-Hessian.

Keywords: digital geometry processing; geodesic distance field; convex quadratic programming (CQP) (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/7/993/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/7/993/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:7:p:993-:d:1364671

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().