Abstract
In this paper, we propose a complete framework for 3D geometry modeling and processing that uses only fast geodesic computations. The basic building block for these techniques is a novel greedy algorithm to perform a uniform or adaptive remeshing of a triangulated surface. Our other contributions include a parameterization scheme based on barycentric coordinates, an intrinsic algorithm for computing geodesic centroidal tessellations, and a fast and robust method to flatten a genus-0 surface patch. On large meshes (more than 500,000 vertices), our techniques speed up computation by over one order of magnitude in comparison to classical remeshing and parameterization methods. Our methods are easy to implement and do not need multilevel solvers to handle complex models that may contain poorly shaped triangles.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic Polygonal Remeshing. ACM Transactions on Graphics. Special Issue for SIGGRAPH Conference, pp. 485–493.
Bengio, Y., Paiement, J.-F., and Vincent, P. 2003. Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering. Proc. NIPS, 2003.
Chen, J. and Hahn, Y. 1990. Shortest Path on a Polyhedron. Proc. 6th ACM Sympos, Comput Geom pp. 360–369.
Chew, L.P. 1993. Guaranteed-Quality Mesh Generation for Curved Surfaces. In Proc. of the Ninth Symposium on Computational Geometry, pp. 274–280.
Cohen, L. 2001. Multiple Contour Finding and Perceptual Grouping Using Minimal Paths. Journal of Mathematical Imaging and Vision, 14(3):225–236.
Cohen, L.D. and Kimmel, R. 1997. Global Minimum for Active Contour Models: A Minimal Path Approach. International Journal of Computer Vision 24(1):57–78.
Cohen-Steiner, D. and Morvan, J.-M. 2003. Restricted Delaunay Triangulations and Normal Cycles. In Proc. 19th ACM Sympos, Comput. Geom. pp. 237–246.
Delingette, H. 1999. General Object Reconstruction Based on Simplex Meshes. International Journal of Computer Vision, 32(2):111–146.
Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Parameterizations of Surface Meshes. Eurographics Conference Proceedings, 21(2):209–218.
Eldar, Y., Lindenbaum, M., Porat, M., and Zeevi, Y. 1997. The Farthest Point Strategy for Progressive Image Sampling. IEEE Trans. on Image Processing, 6(9):1305–1315.
Floater, M.S., Hormann, K., and Reimers, M. 2002. Parameterization of Manifold Triangulations. Approximation Theory X: Abstract and Classical Analysis, pp. 197–209.
Fua, P. 1997. From Multiple Stereo Views to Multiple 3-D Surfaces. International Journal of Computer Vision, 24(1):19–35.
Gu, X. and Yau, S.-T. 2003. Global Conformal Surface Parameterization. In Proc. ACM Symposium on Geometry Processing, 2003 pp. 127–137.
Hoppe, H. 1996. Progressive meshes. In Proc. ACM SIGGRAPH 1996 pp. 99–108.
Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally Smooth Parameterizations with Low Distortion. ACM Transactions on Graphics. Special Issue for SIGGRAPH Conference, pp. 350–357.
Kimmel, R. and Sethian, J. 1998. Computing Geodesic Paths on Manifolds. Proc. Natl. Acad. Sci., 95(15):8431–8435.
Kimmel, R. and Sethian, J.A. 2000. Fast Voronoi Diagrams on Triangulated Surfaces. In Proc. of the 16th European Workshop on Comp. Geom., (EUROCG-00). pp. 1–4.
Kunert, G. 2002. Towards Anisotropic Mesh Construction and Error Estimation in the Finite Element Method. Numerical Methods in PDE, 18:625–648.
Lee, A.W.F., Schröder, P., Sweldens, W., Cowsar, L., and Dobkin, D. 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. Computer Graphics 32(Ann. Conf. Series), 95–104.
Leibon, G. and Letscher, D. 2000. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. ACM Symposium on Computational Geometry, pp. 341–349.
Manay, S. and Yezzi, A. 2003. Second-order Models for Computing Distance Transforms. In Proc. IEEE Variational, Geometric and Level Set Methods 2003, pp. 105–112.
McInerney, T. and Terzopoulos, D. 1996. Deformable models in medical image analysis: A survey. Medical Image Analysis 1(2):91–108.
Moenning, C. and Dodgson, N.A. 2003. Fast Marching Farthest Point Sampling. In Proc. EURO-GRAPHICS, 2003.
Onishi, K. and Itoh, J. 2003. Estimation of the necessary number of points in Riemannian Voronoi diagram. In Proc. CCCG 2003, pp. 19–24.
Osher, S. and Paragios, N. 2003. Geometric Level Set Methods in Imaging, Vision, and Graphics. Springer-Verlag New York, Inc.
Peyré, G. and Cohen, L.D. 2003. Geodesic Remeshing Using Front Propagation. In Proc. IEEE Variational, Geometric and Level Set Methods 2003, pp. 33–40.
Peyré, G. and Cohen, L.D. 2004a. Geodesic Computations for Fast and Accurate Surface Flattening. Preprint CMAP.
Peyré, G. and Cohen, L.D. 2004b. Surface Segmentation Using Geodesic Centroidal Tesselation. In Proc. IEEE 3D Data Processing Visualization Transmission 2004, pp. 995–1002.
Roweis, S. and Saul, L. 2000. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290(5500):2323–2326.
Ruppert, J. 1995. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms, 18(3):548–585.
Sander, P., Wood, Z., Gortler, S., Snyder, J., and Hoppe, H. 2003. Multi-chart Geometry Images. Proc. Symposium on Geometry Processing 2003 pp. 146–155.
Sethian, J. 1999. Level Sets Methods and Fast Marching Methods. 2nd edition, Cambridge University Press.
Sifri, O., Sheffer, A., and Gotsman, C. 2003. Geodesic-based Surface Remeshing. In Proc. 12th International Meshing Roundtable, pp. 189–199.
Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic Remeshing of Surfaces: A Local Parameter-ization Approach. In Proc. 12th International Meshing Roundtable.
Tenenbaum, J.B., de Silva, V., and Langford, J.C. 2000. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290(5500):2319–2323.
Terzopoulos, D. and Vasilescu, M. 1992. Adaptive Meshes and Shells: Irregular Triangulation, Dis-continuities, and Hierarchical Subdivision. In Proc. IEEE CVPR 92. Champaign, Illinois, pp. 829–832.
Tsitsiklis, J. 1995. Efficient Algorithms for Globally Optimal Trajectories. IEEE Trans. on Automatic Control.
Ulichney, R. 1993. The Void-and-Cluster Method for Generating Dither Arrays. Proc. IS&T Symposium on Electronic Imaging Science & Technology, San Jose, CA 1913(9):332–343.
Zigelman, G., Kimmel, R., and Kiryati, N. 2002. Texture Mapping Using Surface Flattening via Multi-dimensional Scaling. IEEE Trans. on Visualization and Computer Graphics, 8(1):198–207.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peyré, G., Cohen, L.D. Geodesic Remeshing Using Front Propagation. Int J Comput Vision 69, 145–156 (2006). https://doi.org/10.1007/s11263-006-6859-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-006-6859-3