“Real time dynamic fracture with volumetric approximate convex decompositions” by Müller-Fischer, Chentanez and Kim

  • ©Matthias Müller-Fischer, Nuttapong Chentanez, and Tae-Yong Kim

Conference:


Type:


Title:

    Real time dynamic fracture with volumetric approximate convex decompositions

Session/Category Title: Sounds & Solids


Presenter(s)/Author(s):


Moderator(s):



Abstract:


    We propose a new fast, robust and controllable method to simulate the dynamic destruction of large and complex objects in real time. The common method for fracture simulation in computer games is to pre-fracture models and replace objects by their pre-computed parts at run-time. This popular method is computationally cheap but has the disadvantages that the fracture pattern does not align with the impact location and that the number of hierarchical fracture levels is fixed. Our method allows dynamic fracturing of large objects into an unlimited number of pieces fast enough to be used in computer games. We represent visual meshes by volumetric approximate convex decompositions (VACD) and apply user-defined fracture patterns dependent on the impact location. The method supports partial fracturing meaning that fracture patterns can be applied locally at multiple locations of an object. We propose new methods for computing a VACD, for approximate convex hull construction and for detecting islands in the convex decomposition after partial destruction in order to determine support structures.

References:


    1. Baker, M., Carlson, M., Coumans, E., Criswell, B., Harada, T., Knight, P., and Zafar, N. B. 2011. Destruction and dynamic artist tools for film and game production. In ACM SIGGRAPH 2011 course notes.Google Scholar
    2. Bao, Z., Hong, J.-M., Teran, J., and Fedkiw, R. 2007. Fracturing rigid materials. IEEE Transactions on Visualization and Computer Graphics 13, 2 (Mar.), 370–378. Google ScholarDigital Library
    3. Glondu, L., Marchal, M., and Dumont, G. 2012. Real-time simulation of brittle fracture using modal analysis. IEEE Trans. on Visualization and Computer Graphics. Google ScholarDigital Library
    4. Iben, H. N., and O’Brien, J. F. 2006. Generating surface crack patterns. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’06, 177–185. Google ScholarDigital Library
    5. Kallay, M. 1984. The complexity of incremental convex hull algorithms in rd. Information Processing Letters 19, 4, 197–.Google ScholarCross Ref
    6. Kaufmann, P., Martin, S., Botsch, M., Grinspun, E., and Gross, M. 2009. Enrichment textures for detailed cutting of shells. In ACM SIGGRAPH 2009 papers, ACM, New York, NY, USA, SIGGRAPH ’09, 50:1–50:10. Google ScholarDigital Library
    7. Kavan, L., Kolingerova, I., and Zara, J. 2006. Fast approximation of convex hull. In Proceedings of the 2nd IASTED international conference on Advances in computer science and technology, ACTA Press, Anaheim, CA, USA, ACST’06, 101–104. Google ScholarDigital Library
    8. Lien, J.-M., and Amato, N. M. 2006. Approximate convex decomposition of polygons. Comput. Geom. Theory Appl. 35, 1 (Aug.), 100–123. Google ScholarDigital Library
    9. Lien, J.-M., and Amato, N. M. 2007. Approximate convex decomposition of polyhedra. In Proceedings of the 2007 ACM symposium on Solid and physical modeling, ACM, New York, NY, USA, SPM ’07, 121–131. Google ScholarDigital Library
    10. Liu, R., Zhang, H., and Busby, J. 2008. Convex hull covering of polygonal scenes for accurate collision detection in games. In Proceedings of graphics interface 2008, Canadian Information Processing Society, Toronto, Ont., Canada, Canada, GI ’08, 203–210. Google ScholarDigital Library
    11. Mamou, K., and Ghorbel, F. 2009. A simple and efficient approach for 3d mesh approximate convex decomposition. In Image Processing (ICIP), 2009 16th IEEE International Conference on, 3501–3504. Google ScholarDigital Library
    12. Molino, N., Bao, Z., and Fedkiw, R. 2005. A virtual node algorithm for changing mesh topology during simulation. In ACM SIGGRAPH 2005 Courses, ACM, New York, NY, USA, SIGGRAPH ’05. Google ScholarDigital Library
    13. Mould, D. 2005. Image-guided fracture. In Proceedings of Graphics Interface 2005, Canadian Human-Computer Communications Society, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, GI ’05, 219–226. Google ScholarDigital Library
    14. Müller, M., Dorsey, J., and McMillan, L. 2001. Real-time simulation of deformation and fracture of stiff materials. In Proceedings of (Eurographics CAS), Computer Animation and Simulation 2001, Springer-Verlag Wien, 113–124. Google ScholarDigital Library
    15. Naylor, B., Amanatides, J., and Thibault, W. 1990. Merging bsp trees yields polyhedral set operations. In Proceedings of the 17th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’90, 115–124. Google ScholarDigital Library
    16. Norton, A., Turk, G., Bacon, B., Gerth, J., and Sweeney, P. 1991. Animation of fracture by physical modeling. Vis. Comput. 7, 4 (July), 210–219. Google ScholarDigital Library
    17. O’Brien, J. F., and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, SIGGRAPH ’99, 137–146. Google ScholarDigital Library
    18. O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002. Graphical modeling and animation of ductile fracture. ACM Trans. Graph. 21, 3 (July), 291–294. Google ScholarDigital Library
    19. Parker, E. G., and O’Brien, J. F. 2009. Real-time deformation and fracture in a game environment. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’09, 165–175. Google ScholarDigital Library
    20. Pauly, M., Keiser, R., Adams, B., Dutré, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. In ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, SIGGRAPH ’05, 957–964. Google ScholarDigital Library
    21. Pfaff, T., Thuerey, N., Cohen, J., Tariq, S., and Gross, M. 2010. Scalable fluid simulation using anisotropic turbulence particles. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, SIGGRAPH ASIA ’10, 174:1–174:8. Google ScholarDigital Library
    22. Raghavachary, S. 2002. Fracture generation on polygonal meshes using voronoi polygons. In ACM SIGGRAPH 2002 conference abstracts and applications, ACM, New York, NY, USA, SIGGRAPH ’02, 187–187. Google ScholarDigital Library
    23. Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’07, 73–80. Google ScholarDigital Library
    24. Smith, J., Witkin, A., and Baraff, D. 2001. Fast and controllable simulation of the shattering of brittle objects. Computer Graphics Forum 20, 2, 81–91.Google ScholarCross Ref
    25. Steinemann, D., Otaduy, M. A., and Gross, M. 2006. Fast arbitrary splitting of deforming objects. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’06, 63–72. Google ScholarDigital Library
    26. Su, J., Schroeder, C., and Fedkiw, R. 2009. Energy stability and fracture for frame rate rigid body simulations. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’09, 155–164. Google ScholarDigital Library
    27. Terzopoulos, D., and Fleischer, K. 1988. Modeling inelastic deformation: viscolelasticity, plasticity, fracture. SIGGRAPH Comput. Graph. 22, 4 (June), 269–278. Google ScholarDigital Library
    28. Tharp, A., Ghosh, M., and Amato, N. M. 2012. Taming large 3d models: Approximate convex decomposition. In Proceedings of summer undergraduate research 2012, Texas University.Google Scholar
    29. Tonge, R., Benevolenski, F., and Voroshilov, A. 2012. Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graph. 31, 4 (July), 105:1–105:8. Google ScholarDigital Library
    30. Turkiyyah, G., Karam, W. B., Ajami, Z., and Nasri, A. 2009. Mesh cutting during real-time physical simulation. In 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, ACM, New York, NY, USA, SPM ’09, 159–168. Google ScholarDigital Library
    31. Zheng, C., and James, D. L. 2010. Rigid-body fracture sound with precomputed soundbanks. In ACM SIGGRAPH 2010 papers, ACM, New York, NY, USA, SIGGRAPH ’10, 69:1–69:13. Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: