W O L F G A N G   B L O C H I N G E R  :: 

Physically Based Simulation of Cloth on Parallel Computers

Simulating flexible objects is far more challenging compared to rigid objects. Cloth is a typical example of the class of flexible objects that has gained considerable attention in science and in industry. Simulating cloth in a physically exact manner poses high computational demands. The simulation process involves a large number of discrete time steps. Within each step the computation can logically be divided into two different phases:

• Physical Modeling Phase: In the first phase of a simulation step, internal forces resulting from deformation and external forces due to gravity or wind effects are determined. Based on these forces, updates for nodal velocities and positions are computed according to Newton’s law of motion.
• Collision Handling Phase: The second phase of a simulation step is responsible for detecting and handling interactions of the garment with other objects in the scene and also interactions of the garment with itself (self-interference). This phase results in motion constraints, repulsion forces, or position/velocity updates for individual nodes.

In this research project we investigate on parallel techniques for both phases, especially focusing on novel methods for parallel collision handling. To deal with the very fine granularity of the physical modeling phase we apply a static data decomposition approach based on advanced graph partitioning methods. Especially with flexible objects, several immanent properties of collision handling make the parallelization of this phase most challenging. Basically, collision handling is a global problem, because any pair of processors can own interfering elements. Thus, communication cannot be limited to processors owning neighboring elements (as within the physical modeling phase). During the course of simulation, the geometry of the considered object can change significantly. This means that also communication partners are changing in a highly dynamic manner. Moreover, interaction patterns cannot be predicted and are often extremely unstructured. We developed a task-parallel method for collision handling which can cope with this high degree of irregularity and which can also be tightly integrated with the physical modeling phase. Specifically, our method is based on fully dynamic problem decomposition realized by the DOTS system platform.

Example Scenes

We evaluate the performance of our approach using two test scenarios. To demonstrate the robustness of our method we focused on problems with a high degree of irregularity. In the following figures we visualize the static problem decomposition of the physical modeling phase (implemented by graph partitioning techniques) by different colors.

Scene 1

This scene consists of a square piece of cloth draping over a thin undulated bar which is posed at some distance to a floor. In the first part of the simulation collisions are locally restricted. Due to the special shape of the bar complicated folding patterns are formed as the cloth falls further downwards. When the cloth reaches the floor, collisions occur more widespread. In this scenario rigid collisions are initially predominant. As the simulation proceeds, fairly complex self-collisions are produced: the cloth folds over itself while it slides towards the troughs of the bar.

Scene 2

In this scene a round table cloth drapes over a sphere with roughly on third of the cloth’s diameter. Initially, collisions only occur in a locally restricted region at the center of the cloth. As the simulation proceeds, the distribution of the collisions in the scene becomes more even. In the last part of the sequence the formation of folds exhibiting complicated self-collisions can be observed. Finally, inter-processor self-collisions occur at the border regions of the cloth.

Performance Results

We used a Linux based cluster for carrying out performance measurements. The cluster nodes (Intel Xeon @ 2.667 GHz, 2 GB main memory) are connected by a Myrinet-2000 network. All program runs compute 25 frames of our test scenes, where a single frame is comprised of 40 simulation steps. The following diagrams show the run times for different number of processors.

Parallel Run Times for Scenes 1 and 2

We additionally compare the average CPU utilization during the collision handling phase for each computed frame with and without dynamic problem decomposition (and load balancing) for program runs on 12 processors. The left diagrams additionally give the total time spent on collision handling for each frame (comprising 40 individual collision handling phases) without dynamic problem decomposition and the right diagrams give the improvement of parallel efficiency obtained for computing the respective frame employing dynamic problem decomposition.

Effects of Dynamic Problem Decomposition (Scene 1)

Effects of Dynamic Problem Decomposition (Scene 2)

Selected Publications:

• B. Thomaszewski, S. Pabst, and W. Blochinger. Parallel techniques for physically-based simulation on multi-core processor architectures. Computers & Graphics;, 32(1):25-40, 2008.
• B. Thomaszewski and W. Blochinger. Physically based simulation of cloth on distributed memory architectures. Parallel Computing, 33(6):377-390, 2007.
• M. Keckeisen and W. Blochinger. Parallel implicit integration for cloth animations on distributed memory architectures. In Proc. of Eurographics Symposium on Parallel Graphics and Visualization 2004, Grenoble, France, June 2004.