Building Collision Simulations: An Introduction to Computer Graphics

An animated explanation of discrete and continuous collision detection algorithms and spatial partitioning optimization techniques.

Collision detection systems show up in all sorts of video games and simulations. But how do you actually build these systems? Turns out that the key ideas behind these systems show up all over a field of computer science called computer graphics. We start off with the basics of animation and then branch off into ideas in discrete and continuous collision detection. We break them down in the context of some simple simulations of a small number of particles, but scaling up these simulations is another challenge entirely. We present big ideas in broad phase optimization schemes for speeding up collision detection including the sweep and prune algorithm, uniform grids, K-D trees, and bounding volume hierarchies. 0:00 Introduction 1:25 Intro to Animation 2:46 Discrete Collision Detection and Response 5:50 Implementation 6:50 Discrete Collision Detection Limitations 8:10 Continuous Collision Detection 11:42 Two Particle Simulations 13:13 Scaling Up Simulations 15:42 Sweep and Prune Algorithm 19:05 Uniform Grid Space Partitioning 20:43 KD Trees 23:51 Bounding Volume Hierarchies 27:12 Recap Correction: At 9:02, the linear interpolation equations should be x(t) = t * x(1) + (1 - t) * x(0) and y(t) = t * y(1) + (1 - t) * y(0). All subsequent derivations have the x(0) switched with x(1). All y(0) should also be switched with y(1) for the same reason. Post-correction 2: I ran the experiment with the naive solution of checking every pair of particles with an added inefficiency in rendering the animations so the comparison wasn't fair and that's why the number was so high. The actual speed up is still fairly significant, but not THAT significant. Minor correction: p.vel is updated and used in the next line at 6:28, p.vel and p.pos should be updated simultaneously This video is supported by a community of Patreons Special Thanks to the following Patreons: Burt Humburg Justin Hiester Michael Nawenstein Richard Wells Zac Landis Support: patreon.com/reducible Twitter: twitter.com/Reducible20 This video wouldn't be possible without the open source library manim created by 3blue1brown: github.com/3b1b/manim Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible 2D Collision Response Vector Equation Derivation Walkthrough: vobarian.com/collisions/2dcollisions2.pdf Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: thegeneralsolution.wordpress.com/2011/12/13/broad-phase-coll… The ideas and presentation in this video were inspired by a culmination of resources -- here are some that I found particularly nice for further exploration: toptal.com/game/video-game-physics-part-ii-collision-detecti… Game Physics Engine Development by Ian Millington Ch. 12 github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune mcihanozer.com