Yaron Lipman
Skip Abstract Section
Skip Supplemental Material SectionAbstract
The problem of mapping triangular meshes into the plane is fundamental in geometric modeling, where planar deformations and surface parameterizations are two prominent examples. Current methods for triangular mesh mappings cannot, in general, control the worst case distortion of all triangles nor guarantee injectivity.
This paper introduces a constructive definition of generic convex spaces of piecewise linear mappings with guarantees on the maximal conformal distortion, as-well as local and global injectivity of their maps. It is shown how common geometric processing objective functionals can be restricted to these new spaces, rather than to the entire space of piecewise linear mappings, to provide a bounded distortion version of popular algorithms.
Supplemental Material
- Ahlfors, L. 1966. Lectures on quasiconformal mappings. University lecture series. American Mathematical Society.Google Scholar
- Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of SIGGRAPH '00, ACM, New York, NY, USA, 157--164. Google ScholarDigital Library
- Amenta, A. B., Bern, M. W., and Eppstein, D. 1997. Optimal point placement for mesh smoothing. In Proc. 8th Symp. Discrete Algorithms, ACM and SIAM, 528--537. Google ScholarDigital Library
- Andersen, E. D., and Andersen, K. D. 1999. The MOSEK interior point optimization for linear programming: an implementation of the homogeneous algorithm. Kluwer Academic Publishers, 197--232.Google Scholar
- Aronov, B., Seidel, R., and Souvaine, D. 1993. On compatible triangulations of simple polygons. Comput. Geom. Theory Appl. 3 (June), 27--35. Google ScholarDigital Library
- Ben-chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27.Google Scholar
- Bern, M. W., and Eppstein, D. 1995. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, D.-Z. Du and F. K.-M. Hwang, Eds., second ed., no. 4 in Lecture Notes Series on Computing. World Scientific, 47--123.Google Scholar
- Bookstein, F. L. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11 (June), 567--585. Google ScholarDigital Library
- Brenner, S., and Scott, L. 2008. The mathematical theory of finite element methods. Texts in applied mathematics. Springer.Google Scholar
- Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29 (July), 38:1--38:6. Google ScholarDigital Library
- Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Pa-rameterizations of Surface Meshes. Computer Graphics Forum 21.Google Scholar
- Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH '95, 173--182. Google ScholarDigital Library
- Floater, M. S., and Hormann, K. 2005. Surface Parameterization: a Tutorial and Survey. Advances in Multiresolution for Geometric Modelling, 157--186.Google Scholar
- Floater, M. S. 2003. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation 72, 685--696. Google ScholarDigital Library
- Gaidashev, D., and Khmelev, D. 2008. On numerical algorithms for the solution of a beltrami equation. SIAM J. Numer. Anal. 46 (May), 2238--2253. Google ScholarDigital Library
- Gortler, S. J., Gotsman, C., and Thurston, D. 2006. Discrete one-forms on meshes and applications to 3d mesh parameterization. Comput. Aided Geom. Des. 23, 2 (Feb.). Google ScholarDigital Library
- Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999, P.-J. Laurent, P. Sablonnière, and L. L. Schumaker, Eds., Innovations in Applied Mathematics. Vanderbilt University Press, Nashville, TN, 153--162.Google Scholar
- Igarashi, T., Moscovich, T., and Hughes, F. J. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph 24, 1134--1141. Google ScholarDigital Library
- Imayoshi, Y., and Taniguchi, M. 1992. An introduction to Teichmüller spaces. Springer-Verlag.Google Scholar
- Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 30, 4, 78:1--78:8. Google ScholarDigital Library
- Jin, M., Kim, J., and Gu, X. D. 2007. Discrete surface ricci flow: Theory and applications. In In IMA Conference on the Mathematics of Surfaces, 209--232. Google ScholarDigital Library
- Johnen, A., Remacle, J.-F., and Geuzaine, C. 2012. Geometrical validity of curvilinear finite elements. In Proceedings of the 20th International Meshing Roundtable. 255--271.Google Scholar
- 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
- Levy, B., Petitjean, S., Ray, N., and Maillo t, J. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM SIGGRAPH conference proceedings, ACM, Ed. Google ScholarDigital Library
- Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
- Lipman, Y., Kim, V., and Funkhouser, T. 2012. Simple formulas for quasiconformal plane deformations. ACM Transactions on Graphics, accepted for publication. Google ScholarDigital Library
- Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP '08, 1495--1504. Google ScholarDigital Library
- Maillot, J., Yahia, H., and Verroust, A. 1993. Interactive texture mapping. In SIGGRAPH '93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 27--34. Google ScholarDigital Library
- Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15--36.Google ScholarCross Ref
- Ruppert, J. 1995. A delaunay refinement algorithm for quality 2-dimensional mesh generation. In Selected papers from the fourth annual ACM SIAM symposium on Discrete algorithms, Academic Press, Inc., Orlando, FL, USA, 548--585. Google ScholarDigital Library
- Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proceeding of SIGGRAPH '01, ACM, New York, NY, USA, 409--416. Google ScholarDigital Library
- Schaefer, S., McPhail, T., and Warren, J. 2006. Image deformation using moving least squares. ACM Trans. Graph. 25 (July), 533--540. Google ScholarDigital Library
- Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. Abf++: fast and robust angle based flattening. ACM Trans. Graph. 24 (April), 311--330. Google ScholarDigital Library
- Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2 (January), 105--171. Google ScholarDigital Library
- Shewchuk, J. R. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, May, 203--222. Google ScholarDigital Library
- Solomon, J., Ben-Chen, M., Butscher, A., and Guibas, L. 2011. As-Killing-As-Possible Vector Fields for Planar Deformation. Computer Graphics Forum 30, 5, 1543--1552.Google ScholarCross Ref
- Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 109--116. Google ScholarDigital Library
- Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of IEEE Visualization, IEEE Computer Society, 355--362. Google ScholarDigital Library
- Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27 (August), 77:1--77:11. Google ScholarDigital Library
- Stephenson, K. 2005. Introduction to circle packing: the theory of discrete analytic functions. Cambridge University Press.Google Scholar
- Tutte, W. T. 1963. How to Draw a Graph. Proceedings of the London Mathematical Society s3--13, 1, 743--767.Google ScholarCross Ref
- Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 78:1--78:11. Google ScholarDigital Library
- Zeng, W., and Gu, X. D. 2011. Registration for 3d surfaces with large deformations using quasi-conformal curvature flow. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2457--2464. Google ScholarDigital Library
- Zeng, W., Luo, F., Yau, S. T., and Gu, X. D. 2009. Surface quasi-conformal mapping by solving beltrami equations. In Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XIII, Springer-Verlag, Berlin, Heidelberg, 391--408. Google ScholarDigital Library
Recommendations
Injective and bounded distortion mappings in 3D
We introduce an efficient algorithm for producing provably injective mappings of tetrahedral meshes with strict bounds on their tetrahedra aspect-ratio distortion.
The algorithm takes as input a simplicial map (e.g., produced by some common deformation ...
Planar shape interpolation with bounded distortion
Planar shape interpolation is widely used in computer graphics applications. Despite a wealth of interpolation methods, there is currently no approach that produces shapes with a bounded amount of distortion with respect to the input. As a result, ...
On the convexity and feasibility of the bounded distortion harmonic mapping problem
Computation of mappings is a central building block in many geometry processing and graphics applications. The pursuit to compute mappings that are injective and have a controllable amount of conformal and isometric distortion is a long endeavor which ...
Comments