Analysis
Collision detection is an essential feature of any real-time rendering system and game engine. It allows objects to interact physically and prevents them from passing through each other. Modern engines typically combine narrow phase algorithms, which compute precise intersections between shapes, with broad phase spatial partitioning structures that reduce the number of required checks (Ericson, 2005). The Separating Axis Theorem (SAT) is one of the most popular narrow phase methods for oriented bounding boxes (OBBs). It provides a mathematically robust way to determine whether two convex shapes intersect by projecting them onto a set of candidate axes (Skeffles, 2022). SAT is particularly useful in 3D engines because it handles rotated objects efficiently and produces reliable results even under continuous motion.
However, SAT becomes extremely expensive when applied to large numbers of objects, since the naive implementation requires O(n²) checks. In order to deal with this, most engines use a hierarchical spatial partitioning structure, where the world is partitioned into smaller regions/chunks. Using Octree and inserting objects into it, the engine can check for collisions with only the objects within the same node or its neighbors. This significantly reduces unnecessary comparisons. This broad phase acceleration is essential for maintaining real-time performance as scene complexity increases, especially in simulations with hundreds or thousands of dynamic objects.
For this project, I implement OBB collision detection using the traditional SAT approach, described by Ericson (2005), combined with both strict and loose Octree variants to evaluate their performance characteristics. The goal is to measure how Octree depth, node size, and looseness influence the number of collision checks and overall frame time. These experiments reflect common engine development concerns, where balancing accuracy and performance is crucial for scalable real-time systems.
Since I was going to start implementing the collision detection system, I wanted to first get to know the basics of how collision detection works and what methods are used in most real-time engines. The starting idea was to have a basic Axis-Aligned Bounding-Box (AABB) collision system with the help of SAT. When I met with my professor, however, we discussed this, and I was told not to bother with the AABB stage at all. However, an AABB, being less general and less applicable to the purposes of the project, seemed to be a more complicated problem to deal with than Oriented Bounding-Box (OBB) collision detection, and so would be simpler to avoid altogether.
For this, I developed a class CubeCollider which holds all the data that is needed for an oriented bounding box: Position, the 3 local axes, and scale. This class also introduces a method that establishes SAT theory in code and prints both OBBs on the 15 candidate axes, and determines whether a separating axis exists or not. If there is no axis of separation, then the two colliders overlap.
I wanted to test that the implementation of the SAT is correct, so I added it to a naive collision detection loop in main.cpp. This loop runs through all of the colliders in the scene and performs an O(n²) baseline. While this is a very inefficient method, it is important for creating a baseline; all future optimizations, including the Octree, are compared to this naive approach to gauge performance gains.
After this was done, I created an Octree data structure, splitting the world into spatial regions, so that after doing that, I can do fewer checks and remove pairs that can't intersect just because they are too far away. The first thing was the creation of this Octree structure, and each node correctly representing a region of space that had been subdivided. I reused my own CubeCollider rendering system, and I made it so each Octree node can be rendered like a wireframe cube, making debugging simpler. This allowed me to verify that the object was placed in the right nodes and the tree was split as anticipated. Now that there's an Octree, the naive O(n²) loop could be turned into a “broad phase pass”, where we would only have to check the colliders in the same node or adjacent nodes, drastically cutting the number of SAT checks per frame.
