Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

Game Physics Lecture

an overview of physics engine functions
by

Ben Smith

on 5 February 2013

Report abuse

Transcript of Game Physics Lecture

What issues do you need to be aware of?
Where do you go to find the solutions?
Understand the limitations of physics engines. Primary Concerns Kinematics: Motion without regard to external forces.
Only consider position, velocity, acceleration.
Dynamics: Motion effected by forces and impulses￼￼. Motion: Modeling Objects Typically, ignore geometry.
Don’t worry about object shape, only important for collisions.
Every object is a point. http://www.essentialmath.com/tutorial.htm–Squirrel Eiserloh’s Problem Overview lecture http://www.cis.cornell.edu/courses/cis3000/2011fa/lectures/16-PhysicsMotion.pdf Difference between kinematics and dynamics,
How do each of them work?
When is one more appropriate than another?
What dynamics do physics engines provide?
What problems do physics engines have? First, Understand: determine an object's position p at time t
Typically know p from a previous time￼￼ Assume: constant velocity v
p(t+Δt) = p(t) + vΔt
Or Δp = p(t+Δt)-p(t) = vΔt
Alternatively: constant acceleration a
v(t+Δt) = v(t) + aΔt (or Δv = aΔt)
p(t+Δt) = p(t) + v(t)
Δt + 1⁄2a(Δt)2
Or Δp = v0Δt + 1⁄2a(Δt)2 Forces affect movement
Springs, joints, connections Gravity, repulsion
Determine velocity from forces
Compute current force F Linear Dynamics Force: F(p,t)
p: current position
t: current time
Creates a vector field
Movement follows ￼￼￼￼field direction Very simple to use.
Non-calculus physics. Difficult.
Expensive. Problems Classic solution: reduce the time step Δt Up the frame rate (not necessarily good) Perform more than one step per frame Each Euler step is called an iteration Multiple iterations per frame Let h be the length of the frame Let n be the number of iterationsΔt = h/n Typically a parameter in your physics engine Particle Systems World is a bunch of particles Particles interact via forces Examples of forces Constant: gravity Position/time dependent: force fields Velocity dependent: drag N-ary dependent: springs, collisions Force is function F(p1,...,pn,v1,...,vn,t) Compute from interaction with other particles At the start of each iteration Compute forces between particle pairs Sum up all of the forces acting on a particle From these forces compute the acceleration Compute velocity and position as before Important detail: delay particle updates Do not move a particle before it is summed This can cause very subtle errors (why?) Most physics engines support particle systems Specify the collection of bodies Specify the forces that can act on the body Specify the time step and number of iterations Positions are updated automatically for you
Additional capabilities: custom scripts Constrained Behavior Suppose we have a bead on a wire The bead can slide freely along wire It can never come off, however hard we pull. How does the bead move under applied forces? Usually a curve given by function C(x,y) = 0 Why don’t we attach to wire with spring? Move the bead normally (maybe off wire) Create shortest spring between bead and curve Apply spring force as if fixed to curve viscous liquids (goopy jelly), ?? What if "curve" is a surface? Constraint Solvers Constraints limit movement
Joints: distance constraint
Contact: non-penetration
Restitution: bouncing
Friction: sliding, sticking Also rolling
Applications: Ropes, chains Stacking Global solver (slow) Solve forces simultaneously
Complex physics
Iterative solver (fast)
while (!done) {solve for λ1 solve for λ2 solve for λ3} Converge to global solution Mutiple Constraints: Very difficult to implement Errors cause joints to fall apart Called position drift
Use a Physics Engine! Constraints/particle systems are finicky Performance/appearance depends on your parameters Expect to do a lot of tuning to get it just right Take Away: For motion, model game objects as points Often a single point to represent the object A rigid body is made of several points Dynamics is the use of forces to move objects Compute acceleration from the sum of forces Use Euler’s method to compute velocity, position Objects can interact in complex ways Particle systems: objects exert a force on one another Constraint solvers: restrictions for more rigid behavior Discrete physics simulation falls embarrassingly short of reality.
“Real” physics is prohibitively expensive...
...so we cheat.
We need to cheat enough to be able to run in real time.
We need to not cheat so much that things break in a jarring and unrecoverable way.
Much of the challenge is knowing how and when to cheat. > “Will the player notice?”
> “Will the player care?”
> “Will the results be predictable?”
> “Are we at least cheating in a consistent way?”
> “Will the simulation break?”
If the simulation breaks, they will notice and they will care!
Some crimes are greater than others. Problems in Physics Goals The Story thus far... Next: Knowing when to cheat credits: Moving objects on the screen Collisions between objects Collision detection: Did a collision occur?
Collision resolution: What do we do? Rigid body if more complex.
Collection of points,
All fixed distance from one another,
Moving one moves them all. Idea: the centroid of the region.
Average of all locations in region.
Alternatively: the center of mass = centroid if density uniform. Body Movement p, t p1, t+Δt Assume F constant entire frame Formulas:
Δa =F/m
Δv = FΔt/m
Δp = F(Δt)2/m Update formulas:
ai = F(pi,iΔt)/m
vi+1 = vi+aiΔt
Non-rigid bodies. Ask: Simplifying things complex simple simpler rigidbodies indestructible Movement: in a vacuum, no air resistance or hugely oversimplified. Collisions: assumed perfect and elastic. 100% energy transfer/retention Moving things around Simulation baggage see Kinematics vs. Dynamics! Flip-book
Syndrome things can happen between frames things MOSTLY (only?) happen between frames! piecewise linear trajectories terms assumed constant through frame Error Accumulates Conservation of Energy?? energy loss is undesirable... but energy gain is EVIL! simulations explode! Rotations assumed to happen instantaneously at frame boundaries Collision Detection Determine if A and B intersect Worse, they're probably in motion If they did collide, we need to know when and we need to figure out how to resolve it Sustained Interactions stacked objects Friction: static & kinetic Constraint & Joints Dealing with the Impossible > Minimum size requirement?Inadequate; fast objects still tunnel
> Maximum speed limit?Inadequate; since speed limit is a function of object size, this would mean small & fast objects (bullets) would not be allowed
> Smaller time step?Helpful, but inadequate; this is essentially the same as a speed limit Possible solutions Interpenetration? Tunneling Tunneling: it sucks. Small objects tunnel more easily. Enforce minimum size? even with min. size requirements and speed limits and a small time-step, you still have degenerate cases that cause tunneling! Rotational tunneling?? Making it fast enough > How should we choose to represent physical bodies?
> How should we simulate and compute motion?
> How can we prevent energy build-up?
> How do we cope with floating point error?
> How can we detect collisions – especially when large numbers of objects are involved?
> How can we prevent tunneling?
> How should we resolve penetration?
> How should we handle contact?
> How do we deal with non-rigid bodies?
> How can we relieve CPU burden? Problems we’re concerned with: Avoid Unnecessary Work Can't afford to be too particular too soon Eschew n-squared operations "everything vs. everything else" = bad consider:
1000 objects
=1000 x 1000
=1 million checks Simulation Islands Space partitioning schemes to divide and conquer. 1000 objects in 10 islands
=10 x (100x100)
=100,000 checks
=1/10th as many! Putting Islands to Sleep a stable island can be treated as "asleep." i.e. when forces and motion remain unchanged all is quiet... a new object appears. When an object enters an island's bounds that island wakes up, newcomer is added to the island, and peace returns. Additionally: Make “educated assumptions” using:
Temporal/frame coherence: Things tend not to have changed a whole lot in the 15ms or so since the previous frame, so save the previous frame’s results!

Spatial coherence: Things tend to miss each other far more often than they collide, and only things in the same neighborhood can collide with each other Exploit work previously done Where We Cheat for Game Design and Implementation Extra: also, eventually: What is a particle system? When is it used?
What is a constraint solver? When is it used? v Ask:
Full transcript