Abstract
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, existing interpolation methods may produce shapes that are significantly different than the input and can suffer from fold-overs and other visual artifacts, making them less useful in many practical scenarios. We introduce a novel shape interpolation scheme designed specifically to produce results with a bounded amount of conformal (angular) distortion. Our method is based on an elegant continuous mathematical formulation and provides several appealing properties such as existence and uniqueness of the solution as well as smoothness in space and time domains. We further present a discretization and an efficient practical algorithm to compute the interpolant and demonstrate its usability and good convergence behavior on a wide variety of input shapes. The method is simple to implement and understand. We compare our method to state-of-the-art interpolation methods and demonstrate its superiority in various cases.
Supplemental Material
Available for Download
Supplemental material.
- Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 157--164. Google ScholarDigital Library
- Alexa, M. 2002. Recent advances in mesh morphing. In Computer graphics forum, vol. 21, Wiley Online Library, 173--198.Google Scholar
- Bao, Y., Guo, X., and Qin, H. 2005. Physically based morphing of point-sampled surfaces. Computer Animation and Virtual Worlds 16, 3--4, 509--518. Google ScholarDigital Library
- Baxter, W., Barla, P., and Anjyo, K. 2008. Rigid shape interpolation using normal equations. In Proceedings of the 6th international symposium on Non-photorealistic animation and rendering, ACM, 59--64. Google ScholarDigital Library
- Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics (TOG) 29, 4, 38. Google ScholarDigital Library
- Choi, J., and Szymczak, A. 2003. On coherent rotation angles for as-rigid-as-possible shape interpolation.Google Scholar
- Crane, K., Pinkall, U., and Schröder, P. 2011. Spin transformations of discrete surfaces. ACM Trans. Graph. 40. Google ScholarDigital Library
- Fröhlich, S., and Botsch, M. 2011. Example-driven deformations based on discrete shells. In Computer Graphics Forum, vol. 30, Wiley Online Library, 2246--2257.Google Scholar
- Fu, H., Tai, C., and Au, O. 2005. Morphing with laplacian coordinates and spatial-temporal texture. In Proceedings of Pacific Graphics, 100--102.Google Scholar
- Gray, A., Abbena, E., and Salamon, S. 2006. Modern differential geometry of curves and surfaces with Mathematica. Chapman & Hall/CRC. Google ScholarDigital Library
- Gu, D., Luo, F., and Yau, S. 2010. Fundamentals of computational conformal geometry. Mathematics in Computer Science 4, 4, 389--429.Google ScholarCross Ref
- Hu, S., Li, C., and Zhang, H. 2004. Actual morphing: a physics-based approach to blending. In Proceedings of the ninth ACM symposium on Solid modeling and applications, Eurographics Association, 309--314. Google ScholarDigital Library
- Igarashi, T., Moscovich, T., and Hughes, J. 2005. As-rigid-as-possible shape manipulation. In ACM Transactions on Graphics (TOG), vol. 24, ACM, 1134--1141. Google ScholarDigital Library
- Kilian, M., Mitra, N., and Pottmann, H. 2007. Geometric modeling in shape space. In ACM Transactions on Graphics (TOG), vol. 26, ACM, 64. Google ScholarDigital Library
- Kircher, S., and Garland, M. 2008. Free-form motion processing. ACM Transactions on Graphics (TOG) 27, 2, 12. Google ScholarDigital Library
- Klassen, E., Srivastava, A., Mio, M., and Joshi, S. 2004. Analysis of planar shapes using geodesic paths on shape spaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on 26, 3, 372--383. Google ScholarDigital Library
- Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Transactions on Graphics (TOG) 24, 3, 479--487. Google ScholarDigital Library
- Lipman, Y., Kim, V., and Funkhouser, T. 2012. Simple formulas for quasiconformal plane deformations. ACM Transactions on Graphics (TOG) 31, 5, 124. 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., Wang, G., Zhang, B., Guo, B., and Shum, H. 2004. Perceptually based approach for planar shape morphing. In Computer Graphics and Applications, 2004. PG 2004. Proceedings. 12th Pacific Conference on, IEEE, 111--120. Google ScholarDigital Library
- Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Computer Graphics Forum, vol. 27, Wiley Online Library, 1495--1504. Google ScholarDigital Library
- Sederberg, T., and Greenwood, E. 1992. A physically based approach to 2--d shape blending. In ACM SIGGRAPH Computer Graphics, vol. 26, ACM, 25--34. Google ScholarDigital Library
- Shapira, M., and Rappoport, A. 1995. Shape blending using the star-skeleton representation. Computer Graphics and Applications, IEEE 15, 2, 44--50. Google ScholarDigital Library
- Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004. Proceedings. 2nd International Symposium on, IEEE, 68--75. Google ScholarDigital Library
- Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In ACM International Conference Proceeding Series, vol. 257, Citeseer, 109--116. Google ScholarDigital Library
- Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27, 3 (Aug.), 77:1--77:11. Google ScholarDigital Library
- Surazhsky, T., and Elber, G. 2002. Metamorphosis of planar parametric curves via curvature interpolation. International Journal of Shape Modeling 8, 02, 201--216.Google ScholarCross Ref
- Surazhsky, V., and Gotsman, C. 2001. Controllable morphing of compatible planar triangulations. ACM Transactions on Graphics 20, 4, 203--231. Google ScholarDigital Library
- Surazhsky, V., and Gotsman, C. 2003. Intrinsic morphing of compatible triangulations. International Journal of Shape Modeling 9, 02, 191--201.Google ScholarCross Ref
- Sykora, D., Dingliana, J., and Collins, S. 2009. As-rigid-as-possible image registration for hand-drawn cartoon animations. In Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering, ACM, 25--33. Google ScholarDigital Library
- Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Transactions on Graphics (TOG) 29, 4, 78. Google ScholarDigital Library
- Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. In Computer Graphics Forum, vol. 31, Wiley Online Library, 1679--1689. Google ScholarDigital Library
- Weintraub, S. 1997. Differential forms: a complement to vector calculus. Academic Press, San Diego.Google Scholar
- Whited, B., and Rossignac, J. 2011. Ball-morph: Definition, implementation, and comparative evaluation. Visualization and Computer Graphics, IEEE Transactions on 17, 6, 757--769. Google ScholarDigital Library
- Winkler, T., Drieseberg, J., Alexa, M., and Hormann, K. 2010. Multi-scale geometry interpolation. In Computer Graphics Forum, vol. 29, Wiley Online Library, 309--318.Google Scholar
- Wolberg, G. 1998. Image morphing: a survey. The visual computer 14, 8, 360--372.Google Scholar
- Xu, D., Zhang, H., Wang, Q., and Bao, H. 2006. Poisson shape interpolation. Graphical models 68, 3, 268--281. Google ScholarDigital Library
- Zeng, W., Luo, F., Yau, S., and Gu, X. 2009. Surface quasi-conformal mapping by solving beltrami equations. Mathematics of Surfaces XIII, 391--408. Google ScholarDigital Library
Index Terms
- Planar shape interpolation with bounded distortion
Recommendations
Bounded distortion harmonic shape interpolation
Planar shape interpolation is a classic problem in computer graphics. We present a novel shape interpolation method that blends C∞ planar harmonic mappings represented in closed-form. The intermediate mappings in the blending are guaranteed to be ...
Real-Time Nonlinear Shape Interpolation
We introduce a scheme for real-time nonlinear interpolation of a set of shapes. The scheme exploits the structure of the shape interpolation problem, in particular the fact that the set of all possible interpolated shapes is a low-dimensional object in ...
Bounded distortion mapping spaces for triangular meshes
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 ...
Comments