## Separation axis collision detection

Member
Posts: 70
Joined: 2004.06
Post: #1
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.
Moderator
Posts: 869
Joined: 2003.01
Post: #2
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/...octree.cpp
look for the function "bool BoxBoxIntersects(const Vector3D* A, const Vector3D* B)" around the middle of the file.
Member
Posts: 70
Joined: 2004.06
Post: #3
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.
Nibbie
Posts: 2
Joined: 2006.10
Post: #4
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.
Member
Posts: 70
Joined: 2004.06
Post: #5
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
Moderator
Posts: 869
Joined: 2003.01
Post: #6
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.

Possibly Related Threads...
 Thread: Author Replies: Views: Last Post Optimize the collision detection alaslipknot 1 2,802 May 12, 2013 08:02 PM Last Post: SethWillits Separation of simulation from Visualization ? imranhabib 3 5,027 Jul 11, 2012 09:41 PM Last Post: AnotherJake Collision detection tutorial ThemsAllTook 7 22,835 Nov 5, 2011 05:20 PM Last Post: SethWillits Help with Collision Detection..(i'm almost there) carmine 1 4,695 Jun 29, 2011 12:33 PM Last Post: ThemsAllTook Seperating Axis Theorem Code mikey 5 4,721 Oct 9, 2010 03:25 PM Last Post: Oddity007