Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Rotated Rectangle Collision Implementation  (Read 2058 times)

0 Members and 1 Guest are viewing this topic.

collechess

  • Newbie
  • *
  • Posts: 10
    • View Profile
Rotated Rectangle Collision Implementation
« on: September 03, 2013, 12:47:48 am »
Recently I've had to implement collision detection between rotated rectangle.  Following this algorithm, http://www.gamedev.net/page/resources/_/technical/game-programming/2d-rotated-rectangle-collision-r2604, I created a function to take the four corners of two rectangles and return a bool as to whether or not they collide.  However, for some reason it registers collisions even when no collisions occur.


bool Game_State::RotatedRectCollision(sf::Vector2f UL1, sf::Vector2f UR1, sf::Vector2f LL1, sf::Vector2f LR1, sf::Vector2f UL2, sf::Vector2f UR2, sf::Vector2f LL2, sf::Vector2f LR2)
{
        sf::Vector2f RectA[4];
        sf::Vector2f RectB[4];
       
        RectA[0] = UL1;
        RectA[1] = UR1;
        RectA[2] = LL1;
        RectA[3] = LR1;
       
        RectB[0] = UL2;
        RectB[1] = UR2;
        RectB[2] = LL2;
        RectB[3] = LR2;
       
        sf::Vector2f Axes[4];
        Axes[0] = sf::Vector2f(UR1.x - UL1.x, UR1.y - UL1.y);
        Axes[1] = sf::Vector2f(UR1.x - LR1.x, UR1.y - LR1.y);
        Axes[2] = sf::Vector2f(UL2.x - LL2.x, UL2.y - LL2.y);
        Axes[3] = sf::Vector2f(UL2.x - UR2.x, UL2.y - UR2.y);

        float ScalarVal[8];

        for(int i = 0; i < 4; i++)
        {
                sf::Vector2f Proj[8];
                int curProj = 0;

                for(int j = 0; j < 4; j++)
                {
                        Proj[curProj].x = Axes[i].x * (RectA[j].x * Axes[i].x + RectA[j].y * Axes[i].y)/(Axes[i].x * Axes[i].x + Axes[i].y * Axes[i].y);
                        Proj[curProj].y = Axes[i].y * Proj[curProj].x / Axes[i].x;

                        curProj++;

                        Proj[curProj].x = Axes[i].x * (RectB[j].x * Axes[i].x + RectB[j].y * Axes[i].y)/(Axes[i].x * Axes[i].x + Axes[i].y * Axes[i].y);
                        Proj[curProj].y = Axes[i].y * Proj[curProj].x / Axes[i].x;

                        curProj++;
       
                }

                for(int j = 0; j < 8; j++)
                {
                        ScalarVal[j] = Proj[j].x * Axes[i].x + Proj[j].y * Axes[i].y;
                }
               
                float min_a = ScalarVal[0];
                float min_b = ScalarVal[4];
                float max_a = ScalarVal[0];
                float max_b = ScalarVal[4];

                for(int j = 1; j < 4; j++)
                {
                        min_a = std::min(min_a, ScalarVal[j]);
                        min_b = std::min(min_b, ScalarVal[j + 4]);
                        max_a = std::max(max_a, ScalarVal[j]);
                        max_b = std::max(max_b, ScalarVal[j + 4]);

                }

                if((min_b > min_a) && (max_b < min_a))
                {
                        return false;
                }
        }

        return true;

}

Ixrec

  • Hero Member
  • *****
  • Posts: 1241
    • View Profile
    • Email
Re: Rotated Rectangle Collision Implementation
« Reply #1 on: September 03, 2013, 01:10:16 am »
Well the error isn't obvious to me, so could you show us a specific false positive?  And you have tried using your debugger to locate the error, right?

Also I think you make the min/max stuff shorter and more readable using std::min_element and std::max_element.

collechess

  • Newbie
  • *
  • Posts: 10
    • View Profile
Re: Rotated Rectangle Collision Implementation
« Reply #2 on: September 03, 2013, 01:32:33 am »
For example, when Rect A is equal to [(242, 133), (228, 142), (233, 120), (219, 129)] and Rect B is equal to [(246, 246), (254, 246), (246, 254), (254, 254)] it registers a collision.  It computes the axes to be (-13, 9), (9, 13), (0, -8), (-8, 0), which I believe is correct.

Foaly

  • Sr. Member
  • ****
  • Posts: 453
    • View Profile
Re: Rotated Rectangle Collision Implementation
« Reply #3 on: September 03, 2013, 09:25:16 am »
There is Code on the wiki that implement a bounding box test using the separated axis theorem. Maybe you find it usefull to look at!

collechess

  • Newbie
  • *
  • Posts: 10
    • View Profile
Re: Rotated Rectangle Collision Implementation
« Reply #4 on: September 07, 2013, 10:09:22 pm »
I had believed that the problem was with the values that I had been inputting, as after I rotated the rectangles, I did not reassign them as top-left, top-right, etc.  However, apparently that was not the case, as it still doesn't work, and registers a collision with basically any values.

For example, A (219, 128) (232, 119) (241, 132) (228, 141) and B (246, 246) (254, 246) (246, 254) (254, 254) registers a collision.

So I once again have no idea what's wrong with the code.