AABB-AABB Intersection Test

1. The Broad Phase: Why Simple Boxes are Better Than Complex Meshes

Imagine two highly detailed 3D models, each with thousands of triangles. Checking if any triangle from the first model intersects with any triangle from the second is a computationally massive task. Doing this for every pair of objects in your scene every frame would bring even a powerful computer to a crawl.

Game engines solve this with a multi-stage process. The first stage, called the broad phase, uses very simple, fast checks to quickly rule out pairs of objects that are nowhere near each other. Only the objects that might be colliding pass on to more precise (and expensive) checks.

The most common bounding volume for this broad phase is the Axis-Aligned Bounding Box (AABB).

An AABB is a box whose faces are perfectly aligned with the primary coordinate axes (X, Y, Z). This "axis-aligned" constraint is crucial because it makes intersection tests incredibly fast.

2. Representing an AABB in Code

Before we can test for intersection, we need to decide how to represent an AABB in our C code. There are two common approaches:

1. Min/Max Points: Storing the coordinates of two opposing corners of the box: the corner with the minimum x, y, and z values, and the corner with the maximum x, y, and z values.
2. Center/Extents: Storing the coordinate of the box's center point, along with its "extents" (half of its width, height, and depth).

We will use the min/max representation because it makes the logic of the intersection test very intuitive. Let's define a struct for it. It's a good idea to create a new header file, like physics_types.h, for this and future physics-related data structures.

// In a new file, physics_types.h




#ifndef PHYSICS_TYPES_H
#define PHYSICS_TYPES_H




#include <cglm/cglm.h> // Assuming you have cglm for vector types

typedef struct {
    vec3 min;
    vec3 max;
} AABB;




#endif // PHYSICS_TYPES_H

This AABB struct will hold the two vectors that define our bounding box in 3D space.

3. The Logic of Intersection: The Separating Axis Theorem

How do we check if two AABBs overlap? The naive approach might involve checking if any of the 8 corners of one box are inside the other. However, this fails for cases where the boxes intersect without any corners being contained.

The correct and efficient method relies on a simple, powerful idea that is a specific case of the Separating Axis Theorem (SAT). It states:

Two AABBs intersect if, and only if, their intervals overlap on all three coordinate axes (X, Y, and Z).

If we can find even one axis where the boxes' projections do not overlap (a "separating axis"), then they cannot be intersecting.

As the video explains for 2D, we just need to check for overlap on each axis independently. For two intervals [min1, max1] and [min2, max2] on a single axis, they overlap if min1 <= max2 AND max1 >= min2.

To extend this to our 3D AABBs, we simply perform this check for the X, Y, and Z axes. If the condition is true for all three, the boxes are colliding.

4. Implementing the AABB vs. AABB Test in C

Now we can translate this simple logic directly into a C function.

With that understanding, here is the C implementation. You can place this in a new physics.c file and create a corresponding physics.h.

// In physics.h



#include <stdbool.h>
#include "physics_types.h"

bool aabb_intersect(const AABB* a, const AABB* b);


// In physics.c



#include "physics.h"

/**
 * Checks if two Axis-Aligned Bounding Boxes are intersecting.
 * @param a Pointer to the first AABB.
 * @param b Pointer to the second AABB.
 * @return true if they intersect, false otherwise.
 */
bool aabb_intersect(const AABB* a, const AABB* b) {
    // Two boxes intersect if and only if they overlap on all three axes.
    // We check for overlap on each axis.
    return (a->min[0] <= b->max[0] && a->max[0] >= b->min[0]) && // X-axis
           (a->min[1] <= b->max[1] && a->max[1] >= b->min[1]) && // Y-axis
           (a->min[2] <= b->max[2] && a->max[2] >= b->min[2]);   // Z-axis
}

This function is remarkably simple and fast, consisting of only six comparisons and two logical AND operations. This is why AABBs are the workhorse of broad-phase collision detection.

5. Testing Your Implementation

To test your new function, you don't need to render anything yet. You can simply define a few AABB structs in your main function and print the results of the intersection test.

// In main.c, after your includes:



#include <stdio.h>
#include "physics.h"

int main() {
    // ...

    // Case 1: Overlapping boxes
    AABB box1 = { .min = {0.0f, 0.0f, 0.0f}, .max = {2.0f, 2.0f, 2.0f} };
    AABB box2 = { .min = {1.0f, 1.0f, 1.0f}, .max = {3.0f, 3.0f, 3.0f} };
    
    if (aabb_intersect(&box1, &box2)) {
        printf("Case 1: Boxes are intersecting (Correct!)\n");
    } else {
        printf("Case 1: Boxes are NOT intersecting (Incorrect!)\n");
    }

    // Case 2: Non-overlapping boxes
    AABB box3 = { .min = {0.0f, 0.0f, 0.0f}, .max = {1.0f, 1.0f, 1.0f} };
    AABB box4 = { .min = {2.0f, 2.0f, 2.0f}, .max = {3.0f, 3.0f, 3.0f} };

    if (aabb_intersect(&box3, &box4)) {
        printf("Case 2: Boxes are intersecting (Incorrect!)\n");
    } else {
        printf("Case 2: Boxes are NOT intersecting (Correct!)\n");
    }

    // Case 3: Touching at the edge
    AABB box5 = { .min = {0.0f, 0.0f, 0.0f}, .max = {1.0f, 1.0f, 1.0f} };
    AABB box6 = { .min = {1.0f, 0.0f, 0.0f}, .max = {2.0f, 1.0f, 1.0f} };

    if (aabb_intersect(&box5, &box6)) {
        printf("Case 3: Boxes are touching (Correct!)\n");
    } else {
        printf("Case 3: Boxes are NOT touching (Incorrect!)\n");
    }

    // ... rest of your main function
}

Running this code should confirm your aabb_intersect function works as expected.

Conclusion

Congratulations! You have just implemented your engine's very first collision detection routine. While simple, this AABB vs. AABB test is a critical building block for creating interactive game worlds.

Key Takeaways:

• Collision detection is often done in phases, with a fast broad phase (like AABB tests) quickly eliminating non-colliding objects.
• An Axis-Aligned Bounding Box (AABB) is a non-rotated box used as a simple approximation of a complex object's shape for fast collision checks.
• AABBs are commonly represented in code by their min and max corner coordinates.
• Two AABBs intersect if and only if their projections overlap on all axes (X, Y, and Z). This is a special case of the Separating Axis Theorem.
• The C implementation of the intersection test is a single line of boolean logic, making it extremely efficient.

Preview of the Next Lesson:
AABBs are excellent for many objects, but they can be a poor fit for objects that are roughly spherical. For those, a different bounding volume is often better. In the next lesson, we will explore another fundamental collision check: implementing a Sphere vs. Sphere intersection test.