Computing Smooth Quasi-geodesic Distance Field (QGDF) with Quadratic Programming. (October 2020)

• Record Type: Journal Article
• Authors: Cao, Luming; Zhao, Junhao; Xu, Jian; Chen, Shuangmin; Liu, Guozhu; Xin, Shiqing; Zhou, Yuanfeng; He, Ying
• Is Part Of: Computer aided design. Volume 127(2020)
• Publication Date: 2020-10
• Subjects: Smooth geodesic distance field -- Quadratic programming -- Convex optimization -- Defect-tolerant distances; 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.2020.102879
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Computing geodesic distances on polyhedral surfaces is an important task in digital geometry processing. Speed and accuracy are two commonly-used measurements of evaluating a discrete geodesic algorithm. In applications, such as parametrization and shape analysis, a smooth distance field is often preferred over the exact, non-smooth geodesic distance field. We use the term Quasi-geodesic Distance Field (QGDF) to denote a smooth scalar field that is as close as possible to an exact geodesic distance field. In this paper, we formulate the problem of computing QGDF into a standard quadratic programming (QP) problem which maintains a trade-off between accuracy and smoothness. The proposed QP formulation is also flexible in that it can be naturally extended to point clouds and tetrahedral meshes, and support various user-specified constraints. We demonstrate the effectiveness of QGDF in defect-tolerant distances and symmetry-constrained distances. Graphical abstract: Highlights: Our method is able to seek a trade-off between accuracy and smoothness. It can be easily extended to point clouds and tetrahedral meshes. It supports 3D models with density functions or anisotropic metric tensor fields. We present two applications: defect tolerant and symmetry driven geodesics.