A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented
by a triangle mesh T , the geodesic metric on T can be computed exactly using computational geometry
methods. Previous work for establishing the geodesic metric on T only supports using half-edge data
structures; i.e., each edge e in T is split into two halves (he1, he2) and each half-edge corresponds to
one of two faces incident to e. In this paper, we prove that the exact-geodesic structures on two halfedges
of e can be merged into one structure associated with e. Four merits are achieved based on the
properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures
can directly add the geodesic distance function without changing the kernel to a half-edge data structure;
(2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an onthe-
fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped
up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP
algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental
results show that when compared to the classic half-edge data structure, the edge-based implementation
of the MMP algorithm reduces running time by 44% and storage by 29% on average.
Liu Y, Fu Q, Liu Y, et al. A distributed computational cognitive model for object recognition[J]. Science in China Series F: Information Sciences, 2013, 56(9): 1-13.
Xu C, Wang T Y, Liu Y, et al. Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes[J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(7): 822-834.
Wang X, Ying X, Liu Y, et al. Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes[J]. Computer-aided Design, 2015: 51-61.
Yongjin Liu · Kai Tang. The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces. 2013.
S Biasotti · Andrea Cerri · Mostafa Abdelrahman · Masaki Aono · A Ben Hamza · Moumen T Elmelegy · A A Farag · Valeria Garro · Andrea Giachetti · Daniela Giorgi. Retrieval and classification on textured 3D models. 2014.
Liu Y. Semi-Continuity of Skeletons in Two-Manifold and Discrete Voronoi Approximation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(9): 1938-1944.
Cheng P, Miao C, Liu Y, et al. Solving the initial value problem of discrete geodesics[J]. Computer-aided Design, 2016: 144-152.
Wang Y, Yu K, Wang C C, et al. Spiral and conformal cooling in plastic injection molding[J]. Computer-aided Design, 2015: 1-11.
Qin Y, Han X, Yu H, et al. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation[J]. ACM Transactions on Graphics, 2016, 35(4).
Gong W, Liu Y, Tang K, et al. Approximate Delaunay mesh reconstruction and quality estimation from point samples[J]. Journal of Computational and Applied Mathematics, 2015, 274(1): 23-34.