“Strict minimizers for geometric optimization” by Levi and Zorin
Conference:
Type(s):
Title:
- Strict minimizers for geometric optimization
Session/Category Title: Meshing Surface, and Meshing
Presenter(s)/Author(s):
Abstract:
We introduce the idea of strict minimizers for geometric distortion measures used in shape interpolation, deformation, parametrization, and other applications involving geometric mappings. The L∞-norm ensures the tightest possible control on the worst-case distortion. Unfortunately, it does not yield a unique solution and does not distinguish between solutions with high or low distortion below the maximum. The strict minimizer is a minimal L∞-norm solution, which always prioritizes higher distortion reduction. We propose practical algorithms for computing strict minimizers. We also offer an efficient algorithm for L∞ optimization based on the ARAP energy. This algorithm can be used on its own or as a building block for an ARAP strict minimizer. We demonstrate that these algorithms lead to significant improvements in quality.
References:
1. Abdelmalek, N. N. 1977. Computing the strict Chebyshev solution of overdetermined linear equations. Mathematics of Computation 31, 140, 974–983.
2. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3D. TOG 32, 4, 106.
3. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Computer graphics and interactive techniques, 157–164.
4. Andersen, E., Roos, C., and Terlaky, T. 2003. On implementing a primal-dual interior-point method for conic quadratic optimization. Mathematical Programming 95, 2, 249–277.Cross Ref
5. Behringer, F. 1981. A simplex-based algorithm for the lexico-graphically extended linear maxmin problem. Euro. J. Operational Research 7, 3, 274–283.Cross Ref
6. Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27, 2, 449–458.Cross Ref
7. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77.
8. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2012. State of the art in quad meshing. In Eurographics STARS.
9. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., Kobbelt, L., et al. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4.
10. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (July), 38:1–38:6.
11. Chen, R., Weber, O., Keren, D., and Ben-Chen, M. 2013. Planar shape interpolation with bounded distortion. ACM Trans. Graph. 32, 4 (July), 108:1–108:12.
12. Desbrun, M., Meyer, M., and Alliez, P. 2002. Meshes and parameterization: Intrinsic parameterizations of surface meshes. Computer Graphics Forum 21, 3, 209.Cross Ref
13. Descloux, J. 1963. Approximations in Lp and Chebyshev approximations. Journal of the Society for Industrial & Applied Mathematics 11, 4, 1017–1026.Cross Ref
14. Fletcher, R., Grant, J., and Hebden, M. 1971. The calculation of linear best Lp approximations. The Computer Journal 14, 3, 276–279.Cross Ref
15. Gao, L., Zhang, G., and Lai, Y. 2012. lp shape deformation. Science China Information Sciences 55, 5, 983–993.Cross Ref
16. Hormann, K., and Greiner, G. 1999. MIPS: An efficient global parameterization method. Curve and Surface Design: Saint-Malo 2000, 153–162.
17. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-Cover: Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3, 375–384.Cross Ref
18. Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25 (April), 412–438.
19. Lawson, C. L. 1972. Transforming triangulations. Discrete mathematics 3, 4, 365–372.
20. Levi, Z., and Gotsman, C. 2015. Smooth rotation enhanced as-rigid-as-possible mesh animation. TVCG.
21. 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.
22. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4, 108.
23. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A Local/Global approach to mesh parameterization. Computer Graphics Forum 27, 5 (July), 1495–1504.
24. Luss, H., and Smith, D. R. 1986. Resource allocation among competing activities: A lexicographic minimax approach. Operations Research Letters 5, 5, 227–231.
25. Marano, M. 1990. Strict approximation on closed convex sets. Approximation Theory and its Applications 6, 1, 99–109.
26. Marchi, E., and Oviedo, J. A. 1992. Lexicographic optimality in the multiple objective linear programming: The nucleolar solution. Euro. J. Operational Research 57, 3, 355–359.Cross Ref
27. Mémoli, F., Sapiro, G., and Thompson, P. 2006. Geometric surface and brain warping via geodesic minimizing lipschitz extensions. In MFCA, 58–67.
28. Myles, A., and Zorin, D. 2012. Global parametrization by incremental flattening. TOG 31, 4, 109.
29. Myles, A., and Zorin, D. 2013. Controlled-distortion constrained global parametrization. TOG 32, 4, 105.
30. Ogryczak, W., and Sliwinski, T. 2007. Lexicographic maxmin optimization for efficient and fair bandwidth allocation. In International Network Optimization Conference (INOC).
31. Pólya, G. 1913. Sur un algorithme toujours convergent pour obtenir les polynômes de meilleure approximation de tchebycheff pour une function continue quelconque. CR Acad. Sci. París 157, 840–843.
32. Ray, N., Li, W., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. TOG 25, 4, 1460–1485.
33. Rice, J. R., and Usow, K. H. 1968. The lawson algorithm and extensions. Mathematics of Computation 22, 101, 118–127.
34. Rice, J. R. 1962. Tchebycheff approximation in a compact metric space. Bull. American Mathematical Society 68, 4, 405–410.Cross Ref
35. Rice, J. R. 1963. Tchebycheff approximation in several variables. Tran. American Mathematical Society 109, 3, 444–466.Cross Ref
36. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. CGF 32, 5, 125–135.
37. Sheffer, A., and de Sturler, E. 2001. Parameterization of Faceted Surfaces for Meshing using Angle-Based Flattening. Engineering with Computers 17, 3, 326–337.Cross Ref
38. Solomon, J., Ben-Chen, M., Butscher, A., and Guibas, L. 2011. As-killing-as-possible vector fields for planar deformation. In CGF, vol. 30, 1543–1552.Cross Ref
39. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, vol. 4.
40. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proc. IEEE Visualization ’02, 355–362.
41. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. TOG 27, 77:1–77:11.
42. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. In CGF, vol. 31, 1679–1689.
