Physics Based Simulation on GPUs

Author:  Benjamin Herrmann, 2005


Introduction

Traditionally, physically based simulation is done on the CPU, however the pace of innovation in graphics hardware is staggering and continues to outpace processor development, while the programmable rendering pipeline on the other hand takes graphics hardware a long step closer to general purpose computing.

This works tries to combine these aspects by presenting an approach of performing physical based simulation on graphics hardware, without the need for memory transfers between system memory and graphics memory. The latter is realised by using the concept of Memory Objects.

The presented algorithms basically allow for the simulation of cloth, rigid and soft bodies based purely on their mesh representation. The main aspects discussed in this work are: preserving shape, collision detection, collision response and moving objects due to external forces (wind, gravitation, etc.). The implementation of these concepts was realised using C++, OpenGL and Cg.

Overview

The main idea of this approach is to simulate objects as an independent point-mass system using the verlet integration scheme. Independent in this context means that the point-masses are simulated independently of any connectivity information. Preserving the shape of the original object is then realised by applying additional rendering passes to satisfy all distance constraints between any two connected particles by offsetting their position such that the original distance between both particles is satisfied. This approach achieves a greater stability than traditional mass-spring systems though it is dependant on the order in which distance constraints are satisfied.

Mapping of algorithms to the streamline computing paradigm of graphics hardware is most easily achieved if particles are simulated absolutely independently of each other. Though this was the basis were we started, the introduction of constraints introduces dependencies, which could only be calculated on graphics hardware by breaking the particle system into independent sub-systems and simulating those in distinct rendering passes.

This model was implemented using a particle-based and an edge-based data structure for representing objects. Also GPU-based collision detection and -response were introduced between any pairs of particles in order to solve self-collision and inter-object collision. A regular binning of the axis-aligned bounding box of the complete particle system was used to increase performance in the otherwise computationally expansive task of comparing all pairs of particles. The parallel execution of collision detection on graphics hardware increased performance significantly in contrast to the CPU implementation using the same approach. This allowed the simulation of a particle system of size 512x512 with pair-wise collision detection at 15.5 fps. on a Intel Pentium 3.2 GHz equipped with a ATI Radeon X600 graphics card.

The verlet integration scheme ensured that changing the position of particles during any phase of the simulation (constraint-solver or collision-response) implicitly adapted the affected particles' velocities, thereby ensuring a greater stability of the simulation as position-offset and stored velocity of a particle could not become asynchronous this way.

For a detailed description of the involved algorithms and their mapping to an implementation on graphics hardware, please consult the written thesis, which can be found in the download section of this document.

Downloads

• Thesis (pdf)
• Presentation (ppt)

Benjamin Herrmann, August 2005, Munich