Ray OBB intersection

2022-08-11

We want to know if a given ray intersects a given oriented bounding box.

Let's look first at the most general case in 2D (we'll look at 3D after): A rectangle rotated and translated into world space by matrix mtw.


Our ray has two points in world space: a and b. The center of our box in world space is c. To transform this problem into an Axis-Aligned Bounding Box (AABB) problem: get a and b relative to c, then apply the reverse rotation:


Where invr is the inverse of the rotation component of mtw.


Our box has width=2 and height=4. But for this algorithm we only care about halfwidth=1 and halfheight=2.

2D Ray AABB intersection in C:

#include <math.h>

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))

struct FVec2 {
    float x, y;
};

int intersects2d(float halfwidth, float halfheight, struct FVec2 raybase, struct FVec2 raytip)
{
    struct FVec2 r;
    r.x = raytip.x - raybase.x;
    r.y = raytip.y - raybase.y;

    float tmin = -HUGE_VAL, tmax = HUGE_VAL;    /* HUGE_VAL constant from math.h */
    float t1, t2;

    t1 = (-halfwidth - base.x) / r.x;
    t2 = (halfwidth - base.x) / r.x;

    tmin = MAX(tmin, MIN(t1, t2));
    tmax = MIN(tmax, MAX(t1, t2));

    t1 = (-halfheight - base.y) / r.y;
    t2 = (halfheight - base.y) / r.y;

    tmin = MAX(tmin, MIN(t1, t2));
    tmax = MIN(tmax, MAX(t1, t2));

    return tmax > MAX(tmin, 0.0f);
}

So with our data, we can call intersects2d like so:

intersects2d(halfwidth, halfheight, a_final, b_final);

Because this algorithm operates on each axis individually, we can abstract it to any dimensional space with a for loop over the dimensions.

3D Ray AABB intersection in C:

union FVec3 {
    struct { float x, y, z; };
    float arr[3];
};

int intersects3d(union FVec3 boxScale, union FVec3 raybase, union FVec3 raytip)
{
    union FVec3 r;
    r.x = raytip.x - raybase.x;
    r.y = raytip.y - raybase.y;
    r.z = raytip.z - raybase.z;

    float tmin = -HUGE_VAL, tmax = HUGE_VAL;
    float t1, t2;

    for (int i = 0; i < 3; i++)
    {
        t1 = (-boxScale.arr[i] - base.arr[i]) / r.arr[i];
        t2 = (boxscale.arr[i] - base.arr[i]) / r.arr[i];

        tmin = MAX(tmin, MIN(t1, t2));
        tmax = MIN(tmax, MAX(t1, t2));
    }

    return tmax > MAX(tmin, 0.0f);
}

Using a union here lets us access FVec3 members with x,y,z as well as [0],[1],[2] via "arr".

boxScale is the vector (halfwidth, halfheight, halfdepth) for the 3D AABB.

We can avoid 3 floating point divisions by inverting r and switching the loop divisions to multiplications like so:

int intersects3d(union FVec3 boxScale, union FVec3 raybase, union FVec3 raytip)
{
    union FVec3 r;
    r.x = 1.0f / (raytip.x - raybase.x);
    r.y = 1.0f / (raytip.y - raybase.y);
    r.z = 1.0f / (raytip.z - raybase.z);

    float tmin = -HUGE_VAL, tmax = HUGE_VAL;
    float t1, t2;

    for (int i = 0; i < 3; i++)
    {
        t1 = (-boxScale.arr[i] - base.arr[i]) * r.arr[i];
        t2 = (boxscale.arr[i] - base.arr[i]) * r.arr[i];

        tmin = MAX(tmin, MIN(t1, t2));
        tmax = MIN(tmax, MAX(t1, t2));
    }

    return tmax > MAX(tmin, 0.0f);
}

Credit to Tavianator for the Ray AABB intersection algorithm.