Collision Detection Essentials

Collision detection is one of those systems that sits at the intersection of almost everything in interactive graphics. Physics simulations depend on it to know when to apply forces. Game logic depends on it to trigger events. AI systems depend on it to navigate environments. Rendering systems depend on it for techniques like shadow casting and occlusion culling. Without reliable collision detection, none of these systems can function correctly. It's not a feature you add at the end of a project. It's infrastructure that everything else is built on top of.

Consider a simple example: a player character walking across uneven terrain. For that to work correctly, the engine needs to know at every frame whether the character's feet are touching the ground, whether they're about to step off a ledge, and whether there's a wall blocking their path. Each of those checks is a collision query. In a complex scene with dozens of characters, hundreds of environmental objects, and dynamic elements like falling debris, the number of collision queries per frame can reach into the tens of thousands. The performance cost of getting this wrong is enormous.

The consequences of poor collision detection go beyond visual glitches. In physics-based simulations, missed collisions can cause objects to gain energy incorrectly, leading to unstable behavior that compounds over time. In competitive games, collision inconsistencies can create fairness problems where one player's experience differs from another's. In safety-critical simulations used for training or engineering, inaccurate collision results can lead to genuinely wrong conclusions. The stakes vary by application, but the need for correctness is universal.

There's also a performance dimension that's easy to underestimate. A naive collision detection system that checks every object against every other object scales at O(n²), meaning that doubling the number of objects quadruples the number of checks. A scene with 1,000 objects would require roughly 500,000 checks per frame. At 60 frames per second, that's 30 million checks every second, most of which will find no collision at all. The entire field of collision detection optimization exists to solve this problem, and the solutions are elegant and worth understanding deeply.^[1]

Modern game engines like Unity and Unreal Engine provide built-in collision systems, and it's tempting to treat them as black boxes. But relying on a black box means you can't diagnose problems when they appear, can't tune performance for your specific use case, and can't extend the system when your project's needs go beyond what the defaults provide. Understanding the underlying algorithms gives you the ability to use these tools more effectively and to build custom solutions when you need them.

Collision detection also connects directly to the user experience in ways that are hard to quantify but easy to feel. A character controller that responds crisply to terrain, a physics object that bounces realistically off a surface, a projectile that registers a hit at exactly the right moment: these details accumulate into an overall sense of quality and responsiveness. Players and users may not be able to articulate why one application feels better than another, but collision fidelity is often a significant part of the answer.

Finally, collision detection is a domain where the gap between theory and practice is unusually wide. Academic resources cover the mathematics thoroughly, but real-world implementations involve tradeoffs, edge cases, and performance constraints that textbooks rarely address. This book aims to bridge that gap by grounding every concept in practical context, showing not just how algorithms work but when to use them, when to avoid them, and how to adapt them to real project requirements.

This book covers collision detection from the ground up, starting with the geometric and mathematical foundations and progressing through increasingly sophisticated algorithms and optimization strategies. The focus is on real-time applications, meaning the techniques discussed are chosen for their practical performance characteristics, not just their theoretical elegance. Every major topic is accompanied by concrete examples and implementation guidance.

The first two chapters establish the foundation. Chapter 1: Geometric Foundations covers the mathematical building blocks you'll use throughout the book: points, vectors, distances, dot products, and cross products. If you're already comfortable with linear algebra, this chapter will serve as a quick refresher and a chance to see how these concepts apply specifically to collision problems. If some of this is new to you, the chapter provides enough grounding to move forward confidently.

Chapter 2: Collision Primitives introduces the geometric shapes that form the basis of most collision systems. These include:

• Spheres and circles, which are the simplest and fastest primitives to test
• Axis-Aligned Bounding Boxes (AABBs), which are efficient and widely used for broad-phase detection
• Oriented Bounding Boxes (OBBs) and capsules, which offer better fit for non-axis-aligned objects
• Triangles and mesh primitives, which are necessary for accurate collision with complex geometry

Chapters 3 and 4 cover the two-phase detection model that underlies most high-performance collision systems. Chapter 3: Broad-Phase Detection Strategies explains how to quickly eliminate pairs of objects that can't possibly be colliding, using spatial partitioning structures like grids, octrees, and bounding volume hierarchies (BVHs). Chapter 4: Narrow-Phase Collision Algorithms then covers the precise tests applied to the candidate pairs that survive the broad phase, including sphere-to-sphere, AABB, OBB, and mixed primitive tests.

Chapter 5: Mesh and Triangle Collision goes deeper into collision detection with complex geometry. This includes triangle-to-triangle intersection tests, ray casting techniques, and mesh-to-mesh detection strategies. These methods are computationally expensive compared to primitive-based approaches, so the chapter also discusses when they're necessary and how to use them efficiently.

Chapter 6: Continuous Collision Detection addresses one of the most common failure modes in real-time systems: fast-moving objects that pass through thin geometry between frames. This phenomenon, known as tunneling, requires a fundamentally different approach to detection. The chapter covers swept volumes, trajectory analysis, and time-of-impact calculations that prevent tunneling without sacrificing performance.

The final two chapters focus on making collision systems work well in practice. Chapter 7: Performance Optimization covers caching strategies, early termination techniques, and GPU-accelerated collision detection. Chapter 8: Implementation Patterns and Best Practices addresses system architecture, data structure choices, and the often-overlooked topic of debugging and testing collision code. These chapters are where the theoretical knowledge from earlier chapters gets translated into production-quality systems.

What this book does not cover is equally worth noting. It does not cover physics response in depth: what happens after a collision is detected, such as impulse resolution, friction modeling, or constraint solving, is a separate discipline with its own extensive literature. It also does not cover collision detection in 2D exclusively, though many of the concepts apply directly. The focus is on 3D real-time graphics, with 2D examples used occasionally for clarity.

This book is designed to be read sequentially, but it's also structured so that individual chapters can stand on their own as references. If you're new to collision detection, reading from start to finish will give you the most coherent learning experience. Each chapter builds on concepts introduced in earlier ones, and the progression from foundations to optimization mirrors the way you'd approach building a real collision system from scratch.

If you're coming to this book with a specific problem in mind, here's a quick guide to finding what you need:

• If your objects are passing through each other at high speeds, go to Chapter 6 on continuous collision detection first.
• If your collision system is too slow for your scene size, start with Chapter 3 on broad-phase strategies and Chapter 7 on optimization.
• If you're not sure which primitive shapes to use for your objects, Chapter 2 will help you make that decision.
• If you're getting incorrect collision results and can't figure out why, Chapter 8 on debugging and testing is the right starting point.
• If you need to implement ray casting for picking, line-of-sight, or projectile detection, go to Chapter 5.

The code examples throughout this book are written in a pseudocode style that maps closely to C++ and similar languages commonly used in graphics development. The goal is clarity over language-specific syntax. You should be able to translate these examples into your language of choice without significant difficulty. Where specific data structures or APIs are referenced, the concepts are explained in enough detail that you can adapt them to your own environment.

Each chapter ends with a summary of key concepts and a set of practical exercises. The exercises are not busywork. They're designed to surface the edge cases and implementation challenges that are easy to miss when reading passively. Working through them, even partially, will significantly deepen your understanding. Some exercises ask you to implement a specific algorithm; others ask you to analyze a scenario and choose the right approach. Both types reflect the kinds of decisions you'll face in real projects.

A note on mathematics: this book assumes you're comfortable with basic linear algebra, including vectors, matrices, and coordinate systems. If you can compute a dot product and understand what a normal vector is, you have enough background to follow along. Where more advanced mathematics appears, it's introduced gradually with enough explanation to make it accessible. The goal is never to impress with mathematical complexity but to give you the tools you actually need.

The best collision detection system is the one that's accurate enough for your use case, fast enough for your performance budget, and simple enough for your team to maintain. There's no universal best solution, only informed tradeoffs.

That principle runs through every chapter of this book. Collision detection is a field full of specialized algorithms, each with its own strengths and weaknesses. The goal isn't to memorize all of them. It's to understand the tradeoffs well enough to make good decisions for your specific situation. A sphere-based collision system that runs at 120 frames per second is often better than a mesh-based system that runs at 40, even if the sphere system is less geometrically precise. Context matters enormously.

You'll also find that many of the concepts in this book connect to broader topics in computer graphics and software engineering. Spatial partitioning structures like octrees appear in rendering pipelines for frustum culling. Ray casting is used for both collision detection and rendering techniques like ambient occlusion. Bounding volume hierarchies are used in ray tracing acceleration structures. Understanding collision detection deeply will make you a better graphics developer overall, not just a better collision programmer.

One practical recommendation: as you read, keep a project in mind. It doesn't have to be a large or complex project. Even a simple scene with a few moving objects is enough to give you a concrete context for applying what you learn. The difference between reading about sphere-to-sphere collision detection and actually implementing it, running it, and watching it work is significant. Theory becomes intuition through practice, and intuition is what lets you solve problems quickly when they appear in production.

Finally, don't be discouraged if some of the mathematics feels unfamiliar at first. Collision detection draws on geometry and linear algebra in ways that can feel abstract until you see them in action. The moment when a dot product stops being a formula and starts being a tool for measuring alignment, or when a bounding volume hierarchy stops being a data structure and starts being a way of thinking about space, is a genuine breakthrough. This book is designed to help you reach those moments as efficiently as possible, with clear explanations, concrete examples, and a focus on the practical over the theoretical.

The chapters ahead cover a lot of ground, but every concept is there for a reason. By the time you reach the conclusion, you'll have a complete picture of how collision detection works, why it works that way, and how to build systems that are both correct and fast. That's a powerful combination, and it's one that will serve you across every graphics project you work on going forward.