Hardware-based simulation and collision detection for large particle systems

ABSTRACT

Particle systems have long been recognized as an essential building block for detail-rich and lively visual environments. Current implementations can handle up to 10,000 particles in real-time simulations and are mostly limited by the transfer of particle data from the main processor to the graphics hardware (GPU) for rendering.This paper introduces a full GPU implementation using fragment shaders of both the simulation and rendering of a dynamically-growing particle system. Such an implementation can render up to 1 million particles in real-time on recent hardware. The massively parallel simulation handles collision detection and reaction of particles with objects for arbitrary shape. The collision detection is based on depth maps that represent the outer shape of an object. The depth maps store distance values and normal vectors for collision reaction. Using a special texture-based indexing technique to represent normal vectors, standard 8-bit textures can be used to describe the complete depth map data. Alternately, several depth maps can be stored in one floating point texture.In addition, a GPU-based parallel sorting algorithm is introduced that can be used to perform a depth sorting of the particles for correct alpha blending.

REFERENCES

• 1: {ATI03} Ati Technologies Inc.: Normal map compression. Tech. rep., ATI Technologies Inc., 2003. http://www.ati.com/developer/techpapers.html.
• 2: {Bat68} Batcher K.: Sorting networks and their applications. In Spring Joint Computer Conference, AFIPS Proceedings (1968), pp. 307--314.
• 3: George Baciu , Wingo S. K. Wong, Image-Based Techniques in a Hybrid Collision Detector, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.254-271, April 2003 [doi>10.1109/TVCG.2003.1196011]
• 4: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 5: {Gre03} Green S.: Stupid opengl shader tricks. http://developer.nvidia.com/docs/IO/8230/GDC2003_OpenGLShaderTricks.pdf, 2003.
• 6: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 7: Mark Jason Harris , Anselmo Lastra, Real-time cloud simulation and rendering, 2003
• 8: Wolfgang Heidrich , Hans-Peter Seidel, View-independent environment maps, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.39-ff., August 31-September 01, 1998, Lisbon, Portugal [doi>10.1145/285305.285310]
• 9: {HZLM02} Hoff K., Zaferakis A., Lin M., Manocha D.: Fast 3D Geometric Proximity Queries between Rigid and Deformable Models Using Graphics Hardware Acceleration. Tech. Rep. TR-02-004, University of North Carolina at Chapel Hill, 2002.
• 10: {KJ01} Kolb A., John L.: Volumetric model repair for virtual reality applications. In EUROGRAPHICS Short Presentation (2001), University of Manchester, pp. 249--256.
• 11: Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Fast penetration depth computation for physically-based animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545266]
• 12: {LG98} Lin M. C., Gottschalk S.: Collision detection between geometric models: a survey. In Proceedings of IMA Conference on Mathematics of Surfaces (1998), pp. 37--56.
• 13: {McA00} McAllister D.: The Design of an API for Particle Systems. Tech. rep., Dep. of Computer Science, University of North Carolina at Chapel Hill, 2000.
• 14: {NT99} Nooruddin F., Turk G.: Simplification and repair of polygonal models using volumetric techniques. Tech. Rep. GITGVU -99-37, Georgia Institute of Technology, Atlanta, 1999.
• 15: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 16: {NVI03} NVIDIA Corporation: NVIDIA SDK. http://developer.nvidia.com, 2003.
• 17: {NVI04} NVIDIA Corporation: OpenGL extension EXT_pixel_buffer_object. http://oss.sgi.com/projects/ogl-sample/registry/EXT/pixel_buffer_object.txt, 2004.
• 18: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 19: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 20: {Per03} Percy J.: OpenGL Extensions. www.ati.com/ developer/techpapers.html, 2003.
• 21: {Ree83} Reeves W.: Particle systems - technique for modeling a class of fuzzy objects. In ACM Proceedings SIGGRAPH (1983), vol. 2, pp. 91--108.
• 22: Karl Sims, Particle animation and rendering using data parallel computation, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.405-413, September 1990, Dallas, TX, USA
• 23: {Ver67} Verlet L.: Computer experiments on classical fluids. i. thermodynamical properties of lennard-jones molecules. Physical Review 159 (1967).
• 24: {VSC01} Vassilev T., Spanlang B., Chrysanthou Y.: Fast cloth animation on walking avatars. In Proc. EUROGRAPHICS (2001), vol. 20, Eurographics Association, pp. 260--267.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
      I.3.7 Three-Dimensional Graphics and Realism