The Jello Cube Assignment 1, CSCI 520
Jernej Barbic, USC
1
The jello cube
Undeformed cube Deformed cube
• The jello cube is elastic,
• Can be bent, stretched, squeezed, …, • Without external forces, it eventually
restores to the original shape. 2
Mass-Spring System
• Several mass points
• Connected to each other by springs
• Springs expand and stretch, exerting force on the mass points
• Very often used to simulate cloth
• Examples:
A 2-particle spring system Another 2-particle example Cloth animation example
3
Newton’s Laws
• Newton’s 2nd law:
• Tells you how to compute acceleration, given the force and mass
• Newton’s 3rd law: If object A exerts a force F on object B, then object B is at the same time exerting force -F on A.
F = ma
−F F
4
Single spring
• Obeys the Hook’s law: F = k (x – x0)
• x0 = rest length
• k = spring elasticity
(aka stiffness)
• For x
5
Hook’s law in 3D
• Assume A and B two mass points connected with a spring.
• Let L be the vector pointing from B to A
• Let R be the spring rest length
• Then, the elastic force exerted on A is:
F=−kHook(|L|−R)
L |L|
6
Damping
• Springs are not completely elastic
• They absorb some of the energy and tend to decrease the velocity of the mass points attached to them
• Damping force depends on the velocity:
F = −kd v
• kd = damping coefficient
• kd different than kHook !!
7
Damping in 3D
• Assume A and B two mass points connected with a spring.
• Let L be the vector pointing from B to A
• Then, the damping force exerted on A is:
(v −v )⋅L L AB
F = −kd
|L| |L|
• Here vA and vB are velocities of points A and B
• Damping force always OPPOSES the motion
8
A network of springs
• Every mass point connected to some other points by springs
• Springs exert forces on mass points
– Hook’s force – Damping force
• Other forces
– External force field
» Gravity
» Electrical or magnetic force field – Collision force
9
How to organize the network (for jello cube)
• To obtain stability, must organize the network of springs in some clever way
• Jello cube is a 8x8x8 mass point network
• 512 discrete points
• Must somehow connect them with springs
Basic network Stable network Network out of control
10
Solution:
Structural, Shear and Bend Springs
• There will be three types of springs:
– Structural – Shear
– Bend
• Each has its own function
11
Structural springs
• Connect every node to its 6 direct neighbours
• Node (i,j,k) connected to
– (i+1,j,k), (i-1,j,k), (i,j-1,k), (i,j+1,k), (i,j,k-1), (i,j,k+1)
(for surface nodes, some of these neighbors might not exists)
• Structural springs establish the basic structure of the jello cube
• The picture shows structural springs for the jello cube. Only springs connecting two surface vertices are shown.
12
Shear springs
• Disallow excessive shearing
• Prevent the cube from distorting
• Every node (i,j,k) connected to its diagonal neighbors
• Structural springs = white
• Shear springs = red
Shear spring (red) resists stretching and thus prevents shearing
13
A 3D cube
(if you can’t see it immediately, keep trying)
Bend springs
• Prevent the cube from folding over
• Every node connected to its second neighbor in every direction
(6 connections per node, unless surface node)
• white=structural springs
• yellow=bend springs (shown for a single node only)
Bend spring (yellow) resists contracting and thus prevents bending
14
External force field
• If there is an external force field, add that force to the sum of all the forces on a mass point
• There is one such equation for every mass point and for every moment in time
F=F+F +F
total Hook damping force field
15
Collision detection
• The movement of the jello cube is limited to a bounding box
• Collision detection easy:
– Check all the vertices if any of them is outside the box
• Inclined plane:
– Equation:
F(x,y,z)=ax+by+cz+d =0
– Initially, all points on the same side of the plane
– F(x,y,z)>0 on one side of the plane and F(x,y,z)<0 on the other – Can check all the vertices for this condition
16
Collision response
• When collision happens, must perform some action to prevent the object penetrating even deeper
• Object should bounce away from the colliding object
• Some energy is usually lost during the collision
• Several ways to handle collision response
• We will use the penalty method
17
The penalty method
• When collision happens, put an artificial collision spring at the point of collision, which will push the object backwards and away
from the colliding object
• Collision springs have elasticity and damping, just like ordinary springs
Boundary of colliding object
F
v
Collision spring
18
Penalty force
• Direction is normal to the contact surface
• Magnitude is proportional to the amount of penetration
• Collision spring rest length is zero
Boundary of colliding object
F
Collision spring
19
Integrators
• Network of mass points and springs
• Hook’s law, damping law and Newton’s 2nd law give acceleration of every mass point
at any given time
• F = ma
– Hook’s law and damping provide F – ‘m’ is point mass
– The value for a follows from F=ma
• Now, we know acceleration at any given time for any point
• Want to compute the actual motion
20
Integrators (contd.)
• Theequationsofmotion:
• x=pointposition,v=pointvelocity,a=pointacceleration • Theydescribethemovementofanysinglemasspoint
• Fhook=sumofallHookforcesonamasspoint
• Fdamping = sum of all damping forces on a mass point
21
dx
dt
=v
d2x dv 1
= =a(t)= (F +F +F )
dt2 dt m
Hook damping force field
Integrators (contd.)
• When we put these equations together for all the mass points, we obtain a system of ordinary differential equations.
• In general, impossible to solve analytically
• Must solve numerically
• Methods to solve such systems numerically are called integrators
• Most widely used: – Euler
– Runge-Kutta 2nd order (aka the midpoint method) (RK2) – Runge-Kutta 4th order (RK4)
22
Integrator design issues
• Numerical stability
– If time step too big, method “explodes”
– t = 0.001 is a good starting choice for the assignment – Euler much more unstable than RK2 or RK4
» Requires smaller time-step, but is simple and hence fast – Euler rarely used in practice
• Numerical accuracy
– Smaller time steps means more stability and accuracy – But also means more computation
• Computational cost
– Tradeoff: accuracy vs computation time
23
Integrators (contd.)
• RK4 is often the method of choice
• RK4 very popular for engineering applications
• The time step should be inversely proportional to the square root of the elasticity k [Courant condition]
• For the assignment, we provide the integrator routines (Euler, RK4)
– void Euler(struct world * jello);
– void RK4(struct world * jello);
– Calls to there routines make the simulation progress one time-step further.
– State of the simulation stored in ‘jello’ and automatically updated
24
Tips
• Use double precision for all calculations (double)
• Do not overstretch the z-buffer
– It has finite precision
– Ok: gluPerspective(90.0,1.0,0.01,1000.0);
– Bad: gluPerspective(90.0,1.0,0.0001,100000.0);
• Choosing the right elasticity and damping parameters is an art
– Trial and error
– For a start, can set the ordinary and collision parameters the
same
• Read the webpage for updates
25