Separating Axis Theorem

D31ee247fed4c3bad76bf30282d897a0
0
dega512 101 Feb 02, 2010 at 03:24

I’m working on some 2D non-axis-aligned rectangle collisions using the separating axis theorem (following this tutorial). My implementation kind of works. Kind of. Here is a link to a video showing how it is working right now (SWF file). Screenshots too just in case:

scrn1.png
scrn2.png
scrn3.png

For whatever reason when one of the rectangles enters the upper-left area of the other it automatically assumes it is a collision :( (as shown in the video, or the bottom right area will cause a false collision if the other rectangle is moving, as shown in the screen shots).

I’m sitting here banging my head trying to figure out where I might be going wrong. So, with that said, I’m looking for pointers on where I could be going wrong!

Not that I’m expecting anyone to, but if somebody really wants to look at the code here it is. Like I said though, I’m looking for a nudge in the right direction so I can figure it out :lol: .

Thanks!
- Zach

6 Replies

Please log in or register to post a reply.

860fe478a2545d6c07b88c759292499e
0
SmokingRope 101 Feb 02, 2010 at 12:29

The part of your code starting with th comment

// Find “values” for each of the projected points (square magnitude)

Should actually be a dot product between each of the projections and the axis

D31ee247fed4c3bad76bf30282d897a0
0
dega512 101 Feb 02, 2010 at 21:54

Thanks a ton for taking a look at my code and pointing that out! That was a good find but that didn’t fix it 100%; it now seems that one of my axes is off and I’m trying to find it (I think it is my 2nd axis: RectA.UR - RectA.LR). I figured it could have been because I wasn’t normalizing each axis but that didn’t do it either. I’ll keep working on it though. Thanks again!

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Feb 02, 2010 at 22:55

Rather than posting a zip containing your entire project, could you just post the relevant piece of the algorithm (including a definition of the used types)?

D31ee247fed4c3bad76bf30282d897a0
0
dega512 101 Feb 03, 2010 at 01:55

@.oisyn Yep!

The first “building block” of my project is an object called ‘CollisionRectangle’ that has four points: UL (upper left), UR (upper right), LL (lower left), and LR (lower right). You build it by passing a center x/y, a width/height, and a rotation and these four points are generated.

UL                         UR
+---------------------------+
|                           |
|            -y             |
|                           |
|           (0,0)           |
|                           |
|            +y             |
|                           |
+---------------------------+
LL                          LR

My collision starts off like the following (pseudocode):

function RectanglesAreColliding(CollisionRectangle a, CollisionRectangle b)
{
    // calculate the axes
    var axis1 = a.UR - a.UL;
    var axis2 = a.UR - a.LR;
    var axis3 = b.UL - b.LL;
    var axis4 = b.UL - b.UR;
    
    return CheckAxis(a, b, axis1) &&
           CheckAxis(a, b, axis2) &&
           CheckAxis(a, b, axis3) &&
           CheckAxis(a, b, axis4);
}

This is where I was talking about how I thought that I might be getting incorrect results because I wasn’t normalizing these axes, but normalizing them made no difference. Also, if I don’t check ‘axis2’ here I get the same results which is leading me to believe that I’m not using the right axis.

My ‘CheckAxis’ is as follows (again, pseudocode, it’s shorter):

function CheckAxis(CollisionRectangle a, CollisionRectangle b, Vector2 axis)
{
    var a_proj_ul = Project(a.UL, axis);
    var b_proj_ul = Project(b.UL, axis);
    
    /* so on and so forth, project each of the 4 corners of each rectangle
        onto the axis */
    
    // find "values" for each of the projected points (used to use
    // square magnitude)
    //
    // thanks to SmokingRope for pointing out I need to use the
    // dot product between the projection and axis here instead!
    var a_ul = Dot(a_proj_ul, axis);
    var b_ul = Dot(b_proj_ul, axis);
    
    /* so on and so forth for each projection... */
    
    // find the min and max "value" for each rect
    var a_min = Math.Min(Math.Min(a_ul, a_ur), Math.Min(a_ll, a_lr));
    var a_max = Math.Max(Math.Max(a_ul, a_ur), Math.Max(a_ll, a_lr));
    var b_min = Math.Min(Math.Min(b_ul, b_ur), Math.Min(b_ll, b_lr));
    var b_max = Math.Max(Math.Max(b_ul, b_ur), Math.Max(b_ll, b_lr));
    
    // check for overlap on this axis
    return b_min <= a_max || b_max <= a_min;
}
860fe478a2545d6c07b88c759292499e
0
SmokingRope 101 Feb 03, 2010 at 03:58

I think your overlap checking is off. I use the following to check for overlap in my own code.

return a_max >= b_min && a_min <= b_max;

What you’ve got returns true in the following scenario:

   B
-----      A
          -----
D31ee247fed4c3bad76bf30282d897a0
0
dega512 101 Feb 03, 2010 at 04:06

Doh! You’re right - that fixed it. Thank you for your help!