iDevGames Forums
Separation axis collision detection - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Separation axis collision detection (/thread-5730.html)



Separation axis collision detection - SOUR-Monkey - Mar 23, 2005 12:51 AM

I have been fiddling with the separation axis method for collision detection, and it looks like it will be good if I can get it working. I did write a working implementation a while ago but lost the code and I've been unable to get it working again since.

This particular implementation needs to detect collisions for artibrarily sized and rotated rectangles.

My take on it is this:
  • Calculate normals (separation axes) for both sides of one of the rectangles
  • Project all points in both rectangles onto both the axes I just calculated
  • If the intervals overlap on both axes, then a collision has occured.
Mostly, this seems to be working. My interval calculation seems a little iffy though, and I'm getting false positives when one of the objects goes above the other, between the left and right edges of the lower rectangle.

So, does that method look right? I know something is wrong, but I have a feeling it is one of my calculations and not the overall concept.


Separation axis collision detection - DoG - Mar 23, 2005 02:58 AM

The separation axes for boxes are the face normals (or actually the principal axes) and their respective cross products.

I've got a C++ implementation based on the sep. axis paper:
http://dog4.dyndns.org:8080/svn/yag/yag/Sources/YAGUtilitieslib/meshoctree.cpp
look for the function "bool BoxBoxIntersects(const Vector3D* A, const Vector3D* B)" around the middle of the file.


Separation axis collision detection - SOUR-Monkey - Mar 23, 2005 06:41 PM

Quote:The separation axes for boxes are the face normals (or actually the principal axes) and their respective cross products.

I assume by this that you mean each box has four axis of separation, the face normals and also their cross products? And what do you mean by 'their respective cross products', the cross product of the face normal and what?

I haven't been able to look at your source code yet, I got a connection timeout when I tried. That may just be the schools connection though, so I'll try when I get home.

Edit: I've tried at home too, no luck. Server timeout.


Separation axis collision detection - belthaczar - Mar 23, 2005 08:09 PM

Are you working in 2D or 3D?

In 3D, there are 15 different axes you must test to determine if Box A and Box B intersect: 3 from the faces from A, 3 from the faces from B, and 3x3 = 9 from the cross products of each face normal of A with each face normal of B.

In 2D, there are 4 different axes to test to determine if Rectangle A intersects with Rectangle B: 2 from the edges of A and 2 from the edges of B. If any of the 4 edges you look at is a valid separating axis, then A & B don't intersect and you can stop checking the remaining edges. If there is overlap on all 4, then A & B do intersect.


Separation axis collision detection - SOUR-Monkey - Mar 23, 2005 08:36 PM

Sorry, yes I am using 2D. And it looks like it works now, I just had to change the order that I checked one object's axes in.

Will moan more if it suddenly fails Smile


Separation axis collision detection - DoG - Mar 24, 2005 01:23 AM

Eh, sorry about the dead link, but I had to turn off the computer last night for something, and forgot to switch it back on later. The perils of running a server over DSL.