“Globally optimal direction fields” by Knöppel, Crane, Pinkall and Schröder

  • ©Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder

Conference:


Type(s):


Title:

    Globally optimal direction fields

Session/Category Title:   Surfaces & Differential Geometry


Presenter(s)/Author(s):


Moderator(s):



Abstract:


    We present a method for constructing smooth n-direction fields (line fields, cross fields, etc.) on surfaces that is an order of magnitude faster than state-of-the-art methods, while still producing fields of equal or better quality. Fields produced by the method are globally optimal in the sense that they minimize a simple, well-defined quadratic smoothness energy over all possible configurations of singularities (number, location, and index). The method is fully automatic and can optionally produce fields aligned with a given guidance field such as principal curvature directions. Computationally the smoothest field is found via a sparse eigenvalue problem involving a matrix similar to the cotan-Laplacian. When a guidance field is present, finding the optimal field amounts to solving a single linear system.

References:


    1. Ahlfors, L. V. 1966. Complex Analysis, 2nd Ed. McGraw-Hill.Google Scholar
    2. Ben-Chen, M., Butscher A., Solomon, J., and Guibas, L. 2010. On Discrete Killing Vector Fields and Patterns on Surfaces. Comp. Graph. Forum 29, 5, 1701–1711.Google ScholarCross Ref
    3. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-Integer Quadrangulation. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
    4. Bommes, D., Zimmer, H., and Kobbelt, L. 2012. Practical Mixed-Integer Optimization for Geometry Processing. In Proc. 7th Int. Conf. Curves & Surfaces, 193–206. Project page: http://www.graphics.rwth-aachen.de/software/comiso. Google ScholarDigital Library
    5. Chen, Y., Davis, T. A., Hager, W W., and Rajamanickam, S. 2009. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Trans. Math. Softw. 35, 3, 22:1–22:14. Google ScholarDigital Library
    6. Cohen-Steiner D., and Morvan, J.-M. 2003. Restricted Delaunay Triangulations and Normal Cycle. In Proc. Symp. Comp. Geom., 312–321. Google ScholarDigital Library
    7. Crane, K., Desbrun, M., and Schröder, P. 2010. Trivial Connections on Discrete Surfaces. Comp. Graph. Forum 29, 5, 1525–1533.Google ScholarCross Ref
    8. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Parameterizations of Surface Meshes. Comp. Graph. Forum 21, 3, 209–218.Google ScholarCross Ref
    9. Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete Differential Forms for Computational Modeling. In Discrete Differential Geometry, A. I. Bobenko, P. Schröder, J. M. Sullivan, and G. M. Ziegler, Eds., Vol. 38 of Oberwolfach Seminars. Birkhäuser Verlag, 287–324.Google Scholar
    10. Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of Tangent Vector Fields. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    11. Gil, A., Segura, J., and Temme, N. M. 2007. Numerical Methods for Special Functions. SIAM. Google ScholarDigital Library
    12. Gu, X., and Yau, S.-T. 2003. Global Conformal Surface Parameterization. In Proc. Symp. Geom. Proc., 127–137. Google ScholarDigital Library
    13. Hertzmann, A., and Zorin, D. 2000. Illustrating Smooth Surfaces. In Proc. ACM/SIGGRAPH Conf., 517–526. Google ScholarDigital Library
    14. Kälberer F., Nieser, M., and Polthier, K. 2007. QuadCover – Surface Parameterization using Branched Coverings. Comp. Graph. Forum 26, 3, 375–384.Google ScholarCross Ref
    15. Kass, M., and Witkin, A. 1987. Analyzing Oriented Patterns. Comp. Vis., Graph., Im. Proc. 37, 3, 362–385. Google ScholarDigital Library
    16. Lefebvre, S., and Hoppe, H. 2006. Appearance-space Texture Synthesis. ACM Trans. Graph. 25, 3, 541–548. Google ScholarDigital Library
    17. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3, 362–371. Google ScholarDigital Library
    18. Ling, C., Nie, J., Qi, L., and Ye, Y. 2009. Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations. SIAM J. on Opt. 20, 3, 1286–1310. Google ScholarDigital Library
    19. MacNeal, R. 1949. The Solution of Partial Differential Equations by means of Electrical Networks. PhD thesis, Caltech.Google Scholar
    20. Mullen, P., Tong, Y., Alliez, P., and Desbrun, M. 2008. Spectral Conformal Parameterization. Comp. Graph. Forum 27, 5, 1487–1494. Google ScholarDigital Library
    21. Napier, T, and Ramachandran, M. 2011. An Introduction to Riemann Surfaces. Birkhäuser.Google Scholar
    22. Nieser M., Palacios, J., Polthier, K, and Zhang, E. 2012. Hexagonal Global Parameterization of Arbitrary Surfaces. IEEE Trans. Vis. Comp. Graph. 18, 6, 865–878. Google ScholarDigital Library
    23. Palacios, J., and Zhang, E. 2007. Rotational Symmetry Field Design on Surfaces. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    24. Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experiment. Math. 2, 1, 15–36.Google ScholarCross Ref
    25. Polthier, K., and Schmies, M. 1998. Straightest Geodesies on Polyhedral Surfaces. In Mathematical Visualization: Algorithms, Applications and Numerics, H.-C. Hege and K. Polthier, Eds. Springer Verlag, 135–152.Google Scholar
    26. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4, 1460–1485. Google ScholarDigital Library
    27. Ray, N., Vallet, B., Li, W. C., and Lévy, B. 2008. N-Symmetry Direction Field Design. ACM Trans. Graph. 27, 2, 10:1–10:13. Google ScholarDigital Library
    28. Ray, N., Vallet, B., Alonso, L., and Lévy, B. 2009. Geometry Aware Direction Field Processing. ACM Trans. Graph. 29, 1. Google ScholarDigital Library
    29. Wirtinger, W. 1927. Zur formalen Theorie der Funktionen von mehr komplexen Veränderlichen. Math. Ann. 97, 1, 357–375.Google ScholarCross Ref
    30. Zhang, E., Mischaikow, K., and Turk, G. 2006. Vector Field Design on Surfaces. ACM Trans. Graph. 25, 4, 1294–1326. Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: