Particle-based simulation of granular materials

ABSTRACT

Granular materials, such as sand and grains, are ubiquitous. Simulating the 3D dynamic motion of such materials represents a challenging problem in graphics because of their unique physical properties. In this paper we present a simple and effective method for granular material simulation. By incorporating techniques from physical models, our approach describes granular phenomena more faithfully than previous methods. Granular material is represented by a large collection of non-spherical particles which may be in persistent contact. The particles represent discrete elements of the simulated material. One major advantage of using discrete elements is that the topology of particle interaction can evolve freely. As a result, highly dynamic phenomena, such as splashing and avalanches, can be conveniently generated by this meshless approach without sacrificing physical accuracy. We generalize this discrete model to rigid bodies by distributing particles over their surfaces. In this way, two-way coupling between granular materials and rigid bodies is achieved.

REFERENCES

• 1: {AT01} Aranson I. S., Tsimring L. S.: Continuum description of avalanches in granular media. Physical Review E 64 (2001), 020301.
• 2: {BA02} Baerentzen J. A., Aanaees H.: Generating signed distance fields from triangle meshes. IMM Technical Report, 21 (2002).
• 3: {Bar97} Baraff D.: An introduction to physically based modeling, course notes. ACM SIGGRAPH, 1997.
• 4: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 5: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 6: Benoit Chanclou , Annie Luciani , Arash Habibi, Physical Models of Loose Soils Dynamically Marked by a Moving Object, Proceedings of the Computer Animation, p.27, June 03-04, 1996
• 7: {CS79} Cundall P. A., Strack O. D. L.: A discrete numerical model for granular assemblies. Geotechnique 29, 1 (1979), 47--65.
• 8: {DC99} Desbrun M., Cani M.-P.: Space-time adaptive simulation of highly deformable substances. Tech. rep., INRIA, 1999.
• 9: {dG99} De Gennes P. G.: Granular matter: a tentative view. Reviews of Modern Physics 71 (1999), S374--S382.
• 10: {DR99} Dury C. M., Ristow G. H.: Competition of mixing and segregation in rotating cylinders. Physics of Fluids 11, 6 (1999), 1387--1394.
• 11: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 12: {HL98} Herrman H. J., Luding S.: Modeling granular media on the computer. Continuum Mech. Thermodyn. 10 (1998), 189--231.
• 13: {HMT01} Hadap S., Magnenat-Thalmann N.: Modeling dynamic hair as continuum. In Eurographics Proceedings. Computer Graphics Forum, Vol. 20, No. 3 (2001).
• 14: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 15: {JGD94} J. Ennis B., Green J., Davies R.: The legacy of neglect in the u.s. Chemical Engineering Progress 90 (1994), 32--43.
• 16: {JNB96} Jaeger H. M., Nagel S. R., Behringer R. P.: Granular solids, liquids, and gases. Reviews of Modern Physics 68, 4 (1996), 1259--1273.
• 17: J. D. Lambert, Numerical methods for ordinary differential systems: the initial value problem, John Wiley & Sons, Inc., New York, NY, 1991
• 18: {Lee94} Lee J.: Heap formation in two-dimensional granular media. Journal of Physics A 27 (1994).
• 19: {LH93} Lee J., Herrmann H. J.: Angle of repose and angle of marginal stability: molecular dynamics of granular particles. Journal of Physics A 26 (1993).
• 20: {LHM95} Luciani A., Habibi A., Manzotti E.: A multi-scale physical model of granular materials. In In Proceedings of Graphics Interface '95 (1995), pp. 136--146.
• 21: {LL86} Landau L. D., Lifshitz E. M.: Theory of Elasticity. Pergamon Books Ltd., 1986.
• 22: Xin Li , J. Michael Moshell, Modeling soil: realtime dynamic models for soil slippage and manipulation, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.361-368, September 1993 [doi>10.1145/166117.166162]
• 23: Matthias Müller , David Charypar , Markus Gross, Particle-based fluid simulation for interactive applications, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 24: Brian Mirtich, Fast and accurate computation of polyhedral mass properties, Journal of Graphics Tools, v.1 n.2, p.31-50, February 1996
• 25: J. J. Monaghan, Simulating free surface flows with SPH, Journal of Computational Physics, v.110 n.2, p.399-406, Feb. 1994 [doi>10.1006/jcph.1994.1034]
• 26: {MP89} Miller G., Pearce A.: Globular dynamics: A connected particle system for animating viscous fluids. Computer and Graphics 13, 3 (1989), 305--309.
• 27: Victor J. Milenkovic , Harald Schmidl, Optimization-based animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.37-46, August 2001 [doi>10.1145/383259.383263]
• 28: Koichi Onoue , Tomoyuki Nishita, Virtual Sandbox, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.252, October 08-10, 2003
• 29: {PB93} Pöschel T., Buchholtz V.: Static friction phenomena in granular materials: Coulomb law versus particle geometry. Physical Review Letters 71, 24 (1993), 3963--3966.
• 30: {PB95} Pöschel T., Buchholtz V.: Molecular dynamics of arbitrarily shaped granular particles. Journal of Physics I France 5 (1995), 1431--1455.
• 31: {PTB*03} Premoze S., Tasdizen T., Bigler J., Lefohn A., Whitaker R.: Particle-based simulation of fluids. Computer Graphics Forum 22, 3 (2003).
• 32: William T. Reeves, Particle systems—a technique for modeling a class of fuzzy objects, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.359-375, July 25-29, 1983, Detroit, Michigan, United States
• 33: {RPBS99} Ramìrez R., Pöschel T., Brilliantov N. V., Schwager T.: Coefficient of restitution of colliding viscoelastic spheres. Physical Review E 60 (1999), 4465--4472.
• 34: {SDW96} Schäfer J., Dippel S., Wolf D. E.: Force schemes in simulations of granular materials. Journal of Physics 6 (1996).
• 35: {SOH99} Sumner R. W., O'Brien J. F., Hodgins J. K.: Animating sand, mud, and snow, Computer Graphics Forum 18, 1 (1999), 17--26.
• 36: {SP98} Schwager T., Pöschel T.: Coefficient of normal restitution of viscous particles and cooling rate of granular gases. Physical Review E 57, 1 (1998), 650--654.
• 37: {SvHSvS04} Snoeijer J. H., Van Hecke M., Somfai E., Van Saarloos W.: Packing geometry and statistics of force networks in granular media. Physical Review E 70 (2004).
• 38: {Ton91} Tonnesen D.: Modeling liquids and solids using thermal particles. In Proc. Graphics Interface (1991), pp. 255--262.
• 39: {TPF89} Terzopoulos D., Platt J., Fleisher K.: Heating and melting deformable models(from goop to glop). In Proc. Graphics Interface (1989), pp. 219--226.
• 40: {TPG99} Treece G. M., Prager R. W., Gee A. H.: Regularised marching tetrahedra: improved iso-surface extraction. Computers and Graphics 23, 4 (1999), 583--598.
• 41: Greg Turk, Re-tiling polygonal surfaces, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.55-64, July 1992
• 42: {WB93} Walton O. R., Braun R. L.: Simulation of rotary-drum and repose tests for frictional spheres and rigid sphere clusters. In DOE/NSF Workshop on Flow of Particulates, Ithaca, NY, 29 Sep. - 1 Oct. 1993 (1993), vol. 29.
• 43: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 44: {YKO96} Yoon H., Koshizuka S., Oka Y.: A particle gridless hybrid method for incompressible flows. Int. J. Numer. Meth. Fluids 29, 4 (1996).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation