Building Collision Simulations: An Introduction to Computer Graphics
ฝัง
- เผยแพร่เมื่อ 28 พ.ค. 2024
- 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: / reducible
Twitter: / 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/2...
Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: thegeneralsolution.wordpress....
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-gam...
Game Physics Engine Development by Ian Millington Ch. 12
github.com/mattleibow/jitterp...
www.mcihanozer.com/tips/comput...
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.
Hello, Can you please upload a tutorial based on Hash-Map and Trie? All of the contents in this channel are so enriched. Thanks for your effort man.
@@AnimationMovieLover We want videos on trie
I spent a couple of hours googling things and trying to work out what I’d misunderstood. I kept getting x at the end of the line for time 0 and x at the beginning of the line for time 1. Wish i’d have spent 5 seconds scrolling down to read the comments 😂🤦♂️
Big brain
Question about those equations, how did you derive them? That's the moment I get lost in the video is when you showed those equations but I haven't a clue how the linear interpolation equations were derived. They seem simple enough that I should be able to derive them myself but I haven't been able to. Even just a hint in the right direction would be useful.
This guy's voice feels like a mix of 3b1b and zach star
YES
Factor in his outstanding use of Manim, and he's basically the 3b1b of computer science
and Isaac Arthur
My first thought was exactly, "this reminds me of 3B1B" :D
@@Greedygoblingames So much so that I think he should at least select a different font. This one is now the irreversible signature of 3b1b. ☺️
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
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!
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.
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
That "re-invention" feeling is one of the coolest aspects of learning this stuff.
@@Reducible i cant agree more haha
What software/program did you use to write the code in?
What program did you use to make the simulation animations?
@@arshawitoelar7675 No animation program. Everything was frame by frame drawn with OpenGL in Java (lwjgl) and I was probably programming in Eclipse IDE. Paint.net software for any art
@@alegian7934 I see, thank you so much
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.
What do they use for n-body simulations? You can't use Sweep and Prune since forces never die out to zero.
@@looksintolasers Depending on how quickly the interaction force decays with the distance, you can still use a variation of the Sweep and Prune method, with a larger interval surrounding the particles.
To compute the force on distant particles, instead of iterating for each particle, you can encapsulate a large number of particles in a single cell, and compute the interaction via a multipole expansion approximation.
One of the most used optimization techniques in n body simulations is called "Barnes-Hut method" if you want to look for information about it :)
@@looksintolasers For short range interaction (or very short meaning no action at a distance with only friction and collision as in granular material) you can also use Verlet list. The idea is simple but need some careful tuning to guarantee that your system will not blow up and produce artefacts : you setup a cutoff distance beyond which you assume the magnitude of your force is negligible compare to the effect of the one resulting from interaction with other particles within the cuttof distance range (and thus not affecting the dynamics of your system), which is natural when no forces at a distance are present. You build a list for each particle of possible neighbor candidates within that range and maintain it for a finite amount of steps. On these steps you don't have to update that list because you have chosen the right cutoff distance such that no particles outside the list can be a candidate for a collision between two consecutive updates. Check the verlet list wikipedia page for more details. This algorithm is very handy because it can be "nested" : you can make "super verlet list" with another bigger cut off distance to make a bigger list you will update at a lower frame rate,and use it to feed your "inside" verlet list such that you update it only by iterating over particles in the super verlet list. And so on. Hope my description is sort of clear but this is the "broad idea" : careful tuning according to the dynamics of your system and you don't have to iterate over all pairs of particles at each time step. It's sort of "caching" candidates for collision over a certain amount of time steps : )
Nevertheless,in molecular dynamics many algorithms exist to handle collision efficiently and the right one to choose depends mainly of the dynamics of your system and its collision rate : ) Verlet list for example is well suited for dense particle systems
@@looksintolasers In practice,you will always have to assume that forces go out to zero at some point. Like you say, gravity, it never ends. Nevertheless you can still make real satisfactory predictions about the motion of solar system planets without considering influence of distant galaxies on it. Or the influence of Mars on any apple that fall to the ground. Yet, the influence of Mars exists. But we can safely disregard its effect compare to earth attraction. In numerical simulation you "can compute everything". But it is mainly useless. You can compare contribution to the net effect and disregard contribution you can say "are too small". Otherwise, it is just garbage contribution to the real effect your are trying to measure. At that point the integration scheme for computing your motion is already probably bringing worse numerical errors to your measures that the one resulting from "neglecting infinitly small effects"
@@Galileo51Galilei the problem I'm having with gravity on small scale is while the protons approach they get more simulation ticks to accelerate. This makes them depart with faster velocity. So on their departure, they get less simulation ticks to slow down.
So kinetic energy sometimes increases too much, especially when the protons get really close.
Any ideas?
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
Thank you! Yeah, I think the reason I was having so much trouble with it is I was messing with angular representations and it wasn't immediately clear to me how to solve it with an angle-free representation. Like I said, pretty rusty on my physics :P Thanks for this comment!
Thank you so much for covering this topic. You inspire me to study something new everyday. So wholesome. Thank you for doing everything. ❤️
+1
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!
13:23 you can see one of the blue particles in the right box getting stuck to a yellow particle and briefly getting slingshot around. same thing happens again at 14:37 between a red and yellow particle.
it looks like the reason this happens is that, during the 1st half of the simulation frame, when two particles are first moved, they penetrate each other at very grazing angles, the 2 particles overlap but already have velocities that would move them away from each other. the collision handling doesn't account for the fact that the two particles are already moving away from each other and just unconditionally reflect both particles' velocities along the collision normal. This results in the velocities deflecting slightly inwards to the opposing particle and remain nearly tangent to that particle's surface.
This continues until the particles reach a sweet spot frame when the next position update would fully depenetrate the 2 particles.
How did you find it? I was looking for any blue particles close to yellow particles at the timestamp and had to pause the video to find it.
@@PanDiaxik all the particles move in straight lines, the slingshot particles move in a brief curve. To me its just eyecatching to see 2 particles move differently from the others even just briefly
Yeees, I have seen it. It's kinda funny
Is it possible now to aim and accelerate particles to merge them 😅?
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!
Fun fact: The tunneling problem is the reason that particles in this simulation that we are currently in, more commonly known as the universe, has a maximum speed limit--what we call the speed of light.
This also explains why we sometimes observe quantum tunneling effects to occur, if the barricade is made too thin. This is clearly a bug in the universe's source code, and as such I wouldn't recommend anyone building any technology that rely on that particular behavior of the universe, as it could become patched and change at any time, and without notice.
BTW, if anyone knows how to get in contact with the great creator, please let me know. I would be willing to submit a feature request on our behalf to improve the collision detection, with the intent of one day being able to lift this restriction on our physics. I presume the great creator employs some kind of bug tracking system and revision control... Or at least I desperately hope that is the case. Oh gawd--what if we were some kind of late night hack, hobbled together over the weekend and there was not even a backup made?!
Ah, existential dread... hello old friend.
dude, wat a comment
Whoever implemented the speed limit feature must be a massive showoff, like, all those time diliation and relative speed stuff is cool, but all these computation surely would eat away CPU cycles like crazy, since it has all those fancy sqrt and square and stuff. The team implementing collision detection's clearly struggling, having requested the speed limit feature in the first place. Maybe if the big brain time dilation coding being or something decided to help them with some fancy anti-tunneling code, there wouldn't be the need for the speed limit in the first place. smh.
1- One of the best teaching videos on TH-cam in terms of quality and content
2- The best video that simplifies collision detection approaches
The guy is a genius! THANK YOU!!
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 .
Yeah this relates to some interesting ideas in spatial hashing that I debated including in the video, but cut out due to it already being fairly long. Thanks for pointing this out though.
Amazing! Its so much easier to understand things when they are visualized and animated like this.
Great work!
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!
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 :)
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..
Great video. Never realized how complicated collision detection could get!
I have been looking for a video like this for the whole day.
Thank you for the great work!
Oh my goodness, this is pretty neat. I am actually working on something like this myself! I've just gotten to the point where I need to begin on the collision system and I stumble upon this wonderful channel (came here from that FFT video)!
great presentation techniques. You started by Introducing the subject and giving a clear target at the end of video. You ended with a clear recap.
Thank you so much for such a great starting point on advanced collision systems.
I just discovered your channel since I am about to have a job interview for a PhD student position about collision detection in physics simulation in industrial mechanics softwares. I try to perfect my knowledge before I get there. Your work is simultaneously very beautiful to look, easy to follow and understand and also complete in the primary description of the problem. You have to continue in this direction it's objectively perfect. I immediately smashed the subscribe button :).
Wow, that's awesome! Thank you so much! Good luck on your job interview!
@@Reducible Thank you! You're welcome, you deserve to be supported in this project, it's useful for anyone in need.
The fun starts when you try to calculate further collisions that occur during during the same frame after a collision has taken place and the trajectory was changed. Or three objects that collide at the same time...
I usually implement an integrate method that takes a delta time an calculates the next frame of the particles or objects accurately, then on collision I try to find the exact collision time and move the whole scene back in time to that time by reducing the delta time accordingly and integrate again with the smaller time step from the last frame, resolve the collision response and integrate again to the next frame by moving the scene by the delta time left. I repeat until no collisions are found anymore. Then the next frame starts. It's very important that the integrate function is stable no matter the time step put in. So to include acceleration you have to use the s' = s + v0 t + ½ a t² term
@@ecicce6749 The drawback is that under certain circumstances the framerate might drop significantly, because there are too many collisions to solve within the interval.
Thanks for your videos, I really like them!
I'm currently working on an agent-based model for simulating the spread of corona in a city, so this video comes at the right time!
Why this does not have more views?? It's a great, simple to understand explanation
This is a very interactive AWESOME video. Thank you soooo much!
Great tutorial, looking forward for more computer graphics tutorials!
13:23 wtf happened to those yellow and blue balls in the middle of the box? They just randomly started to orbit themselves
Bug!
Ha, good eye -- that's a bug, not a feature :P There were way more of these issues in earlier iterations of the simulations, and they happen randomly when there are some weird shear type collisions of particles. I promise I tried fixing all of them. It's really a case of fixing a bug and then introducing like 40 new bugs, probably some underlying mechanics in my code is off slightly.
At some point, I just had to call it and move on because the effort to fix the bug seemed to not be worth it.
@@Reducible Was CCD implemented between spheres? If not, I think this is the problem.
@@italolima855 yes the full proof solution to this is to implement CCD when particles are quite close -- I tried to keep things in the world of discrete collision detection (I started out with this design choice) and the most likely reason this bug occurs is probably because of that.
@@Reducible I asked it because I was trying to do something similar but with partially elastic collisions, and I simply couldn't do it work without CCD because after one frame the spheres with reduced speed would still be intersecting each other, creating a very similar effect.
Fascinating and incredibly informative. Than you.
Please do more videos. Your explanations are excellent!
Great video. I've always wondered how BVHs work, and that explanation was perfect.
Tus videos son asombrosos. Gracias por hacerlos 💙
plz make this a series
Nice video! A programmer who sometimes writes simple games here, and still find this useful :)
Quick comment on the cons for uniform grid space partitioning approach: In fact having many empty grids isn’t a con if implemented with the right data structures.
One can maintain a list of grids, each associated to a list of intersecting objects, but skipping any empty grid:
1. Traverse each object, determine the list of (exactly or potentially) intersecting grids.
2. For each grid, push the object to a list associated to the grid. The latter can be achieved by creating a hash map which maps a grid (eg the key can be (row_id, column_id) for the 2D case).
3. Don’t bother initialize an empty list for each grid.
3. At the end, you can iterate through the hash map, skipping any grid with no intersecting objects.
One assumption here though is that at step 1, we need a relatively efficient algorithm to compute the list of all (or potential) intersecting grids. This is relatively simple to achieve for convex shapes like a circle (or a sphere in 3d space), but could get tricky for concave shapes where one might want to resort to approximating with a bounding box/volume.
It's very useful and educational! Thank you a lot!
WOW!! LOVE ur work...please keep making such videos!!!
This is addictive. Now I want more such videos.
Oh my god, this is amazing! Even thought I’m on Patreon, I still watch the videos here for the sake of the algorithm (get it?), which is also why I comment filler words
You're awesome -- words cannot express my appreciation!
Amazing video!! Thanks for your great work
I'm sorry. I was so much into your videos that I was continuously watching the next suggested video and I forgot to like the previous one. Loved these video.
Yay he’s back !!! Love it
thank you very much! very professional and informative!
This deserves way more views
This is CRAZY! I just made a particle simulation in python and this pops out?? Ready to watch and learn more
Thanks for the great video! A little trivia: for sorting the particles by position, it turns out that bubble sort is actually one of the _best_ ways to do it, assuming the list persists between frames.
Just amazing!!!! Thank you.
One of the best science channels !
I got my project Idea! Thankyou
Awesome video. Thank you
Awesome explanation!
Amazing. Your channel will def take off one day.
For one of the homeworks in my data structures class I had to implement a bounding volume hierarchy. Easily the hardest homework assignment for that class
this channel never fails to surprise me, its the 3b1b of CS
I really learnt something right there! Thanks
really amazing video thank you so so much!! :)
Dude! just... thanks! a lot! I was attempting to code 2d collisions and i was struggling on the equations, playing with angles and polar coordinates. Your method of projection is just magic and it fit in 10 lines of code ahahahah.
Great stuff as always
I love these kinds of videos!
I just checked your code in python for the animation, and I must admit that is wild, and I respect you as you don't know how, like you are the boss bro, thanks, LOVE YOUR VIDEOS!!!!, I'm just reproducing again the video, just to support UwU
12:42 Some ideas:
1. First you need to "enter the frame of reference of the 2 colliding particles". To do that you add the 2 speeds together (as vectors), divide by 2 and subtract from both vectors. You save this vector for later. To see why, think about the point that is in the middle of the line connecting the centers of the 2 objects. This point must be stationary.
2. Now to find the new directions draw a line perpendicular to the line that connects the centers of the 2 spheres and flip the two (converted) velocity vectors along this line.
3. To find the new speed values you need to consider that the total momentum must be preserved (m1*v1+m2*v2 == m1*v'1 + m2*v'2) and the kinetic energy must be preserved (m1*v1^2/2 + m2*v2^2/2 == m1*v'1^2/2 + m2*v'2^2/2). This gives you a system of 2 equations with 2 unknowns (the 2 new speeds).
4. Once you know the new vectors, you add back the vector you subtracted in step 1 to get these vectors in the frame of reference where the box is stationary.
The "ugly equations" shown here are these steps performed on two arbitrary vectors, using vector algebra. When you look at the steps above, you can see why their derivation (and their final look) is such a mess.
very nice, I did quite the same (but without optimisation like sweep and prune, only continuous collision detection and response). It makes me want to try a few things :)
Thank you for this wonderful video :)
Really huge respect for you sir....
This Guy is criminally underrated
Awesome visuals!
Great work!
Great video! I was only familiar with using quad trees to minimize collision detection calculations.
Really good intro!
Thanks, it's really helpful!
finally a channel for computer science/graphics and games thats more technical but cool at the same time fuck yea
Thanks, this is quite helpful as I step into my second game engine project. I do not plan on having walls involving elastic collisions, but I will have fast moving projectiles and I need them to not be able to pass thru sprites undetected. I was thinking to draw lines from previous positions to current positions (left and right edges of round projectile) and check collision of those lines with my sprite rectangle object... but this may end up being a terrible idea in practice. I haven't seen it implemented anywhere. I think the ideas in this video may be more practical. Thanks again.
This is excellent, thanks!
Thank you for teaching humanity
you taught me a lot thanks
Great video!
Good video dude. reminds me of 3blue1brown, very easy to get an intuitive grasp of some very complicated topics.
Damn... cliff hanger. Nice work!
You should definitely do a video on collisions with more complex shapes or maybe constraints, it is really interesting
Thank you for the video
Oops I forgot to subscribe from your other videos. good thing this came back in my recommendations
What a nice video!
Thanks, I want to learn more from you
your channel videos are really interesting . . . LOVE u boi
Thank you @3blue1brown for making these videos possible!
I use an other method : I compute collisions for all pairs with no time limit, and put them in a sorted list (or tree) by the time of collision.. I also store a reference to the earliest collision for each particle. I advance time until the first collision, then do the bounce computation, and do the collision test for the two balls which trajectory changed with all the others. If a new earlier collision is detected (that happens before a previously anticipated collision), I update the sorted tree (remove collision that won't happen anymore and add the new computed collisions).. this way I only compute ~ n collision only each time a collision occurs. Works great only if particle have a predefined trajectory.
What a great video!
Good talk, thank you.
You have to think about the situation where the new position after a collision could potential leads to other collisions as well but with a shrinked down time (a higher fps in this frame)...
Genuine question... Are you somehow related to 3blue1brown???
the way you guys talk, animation style, even the way of explaining is similar,
this isn't a bad thing, heck you guys are best at explaining your topic, I just can't help but draw similarities
Ha I appreciate the comment! No, we are not related :P I'm just a guy that uses the library he so generously made available to make the best CS videos I can.
3b1b created a library to create animations like ones you see here or in his videos. It's called Manim github.com/3b1b/manim
@@Reducible Appreciate that.But we are soo curious how you look like.
This isn't directly related, but this video reminds me of a story:
I was trying to develop a game in GameMaker some years back that was sort of a strategy game where the player could theoretically have an arbitrarily large number of units. My collision system wasn't super optimized, as I was a beginner biting off more than I could chew, but what I really want to talk about is the enemy targeting system. I initially had enemies simply target the closest player unit, but my playtester thought it was random and found it unfun, so I decided to come up with a system where the game dynamically puts player units into groups, then the enemies attack the center of the group rather than individual units and I wanted it to be as optimized as I could reasonably get it.
That threw me down a rabbit hole that I was in for like a year, but ended up using a uniform grid space partitioning algorithm without knowing it. The enemy targeting handler would partition the play space into a uniform grid (I think 16x16 or 32x32) and scanned through all the player ships (up to some max number of units n) and checked their grid positions, updating a corresponding population counter for each respective grid position accordingly, then the enemies would aim for the nearest local maximum on the grid. Then the next frame the targeting handler would cycle through the next n units, update the grid and so on. I was pretty proud of it at the time, but I wish I'd known about bounding volume hierarchies at the time. I had this whole other system that I wanted to use similar to KD trees, but based on nearest neighbors that I loved in theory but could never get to work in practice, which is why I ended up going for the grid system in the first place.
wonderful video my goodness
this channel is like the 3blue1brown of computer science and i love it even though most of it still doesn't make since to me... It will soon enough!
This is gold!
subbed cause this is quality
this is one of those videos that i will always keep open in a tab telling myself i'll do this one day, and it just stays in that tab forever