The Seperating Axis Theorem.

The separating axis theorem is one of the most useful things to know when programming collision detection. The separating axis shows that if you project the extents of the convex object in the direction of the axis and they do not overlap, then they do not intersect. If they do overlap and the objects are convex then the objects intersect.

Below is an example of the separating axis theorem test for AABB v.s AABB (Axis aligned bounding box).

SAT

Implementing SAT for Box V.S Box collision.

The separating axis theorem is useful for intersection tests against two oriented bounding boxes. Below is a 2D picture for easy illustration. First calculate the projection interval radius. What this means is that for every half size of each object, project it onto the axis.  We need to use 15 SATs to test the objects for intersection. 6 for the faces on the boxes excluding parallel faces. 9 for the edges on the boxes, excluding parallel edges.

SAT_Box2

Below is C++ code to test box vs box intersection using the above method.

static inline real
transformToAxis(const CollisionBox &box, const Vector3 &axis)
{
	/*
		Compute the projection interval radius.
	*/
	return box.halfSize.x * real_abs(axis * box.getAxis(0)) +
		box.halfSize.y * real_abs(axis * box.getAxis(1)) +
		box.halfSize.z * real_abs(axis * box.getAxis(2));
}
/*
	This function checks if the two boxes overlap
	along the given axis. The final parameter toCenter
	is used to pass in the vector between the boxes center
	points, to avoid having to recalculate it each time.
*/
static inline bool
overLapOnAxis(const CollisionBox &one, const CollisionBox &two,
	const Vector3 &axis, const Vector3 &toCenter)
{
	// Project the half-size of one onto axis.
	real oneProject = transformToAxis(one, axis);
	real twoProject = transformToAxis(two, axis);

	// Project this onto the axis.
	real distance = real_abs(toCenter * axis);

	// Check for overlap
	return (distance < oneProject + twoProject);
}
/*
	This preprocessor definition is only used as a convenience
	in the boxAndBox intersection method.
*/
#define TEST_OVERLAP(axis) \
overLapOnAxis(one, two, (axis), toCenter)

bool IntersectionTests::boxAndBox(const CollisionBox &one,
 const CollisionBox &two)
{
	// Find the vector between the two centers.
	Vector3 toCenter = two.getAxis(3) - one.getAxis(3);

        return(
		// Check on box one's axis first.
		TEST_OVERLAP(one.getAxis(0)) &&
		TEST_OVERLAP(one.getAxis(1)) &&
		TEST_OVERLAP(one.getAxis(2)) &&

		// And on two's
		TEST_OVERLAP(two.getAxis(0)) &&
		TEST_OVERLAP(two.getAxis(1)) &&
		TEST_OVERLAP(two.getAxis(2)) &&

		// Now on the cross products. Eedge-Edge axis test.
		TEST_OVERLAP(one.getAxis(0) % two.getAxis(0)) &&
		TEST_OVERLAP(one.getAxis(0) % two.getAxis(1)) &&
		TEST_OVERLAP(one.getAxis(0) % two.getAxis(2)) &&
		TEST_OVERLAP(one.getAxis(1) % two.getAxis(0)) &&
		TEST_OVERLAP(one.getAxis(1) % two.getAxis(1)) &&
		TEST_OVERLAP(one.getAxis(1) % two.getAxis(2)) &&
		TEST_OVERLAP(one.getAxis(2) % two.getAxis(0)) &&
		TEST_OVERLAP(one.getAxis(2) % two.getAxis(1)) &&
		TEST_OVERLAP(one.getAxis(2) % two.getAxis(2))
		);
}
#undef TEST_OVERLAP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s