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

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