2021-01-19

[public] 119K views, 17.6K likes, 41.0 dislikes audio only

Reducible

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: https://www.patreon.com/reducible

Twitter: https://twitter.com/Reducible20

This video wouldn't be possible without the open source library manim created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

2D Collision Response Vector Equation Derivation Walkthrough: https://www.vobarian.com/collisions/2dcollisions2.pdf

Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: https://thegeneralsolution.wordpress.com/2011/12/13/broad-phase-collision-detection-bounding-volume-hierarchies-1/

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:

https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects

Game Physics Engine Development by Ian Millington Ch. 12

https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune

http://www.mcihanozer.com/tips/computer-graphics/collision-detection-related/uniform-grid-based/