# Oriented Bounding Box Intersection Point

Hi!
I'm currently working on a 3D car racing game in C adn DirectX but having trouble with the collision detection. I am using OOBs to detect collisions between the cars but cannot determine the intersection point. I am currently working on a 2D level and ignoring the y component. Admittedly I am not a very strong C programmer! I would appreciate any advice on this subject, any alternative methods of implementing collision detection or any good sites. Thank you very much!
###### Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x

Commented:
Try this site. The second section is all about different collision detections.

http://www.gamedev.net/reference/list.asp?categoryid=45
0

Commented:
try something like this for an overlapping rectangle test:

int Collision_Test(int x1, int y1, int w1, int h1,
int x2, int y2, int w2, int h2)
{
// this function tests if the two rects overlap

// get the radi of each rect
int width1  = (w1>>1) - (w1>>3);
int height1 = (h1>>1) - (h1>>3);

int width2  = (w2>>1) - (w2>>3);
int height2 = (h2>>1) - (h2>>3);

// compute center of each rect
int cx1 = x1 + width1;
int cy1 = y1 + height1;

int cx2 = x2 + width2;
int cy2 = y2 + height2;

// compute deltas
int dx = abs(cx2 - cx1);
int dy = abs(cy2 - cy1);

// test if rects overlap
if (dx < (width1+width2) && dy < (height1+height2))
return(1);
else
// else no collision
return(0);

} // end Collision_Test
0

Author Commented:
Thanks for the response but I can already detect if the rectangles overlap - I need to accurately determine the intersection point of the two rectangles...
0

Commented:
There could be up to four intersection points.

One way of doing it might be to represent each of the rectangles using a transformation matrix which transforms a unit box.  This matrix should take into account the orientation and location of the car, and the scale of the bounding box.

Then to do the collision detection between car A and car B, transform A's matrix by the inverse of B's matrix.  You will then have a matrix which defines A in terms of B.  Next transform a unit box by this matrix.  This box represents car A in relation to car B.  So you can now do four highly optimised individual line intersection tests, by testing the four lines of this box against an axis aligned unit box at the origin.

If you're having trouble understanding my description let me know.
0

Commented:
Just had a thought...  The last part of this method wont work in 3d, only 2d.  But it will be able to speed up the intersection tests in 3d, as one of the boxes is now axis aligned and unit.
0

Commented:
when two 2d objects collide (lets say object A and object B), one of the vertecies of object A or B end up sticking into a side on the other object. Picture a triangle running into a rectangle to picture what I mean. That vertex is intersection point, I think.

In 3d, my first sentence isn't correct: sometimes its a line on object A hitting a line on object B or a vertex on object A sticking into a face on object B.

0

Commented:
Here's a simple, non optimized way to do collision detection in 3D:

we are testing object A against object B. First we would want to make sure that A and B are both expressed in the same base. You
could transform all vertices to worldspace, but as mentioned above, it would be smarter to transform the object with the least
vertices to the base of that with the most vertices.

Once all vertices are in the same space, we would have to :

- repeat for all edges of A
- repeat for all polygons of B
- P = plane equation build from three points of polygon from B
- find point of intersection between line A and plane P, will call this point c. Check if c is between the two vertices of A. (0 < (c - A0)/(A1-A0) < 1)
- for all two vertices of B take angle between c and these vertices. Accumulate all these angles.
- if the last sum is 2*pi or 360 degrees, the objects collide. (edge from A collides in poly from B at point c)

This will only work for convex polygons though ..

as far as maths is concerned, it's all really basic :
- finding plane equation P(a,b,c,d) from V1(x,y,z) V2(x,y,z) and V3(x,y,z) :
P(a,b,c) = normalize( V2-V1 dot V3-V1)
P(d) = - (P(a,b,c) dot V1)
- finding the intersection between P(a,b,c,d) and the linepiece through V1(x,y,z) and V2(x,y,z)
temp = - (  (p dot v1 + d) /  (p dot (v2-v1)) )
if temp < 0 or temp > 1 then intersection before V1 or after V2 = no collision .. fast bail ..
C(x,y,z) = V1 + temp * (v2-v1)
- is C(x,y,z) inside the original polygon ? (it is in the plane for sure ..) the polygon is v1(x,y,z) upto vn(x,y,z)
for (i=0, sum=0; i < n; i++)
{
sum += arccos( (v[i] - C) dot (v[i+1] - C))
}
if sum = 2*pi -> collision !!

0