**Numerical Time Integration**

**Wanho Choi**

**(wanochoi.com)**

**가속도**

**(acceleration)**

**속도**

**(velocity)**

**위치**

**(position)**

시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
**Mathematics**

**v(t)**

**v(t)**

**= !p(t)**

**= !p(t)**

**a(t)**

**a(t)**

**= !v(t) = !!p(t)**

시간(t)에 대한 미분
(differentiation)
**= !v(t) = !!p(t)**

**가속도**

**(acceleration)**

**속도**

**(velocity)**

**위치**

**(position)**

시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
**가속도**

**(acceleration)**

**속도**

**(velocity)**

**위치**

**(position)**

시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
시간(t)에 대한 적분
(integration)
시간(t)에 대한 미분
(differentiation)
**Discretization**

**v(t)**

**v(t)**

**= !p(t)**

**= !p(t)**

**a(t)**

**a(t)**

**= !v(t) = !!p(t)**

시간(t)에 대한 미분
(differentiation)
**= !v(t) = !!p(t)**

**v(t**

**v(t**

**+ Δt) = v(t) + Δt ⋅a(t)**

**+ Δt) = v(t) + Δt ⋅a(t)**

**p(t**

**p(t**

**+ Δt) = p(t) + Δt ⋅v(t)**

시간(t)에 대한 적분
(integration)
**+ Δt) = p(t) + Δt ⋅v(t)**

**Is it difficult?**

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

2. rectilinear motion

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

2. rectilinear motion

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

2. rectilinear motion

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

2. rectilinear motion

**x(t**

**x(t**

### +1) = 140 = 10 +1×130

_{from the rate of change of it! }We can get the next position**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t)**

**+ Δt) = x(t) + Δt ⋅v(t)**

_{v(t)}

_{v(t)}### =

**x(t**

**x(t**

**+ Δt) − x(t)**

**+ Δt) − x(t)**

**What is the answer?**

**v(t)**

**v(t)**

### = 130

**x(t)**

**x(t)**

### = 10

**x(t**

**x(t**

### +1) = ?

*t : the current time (hour)*

**x(t) : the current position (km)****v(t) : the current speed (km/h)**

assumption) 1. constant speed

2. rectilinear motion

**x(t**

**x(t**

### +1) = 140 = 10 +1×130

_{from the rate of change of it! }We can get the next position**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t)**

**+ Δt) = x(t) + Δt ⋅v(t)**

**적분**

**(integration)**

**미분**

**(differentiation)**

**v(t)**

**v(t)**

### =

**x(t**

**x(t**

**+ Δt) − x(t)**

**+ Δt) − x(t)**

*Δt*

**Taylor’s Expansion (Taylor Series)**

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

*t*

2
### 2

**⋅!!x(t) + Δ**

**⋅!!x(t) + Δ**

*t*

3
### 2

**⋅!!!x(t) +!**

**⋅!!!x(t) +!**

**What is the meaning of it?**

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

*t*

2
### 2

**⋅!!x(t) + Δ**

**⋅!!x(t) + Δ**

*t*

3
### 2

**⋅!!!x(t) +!**

**⋅!!!x(t) +!**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

!
**x(t)**

**path**

**tangent vector:**

**!x(t)**

**!x(t)**

**Approximation**

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

*t*

2
### 2

**⋅!!x(t) + Δ**

**⋅!!x(t) + Δ**

*t*

3
### 2

**⋅!!!x(t) +!**

**⋅!!!x(t) +!**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

_{x(t}

_{x(t}*+ Δt)*

**path**

**Numerical Integration: Euler Method**

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

**+ Δt) = x(t) + Δt ⋅ !x(t) + Δ**

*t*

2
### 2

**⋅!!x(t) + Δ**

**⋅!!x(t) + Δ**

*t*

3
### 2

**⋅!!!x(t) +!**

**⋅!!!x(t) +!**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅ !x(t)**

**+ Δt) = x(t) + Δt ⋅ !x(t)**

**= x(t) + Δt ⋅v(t)**

**= x(t) + Δt ⋅v(t)**

*numerical error*

**x(t**

**x(t**

*+ Δt)*

**path**

**It differs from the analytic solutions.**

**v(t)**

**v(t)**

**= v(0) + t ⋅a**

**= v(0) + t ⋅a**

**p(t)**

**p(t)**

**= p(0) + t ⋅v(0) +**

**= p(0) + t ⋅v(0) +**

*t*

2

### 2

**⋅a**

**Mass-Spring-Damper System**

**01_FreeFall**

*m*

*m*

**⋅g**

*m*

**⋅!!x(t)**

**⋅!!x(t)**

**v(t**

**+ Δt) = v(t) + Δt ⋅g**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t)***m*⋅

**v(t**

**+ Δt) − v(t)***Δt*

**= m ⋅g****01_FreeFall**

**The velocity increases more gradually as it falls downward.**
**So, the every interval of time is increasing.**

**02_MassSpring_ForwardEuler**

*m*

*m*

**⋅g**

*m*

**⋅!!x(t)**

**⋅!!x(t)**

*k*

**⋅x(t)**

**⋅x(t)**

**v(t**

**+ Δt) = v(t) + Δt ⋅g − Δ**t*⋅ k*

*m*

**⋅x(t)**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t)***m*⋅

**v(t**

**+ Δt) − v(t)***Δt*

**= m ⋅g − k ⋅x(t)****02_MassSpring_ForwardEuler**

**03_MassSpringDamper_ForwardEuler**

*m*

*m*

**⋅g**

*m*

**⋅!!x(t)**

**⋅!!x(t)**

*k*

**⋅x(t)**

**⋅x(t)**

*c*

**⋅v(t)**

**⋅v(t)**

**v(t**

**+ Δt) = v(t) + Δt ⋅g − Δ**t*⋅ k*

*m*

**⋅x(t) − Δ***t*

*⋅c*

*m*

**⋅v(t)**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t)***m*⋅

**v(t**

**+ Δt) − v(t)***Δt*

**= m ⋅g − k ⋅x(t) − c⋅v(t)****03_MassSpringDamper_ForwardEuler**

**It oscillates stably.**

**Backward Euler Time Integration**

**Backward Euler Time Integration**

**Backward Euler Time Integration**

**Backward Euler Time Integration**

*m !!x(t)*

**= f (t) = f (x(t),v(t)) = mg − kx(t) − cv(t)**

**Δx ≡ x(t + Δt) − x(t)****Backward Euler Time Integration**

*m*

**!!x(t)**

**= f (t) = f (x(t),v(t)) = mg − kx(t) − cv(t)**

**Δx = Δt ⋅v(t)****Δv = Δ**

*t*

*m*

**⋅ f(t)**

**Δx = Δt ⋅v(t + Δt)****Δv = Δ**

*t*

*m*

**⋅ f(t + Δt)****explicit Euler**

**(forward Euler)**

**implicit Euler**

**(backward Euler)**

**conditionally stable** **unconditionally stable**
**but, unknowns: ****f(t***+ Δt)*
**vs**

**Δx ≡ x(t + Δt) − x(t)****Δv ≡ v(t + Δt) − v(t)**

**Explicit vs Implicit**

### To generate an animation of an object, it needs to

### compute the location of it for a series of time steps.

**• Explicit time integration: The positions of the nodes **

### in the next time step are computed only using past

### information.

**• Implicit time integration: The positions, velocities, **

### and accelerations in the next time step are computed

### simultaneously. This requires predicting the internal

### forces at the next time step.

**Backward Euler Time Integration**

**Δv = Δ***t*

**Backward Euler Time Integration**

**Δv = Δ***t*

*m* **⋅ f(t + Δt) = Δ***t*

**Backward Euler Time Integration**

**Δv = Δ**

*t*

*m*

*= Δ*

**⋅ f(t + Δt)***t*

*m*

**⋅ f(t) + Δx ⋅ ∂**

**f(t)****∂x**

**+ Δv ⋅ ∂**

**f(t)****∂v**⎛ ⎝⎜ ⎞⎠⎟

### (

∵Taylor's expansion### )

= Δ*t*

*m*

**⋅ f x(t + Δt),v(t + Δt)**### (

### )

**Backward Euler Time Integration**

**Δv = Δ**

*t*

*m*

*= Δ*

**⋅ f(t + Δt)***t*

*m*

**⋅ f(t) + Δx ⋅ ∂**

**f(t)****∂x**

**+ Δv ⋅ ∂**

**f(t)****∂v**⎛ ⎝⎜ ⎞⎠⎟ = Δ

*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c**### (

### )

∵Taylor's expansion### (

### )

**∵∂f / ∂x = −k,∂f / ∂v = −c**### (

### )

= Δ*t*

*m*

**⋅ f x(t + Δt),v(t + Δt)**### (

### )

**∵f = mg − cv − kx**### (

### )

**Backward Euler Time Integration**

**Δv = Δ**

*t*

*m*

**⋅ f(t + Δt)**

**∵Δx = Δt ⋅v(t + Δt) = Δt ⋅ v(t) + Δv**### (

### )

### (

### )

= Δ*t*

*m*

**⋅ f(t) + Δx ⋅ ∂**

**f(t)****∂x**

**+ Δv ⋅ ∂**

**f(t)****∂v**⎛ ⎝⎜ ⎞⎠⎟ = Δ

*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c**### (

### )

∵Taylor's expansion### (

### )

**∵∂f / ∂x = −k,∂f / ∂v = −c**### (

### )

= Δ*t*

*m*

**⋅ f x(t + Δt),v(t + Δt)**### (

### )

**∵f = mg − cv − kx**### (

### )

= Δ*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ v(t) + Δv**### (

### (

### )

**⋅ k − Δv ⋅c**### )

**Backward Euler Time Integration**

**Δv = Δ**

*t*

*m*

**⋅ f(t + Δt)**

**∵Δx = Δt ⋅v(t + Δt) = Δt ⋅ v(t) + Δv**### (

### )

### (

### )

= Δ*t*

*m*

**⋅ f(t) + Δx ⋅ ∂**

**f(t)****∂x**

**+ Δv ⋅ ∂**

**f(t)****∂v**⎛ ⎝⎜ ⎞⎠⎟ = Δ

*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c**### (

### )

∵Taylor's expansion### (

### )

**∵∂f / ∂x = −k,∂f / ∂v = −c**### (

### )

= Δ*t*

*m*

**⋅ f x(t + Δt),v(t + Δt)**### (

### )

**∵f = mg − cv − kx**### (

### )

= Δ*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ v(t) + Δv**### (

### (

### )

**⋅ k − Δv ⋅c**### )

= Δ*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t) − Δt ⋅ k ⋅ Δv − Δv ⋅c**### (

### )

**Backward Euler Time Integration**

**Δv = Δ**

*t*

*m*

**⋅ f(t + Δt)**

**∵Δx = Δt ⋅v(t + Δt) = Δt ⋅ v(t) + Δv**### (

### )

### (

### )

= Δ*t*

*m*

**⋅ f(t) + Δx ⋅ ∂**

**f(t)****∂x**

**+ Δv ⋅ ∂**

**f(t)****∂v**⎛ ⎝⎜ ⎞⎠⎟ = Δ

*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c**### (

### )

∵Taylor's expansion### (

### )

**∵∂f / ∂x = −k,∂f / ∂v = −c**### (

### )

= Δ*t*

*m*

**⋅ f x(t + Δt),v(t + Δt)**### (

### )

**∵f = mg − cv − kx**### (

### )

= Δ*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ v(t) + Δv**### (

### (

### )

**⋅ k − Δv ⋅c**### )

= Δ*t*

*m*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t) − Δt ⋅ k ⋅ Δv − Δv ⋅c**### (

### )

**∴Δv =**

*Δt*

*m*

*+ Δt*2

*⋅ k + Δt ⋅c*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)**### (

### )

**Backward Euler Time Integration**

**v(t**

**v(t**

**+ Δt) = v(t) +**

**+ Δt) = v(t) +**

*Δt*

*m*

*+ Δt*

2 *⋅ k + Δt ⋅c*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)**

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)**

### (

### )

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**energy loss**

**artificial damping**

**05_MassSpringDamper_BackwardEuler**

**v(t**

**v(t**

**+ Δt) = v(t) +**

**+ Δt) = v(t) +**

*Δt*

*m*

*+ Δt*

2 *⋅ k + Δt ⋅c*

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)**

**⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)**

### (

### )

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**energy loss**

**artificial damping**

**04_MassSpring_BackwardEuler**

**v(t**

**v(t**

**+ Δt) = v(t) +**

**+ Δt) = v(t) +**

*Δt*

*m*

*+ Δt*

2 *⋅ k*

**⋅ m ⋅g − kx(t) − Δt ⋅ k ⋅v(t)**

**⋅ m ⋅g − kx(t) − Δt ⋅ k ⋅v(t)**

### (

### )

**Comparison: 02 vs 04**

**We can use a large time step because it is unconditionally stable.**
**However, it has some artificial damping.**

**Ground Truth**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

!

**Explicit Time Integration**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

_{x(t}

_{x(t}*+ Δt)*

**More Stiff, Larger Error**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

_{x(t}

_{x(t}*+ Δt)*

_{x(t}

_{x(t}*+ Δt)*

*numerical error* *numerical error*

**path**

**Implicit Time Integration**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

**Implicit Time Integration**

**x(t**

**x(t**

*+ Δt)*

**x(t)**

**x(t)**

**x(t**

**x(t**

*+ Δt)*

*numerical error*

**path**

**Explicit vs Implicit**

**Both schemes have some numerical errors,**
**but explicit diverges and implicit converges!**

**explicit** **implicit**

**Summary**

### • Implicit time integration is slower than explicit

### one because a system of equations must be

### solved.

### • However, explicit time integration has

### numerous problems including instability at

### large time steps and slow propagation of the

### effects of forces over the object’s material.

**Summary**

**• Explicit time integration**

### • Too large time step: unstable

### • Too small time step: too slow

**• Implicit time integration**

**06_MassSpring_PBD**

**v(t**

**v(t**

**+ Δt) = v(t) + Δt ⋅ m ⋅g − kx(t)**

**+ Δt) = v(t) + Δt ⋅ m ⋅g − kx(t)**

### (

### )

**x(t**

**x(t**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**+ Δt) = x(t) + Δt ⋅v(t + Δt)**

**v(t**

**v(t**

*+ Δt) =*

**x(**

**Δt) − x(t)**

**Δt) − x(t)**