Adaptive deformations with fast tight bounds

ABSTRACT

Simulation of deformations and collision detection are two highly intertwined problems that are often treated separately. This is especially true in existing elegant adaptive simulation techniques, where standard collision detection algorithms cannot leverage the adaptively selected degrees of freedom. We propose a seamless integration of multigrid algorithms and collision detection that identifies boundary conditions while inherently exploiting adaptivity. We realize this integration through multiscale bounding hierarchies, a novel unified hierarchical representation, together with an adaptive multigrid algorithm for irregular meshes and an adaptivity-aware hierarchical collision detection algorithm. Our solution produces detailed deformations with adapted computational cost, but it also enables robust interactive simulation of self-colliding deformable objects with high-resolution surfaces.

REFERENCES

• 1: Burak Aksoylu , Andrei Khodakovsky , Peter Schröder, Multilevel Solvers for Unstructured Surface Meshes, SIAM Journal on Scientific Computing, v.26 n.4, p.1146-1165, 2005 [doi>10.1137/S1064827503430138]
• 2: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 3: William L. Briggs , Van Emden Henson , Steve F. McCormick, A multigrid tutorial: second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 4: Jernej Barbič , Doug L. James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 5: {Bra77} Brandt A.: Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 138 (1977).
• 6: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 7: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, A multiresolution framework for dynamic deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545268]
• 8: {CPS92} Cottle R., Pang J., Stone R.: The Linear Complementarity Problem. Academic Press, 1992.
• 9: Gino van den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, v.2 n.4, p.1-13, April 1997
• 10: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 11: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 12: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 13: {GM97} Gibson S. F., Mirtich B. V.: A Survey of Deformable Modeling in Computer Graphics. Tech. rep., Mitsubishi Electric Research Laboratory, 1997.
• 14: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 15: Seth Green , George Turkiyyah , Duane Storti, Subdivision-based multilevel methods for large scale engineering simulation of thin shells, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566321]
• 16: {GW05} Georgii J., Westermann R.: A multigrid framework for real-time simulation of deformable volumes. Proc. of VRI-PHYS (2005).
• 17: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 18: Doug L. James , Dinesh K. Pai, Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects, ACM Transactions on Graphics (TOG), v.22 n.1, p.47-82, January 2003 [doi>10.1145/588272.588278]
• 19: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 20: {KZ05} Kavan L., Zara J.: Fast collision detection for skeletally deformable models. Proc. of Eurographics (2005).
• 21: {LAM01} Larsson T., Akenine-Möller T.: Collision detection for continuously deforming bodies. Eurographics (2001).
• 22: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of Graphics Interface 2004, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 23: Matthias Müller , Bruno Heidelberger , Matthias Teschner , Markus Gross, Meshless deformations based on shape matching, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 24: S McCormick , J Thomas, The fast adaptive composite grid (FAC) method for elliptic equation, Mathematics of Computation, v.46 n.174, p.439-456, April 1986 [doi>10.2307/2007986]
• 25: {NMK*05} Nealen A., Müller M., Keiser R., Boxermann E., Carlson M.: Physically based deformable models in computer graphics. Eurographics STAR (2005).
• 26: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 27: Carol O'Sullivan , John Dingliana , Thanh Giang , Mary K. Kaiser, Evaluating the visual fidelity of physically based animations, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 28: Miguel A. Otaduy , Ming C. Lin, Sensation preserving simplification for haptic rendering, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 29: {Ran99} Rannacher R.: Error control in finite element computations. NATO Science Series, Series C: Mathematics and Physical Sciences 536 (1999), 247--278.
• 30: {RKC02} Redon S., Kheddar A., Coquillart S.: Fast continuous collision detection between rigid bodies. Proc. of Eurographics (2002).
• 31: Avneesh Sud , Naga Govindaraju , Russell Gayle , Ilknur Kabul , Dinesh Manocha, Fast proximity computation among deformable models using discrete Voronoi diagrams, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 32: Lin Shi , Yizhou Yu , Nathan Bell , Wei-Wen Feng, A fast multigrid algorithm for mesh deformation, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 33: {THM*03} Teschner M., Heidelberger B., Müeller M., Pomeranets D., Gross M.: Optimized spatial hashing for collision detection of deformable objects. Proc. of Vision, Modeling and Visualization (2003).
• 34: {TKH*05} Teschner M., Kimmerle S., Heidelberger B., Zachmann G., Raghupathi L., Furhmann A., Cani M.-P., Faure F., Magnenat-Thalmann N., Strasser W., Volino P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1 (2005).
• 35: Ulrich Trottenberg , Anton Schuller, Multigrid, Academic Press, Inc., Orlando, FL, 2000
• 36: {VMT94} Volino P., Magnenat-Thalmann N.: Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Eurographics (1994).
• 37: Pascal Volino , Nadia Magnenat-Thalmann, Resolving surface collisions through intersection contour minimization, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 38: {WT04} Wu X., Tendick F.: Multigrid integration for interactive deformable body simulation. International Symposium on Medical Simulation (2004).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling