Collision handling!

Collision handling!

L’altra metà del motore fisico

Collision Handling:

un’ottimizzazione

Distinzione a-priori fra:

oggetti statici

so che sono sempre fermi (vel = 0)

«sfondo»

influenzano gli altri oggetti, ma non ne sono influenzati oggetti dinamici

possono spostarsi

Due tipi di collisione:

one way:

oggetti dinamici con oggetti statici two ways:

oggetti dinamici con oggetti dinamici

Statico: Dinamico:

Statico:

Dinamico:

X One Way

One Way Two Ways

Collision Handling

Collision detection

scoprire quando avvengono

Collision response

includerne gli effetti nella dinamica

Collision response

Garantire la non compenetrazione

rimettere gli oggetti in pos valida (quando: sempre)

Urto

aggiungere impulsi da impatto (rimbalzi, etc) (quando: la collisione non c’era, nello step prec.)

Attrito

fra i due oggetti

dissipazione di energia

(quando: dal 2ndo step consecutivo di collisione)

Effetti ad-hoc (scripted, etc)

fratturazioni, ammaccamenti, etc (quando, e se:dipende dal gameplay)

Non compenetrazione

posizione non valida?

strategia 1: revert a ultima pos valida(facile, ma debole)

strategia 2: proiezione a pos valida + vicina

non valido proiezione in pos valida

Non compenetrazione

con Position Based Dynamics:

solo un altro vincolo di posizione

bonus: vel aggiornata, simile a urto anaelasitico

imposizione

del vincolo:

one way :

sposto solo l’oggetto dinamico two ways :

sposto entrembi gli oggetti,

ciascuno in modo proporzionale alla massa dell’altro

ma,

non noto a priori

Attrito

Su contatto prolungato

(collisione con oggetto col quale avevo giá colliso)

Come:

forze in dir opposte al moto di entità proporzionale al moto oppure: semplice DAMP

Urto

Modifica (improvvisa!) della

risolvere l’urto = determinare le nuove vel

Mantiene sempre

Vari casi:

urto (puramente) elastico

se vale inoltre: mantenimento dell’energia! (cinetica)

se vale inoltre: impulso in dir di normale del punto impattato urto (puramente) anaelasitco

se vale inoltre: stessa vel. per i due corpi dopo urto (come se urto fonde i due corpi insieme) e casi intermedi

basta interpolare le vel risultanti nei due estremi i.e. tramite un impulso

(momentum )

Momento:

Urto (puramente) anaelesastico

PRIMA: DOPO:

?

Momento:

unica incognita

= …

Urto (puramente) elesastico

Mantenimento:

momento(come sempre)

energia cinetica (0 perdita energia)

Ipotesi:

Ǝ piano di impatto (o, in 2D, linea)

inpulso ortogonale a questo piano

Soluz:

scomporre le vel in due componenti:

comp. ortogonale al piano di impatto comp. parallela al piano di impatto l’urto modifica solo la prima delle due, e solo nel suo modulo e/o verso (stessa dir)

ci serve (la normale di) questo piano!

Quando la collision detection restituisce «SI», ci dia questo dato.

Urto (puramente) elesastico

PRIMA:

Momento:

Energia:

/2

piano di impatto

DOPO:

′

′

Momento:

′ ′

Energia:

′ ′ /2

Urto (puramente) elesastico

PRIMA:

Momento:

Energia:

/2

DOPO:

′

′

Momento:

Energia:

′ ′ /2

Urto (puramente) elesastico

Soluz in casi particolari:

due masse uguali:

swap delle due componenti velocità ortogonali al piano di impatto

urto one-way (con A statico):

==>

massa di A inf & vel di A = 0

==>

inversione della comp ortogonale al piano di impatto di B

Urti fra corpi rigidi ^(*)

(*) cioè dotati di vel angolari

Per ora abbiamo considerato solo urti fra particelle (no vel angolare)

in Position Based Dynamics con corpi rigidi ottenuti attraverso vincoli di equdistanza, questo basta

Per urti fra corpi rigidi, bisogna trovare anche la vel angolare dopo l’urto

stessi principi, ma considerare anche:

momento angolare

oltre al momento

energia cinetica rotazionale

le oltre a quella del moto rettilineo

si mantiene

si mantiene, in urti elastici

Collision Response:

recap

Dalla collision detection, serve sapere:

collisione Sì / No

«c’è intersezione?»

e, quando Sì…

posizione«safe» non compenetraz come delta fra pos attale e pos safe (per garantire nn compenetraz) normaledel piano di collisione

es. norm del punto impattato (per risolvere l’urto)

collision data

Collision Handling

Collision detection scoprire se c’é collisione (e, nel caso, fornire i dati per la response)

Collision response

includerne gli effetti nella dinamica

Collision detection

Il problema: l’efficienza Osservazione:

l’enorme maggioranza delle coppie di oggetti, nell’enorme maggioranza dei momenti,

NON collide.

per l’efficienza dei test,

bisogna ottimizzare innanzitutto il caso in di NON collisione

«early reject» del test

Collision detection

Problemi di efficienza:

a) test fra due oggetti:

Come renderlo efficiente?

b) evitare esplosione quadratica dei test

N oggetti N

tests ?

Geometric proxies

Geometric proxy

Rappresentazione

degli oggetti usata dal motore fisico (e altro)

(nota: molto più semplice e approssimato del modello usato nel rendering!)

Due tipi di usi:

come Bounding Volume

limite supall’estensione dell’oggetto (oggetto “tutto dentro” il bounding volume)

test conservativi

come Collision Object (o “hit-box”) approxdell’estensione dell’oggetto

test approssimati

Used in:

physic engine

collision detection collision response

rendering optimizations

view frustum culling occlusion culling

AI

visibility test

GUI

picking (one of the ways)

Semantica di un geometric proxy

intersection( proxy_A , <qualcosa> ) =/= Ø

? quando

fa da Bounding Volume :

se NO: non c`è collisione se SI: non so ancora

quando

fa da Collision Object :

se NO: non c`è collisione se SI: c`è collisione!

e dal proxy calcolo i dati della collisione

un altro proxy, o un punto, o un raggio…

una ottimizzazione!

«early reject»

un’approssimazione (lossy)

della collision detection

Tipi di Geometric proxies

Axis Aligned (Bounding) Box

aka AABB

generic (Bounding) Box Discrete Oriented Polytope

aka DOP

(Bounding) Sphere (Bounding) Ellipsoid

(axis aligned or not)

(Bounding) Cylinder Poliedri convessi Poliedri non convessi Mesh 3D

(mesh colliders)

“Capsule”

…

Tipi di Geometric Proxies:

difetti e pregi

quanto sono

onerosi da pre-computare

/

quanto sono

sono robusti a trasformazioni ?

quelle che usiamo, e.g. isometriche

quanto sono

degli oggetti?

(in media / di solito / per la categoria di oggetti) se bounding volume ==> quanto è piccolo / aderente se collision object ==> quanto è buona l’apporx

quanto è onerosa una

di intersezione?

con punti, raggi, altri proxies … e, quanto sono buoni i collision data?

Sphere

☺ abbastanza facile da computare / aggiornare

in modo approssimato

☺ piccola da storare

centro (punto), raggio (scalare)

☺ molto facile da testare (con tutto)

come?

☺ facile effettuare rotaz + traslaz + scaling

come?

qualità approssimaz:

dipende (come sempre). Spesso, no. Chidersi, ad es:

una testa? un uomo? una casa? una penna?

Geometry proxies:

«Capsule»

Def:

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 with:

a segment (two end-points) a radius (a scalar)

Exercise :

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

(A: quite well popular proxy!)

Geometry proxies:

a half space

Trivial, but useful

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

Storage:

(nx, ny, nz, k)

a normal, a distance from the origin

test, rotations, etc: trivial

Geometry proxies:

«AABB»

Axis Aligned (Bounding) Box Molto facile da aggiornare Coinciso da storare

tre intervalli: su X, su Y, su Z

Banale da testare…

non robusto a rotazioni!

solo scalature / traslazioni

Box

“Parallelepiped”

non axis aligned storage (e.g):

a rotation an AABB

robust to rotations too

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

Good approx,

still 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-plane

Geometry proxies (in 3D):

a (general) polyhedron

Luxury Hit-Boxes :)

The mostaccurateapproximations The mostexpensivetests / storage

Specific algorithms to test for collisions

requiring some preprocessing and data structure

Creation (as meshes):

sometimes, with automatic simplification often, hand made (low poly modelling) (they are assets!)

Similar to a 3D mesh?

e.g. adaptive res but…

(they would be wasted, asBounding Volumes!) concave too

hit-boxes

Differences with «commmon» meshes :

much lower res (~ O(10²) )

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

3D Meshes as hit-boxes

mesh for rendering (in wireframe) Collision object:

3D Meshes as hit-boxes

mesh for rendering (~300 tri faces)

(in wireframe)

Collision object:

12 (polygonal) faces

Geometry proxies:

Composite Hit-Boxes

Union of Hit-Boxes

inside iff inside of any sub Hit-Box

useful !

e.g.

union of convexHit-Boxes ==> concave Hit-Box e.g.

shape partially defined by a sphere,

partially by a box, etc ==> better approximation

creation: typically by hand

(remember: hit-boxes are usually assets)

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;

}

Collision Object

a simple Bounding Volume

around a more complex Collision Object

approximating the object note: the twocollide

aren’t the same function (overloading)

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: typically, supported proxy types

can be used as either Bounding Volumesor Hit-Boxes

Type A Type B Type C

Type A Type B Type C

algorithm algorithm algorithm

algorithm algorithm algorithm

VS a Point a Ray

algorithm

algorithm algorithm

algorithm

algorithm

algorithm useful,

e.g.

for visibility