Greedy Cut Construction for Parameterizations. (13th July 2020)

• Record Type: Journal Article
• Authors: Zhu, Tianyu; Ye, Chunyang; Chai, Shuangming; Fu, Xiao‐Ming
• Is Part Of: Computer graphics forum. Volume 39:Number 2(2020)
• Page Start: 191
• Page End: 202
• Publication Date: 2020-07-13
• Subjects: CCS Concepts -- Computing methodologies → Shape modeling; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13923
• Languages: English
• ISSNs: 0167-7055

Abstract

Abstract: We present a novel method to construct short cuts for parameterizations with low isometric distortion. The algorithm contains two steps: (i) detect feature points, where the distortion is usually concentrated; and (ii) construct a cut by connecting the detected feature points. Central to each step is a greedy method. After generating a redundant feature point set, a greedy filtering process is performed to identify the feature points required for low isometric distortion parameterizations. This filtering process discards the feature points that are useless for distortion reduction while still enabling us to obtain low isometric distortion. Next, we formulate the process of connecting the detected feature points as a Steiner tree problem. To find an approximate solution, we first successively and greedily produce a collection of auxiliary points. Then, a cut is constructed by connecting the feature points and auxiliary points. In the 26, 299 test cases in which an exact solution to the Steiner tree problem is available, the length of the cut obtained by our method is on average 0.17% longer than optimal. Compared to state‐of‐the‐art cut construction methods, our method is one order of magnitude faster and generates shorter cuts while achieving similar isometric distortion.