“Globally smooth parameterizations with low distortion” by Khodakovsky, Litke and Schröder

Good parameterizations are of central importance in many digital geometry processing tasks. Typically the behavior of such processing algorithms is related to the smoothness of the parameterization and how much distortion it contains. Since a parameterization maps a bounded region of the plane to the surface, a parameterization for a surface which is not homeomorphic to a disc must be made up of multiple pieces. We present a novel parameterization algorithm for arbitrary topology surface meshes which computes a globally smooth parameterization with low distortion. We optimize the patch layout subject to criteria such as shape quality and metric distortion, which are used to steer a mesh simplification approach for base complex construction. Global smoothness is achieved through simultaneous relaxation over all patches, with suitable transition functions between patches incorporated into the relaxation procedure. We demonstrate the quality of our parameterizations through numerical evaluation of distortion measures and the excellent rate distortion performance of semi-regular remeshes produced with these parameterizations. The numerical algorithms required to compute the parameterizations are robust and run on the order of minutes even for large meshes.

1. BIERMANN, H., MARTIN, I., BERNARDINI, F., AND ZORIN, D. 2002. Cut-and-Paste Editing of Multiresolution Surfaces. ACM Transactions on Graphics 21, 3, 312–321. Google ScholarDigital Library
2. CIGNONI, P., ROCCHINI, C., AND SCOPIGNO, R. 1998. Metro: Measuring Error on Simpli ed Surfaces. Computer Graphics Forum 17, 2, 167–174.Google ScholarCross Ref
3. DESBRUN, M., MEYER, M., AND ALLIEZ, P. 2002. Intrinsic Parameterizations of Surface Meshes. Computer Graphics Forum 21, 3, 209–218.Google ScholarCross Ref
4. ECK, M., DEROSE, T. D., DUCHAMP, T., HOPPE, H., LOUNSBERY, M., AND STUETZLE, W. 1995. Multiresolution Analysis of Arbitrary Meshes. In Proceedings of SIGGRAPH, 173–182. Google Scholar
5. FLOATER, M. S. 1997. Parameterization and Smooth Approximation of Surface Triangulations. Computer Aided Geometric Design 14, 3, 231–250. Google ScholarDigital Library
6. FLOATER, M. S. 2003. Mean Value Coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
7. GARLAND, M., AND HECKBERT, P. S. 1997. Surface Simplification Using Quadric Error Metrics. In Proceedings of SIGGRAPH, 209–216. Google Scholar
8. GOTSMAN, C., GU, X., AND SHEFFER, A. 2003. Fundamentals of Spherical Parameterization for 3D Meshes. In Proceedings of SIGGRAPH. Google Scholar
9. GRIMM, C. M., AND HUGHES, J. F. 1995. Modeling Surfaces of Arbitrary Topology using Manifolds. In Proceedings of SIGGRAPH, 359–368. Google Scholar
10. GU, X., AND YAU, S.-T. 2003. Global Conformal Surface Parameterization. Submitted for publication, April.Google Scholar
11. GU X., GORTLER, S. J., AND HOPPE, H. 2002. Geometry Images. ACM Transactions on Graphics 21, 3, 355–361. Google ScholarDigital Library
12. GUSKOV, I., VIDIMČE, K., SWELDENS, W., AND SCHRÖDER, P. 2000. Normal Meshes. In Proceedings of SIGGRAPH, 95–102. Google Scholar
13. GUSKOV, I., KHODAKOVSKY, A., SCHRÖDER, P., AND SWELDENS, W. 2002. Hybrid Meshes: Multiresolution using Regular and Irregular Refinement. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, 264–272. Google Scholar
14. HOPPE, H. 1996. Progressive Meshes. In Proceedings of SIGGRAPH, 99–108. Google Scholar
15. HORMANN, K., AND GREINER, G. 2000. MIPS: An efficient Global Parametrization Method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.Google Scholar
16. KHODAKOVSKY, A., AND GUSKOV, I. 2003. Compression of Normal Meshes. In Geometric Modeling for Scientific Visualization. Springer-Verlag.Google Scholar
17. KHODAKOVSKY, A., SCHRÖDER, P., AND SWELDENS, W. 2000. Progressive Geometry Compression. In Proceedings of SIGGRAPH, 271–278. Google ScholarDigital Library
18. KOBBELT, L., CAMPAGNA, S., AND SEIDEL, H.-P. 1998. A General Framework for Mesh Decimation. In Graphics Interface ’98, 43–50.Google Scholar
19. LEE, A. W. F., SWELDENS, W., SCHRÖDER, P., COWSAR, L., AND DOBKIN, D. 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. In Proceedings of SIGGRAPH, 95–104. Google Scholar
20. LEE, A., DOBKIN, D., SWELDENS, W., AND SCHRÖDER, P. 1999. Multiresolution Mesh Morphing. In Proceedings of SIGGRAPH, 343–350. Google Scholar
21. LEE, A., MORETON, H., AND HOPPE, H. 2000. Displaced Subdivision Surfaces. In Proceedings of SIGGRAPH, 85–94. Google ScholarDigital Library
22. LÉVY, B., PETITJEAN, S., RAY, N., AND MAILLOT, J. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Transactions on Graphics 21, 3, 362–371. Google ScholarDigital Library
23. LOOP, C. 1987. Smooth Subdivision Surfaces Based on Triangles. Master’s thesis, University of Utah, Department of Mathematics.Google Scholar
24. MAILLOT, J., YAHIA, H., AND VERROUST, A. 1993. Interactive Texture Mapping. In Proceedings of SIGGRAPH, 27–34. Google Scholar
25. PINKALL, U., AND POLTHIER, K. 1993. Computing Discrete Minimal Surfaces. Experimental Mathematics 2, 1, 15–36.Google ScholarCross Ref
26. PRAUN, E., AND HOPPE, H. 2003. Spherical Parameterization and Remeshing. In Proceedings of SIGGRAPH. Google Scholar
27. SANDER, P. V., SNYDER, J., GORTLER, S. J., AND HOPPE, H. 2001. Texture Mapping Progressive Meshes. In Proceedings of SIGGRAPH, 409–416. Google Scholar
28. SANDER, P., GORTLER, S., SNYDER, J., AND HOPPE, H. 2002. Signal-Specialized Parameterization. In Eurographics Workshop on Rendering, 87–100. Google Scholar
29. SHEFFER, A., AND HART, J. C. 2002. Seamster: Inconspicuous Low-Distortion Texture Seam Layout. In IEEE Visualization, 291–298. Google ScholarDigital Library
30. SHEWCHUK, J. R. 2002. What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. Eleventh International Meshing Roundtable.Google Scholar
31. SORKINE, O., COHEN-OR, D., GOLDENTHAL, R., AND LISCHINSKI, D. 2002. Bounded-distortion Piecewise Mesh Parameterization. In IEEE Visualization, 355–362. Google Scholar
32. STRANG, G., AND NGUYEN, T. 1996. Wavelets and Filter Banks. Wellesley-Cambridge Press.Google Scholar
33. WOOD, Z. J., DESBRUN, M., SCHRÖDER, P., AND BREEN, D. 2000. Semi-Regular Mesh Extraction from Volumes. In IEEE Visualization, 275–282. Google Scholar
34. ZORIN, D., SCHRÖDER, P., AND SWELDENS, W. 1996. Interpolating Subdivision for Meshes with Arbitrary Topology. In Proceedings of SIGGRAPH 96, 189–192. Google Scholar