Zohar Levi
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
a185.zip (529.5 KB)
Supplemental material.
- Abdelmalek, N. N. 1977. Computing the strict Chebyshev solution of overdetermined linear equations. Mathematics of Computation 31, 140, 974--983.Google Scholar
- Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3D. TOG 32, 4, 106. Google ScholarDigital Library
- Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Computer graphics and interactive techniques, 157--164. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Behringer, F. 1981. A simplex-based algorithm for the lexico-graphically extended linear maxmin problem. Euro. J. Operational Research 7, 3, 274--283.Google ScholarCross Ref
- Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27, 2, 449--458.Google ScholarCross Ref
- Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Desbrun, M., Meyer, M., and Alliez, P. 2002. Meshes and parameterization: Intrinsic parameterizations of surface meshes. Computer Graphics Forum 21, 3, 209.Google ScholarCross Ref
- Descloux, J. 1963. Approximations in Lp and Chebyshev approximations. Journal of the Society for Industrial & Applied Mathematics 11, 4, 1017--1026.Google ScholarCross Ref
- Fletcher, R., Grant, J., and Hebden, M. 1971. The calculation of linear best Lp approximations. The Computer Journal 14, 3, 276--279.Google ScholarCross Ref
- Gao, L., Zhang, G., and Lai, Y. 2012. lp shape deformation. Science China Information Sciences 55, 5, 983--993.Google ScholarCross Ref
- Hormann, K., and Greiner, G. 1999. MIPS: An efficient global parameterization method. Curve and Surface Design: Saint-Malo 2000, 153--162.Google Scholar
- Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-Cover: Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3, 375--384.Google ScholarCross Ref
- Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25 (April), 412--438. Google ScholarDigital Library
- Lawson, C. L. 1972. Transforming triangulations. Discrete mathematics 3, 4, 365--372. Google ScholarDigital Library
- Levi, Z., and Gotsman, C. 2015. Smooth rotation enhanced as-rigid-as-possible mesh animation. TVCG.Google Scholar
- 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
- Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4, 108. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Luss, H., and Smith, D. R. 1986. Resource allocation among competing activities: A lexicographic minimax approach. Operations Research Letters 5, 5, 227--231. Google ScholarDigital Library
- Marano, M. 1990. Strict approximation on closed convex sets. Approximation Theory and its Applications 6, 1, 99--109.Google Scholar
- 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.Google ScholarCross Ref
- Mémoli, F., Sapiro, G., and Thompson, P. 2006. Geometric surface and brain warping via geodesic minimizing lipschitz extensions. In MFCA, 58--67.Google Scholar
- Myles, A., and Zorin, D. 2012. Global parametrization by incremental flattening. TOG 31, 4, 109. Google ScholarDigital Library
- Myles, A., and Zorin, D. 2013. Controlled-distortion constrained global parametrization. TOG 32, 4, 105. Google ScholarDigital Library
- Ogryczak, W., and Sliwinski, T. 2007. Lexicographic maxmin optimization for efficient and fair bandwidth allocation. In International Network Optimization Conference (INOC).Google Scholar
- 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.Google Scholar
- Ray, N., Li, W., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. TOG 25, 4, 1460--1485. Google ScholarDigital Library
- Rice, J. R., and Usow, K. H. 1968. The lawson algorithm and extensions. Mathematics of Computation 22, 101, 118--127.Google Scholar
- Rice, J. R. 1962. Tchebycheff approximation in a compact metric space. Bull. American Mathematical Society 68, 4, 405--410.Google ScholarCross Ref
- Rice, J. R. 1963. Tchebycheff approximation in several variables. Tran. American Mathematical Society 109, 3, 444--466.Google ScholarCross Ref
- Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. CGF 32, 5, 125--135. Google ScholarDigital Library
- Sheffer, A., and de Sturler, E. 2001. Parameterization of Faceted Surfaces for Meshing using Angle-Based Flattening. Engineering with Computers 17, 3, 326--337.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, vol. 4. Google ScholarDigital Library
- Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proc. IEEE Visualization '02, 355--362. Google ScholarDigital Library
- Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. TOG 27, 77:1--77:11. Google ScholarDigital Library
- Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. In CGF, vol. 31, 1679--1689. Google ScholarDigital Library
Index Terms
- Strict minimizers for geometric optimization
Recommendations
Simple constrained deformations for geometric modeling and interactive design
Special issue on interactive sculptingDeformations are a powerful tool for shape modeling and design. We present a new model for producing controlled spatial deformations, which we term Simple Constrained Deformations (Scodef). The user defines a set of constraint points, giving a desired ...
A Method for Deforming Polygonal Shapes into Smooth Spline Surface Models
IV '99: Proceedings of the 1999 International Conference on Information VisualisationThis paper describes a new spline formulation that supports deformation of polygonal shapes into smooth spline surface models. Once a polygonal shape with underlying rectangular topology is specified by the user, it is deformed into a smooth surface ...
Technical Section: Layered deformation of solid model using conformal mapping
In this paper, we present a solid model deformation method based on layered conformal mapping. For a solid model represented by base patch and height field, the shape of the model can be deformed by interactive means, such as changing the base patch by ...
Comments