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.
Quote this message in a reply
DoG
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.
Quote this message in a reply
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.
Quote this message in a reply
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.
Quote this message in a reply
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 Smile
Quote this message in a reply
DoG
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.
Quote this message in a reply
Post Reply 

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