Building Collision Simulations: An Introduction to Computer Graphics

[@Reducible]

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.

[@AnimationMovieLover]

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.

[@watchlistsclips3196]

@@AnimationMovieLover We want videos on trie

[@chrisprendergast5477]

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 😂🤦‍♂️

[@masternobody1896]

Big brain

[@imadetheuniverse4fun]

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.

[@NovaWarrior77]

Thank you for: A. Doing this work. B. Making it free. Awesome and inspiring.

[@all462]

+

[@Henrix1998]

28 minutes just flew by. Good job keeping viewers interested and focused

[@f1ncc246]

This guy's voice feels like a mix of 3b1b and zach star

[@isaacchen3857]

YES

[@ilonachan]

Factor in his outstanding use of Manim, and he's basically the 3b1b of computer science

[@amicloud_yt]

and Isaac Arthur

[@Greedygoblingames]

My first thought was exactly, "this reminds me of 3B1B" :D

[@ArnaudMEURET]

@@Greedygoblingames So much so that I think he should at least select a different font. This one is now the irreversible signature of 3b1b. ☺️

[@eshh183]

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!

[@MrDgf97]

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.

[@AwesTube]

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!

[@alegian7934]

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

[@Reducible]

That "re-invention" feeling is one of the coolest aspects of learning this stuff.

[@JacobNax]

@@Reducible i cant agree more haha

[@arshawitoelar7675]

What software/program did you use to write the code in? What program did you use to make the simulation animations?

[@alegian7934]

@@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

[@arshawitoelar7675]

@@alegian7934 I see, thank you so much

[@AwadMukbil]

1- One of the best teaching videos on KZbin in terms of quality and content 2- The best video that simplifies collision detection approaches The guy is a genius! THANK YOU!!

[@LorenzoValente]

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

[@Reducible]

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!

[@SimulatingPhysics]

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.

[@looksintolasers]

What do they use for n-body simulations? You can't use Sweep and Prune since forces never die out to zero.

[@SimulatingPhysics]

@@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 :)

[@Galileo51Galilei]

@@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

[@Galileo51Galilei]

@@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"

[@TheRainHarvester]

@@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?

[@chinmay4436]

Thank you so much for covering this topic. You inspire me to study something new everyday. So wholesome. Thank you for doing everything. ❤️

[@motbus3]

+1

[@Andrew90046zero]

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!

[@HadienReiRick]

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.

[@PanDiaxik]

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.

[@HadienReiRick]

@@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

[@RuanD]

Yeees, I have seen it. It's kinda funny

[@daysetx]

Is it possible now to aim and accelerate particles to merge them 😅?

[@ptitbgdu8040]

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 :).

[@Reducible]

Wow, that's awesome! Thank you so much! Good luck on your job interview!

[@ptitbgdu8040]

@@Reducible Thank you! You're welcome, you deserve to be supported in this project, it's useful for anyone in need.

[@martindobrev7263]

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 .

[@Reducible]

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.

[@AVUREDUES54]

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

[@Reducible]

You're awesome -- words cannot express my appreciation!

[@ray3369]

Thank you for providing such a high quality video for free! This was awesome!

[@mandisaplaylist]

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.

[@vijay6877]

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.

[@guilhermecorrea3604]

Why this does not have more views?? It's a great, simple to understand explanation

[@real7876]

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.

[@PedroCristian]

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.

[@spironan]

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!

[@CoughSyrup]

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.

[@iilugs]

dude, wat a comment

[@youtubehandlesux]

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.

[@dodziraynard]

😅

[@gutzimmumdo4910]

finally a channel for computer science/graphics and games thats more technical but cool at the same time fuck yea

[@hjdbr1094]

13:23 wtf happened to those yellow and blue balls in the middle of the box? They just randomly started to orbit themselves

[@teunschuur7988]

Bug!

[@Reducible]

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.

[@italolima855]

@@Reducible Was CCD implemented between spheres? If not, I think this is the problem.

[@Reducible]

​@@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.

[@italolima855]

@@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.

[@thegrandarchmage_]

I have been looking for a video like this for the whole day. Thank you for the great work!

[@ReadersOfTheApocalypse]

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...

[@ecicce6749]

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

[@ReadersOfTheApocalypse]

@@ecicce6749 The drawback is that under certain circumstances the framerate might drop significantly, because there are too many collisions to solve within the interval.

[@amaarquadri]

Great video. Never realized how complicated collision detection could get!

[@MrFirelord]

Thanks!

[@Amplefii]

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!

[@Dan-sk2ff]

I didn't fundamentally understand a word of what was uttered. But I watched till the end. 10/10, it was interesting.

[@amicloud_yt]

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)!

[@TanmayGejapati]

this channel never fails to surprise me, its the 3b1b of CS

[@shivasurya3546]

One of the best science channels !

[@charlie3k]

At 14:48, there is a small blue particle that seems to orbit a large yellow particle (in the upper left region of the box)

[@xAtMaxx-ee1kn]

LOL that's right, Good catch. How is that possible? Seems like it should not be possible..

[@willjohnson4579]

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!

[@atalazs]

did someone notice the strange rotating movement at 13:23 near the middle of blue and yellow dot? Seems as the particle is trapped and notices hundreds of collisions with the same particle.

[@jellewestra]

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!

[@rubixtheslime]

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.

[@chrisv8341]

Yay he’s back !!! Love it

[@proxy1035]

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

[@DetectivePoofPoof]

Amazing! Its so much easier to understand things when they are visualized and animated like this. Great work!

[@tarunbalchandbhaimulchanda6929]

This Guy is criminally underrated

[@OmarChida]

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 :)

[@darksigmavideos4013]

0:47 if you want a precise model, use: v(f+1/2) = v(f) + a*dt/2 p(f+1) = p(f) + v(f+1/2) v(f+1) = v(f+1/2) + a*dt/2 This assumes constant acceleration. Dynamic acceleration becomes quite a bit more of a complex system.

[@ico-theredstonesurgeon4380]

This is CRAZY! I just made a particle simulation in python and this pops out?? Ready to watch and learn more

[@Illogical.]

9:08 To my knowledge, this is how Mario's collision works in Super Mario 64. Every time Mario moves, each frame is split into 4 seperate collision detections. And Mario has a maximum forwards momentum. There are a couple of problems here though. Mario has a maximum FORWARDS momentum. Backwards momentum is not limited. To clarify, this is relative to the direction, the player character's facing. There is also another problem. Since walls don't always allign with the grid, they had the excellent idea to only calculate collision for the nearest wall each frame, so the player can both go through corners of walls and go through walls backwards if they find a way to increase their backwards momentum enough. (Mario always turns to the direction, he's walking/running, so you can't just walk backwards. If you want to know more, the trick for going backwards fast is called blj or Backwards Long-Jump.)

[@sebbes333]

18:00 -ish Then you check those "suspect" particles* along the Y-axis in the same way, to ACTUALLY find out if those particles collide. Because the Y-axis will determine that the first pair do NOT collide, while the second pair still DO collide & therefore are colliding. (*not all particles, ONLY those marked with green square here needs checking)

[@Reducible]

Yup I tried emphasizing "possible collisions" (didn't have space to write it out with that algorithm). Thanks for putting this clarification our there.

[@fudgeracoon2529]

Great tutorial, looking forward for more computer graphics tutorials!

[@Twisted_Logic]

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.

[@leonardofernandezrios7768]

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

[@ashuzon]

This is addictive. Now I want more such videos.

[@oneeyejack2]

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.

[@jamesgalante7967]

This deserves way more views

[@yackamajez]

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

[@davidhand9721]

For the game 5ong, I used a tree structure where each node was a key-item pair and the key was the bounding rect of the item. The bounding rect of each _node_ was the smallest rect containing its item key and all of its child nodes' bounding rects. The invariant for the node relationships was that the child nodes were bounded in number and no node had direct children that had overlapping bounding nodes. This way, while searching for collisions with a position rect (or a sweep between old and new positions) each node either had a collision with its own key, exactly one of its children, or nothing.

[@MrBTOdell]

In the bottom-left corner of the particle simulation, you can see an orange and yellow particle collide and "swing" around each other. 14:34

[@RiversJ]

What you encountered was the computational aspect of the nbody problem. The video has magnificent solutions some of which i will be trying to learn them. Getting hamstrung at 100 particles is pretty low though (and has been the common theme until lately). If you multithreaded that problem and murdered any notion of OOP programming and instead iterated over sections of the data in thread sized chunks with duplicate data you could reach around 1800 particles before hitting performance limits. OOP is fantastic for object shaped problems and absolutely horrible for raw data transformation over massive data sets, mostly due to cache issues and concurrency congestion.

[@RiversJ]

What you should expect a high end macbook to hit is around 1000 particles while retaining high frame rates.

[@thesituation5315]

Yeah, I was really confused when he said it took 3 minutes to do 100 particles. I'm trying to make a 2D physics engine, and I haven't even optimized it that much, and it can do around 1500 to 2000 particles before the limitations set in.

[@charithjeewantha]

This is a very interactive AWESOME video. Thank you soooo much!

[@9403Victor]

Tus videos son asombrosos. Gracias por hacerlos 💙

[@andreemery4964]

At 14:50 you can see that for one of the large yellow balls on the center-left, there is a little blue ball that 'curls' around it. Looks like an artifact from the collision logic.

[@erich_l4644]

Instead of saying “Now I am going to give you an explanation of X”, just explain X. Thanks for this work

[@hadesthx]

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.

[@TheInevitableHulk]

Thank you so much for such a great starting point on advanced collision systems.

[@jongxina3595]

Amazing. Your channel will def take off one day.

[@theblobber4461]

In 26:31, I don't get why two bounding boxes with no intersection can't have collision. It should depend on the velocity of the particle within the bounding box. If the velocity is large enough to reach the other bounding box in one frame, they will collide.

[@kychemclass5850]

Fascinating and incredibly informative. Than you.

[@ianegan]

This was a great video...I'm trying to "figure this stuff out" and so when i learned there is a word to describe one of the other issues i had noticed because it was so common (aka tunneling).

[@takethegaussian7548]

Please do more videos. Your explanations are excellent!

[@stanisawmrowiec9596]

how this simulation works? you can even see at 14:35 near left bottom corner that yellow and orange balls dont simply bounce but "orbits" or something for a while

[@joseville]

Great video!!! At 12:48, what is the angle bracket notation? E.g. I was thinking it might be a 2D vector with components "v1-v2" and "C1-C2", but since v1, v2, C1, and C2 are vectors (I'm assuming) themselves threw me off since vector components have to be scalar.

[@sonyo]

It's the scalar product (or dot product).

[@_sophies]

Great video. I've always wondered how BVHs work, and that explanation was perfect.

[@twipps7700]

This video helped my understand my bugs alot better thanks!!

[@npip99]

20:29 Can't you use a hashmap, mapping Square's coordinates -> List of circles intersecting that square, and then only loop over the keys of the hashmap? Hashmaps are O(1) and this resolves the empty square problem.

[@OtjPlateo]

"Can't you use a hashmap?" you can. But it would only be 1 more alternative, not the best solution. But probably a very good one considering how easy the implementation is. For example, hashmaps would certainly be slower than a grid-based solution because of the overhead. Remember that time-complexity is not the only limiting factor, but also how fast you can load data into the CPU caches. Because of the dynamic nature of hashmaps this will be very slow (the CPU prefers data that is stored close or even next to each other). You also have to recalculate the hash every time you want to look up a key.

[@HuntingKingYT]

Thanks for reminding every developer his worst nightmare!

[@watchlistsclips3196]

Want more videos on advanced graph theory like minimum spanning ,fenwick,segment trees,dp,greedy,trees,tries,number theory,divide and conquer,Amortized Analysis,Sieve of Eratosthenes .Will be of great help for everyone all over the world

[@benjaminfranklin329]

Good basic intro, probably would have been helpful to mention that tree based approaches introduce challenges with dynamic updating the tree each frame, whilst not necessarily covering the provlem

[@chyle16]

13:22-13:25 dat yellow circle just spun that blue circle like a boss

[@ahmadassad6235]

plz make this a series

[@Soandnb]

13:23 there's a blue particle that does a fun spin around a large yellow particle!

[@AA-gl1dr]

Thank you for teaching humanity

[@dennisbrand5269]

14:50 What the heck did happend with the blue and yellow ball to the left, roughly at (0.1, 0.45), if the width and height of the box were 1 and the origin would be in the left-top-corner?! The blue ball circled around the yellow one. Edit: typo

[@WhiterockFTP]

14:35 wtf are the yellow and orange circles right in the lower left corner doing?? hugging and doing a 180, this is certainly not a collision how it is supposed to be :D

[@askplays]

what do the angle brackets at 12:42 mean? at first i thought it was a vector but i'm clueless on how you would make a vector with a vector as the x coordinate. and why the hell do you get the magnitude of a scalar value??? when you already square it?

[@-nafa-3229]

It's very useful and educational! Thank you a lot!

[@2Dparrot]

I love this video, and the way you explain the topic is really informative. However I'm super distracted by the piano music in the background which makes it really hard to focus on the actual material you're discussing. Would you happen to have a version of this without the music somewhere, or would you mind re-uploading the same vid without music? Again great video, just really hard to focus on your explanation with the music in the background.

[@jroseme]

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.

[@ДаниилРабинович-б9п]

6:47 there's a bug that can happen with this implementation, specifically, when you collide with the ceiling, if your position is very close to the ceiling, the mirrored velocity could become not enough to the box, which if I understand correctly, will result in the ball drifting upwards infinitely. fixable by a check for velocity direction for example.

[@thelookofdisapproval8234]

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

[@Reducible]

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.

[@remmoze]

3b1b created a library to create animations like ones you see here or in his videos. It's called Manim github.com/3b1b/manim

[@watchlistsclips3196]

@@Reducible Appreciate that.But we are soo curious how you look like.

[@o_sch]

i havent watched all the way in but I think I have a solution somewhat to the 100 particles issue. If you are using forces between particles you can find a point where the force is negligible because of their distance. Now keep that distance in mind, that is a constant and is very important. Now imagine dividing the space into a grid. You only check for interactions in each box. Then update each particle's box. This cuts down on total checks but what about particles on the edge of another box. They still need to be checked. So what you do is you extend it so you have a 3x3 grid. That way a particle in the say, far right, of the box you are checking, can check interactions with particles in the right adjacent box. The box width/height needs to only be the same as that distance we found earlier, because by checking particles in a box with only other particles in a 3x3 grid around that box, the minimum distance to where a particle can still be close enough that forces matter yet be outside the grid is the one we found earlier. If you make each box equal to or greater than that then each particle's maximum interaction range MUST be contained inside the grids. Why use a box shaped grid and not something circular? Well what you could do for each interaction is wrap it in an if statement to check if their distance is in the right range. But finding distance is a costly operation. So if you tile the space into zones then the distance is basically already found for you. You cant use circle shaped zones because they cant tile the plane infinitely, squares can though. So basically for my method you do this: 1. Loop through each grid zone 2. In each grid zone loop through each particle 3. For each particle loop through all other particles in a 3x3 grid zone grid centered on the current grid zone 4. For each particle particle pair check to see if the distance is smaller than the negligible one. 5. If after all of that it is still true then you can run the collision algorithm

[@Dominikbeck12]

I did a colision computation of large number of particles as part of HW in my first year of university physics studies. Interestingly, there is so more to this models. For example, if you define a particle energy to be E = 1/2 mv^2, then the number of particles in specific energy interval dE is proportional to exp(-k*E) (Boltzman distribution). If we would like to find a distribution function of velocity components vx, they are gaussian.

[@Reducible]

Huh that is super interesting and I wasn't aware of this fact. Thanks for sharing! And yeah, this video is really just touching the surface of an incredibly deep subfield. So many people have gotten PhD's from innovations in this area of computer science/graphics.

[@lbranco93]

Anybody noticed at 13:22 the small blue particle circling the large yellow one at the center of the simulation?

[@adityams1659]

WOW!! LOVE ur work...please keep making such videos!!!

[@Wecoc1]

14:50 Weird collision effect yellow + cyan on (0.1, 0.4) approx., I have no idea what happened there...

[@dummybugstudios6450]

TLDR: The 2D collision response vector equation is so clever! It requires no trig functions so it's really fast. It effectively reframes the 2D collision problem into the simple 1D collision problem by rotating the space so it looks like the circles are just colliding head on and then applying the formula for 1 dimension. When two circles collide in 2D, say one is slightly above and to the right of the other, you can imagine a normal vector (going from center of one circle to the other) and a tangent vector (which is 90 degrees to the normal vector and tangent to the point of collision). You can express the velocities in terms of these vectors by projecting the velocities onto them (using the dot product), effectively rotating your frame of reference so that the tangent and normal vectors are your new x and y axis. The clever insight here is that there is no force in the direction of the tangent vector so whatever component of the velocity is in that direction, it won't change! You only have to calculate the new velocities for the normal direction using the equation for collisions in 1D. Once you have the new velocities in the reference frame of the normal and tangent vectors, you can convert them back into your original reference frame by multiplying them by the normal and tangent vectors! If you wanna know more, read the pdf in the description: www.vobarian.com/collisions/2dcollisions2.pdf

[@yannrolland4193]

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 :)

[@churrte]

Amazing video!! Thanks for your great work

[@leonhardolaye-felix8811]

14:38 check that freak collision in the bottom left with the blue and green particle. Wonder what caused that 🤔