Sign in to follow this  
ramy

Collision detection

Recommended Posts

Hello everybody, could anybody assist me with the following: -obb collision detection tutorials, and the point of intersection. -i also dont understand how to compute it. -in a car racing game, wat type of collision would fit cars other than obb? several ppl tried, but i got confused, so could somebody help me in these plz? thanks in advanced

Share this post


Link to post
Share on other sites
I'm not sure what would work better than OBBs for cars. If you wanted to be more accurate (but more complicated), you could treat them as a collection of convex objects (tires, chassis, etc.) connected rigidly. But OBBs are a lot easier and are a good approximation.

Both static and dynamic (i.e. moving) collision detection can be performed between OBBs using the separating axis theorem. For static intersection you should be able to get a normal and depth, and for dynamic intersection you can reconstruct the contact features.

Simple boolean intersection is pretty easy - in the collision detection section of the articles on this site is a gamasutra article which explains the algorithm. Swept intersection is a little trickier, and reconstructing the point of intersection can get a little complicated as well.

However, it's all covered in Dave Eberly's book '3D Game Engine Design' (and also his physics book), as well as in code and .pdf's on his Magic Software site. If you're serious about the OBB approach, that's where you'll want to look.

Share this post


Link to post
Share on other sites
i am serious, thx alot.

i have taken a look in magic software, and in gamasutra, i kinda got mixed up, why 15 sides?

anyways, ill try that book u told me.

thx

Share this post


Link to post
Share on other sites
15 sides for 15 potential separation axis tests.

3 faces of polygon A
3 Faces of polygon B

Dir1 of polygonA x Dir1 of polygonB
Dir1 of polygonA x Dir2 of polygonB
Dir1 of polygonA x Dir3 of polygonB


Dir2 of polygonA x Dir1 of polygonB
Dir2 of polygonA x Dir2 of polygonB
Dir2 of polygonA x Dir3 of polygonB

Dir3 of polygonA x Dir1 of polygonB
Dir3 of polygonA x Dir2 of polygonB
Dir3 of polygonA x Dir3 of polygonB

erad up on separation axis theorem and it's uses.

Share this post


Link to post
Share on other sites
yep.

then from there it's 'projecting' the box on those axes, and finding if the projection segements overlap.

then to find the collision point is a bit more work.

Share this post


Link to post
Share on other sites
//A
VECTOR& a, //extents
VECTOR& Pa, //position
VECTOR* A, //orthonormal basis

does anybody know what does orthonormal mean in the above information?

these 3 vectors are information of a box, in the obb.

Share this post


Link to post
Share on other sites
The orthonormal basis is just 3 mutually orthogonal unit-length axes (i.e. they are all perpendicular to each other). As an example, the X, Y and Z axes in world space are an orthonormal basis.

Share this post


Link to post
Share on other sites
I'm slightly tipsy, so forgive me if the explainations don;t seem to make a lot of sense....

the orthonormal basis can be as simple as the 3x3 orientation matrix.

pull out each rows or columns of the matrix (depending if it's a row-major or column-major matrix sytem you use) to get the 3 vectors you need.

ok, as far as finding the collision points, I might as well detail the calculations.


struct OBBox
{
Vector P; // centre of the box
Vector L[3]; // axes of the box
Vector E; // extent of the box
};

// calculate projection of a box onto an axis and return the
//interval of projection
void OBBox::ProjectOnAxis(const Vector& Axis, float &min, float &max) const
{
float p = P.Dot(Axis);
float r = abs(D[0].Dot(Axis)) * E.x + abs(D[1].Dot(Axis)) * E.y + abs(D[2].Dot(Axis)) * E.z;
min = p - r;
max = p + r;
}

// see if two box intervals over an axis intersect, and if so
// calculate the amount of overlap
bool OBBox::AxisOverlap(const Vector& Axis, const OBBox& Box, float &depth) const
{
float min1, max1;
float min2, max2;
this->ProjectOnAxis(Axis, min1, max1);
Box->ProjectOnAxis(Axis, min2, max2);

if (min1 > max2 || min2 > max1) return false;

float d0 = abs(max1 - min2);
float d1 = abs(max2 - min1);
depth = (d0 < d1)? d1 : d0;
return true;
}

bool OBBOx::Intersect(const OBBox& Box, Vector& Normal, float& depth) const
{
Vector Axis[15];
float d[15];

Vector* pAxis = &Axis[0];
float* pd = &d[0];

*pAxis = this->L[0];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[1];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[2];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;

*pAxis = Box.L[0];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = Box.L[1];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = Box.L[2];
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;

*pAxis = this->L[0].Cross(Box.L[0]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[0].Cross(Box.L[1]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[0].Cross(Box.L[2]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;

*pAxis = this->L[1].Cross(Box.L[0]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[1].Cross(Box.L[1]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[1].Cross(Box.L[2]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;

*pAxis = this->L[2].Cross(Box.L[0]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[2].Cross(Box.L[1]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;
*pAxis = this->L[2].Cross(Box.L[2]);
if (!AxisOverlap(Box, *pd)) return false; pAxis++; pd++;

// no separation axis found.
// find the collision plane, and the penetration depth
Vector D = Box.P - this->P;
return FindIntersectionPlane(D, Axis, d, Normal, depth);
}

bool OBBox::FindIntersectionPlane(const Vector& D, Vector* Axis, float* d, Vector& Normal, float& depth)
{
// fond the separation plane with the minimum intersection and
// use it as the collision plane
float dmin;
int imin=-1;
for(int i = 0; i < 15; i ++)
{
float dist = Axis[i].GetLength();

// sanity check
if (dist < 1.0E-6f)
continue;

d[i] /= dist;

if (imin == -1 || d[i] < dmin)
{
dmin = d[i];
imin = i;
}
}

// degenerate case. error.
if (imin == -1)
return false;

// makes sure the collison plane normal is facing the right way
if (Axis[imin] * D < 0.0f)
Axis[imin] *= -1.0f;

Normal = Axis[imin];
depth = d[i];

return true;
}



Share this post


Link to post
Share on other sites
that should give you the collision plane and depth between the two boxes.

to find the contacting points, it's a bit more work again :)

You need to find the points of box A that are the 'highest' along that plane normal, and take the points on B that are the 'lowest' along that normal.

that should give a group of points on A and B.

the number of points on A and B can either be 4 (a whole face), 2 (an edge) or 1 (a single vertex).

So, imagine you have a box sitting on a table.

the collisoin normal will face up. the points on the table the 'highest' along that direction are the 4 points at the top of the table. the points on the box the 'lowest' along that direction will be the 4 corners at the bottom on the box.

so you have a 4-point polygon against another 4-point polygon.

what you need to do is clip one polygon against another, like in any standard 2D/3D clipping system.

Say the box is resting in the middle of the table, the clipping will give the 4 corners of the box. using those corners, and the collision depth, then you have the 4 collision points, with their penetration depth, and their collision normal. YOu can then generate collision impulses on those corners to keep the box on the table or bounce it around.


if the box is overhanging on the edge of the table, you'll have a different set of vertices (maybe two vertices of the box, and two vertices on the edge of the table).

if you have the box balanced on edge on the table, then you'd get a clipping of an edge versus the quad defined by the top of the table. In that case, you'll get 2 points of collision.

I'm not giving you any clipping code, since it should be easy to find, and it's quite a lengthy piece of code.

Share this post


Link to post
Share on other sites
Can't i get it out of the plane equation?
Ax + By + Cy + d = 0 ?

If i have the plane normal of the Obb and the equation will be more than zero, can't we get d?
im totally confused now.

ok i dont think that would work!

Share this post


Link to post
Share on other sites
im trying to get it in my head bit by bit, orthonormal is the matrix (if we can say) that rotates the obb to the world axis ( i.e. X axis, Y axis and Z axis).

and after orienting the obb, i project each plane on the corresponding axis, i do that for both obbs and c if they over lap?
olii, the code u just wrote, did wat i said right?

if there is a collision, then atleast one side will overlap?!

is that correct? somebody correct me please.

Share this post


Link to post
Share on other sites
Quote:
Original post by ramy
im trying to get it in my head bit by bit, orthonormal is the matrix (if we can say) that rotates the obb to the world axis ( i.e. X axis, Y axis and Z axis).

and after orienting the obb, i project each plane on the corresponding axis, i do that for both obbs and c if they over lap?
olii, the code u just wrote, did wat i said right?

if there is a collision, then atleast one side will overlap?!

is that correct? somebody correct me please.


by 'plane' I assume you mean 'face' or'quad'. SO in theory, you could project every vertices of the box onto the axis (do a dot product of the vertex times the axis direction), and take the minimum and maximum to get the interval of the box, but there are shortcuts when projecting an OBB onto an arbitrary axis. I used shortcuts, to speed up the calculations.

the function ProjectOnAxis() just calculates the [min, max] projection interval of a box along an axis.

the function AxisOverlap() tests if the projection intervals on an axis for two boxes overlap or not.

Intersect() simply project the boxes onto the 15 axes and test if the boxes projection intervals are disjoint (meaning, NOT overlapping) along at least one axis.

If the boxes don't overlap, then it means that you could fit a piece of paper between the boxes, so then, the boxes can;t intersect, since they are dijoint.

If all axes intersect, then FindIntersectionPlane() finds the axis with the minimum overlap depth between the 15 axes.

the plane returned is in the form (Normal, d).

in parametric equation form, the plane equation is then

[Normal.x] * X + [Normal.y] * Y + [Normal.z] * Z + [-d] = 0


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hey, im back :D

remember the:
struct OBBox
{
Vector P; // centre of the box
Vector L[3]; // axes of the box
Vector E; // extent of the box
};

wat did u mean by Vector L[3]; // axes of the box ??

i thought it was the directtion of the vector that it is moving in?

wat is it then if its a matrix?

Share this post


Link to post
Share on other sites
For cars you might be better off representing the collision shape as

1. a convex hull (or just a box)
2. a collection of spheres.

Then for collisions between one car and another you test the spheres of one against the convex hull(or box) of the other, and maybe the other way around. Then it's very easy to implement swept tests and avoid nasty things happening in the case of a head-on crash (if both cars are going at 120mph and your physics step is 1/60th of a second they could end up penetrating by 2m otherwise, which might be hard to resolve).

Also you could use the spheres to collide the cars against the world (presumably a triangle mesh), again easier and faster and more ammenable to swept tests than using a convex hull/box.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
hey, im back :D

remember the:
struct OBBox
{
Vector P; // centre of the box
Vector L[3]; // axes of the box
Vector E; // extent of the box
};

wat did u mean by Vector L[3]; // axes of the box ??

i thought it was the directtion of the vector that it is moving in?

wat is it then if its a matrix?


COnvex hulls collision tests are more complicated. Spheres are simple, maybe you should consider that. It would make it far easier to trace spheres against the geometry than boxes.


There is no direction of movement in the code. the code only works with overlaps, but you can extend it to do swept tests.

To extend if using swept tests, go to Dave Eberly's website (www.magic-software.com), he has some docs on doing box box collisions, and also how to deal with velocities.

discussion
code+docs

this is a tutorial I wrote to do 2D polygonal collision detection, in swept form as well as in overlaps. You'll find the code very similar to what's above, the principle is the same. You can extend the code above and use the same ideas I presented in the tutorial, and do the test in swept form.

The advantage of the method is that you can extend it to box-triangles just as easy. It's exactly the same code, just different axes of projection to test, and another interval calculation function for the triangles.

Now, L[3] are the three orthonormal axes of the box. If you have a matrix, those vectors can either be the first 3 columns or the first 3 rows of your orientation matrix, depending if it's row-major or column-major.

If you are unsure, just extract the rows of the matrix as 3 vectors, and render line segments inside the box, and see if it coincides with the orientation of the box. If not, try to extract the columns into 3 vectors, and do the same. One way or another, the vectors will be facing the same as the faces of the cube.

Frankly, if this is bugging you, really consider using spheres. It's efficient, and a lot more simple to get to grips with, and gives a good approximation. You can model a car with say, 6 spheres for the chassis, the two in the middle being slightly bigger for the hood.

Share this post


Link to post
Share on other sites
well, to say a truth, i want to get obb done with, to finish off the collision, ill deal with the collision point later on.

but for now, i want to know the obb, i think thats gr8 until now.

if just poped to my mind, that i can rotate both boxes so they r aligned to world axis, and them check them via aabb, wat do u think?

which would be faster do u think?

Share this post


Link to post
Share on other sites
that last reply was alot of help

im almost done with it.

by saying: "D[0].Dot(Axis)" i prosume u meant "L[0].Dot(Axis)" in ProjectOnAxis() cause its only makes sence that way, right? sorry to bother u soo much oliii.

Share this post


Link to post
Share on other sites
Quote:
if just poped to my mind, that i can rotate both boxes so they r aligned to world axis, and them check them via aabb, wat do u think?


Well, you could rotate one or the other into alignment with the world axes, but not both :-) In the end though it all comes out about the same - either you do some dot products up front to rotate one of the OBBs, or you do them later during the separating axis tests.

I haven't compared the number of ops between the two approaches though, so I suppose one or the other might be a little faster.

Quote:
by saying: "D[0].Dot(Axis)" i prosume u meant "L[0].Dot(Axis)" in ProjectOnAxis() cause its only makes sence that way, right?


Pretty sure he means L[].Dot(Axis).

Share this post


Link to post
Share on other sites
on the magic-software site mentioned by oliii you can also find code for the routine.

The second box is transformed to the space of the first box, so it becomes an AABB - OBB cd problem.

I'm still working on finding the contact points, it's going very slow but steady.

Share this post


Link to post
Share on other sites
Quote:
by saying: "D[0].Dot(Axis)" i prosume u meant "L[0].Dot(Axis)" in ProjectOnAxis() cause its only makes sence that way, right?


yes. It's pseudo code, in the way that I re-wrote it (although I've got the exact same code somewhere...).

Quote:
Well, you could rotate one or the other into alignment with the world axes, but not both :-) In the end though it all comes out about the same - either you do some dot products up front to rotate one of the OBBs, or you do them later during the separating axis tests.

I haven't compared the number of ops between the two approaches though, so I suppose one or the other might be a little faster.


The number of ops does no matter that much in the code above, since it's grossly unoptimised. Dave Eberly again has the optimum version of the code, but it involves a lot of work, and it's difficult to debug, and obviously harder to read. In the end, the code, when optimised, is really really efficient, and if you transform into one of the OBB's space, he claims he get better performance (less dot products), but I'm not sure if it weights out with the matrix multiplication. For further optimisations, I'm also wondering if the extent vector of the box could be just removed, and the three direction vectors scaled by the extent components. You have then a smaller OBB structure, and less calcs.

Anyway, the code above is in the most basic form. If you really want a good OBB algorithm, it will be a lot of work.

And again, OBB-triangles, triangles-triangles are the same thing as far as the separation axis algorithm is concerned.

About the contact points, As soon as you get the normal of collision (in the second part of the code above), then it's simply a matter of finding the face or point or edge on each OBB that is 'supporting' the OBB along that normal. Then you clip the face/face, or face/edge if you have such results, or just do an edge-edge collision, or a point plane collision (I don't think you'll ever get edge-point or point point collisions, but if you do, you can consider them, quite trivial).

Share this post


Link to post
Share on other sites
Has anyone successfully implemented the OFG collisiondetection by Eli Kara?
http://www.gamedev.net/reference/articles/article2045.asp

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this