Collision Detection and Response

Collision Detection and Response
How to do this?
Here is where my object is
Here is where my object is going to be
Here is where I want my object to be
A box that isDefined by the min and max coordinates of an objectAlways aligned with the coordinate axesHow can we tell if a point p is inside the box?
Axis Aligned Bounding Boxes(AABB)
Initial Airplane Orientation
Airplane Orientation 2
Do a bunch of ifsif(px<=maxx&&py<=maxy&&pz<=maxz&&px>=minx&&py>=miny&&pz>=minz)then collide = true;else collide = false
AABB
P
minx
maxx
maxy
miny
ifmins/maxes overlapthen collide = trueelse collide = false;
Comparing AABBs
Bminx
Bmaxx
Bmaxy
Bminy
Aminx
Amaxx
AABB Approach
Initialization: Iterate through vertices and findminsand maxes
After Transformations: Iterate through AABB vertices and findminsand maxes
Initializationiterate through all vertices of your model to find theminsand maxes for x, y, and zDuring runtimeTest if any of the AABBmins/maxes of one object overlap with another object’s AABBmins/maxesMAKE SURE THAT THE AABB VALUES ARE IN THE SAME COORDINATE FRAME (e.g., world coordinates)!If they aren’t, then manually transform them so they are.This is equivalent to multiplying the 8 points by a matrix for each objectThen make sure to recalculate yourmins/maxes from the 8 transformed points!Note: it is possible to do this with only 2 points from the box: (minx,miny,minz), (maxx,maxy,maxz), but not required
AABB Approach
Keep a position p and a unit vector v.Each frame add the vector to the positionp+v*speed,This is essentially how the camera works in my latest code sample on my webpageHow about gravity?Add a gravity vector (e.g., g = [0,-1,0]v+=v+g*gravityp+=v*speedglTranslatefv(p)where gravity and speed are float
Shoot a projectile
Equation:Ax+By+Cz+D= 0[A,B,C] is the normal of the planeD is how far from the origin it isp = (xp,yp,zp)What is the shortest distance from p to theplane?Axp+Byp+Czp+ D = signed distance(assuming [A,B,C] is length 1)For AABBs,normalsare alwaysgoing to be parallel to a principle axise.g., x-axis: [A,B,C] = [1,0,0]
Collision Detection: Planes and Points
[A,B,C]
D
P
+
-
Manually (i.e., make your own matrix multiplication functions) transform all thingscollidableinto the same coordinate frame (e.g. world coordinates)E.g., if you have :gluLookat(…)glPushMatrix()glTranslatefv(p);Draw sphere projectileglPopMatrix()glPushMatrix();glRotate(a,x,y,z)glTranslate(tx,ty,tz)Draw a BBglPopMatrix()
Manually Transforming Objects for Collisions
Get the vertices of this BB and multiply them by the RT matrix: e.g.,RTvifor each of the 8 vertices,vi. This will put the BB into world coordinates
RT matrix
Thephere is already a position in world coordinates! YAY!
Manually transform the projectile into the BB’s object coordinate frame (less work forcpu)E.g., if you have :gluLookat(…)glPushMatrix()glTranslatefv(p);Draw sphere projectileglPopMatrix()glPushMatrix();glRotate(a,x,y,z)glTranslate(tx,ty,tz)Draw a BBglPopMatrix()
Another way to do the transform
RT matrix
Multiplypby (RT)-1or (-T)(-R)pAnd do the same its direction vectorv2) do collision detection and response calculations with the untransformed BB3) Put p back into world coordinates withRTpand its direction vectorvWatchoutfor non-uniform scaling – for this you would need dodomultiplications of the form M-1Tv
collide = true; // then what?Calculate ray intersection with the planeCalculate reflection vector (sound familiar?)Calculate new positionRays are made of an origin (a point) and a direction (a vector)
Simple Collision Response
Raydirection
Rayorigin
N
Refldirection
Current Position
Next Position
Make sure N andRaydirectionare normalized!Adjacent = A*RayoriginX+ B*RayoriginY+ C*RayoriginZ+Dadjacent /cos(θ) = hypotenuseThat is, dot (Raydirection, N) =cos(θ)Rayorigin+Raydirection*hypotenuse =i
Ray-Plane Intersections
Raydirection
Rayorigin
N
Refldirection
θ
θ
adjacent
i
Really we should use physics here but…Think back to lightingRefldirection=-2dot(N,Raydirection) *N +Raydirection
Calculate a Reflection
Raydirection
Rayorigin
N
Refldirection
θ
θ
adjacent
i
1) test collisions and response on untransformed objects before trying it with applied transformsActually, the onlyrequirementis projectile transformations.2) use spheres for the projectiles ( you can basically treat these as points) and then you do not need to implement separating axes with OBB3) draw your bounding boxes so you can see them (this is actually required is the project)4) graduates : Don’t worry, I don’t expect terrain collisions
Tips for making Assignment 3 easier
A box thatStays oriented to the model regardless of transformationsThese are often defined by artists in the 3D modeling programThere are algorithms to compute the minimum OBB, but this is out of scope for this classHow to create the initial box?1) Either:Iterate through vertices (same as AABBMake a nice box with a modeling program2) Convert to plane equations
Oriented Bounding Boxes (OBB)
Airplane Orientation 1
Airplane Orientation 2
Take 3 vertices from one side of your boxCompute the normal[v3-v1] X [v2-v1] = [a,b,c]Normalize the normal[A,B,C] =[a,b,c]/ ||[a,b,c]||Solve the following:Ax +By+Cz+ D = 0Plug in a point we knowis on the planeAv1x+ Bv1y+ Cv1z= - D
Creating the Plane Equations
v1
v2
v3
Equation:Ax+By+Cz+D= 0[A,B,C] is the normal of the planeD is how far from the origin it isp = (xp,yp,zp)What is the shortest distance from p to theplane?Axp+Byp+Czp+ D = signed distance(assuming [A,B,C] is length 1)
Collision Detection: Planes and Points
[A,B,C]
D
P
+
-
If( a point evaluates to be <=0 distance from all 6 planes that make up the boxThen collide = trueElse collide = false
OBB – Point Collision
Test whether any of the 8 points that make up one box collide with the otherDo this for both boxes.This won’t always work in 3D…
Collision Detection: OBB and OBB
In ANY of the following cases, if all of the collision tests evaluate to positive, then assume no intersection1) Test collisions between all the vertices of BBAand all the planes of the BBB2) Test the collisions between all the vertices of BBBand all the planes of the BBA3) Then test collisions between all the vertices of BBAand BBBand all cross products of each pair of edgenormalsof BBAand BBBThis actually works for any convex polyhedron. There areoptimizationsfor OBBs…
Separating Axes
Again, you will have to make sure that all planes, points, etc are in the same coordinate frame when computing collisions.Think aboutnormalsVertex:Mvas usualNormal: M-1Tn, n= [A,B,C,0]T// this is a vector!Transform the plane equationp = [A,B,C,D]Matrix M = arbitrary transformsM-1TpOR, if you don’t have any non-uniform scalingMpWhat would happen if you had non uniform scaling?
Transforming OBB Planes