Tera-scale Computing

High-Performance Physical Simulations on Next-Generation Architecture with Many Cores

PHYSICS SIMULATION PIPELINE

Figure 1: Overview of physical simulation
click image for larger view
 

Figure 1 shows a typical time step in a physical simulation application. For each time step of a simulation, a physical simulation application takes as input the state of the simulated scene (e.g., positions, orientations, and velocities of all objects), as well as external control information (e.g., what the player is doing in a game). The application then computes the physical processes that potentially lead to an updated state (e.g., force, torque, or pressure generation). Depending on the scheme used, this information will be used to advance the state forward in time (e.g., time integration of the laws of motion), yielding a new candidate state. Should phenomena such as collisions or other constraints be triggered, the state may be updated in response to this collision or constraint, and the force computation/time stepping phases will be repeated, possibly with a smaller time step.

While game and production physics share the same iterative process, they exhibit important differences. These differences stem from the execution time requirements of their domains. Production physics is primarily used for special effects in movies and other off-line simulations. The execution time limit for these environments is typically a few minutes per frame in order to simulate the complete effect in a reasonable amount of time (e.g., less than a day). Game physics, on the other hand, is concerned with real-time simulation used in computer games. Thus, the execution time limit is at most tens of milliseconds per frame. Both areas of physical simulation have the goal of providing maximum visual plausibility within their execution time requirements.

We now describe how we model some specific phenomena.

Fluid Simulation

Production physics: Simulated water volumes are key elements in an increasing number of feature films, making fluid simulation (a.k.a., Computational Fluid Dynamics, or CFD) very common in the special effects industry today. Our production-quality fluid simulation application models a body of water with a free surface (as opposed to water flowing in a pipe or other airtight container). The application uses a combination of a three-dimensional grid and a set of particles [4]. The simulation tracks the velocity and pressure of the water in each grid cell. It computes how velocity and pressure change at each time step using incompressible Navier-Stokes equations. This is very computationally expensive, and it becomes much more so as the number of grid cells goes up. Unfortunately, unless prohibitively large grid resolutions are to be used, the grid cannot accurately represent intricate geometrical features of the water surface (such as thin sheets and droplets). Therefore, particles are sprinkled around the surface and advected along with the fluid. The updated positions and velocities of these particles are used to enhance the resolution of the water surface.

Game Physics: While CFD is the method of choice for high-fidelity simulation of fluids, its high computational requirements necessitate off-line rendering. Game physics therefore uses much faster, although less accurate, techniques. Smoothed Particle Hydrodynamics (SPH) has recently emerged as a popular technique for interactive simulation of fluids [9]. The SPH method represents a fluid as a set of discrete particles and models a resistance to density changes: when particles get too close to one another, a repulsive force separates them; when they get too far from each other, an attractive force brings them together. If a pair of particles is far enough apart, no forces act between them. SPH discretizes the Navier-Stokes equations and samples its solution at a finite number of such particles in space and time. While in the grid-based method the position of these sample points is fixed, in the SPH the particles are free to move around. This difference fundamentally changes the way the Navier- Stokes equations are solved and generally leads to much smaller complexity and ease of implementation, making SPH more suitable for interactive environments.

Cloth Simulation

Production physics: Cloth simulation models a cloth surface that can deform under the influence of external forces such as gravity or forced stretching, and internal forces such as the elastic response to tensile stress, shearing, and bending [2]. This application also models collisions of the piece of cloth with itself and other elements in the environment. The deformable cloth is modeled as a set of mass particles connected to form a triangle mesh. The mesh is endowed with a network of spring elements aligned with all triangle edges and altitudes, as well as between adjacent triangles. These springs model the cloth's resistance to various forms of deformation. Collision detection and resolution is a key part of this application. After the velocities and positions of the cloth particles are updated, collisions are detected. If the collisions cannot be resolved, the application undoes the updates from this iteration and re-executes it with a smaller time step.

Game Physics: Similar to production physics, game physics models a cloth object as a set of particles [7]. Each particle is subject to external forces, such as gravity, wind and drag, as well as various constraints. These constraints are used to maintain the overall shape of the object (spring constraints), and to prevent interpenetration with the environment (collision constraints). The particle's equation of motion resulting from applying the external forces is integrated using explicit Verlet integration. The above-mentioned constraints create a system of equations linking the particles' positions together. This system is solved at each simulation time step by relaxation, that is, by enforcing the constraints one after another for a fixed number of iterations. This method is less accurate but faster than the Conjugate Gradient solver [7] used in production physics, which enables the game cloth to simulate in real time. In addition, self-collisions are typically ignored.

Face Simulation

Production physics: Face simulation animates a model of a human face to provide an anatomically correct visualization of a person speaking or making facial expressions [12]. The application we examine assumes that inertia has a negligible effect on human faces in typical situations, and it therefore models facial motion as a sequence of steady states. Each state is defined by facial muscle activation and the position of the cranium and jawbone. The face is modeled as a tetrahedral mesh, which is driven by the facial musculature and the motion of the jawbone. The application takes as input a time sequence of muscle activation values and kinematics parameters for the jaw motion. The finite element method is used to define the forces (elastic deformation resistance and active muscle contraction) that act on the face and determine its shape.

Rigid Body Simulation

Game Physics: Rigid body dynamics [3] simulates motion and interaction of non-deformable objects when forces and torques are present in the system. Rigid body dynamics is the most commonly used physical simulation in video games today. Examples of rigid bodies in games are vehicles, rag dolls, cranes, barrels, crates, and even whole buildings. The traditional approach solves a system of ordinary differential equations, which represent Newton's second law of motion, F=ma, where m is the mass of an object, a is its acceleration, and F is the applied force. The applied force determines the acceleration of the object, so velocity and position are obtained by integration of the above equation. The main computational challenge comes from the fact that rigid bodies' motion is constrained due to their interaction with the environment. For example, consider a destructive environment in a video game where 1000s of rigid objects explode, collapse, and collide, resulting in 100,000s of interactive contacts. To realistically simulate such a scene requires determination of collisions, calculation of collision contact points, and physically correct computation of the contact forces that result from these contacts. To accelerate collision detection relies on spatial partitioning data structures, such as grids or bounding volume hierarchies. To determine contact forces that result from collision contact, we model the contact as a linear complementary problem [1].

Rigid body simulation in games today assumes that rigid bodies cannot break. In general, this assumption is not true in production physics. Today's films use animation of elasticity and fracture. However, these techniques are too slow for interactive use.

Back to Top