Physically based animation
Physically based animation is an area of interest within computer graphics concerned with the simulation of physically plausible behaviors at interactive rates. Advances in physically based animation are often motivated by the need to include complex, physically inspired behaviors in video games, interactive simulations, and movies. Although off-line simulation methods exist to solve most all of the problems studied in physically-based animation, these methods are intended for applications that necessitate physical accuracy and slow, detailed computations. In contrast to methods common in offline simulation, techniques in physically based animation are concerned with physical plausibility, numerical stability, and visual appeal over physical accuracy. Physically based animation is often limited to loose approximations of physical behaviors because of the strict time constraints imposed by interactive applications. The target frame rate for interactive applications such as games and simulations is often 25-60 hertz, with only a small fraction of the time allotted to an individual frame remaining for physical simulation. Simplified models of physical behaviors are generally preferred if they are more efficient, easier to accelerate (through pre-computation, clever data structures, or SIMD/GPGPU), or satisfy desirable mathematical properties (such as unconditional stability or volume conservation when a soft body undergoes deformation). Fine details are not important when the overriding goal of a visualization is aesthetic appeal or the maintenance of player immersion since these details are often difficult for humans to notice or are otherwise impossible to distinguish at human scales.
Physically based animation is now common in movies and video games, and many techniques were pioneered during the development of early special effects scenes and game engines. Star Trek II: The Wrath of Khan famously used particle systems in the Genesis explosion scene to create the visual effect of a flaming shockwave engulfing a planet. Despite being released before physics engines were a common feature in games, System Shock incorporated rigid body physics in its engine and was widely considered innovative for this feature and the novel sense of interaction it afforded players. Valve later developed Half-Life and used rigid body physics to create environmental puzzles for the player, such as obstacles that could not be reached without stacking boxes. Half-Life 2 featured a more advanced physics engine that incorporated constrained systems such as pulleys or levers with more environmental puzzles to showcase these features. Physics engines are now much more common in games, and their frequent appearance has motivated research in physically based animation by companies such as Nvidia.
Physically based animation in games and simulations
Physically based animation is common in games and simulations where users have the expectation of interaction with the environment. Physics engines such as Havok, PhysX, and Bullet exist as separately developed products to be licensed and included in games. In games such as Angry Birds or World of Goo, physically based animation is itself the primary game mechanic and players are expected to interact with or create physically simulated systems in order to achieve goals. Aspects of physics puzzle games exist in many games that belong to other genres but feature physically based simulation. Allowing physical interaction with the environment through physically based animation promotes non-linear solutions to puzzles by players, and can sometimes results in solutions to problems presented in games that were not deliberately included by level designers. Simulations used for purposes other than entertainment, such as military simulations, also make use of physically based animation to portray realistic situations and maintain the immersion of users. Many techniques in physically based animation are designed with GPGPU implementations in mind or can otherwise be extended to benefit from graphics hardware, which can be used to make physically based simulations fast enough for gaming. GPU time is often reserved for rendering, however, and frequent data transfers between the host and device can easily become a bottleneck to performance.
Physically based animation in movies
Simulations can be performed offline (as in apart from when they are viewed) in the development of special effects for movies. Speed is therefore not strictly a necessity in the production of special effects but is still desirable for reasonably responsive feedback and because the hardware required for slower methods is more expensive. However, physically based animation is still preferred because slower, more accurate methods can be costly and limiting. The physical accuracy of small details in a special effect are not meaningful to their visual appeal, restrict the amount of control that artists and directors can exert over behavior, and increase the monetary cost and time required to achieve results. It is necessary to be able to dictate the high level behavior of physically inspired effects in movies in order to achieve a desired artistic direction, but scripting physical behaviors on the level of small details can be unfeasible when fluids, smoke, or many individual objects are involved. Physically based animation generally affords more artist control over the appearance of simulated results and is also more convenient when desired effects might bend or defy physics.
Rigid Body Simulation
Simplified rigid body physics is relatively cheap and easy to implement, which is why it appeared in interactive games and simulations earlier than most other techniques. Rigid bodies are assumed to undergo no deformation during simulation so that rigid body motion between time steps can be described as a translation and rotation, traditionally using affine transformations stored as 4x4 matrices. Alternatively, quaternions can be used to store rotations and vectors can be used to store the objects offset from the origin. The most computationally expensive aspects of rigid body dynamics are collision detection, correcting interpenetration between bodies and the environment, and handling resting contact. Rigid bodies are commonly simulated iteratively, with back-tracking to correct error using smaller timesteps. Resting contact between multiple rigid bodies (as is the case when rigid bodies fall into piles or are stacked) can be particularly difficult to handle efficiently and may require complex contact and shock propagation graphs in order to resolve using impulse-based methods. When simulating large numbers of rigid bodies, simplified geometries or convex hulls are often used to represent their boundaries for the purpose of collision detection and response (since this is generally the bottleneck in simulation).
Soft Body Simulation
Soft bodies can easily be implemented using spring-mesh systems. Spring mesh systems are composed of individually simulated particles that are attracted to each other by simulated spring forces and experience resistance from simulated dampeners. Arbitrary geometries can be more easily simulated by applying spring and dampener forces to the nodes of a lattice and deforming the object with the lattice. However, explicit solutions to these systems are not very numerically stable and are extremely difficult to control the behavior of through spring parameters. Techniques that allow for physically plausible and visually appealing soft bodies, are numerically stable, and can be configured well by artists were prohibitively expensive in early gaming history, which is why soft bodies were not as common as rigid bodies. Integration using Runge-Kutta methods can be used to increase the numerical stability of unstable techniques such as spring meshes or finer time steps can be used for simulation (although this is more costly and cannot make spring meshes stable for arbitrarily large forces). Techniques such as shape matching and position based dynamics address these problems with interactive games and simulations in mind. Position based dynamics is used in mainstream game engines such as Bullet (software), Havok, and PhysX. Unconditional stability and ease of configuration are particularly desirable properties of soft body simulations that can be difficult to achieve with spring-mesh systems, although they are still often used in games because of their simplicity and speed.
Computational fluid dynamics can be expensive, and interactions between multiple fluid bodies or with external objects/forces can require complex logic to evaluate. Fluid simulation is generally achieved in video games by simulating only the height of bodies of water to create the effect of waves, ripples, or other surface features. For relatively free bodies of liquid, Lagrangian or semi-Lagrangian methods are often used to speed up the simulation by treating particles as finite elements of fluid (or carriers of physical properties) and approximating the Navier-Stokes equations . It is uncommon to simulate bodies of fluid in games, although surface features may be simulated using similar methods and fluid simulations may be used to generate textures or height-fields to render water in real-time without real-time simulation (this is commonly done for large bodies of water in games). Fluid simulations can be computed using commodity graphics hardware through GPGPU, and height fields can be efficiently computed that result in wave-like behavior using Lattice Boltzmann methods. Alternatively, surface features and waves can be simulated as particles and a height field generated from the simulated particles in real-time. This also allows for efficient two way interaction between the fluid and floating objects.
Particle systems are an extremely popular technique for creating visual effects in movies and games because of their ease of implementation, efficiency, extensibility, and artist control. The update cycle of particle systems usually consists of the three phases: generation, simulation, and extinction. These phases respectively consist of the introduction of new particles, simulating them through the next timestep, and removing particles that have exceeded their life-span. The physical and visual attributes of particles are usually randomized on generation with the range and distribution of attributes controlled by the artist. Particle systems can further be made to generate particle systems themselves to create more complex and dynamic effects, and their high-level behavior can be choreographed through a framework of operators as in the canonical Sims paper.  Early games that rendered systems of particles suffered from clipping artifacts when particles partially intersected geometry in the environment, and this artifact was especially noticeable for large particles (which were often used to stand in for smoke). Soft particles address these artifacts through careful shading and manipulation of the transparency of particles, such that particles become more transparent as they approach surfaces.
In physically based animation, flocking refers to a technique that models the complex behavior of birds, schools of fish, and swarms of insects using virtual forces. These virtual forces simulate the tendency for flocks to center their velocities, avoid collisions and crowding, and move toward the group. In these simulations, individual members of the flock (sometimes called boids, short for bird-oid) act without collaboration using only information about the position and velocity of their peers to create the illusion of synchronized, group behavior efficiently. Flocking can be used to efficiently approximate the behavior of crowds of humans as well, and methods based on flocking are often used for crowds of NPCs in gaming. Unreal and Half-Life were among the first games to implement flocking, which was used to model the behavior of birds and flying creatures present in outdoor levels.
Physically Based Character Animation
Characters in games and simulations are traditionally animated through methods such as keyframing that define animations through compositions of smaller, static motions sequenced to convey more complex behavior. Visually, these static methods cannot easily convey complex interactions with the environment and make lifelike character motion difficult to accomplish. Techniques in physically based character animation achieve dynamic animations that respond to user interaction, external events, and the environment by optimizing motions toward specified goals given physically based constraints such as energy minimization. The adoption of physically based character animation, as opposed to more static methods, has been slow in the gaming industry due to the increased cost and complexity associated with its use. Physically based character animation has been used in the Skate (video game) series of video games, and in the independently developed first-person shooter StarForge.
- Baraff; Witkin (1999). "Physically Based Modeling Course Notes". SIGGRAPH. Course 36.
- Reeves, W. "Particle Systems - A technique for modeling a class of fuzzy objects" (PDF). ACM Transactions on Graphics.
- Müller, M.; B. Heidelberger; M. Hennix; J. Ratcliff (2006). "Position Based Dynamics" (PDF). Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys).
- Müller, M.; B. Heidelberger; M. Teschner; M. Gross (2005). "Meshless Deformations Based on Shape Matching". Proceedings of SIGGRAPH. 24 (3): 471. doi:10.1145/1073204.1073216.
- Foster; Metaxas (1996). "Realistic Animation of Liquids" (PDF). Graphical Models and Image Processing. 58 (5): 471–483. doi:10.1006/gmip.1996.0039.
- Stam, J. (1999). "Stable Fluids" (PDF). SIGGRAPH.
- Geist, Robert; Christopher Corsi; Jerry Tessendorf; James Westall (2010). "Lattice-Boltzmann Water Waves" (PDF). ISVC.
- Yuksel, Cem; Donald House; John Keyser (2007). "Wave Particles" (PDF). SIGGRAPH. 26 (3): 99. doi:10.1145/1276377.1276501.
- Sims, Karl (August 1990). "Particle Animation and Rendering Using Data Parallel Computation" (PDF). Computer Graphics. 4. 24 (4): 405–413. doi:10.1145/97880.97923.
- Reynolds, C. (1989). "Flocks, herds and schools: A distributed behavioral model". SIGGRAPH.
- Geijtenbeek, T.; N. Pronost; A. Egges; and M.H. Overmars (2011). "Interactive Character Animation using Simulated Physics" (PDF). Eurographics.