[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/1272690.1272715acmconferencesArticle/Chapter ViewAbstractPublication PagesscaConference Proceedingsconference-collections
Article

Adaptive deformations with fast tight bounds

Published: 03 August 2007 Publication History

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]
{AKS05} Aksoylu B., Khodakovsky A., Schröder P.: Multilevel solvers for unstructured surface meshes. SIAM Journal on Scientific Computing 26, 4 (2005), 1146--1165.
[2]
{BFA02} Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH (2002).
[3]
{BHM00} Briggs W. L., Henson V. E., McCormick S. F.: A Multigrid Tutorial, 2nd Edition. SIAM, 2000.
[4]
{BJ05} Barbič J., James D. L.: Real-time subspace integration for St. Venant-Kirchhoff deformable models. Proc. of ACM SIGGRAPH (2005).
[5]
{Bra77} Brandt A.: Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 138 (1977).
[6]
{BW98} Baraff D., Witkin A.: Large steps in cloth simulation. Proc. of ACM SIGGRAPH (1998).
[7]
{CGC*02} Capell S., Green S., Curless B., Duchamp T., Popovic Z.: A multiresolution framework for dynamic deformations. Proc. of ACM SIGGRAPH SCA (2002).
[8]
{CPS92} Cottle R., Pang J., Stone R.: The Linear Complementarity Problem. Academic Press, 1992.
[9]
{dB97} den Bergen G. V.: Efficient collision detection of complex deformable models using aabb trees. J. Graphics Tools 2, 4 (1997), 1--14.
[10]
{DDCB01} Debunne G., Desbrun M., Cani M. P., Barr A. H.: Dynamic real-time deformations using space and time adaptive sampling. Proc. of ACM SIGGRAPH (2001).
[11]
{GKS02} Grinspun E., Krysl P., Schröder P.: CHARMS: A simple framework for adaptive simulation. Proc. of ACM SIGGRAPH (2002).
[12]
{GLM96} Gottschalk S., Lin M., Manocha D.: OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM SIGGRAPH (1996), 171--180.
[13]
{GM97} Gibson S. F., Mirtich B. V.: A Survey of Deformable Modeling in Computer Graphics. Tech. rep., Mitsubishi Electric Research Laboratory, 1997.
[14]
{GRLM03} Govindaraju N., Redon S., Lin M., Manocha D.: CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Proc. of ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware (2003), 25--32.
[15]
{GTS02} Green S., Turkiyyah G., Storti D.: Subdivision-based multilevel methods for large scale engineering simulation of thin shells. Proc. of ACM Symposium on Solid Modeling and Applications (2002), 265--272.
[16]
{GW05} Georgii J., Westermann R.: A multigrid framework for real-time simulation of deformable volumes. Proc. of VRI-PHYS (2005).
[17]
{ITF04} Irving G., Teran J., Fedkiw R.: Invertible finite elements for robust simulation of large deformation. Proc. of ACM SIGGRAPH/Eurographics SCA (2004), 131--140.
[18]
{JP03} James D. L., Pai D. K.: Multiresolution Green's function methods for interactive simulation of large-scale elastostatic objects. ACM TOG 22, 1 (2003).
[19]
{JP04} James D. L., Pai D. K.: BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH (2004).
[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]
{MG04} Müller M., Gross M.: Interactive virtual materials. Proc. of Graphics Interface (2004).
[23]
{MHTG05} Müller M., Heidelberger B., Teschner M., Gross M.: Meshless deformations based on shape matching. Proc. of ACM SIGGRAPH (2005), 471--478.
[24]
{MT86} McCormick S. F., Thomas J.: The fast adaptive composite grid (FAC) method for elliptic equations. Mathematics of Computation 46, 174 (1986), 439--456.
[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]
{OBH02} O'Brien J. F., Bargteil A. W., Hodgins J. K.: Graphical modeling and animation of ductile fracture. Proc. of ACM SIGGRAPH (2002), 291--294.
[27]
{ODGK03} O'Sullivan C., Dingliana J., Giang T., Kaiser M. K.: Evaluating the visual fidelity of physically based animations. Proc. of ACM SIGGRAPH (2003), 527--536.
[28]
{OL03} Otaduy M. A., Lin M. C.: Sensation preserving simplification for haptic rendering. Proc. of ACM SIGGRAPH (2003).
[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]
{SGG*06} Sud A., Govindaraju N. K., Gayle R., Kabul I., Manocha D.: Fast proximity computation among multiple deformable models using discrete voronoi diagrams. Proc. of ACM SIGGRAPH (2006).
[32]
{SYBF06} Shi L., Yu Y., Bell N., Feng W.-W.: A fast multi-grid algorithm for mesh deformation. Proc. of ACM SIGGRAPH (2006).
[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]
{TOS01} Trottenberg U., Oosterlee C., Schüller A.: Multigrid. Academic Press, 2001.
[36]
{VMT94} Volino P., Magnenat-Thalmann N.: Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Eurographics (1994).
[37]
{VMT06} Volino P., Magnenat-Thalmann N.: Resolving surface collisions through intersection contour minimization. Proc. of ACM SIGGRAPH (2006).
[38]
{WT04} Wu X., Tendick F.: Multigrid integration for interactive deformable body simulation. International Symposium on Medical Simulation (2004).

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SCA '07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation
August 2007
287 pages
ISBN:9781595936240

Sponsors

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 03 August 2007

Check for updates

Qualifiers

  • Article

Conference

SCA07
Sponsor:

Acceptance Rates

SCA '07 Paper Acceptance Rate 28 of 81 submissions, 35%;
Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)1
Reflects downloads up to 01 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Affine body dynamicsACM Transactions on Graphics10.1145/3528223.353006441:4(1-14)Online publication date: 22-Jul-2022
  • (2019)Multi-Resolution Modeling of Shapes in ContactProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402532:2(1-26)Online publication date: 26-Jul-2019
  • (2017)An adaptive generalized interpolation material point method for simulating elastoplastic materialsACM Transactions on Graphics10.1145/3130800.313087936:6(1-12)Online publication date: 20-Nov-2017
  • (2017)Adaptive Physically Based Models in Computer GraphicsComputer Graphics Forum10.1111/cgf.1294136:6(312-337)Online publication date: 1-Sep-2017
  • (2015)Fast contact determination for intersecting deformable solidsProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822015(205-214)Online publication date: 16-Nov-2015
  • (2014)Signed distance fields for polygon soup meshesProceedings of Graphics Interface 201410.5555/2619648.2619655(35-41)Online publication date: 7-May-2014
  • (2013)Numerical methods for linear complementarity problems in physics-based animationACM SIGGRAPH 2013 Courses10.1145/2504435.2504443(1-42)Online publication date: 21-Jul-2013
  • (2013)Simulating liquids and solid-liquid interactions with lagrangian meshesACM Transactions on Graphics10.1145/2451236.245124332:2(1-15)Online publication date: 30-Apr-2013
  • (2011)Efficient elasticity for character skinning with contact and collisionsACM Transactions on Graphics10.1145/2010324.196493230:4(1-12)Online publication date: 25-Jul-2011
  • (2011)Efficient elasticity for character skinning with contact and collisionsACM SIGGRAPH 2011 papers10.1145/1964921.1964932(1-12)Online publication date: 7-Aug-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media