Contents
When you want to do real time computer physics, like what we see in games, you will have to break the world into understandable items. It’s like Caesar’s divide and conquer tactic. When you are playing in a complex scene, all what really goes on in the physics engine is broken into small, but many pieces. This enables further optimization down the line, which will be covered later, but for now this keeps the collision detection and collision response algorithms easy to understand.
However, now for the basic primitives.
The axis-aligned bounding box (AABB) is the most common bounding volume in collision detection algorithm. It is a rectangular 4-sided box in 2D and 6-sided box in 3D categorized by having its faces oriented along the coordinate system. The best property of AABB is it’s a fast collision check, which simply involves comparison of coordinates. This is the cheapest and fastest way to check for collision.
An axis aligned bounding box is mostly used in broadphase collision detection. That is, it’s used to group potential colliding objects to reduce calculation time, by excluding objects which are too far away in a very efficient manner.
There are three common representations for AABBs:
struct AABB { AABB() : min(), max() {} AABB(const Point & minPoint, const Point & maxPoint) : min(minPoint) , max(maxPoint) {} Point min; Point max; };
struct AABB { AABB() : min(), w() {} AABB(const Point & minPoint, const Point & width) : min(minPoint) , w(width) {} Point min; Point w; };
struct AABB { AABB() : c(), r() {} AABB(const Point & center, const Point & halfwidths) : c(center) , r(halfwidths) {} Point c; // center point Point r; // halfwidths };
In our tutorials we will be using the last AABB representation with a center point and halfwidth as this representation is the most efficient. The halfwidth values can be often stored in fewer bits than the corner position values. This representation also allows to test as a bounding sphere.
Collision detection algorithms implementation with AABB:
A sphere is another basic primitive and like AABB have inexpensive intersection test. Spheres has also a benefit of being very easy to transform. It is represented by a point, its center, and a radius.
struct Sphere { Sphere() : center(), radius() {} Sphere( const Point & center, double radius ) : center(center) , radius(radius) {} Point center; double radius = 0; };
Collision detection algorithms implementation with spheres:
An oriented bounding box is a cube or cuboid encapsulating one or more objects. There are many representations for OBBs:
The prefered way of representing OBBs is by a center point with matrix and three halfedge length as it allows for a cheaper intersection tests.
A cylinder is not a common volume found in physics engines. More often capsules are used to represent a cylinder. Cylinders intersection tests are quite expensive and that makes them less attractive as a bounding volum for collision detection.
Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.