1 of 78

Simulation, Kinematics, Animation

Computer Graphics and Imaging

UC Berkeley CS 184/284A

Discussion 13

2 of 78

Week 12 Announcements

  • Homework 4 is due Friday, November 27th
  • Project proposal now due tonight, Thursday, 11:59pm

Worksheet

3 of 78

Physical simulation

  • We have a physical basis for the motion of single particles: gravity, friction, springs, etc.

4 of 78

Physical simulation

  • We have a physical basis for the motion of single particles: gravity, friction, springs, etc.
  • How can we simulate this behavior on our laptop within reasonable compute limits?

5 of 78

Euler’s method

  • Problem: consider a system defined by a differential equation��
  • To simulate the system, we want to estimate .

6 of 78

Euler’s method

  • Problem: consider a system defined by a differential equation��
  • To simulate the system, we want to estimate .
  • Discretize over time intervals ! Let be velocity, acceleration.

7 of 78

Euler’s method

  • Problem: consider a system defined by a differential equation��
  • To simulate the system, we want to estimate .
  • Discretize over time intervals ! Let be velocity, acceleration.

8 of 78

​

9 of 78

Explicit Euler’s Method

position

velocity

acceleration

10 of 78

Newton’s Second Law of Motion

11 of 78

Question 1

12 of 78

Question 1.1

13 of 78

Question 1.1 Answer

14 of 78

Example:

15 of 78

Example:

16 of 78

Not physically possible! (?) (pendulum cannot swing past θ0 = 0.1 rad)

17 of 78

  • Problem with Euler’s method: Errors accumulate! Need very small step size (more steps) to achieve low approximation error.

Not physically possible! (?) (pendulum cannot swing past θ0 = 0.1 rad)

18 of 78

Not physically possible! (?) (pendulum cannot swing past θ0 = 0.1 rad)

  • Problem with Euler’s method: Errors accumulate! Need very small step size (more steps) to achieve low approximation error.
  • See parts 4 and 5 for more detail — turns out Euler’s method is never numerically stable for this setting.

19 of 78

Hint:

20 of 78

21 of 78

22 of 78

23 of 78

θ

24 of 78

Modifications to Euler’s Method

25 of 78

Modifications to Euler’s Method

Explicit Euler’s method can be unstable, since errors accumulate. Some modifications to explicit Euler’s method include:

  1. Implicit Euler’s method (AKA backward Euler’s method).
  2. Modified Euler’s method.
  3. Verlet integration.

26 of 78

Modifications to Euler’s Method

  1. Implicit Euler’s method (AKA backward Euler’s method).

​

  1. Modified Euler’s method.

​

  1. Verlet integration.

Normal for comparison

27 of 78

Modifications to Euler’s Method

  1. Implicit Euler’s method (AKA backward Euler’s method).
  2. More stable than explicit Euler, better for stiff systems
  3. Requires solving non-linear equations (and more complex)
  4. Uses velocity at next time step
  5. Modified Euler’s method.
  6. More stable than explicit Euler, better for stiff systems
  7. Average velocities at start and endpoint
  8. Verlet integration.
  9. Doesn’t require velocity (position-based)
  10. Not physically based, dissipates energy (error)

28 of 78

Hooke’s Law

  • Recall that Hooke’s Law is used to calculate the force acting on a particle due to a spring.

💡 Remember that acceleration is the double derivative! Therefore, acceleration = Force/mass

29 of 78

Question 2

30 of 78

Q2 Multitudes of Euler’s Methods

31 of 78

Q2.1 Multitudes of Euler’s Methods

32 of 78

Q2.1 Multitudes of Euler’s Methods

33 of 78

Q2.1 Multitudes of Euler’s Methods

x1 = x0 + Δtx0 = (0, 1) + (-1, 0) = (-1, 1)

x1 = x0 + Δtx0 = (-1, 0) + (0, 0) = (-1, 0)

x1 = ?

Hint! 💡 F = ma so a = Force/mass

34 of 78

Modeling the Problem with a Spring System

At t=1, we want to solve for position and velocity using Euler’s, and acceleration via the spring equation

34

b

a

35 of 78

Q2.1 Multitudes of Euler’s Methods

Hooke’s Law

36 of 78

Q2.1 Multitudes of Euler’s Methods

Why unneeded? Since we only care about x3 (which doesn’t depend on x2).

37 of 78

Q2.1 Multitudes of Euler’s Methods

38 of 78

Q2.1 Multitudes of Euler’s Methods

39 of 78

Q2.2 Multitudes of Euler’s Methods

40 of 78

Q2.2 Multitudes of Euler’s Methods

41 of 78

Q2.3 Multitudes of Euler’s Methods

42 of 78

Q2.3 Multitudes of Euler’s Methods

43 of 78

Q2.4 Multitudes of Euler’s Methods

44 of 78

Q2.4 Multitudes of Euler’s Methods

45 of 78

Q2.5 Multitudes of Euler’s Methods

46 of 78

Q2.5 Multitudes of Euler’s Methods

47 of 78

47

Q3:

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(a) Give some pros and cons of using the explicit Euler method.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

48 of 78

48

Q3:

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(a) Give some pros and cons of using the explicit Euler method.

Pros - simple and easy to compute, we don’t always care about precision in graphics (i.e. close enough is good enough).

Cons - inaccurate and unstable, which frequently leads to divergent results, especially as time progresses and errors accumulate.

​

​

​

​

49 of 78

49

Q3:

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

50 of 78

50

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

51 of 78

51

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

52 of 78

52

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

53 of 78

53

Recall the forward, or explicit Euler method, which uses the following update rules:

​

where respectively denote the position, velocity, and acceleration at time t.

(b) Say we have a particle with mass 1 starting at position with an initial velocity and no initial acceleration. The particle is at one end of a spring, whose other end is the origin (0, 0), and whose spring constant is k = 1 and rest length is 1. Calculate particle’s position at t = 3 using the explicit Euler method with timestep .

54 of 78

Animation & Inverse Kinematics

55 of 78

Question 3

56 of 78

57 of 78

58 of 78

= (a, b)

a = x cosθ

b = x sinθ

59 of 78

60 of 78

a

b

61 of 78

62 of 78

63 of 78

64 of 78

65 of 78

66 of 78

67 of 78

68 of 78

69 of 78

70 of 78

Let’s Take Attendance.

  • Be sure to select Week 12 and input your TA’s secret word 😉
  • Any feedback? Let us know!

71 of 78

71

Q1:

What are keyframes and what do we do with them?

​

​

​

72 of 78

72

Q1:

What are keyframes and what do we do with them?

Important moments in some transition/motion, usually starting and ending points. We interpolate between them (though not linearly, usually too complex) to create frames between the keyframes to form fluid video - known as tweening.

​

​

​

73 of 78

73

Q2.1:

What is the difference between forward and inverse kinematics?

​

​

​

​

74 of 78

74

Q2.1:

What is the difference between forward and inverse kinematics?

Forward - we provide angles (e.g. for joints), computer determines final position (e.g. of end of limbs).

Inverse - we provide ending position, need to compute the joint angles to reach the position.

​

​

​

​

​

75 of 78

75

Q2.2:

What are some problems associated with inverse kinematics?

​

​

​

​

​

76 of 78

76

Q2.2:

What are some problems associated with inverse kinematics?

Sometimes has multiple possible solutions (sometimes connected to each other, sometimes separate), sometimes has no solutions, want to make sure solution found is realistic, etc.

​

​

​

​

​

77 of 78

https://github.com/cal-cs184/rope_simulation

​

This is a smaller, toy version of Project 4 to get intuition about simulation

78 of 78