“Nonconvex rigid bodies with stacking” by Guendelman, Bridson and Fedkiw

  • ©Eran Guendelman, Robert Bridson, and Ronald Fedkiw




    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 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.


    1. BACIU, G., AND WONG, S. K. 2000. The impulse graph: a new dynamic structure for global collisions. CGForum 19, 3, 229–238.Google Scholar
    2. BARAFF, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. Comput. Graph. (Proc. SIGGRAPH 89) 23, 3, 223–232. Google ScholarDigital Library
    3. BARAFF, D. 1990. Curved surfaces and coherence for non-penetrating rigid body simulation. Comput. Graph. (Proc. SIGGRAPH 90) 24, 4, 19–28. Google ScholarCross Ref
    4. BARAFF, D. 1991. Coping with friction for non-penetrating rigid body simulation. Comput. Graph. (Proc. SIGGRAPH 91) 25, 4, 31–40. Google ScholarDigital Library
    5. BARAFF, D. 1993. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica, 10, 292–352.Google ScholarDigital Library
    6. BARAFF, D. 1994. Fast contact force computation for non-penetrating rigid bodies. In Proc. SIGGRAPH 94, 23–34. Google Scholar
    7. BARAFF, D. 1995. Interactive simulation of solid rigid bodies. IEEE Comput. Graph. and Appl. 15, 3, 63–75. Google ScholarDigital 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. Google Scholar
    9. BHATT, V., AND KOECHLING, J. 1995. Three-dimensional frictional rigidbody impact. ASME J. Appl. Mech. 62, 893–898.Google ScholarCross Ref
    10. BUSS, S. R. 2000. Accurate and efficient simulation of rigid-body rotations. J. Comput. Phys. 164, 2. Google ScholarDigital 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.Google ScholarCross Ref
    12. CHENNEY, S., AND FORSYTH, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proc. SIGGRAPH 2000, 219–228. Google ScholarDigital 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. Google ScholarDigital Library
    14. DESBRUN, M., AND GASCUEL, M.-P. 1995. Animating soft substances with implicit surfaces. In Proc. SIGGRAPH 95, 287–290. Google Scholar
    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. Google Scholar
    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. Google ScholarDigital Library
    17. GASCUEL, M.-P. 1993. An implicit formulation for precise contact modeling between flexible solids. In Proc. SIGGRAPH 93, 313–320. Google Scholar
    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. Google Scholar
    19. HAHN, J. K. 1988. Realistic animation of rigid bodies. Comput. Graph. (Proc. SIGGRAPH 88) 22, 4, 299–308. Google ScholarDigital 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.Google Scholar
    21. KIM, T.-Y., AND NEUMANN, U. 2002. Interactive multiresolution hair modeling and editing. ACM Trans. Graph. 21, 3, 620–629. Google ScholarDigital 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. Google Scholar
    23. KOKKEVIS, E., METAXAS, D., AND BADLER, N. 1996. User-controlled physics-based animation for articulated figures. In Proc. Comput. Anim. ’96. Google Scholar
    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.Google ScholarCross Ref
    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.Google Scholar
    26. MILENKOVIC, V. J., AND SCHMIDL, H. 2001. Optimization-based animation. In Proc. SIGGRAPH 2001, 37–46. Google ScholarDigital 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. Google Scholar
    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. Google ScholarDigital 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. Google Scholar
    30. MIRTICH, B. 1996. Fast and accurate computation of polyhedral mass properties. J. Graph. Tools 1, 2, 31–50. Google ScholarDigital Library
    31. MIRTICH, B. 2000. Timewarp rigid body simulation. In Proc. SIGGRAPH 2000, 193–200. Google ScholarDigital Library
    32. MOORE, M., AND WILHELMS, J. 1988. Collision detection and response for computer animation. Comput. Graph. (Proc. SIGGRAPH 88) 22, 4, 289–298. Google ScholarDigital Library
    33. MUSETH, K., BREEN, D., WHITAKER, R., AND BARR, A. 2002. Level set surface editing operators. ACM Trans. Graph. 21, 3, 330–338. Google ScholarDigital Library
    34. OSHER, S., AND FEDKIW, R. 2002. Level set methods and dynamic implicit surfaces. Springer-Verlag. New York, NY.Google Scholar
    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.Google ScholarCross Ref
    36. PENTLAND, A., AND WILLIAMS, J. 1989. Good vibrations: modal dynamics for graphics and animation. Comput. Graph. (Proc. SIGGRAPH 89) 23, 3, 215–222. Google ScholarDigital 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. Google Scholar
    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. Google ScholarDigital Library
    39. REDON, S., KHEDDAR, A., AND COQUILLART, S. 2002. Fast continuous collision detection between rigid bodies. CGForum 21, 3, 279–288.Google Scholar
    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. Google Scholar
    41. SCHMIDL, H. 2002. Optimization-based animation. PhD thesis, University of Miami. Google Scholar
    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. Google ScholarDigital Library
    43. SCLAROFF, S., AND PENTLAND, A. 1991. Generalized implicit functions for computer graphics. Comput. Graph. (Proc. SIGGRAPH 91) 25, 4, 247–250. Google ScholarDigital Library
    44. SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591–1595.Google ScholarCross Ref
    45. SIMS, K. 1994. Evolving virtual creatures. In Proc. SIGGRAPH 94, 15–22. Google Scholar
    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.Google ScholarCross Ref
    47. STEWART, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Review 42, 1, 3–39. Google ScholarDigital Library
    48. TERZOPOULOS, D., PLATT, J., BARR, A., AND FLEISCHER, K. 1987. Elastically deformable models. Comput. Graph. (Proc. SIGGRAPH 87) 21, 4, 205–214. Google ScholarDigital Library
    49. TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 1528–1538.Google ScholarCross Ref
    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. Google ScholarDigital 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.Google ScholarCross Ref

ACM Digital Library Publication: