DE-Path: A Differential-Evolution-Based Method for Computing Energy-Minimizing Paths on Surfaces. (September 2019)

• Record Type: Journal Article
• Authors: Ye, Zipeng; Liu, Yong-Jin; Zheng, Jianmin; Hormann, Kai; He, Ying
• Is Part Of: Computer aided design. Volume 114(2019)
• Page Start: 73
• Page End: 81
• Publication Date: 2019-09
• Subjects: Energy-minimizing paths -- Differential evolution -- Global solver; 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.2019.05.025
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Computing energy-minimizing paths that are general for different energy forms is a common task in science and engineering. Conventional methods adopt numerical solvers, such as conjugate gradient or quasi-Newton. While these are efficient, the results are highly sensitive with respect to the initial paths. In this paper we develop a method based on differential evolution (DE) for computing optimal solutions. We propose a simple strategy to encode paths and define path operations, such as addition and scalar multiplication, so that the discrete paths can fit into the DE framework. We demonstrate the effectiveness of our method on three applications: (1) computing discrete geodesic paths on surfaces with non-uniform density function; (2) finding a smooth path that follows a given vector field as much as possible; and (3) finding a curve on a terrain with (near-) constant slope. Highlights: We presented a method to solve a general shortest path problem on 2-manifold meshes. We proposed a map from discrete paths to density distributions on 2-manifold. We presented an application which is finding a path on a terrain with constant slope.