南京理工大学学报（自然科学版）2016，Vol.40Issue(2)：190-198,9.DOI:10.14177/j.cnki.32-1397n.2016.40.02.010
基于MMDS的近似测地距离快速求解算法
Rapidly calculating approximate geodesic distance based on metric multidimensional scaling
摘要
Abstract
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 ge-ometry, and it has ability to quickly calculate the approximate geodesic distance between any two points with a pre-defined precision on 3D mesh models.关键词
数字几何处理/三角网格模型/高维嵌入/测地距离/度量多维尺度分析Key words
digital geometry processing/triangular meshes/high-dimensional embedding/geodesic distances/metric multidimensional scaling分类
信息技术与安全科学引用本文复制引用
陈红华,庞明勇..基于MMDS的近似测地距离快速求解算法[J].南京理工大学学报（自然科学版）,2016,40(2):190-198,9.基金项目
国家自然科学基金(41271383 （）
60873175) （）
