A survey on fast simulation of elastic objects

doi:10.1007/s11704-018-8081-1

Front. Comput. Sci.

2019, Vol. 13

Issue (3) : 443-459 https://doi.org/10.1007/s11704-018-8081-1

REVIEW ARTICLE

A survey on fast simulation of elastic objects

Jin HUANG, Jiong CHEN, Weiwei XU(

), Hujun BAO(

)

State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310058, China

Download: PDF(872 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Elastic simulation plays an important role in computer graphics and has been widely applied to film and game industries. It also has a tight relationship to virtual reality and computational fabrication applications. The balance between accuracy and performance are the most important challenge in the design of an elastic simulation algorithm. This survey will begin with the basic knowledge of elastic simulation, and then investigate two major acceleration techniques for it. From the viewpoint of deformation energy, we introduce typical linearization and reduction ideas for accelerating. We also introduce some recent progress in projective and position-based dynamics, which mainly rely on special numerical methods. Besides, optimal control for elastic objects and typical collision resolving techniques are discussed. Finally, we discuss several possible future works on integrating elastic simulation into virtual reality and 3D printing applications.

Keywords computer graphics elastic simulation reduction linearization

Corresponding Author(s): Weiwei XU

Just Accepted Date: 16 October 2018 Online First Date: 26 February 2019 Issue Date: 24 April 2019

Cite this article:

Jin HUANG,Jiong CHEN,Weiwei XU, et al. A survey on fast simulation of elastic objects[J]. Front. Comput. Sci., 2019, 13(3): 443-459.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-8081-1
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I3/443

1	SBrenner, RScott. TheMathematical Theory of Finite Element Methods. Springer Science & Business Media, 2007
2	MHauth, O Etzmuss, WStrasser. Analysis of numerical methods for the simulation of deformable models. The Visual Computer, 2003, 19(7): 581–600 https://doi.org/10.1007/s00371-003-0206-2
3	DBaraff, AWitkin. Large steps in cloth simulation. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniqtdes. 1998, 43–54 https://doi.org/10.1145/280814.280821
4	ESifakis, JBarbic. FEM simulation of 3D deformable solids: a practitioner’s guide to theory, discretization and model reduction. In: Proceedings of ACM SIGGRAPH 2012 Courses. 2012, 20 https://doi.org/10.1145/2343483.2343501
5	MMüller, MGross. Interactive virtual materials. In: Proceedings of the Conference on Graphics Interface. 2004, 239–246
6	DTerzopoulos, AWitkin. Physically based models with rigid and deformable components. IEEE Computer Graphics and Applications, 1988, 8(6): 41–51 https://doi.org/10.1109/38.20317
7	DMetaxas, D Terzopoulos. Dynamic deformation of solid primitives with constraints. ACM SIGGRAPH Computer Graphics, 1992, 26(2): 309–312 https://doi.org/10.1145/142920.134085
8	K KHauser, CShen, J FO’Brien. Interactive deformation using modal analysis with constraints. In: Proceedings of the Conference on Graphics Interface. 2003, 16–17
9	D MKaufman, SSueda, D LJames, D K Pai. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics, 2008, 27(5): 164 https://doi.org/10.1145/1409060.1409117
10	TKim, D LJames. Physics-based character skinning using multidomain subspace deformations. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8): 1228–1240 https://doi.org/10.1109/TVCG.2012.78
11	SCapell, SGreen, BCurless, T Duchamp, ZPopović. Interactive skeleton-driven dynamic deformations. ACM Transactions on Graphics, 2002, 21(3): 586–593 https://doi.org/10.1145/566654.566622
12	JHuang, XLiu, HBao, B Guo, H YShum. An efficient large deformation method using domain decomposition. Computers & Graphics, 2006, 30(6): 927–935 https://doi.org/10.1016/j.cag.2006.08.014
13	JBarbič, YZhao. Real-time large-deformation substructuring. ACM Transactions on Graphics, 2011, 30(4): 91
14	MMüller, JDorsey, LMcMillan, R Jagnow, BCutler. Stable real-time deformations. In: Proceedings of the 2002 ACM SIGGRAPH/ Eurographics Symposium on Computer Animation. 2002, 49–54 https://doi.org/10.1145/545261.545269
15	OEtzmuß, M Keckeisen, WStraßer. A fast finite element solution for cloth modelling. In: Proceedings of the 11th Pacific Conference on Computer Graphics and Applications. 2003, 244–251 https://doi.org/10.1109/PCCGA.2003.1238266
16	IChao, U Pinkall, PSanan, PSchröder. A simple geometric model for elastic deformations. ACM Transactions on Graphics, 2010, 29(4): 38 https://doi.org/10.1145/1778765.1778775
17	AMcAdams, YZhu, ASelle, M Empey, RTamstorf, JTeran, E Sifakis. Efficient elasticity for character skinning with contact and collisions. ACM Transactions on Graphics, 2011, 30(4): 37 https://doi.org/10.1145/2010324.1964932
18	SMartin, P Kaufmann, MBotsch, MWicke, MGross. Polyhedral finite elements using harmonic basis functions. Computer Graphics Forum, 2008, 27(5): 1521–1529 https://doi.org/10.1111/j.1467-8659.2008.01293.x
19	Z FFu, JHe. Modal Analysis. Oxford: Butterworth-Heinemann, 2001
20	JBarbič, DJames. Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models. In: Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2007, 171–180
21	APentland, J Williams. Good vibrations: modal dynamics for graphics and animation. ACMSIGGRAPH Computer Graphics, 1989, 23(3): 207–214 https://doi.org/10.1145/74334.74355
22	MSilva, N MMaia. Modal Analysis and Testing. Springer-Verlag, 1989
23	JBarbič, D LJames. Real-time subspace integration for St. Venant- Kirchhoff deformable models. ACM Transactions on Graphics, 2005, 24(3): 982–990 https://doi.org/10.1145/1073204.1073300
24	CVon Tycowicz, CSchulz, H PSeidel, K Hildebrandt. An efficient construction of reduced deformable objects. ACM Transactions on Graphics, 2013, 32(6): 213 https://doi.org/10.1145/2508363.2508392
25	YYang, DLi, WXu, YTian, CZheng. Expediting precomputation for reduced deformable simulation. ACM Transactions on Graphics, 2015, 34(6): 243 https://doi.org/10.1145/2816795.2818089
26	T RLanglois, S SAn, K KJin, D L James. Eigenmode compression for modal sound models. ACM Transactions on Graphics, 2014, 33(4): 40 https://doi.org/10.1145/2601097.2601177
27	CZheng, D LJames. Toward high-quality modal contact sound. ACM Transactions on Graphics, 2011, 30(4): 38 https://doi.org/10.1145/2010324.1964933
28	P GKry, D LJames, D KPai. Eigenskin: real time large deformation character skinning in hardware. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2002, 153–159 https://doi.org/10.1145/545261.545286
29	TKim, D LJames. Skipping steps in deformable simulation with online model reduction. ACM Transactions on Graphics, 2009, 28(5): 123 https://doi.org/10.1145/1618452.1618469
30	SMartin, B Thomaszewski, EGrinspun, MGross. Example-based elastic materials. ACM Transactions on Graphics, 2011, 30(4):72 https://doi.org/10.1145/2010324.1964967
31	WZhang, JZheng, N MThalmann. Real-time subspace integration for example-based elastic material. Computer Graphics Forum, 2015, 34(2): 395–404 https://doi.org/10.1111/cgf.12569
32	HXu, YLi, YChen, J Barbič. Interactive material design using model reduction. ACM Transactions on Graphics, 2015, 34(2): 18 https://doi.org/10.1145/2699648
33	XChen, CZheng, KZhou. Example-based subspace stress analysis for interactive shape design. IEEE Transactions on Visualization and Computer Graphics, 2017, 23(10): 2314–2327 https://doi.org/10.1109/TVCG.2016.2618875
34	FHahn, SMartin, BThomaszewski, RSumner, SCoros, MGross. Rig-space physics. ACM Transactions on Graphics, 2012, 31(4): 72 https://doi.org/10.1145/2185520.2185568
35	FHahn, B Thomaszewski, SCoros, R WSumner, MGross. Efficient simulation of secondary motion in rig-space. In: Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2013, 165–171 https://doi.org/10.1145/2485895.2485918
36	S WBailey, DOtte, PDilorenzo, J F O’Brien. Fast and deep deformation approximations. ACM Transactions on Graphics, 2018, 37(4): 119 https://doi.org/10.1145/3197517.3201300
37	BGilles, G Bousquet, FFaure, D KPai. Frame-based elastic models. ACM Transactions on Graphics, 2011, 30(2): 15 https://doi.org/10.1145/1944846.1944855
38	PJoshi, MMeyer, TDeRose, B Green, TSanocki. Harmonic coordinates for character articulation. ACM Transactions on Graphics, 2007, 26(3): 71 https://doi.org/10.1145/1276377.1276466
39	YTeng, MMeyer, TDeRose, T Kim. Subspace condensation: full space adaptivity for subspace deformations. ACM Transactions on Graphics, 2015, 34(4): 76 https://doi.org/10.1145/2766904
40	YYang, WXu, XGuo, K Zhou, BGuo. Boundary-aware multidomain subspace deformation. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(10): 1633–1645 https://doi.org/10.1109/TVCG.2013.12
41	WLu, NJin, RFedkiw. Two-way coupling of fluids to reduced deformable bodies. In: Proceedings of the ACM SIGGRAPH/ Eurographics Symposium on Computer Animation. 2016, 67–76
42	CYang, SLi, YLan, L Wang, AHao, HQin. Coupling time-varying modal analysis and FEM for real-time cutting simulation of objects with multi-material sub-domains. Computer Aided Geometric Design, 2016, 43: 53–67 https://doi.org/10.1016/j.cagd.2016.02.014
43	DHarmon, DZorin. Subspace integration with local deformations. ACM Transactions on Graphics, 2013, 32(4): 107 https://doi.org/10.1145/2461912.2461922
44	YWang, A Jacobson, JBarbič, LKavan. Linear subspace design for real-time shape deformation. ACM Transactions on Graphics, 2015, 34(4): 57 https://doi.org/10.1145/2766952
45	CYang, SLi, YLan, L Wang, AHao, HQin. Coupling time-varying modal analysis and fem for real-time cutting simulation of objects with multi-material sub-domains. Computer Aided Geometric Design, 2016, 43: 53–67 https://doi.org/10.1016/j.cagd.2016.02.014
46	S SAn, TKim, D LJames. Optimizing cubature for efficient integration of subspace deformations. ACM Transactions on Graphics, 2008, 27(5): 165 https://doi.org/10.1145/1409060.1409118
47	M GChoi, H SKo. Modal warping: real-time simulation of large rotational deformation and manipulation. IEEE Transactions on Visualization and Computer Graphics, 2005, 11(1): 91–101 https://doi.org/10.1109/TVCG.2005.13
48	JHuang, YTong, KZhou, H Bao, MDesbrun. Interactive shape interpolation through controllable dynamic deformation. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(7): 983–992 https://doi.org/10.1109/TVCG.2010.109
49	SLi, JHuang, FGoes de, X Jin, HBao, MDesbrun. Space-time editing of elastic motion through material optimization and reduction. ACMTransactions on Graphics, 2014, 33(4): 108 https://doi.org/10.1145/2601097.2601217
50	ZPan, HBao, JHuang. Subspace dynamic simulation using rotationstrain coordinates. ACM Transactions on Graphics, 2015, 34(6): 242 https://doi.org/10.1145/2816795.2818090
51	MMüller, B Heidelberger, MTeschner, MGross. Meshless deformations based on shape matching. ACM Transactions on Graphics, 2005, 24(3): 471–478 https://doi.org/10.1145/1073204.1073216
52	MMüller, HBruno, HMarcus, R John. Position based dynamics. Journal of Visual Communication and Image Representation, 2007, 18(2): 109–118 https://doi.org/10.1016/j.jvcir.2007.01.005
53	A RRivers, D LJames. Fastlsm: fast lattice shape matching for robust real-time deformation. ACM Transactions on Graphics, 2007, 26(3): 82 https://doi.org/10.1145/1276377.1276480
54	MMüller, N Chentanez. Solid simulation with oriented particles. ACM Transactions on Graphics, 2011, 30(4): 92 https://doi.org/10.1145/2010324.1964987
55	JBender, M Müller, M AOtaduy, MTeschner. Position-based methods for the simulation of solid objects in computer graphics. In: Proceedings of Eurographics 2013-State of the Art Reports. 2013, 1–22
56	MFratarcangeli, V Tibaldo, FPellacini. Vivace: a practical gauss-seidel method for stable soft body dynamics. ACM Transactions on Graphics, 2016, 35(6): 214 https://doi.org/10.1145/2980179.2982437
57	CDeul, T Kugelstadt, MWeiler, JBender. Direct position-based solver for stiff rods. In: Proceedings of Computer Graphics Forum. 2018 https://doi.org/10.1111/cgf.13326
58	JHuang, XShi, XLiu, K Zhou, BGuo, HBao. Geometrically based potential energy for simulating deformable objects. The Visual Computer, 2006, 22(9): 740–748 https://doi.org/10.1007/s00371-006-0058-7
59	JHuang, HZhang, XShi, X Liu, HBao. Interactive mesh deformation with pseudo material effects. Computer Animation and Virtual Worlds, 2006, 17(3-4): 383–392 https://doi.org/10.1002/cav.141
60	TLiu, A W Bargteil, J FOBrien, LKavan. Fast simulation of massspring systems. ACM Transactions on Graphics, 2013, 32(6): 214 https://doi.org/10.1145/2508363.2508406
61	SBouaziz, SMartin, TLiu, L Kavan, MPauly. Projective dynamics: fusing constraint projections for fast simulation. ACM Transactions on Graphics, 2014, 33(4): 154 https://doi.org/10.1145/2601097.2601116
62	CBrant, E Eisemann, KHilbebrant. Hyper-reduced projective dynamics. ACM Transactions on Graphics, 2018, 37(4): 154 https://doi.org/10.1145/3197517.3201387
63	RNarain, MOverby, G EBrown. Admm &supe; projective dynamics: fast simulation of general constitutive models. In: Proceedings of the ACMSIGGRAPH/Eurographics Symposium on Computer Animation. 2016, 21–28
64	HWang. A chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics, 2015, 34(6): 246 https://doi.org/10.1145/2816795.2818063
65	TLiu, S Bouaziz, LKavan. Quasi-newton methods for real-time simulation of hyperelastic materials. ACM Transactions on Graphics, 2017, 36(3): 23 https://doi.org/10.1145/2990496
66	HWang, YYang. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics, 2016, 35(6): 212 https://doi.org/10.1145/2980179.2980236
67	YPeng, BDeng, JZhang, F Geng, WQin, LLiu. Anderson acceleration for geometry optimization and physics simulation. 2018, arXiv preprint arXiv: 1805.05715
68	AWitkin, MKass. Spacetime constraints. ACM Siggraph Computer Graphics, 1988, 22(4): 159–168 https://doi.org/10.1145/378456.378507
69	JBarbič, M Silva da, JPopovíc. Deformable object animation using reduced optimal control. ACM Transactions on Graphics, 2009, 28(3): 53
70	KHildebrandt, CSchulz, CTycowicz von, KPolthier. Interactive spacetime control of deformable objects. ACM Transactions on Graphics, 2012, 31(4): 71 https://doi.org/10.1145/2185520.2185567
71	MKass, J Anderson. Animating oscillatory motion with overlap: wiggly splines. ACM Transactions on Graphics, 2008, 27(3): 28 https://doi.org/10.1145/1360612.1360627
72	JBarbič, FSin, EGrinspun. Interactive editing of deformable simulations. ACM Transactions on Graphics, 2012, 31(4): 70
73	SLi, JHuang, MDesbrun, X Jin. Interactive elastic motion editing through space–time position constraints. Computer Animation and Virtual Worlds, 2013, 24(3-4): 409–417 https://doi.org/10.1002/cav.1521
74	JBarbič, J Popovíc. Real-time control of physically based simulations using gentle forces. ACM Transactions on Graphics, 2008, 27(5): 163
75	CSchulz, C Tycowicz von, H PSeidel, KHildebrandt. Animating deformable objects using sparse spacetime constraints. ACM Transactions on Graphics, 2014, 33(4): 109 https://doi.org/10.1145/2601097.2601156
76	MTeschner, S Kimmerle, BHeidelberger, GZachmann, L Raghupathi, AFuhrmann, M PCani, FFaure, NMagnenat-Thalmann, WStrasser, PVolino. Collision detection for deformable objects. Computer Graphics Forum, 2005, 24(1): 61–81 https://doi.org/10.1111/j.1467-8659.2005.00829.x
77	SRedon, A Kheddar, SCoquillart. Fast continuous collision detection between rigid bodies. Computer Graphics Forum, 2002, 21(3): 279–287 https://doi.org/10.1111/1467-8659.t01-1-00587
78	XZhang, SRedon, MLee, Y J Kim. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Transactions on Graphics, 2007, 26(3): 15 https://doi.org/10.1145/1276377.1276396
79	XProvot. Collision and Self-collision Handling in Cloth Model Dedicated to Design Garments. Computer Animation and Simulation, Springer, Vienna, 1997, 177–189
80	RBridson, RFedkiw, JAnderson. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics (ToG), 2002, 21(3): 594–603 https://doi.org/10.1145/566654.566623
81	DHarmon, EVouga, RTamstorf, E Grinspun. Robust treatment of simultaneous collisions. ACM Transactions on Graphics, 2008, 27(3): 23 https://doi.org/10.1145/1360612.1360622
82	TBrochu, E Edwards, RBridson. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics, 2012, 31(4): 96 https://doi.org/10.1145/2185520.2185592
83	MTang, D Manocha, S EYoon, PDu, J PHeo, R FTong. Volccd: fast continuous collision culling between deforming volume meshes. ACM Transactions on Graphics, 2011, 30(5): 111 https://doi.org/10.1145/2019627.2019630
84	MTang, RTong, ZWang, D Manocha. Fast and exact continuous collision detection with bernstein sign classification. ACM Transactions on Graphics, 2014, 33(6): 186 https://doi.org/10.1145/2661229.2661237
85	HWang. Defending continuous collision detection against errors. ACM Transactions on Graphics, 2014, 33(4): 122 https://doi.org/10.1145/2601097.2601114
86	ZWang, MTang, RTong, D Manocha. Tightccd: efficient and robust continuous collision detection using tight error bounds. Computer Graphics Forum, 2015, 34(7): 289–298 https://doi.org/10.1111/cgf.12767
87	K JChoi, H SKo. Stable but responsive cloth. In: Proceedings of ACM SIGGRAPH 2005 Courses. 2005 https://doi.org/10.1145/1198555.1198571
88	SFisher, M CLin. Deformed Distance Fields for Simulation of Non-penetrating Flexible Bodies. Computer Animation and Simulation 2001, Springer, Vienna, 2001, 99–111
89	MKeiser, B Heidelberger, MGross. Consistent Penetration Depth Estimation for Deformable Collision Response. Vision, Modeling, and Visualization, IOS Press, 2004, 339–346
90	DHarmon, EVouga, BSmith, R Tamstorf, EGrinspun. Asynchronous contact mechanics. ACM Transactions on Graphics, 2009, 28(3): 87 https://doi.org/10.1145/1531326.1531393
91	MTang, D Manocha, M AOtaduy, RTong. Continuous penalty forces. ACM Transactions on Graphics, 2012, 31(4): 107 https://doi.org/10.1145/2185520.2185603
92	M AOtaduy, R Tamstorf, DSteinemann, MGross. Implicit contact handling for deformable objects. Computer Graphics Forum, 2009, 28(2): 559–568 https://doi.org/10.1111/j.1467-8659.2009.01396.x
93	SLi, ZPan, JHuang, H Bao, XJin. Deformable objects collision handling with fast convergence. Computer Graphics Forum, 2015, 34(7): 269–278 https://doi.org/10.1111/cgf.12765
94	JBarbič, D LJames. Subspace self-collision culling. ACM Transactions on Graphics, 2010, 29(4): 81
95	S CSchvartzman, J Gascón, M AOtaduy. Bounded normal trees for reduced deformations of triangulated surfaces. In: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2009, 75–82 https://doi.org/10.1145/1599470.1599480
96	YTeng, M AOtaduy, TKim. Simulating articulated subspace selfcontact. ACM Transactions on Graphics, 2014, 33(4): 106 https://doi.org/10.1145/2601097.2601181
97	DHarmon, DZorin. Subspace integration with local deformations. ACM Transactions on Graphics, 2013, 32(4): 107 https://doi.org/10.1145/2461912.2461922
98	JBarbič, D LJames. Six-DoF haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics, 2008, 1(1): 39–52 https://doi.org/10.1109/TOH.2008.1
99	YLipeng, LShuai, HAimin, Q Hong. Realtime two-way coupling of meshless fluids and nonlinear fem. Computer Graphics Forum, 2012, 31(7): 2037–2046 https://doi.org/10.1111/j.1467-8659.2012.03196.x
100	XChen, CZheng, WXu, KZhou. An asymptotic numerical method for inverse elastic shape design. ACM Transactions on Graphics, 2014, 33(4): 95 https://doi.org/10.1145/2601097.2601189

[1]

Article highlights

Download

[1]	Yue XIE,Ye YUAN,Xiang CHEN,Changxi ZHENG,Kun ZHOU. Continuous optimization of interior carving in 3D fabrication[J]. Front. Comput. Sci., 2017, 11(2): 332-346.
[2]	Yanyan ZHANG,Jianchun ZHANG,Zhisong PAN,Daoqiang ZHANG. Multi-view dimensionality reduction via canonical random correlation analysis[J]. Front. Comput. Sci., 2016, 10(5): 856-869.
[3]	Zhaoman ZHONG,Zongtian LIU,Yun HU,Cunhua LI. Efficient multi-event monitoring using built-in search engines[J]. Front. Comput. Sci., 2016, 10(2): 281-291.
[4]	Leilei YANG,Songcan CHEN. Linear discriminant analysis with worst between-class separation and average within-class compactness[J]. Front. Comput. Sci., 2014, 8(5): 785-792.
[5]	Lishan QIAO, Limei ZHANG, Songcan CHEN. Dimensionality reduction with adaptive graph[J]. Front Comput Sci, 2013, 7(5): 745-753.
[6]	Pu HUANG, Zhenmin TANG, Caikou CHEN, Xintian CHENG. Nearest-neighbor classifier motivated marginal discriminant projections for face recognition[J]. Front Comput Sci Chin, 2011, 5(4): 419-428.
[7]	ZHANG Jian, ZHANG Wenhui, ZHAN Naijun, SHEN Yidong, CHEN Haiming, ZHANG Yunquan, WANG Yongji, WU Enhua, WANG Hongan, ZHU Xueyang. Basic research in computer science and software engineering at SKLCS[J]. Front. Comput. Sci., 2008, 2(1): 1-11.

Viewed

Full text

Abstract

Cited

Shared

Discussed