Geometry proxies (in 2D):

(1)

Geometry proxies (in 2D):

a Convex Polygon



Intersection of half-planes

 each delimited by a line



Stored as:

 a collection of (oriented) lines



Test:

 a point is inside iff it is in each half-plane



A very good expressiveness, with only moderate complexity

Geometry proxies (in 3D):

a Convex Polyhedron



Intersection of half-space



Similar as previous, but in 3D

 stored as a collection of planes

 each plane = a vec4

(normal, distance from origin)

 test: inside proxy iff inside each half-space

(2)

Geometry proxies (in 3D):

a (general) Polyhedron

 Luxury Hit-Boxes :)

 The most accurateapproximations

 The most expensivetests / storage

 Specific algorithms to test for collisions

 requiring some preprocessing

 and data structures (BSP-trees, see later)

 Creation (as meshes):

 sometimes, with automatic simplification

 often, handmade (using low-poly modelling)

 (note: proxies are assets!)

 Similar to a 3D mesh?

 e.g. adaptive resolution

 but…

(they would be wasted, asBounding Volumes!) potentiallyconcave

3D Meshes as hit-boxes



Differences with «common» meshes :

 much lower res ^{(~ O(10}²) faces max)

 no attributes (no uv-mapping, no col, etc)

 generic polygons, not tris: ok (as long as they are flat)

 closed, water-tight(inside != outside)

 sometimes: convex only

the ones used for rendering

(3)

3D Meshes as hit-boxes

mesh for rendering

(~600 tri faces) (in wireframe) Collision object:

10 (polygonal) faces

3D Meshes as hit-boxes

mesh for rendering (~300 tri faces)

(in wireframe)

Collision object:

12 (polygonal) faces

(4)

Composite Geometry proxies



Union of Proxies

 inside iff inside of any sub-proxy



useful ! for example:

 union of convexpolyhedra = concave polyhedron

 union of a sphere, two capsules, one box =

a good, but cheap, approximation of a given shape



creation: it’s manual work

 (remember: hit-boxes are usually assets)

 potentially: a good problem for AI ?

if (!collide( boundingVol, X ) ) {

return NO_COLLISION; // early reject }

else {

CollisionData d;

if (collide( hitBox, X , &d )) {

return d; // for the response!

}

else return NO_COLLISION;

}

Bounding Volume + Collision Object

a simple Bounding Volume

around a more complex Collision Object

approximating the object note: the twocollide

aren’t the same function (overloading)

(5)

Which geometric proxy to support ?

 an implementation choice of the Physics Engine

 note: # of intersection tests to be implemented quadratic with # of types supported

 note: supported proxy types

can be used as either Bounding Volumesor Hit-Boxes

Type A Type B Type C

algorithm algorithm algorithm

VS a Point a Ray

algorithm

algorithm algorithm

algorithm

algorithm Rays are

useful, e.g.

for visibility

Collision detection:

strategies

 Static

Collision detection

 (“a posteriori”, “discrete”)

 approximated

 simple + quick

 Dynamic

Collision detection

 (“a priori”, “continuous”)

 accurate

 demanding

t

t + dt

COLLISION t

NO COLL

t + dt

COLLISION

(6)

Collision detection:

Discrete

«static»

(because objects are tested as if they are still)

«a posteriori»

(because coll are detected after they happen)

«discrete»

(bacause it is checked at discrete time intervals)

 Collisions-check after every step of dynamics

 Problem: lack of self-intersection is violated

 and then just fixed as part of the collision response

 Problem: tunnel effect

 happens more when:

- dt is large, - or vels are large, - or objects are thin

t

NO COLLISION

t + dt

NO COLLISION  Aka:

Collision detection:

Continuous

«dynamic»

(because moving objects are tested)

«a priori»

(because coll are detected before they happen)

«cotinuous»

(bacause it is checked over a time interval)

 Check intersection on the volume swept by

the collision object during the current frame

 Italian: spazzata

 Extra bonus:

 intersection can be prevented, not fixed: clean, elegant, accurate

 just find max dt s.t. no collision occurs: move object by that much

 Problem: computation is demanding

 easy for: points (they become lines)

 easy for: spheres (they become capsules) (how?)

 rarely used for anything else: other colliders are not as simple.

 used at all only when really needed (designer choice!):

i.e. colliders are small, vel large, and dt cannot be decreased Aka:

(7)

Collision detection: in 2D

(easier problem)

 Same problems, same solutions

 e.g.:

2D spatial indexing,

2D bounding volumes(2D geom. proxies)…

 But we have : collision detection for 2D sprites (in screen space)

 accurate:«pixel perfect»

 efficient:HW supported! (hard wired, e.g part of blit operations)

 (no need for collision objectapproximation)

NO COLLISION NO COLLISION COLLISION

e.g.

quad-trees

e.g.

2D AABB, circles

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 ?

(8)

Avoiding

a quadratic number of tests



For this purpose,

we need some auxiliary data structure

 use it to bypass most obj-to-obj test

(the… earliest reject is to not even do the test!)

 build it only once, for static parts

 update it every frame, for dynamic parts



Classes of solutions:

1) Spatial Indexing Structures

2) BVH– Bounding Volume Hierarchies

Spatial indexing structures



Data structures to accelerate queries of the kind:

«I’m here. Which objects are in my proximity? »



Challenges:

 (1) fast construction / update

 (2) fast access / usage



Commonest structures (in games):

 Regular Grid

 kD-Tree

 Oct-Tree

 in a 2D game: the Quad-Tree

 BSP Tree

(9)

a b

c d e f

g h i j

k l

m n o p

q r s

Regular Grid (or: lattice)

the scene

a b c d e f g h i j k l m

n o p q r s

Regular Grid (or: lattice)

 Array 3D of cells (same size)

 each cell: a list of pointers to collision-objects

 Indexing function:

 Point3D  cell index, (constant time!)

 Construction: (“scatter” approach)

 for each object B[ i ]

 find the cells C[ j ] which it touches

 add a pointer in C[ j ] to B[ i ]

 Queries:

 given a point to test p,

find cell C[ j ], test all objects linked to it

 Problem: cell size

 too small: memory occupancy too large quadratic with inverse of cell size!

 too big: too many objects in one cell

 sometimes, no cell size is good enough 

(10)

kD-tree

the scene

A

B C

D E

F G

I

H

^H ^I

K J

J K

M L

^L ^M

N O

D E F

H

K M

N O

kD-trees

 Hierarchical structure: a tree

 each node: a subpart of the 3D scene (a AABB)

 root: the entire scene

 child nodes: partitions of the parent node

 objects linked to leafs

 kD-tree:

 binary tree

 each node: split over one dimension (in 3D: X,Y,Z)

 variant:

 each node optimizes (and stores) which dimension, or

 always apply same order: e.g. X, then Y, then Z, then X,…

 variant:

 each node optimizes the split point, or

 always in the middle

(11)

Quad-Tree (in 2D)

the (2D) world

often used forterrains

Oct Tree

(same, for 3D)

(12)

Quad trees (in 2D) Oct trees (in 3D)



Similar to kD-trees, but:

 tree: branching factor: 4 (2D) or 8 (3D)

 each node: splits into all dimensions at once, (in the middle)



Construction (just as kD-trees):

 continue splitting until a end nodes has few enough objects

(or limit level reached)

BSP-tree

Binary Spatial Partitioning tree

the world

(13)

BSP-trees for

the Concave Polyhedron proxy

BSP-trees for

the Concave Polyhedron proxy

F

D

A

OUT B

OUT

OUT C

IN D OUT

E

OUT IN F E

C B

A

(14)

BSP-tree

Binary Spatial Partitioning tree

 Another hierarchical spatial structure

 it’s a binary tree (like the kD-tree)

 root = all scene (like the kD-tree)

 but, each node is split by an arbitraryplane

 (in 2D: by a line)

 plane can be stored succinctly, as: (nx, ny, nz, k)

 construction: planes can be optimized for the given scene

 e.g. go for a 50%-50% object split at each node

 e.g. try to leave exactly one object at leaves

 (assuming it is always possible to split any two apart – reasonable assumption)

 Also used to: General Polyhedron proxies collision

 each leaf: fully inside or fully outside

 just one bool !

 tree precomputed, for a given input Polyhedron,

 nodes = faces of the polyhedron

 optimizing for balance

Reminder:

Plane VS Point test



Input: a point 𝑞 a plane given by:

 its normal:

𝑛

 a point on it: 𝑝



Q: on which side of the plane is 𝑞 ?



A: it’s the sign of

𝑛 𝑞 −𝑝 = 𝑛 𝑞 −𝑛 𝑝= 𝑛 𝑞 +𝐾 =

(𝑛 , 𝑛 , 𝑛 , 𝐾) (𝑞 , 𝑞 , 𝑞 , 1)

𝑞

𝑝

𝑛

the vec4

representing the plane

𝐾= −𝑛 𝑝

(minus dist. of plane from orig.)

(15)

BVH

Bounding Volume Hierarchy

BVH

Bounding Volume Hierarchy

E

F

A D

C B

E F

A B C D

(16)

BVH

Bounding Volume Hierarchy

E

F

A D

C

G B

H

J

K

M

J K

F

G H E

A B C D

BVH

Bounding Volume Hierarchy



Idea: use the scene hierarchy given by the scene graph

 (instead of a spatial derived one)



associate a Bounding Volumes to each node

 rule: a BV of a node bounds all objects in the subtree



construction / update: quick! 

 bottom-up: recursive (how?)



using it at query time:

 top-down: depth-first visit (how?)

 note: it’s not a single root-to-leaf visit

 may need to follow all children of a node which intersect (in a BSP-tree: only one)

(17)

Spatial indexing structures Recap

 Regular Grid

 the most parallelizable (to update / construct / use)

 constant time access (best!)

 quadratic / cubic space (2D, 3D)

 kD-tree, Oct-tree, Quad-tree

 compact

 simple

 BSP-tree

 optimized splits!  best performance when accessed

 optimized splits!  more complex construction / update

 suited for the staticparts of the scene

 (also, used for Generic Polyhedron Collision Objects)

 BVH

 simplest construction

 non necessarily very efficient to access

 may need to traverse multiple children

 if uses same hierarchy of the scene-graph: not always the best

 suited for the dynamicparts of the scene

Physics Engine:

parallel implementation?

 Task: Dynamics:

 (forces, speed and position updates…)

 simple structures, fixed workflow

 highly parallelizable: so GPU

 Task: Constraints Enforcement:

 (all the various kinds of them…)

 still moderately simple structures, fixed workflow

 still highly parallelizable: hopefully, GPU

 Task: Collisions Detection:

 non-trivial data structures: hierarchies, recursive algorithms…

 hugely variable workflow

 (quick on no-collision, more complex on the few near miss and hits)

 difficult to parallelize: so CPU

 but the outcome affects other two tasks (e.g. creates constraints):

 ==> CPU-GPUcommunication,

 ==> GPU structures updates (problematic, on many architectures)

(18)

To learn more about game physics



Erwin Coumans

SIGGRAPH 2015 course

http://bulletphysics.org/wordpress/?p=432



Müller-Fischer et al.

Real-time physics

(Siggraph course notes, 2008)

http://www.matthiasmueller.info/realtimephysics/

In

Attaching to a GameObject…

 …a RigidBodycomponent means:

 « use Unity built-in phys. dynamicson this object »

 unless itsisKinematicflag is activated (if so: no dynamics)

 …a Collidercomponent means:

 « use Unity built-in collision detectionfor this object »

 …both the components means:

 « use Unity built-incollision response for this object »

 unless isTriggerflag is activated (if so: no response)

 also, collider is used to precompute distribution of mass constants of RigidBody (barycenter, moment of inertia)

 Note: collision detection can happen without response:

ad-hoc collision effects are purely scripted instead

 write method onTriggerEnter( Collider other )

 e.g.: avatar touches object: collects object arrowhead touches soldier: dies;

(19)

In : colliders

 parameters for the built-in response:

 “Bounciness” : 1.0: purely elasticimpacts 0.0: purely staticimpacts or any intermediate values

 Friction : (separate values for dynamic/ static)

 flags to choose how to combine Friction / Bounciness

of two colliding objects (max, min…)

 collider: a geometric proxy,

(used as a collision object)

 several types available

 (sphere, box… -- see next slide)

 “isTrigger” flag:

 «just collision detectionplease, disable built-in collision response»

the

physical material asset associated to the collider

In :

available collider types

 Simple geometric shapes:

 Sphere

 Capsule

 Box (general, not Axis Aligned: can be rotated)

 Cylinder

 Plane (finite, i.e., a rectangle)

 Polyhedron: (meshCollider)

 convex: convex flag is set

 generic: convex flag not set

(no built-in collision response)

 must be associated to a (low poly!) a mesh asset

 Specialized proxies, for particular objects:

 terrains, i.e., height-fields (TerrainCollider)

 car wheels (WheelCollider) (ad-hoc “wheel-like” collision response)

 And composite proxies

 just add multiple collider components to one game-object interactive WYSIWYG shape editor integrated in IDE

user responsibility to specify this!

(20)

In :

other physics parameters/flags

 Staticflag

 if set: cannot move. If not: object is dynamic

 user responsibility: as we know, crucial for optimization!

 Mass

 total, irrespective of distribution

 Drag

 (1-DAMP)/sec -- separate values for vel / angular vel

 Collision detection mode

 “discrete” (always discrete)

 “continuous dynamic” (always continuous)

 “continuous static” (continuous VS static objects, discrete VS dynamic objects)

 Use-gravityflag:

 note: gravity acceleration is a global “Project Setting”

 Simple positional / rotational constraints

 separate “freeze” flags for X,Y,Z (position) and for X,Y,Z Euler angle (rotation)

in associated RigidBody component in

GameObject