?
Solved

Oriented Bounding Box Intersection Point

Posted on 2003-03-04
9
Medium Priority
?
20,287 Views
Last Modified: 2013-12-26
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!
0
Comment
Question by:Mags77
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 1

Expert Comment

by:helmet275
ID: 8065968
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 Comment

by:Mags77
ID: 8066777
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
 
LVL 1

Accepted Solution

by:
helmet275 earned 200 total points
ID: 8069673
Try this site. The second section is all about different collision detections.

http://www.gamedev.net/reference/list.asp?categoryid=45
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Expert Comment

by:willstones
ID: 8406522
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
 
LVL 2

Expert Comment

by:willstones
ID: 8406561
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
 

Expert Comment

by:ry4096
ID: 9183857
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
 
LVL 2

Expert Comment

by:enkimute
ID: 10970747
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

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: …
Have you created a query with information for a calendar? ... and then, abra-cadabra, the calendar is done?! I am going to show you how to make that happen. Visualize your data!  ... really see it To use the code to create a calendar from a q…
Suggested Courses
Course of the Month10 days, 2 hours left to enroll

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question