GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries
Authors: 
Qianwei Xia, Juyong Zhang, Zheng Fang, 
Jin Li, Mingyue Zhang, Bailin Deng, Ying HeAuthors Info & Claims
Pages 4930 - 4939
Abstract
In this article, we develop a novel method for fast geodesic distance queries. The key idea is to embed the mesh into a high-dimensional space, such that the euclidean distance in the high-dimensional space can induce the geodesic distance in the original manifold surface. However, directly solving the high-dimensional embedding problem is not feasible due to the large number of variables and the fact that the embedding problem is highly nonlinear. We overcome the challenges with two novel ideas. First, instead of taking all vertices as variables, we embed only the saddle vertices, which greatly reduces the problem complexity. We then compute a local embedding for each non-saddle vertex. Second, to reduce the large approximation error resulting from the purely euclidean embedding, we propose a cascaded optimization approach that repeatedly introduces additional embedding coordinates with a non-euclidean function to reduce the approximation residual. Using the precomputation data, our approach can determine the geodesic distance between any two vertices in near-constant time. Computational testing results show that our method is more desirable than previous geodesic distance queries methods.
References
[1]
X. Ying, X. Wang, and Y. He, “Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem,” ACM Trans. Graph., vol. 32, no. 6, 2013, Art. no.
[2]
J. S. Mitchell, D. M. Mount, and C. H. Papadimitriou, “The discrete geodesic problem,” SIAM J. Comput., vol. 16, no. 4, pp. 647–668, 1987.
[3]
K. Crane, C. Weischedel, and M. Wardetzky, “Geodesics in heat: A new approach to computing distance based on heat flow,” ACM Trans. Graph., vol. 32, no. 5, pp. 152:1–152:11, 2013.
[4]
Y. Y. Adikusuma, Z. Fang, and Y. He, “Fast construction of discrete geodesic graphs,” ACM Trans. Graph., vol. 39, no. 2, pp. 14:1–14:14, 2020.
[5]
K. Xuet al., “Partial intrinsic reflectional symmetry of 3D shapes,” ACM Trans. Graph., vol. 28, no. 5, 2009, Art. no.
[6]
D. Raviv, A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Full and partial symmetries of non-rigid shapes,” Int. J. Comput. Vis., vol. 89, no. 1, pp. 18–39, 2010.
[7]
G. Zigelman, R. Kimmel, and N. Kiryati, “Texture mapping using surface flattening via multidimensional scaling,” IEEE Trans. Vis. Comput. Graphics, vol. 8, no. 2, pp. 198–207, Second Quarter 2002.
[8]
A. Clements and H. Zhang, “Robust 3D shape correspondence in the spectral domain,” in Proc. IEEE Int. Conf. Shape Model. Appl., 2006, pp. 118–129.
[9]
A. Tevs, M. Bokeloh, M. Wand, A. Schilling, and H.-P. Seidel, “Isometric registration of ambiguous and partial data,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., 2009, pp. 1185–1192.
[10]
S.-Q. Xin, X. Ying, and Y. He, “Constant-time all-pairs geodesic distance query on triangle meshes,” in Proc. ACM SIGGRAPH Symp. Interactive 3D Graph. Games, 2012, pp. 31–38.
[11]
D. Panozzo, I. Baran, O. Diamanti, and O. Sorkine-Hornung, “Weighted averages on surfaces,” ACM Trans. Graph., vol. 32, no. 4, pp. 60:1–60:12, 2013.
[12]
J. Solomon, R. M. Rustamov, L. J. Guibas, and A. Butscher, “Earth mover's distances on discrete surfaces,” ACM Trans. Graph., vol. 33, no. 4, pp. 67:1–67:12, 2014.
[13]
A. Mead, “Review of the development of multidimensional scaling methods,” J. Roy. Statist. Soc., Ser. D Stat., vol. 41, no. 1, pp. 27–39, 1992.
[14]
J. Chen and Y. Han, “Shortest paths on a polyhedron,” in Proc. 6th Annu. Symp. Comput. Geometry, 1990, pp. 360–369.
[15]
V. Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, and H. Hoppe, “Fast exact and approximate geodesics on meshes,” ACM Trans. Graph., vol. 24, no. 3, pp. 553–560, 2005.
[16]
S.-Q. Xin and G.-J. Wang, “Improving Chen and Han's algorithm on the discrete geodesic problem,” ACM Trans. Graph., vol. 28, no. 4, pp. 104:1–104:8, 2009.
[17]
X. Ying, S.-Q. Xin, and Y. He, “Parallel Chen-Han (PCH) algorithm for discrete geodesics,” ACM Trans. Graph., vol. 33, no. 1, pp. 9:1–9:11, 2014.
[18]
Y.-J. Liu, “Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures,” Comput.-Aided Des., vol. 45, no. 3, pp. 695–704, 2013.
[19]
C.-X. Xu, T. Y. Wang, Y.-J. Liu, L. Liu, and Y. He, “Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes,” IEEE Trans. Vis. Comput. Graphics, vol. 21, no. 7, pp. 822–834, Jul. 2015.
[20]
Y. Qin, X. Han, H. Yu, Y. Yu, and J. Zhang, “Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation,” ACM Trans. Graph., vol. 35, no. 4, pp. 125:1–125:13, 2016.
[21]
Y. Qin, X. Han, H. Yu, Y. Yu, and J. Zhang, “Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation,” ACM Trans. Graph., vol. 35, no. 4, pp. 125:1–125:13, 2016.
[22]
J. A. Sethian, “Fast marching methods,” SIAM Rev., vol. 41, no. 2, pp. 199–235, 1999.
[23]
R. Kimmel and J. A. Sethian, “Computing geodesic paths on manifolds,” Proc. Nat. Acad. Sci. USA, vol. 95, no. 15, pp. 8431–8435, 1998.
[24]
E. L. Melvær and M. Reimers, “Geodesic polar coordinates on polygonal meshes,” Comput. Graph. Forum, vol. 31, no. 8, pp. 2423–2435, 2012.
[25]
A. G. Belyaev and P. Fayolle, “On variational and PDE-based distance function approximations,” Comput. Graph. Forum, vol. 34, no. 8, pp. 104–118, 2015.
[26]
J. Tao, J. Zhang, B. Deng, Z. Fang, Y. Peng, and Y. He, “Parallel and scalable heat methods for geodesic distance computation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 43, no. 2, pp. 579–594, Feb. 2021.
[27]
X. Wang, Z. Fang, J. Wu, S. Xin, and Y. He, “Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces,” Comput. Aided Geometric Des., vol. 52, pp. 262–284, 2017.
[28]
S. Xinet al., “Lightweight preprocessing and fast query of geodesic distance via proximity graph,” Comput.-Aided Des., vol. 102, pp. 128–138, 2018.
[29]
T. F. Cox and M. Cox, Multidimensional Scaling, Second Edition, 2nd ed. London, U.K.: Chapman and Hall/CRC, 2000.
[30]
O. Sorkine and D. Cohen-Or, “Least-squares meshes,” in Proc. Int. Conf. Shape Model. Appl., 2004, pp. 191–199.
[31]
R. R. Coifmanet al., “Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps,” Proc. Nat. Acad. Sci. USA, vol. 102, no. 21, pp. 7426–7431, 2005.
[32]
F. Fouss, A. Pirotte, J. Renders, and M. Saerens, “Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation,” IEEE Trans. Knowl. Data Eng., vol. 19, no. 3, pp. 355–369, Mar. 2007.
[33]
Y. Lipman, R. M. Rustamov, and T. A. Funkhouser, “Biharmonic distance,” ACM Trans. Graph., vol. 29, no. 3, pp. 27:1–27:11, 2010.
[34]
B. Lévy and N. Bonneel, “Variational anisotropic surface meshing with voronoi parallel linear enumeration,” in Proc. 21st Int. Meshing Roundtable, 2013, pp. 349–366.
[35]
Z. Zhong, W. Wang, B. Levy, J. Hua, and X. Guo, “Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metric,” ACM Trans. Graph., vol. 37, no. 4CD, pp. 1–16, 2018.
[36]
S. Bouaziz, M. Deuss, Y. Schwartzburg, T. Weise, and M. Pauly, “Shape-Up: Shaping discrete geometry with projections,” Comput. Graph. Forum, vol. 31, no. 5, pp. 1657–1667, 2012.
[37]
T. Liu, S. Bouaziz, and L. Kavan, “Quasi-newton methods for real-time simulation of hyperelastic materials,” ACM Trans. Graph., vol. 36, no. 3, pp. 23:1–23:16, 2017.
[38]
J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed. New York, NY, USA: Springer-Verlag, 2006.
[39]
S. Agarwalet al., “Ceres solver,” [Online]. Available: http://ceres-solver.org/
Index Terms
- GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries
Index terms have been assigned to the content through auto-classification.
Recommendations
Constrained discriminant neighborhood embedding for high dimensional data feature extraction
When handling pattern classification problem such as face recognition and digital handwriting identification, image data is always represented to high dimensional vectors, from which discriminant features are extracted using dimensionality reduction ...
Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance Queries
SA '22: SIGGRAPH Asia 2022 Conference PapersGeodesic distances between pairs of points on a 3D mesh surface are a crucial ingredient of many geometry processing tasks, but are notoriously difficult to compute efficiently on demand. We propose a novel method for the compact storage of geodesic ...
High-Dimensional Multimodal Distribution Embedding
ICDMW '10: Proceedings of the 2010 IEEE International Conference on Data Mining WorkshopsHigh-dimensional data is emerging in more and more varied domains, but its analysis has revealed to be difficult due to the curse of dimensionality. Dimension reduction emerged as a powerful tool in overcoming problems related to high-dimensionality, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1077-2626 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 December 2022
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in