“Globally optimal direction fields” by Knöppel, Crane, Pinkall and 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
