Eric G. Parker
James F. O'Brien
ABSTRACT
This paper describes a simulation system that has been developed to model the deformation and fracture of solid objects in a real-time gaming context. Based around a corotational tetrahedral finite element method, this system has been constructed from components published in the graphics and computational physics literatures. The goal of this paper is to describe how these components can be combined to produce an engine that is robust to unpredictable user interactions, fast enough to model reasonable scenarios at real-time speeds, suitable for use in the design of a game level, and with appropriate controls allowing content creators to match artistic direction. Details concerning parallel implementation, solver design, rendering method, and other aspects of the simulation are elucidated with the intent of providing a guide to others wishing to implement similar systems. Examples from in-game scenes captured on the Xbox 360, PS3, and PC platforms are included.
- {Bar89} Baraff D.: Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proceedings of ACM SIGGRAPH 1989 (1989), pp. 223--232. Google Scholar
Digital Library
- {Bar92} Baraff D.: Dynamic Simulation of Non-Penetrating Rigid Bodies. PhD thesis, Computer Science Department, Cornell University, 1992. Google ScholarDigital Library
- {Bar94} Baraff D.: Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of ACM SIGGRAPH 1994 (1994). Google ScholarDigital Library
- {BFA02} Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of ACM SIGGRAPH 2002 (2002). Google ScholarDigital Library
- {BH79} Belytschko T., Hsieh B.: Application of higher order corotational stretch theories to nonlinear finite element analysis. Computers&Structures 11 (1979), 175--182.Google ScholarCross Ref
- {BHTF07} Bao Z., Hong J.-M., Teran J., Fedkiw R.: Fracturing rigid materials. IEEE Transactions on Visualization and Computer Graphics 13, 2 (2007), 370--378. Google ScholarDigital Library
- {BW92} Baraff D., Witkin A.: Dyanmic simulation of non-penetrating flexible bodies. In Proceedings of ACM SIGGRAPH 1992 (1992), pp. 303--308. Google ScholarDigital Library
- {BW97} Baraff D., Witkin A.: Partitioned Dynamics. Tech. rep., Robotics Institute, Carnegie Mellon University, 1997. Technical Report CMU-RI-TR-97-33.Google Scholar
- {BW98} Baraff D., Witkin A.: Large steps in cloth simulation. In Proceedings of ACM SIGGRAPH 1998 (1998), pp. 43--54. Google ScholarDigital Library
- {BWHT07} Bargteil A. W., Wojtan C., Hodgins J. K., Turk G.: A finite element method for animating large viscoplastic flow. In Proceedings of ACM SIGGRAPH 2007 (Aug. 2007), pp. 291--294. Google ScholarDigital Library
- {CAR*09} Chentanez N., Alterovitz R., Ritchie D., Cho L., Hauser K. K., Goldberg K., Shewchuk J. R., O'Brien J. F.: Interactive simulation of surgical needle insertion and steering. In Proceedings of ACM SIGGRAPH 2009 (Aug. 2009). Google ScholarDigital Library
- {CLMP95} Cohen J. D., Lin M. C., Manocha D., Ponamgi M. K.: I-COLLIDE: An interactive and exact collision detection system for large scale environments. In Proceedings of the ACM Symposium on Interactive 3D Graphics (Apr. 1995), pp. 189--196. Google ScholarDigital Library
- {CMPW01} Cook R. D., Malkus D. S., Plesha M. E., Witt R. J.: Concepts and Applications of Finite Element Analysis, fourth ed. John Wiley&Sons, New York, 2001. Google ScholarDigital Library
- {Cou08} Coumans E.: Bullet physics. www.bulletphysics.com, 2008.Google Scholar
- {Ebe04} Eberly D. H.: Game Physics. Morgan Kaufmann, 2004. Google ScholarDigital Library
- {EKS03} Etzmuß O., Keckeisen M., Straßer W.: A fast finite element solution for cloth modelling. In Proceedings of the Pacific Conference on Computer Graphics and Applications (2003), p. 244. Google ScholarDigital Library
- {Erl07} Erleben K.: Velocity-based shock propagation for multibody dynamics animation. In ACM Trans. on Graphics (2007), vol. 26. Google ScholarDigital Library
- {ESHD05} Erleben K., Sporring J., Henriksen K., Dohlman H.: Physics based animation. Charles River Media, 2005. Google ScholarDigital Library
- {Fel07} Felippa C.: Introduction to finite element methods. www.colorado.edu/engineering/cas/courses.d/NFEM.d, 2007. Course notes published as webpages.Google Scholar
- {GBF03} Guendelman E., Bridson R., Fedkiw R.: Non-convex rigid bodies with stacking. In Proceedings of ACM SIGGRAPH 2003 (2003). Google ScholarDigital Library
- {GM97} Gibson S. F. F., Mirtich B.: A Survey of Deformable Modeling in Computer Graphics. Tech. rep., Mitsubishi Electric Research Laboratories, 1997.Google Scholar
- {HFS*01} Hirota G., Fisher S., State A., Lee C., Fuchs H.: An implicit finite element method for elastic solids in contact. In Proc. of Computer Animation (2001), pp. 136--146.Google ScholarCross Ref
- {HGS*07} Hughes C. J., Grzeszczuk R., Sifakis E., Kim D., Kumar S., Selle A. P., Chhugani J., Holliman M., Chen Y.-K.: Physical simulation for animation and visual effects: parallelization and characterization for chip multiprocessors. ACM SIGARCH Computer Architecture News 35, 2 (2007), 220--231. Google ScholarDigital Library
- {HSO03} Hauser K. K., Shen C., O'Brien J. F.: Interactive deformation using modal analysis with constraints. In Graphics Interface (June 2003), pp. 247--256.Google Scholar
- {HVT08} Harmon D., Vouga E., Tamstorf R.: Robust treatment of simultaneous collisions. In Proceedings of ACM SIGGRAPH 2008 (2008). Google ScholarDigital Library
- {Ing96} Ingber L.: Adaptive simulated annealing (asa): Lessons learned. Control and Cybernetics 25 (1996), 33--54.Google Scholar
- {IO06} Iben H. N., O'Brien J. F.: Generating surface crack patterns. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Sept. 2006), pp. 177--185. Google ScholarDigital Library
- {ITF04} Irving G., Teran J., Fedkiw R.: Invertible finite elements for robust simulation of large deformation. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation (July 2004), pp. 131--140. Google ScholarDigital Library
- {JP99} James D. L., Pai D. K.: Artdefo: accurate real time deformable objects. In Proceedings of ACM SIGGRAPH 1999 (1999), pp. 65--72. Google ScholarDigital Library
- {KEP05} Kaufman D. M., Edmunds T., Pai D. K.: Fast frictional dynamics for rigid bodies. In Proceedings of ACM SIGGRAPH 2005 (2005). Google ScholarDigital Library
- {KK99} Karypis G., Kumar V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIA J. Sci. Comput. (1999), 359--392. Google ScholarDigital Library
- {MBF04} Molino N., Bao Z., Fedkiw R.: A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. 23, 3 (2004), 385--392. Google ScholarDigital Library
- {MDM*02} Müller M., Dorsey J., McMillan L., Jagnow R., Cutler B.: Stable real-time deformations. In ACM SIGGRAPH Symposium on Computer Animation (July 2002), pp. 49--54. Google ScholarDigital Library
- {MG04} Müller M., Gross M.: Interactive virtual materials. In Proceedings of Graphics Interface 2004 (2004), pp. 239--246. Google ScholarDigital Library
- {Mic05} Microsoft: Direct x 10 developer documentation/texture skinning. msdn.microsoft.com/en-us/library, 2005.Google Scholar
- {MMDJ01} Müller M., McMillan L., Dorsey J., Jagnow R.: Real-time simulation of deformation and fracture of stiff materials. In Proceedings of the Eurographic workshop on Computer animation and simulation (2001), pp. 113--124. Google ScholarDigital Library
- {MSJT08} Müller M., Stam J., James D., Thürey N.: Real time physics: class notes. In SIGGRAPH '08: ACM SIGGRAPH 2008 classes (2008), pp. 1--90. Google ScholarDigital Library
- {MW88} Moore M., Wilhelms J.: Collision detection and response for computer animationr3. In Proceedings of SIGGRAPH 1988 (1988), pp. 289--298. Google ScholarDigital Library
- {NMK*05} Nealen A., Müller M., Keiser R., Boxerman E., Carlson M.: Physically based deformable models in computer graphics. Tech. rep., Eurogrphics 2005 state of the art report, 2005.Google Scholar
- {NOR91} Nour-Omid B., Rankin C. C.: Finite rotation analysis and consistent linearization using projectors. Comp. Methds. Appl. Mech. Engrg. 93 (1991), 353--384.Google ScholarCross Ref
- {NPF05} Nesme M., Payan Y., Faure F.: Efficient, physically plausible finite elements. In Eurographics 2005, short papers (Trinity College, Dublin, Irlande, Aug. 2005), Dingliana J., Ganovelli F., (Eds.).Google Scholar
- {O'B00} O'Brien J. F.: Graphical Modeling and Animation of Fracture. PhD thesis, College of Computing, Georgia Institute of Technology, 2000. Google ScholarDigital Library
- {OBH02} O'Brien J. F., Bargteil A. W., Hodgins J. K.: Graphical modeling and animation of ductile fracture. In Proceedings of ACM SIGGRAPH 2002 (Aug. 2002), pp. 291--294. Google ScholarDigital Library
- {OH99} O'Brien J. F., Hodgins J. K.: Graphical modeling and animation of brittle fracture. In Proceedings of ACM SIGGRAPH 1999 (Aug. 1999), pp. 137--146. Google ScholarDigital Library
- {OTSG09} Otaduy M. A., Tamstorf R., Steinemann D., Gross M.: Implicit contact handling for deformable objects. Computer Graphics Forum (Proc. of Eurographics) 28, 2 (apr 2009).Google Scholar
- {Pis84} Pissanetzky S.: Sparse Matrix Technology. Academic Press, London, 1984.Google Scholar
- {SBT07} Spillmann J., Becker M., Teschner M.: Non-iterative computatino of contact forces for deformable objects. Journal of WSCG 15, 1--3 (2007), 33--40.Google Scholar
- {Sel01} Sellers D.: An overview of proportional plus integral plus derivative control and suggestions for its successful application and implementation. In Proceedings for the 2001 International Conference on Enhanced Building Operations (2001).Google Scholar
- {She94} Shewchuk J. R.: An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Tech. Rep. CMU-CS-94-125, School of Computer Science, Carnegie Mellon University, Mar. 1994.Google ScholarDigital Library
- {SWB00} Smith J., Witkin A., Baraff D.: Fast and control-lable simulation of the shattering of brittle objects. Computer Graphics Interface (may 2000), 27--34.Google Scholar
- {Ter01} Terdiman P.: Memory-optimized bounding-volume hierarchies. www.codercorner.com/Opcode.pdf, 2001.Google Scholar
- {TKZ*04} Teschner M., Kimmerle S., Zachmann G., Heidelberger B., Raghupathi L., Fuhrmann A., Cani M.-P., Faure F., Magnetat-Thalmann N., Strasser W.: Collision detection for deformable objects. Tech. rep., Eurographics Association, 2004.Google Scholar
- {TPBF87} Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models. In Proceedings of ACM SIGGRAPH 1987 (jul 1987), vol. 21, pp. 205--214. Google ScholarDigital Library
Index Terms
- Real-time deformation and fracture in a game environment
Recommendations
Graphical modeling and animation of ductile fracture
SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniquesIn this paper, we describe a method for realistically animating ductile fracture in common solid materials such as plastics and metals. The effects that characterize ductile fracture occur due to interaction between plastic yielding and the fracture ...
Graphical modeling and animation of ductile fracture
In this paper, we describe a method for realistically animating ductile fracture in common solid materials such as plastics and metals. The effects that characterize ductile fracture occur due to interaction between plastic yielding and the fracture ...
Phase-field modelling and analysis of rate-dependent fracture phenomena at finite deformation
AbstractFracture of materials with rate-dependent mechanical behaviour, e.g. polymers, is a highly complex process. For an adequate modelling, the coupling between rate-dependent stiffness, dissipative mechanisms present in the bulk material and crack ...
Comments