Basic primitives

By , last updated October 8, 2016

Introduction

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.

Axis aligned bounding box (AABB)

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.

Axis aligned bounding box

A bounding box encapsulating other objects.

There are three common representations for AABBs:

  1. Minimum and maximum coordinate values along each axis.
    min max points aabb basic primitive aligned box

    struct AABB
    {
        AABB() : min(), max() {}
     
        AABB(const Point & minPoint, const Point & maxPoint)
            : min(minPoint)
            , max(maxPoint)
        {}
     
        Point min;        
        Point max;        
    };
    
  2. Minimum corner point and the width or the diameter from the corner.
    min width points aabb basic primitive aligned box
  3. struct AABB
    {
        AABB() : min(), w() {}
     
        AABB(const Point & minPoint, const Point & width)
            : min(minPoint)
            , w(width)
        {}
     
        Point min;        
        Point w;        
    };
    
  4. Center point C and halfwidth extents or radius.
    center radius points aabb basic primitive aligned box

    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:

Sphere

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.

Sphere, with center and a radius r.

Sphere, with center and a radius r.

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:

Cube, cuboid or oriented bounding box OBB

An oriented bounding box is a cube or cuboid encapsulating one or more objects. There are many representations for OBBs:

  1. A collection of eight vertices
  2. A collection of six planes
  3. A collection of three slabs (a pair of parallel planes)
  4. A corner vertex and three mutually orthogonal edge vectors
  5. A center point, an orientation matrix and three halfedge length

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.

Cube / hexahedron

Cube / hexahedron

Cylinder

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.

Cylinder

Cylinder

Capsule

Capsule

Capsule

Convex mesh

Convex hull

Convex hull

Concave mesh

Concave mesh

Concave mesh

Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.

Comments

Be the first to comment.

Leave a Reply


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*