Collision Detection and Response

Report
Here is where I want
my object to be
Here is where my
object is
Here is where my
object is going to be

A box that is
Initial Airplane Orientation
◦ Defined by the min and max
coordinates of an object
◦ Always aligned with the
coordinate axes

How can we tell if a point p
is inside the box?
Airplane Orientation 2

Do a bunch of ifs
◦ if(
px<= maxx &&
py<= maxy &&
pz<= maxz &&
px>= minx &&
py>= miny &&
pz>= minz )
then collide = true;
else collide = false
minx
maxx
maxy
P
miny

if mins/maxes overlap
then collide = true
else collide = false; Bmaxy
Bminx
Bmaxx
Amaxx
Aminx
Bminy
Initialization: Iterate through vertices
and find mins and maxes
After Transformations: Iterate through AABB vertices and find
mins and maxes

Initialization
◦ iterate through all vertices of your model to find the
mins and maxes for x, y, and z

During runtime
◦ Test if any of the AABB mins/maxes of one object
overlap with another object’s AABB mins/maxes
 MAKE 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 object
 Then make sure to recalculate your mins/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





Keep a position p and a unit vector v.
Each frame add the vector to the position
p+v*speed,
This is essentially how the camera works in my
latest code sample on my webpage
How about gravity?
◦ Add a gravity vector (e.g., g = [0,-1,0]
◦ v+=v+g*gravity
◦ p +=v*speed
◦ glTranslatefv(p)
◦ where gravity and speed are float

Equation: Ax+By+Cz+D = 0

◦ [A,B,C] is the normal of the plane
◦ D is how far from the origin it is
p = (xp,yp,zp)
What is the shortest distance from p to the
plane?



Axp+Byp+Czp+ D = signed distance
(assuming [A,B,C] is length 1)
For AABBs, normals are always
going to be parallel to a principle axis
e.g., x-axis: [A,B,C] = [1,0,0]
+
[A,B,C]
P
D
-


Manually (i.e., make your own matrix multiplication
functions) transform all things collidable into the
same coordinate frame (e.g. world coordinates)
E.g., if you have :

gluLookat(…)
glPushMatrix()

glPopMatrix()

◦ glTranslatefv(p);
◦ Draw sphere projectile
glPushMatrix();
◦ glRotate(a,x,y,z)
◦ glTranslate(tx,ty,tz)
◦ Draw a BB
glPopMatrix()
The p here is already a position in
world coordinates! YAY!
RT matrix
Get the vertices of this BB and
multiply them by the RT matrix:
e.g., RTvi for each of the 8
vertices, vi. This will put the BB
into world coordinates


Manually transform the projectile into the BB’s
object coordinate frame (less work for cpu)
E.g., if you have :

gluLookat(…)
glPushMatrix()

glPopMatrix()

◦ glTranslatefv(p);
◦ Draw sphere projectile
glPushMatrix();
◦ glRotate(a,x,y,z)
◦ glTranslate(tx,ty,tz)
◦ Draw a BB
glPopMatrix()
1) Multiply p by (RT)-1 or (-T)(-R)p
2) And do the same its direction
vector v
2) do collision detection and
response calculations with the
untransformed BB
3) Put p back into world coordinates
with RTp and its direction vector v
RT matrix Watchout for non-uniform scaling –
for this you would need do do
multiplications of the form M-1Tv

collide = true; // then what?
◦ Calculate ray intersection with the plane
◦ Calculate reflection vector (sound familiar?)
◦ Calculate new position

Rays are made of an origin (a point) and a
direction (a vector)
Refldirection
N
Current Position
Rayorigin
Next
Position



Make sure N and Raydirection are normalized!
Adjacent = A*RayoriginX + B*RayoriginY + C*RayoriginZ +D
adjacent / cos(θ) = hypotenuse
◦ That is, dot (Raydirection , N) = cos(θ)

Rayorigin+Raydirection*hypotenuse = i
Refldirection
N
θ
i
Rayorigin
θ


Really we should use physics here but…
Think back to lighting
◦ Refldirection =-2dot(N, Raydirection) *N + Raydirection
Refldirection
N
θ
i
Rayorigin
θ

1) test collisions and response on untransformed
objects before trying it with applied transforms
◦ Actually, the only requirement is 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 OBB
3) 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

A box that
◦ Stays oriented to the model
regardless of transformations
◦ These are often defined by artists
in the 3D modeling program
◦ There are algorithms to compute
the minimum OBB, but this is out
of scope for this class
◦ How to create the initial box?
 1) Either:
 Iterate through vertices (same as
AABB
 Make a nice box with a modeling
program
 2) Convert to plane equations
Airplane Orientation 1
Airplane Orientation 2


Take 3 vertices from one side of your box
Compute the normal
◦ [v3-v1] X [v2-v1] = [a,b,c]
◦ Normalize the normal
◦ [A,B,C] =[a,b,c] / ||[a,b,c]||

v2
Solve the following:
◦ Ax +By+ Cz + D = 0

Plug in a point we know
is on the plane
◦ Av1x + Bv1y + Cv1z = - D
v3
v1

Equation: Ax+By+Cz+D = 0

◦ [A,B,C] is the normal of the plane
◦ D is how far from the origin it is
p = (xp,yp,zp)
What is the shortest distance from p to the
plane?


Axp+Byp+Czp+ D = signed distance
(assuming [A,B,C] is length 1)
[A,B,C]
P
D
+
-



If( a point evaluates to be <=0 distance from
all 6 planes that make up the box
Then collide = true
Else collide = false

Test whether any of the 8 points that make
up one box collide with the other
◦ Do this for both boxes.
◦ This won’t always work in 3D…

In ANY of the following cases, if all of the
collision tests evaluate to positive, then
assume no intersection
◦ 1) Test collisions between all the vertices of BBA and
all the planes of the BBB
◦ 2) Test the collisions between all the vertices of BBB
and all the planes of the BBA
◦ 3) Then test collisions between all the vertices of
BBA and BBB and all cross products of each pair of
edge normals of BBA and BBB
This actually works for any convex polyhedron. There
are optimizations for OBBs…


Again, you will have to make sure that all
planes, points, etc are in the same coordinate
frame when computing collisions.
Think about normals
◦ Vertex: Mv as usual
◦ Normal: M-1Tn, n= [A,B,C,0]T // this is a vector!

Transform the plane equation
◦ p = [A,B,C,D]
◦ Matrix M = arbitrary transforms
 M-1Tp
◦ OR, if you don’t have any non-uniform scaling
 Mp
 What would happen if you had non uniform scaling?

similar documents