Fast and Exact Discrete Geodesic Computation Based on Triangle-Oriented Wavefront Propagation

摘要

Computing discrete geodesic distance over triangle meshes is onernof the fundamental problems in computational geometry and computerrngraphics. In this problem, an effective window pruning strategyrncan significantly affect the actual running time. Due to its importance,rnwe conduct an in-depth study of window pruning operationsrnin this paper, and produce an exhaustive list of scenarios where onernwindow can make another window partially or completely redundant.rnTo identify a maximal number of redundant windows usingrnsuch pairwise cross checking, we propose a set of procedures tornsynchronize local window propagation within the same triangle byrnsimultaneously propagating a collection of windows from one trianglernedge to its two opposite edges. On the basis of such synchronizedrnwindow propagation, we design a new geodesic computationrnalgorithm based on a triangle-oriented region growing scheme. Ourrngeodesic algorithm can remove most of the redundant windows atrnthe earliest possible stage, thus significantly reducing computationalrncost and memory usage at later stages. In addition, by adoptingrntriangles instead of windows as the primitive in propagation management,rnour algorithm significantly cuts down the data managementrnoverhead. As a result, it runs 4-15 times faster than MMP andrnICH algorithms, 2-4 times faster than FWP-MMP and FWP-CH algorithms,rnand also incurs the least memory usage.