More Web Proxy on the site http://driver.im/

Article

Nonconvex rigid bodies with stacking

Authors:

Eran Guendelman,

Robert Bridson,

Ronald FedkiwAuthors Info & Claims

SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

Pages 871 - 878

https://doi.org/10.1145/1201775.882358

Published: 01 July 2003 Publication History

Abstract

We consider the simulation of nonconvex rigid bodies focusing on interactions such as collision, contact, friction (kinetic, static, rolling and spinning) and stacking. We advocate representing the geometry with both a triangulated surface and a signed distance function defined on a grid, and this dual representation is shown to have many advantages. We propose a novel approach to time integration merging it with the collision and contact processing algorithms in a fashion that obviates the need for ad hoc threshold velocities. We show that this approach matches the theoretical solution for blocks sliding and stopping on inclined planes with friction. We also present a new shock propagation algorithm that allows for efficient use of the propagation (as opposed to the simultaneous) method for treating contact. These new techniques are demonstrated on a variety of problems ranging from simple test cases to stacking problems with as many as 1000 nonconvex rigid bodies with friction as shown in Figure 1.

Supplementary Material

MP4 File (guendelman_nonconvex.mp4)

Download
37.49 MB

References

[1]

BACIU, G., AND WONG, S. K. 2000. The impulse graph: a new dynamic structure for global collisions. CGForum 19, 3, 229--238.

[2]

BARAFF, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. Comput. Graph. (Proc. SIGGRAPH 89) 23, 3, 223--232.

Digital Library

[3]

BARAFF, D. 1990. Curved surfaces and coherence for non-penetrating rigid body simulation. Comput. Graph. (Proc. SIGGRAPH 90) 24, 4, 19--28.

Digital Library

[4]

BARAFF, D. 1991. Coping with friction for non-penetrating rigid body simulation. Comput. Graph. (Proc. SIGGRAPH 91) 25, 4, 31--40.

Digital Library

[5]

BARAFF, D. 1993. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica, 10, 292--352.

Digital Library

[6]

BARAFF, D. 1994. Fast contact force computation for non-penetrating rigid bodies. In Proc. SIGGRAPH 94, 23--34.

Digital Library

[7]

BARAFF, D. 1995. Interactive simulation of solid rigid bodies. IEEE Comput. Graph. and Appl. 15, 3, 63--75.

Digital Library

[8]

BARZEL, R., HUGHES, J. F., AND WOOD, D. N. 1996. Plausible motion simulation for computer graphics. In Comput. Anim. and Sim. '96, Proc. Eurographics Workshop, 183--197.

Digital Library

[9]

BHATT, V., AND KOECHLING, J. 1995. Three-dimensional frictional rigidbody impact. ASME J. Appl. Mech. 62, 893--898.

[10]

BUSS, S. R. 2000. Accurate and efficient simulation of rigid-body rotations. J. Comput. Phys. 164, 2.

Digital Library

[11]

CHATTERJEE, A., AND RUINA, A. 1998. A new algebraic rigid body collision law based on impulse space considerations. ASME J. Appl. Mech. 65, 4, 939--951.

[12]

CHENNEY, S., AND FORSYTH, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proc. SIGGRAPH 2000, 219--228.

Digital Library

[13]

CUTLER, B., DORSEY, J., MC MILLAN, L., MÜLLER, M., AND JAGNOW, R. 2002. A procedural approach to authoring solid models. ACM Trans. Graph. 21, 3, 302--311.

Digital Library

[14]

DESBRUN, M., AND GASCUEL, M.-P. 1995. Animating soft substances with implicit surfaces. In Proc. SIGGRAPH 95, 287--290.

Digital Library

[15]

FISHER, S., AND LIN, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Comput. Anim. and Sim. '01, Proc. Eurographics Workshop, 99--111.

Digital Library

[16]

FRISKEN, S. F., PERRY, R. N., ROCKWOOD, A. P., AND JONES, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proc. SIGGRAPH 2000, 249--254.

Digital Library

[17]

GASCUEL, M.-P. 1993. An implicit formulation for precise contact modeling between flexible solids. In Proc. SIGGRAPH 93, 313--320.

Digital Library

[18]

GIBSON, S. F. F. 1998. Using distance maps for accurate surface representation in sampled volumes. In Proc. of IEEE Symp. on Vol. Vis., 23--30.

Digital Library

[19]

HAHN, J. K. 1988. Realistic animation of rigid bodies. Comput. Graph. (Proc. SIGGRAPH 88) 22, 4, 299--308.

Digital Library

[20]

HIROTA, G., FISHER, S., STATE, A., LEE, C., AND FUCHS, H. 2001. An implicit finite element method for elastic solids in contact. In Comput. Anim.

[21]

KIM, T.-Y., AND NEUMANN, U. 2002. Interactive multiresolution hair modeling and editing. ACM Trans. Graph. 21, 3, 620--629.

Digital Library

[22]

KIM, Y. J., OTADUY, M. A., LIN, M. C., AND MANOCHA, D. 2002. Fast penetration depth computation for physically-based animation. In ACM Symp. Comp. Anim.

Digital Library

[23]

KOKKEVIS, E., METAXAS, D., AND BADLER, N. 1996. User-controlled physics-based animation for articulated figures. In Proc. Comput. Anim. '96.

Digital Library

[24]

LEWIS, A. D., AND MURRAY, R. M. 1995. Variational principles in constrained systems: theory and experiments. Int. J. Nonlinear Mech. 30, 6, 793--815.

[25]

LIN, M., AND GOTTSCHALK, S. 1998. Collision detection between geometric models: A survey. In Proc. of IMA Conf. on Math. of Surfaces, 37--56.

[26]

MILENKOVIC, V. J., AND SCHMIDL, H. 2001. Optimization-based animation. In Proc. SIGGRAPH 2001, 37--46.

Digital Library

[27]

MILENKOVIC, V. J. 1996. Position-based physics: simulation the motion of many highly interacting spheres and polyhedra. In Proc. SIGGRAPH 96, 129--136.

Digital Library

[28]

MIRTICH, B., AND CANNY, J. 1995. Impulse-based dynamic simulation. In Alg. Found. of Robotics, A. K. Peters, Boston, MA, K. Goldberg, D. Halperin, J.-C. Latombe, and R. Wilson, Eds., 407--418.

Digital Library

[29]

MIRTICH, B., AND CANNY, J. 1995. Impulse-based simulation of rigid bodies. In Proc. of 1995 Symp. on Int. 3D Graph., 181--188, 217.

Digital Library

[30]

MIRTICH, B. 1996. Fast and accurate computation of polyhedral mass properties. J. Graph. Tools 1, 2, 31--50.

Digital Library

[31]

MIRTICH, B. 2000. Timewarp rigid body simulation. In Proc. SIGGRAPH 2000, 193--200.

Digital Library

[32]

MOORE, M., AND WILHELMS, J. 1988. Collision detection and response for computer animation. Comput. Graph. (Proc. SIGGRAPH 88) 22, 4, 289--298.

Digital Library

[33]

MUSETH, K., BREEN, D., WHITAKER, R., AND BARR, A. 2002. Level set surface editing operators. ACM Trans. Graph. 21, 3, 330--338.

Digital Library

[34]

OSHER, S., AND FEDKIW, R. 2002. Level set methods and dynamic implicit surfaces. Springer-Verlag. New York, NY.

[35]

PANDOLFI, A., KANE, C., MARSDEN, J., AND ORTIZ, M. 2002. Time discretized variational formulation of non-smooth frictional contact. Int. J. Num. Meth. in Eng. 53, 1801--1829.

[36]

PENTLAND, A., AND WILLIAMS, J. 1989. Good vibrations: modal dynamics for graphics and animation. Comput. Graph. (Proc. SIGGRAPH 89) 23, 3, 215--222.

Digital Library

[37]

PONAMGI, M. K., MANOCHA, D., AND LIN, M. C. 1995. Incremental algorithms for collision detection between solid models. In Proc. ACM Symp. Solid Model. and Appl., 293--304.

Digital Library

[38]

POPOVIĆ, J., SEITZ, S. M., ERDMANN, M., POPOVIĆ, Z., AND WITKIN, A. 2000. Interactive manipulation of rigid body simulations. In Proc. SIGGRAPH 2000, 209--217.

Digital Library

[39]

REDON, S., KHEDDAR, A., AND COQUILLART, S. 2002. Fast continuous collision detection between rigid bodies. CGForum 21, 3, 279--288.

[40]

SAUER, J., AND SCHÖMER, E. 1998. A constraint-based approach to rigid body dynamics for virtual reality applications. In Proc. ACM Symp. on Virt. Reality Soft. and Tech., 153--162.

Digital Library

[41]

SCHMIDL, H. 2002. Optimization-based animation. PhD thesis, University of Miami.

Digital Library

[42]

SCHROEDER, W. J., LORENSEN, W. E., AND LINTHICUM, S. 1994. Implicit modeling of swept surfaces and volumes. In Proc. of Vis., IEEE Computer Society Press, 40--55.

Digital Library

[43]

SCLAROFF, S., AND PENTLAND, A. 1991. Generalized implicit functions for computer graphics. Comput. Graph. (Proc. SIGGRAPH 91) 25, 4, 247--250.

Digital Library

[44]

SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591--1595.

[45]

SIMS, K. 1994. Evolving virtual creatures. In Proc. SIGGRAPH 94, 15--22.

Digital Library

[46]

STEWART, D. E., AND TRINKLE, J. C. 2000. An implicit time-stepping scheme for rigid body dynamics with coulomb friction. In IEEE Int. Conf. on Robotics and Automation, 162--169.

[47]

STEWART, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Review 42, 1, 3--39.

Digital Library

[48]

TERZOPOULOS, D., PLATT, J., BARR, A., AND FLEISCHER, K. 1987. Elastically deformable models. Comput. Graph. (Proc. SIGGRAPH 87) 21, 4, 205--214.

Digital Library

[49]

TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 1528--1538.

[50]

WEBB, R., AND GIGANTE, M. 1992. Using dynamic bounding volume hierarchies to improve efficiency of rigid body simulations. In Comm. with Virt. Worlds, CGI Proc. 1992, 825--841.

Digital Library

[51]

WESTERMANN, R., KOBBELT, L., AND ERTL, T. 1999. Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Vis. Comput. 15, 2, 100--111.

Cited By

Bosch M(2020)N-dimensional rigid body dynamicsACM Transactions on Graphics10.1145/3386569.339248339:4(55:1-55:6)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392483
Wachs A(2019)Particle-scale computational approaches to model dry and saturated granular flows of non-Brownian, non-cohesive, and non-spherical rigid bodiesActa Mechanica10.1007/s00707-019-02389-9230:6(1919-1980)Online publication date: 22-Mar-2019
https://doi.org/10.1007/s00707-019-02389-9
Li SZhang TWang GSun HManocha D(2017)Multi-contact frictional rigid dynamics using impulse decomposition2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2017.8206547(6420-6427)Online publication date: 24-Sep-2017
https://dl.acm.org/doi/10.1109/IROS.2017.8206547
Show More Cited By

Index Terms

Nonconvex rigid bodies with stacking
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

Recommendations

Nonconvex rigid bodies with stacking

We consider the simulation of nonconvex rigid bodies focusing on interactions such as collision, contact, friction (kinetic, static, rolling and spinning) and stacking. We advocate representing the geometry with both a triangulated surface and a signed ...
Mass splitting for jitter-free parallel rigid body simulation

We present a parallel iterative rigid body solver that avoids common artifacts at low iteration counts. In large or real-time simulations, iteration is often terminated before convergence to maximize scene size. If the distribution of the resulting ...
Fast frictional dynamics for rigid bodies
SIGGRAPH '05: ACM SIGGRAPH 2005 Papers

We describe an efficient algorithm for the simulation of large sets of non-convex rigid bodies. The algorithm finds a simultaneous solution for a multi-body system that is linear in the total number of contacts detected in each iteration. We employ a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

July 2003

683 pages

ISBN:1581137095

DOI:10.1145/1201775

Conference Chair:
Alyn P. Rockwood
Colorado School of Mines

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH03

Sponsor:

SIGGRAPH

SIGGRAPH03: Special Interest Group on Computer Graphics and Interactive Techniques

July 27 - 31, 2003

California, San Diego

Acceptance Rates

SIGGRAPH '03 Paper Acceptance Rate 81 of 424 submissions, 19%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
2,514
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bosch M(2020)N-dimensional rigid body dynamicsACM Transactions on Graphics10.1145/3386569.339248339:4(55:1-55:6)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392483
Wachs A(2019)Particle-scale computational approaches to model dry and saturated granular flows of non-Brownian, non-cohesive, and non-spherical rigid bodiesActa Mechanica10.1007/s00707-019-02389-9230:6(1919-1980)Online publication date: 22-Mar-2019
https://doi.org/10.1007/s00707-019-02389-9
Li SZhang TWang GSun HManocha D(2017)Multi-contact frictional rigid dynamics using impulse decomposition2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2017.8206547(6420-6427)Online publication date: 24-Sep-2017
https://dl.acm.org/doi/10.1109/IROS.2017.8206547
Kim JIm JKim CLee J(2016)Subtle features of ice with cloudy effects and scratches from collision damageComputer Animation and Virtual Worlds10.1002/cav.169927:3-4(271-279)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1002/cav.1699
Marvel JBostelman R(2014)A Cross-Domain Survey of Metrics for Modelling and Evaluating CollisionsInternational Journal of Advanced Robotic Systems10.5772/5884611:9Online publication date: 1-Jan-2014
https://doi.org/10.5772/58846
Pirk SNiese THädrich TBenes BDeussen O(2014)Windy treesACM Transactions on Graphics10.1145/2661229.266125233:6(1-11)Online publication date: 19-Nov-2014
https://dl.acm.org/doi/10.1145/2661229.2661252
Tomcin RSibbing DKobbelt L(2014)Efficient enforcement of hard articulation constraints in the presence of closed loops and contactsComputer Graphics Forum10.1111/cgf.1232233:2(235-244)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1111/cgf.12322
Glondu LSchvartzman SMarchal MDumont GOtaduy M(2014)Fast Collision Detection for Fracturing Rigid BodiesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.9820:1(30-41)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1109/TVCG.2013.98
Han DHsu SMcNamara AKeyser JHoyet LSanders BGeigel JStefanucci J(2013)Believability in simplifications of large scale physically based simulationProceedings of the ACM Symposium on Applied Perception10.1145/2492494.2492504(99-106)Online publication date: 22-Aug-2013
https://dl.acm.org/doi/10.1145/2492494.2492504
Glondu LSchvartzman SMarchal MDumont GOtaduy MBoulic RKomura T(2012)Efficient collision detection for brittle fractureProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2422356.2422397(285-294)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2422356.2422397
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents