# How can check a collision between 2 non-axis aligned boxes?

I'm making a simple and easy game and I need to detect the collision between 2 boxes. It only needs to return trueor false, no physics involved.

I started working and couldn't find an algorithm that would check the collision for turned squares.

Here I visualized the problem.

As you can see squares 1, 2 and 3 would return true because they collide with the green squares. 4 would return false because it isn't colliding.

I do have all the squares of both colors in separate array lists.

Does anybody know a library or algorithm for this problem? Thanks in advance.

• You might want to consider another interesting corner-case: i.imgur.com/Q1DKpp1.png – Philipp Jul 24 '15 at 11:33

Box2D has a Java library. It might be a bit more than you need but it's pretty robust and used in all sorts of projects. Maybe someone else can recommend a better library solely for collision detection.

If you want to roll your own solution, which would probably be better if you want to keep it simple, you'll need to look into Oriented Bounding Box (OBB) collision detection. The Axis Aligned Bounding Box (AABB) algorithm is super simple but OBB is not nearly as nice. It requires a fair amount of math involving matrices so if you're not solid on that this is a great opportunity to learn.

Separating Axis Theorem (SAT) might be a bit much for 2d OBBs but it's a solid multi-purpose collision detection algorithm. Gilbert–Johnson–Keerthi (GJK) is another algorithm that's used more for objects that are in motion but may also be good for your needs.

Real-time Collision Detection by Christopher Ericson has some really great samples and the book is great for all things related to collision detection. The book actually has a really great example method that I don't think I can paste here because of copyright. However there are always more examples online.

http://rocketmandevelopment.com/blog/separation-of-axis-theorem-for-collision-detection/

http://back2basic.phatcode.net/?Issue_%231:2D_Convex_Polygon_Collision_using_SAT

• SAT is what is needed. The links given in this answer are overly complex in my opinion though. Here is a great tutorial about 2D polygon physics from MetaNet Software which covers SAT. It has some nice interactive examples as well so you can see how the algorithm behaves. metanetsoftware.com/technique/tutorialA.html – Fuzzy Logic Jul 23 '15 at 20:39

You're assumption that you do not need any physics is wrong, anytime you are dealing with moving objects in 1D, 2D, 3D... environments and you need to detect if two objects will collide then you are doing physics calculations. You can not get away from it.

Returning true or false is easy, but figuring out if a collision has happened or not can range from simple to extremely complex. Let's say you have something like this:

class RenderModel {
private:
Vector3 m_size;      // For 2D Set Z to 0 and Ignore
Vector3 m_origin;    // Center Point Of The Model
Vector3 m_position;  // Position In World Space
std::vector<Vector3> m_vMeshCoordinates;
std::vector<Vector2> m_vTextureCoordinates;

public:
Model( Vector3& worldPosition, Vector3& size );
virtual ~Model();

virtual void render() = 0; // Purely Virtual
virtual void update() = 0; // Purely Virtual

private:
RenderModel( const RenderModel& c ); // not implemented
RenderModel& operator=( const RenderModel& c ); // not implemented

}; // RenderModel

class Box : public RenderModel {
public:
Box( Vector3& worldPosition, Vector3& size );
virtual ~Box();

virtual void render() override;
virtual void update() override;

private:
Box( const Box& c ); // not implemented
Box& operator=( const Box& c ); // not implemented
}; // Box


Here we have a class hierarchy were RenderModel is abstract and can not be instantiated but a derived class can be. With this setup each model type would have to implement its own render & update function.

The render call will only draw its contents and the update function is where the object's world position will change.

If you are working with only a 2D environment then I would use an Edge Detecting system with simple ray tracing or Bounding Circles around each object and check the distance between each radius and if they intersect. You need to incorporate a property to these boxes or objects to define them if they are static or dynamic. All static objects will not move in the game or simulation. Anything dynamic will move.

Class WorldMap {
public:
enum BoundingType {
// 2D
BT_BOUNDING_TRIANGLE,  // Rarely Used
BT_BOUNDING_BOX,
BT_BOUNDING_CIRCLE,
BT_BOUNDING_ELIPSE,
// 3D
BT_BOUDNING_PYRAMID,   // Rarely Used
BT_BOUDNING_CUBE,      // Doesn't Have To Be Perfect Cube Just A 3D Box
BT_BOUNDING_CYLINDER,
BT_BOUNDING_SPHERE
}; // BoundingType

enum CollisionType {
CT_RAY_TRACE,
CT_LINE_INTERSECTION,
CT_SHAPE_TO_SHAPE_INTERSECTION
}; // CollisionType

private:
std::vector<std::shared_ptr<RenderModel>> m_vStaticObjects;
std::vector<std::shared_ptr<RenderModel>> m_vDynamicObjects;
Vector3  m_origin;  // Center Location of World
Vector3  m_size;    // Size Of World for 2D set Z to 0 and ignore

// ... other various world elements, objects, properties etc.

public:
WorldMap();
~WorldMap();

void render();
void update();

bool testCollisions( const RenderModel& modelTested, const Vector3& velocity, const enum BoundingType& bt, const enum CollisionType& ct,   );

}; // WorldMap

bool WorldMap::testCollision( const RenderModel& modelTested, const Vector3& velocity, const enum BoundingType& bt, const enum CollisionType& ct ) {
// Here you would need different case statements based on bounding type
// as well as collision type you are using.

// The simplest for 2D is Circle against Circle, and you would return
// true or false if their radius intersects at the given moment of detection.

// Since this WorldMap Class has two containers of shared ptrs of Render Model Objects
// where one is static and their world positions are fixed and
// the other container are objects that can be moved around in the world;
// these two containers will help you simplify and reduce the number of calls to test for collisions.

// Since you know that the static container of objects will not move
// you do not have to test them against another static object.

// This leaves you with only testing Dynamic against Static and Dynamic against Dynamic.

// If you want to get a little more advanced you can still use Circle to Circle
// intersection and use the velocity direction vector to add in ray tracing
// and if that ray doesn't see any other object then you know this object
// will always return false and can skip it.

// If the ray does intersect into another object then this object will probably
// collide within a period of time.

// You would then return true when the collision happens.

} // testCollision


The nice thing about ray tracing is due to the fact that it looks ahead the entire time in that direction. If their are no bounding shapes in its sight then no collision will happen, this is cheaper then testing each object against every other object!