“Fundamentals of spherical parameterization for 3D meshes”

  • ©Craig Gotsman, Xianfeng Gu, and Alla Sheffer




    Fundamentals of spherical parameterization for 3D meshes



    Parameterization of 3D mesh data is important for many graphics applications, in particular for texture mapping, remeshing and morphing. Closed manifold genus-0 meshes are topologically equivalent to a sphere, hence this is the natural parameter domain for them. Parameterizing a triangle mesh onto the sphere means assigning a 3D position on the unit sphere to each of the mesh vertices, such that the spherical triangles induced by the mesh connectivity are not too distorted and do not overlap. Satisfying the non-overlapping requirement is the most difficult and critical component of this process. We describe a generalization of the method of barycentric coordinates for planar parameterization which solves the spherical parameterization problem, prove its correctness by establishing a connection to spectral graph theory and show how to compute these parameterizations.


    1. ALEXA, M. 2000. Merging Polyhedral Shapes with Scattered Features. The Visual Computer 16, 1, 26–37.]]Google ScholarDigital Library
    2. CHUNG, F. R. K. 1997. Spectral Graph Theory. CBMS 92, AMS.]]Google Scholar
    3. COLEMAN, T. F., AND LI, Y. 1996. An Interior Trust Region Approach for Nonlinear Minimization Subject to Bounds. SIAM Journal on Optimization, 6, 418–445.]]Google ScholarDigital Library
    4. COLINDE VERDIERE, Y. 1990. Sur un Nouvel Invariant des Graphes et un Critere de Planarite. Journal of Combinatorial Theory B 50, 11–21. {English translation: On a New Graph Invariant and a Criterion for Planarity. In Graph Structure Theory. 1993. (N. Robertson, P. Seymour, Eds.) Contemporary Mathematics, AMS, 137–147.}]] Google ScholarDigital Library
    5. DAS, G., AND GOODRICH, M. T. 1997. On the Complexity of Optimization Problems for 3-Dimensional Convex Polyhedra and Decision Trees. Computational Geometry, 8, 123–137.]] Google ScholarDigital Library
    6. DESBRUN, M., MEYER, M., AND ALLIEZ, P. 2002. Intrinsic Parameterizations of Surface Meshes. Computer Graphics Forum, 21, 3, 210–218.]]Google ScholarCross Ref
    7. DO CARMO, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.]]Google Scholar
    8. FIEDLER, M. 1975. A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Application to Graph Theory. Czechoslovak Math. Journal, 25, 619–633.]]Google Scholar
    9. FLOATER, M. S. 1997. Parameterization and Smooth Approximation of Surface Triangulations. Computer Aided Geometric Design, 14, 231–250.]] Google ScholarDigital Library
    10. FLOATER, M. S. 2003. Mean-value Coordinates. Computer Aided Geometric Design, 20, 19–27.]] Google ScholarDigital Library
    11. FLOATER, M. S. 2003. One-to-one Piecewise Linear Mappings Over Triangulations. Mathematics of Computation 2, 685–696.]] Google Scholar
    12. GU, X., AND YAU, S.-T. 2002. Computing Conformal Structures of Surfaces. Communications in Information and Systems, 2, 2, 121–146.]]Google ScholarCross Ref
    13. GU, X., GORTLER, S., AND HOPPE, H. 2002. Geometry Images. ACM Transactions on Graphics, 21, 3, 355–361.]] Google ScholarDigital Library
    14. GUSKOV, I., VIDIMCE, K., SWELDENS, W., AND SCHROEDER, P. 2000. Normal Meshes. In Proceedings of ACM SIGGRAPH 2000, ACM Press/ ACM SIGGRAPH, New York, K. Akeley, Ed., Computer Graphics Proceedings, Annual Conferences Series, ACM, 95–102.]] Google Scholar
    15. HAKER, S., ANGENENT, S., TANNENBAUM, A., KIKINIS, R., AND SAPIRO, G. 2000. Conformal Surface Parameterization for Texture Mapping. IEEE Transactions on Visualization and Computer Graphics, 6, 2, 1–9.]] Google ScholarDigital Library
    16. HALL, K. M. 1970. An r-dimensional Quadratic Placement Algorithm. Management Science, 17, 219–229.]]Google ScholarCross Ref
    17. KANAI, T., SUZUKI, H., AND KIMURA, F. 2000. Metamorphosis of Arbitrary Triangular Meshes. IEEE Computer Graphics and Applications, 20, 2, 62–75.]] Google ScholarDigital Library
    18. KARNI, Z., AND GOTSMAN, C. Spectral Compression of Mesh Geometry. In Proceedings of ACM SIGGRAPH 2000, ACM Press / ACM SIGGRAPH, New York, K. Ackley, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 279–286.]] Google Scholar
    19. KOBBELT, L. P., VORSATZ, J., LABISK, U., AND SEIDEL, H.-P. 1999. A Shrink-wrapping Approach to Remeshing Polygonal Surfaces. Computer Graphics Forum, 18, 3, 119–129.]]Google ScholarCross Ref
    20. KOREN, Y. 2001. On Spectral Graph Drawing. Preprint, Weizmann Institute of Science.]]Google Scholar
    21. LEVY, 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
    22. LOVASZ, L., AND SCHRIJVER, A. 1999. On the Nullspace of a Colin de Verdiere Matrix. Annales de l’Institute Fourier 49, 1017–1026.]]Google ScholarCross Ref
    23. PINKALL, U., AND POLTHIER, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics, 2, 15–36.]]Google ScholarCross Ref
    24. RICHTER-GEBERT, J. 1996. Realization Spaces of Polytopes. Lecture Notes in Math #1643, Springer.]]Google Scholar
    25. SANDER, P. V., SNYDER, J., GORTLER S. J., AND HOPPE, H. 2001. Texture Mapping Progressive Meshes. In Proceedings of ACM SIGGRAPH 2001, ACM Press/ ACM SIGGRAPH, New York, E. Fiume, Ed., Computer Graphics Proceedings, Annual Conferences Series, ACM, 409–416.]] Google Scholar
    26. SHAPIRO A., AND TAL, A. 1998. Polygon Realization for Shape Transformation. The Visual Computer, 14, 8–9, 429–444.]]Google ScholarCross Ref
    27. SHEFFER, A., GOTSMAN C., AND DYN, N. 2003. Robust Spherical Parameterization of Triangular Meshes. In Proceedings of 4th Israel-Korea Binational Workshop on Computer Graphics and Geometric Modeling, Tel Aviv, 94–99.]]Google Scholar
    28. SHEFFER, A. ANDDE STURLER, E. 2001. Parameterization of Faceted Surfaces for Meshing Using Angle Based Flattening. Engineering with Computers, 17, 3, 326–337.]]Google ScholarCross Ref
    29. TUTTE. W. T. 1963. How to Draw a Graph. Proc. London Math. Soc. 13, 3, 743–768.]]Google ScholarCross Ref

ACM Digital Library Publication: