Link to home
Create AccountLog in
Game Programming

Game Programming

--

Questions

--

Followers

Top Experts

Avatar of Mags77
Mags77

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!

Zero AI Policy

We believe in human intelligence. Our moderation policy strictly prohibits the use of LLM content in our Q&A threads.


Avatar of helmet275helmet275

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

Avatar of Mags77Mags77

ASKER

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...  

ASKER CERTIFIED SOLUTION
Avatar of helmet275helmet275

Link to home
membership
Log in or create a free account to see answer.
Signing up is free and takes 30 seconds. No credit card required.
Create Account

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.

Reward 1Reward 2Reward 3Reward 4Reward 5Reward 6

EARN REWARDS FOR ASKING, ANSWERING, AND MORE.

Earn free swag for participating on the platform.


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.

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.


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 !!


Free T-shirt

Get a FREE t-shirt when you ask your first question.

We believe in human intelligence. Our moderation policy strictly prohibits the use of LLM content in our Q&A threads.

Game Programming

Game Programming

--

Questions

--

Followers

Top Experts

Game programming is the software development of video games. Game programming requires substantial skill in software engineering as well as specialization in simulation, computer graphics, artificial intelligence, physics, audio programming, and input. Like other software, game development programs are generated from source code to the actual program by a compiler. Source code can be developed with almost any text editor, but most professional game programmers use a full integrated development environment (IDE).