Journal Home > Volume 2 , Issue 2

We present an efficient and robust method which performs well for both strain limiting and treatment of simultaneous collisions. Our method formulates strain constraints and collision constraints as a serial of linear matrix inequalities (LMIs) and linear polynomial inequalities (LPIs), and solves an optimization problem with standard convex semidefinite programming solvers. When performing strain limiting, our method acts on strain tensors to constrain the singular values of the deformation gradient matrix in a specified interval. Our method can be applied to both triangular surface meshes and tetrahedral volume meshes. Compared with prior strain limiting methods, our method converges much faster and guarantees triangle flipping does not occur when applied to a triangular mesh. When performing treatment of simultaneous collisions, our method eliminates all detected collisions during each iteration, leading to higher efficiency and faster convergence than prior collision treatment methods.


menu
Abstract
Full text
Outline
About this article

Efficient and robust strain limiting and treatment of simultaneous collisions with semidefinite programming

Show Author's information Zhendong Wang1( )Tongtong Wang1Min Tang1Ruofeng Tong1
College of Computer Science and Technology, Zhejiang University, China.

Abstract

We present an efficient and robust method which performs well for both strain limiting and treatment of simultaneous collisions. Our method formulates strain constraints and collision constraints as a serial of linear matrix inequalities (LMIs) and linear polynomial inequalities (LPIs), and solves an optimization problem with standard convex semidefinite programming solvers. When performing strain limiting, our method acts on strain tensors to constrain the singular values of the deformation gradient matrix in a specified interval. Our method can be applied to both triangular surface meshes and tetrahedral volume meshes. Compared with prior strain limiting methods, our method converges much faster and guarantees triangle flipping does not occur when applied to a triangular mesh. When performing treatment of simultaneous collisions, our method eliminates all detected collisions during each iteration, leading to higher efficiency and faster convergence than prior collision treatment methods.

Keywords: strain limiting, collision response, linear matrix inequality (LMI), semidefinite programming

References(21)

[1]
Wang, H.; O’Brien, J.; Ramamoorthi, R. Multiresolution isotropic strain limiting. ACM Transactions on Graphics Vol. 29, No. 6, Article No. 156, 2010.
[2]
Ma, G.; Ye, J.; Li, J.; Zhang, X. Anisotropic strain limiting for quadrilateral and triangular cloth meshes. Computer Graphics Forum Vol. 35, No. 1, 89-99, 2016.
[3]
Narain, R.; Samii, A.; O’Brien, J. F. Adaptive anisotropic remeshing for cloth simulation. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 152, 2012.
[4]
Bridson, R.; Fedkiw, R.; Anderson, J. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics Vol. 21, No. 3, 594-603, 2002.
[5]
Harmon, D.; Vouga, E.; Tamstorf, R.; Grinspun, E. Robust treatment of simultaneous collisions. ACM Transactions on Graphics Vol. 27, No. 3, Article No. 23, 2008.
[6]
Boyd, S.; Vandenberghe, L. Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
DOI
[7]
Provot, X. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In: Graphics Interface. Canadian Information Processing Society, 147-154, 1995.
[8]
Goldenthal, R.; Harmon, D.; Fattal, R.; Bercovier, M.; Grinspun, E. Efficient simulation of inextensible cloth. ACM Transactions on Graphics Vol. 26, No. 3, Article No. 49, 2007.
[9]
English, E.; Bridson, R. Animating developable surfaces using nonconforming elements. ACM Transactions on Graphics Vol. 27, No. 3, Article No. 66, 2008.
[10]
Thomaszewski, B.; Pabst, S.; Straßer, W. Continuum-based strain limiting. Computer Graphics Forum Vol. 28, No. 2, 569-576, 2009.
[11]
Brochu, T.; Edwards, E.; Bridson, R. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 96, 2012.
[12]
Tang, M.; Tong, R.; Wang, Z.; Manocha, D. Fast and exact continuous collision detection with Bernstein sign classification. ACM Transactions on Graphics Vol. 33, No. 6, Article No. 186, 2014.
[13]
Wang, H. Defending continuous collision detection against errors. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 122, 2014.
[14]
Provot, X. Collision and self-collision handling in cloth model dedicated to design garments. 1997. Available at https://graphics.stanford.edu/courses/cs468-02-winter/Papers/Collisions_vetements.pdf.
DOI
[15]
Huh, S.; Metaxas, D. N.; Badler, N. I. Collision resolutions in cloth simulation. In: Proceedings of the 14th Conference on Computer Animation, 122-127, 2001.
[16]
Tsiknis, K. D. Better cloth through unbiased strain limiting and physics-aware subdivision. Master Thesis. The University of British Columbia, 2006.
[17]
Tang, M.; Manocha, D.; Otaduy, M. A.; Tong, R. Continuous penalty forces. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 107, 2012.
[18]
Bouaziz, S.; Martin, S.; Liu, T.; Kavan, L.; Pauly, M. Projective dynamics: Fusing constraint projections for fast simulation. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 154, 2014.
[19]
Müller, M.; Heidelberger, B.; Hennix, M.; Ratcliff, J. Position based dynamics. Journal of Visual Communication and Image Representation Vol. 18, No. 2, 109-118, 2007.
[20]
Kovalsky, S. Z.; Aigerman, N.; Basri, R.; Lipman, Y. Controlling singular values with semidefinite programming. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 68, 2014.
[21]
Andersen, E. D.; Andersen, K. D. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In: Applied Optimization, Vol. 33. Frenk, H.; Roos, K.; Terlaky, T.; Zhang, S. Eds. Springer US, 197-232, 2000.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 02 December 2015
Accepted: 14 January 2016
Published: 07 April 2016
Issue date: June 2016

Copyright

© The Author(s) 2016

Acknowledgements

This research is supported in part by the National High-tech R&D Program of China (No. 2013AA013903), National Natural Science Foundation of China (No. 61572423), Zhejiang Provincial NSFC (No. LZ16F020003), the National Key Technology R&D Program of China (No. 2012BAD35B01), the Doctoral Fund of Ministry of Education of China (No. 20130101110133). Ruofeng Tong is partly supported by National Natural Science Foundation of China (No. 61572424).

Rights and permissions

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http:// creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.

Return