Building Collision Simulations: An Introduction to Computer Graphics
466,472
Published 2021-01-19
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: www.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: www.vobarian.com/collisions/2dcollisions2.pdf
Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: thegeneralsolution.wordpress.com/2011/12/13/broad-…
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:
www.toptal.com/game/video-game-physics-part-ii-col…
Game Physics Engine Development by Ian Millington Ch. 12
github.com/mattleibow/jitterphysics/wiki/Sweep-and…
www.mcihanozer.com/tips/computer-graphics/collisio…
All Comments (21)
-
Dumb mistake alert: 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.
-
This guy's voice feels like a mix of 3b1b and zach star
-
Thank you for: A. Doing this work. B. Making it free. Awesome and inspiring.
-
28 minutes just flew by. Good job keeping viewers interested and focused
-
I was curious why the animation style was so similar to 3b1b, but I see from the description that he developed a custom library for animation for free use. Both of you guys are awesome.
-
Just wow! Really speechless. I still can't believe that in just 30 minutes you were able to cover from the very basics of animation, i.e. the frame by frame rendering, to complex techniques like object and space partitioning. Thank you soo much for these Amazinggg videos! Really looking forward to more CS Graphic and Animation oriented videos!
-
Im studying computer science, and when I was still 15 years old I coded up my first app, a collision based game. I "re-invented" the first 10 minutes of the video on my own and got all the bugs you mentioned one by one but in the end it was so close to the paradigm I was taught in university :D
-
Hey, very nice explanation! The Sweep and Prune algorithm offers a massive optimization despite how incredibly easy it is to implement. It's immensely useful in molecular dynamics along with the Bounding Volume boundary Hierarchy although the latter may be somewhat more tedious to implement.
-
This video is a fountain of knowledge. I never knew how continuous collision worked, and how game engines optimized their physics. I've heard about k-d trees (and bi/quad/oct trees) but didn't know how k-d trees worked. Glad I found this!
-
Finding your channel is a gem. I've been tasked to take charge of everything physics and collision for my group's game engine and chancing upon you on your GJK video and this lead me in a good direction, really appreciate you linking the resources you draw your knowledge from as that's where i get to learn more and attempt to implement them!
-
Thank you so much for covering this topic. You inspire me to study something new everyday. So wholesome. Thank you for doing everything. ❤️
-
I'm an animator professionally and it's fascinating to see the mathematical equivalent of all the processes I just intuitively do in my head. Great video!
-
Dude, your videos are pure gold. Computer Science students must LOVE you! Just a little note :D 2D particle-to-particle collision response closed formulas look hard and ugly, it is easier to deal with it by proceding by steps. First, split both v1 and v2 in two components, one parallel to the line of collision and the other tangent to it. You'll obtain 4 vectors: v1p, v1t, v2p and v2t. The final velocity vector for the first particle will be v1p + v2t, the final velocity vector for the second one will be v2p + v1t :) in other words: when two sphere collides, their velocity component tangent to the line of collision have to be swapped. This works if the two masses are the same but it is not that hard to take also that into account
-
massive respect for you and this channel. These videos must take so much time and effort, and you put it out completely free. We need more channels that make high quality content because they know how and have motivation, here's to another golden age of youtube led by channels like Reducible!
-
Amazing! Its so much easier to understand things when they are visualized and animated like this. Great work!
-
Just great content! I have always dreamt of creating content about computer science and computer graphics because I just love these topics. I realised that you are doing it a lot better than I will ever do and that's great, it makes me happy! Keep it up and thanks for your efforts :)
-
1- One of the best teaching videos on YouTube in terms of quality and content 2- The best video that simplifies collision detection approaches The guy is a genius! THANK YOU!!
-
Great video. Never realized how complicated collision detection could get!
-
Excellent tutorial! What suprises me is that you approach difficult concepts on a simple and understandable fashion. As a designer helps me a lot to learn all this background stuff which is hidden deep inside the bibliographies and PHDs. Hope to see more topics covered in the future such as Rigid Body Collisions extended on 3 Dimensions, Eulerian and Lagrangian Fluids and so on..
-
For the grid aproach you can keep only cells with at least 1 object in them in set/map with hash function based on their coordinates. This will allow you to have very good resolution without big memory footprint .
