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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Wang, H.; O’Brien, J.; Ramamoorthi, R. Multiresolution isotropic strain limiting. ACM Transactions on Graphics Vol. 29, No. 6, Article No. 156, 2010.
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.
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.
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.
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.
Boyd, S.; Vandenberghe, L. Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
Provot, X. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In: Graphics Interface. Canadian Information Processing Society, 147–154, 1995.
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.
English, E.; Bridson, R. Animating developable surfaces using nonconforming elements. ACM Transactions on Graphics Vol. 27, No. 3, Article No. 66, 2008.
Thomaszewski, B.; Pabst, S.; Straßer, W. Continuumbased strain limiting. Computer Graphics Forum Vol. 28, No. 2, 569–576, 2009.
Brochu, T.; Edwards, E.; Bridson, R. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 96, 2012.
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.
Wang, H. Defending continuous collision detection against errors. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 122, 2014.
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.
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.
Tsiknis, K. D. Better cloth through unbiased strain limiting and physics-aware subdivision. Master Thesis. The University of British Columbia, 2006.
Tang, M.; Manocha, D.; Otaduy, M. A.; Tong, R. Continuous penalty forces. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 107, 2012.
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.
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.
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.
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.
Author information
Authors and Affiliations
Corresponding author
Additional information
Zhendong Wang is a Ph.D. candidate in the College of Computer Science and Technology at Zhejiang University, Hangzhou, China. He received his B.S. degree in 2013 from the College of Computer atWuhan University,Wuhan, China. His research interests include physically-based cloth simulation, collision detection, and GPU computing.
Tongtong Wang is a Ph.D. candidate in the College of Computer Science and Technology at Zhejiang University, Hangzhou, China. She received her B.S. degree in 2014 from Shandong University, Jinan, China. Her research interests include cloth simulation and collision detection.
Min Tang received his B.S. degree in 1994 and Ph.D. degree in 1999 from the Department of Computer Science and Engineering at Zhejiang University, Hangzhou, China. Currently, he is a professor at Zhejiang University. He was a visiting scholar in the Department of Computer Science, Wichita State University in 2006, and in the Department of Computer Science, UNC-Chapel Hill in 2008. His research interests include image processing, CAD&CG, and collision detection.
Ruofeng Tong received his B.S. degree in 1991 from the Department of Mathematics at Fudan University and Ph.D. degree in 1996 from the Department of Mathematics at Zhejiang University, China. Currently, he is a professor in the College of Computer Science and Engineering, Zhejiang University. His research interests include computer vision, image processing, and CAD&CG.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as 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.
About this article
Cite this article
Wang, Z., Wang, T., Tang, M. et al. Efficient and robust strain limiting and treatment of simultaneous collisions with semidefinite programming. Comp. Visual Media 2, 119–130 (2016). https://doi.org/10.1007/s41095-016-0042-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41095-016-0042-8