|Table of Contents|

Rapidly calculating approximate geodesic distance based on metric multidimensional scaling


Research Field:
Publishing date:


Rapidly calculating approximate geodesic distance based on metric multidimensional scaling
Chen HonghuaPang Mingyong
Department of Educational Technology,Nanjing Normal University,Nanjing 210097,China
digital geometry processing triangular meshes high-dimensional embedding geodesic distances metric multidimensional scaling
A novel algorithm is proposed for rapidly calculating approximate geodesic distance between any vertex pair on a triangular mesh based on the metric multidimensional scaling(MMDS)technique.The geodesic calculating on the surface of a given mesh in the low-dimensional space is transformed into the Euclidean distance computing in a high-dimensional Euclidean space.The given mesh is decimated to its simplified version,then all geodesic distances are calculated on the original mesh only for the vertex pairs of the simplified mesh,and subsequently the simplified mesh is embeded into a high-dimensional space according to the computed distances by employing the MMDS.Regarding the vertices of the simplified mesh as control points,the remaining vertices of the original mesh is embeded into the high-dimensional space by using the least square method.Finally the Euclidean distances are calculated in the high-dimensional Euclidean space to express the approximate geodesic distances between any two points in the originat mesh.Experiments show that the method is robust and can deal with different models with various complexities of topology and geometry,and it has ability to quickly calculate the approximate geodesic distance between any two points with a pre-defined precision on 3D mesh models.


[1] Liang L,Szymczak A,Wei M.Geodesic spin contour for partial near-isometric matching[J].Computers & Graphics,2015,46:156-171.
[2]Taimouri V,Hua J.Deformation similarity measurement in quasi-conformal shape space[J].Graphical Models,2014,76(2):57-69.
[3]Tung T,Matsuyama T.Geodesic mapping for dynamic surface alignment[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(5):901-913.
[4]Lian Z,Godil A,Sun X,et al.CM-BOF:visual similarity-based 3D shape retrieval using clock matching and bag-of-features[J].Machine Vision & Applications,2013,24(8):1685-1704.
Zhou Yan,Liu Shengjun,Jin Xiaogang,et al.Geodesic-based constrained deformations for polygonal mesh models[J].Journal of Software,2007,18(6):1543-1552.
[6]Liu Y J,Chen Z,Tang K.Construction of iso-contours,bisectors and Voronoi diagrams on triangulated surfaces[J].IEEE Transactions on Software Engineering,2010,33(8):1502-1517.
[7]Chen J,Han Y.Shortest path on the polyhedron,Part I[J].International Journal of Computational Geometry & Application,1996,6(2):360-369.
[8]Kaneva B,O'Rourke J,Kaneva B.An implementation of Chen & Han's shortest paths algorithm[C]//Proceedings of 21st Canadian Conference on Computational Geometry.Fredericton,Canada:University of New Brunswick,2000:139-146.
[9]Ying X,Xin S Q,He Y.Parallel Chen-Han(PCH)algorithm for discrete geodesics[J].ACM Transactions on Graphics,2013,33(1):57-76.
[10]Mitchell J S,Mount D M,Papadimitriou C H.The discrete geodesic problem[J].SIAM Journal on Computing,1987,16(4):647-668.
[11]Surazhsky V,Surazhsky T.Fast exact and approximate geodesics on meshes[J].ACM Transactions on Graphics,2005,24(3):553-560.
[12]Liu Y J,Zhou Q Y,Hu S M.Handling degenerate cases in exact geodesic computation on triangle meshes[J].Visual Computer,2007,23(9-11):661-668.
[13]Liu Y J.Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures[J].Computer-Aided Design,2013,45(3):695-704.
[14]Xu C X,Wang T,Liu Y J,et al.Fast wavefront propagation for computing exact discrete geodesics on meshes[J].IEEE Transactions on Visualization & Computer Graphics,2015,21(7):822-834.
[15]Kanai T,Suzuki H.Approximate shortest path on a polyhedral surface and its applications[J].Computer-Aided Design,2001,33(11):801-811.
[16]Ying X,Wang X,He Y.Saddle vertex graph:a novel solution to the discrete geodesic problem[J].ACM Transactions on Graphics,2013,32(6):2504-2507.
[17]Kimmel R,Sethian J A.Computing geodesic paths on manifolds[J].Proceedings of the National Academy of Sciences of the United States of Amercia,1998:8431-8435.
[18]Novotni M,Klein R.Computing geodesic distances on triangular meshes[C]//Proceedings of WSCG.Plzen,Czech:University of West Bohernia,2002:341-347.
[19]Crane K,Weischedel C,Wardetzky M.Geodesics in heat:a new approach to computing distance based on heat flow[J].ACM Transactions on Graphics,2013,32(5):13-15.
[20]Buja A,Swayne D F,Littman M L,et al.Data visualization with multidimensional scaling[J].Journal of Computational and Graphical Statistics,2008,17(2):444-472.
[21]Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensional reduction[J].Science,2000,290(12):2319-2323.
[22]Roweis S T,Saul L K.Nonlinear dimensionality analysis by locally linear embedding[J].Science,2000,290(12):2323-2326.
Wang Xiaokan,Mao Xia.Human face analysis with nonlinear manifold learning[J].Journal of Electronics & Information Technology,2011,33(10):2531-2535.
Cao Mingming,Gan Zongliang,Cui Ziguan,et al.Novel neighbor embedding face hallucination based on non-negative weights and 2D-PCA feature[J].Journal of Electronics & Information Technology,2015,37(4):777-783.
[25]Sorkin O,Cohen-Or D.Least-squares meshes[C]//Proceedings of Shape Modeling International.Genova,Italy:IEEE,2004:191-199.
Pan Zhigeng,Pang Mingyong.Survey for decimation of geometric meshes[J].Journal of Jiangsu University(Natural Science),2005,26(1):67-71.
[27]Schroeder W J,Zarge J A,Lorensen W E.Decimation of triangle meshes[J].Computer Graphics,1992,26(2):65-70.
Zhou Kun,Pan Zhigeng,Shi Jiaoying.Mesh simplification algorithm based on triangle collapse[J].Chinese Journal of Computers,1998,21(6):506-513.
[29]Hoppe H,Derose T,Duchamp T,et al.Mesh optimization[C]//Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York,US:ACM,1993:19-26.
[30]Garland M,Heckbert P.Surface simplification using quadric error metrics[J].Computer Graphics,1997,31(3):209-216.
[31]Varadhan S R S.On the behavior of the fundamental solution of the heat equation with variable coefficients[J].Communications on Pure and Applied Mathematics,1967,20(2):431-455.
[32]Botsch M.On linear nariational surface deformation methods[J].IEEE Transactions on Visualization & Computer Graphics,2008,14(1):213-230.


Last Update: 2016-04-30