Computer Graphics II

Time Integration(update) Methods

Time integration methods

Mankyu Sung 1
Computer Graphics II

Various Time Integration Methods

 Euler method
 Midpoint method
 Semi-implicit method (We are going to use this method)
 Verlet method
 Runge-kutta method

Mankyu Sung 2
Computer Graphics II

Simple Time Integration Method

 𝐹𝑂𝑅𝐶𝐸 = 𝑀𝐴𝑆𝑆 × 𝐴𝐶𝐶𝐸𝐿𝐸𝑅𝐴𝑇𝐼𝑂𝑁
The acc. at p0 at
𝐹 𝑝𝑜 , 𝑡 = 𝑚 ∗ 𝑎(𝑝𝑜 , 𝑡) time t

The Force at p0 at
time t
𝑣ሶ 𝑡 = 𝑎(𝑡) , 𝑝𝑜ሶ 𝑡 = 𝑣(𝑡)

𝐹 𝑝𝑜 , 𝑡 = 𝑚 ∗ 𝑝𝑜ሷ (𝑡)
 Above equation is differential equation (2nd differential equation)
 Hard to get the solution->We must estimate it !

Mankyu Sung 3
Computer Graphics II

Taylor series
∆𝑡 2 ∆𝑡 𝑛 𝑛
𝑝𝑜 𝑡 + ∆𝑡 = 𝑝𝑜 𝑡 + ∆t ∗ 𝑝𝑜ሶ 𝑡 + 𝑝0ሷ 𝑡 + ⋯ + 𝑝𝑜 𝑡
2 𝑛!

 Since it goes to infinite, we estimate it with the first and second term
only
 if ∆𝑡 is really small…
𝑝𝑜 𝑡 + ∆𝑡 ≈ 𝑝𝑜 𝑡 + ∆t ∗ 𝑝𝑜ሶ 𝑡
 Let’s split above formula into two terms.. 𝐹(𝑡)
𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡 = 𝑣 𝑡 + ∆𝑡
𝑚
𝑝𝑜 (𝑡 + ∆𝑡) = 𝑝𝑜 (𝑡) + 𝑣(𝑡)∆𝑡
Mankyu Sung 4
Computer Graphics II

Euler Method
 The simplest method

𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡 : Update of Velocity

𝑝𝑜 (𝑡 + ∆𝑡) = 𝑝𝑜 (𝑡) + 𝑣(𝑡)∆𝑡 : Update of Position with

Old velocity

Mankyu Sung 5
Computer Graphics II

Euler Method
 if velocity is constant during ∆𝑡..
 1. Using net force, calculate acceleration

𝑎 𝑡 = 𝐹(𝑡)/𝑚
 2. calculate velocity with the acceleration

𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡
 3. calculate position with the velocity

𝑝𝑜 𝑡 + ∆𝑡 = 𝑝𝑜 𝑡 + 𝑣(𝑡)∆𝑡

Mankyu Sung 6
Computer Graphics II

Problem of Euler method : Circular motion Error gets bigger

𝑥2 𝑥1
 The ∆𝑡 must be very small for accuracy errors
 However, if ∆𝑡 is too small, then no guarantee of real-time ∆𝑡
𝑥0
1st order derivate
truth : tangent

Euler method

 Problem is once an error occurs, it accumulate at next time frame

Mankyu Sung 7
Computer Graphics II

Mid point method

∆𝑡 ∆𝑡
 Estimating tangent in Half-step: 𝑣 𝑡 + = 𝑣 𝑡 + 𝑎(𝑡, 𝑣)
2 2
 Full step:
∆𝑡 ∆𝑡
𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 + , 𝑣(𝑡 + ) ∆t
2 2

𝑥′1 𝑥1/2
 Compute position similarly with 𝑣
𝑥1
𝑥0

Mankyu Sung 8
Computer Graphics II

Semi-Implicit method (a.k.a Backward Euler method)

 Most of Physics Engine use this method
 Simple to implement

𝑎 𝑡 = 𝐹(𝑡)/𝑚 𝑎 𝑡 = 𝐹(𝑡)/𝑚

𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡 𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡

𝑝𝑜 𝑡 + ∆𝑡 = 𝑝𝑜 𝑡 + 𝑣(𝑡)∆𝑡 𝑝𝑜 𝑡 + ∆𝑡 = 𝑝𝑜 𝑡 + 𝑣(𝑡 + ∆𝑡)∆𝑡

Euler method Semi-implicit method

 Does not guarantee more accuracy than Euler Method but more stable

Mankyu Sung 9
Computer Graphics II

Verlet Integration method

 Does not maintain current velocity, instead, estimate position from
acceleration directly

𝑣 𝑡 + ∆𝑡 = 𝑣 𝑡 + 𝑎 𝑡 ∆𝑡
𝑝𝑜 𝑡 + ∆𝑡 = 2𝑝𝑜 𝑡 − 𝑝𝑜 𝑡 − ∆𝑡 + 𝑎(𝑡)∆𝑡 2
𝑝𝑜 𝑡 + ∆𝑡 = 𝑝𝑜 𝑡 + 𝑣(𝑡)∆𝑡
No velocity!

Euler method Verlet integration method

 Accurate and stable

 Problem : What do we do at time = 0 ?

Mankyu Sung 10
Computer Graphics II

RK (Runge-Kutta method)
 4th derivative
 Most accurate but takes time to compute

 Googling for more information

Mankyu Sung 11
Computer Graphics II

Integrator of Cyclone 𝑝′ : Position at the next frame

 Two parts 𝑝ሶ :1st derivate of position with respect
𝑡2 to time (velocity)
 Position update 𝑝′ = 𝑝 + 𝑝𝑡ሶ + 𝑝ሷ
2 Since this value is quite
small, just ignore it
𝑝′ = 𝑝 + 𝑝𝑡ሶ

 Velocity update 𝑝ሶ ′ = 𝑝ሶ + 𝑝𝑡ሷ

𝑝ሶ ′ = 𝑝𝑑
ሶ + 𝑝𝑡ሷ Add Damping d

𝑝ሶ ′ = 𝑝𝑑
ሶ 𝑡 + 𝑝𝑡ሷ Since Damping depends on
time interval
 Requites Time interval (for example Δt=0.033)

Mankyu Sung 12
 Computer Graphics II

class Particle void setInverseMass(const real inverseMass);

{ real getInverseMass() const;
public: bool hasFiniteMass() const;
void setDamping(const real damping);
protected: real getDamping() const;
real inverseMass; void setPosition(const Vector3 &position);
real damping; void setPosition(const real x, const real y, const real z);
Vector3 position; void getPosition(Vector3 *position) const;
Vector3 velocity; vector3 getPosition() const;
Vector3 forceAccum; void setVelocity(const Vector3 &velocity);
Vector3 acceleration; void setVelocity(const real x, const real y, const real z);
public: void getVelocity(Vector3 *velocity) const;
void integration(real duration); vector3 getVelocity() const;
void setMass(real m); void setAcceleration(const Vector3 &acceleration);
real getMass(); void setAcceleration(const real x, const real y, const real z);
void getAcceleration(Vector3 *acceleration) const;
vector3 getAcceleration() const;
void clearAccumulator();
void addForce(const Vector3 &force);

Mankyu Sung 13
Computer Graphics II

Original Euler Integration

void Particle::integrate(real duration)

{
// We don't integrate things with zero mass.
if (inverseMass <= 0.0f) return;
assert(duration > 0.0);
// Update linear position.
position.addScaledVector(velocity, duration); //pos = pos + vel*duration
// Work out the acceleration from the force
Vector3 resultingAcc = acceleration; //acc = acc + force * 1/ mass
resultingAcc.addScaledVector(forceAccum, inverseMass);
// Update linear velocity from the acceleration.
velocity.addScaledVector(resultingAcc, duration); //vel = vel + acc*duration
// Impose drag.
velocity *= real_pow(damping, duration); //vel = vel * damping
// Clear the forces.
clearAccumulator(); //force = 0
}

Mankyu Sung 14
Computer Graphics II

Semi-implicit Method

void Particle::integrate(real duration)

{
// We don't integrate things with zero mass.
if (inverseMass <= 0.0f) return;
assert(duration > 0.0);
// Work out the acceleration from the force
Vector3 resultingAcc = acceleration; //acc = acc + force * 1/ mass
resultingAcc.addScaledVector(forceAccum, inverseMass);
// Update linear velocity from the acceleration.
velocity.addScaledVector(resultingAcc, duration); //vel = vel + acc*duration
// Impose drag.
velocity *= real_pow(damping, duration); //vel = vel * damping

// Update linear position.

position.addScaledVector(velocity, duration); //pos = pos + vel*duration

// Clear the forces. Use the velocity at next frame

clearAccumulator(); //force = 0
}
Mankyu Sung 15
Computer Graphics II

Simulation Framework
Let’s simulate a object…

Mankyu Sung 16
Computer Graphics II

Required Libraries
 FLTK(Fast Light Tool kit) - https://www.fltk.org/
 Window Creation, Event handling (similar to glfw)
 MS Windows static libraries are going to be provided
 For Linux users, please build it up by yourself
 OpenGL Classic
 FreeGLUT (https://freeglut.sourceforge.net/)
 Never use Shader programming
 CPU only

Mankyu Sung 17
Computer Graphics II

Physics Framework

Rendering : OpenGL classic

UI : FLTK(FastLight ToolKit)
OS : windows 7/10
Integrated with Cyclone

Mankyu Sung 18
 Computer Graphics II

MyGlWindow Class object

{
draw()
public:
{
void draw(int shadow)
///
{
//draw shadow
setupShadows();
if (shadow)
object->draw(1);
glColor3f(0.1f, 0.1f, 0.1f);
unsetupShadows();
else
glColor3f(1.0f, 0.0f, 0.0f);
glEnable(GL_LIGHTING);
//draw objects
//draw something
glPushMatrix();
object->draw(0);
}
glPopMatrix();
}
}

Mankyu Sung 19
Computer Graphics II

MyGlWindow
 void update()
 This function is called 60 times in a second(controllable)

 Void test()
 This function is called whenever you press the button

Mankyu Sung 20
 Computer Graphics II

Coordinate system saving/restoring

 Whenever you wants to transform a object, save the current coordinate system. When you
done, restore it
 glPushMatrix()
 Save current coordinate system
 glPopMatrix()
 Restore old coordinate system
 They have a stack structure inside

 glTranslatef(x,y,z) : Translate to (x,y,z)

 glRotatef(deg, x,y,z) : Rotate deg with x,y,z rotation axis
 glScalef(x,y,z) : scale it with x, y, z

Mankyu Sung 21
Computer Graphics II

Example
 Ball Drawing
 glutSolidSphere(size, 30, 30);
 Size : ball size
 30, 30 : # of subdivision on x and y axis (Higher the values is, More detail)
 Translate a Ball and draw it.

Vector3 position;
float size = 2.0;
glPushMatrix(); //save current coord system
glTranslatd(position.x, position.y, position.z);
glutSolidSphere(size, 30, 30); //size = 2.0
glPopMatrix(); //restore the coord system

Mankyu Sung 22
Computer Graphics II

Draw a ball at (0,3,0)

Mankyu Sung 23
Computer Graphics II

https://padlet.com/mksung89/mover

Mankyu Sung 24
Computer Graphics II

Mover class

class Mover
{
public:
Mover();
~Mover();

cyclone::Vector3 m_position;

void update();
void stop();
void draw(int shadow);
};

Mankyu Sung 25
Computer Graphics II

How to get Δt
 1. Add timing.h
 2. TimingData::init() //Reset timer(Probably at the constructor)
 3. TimingData::get().update(); //Update the timer
 4. Δt = (float)TimingData::get().lastFrameDuration * 0.003; //

Mankyu Sung 26
Computer Graphics II

Next : bouncing ball Simulating with Cyclone

Mankyu Sung 27