Fakultät Informatik

Efficient Realization of Mass-Spring Systems on Graphics Hardware

by  Florian Echtler, 2004


Abstract
Physics-based simulation of deformable objects is a valuable tool for creating realistic and plausible computer graphics. However, even the calculations involved for simple abstractions like mass-spring models are highly demanding, especially when real-time simulation is desired.

This diploma thesis explores the possibility to use the powerful vector computation engine present in modern 3D graphics hardware for these calculations and shows a significant performance gain over CPU-based solutions, which in turn allows the use of larger and more detailed models.


Introduction
There exists a multitude of papers regarding the topic of physical simulation. This vast field of research can be partitioned roughly into three separate subtopics: particle systems (fluids/gasses), rigid bodies and deformable objects. This thesis primarily deals with the latter.

Simulating elastic or plastic objects has widely different uses. A significant amount of research is directed towards surgery training in virtual environments, as the simulated tissue should behave as close to the real thing as possible.
Entertainment is another possible field of use. Computer games or rendered movies always strive for more realism, and elastic objects or organic beings that move realistically do wonders for plausibility.
Designers, especially fashion designers, also have various uses for simulating flexible materials like cloth. It is a huge advantage to be able to get a first impression of a new piece of clothing without actually having to tailor it.

Of course, the ultimate goal is not only to create realistic motion, but to do it in realtime. Only then will an user be able to properly interact with the simulation.

Mathematical Methods
The field of deformable object simulation can itself be subdivided according to the mathematical foundations that are used. There are basically two important methods: the finite-element method and mass-spring systems.

In cases where accuracy is premium, the finite-element method, or FEM for short, is widely used. But where speed is of greater importance, simpler models like mass-spring systems have their merits, too. These approaches describe an elastic model as a (likely irregular) mesh of springs connected at mass points, around which they can freely rotate. Motion and deformation of the entire object are thereby expressed through the relative motion of individual mass points.

Of course, the calculations involved are still time-consuming and require a lot of floating point processing power. A discrete integration method is used to calculate the state of the mass-spring system at a time in the future, based on its past and current states. This requires the calculation and manipulation of force, velocity, acceleration and displacement vectors at a high rate, thereby putting quite a strain on a common CPU when interactive frame rates are desired.

No CPU Attached
One possibility to take the load off the CPU comes from an unexpected direction. Modern-day graphics hardware, such as ATI's Radeon or Nvidia's GeForce, carries a high-performance graphics processing unit (GPU), which often surpasses the CPU in some performance aspects, like vector calculations. Of course, GPUs were primarily designed with 4-component (red, green, blue, alpha) color vectors and applications like texture mapping in mind, and earlier models, like the famed 3DFX Voodoo card, could indeed not be used for other purposes.

However, with the advent of so-called shaders, small assembly programs which are executed directly on the GPU and allow parts of its functionality to be customized, nothing prevents this vector crunching power to be used for the calculation of spatial vectors, as it is necessary for mass-spring simulation. Until recently, one major drawback to this approach has been the fact that the newly calculated position vectors, present in graphics memory, had to be read back by the CPU and re-inserted into the graphics pipeline.

But with the recently presented OpenGL Superbuffers extension and its beta implementation by ATI, this performance bottleneck has been erased. Superbuffers allow independent management of memory blocks on the graphics card and thereby make it possible to use the same memory range either as color or spatial vectors without having to read it back through the CPU. In this thesis, the potential of this approach shall be examined.

Examples
Some screenshots are given below. Click on the images to download a short MPEG4 movie.

+
dragging the Stanford bunny
+
elastic bar under influence of gravity
+
simulated liver
plastic cuboid before...
...and after deformation
 

News

Matthias Niessner, our new Professor from Stanford University, offers a number of interesting topics for  master theses.

 

A new PhD/PostDoc position on  Computational Fabrication and 3D Printing is available at the Computer Graphics & Visualization group.

 

A new PhD position is available at the games engineering group.  Check it out here.