Time Integration

The simulation techniques to produce physically based deformations are often force based.

Internal and external forces are accumulated from which accelerations are computed based on Newton’s second law of motion (Eq.3.3). A set of ordinary or partial differential equations defines the force fields applied to the different elements that represent the system. Then, a numerical integration scheme is employed to integrate the acceleration, in order to obtain the velocity and then the position of the element in a given time step.

F=ma (3.3)

whereF=P

j=1F_jis the internal and external forces vector.Facts to push and pull an object around in space. Theain this equation expresses the acceleration vector (a=_m^F), andmis the mass of the object, which is constant.

42

3.3. PHYSICS-BASED DEFORMATION

Given the positionsx_i(t) and velocitiesv_i(t) of a point at timet, new positionsx_i(t+h) and new velocitiesv_i(t+h) need to be determined for the next time step of the simulation t+h, according to the equation of motion (Eq.3.3). For this, we first transform (Eq.3.4) into a first order differential equation (Eq.3.5):

F_external=M∂²x whereDis the damping matrix that represents viscous damping applied to each element in the system, andMthe mass matrix.

Solving Eq. 3.5can be done using a numerical integration method. Traditionally, nu-merical integration schemes can be divided into three general categories: explicit (for-ward) Euler integration (Section 3.3.1.1), implicit (backward) Euler integration (Section 3.3.1.2) and Verlet integration (Section 3.3.1.3). Therefore, these numerical integration methods deal with how to advance a simulation from one time step to the next step. In the following, we provide a short review of these methods, explaining their differences and drawbacks.

3.3.1.1 Forward Euler Integration

The simplest method of numerical integration is the explicit (forward) Euler scheme, which uses the positions, velocities, and external forces at the current time step to compute the corresponding values of the following step. The explicit Euler scheme is given by the following update rules:

v_t+h=v_t+ha_t (3.6)

x_t+h=x_t+hv_t (3.7)

This scheme guarantees first order precision of the computed positions and velocities.

We are treatinghas a time step and it is sufficiently small, where hcontrols stability and speed of the computation.vis the velocity vector,xis the position vector, and tis a specific time during the simulation. A solution obtained using explicit Euler scheme is quite unstable, suffers of overshooting problems and exhibits inferior accuracy. The smaller the time step, the higher the stability, and vice versa. The major drawback of this scheme is that the resultant deformation tends to vibrate and even explode, when time steps are too large.

CHAPTER 3. LAYERED SKIN DEFORMATION

3.3.1.2 Backward Euler Integration

In contrast to the explicit Euler scheme, the implicit (backward) Euler scheme assumes for the solution of the next simulation state that future variables are known. In other words, with the backward Euler scheme, we update the current position, not with the current velocity and acceleration but with the resulting velocity and acceleration. The problem with this approach is that the velocities and accelerations of the next time step are unknown. We need to solve for them, which can be done by treating implicit Euler integration as a linear equation and solve for it. However, the resulting set of equations can be large, which makes solving them each time step is computationally more expensive than the explicit method. An alternative solution is to use an explicit Euler scheme and then use the result to compute the implicit integration. This is known as a predictor-corrector method, since we predict a solution using the explicit Euler equation and then correct for errors using the implicit scheme.

The simplest implicit integration scheme is given by the following update rules:

v_t+h=v_t+hF_external−dv_t+h/dt

m (3.8)

x_t+h=x_t+hv_t+h (3.9)

Although implicit methods are computationally expensive, they have the advantage of stability and are useful for large particle systems.

3.3.1.3 Verlet Integration

Verlet integration [Verlet, 1968] is a velocity-less integration scheme, which is frequently used in video games, mainly due to [Jakobsen, 2001] (Jakobsen is the first to employ Verlet integration in games). He developed the PhysX engine of a popular game called

“Hitman: Codename 47", where he employed the Verlet scheme to simulate rag dolls, cloth and plants. The Verlet integration method works by using the current and previous position to create the velocity, instead of using the exact velocity (Eq. 3.10). In this formulation, the velocity term disappears and the position at the next time stepx_t+h depends only on the current forces applied to the point, current position and position at the previous time step. However, because the velocity is now given only implicitly by using the previous position, the time step need to be kept constant between each call to the numerical integrator.

x_t+h=2x_t−x_t−h+a_th² (3.10) 44

3.3. PHYSICS-BASED DEFORMATION

Verlet integration offers stability as well as other properties that are important in physical systems, such as time-reversibility, area preserving properties, and conservation of the energy of the system. In addition, Verlet integration is easy to implement. Simple pseudo-code is presented in Alg. 3. While standard Verlet integration is unconditionally stable, it does not incorporate velocity, which makes it difficult to use with velocity dependent forces.

Algorithm 3:Verlet integration pseudo-code

Input :DoubletimeStep,VectorpreviousPositions,VectorcurrentPositions, VectorcurrentAccelerations

5: currentPositions= 1.99·currentP ositions−0.99·previousP ositions+ currentA ccel erations·timeSte p·timeSte p

6: // The two factors 1.99 and 0.99 are included

7: //, in order to introduce a small amount of drag in the system

8: previousPositions=oldPositions

9: end while