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.
Referencess
Ericson, C. & Sony Computer Entertainment America. (2005). Real-Time Collision Detection. In The Morgan Kaufmann Series in Interactive 3D Technology. Morgan Kaufmann Publishers. https://www.r-5.org/files/books/computers/algo-list/realtime-3d/Christer_Ericson-Real-Time_Collision_Detection-EN.pdf
Skeffles. (2022, April 17). How 2D game collision works (Separating axis theorem) [Video]. YouTube. https://www.youtube.com/watch?v=dn0hUgsok9M
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.
for (auto* c : currentScene->GetColliders())
c->is_intersecting = false;
for (int i = 0; i < currentScene->GetColliders().size(); i++)
{
for (int j = i + 1; j < currentScene->GetColliders().size(); j++)
{
naive_checks++;
if (currentScene->GetColliders()[i]->intersects(*currentScene->GetColliders()[j]))
{
naive_collisions++;
currentScene->GetColliders()[i]->is_intersecting = true;
currentScene->GetColliders()[j]->is_intersecting = true;
}
}
}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.
In order to continue, I had to come up with a method for populating the Octree. For this, I followed Ericson’s straddling‑based insertion approach. The principle behind it is simple: if the object is not contained completely in a child node (it overlaps with one or more of the node's separating planes), it is stored at the current node. If it does fit in cleanly, the insertion continues recursively until it is inserted into the appropriate child. The octant index is calculated by considering the placement of the center of the object on each axis (left or right on X-axis, below or above on Y-axis, behind or in front on Z-axis) relative to the center of the node. The three comparisons create a 3-bit index (0 to 7) which selects the right child node. This technique guarantees that objects will be put as deep as possible in the tree without breaking the rule of spatial correctness and without forcing objects into nodes that do not belong.
How insertion works:
void Octree::insert(Node* node, CubeCollider* collider)
{
int index = 0;
bool straddle = false;
for (int i = 0; i < 3; i++) {
float delta = collider->transform.position[i] - node->center[i];
if (fabs(delta) < node->half_width + collider->size) {
straddle = true;
break;
}
if (delta > 0.0f) index |= (1 << i); // ZYX
}
if (!straddle && node->child[index]) {
insert(node->child[index], collider);
} else {
node->colliders.push_back(collider);
}
}This approach was not suitable for OBBs, however, since the extent of an OBB along an axis is influenced not only by the size of the OBB, but also by its orientation. The correct way to do this is to calculate the OBB’s orthographic radius on each node axis of the octree. I could use the OBB's half‑sizes and the dot products of the OBB's orientation matrix against the X, Y, and Z planes to accurately determine if the OBB overlaps a plane of division. This radius will provide proper straddling for rotated boxes and will only place an object in children nodes when it is a complete fit in one octant. The only downside of this method is that it requires a few additional dot-product calculations, but the accuracy gained is essential for handling rotated objects correctly.
void Octree::insert(Node* node, CubeCollider* collider)
{
OBB obb = collider->get_OBB();
int index = 0;
bool straddle = false;
for (int i = 0; i < 3; i++) {
float delta = obb.center[i] - node->center[i];
float projectedRadius =
fabs(obb.axes[0][i]) * obb.halfSize.x +
fabs(obb.axes[1][i]) * obb.halfSize.y +
fabs(obb.axes[2][i]) * obb.halfSize.z;
if (std::fabs(delta) < projectedRadius) {
straddle = true;
break;
}
if (delta > 0.0f) index |= (1 << i); // ZYX
}
if (!straddle && node->child[index]) {
insert(node->child[index], collider);
} else {
node->colliders.push_back(collider);
}
}Once the Octree is populated, the next step is to efficiently detect collisions between the colliders stored in its nodes. The collision‑checking function performs this in three stages: intra-node checks, parent-child checks, and sibling checks, followed by a recursive descent into the child nodes. This ensures that all potentially intersecting pairs are tested exactly once, without falling back to the naive O(n²) approach.
Intra‑node collision checks:
for (size_t i = 0; i < node->colliders.size(); i++)
{
for (size_t j = i + 1; j < node->colliders.size(); j++)
{
octree_checks++;
if (node->colliders[i]->intersects(*node->colliders[j]))
{
octree_collisions++;
node->colliders[i]->is_intersecting = true;
node->colliders[j]->is_intersecting = true;
}
}
}Parent-Child collision checks:
for (int c = 0; c < 8; c++)
{
Node* child = node->child[c];
if (!child) continue;
for (CubeCollider* a : node->colliders)
for (CubeCollider* b : child->colliders)
{
octree_checks++;
if (a->intersects(*b))
{
octree_collisions++;
a->is_intersecting = true;
b->is_intersecting = true;
}
}
}Sibling collision checks:
for (int a = 0; a < 8; a++)
{
Node* A = node->child[a];
if (!A) continue;
for (int b = a + 1; b < 8; b++)
{
Node* B = node->child[b];
if (!B) continue;
for (CubeCollider* ca : A->colliders)
for (CubeCollider* cb : B->colliders)
{
octree_checks++;
if (ca->intersects(*cb))
{
octree_collisions++;
ca->is_intersecting = true;
cb->is_intersecting = true;
}
}
}
}Finally, the function recursively processes each child node. This ensures that the entire tree is traversed and that collision checks are performed at every level.
With this done, I had met my initial goal, but I wasn't satisfied with the performance. This made me consider whether there was any further optimisation possible for this structure. A natural next step was a loose octree, where the range was not necessarily a cube, but was still represented as an octree, but one with additional data stored. The strict octree already gave all the required data and structure, while the additional data was relatively easy to add in: just a looseness factor, which in most of the cases extends the reach of a node by x2. This expansion enables other objects that otherwise would require more than one child to be easily contained within the sole child. In consequence, a lot less is stored at higher levels of the tree and many fewer straddling cases.
This structural change can directly affect the performance. A strict octree contains lots of OBBs that overlap node boundaries, particularly OBBs that are rotated, which cannot be deeply inserted into the tree. They are stored in parent nodes, which leads to more levels of collision checking at higher levels. The other extreme is the loose octree, which avoids these overlaps of boundaries and can have most of its child nodes expanded, thus placing most objects far down the tree. With these larger nodes, objects now descend deeper into the tree, giving the partitioning more discriminatory power (Ericson, 2005). This results in smaller collider lists per node, fewer parent/child checks, and fewer checks between siblings, and ultimately in an efficient overall broad-phase. The advantage of the loose octree is that it often requires a large memory increase because the volume of the nodes is increased, but on the other hand, the number of collision checks can be significantly reduced, particularly when there are many dynamic and/or rotated objects in the scene.
The benchmarking tool is used to evaluate the performance of the collision detection system with various configurations. It has the ability to compare the naive SAT approach, the strict Octree, and the loose Octree in a consistent and repeatable manner, as it stores the results of performance measurements obtained over a fixed number of frames. The tool is separate from simulation logic and will only watch the engine while there are no interactions between the measurement and the results. The program initializes a benchmark run with a number of frames the tool should record and a label for the mode (Naive, Strict Octree, Loose Octree). Once turned on, it goes into a recording mode, accumulating data each frame. It keeps the FPS, the millisecond time taken to each frame, and the number of collisions performed by the collision system that is active. Values are added onto internal history buffers until the desired number of frames has been reached. When the recording finishes, an auto-generated CSV file is created. The file is structured as a table of one row per frame and followed by a metadata header with the collision mode and number of cubes. The FPS, frame time, and number of collision checks are shown in each row. The results stay fit in this compact format, which helps it to be loaded into spreadsheets or plotting tools to visually compare results. The benchmarking tool emphasizes the simplicity of the system - only the essential timing and collision check data are recorded, and then exported in a clean format - in order to create a solid baseline assessing the performance characteristics of all the implemented collision detection strategies during the project.
void Benchmark::update(float delta_time, int cube_count, int collision_checks)
{
if (!is_recording) return;
fps_history.push_back(1.0f / delta_time);
ms_history.push_back(delta_time * 1000.0f);
collision_checks_history.push_back(collision_checks);
frame_count++;
if (frame_count >= target_frames)
{
is_recording = false;
double currentTime = glfwGetTime();
save("benchmarks/fps_output_" + std::to_string(currentTime) + ".csv", cube_count);
}
}
The first benchmark is the time it takes to perform the three collision detection methods using a naive SAT with a nested loop, strict octree, and loose octree (per frame, tested on 440 cubes). Across the full range of samples, the naive approach consistently sits an order of magnitude higher in cost - between 15-30ms per frame, often with sharp spikes across the entire sample set. The strict octree is still in the range of 2–5 ms with occasional peaks, while the loose octree is still near 1 ms and is in the most stable range of the three. This clearly shows that both octree‑based methods drastically reduce the time spent on collision detection compared to the naive method, with the loose octree offering the best raw performance, at the cost of some precision.
The second benchmark aims to build upon this and explore how many objects can be simulated at 60 frames per second (fps) by each method. If the seeds, objects are distributed into, and the maximum depth on the octree is 4, the naive method can maintain 60 FPS around 440 objects, the strict octree will have about 1230 objects, and the loose octree will have about 6230 objects. The naive and strict octree gives nearly the same and very precise collisions, while the loose octree gives fewer collision checks, and sometimes it does not detect collisions because of its loose spatial restriction.
A separate depth test is performed, resulting in the lowest and most stable delta time found at depths of 3 and 4, with good performance precision at a depth of 4. A shallower tree would overload nodes, and a deeper tree would add unnecessary overhead.
The current limits are also affected from a rendering point of view, such as the number of draw calls. The actual object ceiling is much higher, as with instancing and batching, many more cubes can be rendered while not impacting the performance of collision on the CPU.
Finally, a dedicated stress test with a loose Octree at a depth of 4 showed that the system can render and process collision checks for approximately 300000 colliders with 0.1FPS, which is very impressive considering the number of colliders a typical real-time game may contain.