基于MMDS的近似测地距离快速求解算法  

Rapidly calculating approximate geodesic distance based on metric multidimensional scaling

作　　者：陈红华[1] 庞明勇[1] 

机构地区：[1]南京师范大学教育技术系,江苏南京210097

出　　处：《南京理工大学学报》2016年第2期190-198,共9页Journal of Nanjing University of Science and Technology

基　　金：国家自然科学基金(41271383;60873175)

摘　　要：通过运用度量多维尺度分析(Metric multidimensional scaling,MMDS)技术,将低维曲面上的测地距离计算转化为高维空间中的欧氏距离计算问题,提出一种快速求解三角网格上任意两点间近似测地距离的算法。首先对给定三角网格模型进行简化,得到原网格模型的简化版本。在原始网格模型上求取简化网格中所有顶点对的测地距离,并根据得到的测地距离将简化网格嵌入到高维空间中。运用最小二乘方法将原网格中其他顶点也嵌入到该高维空间。最后,在高维空间中计算顶点之间的欧氏距离来近似表示原网格上任意两点间的测地距离。实验表明,该文算法运行稳定,能够快速计算出不同网格模型上不同顶点间的近似测地距离。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. Re-garding 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 predefined precision on 3D mesh models.

关 键 词：数字几何处理 三角网格模型 高维嵌入 测地距离 度量多维尺度分析 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]