The other half of the physics engine

Collision handling!



The other half of the physics engine

Collision Handling:

one preliminary optimization

 A-priori distinction between:

 static objects

 always still (vel = 0)

 the stage, the background

 they affect other objects, but are not affected by them

 dynamic objects

 can move

 Two types of collision:

 one way:

dynamic objects with static objects

 two ways:

dynamic objects with dynamic objects

Static: Dynamic:

Static:

Dynamic:

X One Way

One Way Two Ways

Collision Handling



Collision detection

 find out when collision happens



Collision response

 make collision affect dynamics

Collision response: tasks



Enforce non intersection

 put objects back into valid, intersection-free positions

 when: always



Impacts

 add an impulse (rebounds, bounces)

 when: wasn’t colliding the previous frame



Friction between the two objects

 dissipation of energy

 when: from the 2nd consecutive collision step



Ad-hoc effects (scripted)

 breaking, damages, collection, loss of HP, etc.

 when, and if:gameplay dependent

Enforcing non-intersection



not a valid position?

 strategy 1: revert to last valid pos (easy, but weak)

 strategy 2: project on closest valid pos

not valid projection to valid pos

Enforcing non-intersection



with Position Based Dynamics:

just another positional constraint

 as a bonus: update of velocity, similar to an inelastic impact



enforcing of this constraint:

 for two-ways collisions:

both objects move away from each other

 again, each one proportionally to the mass of the other

 yet another application of the minimization of m ∙ displacement²

 for one-way collisions:

only the dynamic object moves (all the way)

 static object can be understood as having infinite m

but, it’s not known a priori.

It is created by a detected collision

Impacts

 Sudden update of velocity

 resolve for the impact = determine the new velocities

 Total momentum always mantained

 Cases:

 (completely) elasticimpact

 assumption: kinetic energyis also kept

 assumption: impulse is given in the normal direction

 (completely) inelasticimpact

 assumption:

the two objects share the same velocity after the impact (i.e. the impact fuses them together)

 intermediate cases

 just interpolate the velocities found for the two other cases that is, technically,

an impulse

𝑣⃗ 𝑚

Momentum:

( 𝑚 + 𝑚 ) 𝑣⃗

(Completely) inelastic impact

BEFORE: AFTER:

𝑚 𝑣⃗

𝑚 𝑣⃗

𝑣⃗ = ? 𝑚 + 𝑚

Momentum:

𝑚 𝑣⃗ + 𝑚 𝑣⃗

the only unknown

= …

(Completely) elastic impact



Two invariants:

 momentum(as always)

 kinetic energy (0 energy loss)



We also assume:

 Ǝ local impact place

 (or, in 2D, line)

 the impulse is delivered orthogonally to it



How to apply impact:

 split velocities into two components:

 comp. orthogonal to impact plane

 comp. parallel to impact place

 the impact only affects the former

we need its normal (a unit vector) When

collision detection returns «YES», it must give this, as part of the collision data.

that’s never really the case in reality, BTW.

Some energy is lost.

No impact can be completely elastic in practice.

(Completely) elastic impact

BEFORE:

𝑚

𝑣⃗

𝑚

𝑣⃗

Momentum:

𝑚 𝑣⃗ + 𝑚 𝑣⃗

Energy:

( 𝑚 𝑣⃗ + 𝑚 𝑣⃗ )/2

plane of impact

AFTER:

𝑚 𝑣′

𝑚

𝑣′

Momentum:

𝑚 𝑣′ + 𝑚 𝑣′

Energy:

( 𝑚 𝑣′ + 𝑚 𝑣′ )/2

(Completely) elastic impact

BEFORE:

𝑚 𝑜⃗

𝑚

𝑜⃗

Momentum:

𝑚 (𝑝⃗ + 𝑜⃗ ) + 𝑚 (𝑝⃗ + 𝑜⃗ ) Energy:

( 𝑚 (𝑝⃗ + 𝑜⃗ ) + 𝑚 (𝑝⃗ + 𝑜⃗ ) )/2

AFTER:

𝑚 𝑜′

𝑚

𝑜′

Momentum:

𝑚 (𝑝⃗ +𝑜 ) + 𝑚 (𝑝⃗ +𝑜 ) Energy:

( 𝑚 (𝑝⃗ + 𝑜′ ) + 𝑚 (𝑝⃗ + 𝑜′ ) )/2

𝑝⃗

𝑝⃗

𝑝⃗

𝑝⃗

an easier case:

(Completely) elastic impact in 1D

 In 1D, velocities are… 1D vectors, i.e. (signed) scalars

 Two equalities:

 solving for 𝑣′ , 𝑣′

we get a quadratic equation (exercise), with two solutions

 one is always: 𝑣′ = 𝑣 𝑣′ = 𝑣

 the other one is what we are looking for

𝑚 𝑣 + 𝑚 𝑣

momentum before

( 𝑚 𝑣 + 𝑚 𝑣 )/2

energy before

( 𝑚 𝑣′ + 𝑚 𝑣′ )/2

energy after

=

=

𝑚 𝑣′ + 𝑚 𝑣′

momentum after

an easier case:

(Completely) elastic impact in 1D

Solutions for a few particular cases (verify!):

 the two masses are equal: 𝑚 = 𝑚

velocities are swapped: 𝑣′ =𝑣 𝑣′ =𝑣

 A is static (one-way impact): 𝑣 = 0 𝑚 → ∞ velocity of B is flipped: 𝑣′ = 0 𝑣′ = −𝑣

(Completely)

elastic impact in 2D or 3D

TO UPDATE VELOCITIES:

Given: velocities vA,vB the normal of impact n

Step 1:find the components of vAand vB along direction n, Scalar xA = dot( vA , n )

Scalar xB = dot( vB , n )

Step 2:remove these components from both velocities vA -= xA * n

vB -= xB * n

Step 3:resolve 1D elastic impact on xA, xB

determining after-impact xA’,xB’(see previous two slides).

Step 4:add the new components along nto both velocities vA += xA’* n

vB += xB’* n

Frictions ( italian: attriti )



On prolonged contacts

 (collision with an object that was already colliding)



How to:

 forces in contrary direction of current vel, its magnitude proportional to current speed

 or: just increase DAMP (cheap, less accurate)



Static friction != dynamic friction

 (static is higher)

 static if the relative speed is zero

(negates a force which would start a movement)

Impact between rigid bodies (*)



So far, we only considered collision between particles (no rotation, no angular vel)

 for Position Based Dynamics,

with rigid bodies composed of particles and equidistance constraints, this is all that is needed



With rigid bodies, the impact also affects the two angular velocities

 same principles, but now applied also to:

 angular momentum (always kept)

 angular kinetic energy (kept, for elastic only)

 not just the rectilinear kinetic speed

Outcome of a

Collision Detection



collision: Yes / No

 «is the intersection non null?»



and, if Yes…

 produce data required by the collision response:

 positionof impacted points

 normalsof impacted points

 maybe, closest «safe»

collision-free position

collision data

Collision Handling



Collision detection



find out if there’s a collision (and, if so, provide the data for the response)



Collision response



implement the effects of collision

inside the dynamics

Collision detection.

The usual problem: efficiency



Observation:

 by far the majority of the objects, in by far the majority of the frames:

 do NOT collide

 aren’t even close !



Therefore:

 for efficiency, the most important case to optimize is when there is no collision

 especially when it’s not even a close call

 i.e., we want «early rejection»: quick detection of lack of collision,

in clear cases, like when the two objects are far

 hits, and close misses, can be much slower

Collision detection



Challenges for efficiency:

a) test between two objects:



How to make it efficient?

b) avoid quadratic explosion on the number of tests



N objects  N

tests ?

Geometric proxies

Geometric proxies



Strongly simplified and volumetric representation of (3D, 2D) objects



not the same repres. used by the rendering («for the look»), i.e. a Triangle Mesh

 proxy is typically much simpler, more approximated

 it’s a volume (inside ≠ outside), not just a surface



Many objects are represented by one of each

 one Mesh (rendering only)

 one Proxy (all the rest)

 e.g., in Unity: Mesh ≠ Collider

(singular: proxy)

Geometric proxies:

uses in a game engine



physics

 collision detection

 collision response



rendering optimizations

 view frustum culling

 occlusion culling



AI

 visibility test



GUI

 picking (it’s one of the ways)

Geometric proxies:

two possible roles

A proxy can be used :



as a Bounding-Volume

 upper boundto

the extension of the object

 (the object is all inside the proxy)

conservative tests



as a Collision Object

 approximation

of the extension of the object

 (the object is partly outside the proxy)

approximate tests

or “hit-box”

or “collider”

Geometric proxies:

two possible roles

intersection( proxy_A , <something> ) ≠ Ø

?



when

is used as a Bounding Volume :

 if = Ø

:

 if ≠ Ø : don’t know yet



when

is used as a Collision Object :

 if = Ø

:

 if ≠ Ø : collision

 compute collision data from the proxies

another proxy, or a point, or a ray

an optimization!

«early reject»

final approximation for the collision detection

Types of

Geometric proxies

 Axis Aligned (Bounding) Box

 aka AABB

 “Capsule”

 general (bounding) Box

 Discrete Oriented Polytope

 aka DOP

 (bounding) Sphere

 (bounding) Ellipsoid

 (axis aligned or not)

 (Bounding) Cylinder

 Convex polyhedron

 general Polyhedron

 (aka mesh colliders)

 …

Types of Geometric Proxies:

good and bad for…?



how difficult is to compute / update it ?



how heavy is it to store ?



is it possible/easy to transform it ?

 with the spatial transformations we use, i.e. isometries



expressiveness: how well can it approximate / bound the objects I need in my game?

 for bounding volumes ==> how small can the proxy be

 for collision objects ==> how good the approximation;

and, how accurate are resulting collision data?



how complex is the intersection query ?

 testing for intersection with: other proxies, points, rays

Geometry proxies:

Sphere



 easy to compute / udate

 at least, apprximatively



 tiny storage

 center (point), radius (scalar)



 very easy to test (VS most thing)

 how? (exercise - try against: sphere, points, rays)



 easy to transform (rotat + trasl + scaling)

 how? (exercise)



 expressiveness:

 sufficient only for a few objects.

 an head, a ball? ok. But: a person? a house, a pen?

Geometry proxies:

«Capsule»



Definition:

 Sphere ==

set of all points with dist from a point< radius

 Capsule ==

set of all points with dist from a segment< radius

 i.e. a cylinder ended with two half-spheres (all same radius)



Stored as:

 two points (the two endpoints of the segment)

 a radius (one scalar)



Exercise :

 Q: how does it «score» w.r.t. the above measures?

 (A: quite well  very popular proxy!)



I.e., an oriented plane



Trivial, but useful

 e.g. for a flat terrain, or a wall

 typically, for static objects



Storage:

 a point p on plane, planenormal n (unitary vector)

 or: optimized as a ( p_x, p_y, p_z , k ) (a Vector4) with k = -dot( p, n )



Tests, Transforamtion, etc: easy

Geometry proxies:

a half space

Geometry proxies:

«AABB»

Axis Aligned (Bounding) Box



Easy to compute / update



Storage

 as three intervals

AABB = [ x_min,x_max] × [ y_min,y_max] × [ z_min,z_max]

 Equivalently, as two points p_min,p_max



Easy to test

 test against a point trivial (are p_x, p_y, y_z in the intevals?)



but, cannot be transformed!   

 transation: ok,

scalings: ok, (even non uniform) rotations: NOTok

Geometry proxies:

«Box»

i.e. “Parallelepiped”



non axis aligned



storage:

 an AABB …

plus, a rotation R (e.g. a quaternion)



easy to test

 e.g.: to test agaisnt a point,

apply R^-1 then test against the AABB



can be rotated too

 (but doesn’t work with non-uniform scalings)