Analysis

Introduction

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.