Statistical simulation of rigid bodies

ABSTRACT

We describe a method for replacing certain stages of rigid body simulation with a statistically-based approximation. We begin by collecting statistical data regarding changes in linear and angular momentum for collisions of a given object. From this data we extract a statistical "signature" for the object, giving a compact representation of the object's response to collision events. During object simulation, both the collision detection and the collision response calculations are replaced by simpler calculations based on the statistical signature.

Using this approach, we are able to achieve significant improvement in the performance of rigid body simulation. The statistical behavior of the simulation is maintained, including achieving valid resting positions. We present results from a variety of simulations that demonstrate the method and its performance improvement. The method is appropriate for rigid body simulation situations requiring significant performance improvement, and allowing for some loss in fidelity.

REFERENCES

• 1: [AECO05] Atencio Y., Esperanca C., Cavalcanti P., Oliveira A.: A collision detection and response scheme for simplified physically based animation. In SIBGRAPI, the 18th Brazilian Symposium on Computer Graphics and Image Processing (2005), pp. 291--298. 3
• 2: [AMHH08] Akenine-Möller T., Haines E., Hoffman N.: Real-Time Rendering 3rd Edition. A. K. Peters, Ltd., Natick, MA, USA, 2008. 3
• 3: [Ber97] Berka R.: Reduction of computations in physics-based animation using level of detail. In 13th Spring Conference on Computer Graphics (1997), pp. 69--76. 2
• 4: [BHW96] Barzel R., Hughes J. F., Wood D. N.: Plausible motion simulation for computer graphics animation. In Proc. Eurographics Workshop Computer Animation and Simulation (1996), Springer, pp. 183--197. 2
• 5: [BJ05] Barbič J., James D. L.: Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. 24, 3 (2005), 982--990. 2
• 6: [BW01] Baraff D., Witkin A.: Physically-Based Modeling. Tech. rep., SIGGRAPH Course Notes: pixar.com/companyinfo/research/pbm2001/, 2001. 1, 3
• 7: [CF97] Chenney S., Forsyth D.: View-dependent culling of dynamic systems in virtual environments. In Proceedings of Symposium on Interactive 3D Graphics (1997), pp. 55--58. 2
• 8: [CF00] Chenney S., Forsyth D. A.: Sampling plausible solutions to multi-body constraint problems. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 2000), ACM Press/Addison-Wesley Publishing Co., pp. 219--228. 2
• 9: [CH97] Carlson D. A., Hodgins J. K.: Simulation levels of detail for real-time animation. In Proceedings Of Graphics Interface (1997), pp. 1--8. 2
• 10: [CLMP95] Cohen J. D., Lin M. C., Manocha D., Ponamgi M.: I-collide: an interactive and exact collision detection system for large-scale environments. In SI3D '95: Proceedings of the 1995 symposium on Interactive 3D graphics (New York, NY, USA, 1995), ACM, pp. 189--ff. 7
• 11: [EL01] Ehmann S., Lin M.: Accurate and fast proximity queries between polyhedra using surface decomposition. Computer Graphics Forum (Proceedings of Eurographics) 20, 3 (2001), 500--510. 7
• 12: [GBF03] Guendelman E., Bridson R., Fedkiw R.: Nonconvex rigid bodies with stacking. Transactions on Graphics 22 (2003), 871--878. Proceedings of SIGGRAPH 2003. 1
• 13: [Hub96] Hubbard P. M.: Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. 15, 3 (1996), 179--210. 3
• 14: [Jak03] Jakobsen T.: Advanced Character Physics. Tech. rep., Gamasutra.com Resource guide: gamasutra.com/resource_guide/20030121/jacobson_01.shtml, 2003. 3
• 15: [JF03] James D. L., Fatahalian K.: Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics 22 (2003), 879--887. 2
• 16: [JP04] James D. L., Pai D. K.: Bd-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. 23, 3 (2004), 393--398. 3
• 17: [MC95] Mirtich B., Canny J.: Impulse-based simulation of rigid bodies. In SI3D '95: Proceedings of the 1995 symposium on Interactive 3D graphics (New York, NY, USA, 1995), ACM, pp. 181--ff. 3
• 18: [Mir96] Mirtich B.: Impulse-Based Dynamic Simulation of Rigid Body Systems. Ph.D. thesis, Computer Science, University of California at Berkeley, Berkeley, CA, 1996. (See Section 7.5). 4
• 19: [OD01] O'Sullivan C., Dingliana J.: Collisions and perception. ACM Trans. Graph. 20, 3 (2001), 151--168. 2
• 20: [ODGK03] O'Sullivan C., Dingliana J., Giang T., Kaiser M. K.: Evaluating the visual fidelity of physically based animations. ACM Trans. Graph. 22, 3 (2003), 527--536. 2
• 21: [PSE*00] Popović J., Seitz S. M., Erdmann M., Popović Z., Witkin A.: Interactive manipulation of rigid body simulations. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 2000), ACM Press/Addison-Wesley Publishing Co., pp. 209--217. 3
• 22: [TJ08] Twigg C. D., James D. L.: Backward steps in rigid body simulation. ACM Trans. Graph. 27, 3 (2008), 1--10. 3
• 23: [TLP06] Treuille A., Lewis A., Popović Z.: Model reduction for real-time fluids. ACM Trans. Graph. 25, 3 (2006), 826--834. 2
• 24: [TT01] Thomas F., Torras C.: 3d collision detection: A survey. Computers and Graphics 25 (2001), 269--285. 3

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation