Abstract
Geodesic paths and distances on meshes are used for many applications such as parameterization, remeshing, mesh segmentation, and simulations of natural phenomena. Noble works to compute shortest geodesic paths have been published. In this paper, we present a new approach to compute the straightest path from a source to one or more vertices on a manifold mesh with a boundary. A cutting plane with a source and a destination vertex is first defined. Then the straightest path between these two vertices is created by intersecting the cutting plane with faces on the mesh. We demonstrate that our straightest path algorithm contributes to reducing distortion in a shape-preserving linear parameterization by generating a measured boundary.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chen, J., Han, Y.: Shortest Paths on a Polyhedron; Part I: Computing Shortest Paths. Int. J. Comp. Geom. & Appl. 6(2) (1996)
Desbrun, M., Meyer, M., Alliez, P.: Intrinsic Parameterizations of Surface Meshes. In: Eurographics 2002 Conference Proceeding (2002)
Floater, M.: Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design (1997)
Floater, M.: Mean Value Coordinates. Comput. Aided Geom. Des. (2003)
Kaneva, B., O’Rourke, J.: An implementation of Chen and Han’s sortest paths algorithm. In: Proc. of the 12th Canadian Conf. on Computational Geometry (2000)
Kanai, T., Suzuki, H.: Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and Its Applications. Proc. Geometric Modeling and Processing 2000, HongKong (2000)
Kimmel, R., Sethian, J.A.: Computing Geodesic Paths on Manifolds. Proc. Natl. Acad. Sci. USA 95 (1998)
Lee, Y., Kim, H., Lee, S.: Mesh Parameterization with a Virtual Boundary. Computer and Graphics 26 (2002)
Lee, H., Kim, L., Meyer, M., Desbrun, M.: Meshes on Fire. In: Computer Animation and Simulation 2001, Eurographics (2001)
Lee, H., Tong, Y., Desbrun, M.: Geodesics-Based One-to-One Parameterization of 3D Triangle Meshes. IEEE Multimedia 12(1) (January/March 2005)
Mitchell, J.S.B.: Geometric Shortest Paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry. Elsevier Science, Amsterdam (2000)
Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The Discrete Geodesic Problem. SIAM J. of Computing 16(4) (1987)
Peyré, G., Cohen, L.: Geodesic Re-meshing and Parameterization Using Front Propagation. In: Proceedings of VLSM 2003 (2003)
Polthier, K., Schmies, M.: Straightest Geodesics on Polyhedral Surfaces. Mathematical Visualization (1998)
Polthier, K., Schmies, M.: Geodesic Flow on Polyhedral Surfaces. In: Proceedings of Eurographics-IEEE Symposium on Scientific Visualization 1999 (1999)
Riken, T., Suzuki, H.: Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and Its Applications. In: Geometric Modeling and Processing 2000, Hongkong (2000)
Sander, P.V., Snyder, J., Gortler, S.J., Hoppe, H.: Texture Mapping Progressive Meshes. In: Proceedings of SIGGRAPH 2001 (2001)
Sifri, O., Sheffer, A., Gotsman, C.: Geodesic-based Surface Remeshing. In: Proceedings of 12th Intnl. Meshing Roundtable (2003)
Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., Hoppe, H.: Fast Exact and Approximate Geodesics on Meshes. In: ACM SIGGRAPH 2005 Conference Proceedings (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lee, S., Han, J., Lee, H. (2006). Straightest Paths on Meshes by Cutting Planes. In: Kim, MS., Shimada, K. (eds) Geometric Modeling and Processing - GMP 2006. GMP 2006. Lecture Notes in Computer Science, vol 4077. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11802914_47
Download citation
DOI: https://doi.org/10.1007/11802914_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36711-6
Online ISBN: 978-3-540-36865-6
eBook Packages: Computer ScienceComputer Science (R0)