“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