This chapter introduces Linear Complementary Problem (LCP) Solvers as a method for implementing real-time physics for games. This chapter explains principles and algorithms with practical examples and reasoning. When first investigating and writing a solver, one can easily become overwhelmed by the number of different methods and lack of implementation details, so this chapter will demonstrate the various methods from a practical point of view rather than a theoretical one; using code samples and real test cases to help understanding.
TopIntroduction
With the ever-increasing visual realism in today’s computer-generated scenes, it should come as no shock that people also expect the scene to move and react no less realistically. With the computational power available today, the ability to run physically accurate real-time simulations is required to hold a players attention.
Simulating scenes, using physics-based methods, is important because it enables us to produce environments that respond to unpredictable actions and simulate situations that are indistinguishable from real life, e.g. buildings collapsing. However, it is very difficult to simulate reliably, large number of objects and complex articulated structures as shown in Figure 1.
Figure 1. Simulation screenshots demonstrate stable stacking (left), articulated joints for characters (middle) and chains of objects (right)
Writing a flexible, scalable rigid body simulator is a challenging task because you need strong background knowledge in programming and Newtonian mechanics. While there are several approaches (i.e. penalty methods, impulse methods), solvers offer numerous advantages, such as requiring less user tuning and the ability to handle highly coupled configurations (e.g. large stacks or chains).
The reader, after being introduced to how solvers operate and how they are constructed, is introduced to dependent techniques; such as sparse matrices. And while we try and explain everything from the bottom-up, it is still required that the reader is at least familiar with basic Newton’s laws and calculus techniques. After completing this chapter, the reader should have a basic understanding of what a solver is, how to implement one, and how to use it.
TopBackground
Rigid Body Dynamics
Rigid body dynamics is a well understood and documented field, and as such, will not be covered here. For background information, we recommend reading (Baraff, 1999; Eberly, 2004; Hecker, 1998), which gives details on unconstrained dynamics and concepts such as body mass, acceleration, velocity and the equations of motion, which we use throughout this chapter.
While we introduce the reader to writing a practical LCP solver, there are also commercial and open source engines, which can be taken advantage of, and we would recommend them for the purposes of background knowledge. Some well-known LCP simulation engines are:
- •
Open Dynamics Engine (ODE), (Smith, 2004)
- •
PhysX (NVIDIA, 2011)
- •
Newton Game Dynamics (Jerez & Suero, 2003)
- •
Havok (Havok, 1998)
- •
Crisis Physics Engine (Vondrak, 2006).