11 - Finding collisions among thousands of objects blazing fast 

Thank you for these videos, they are an absolute treasure.

Hash grids are my go-to solutions for all things that interact in space; which is a lot. They seem to always beat other spatial partitioning algos

i was playing around with building a simple game with lots of moving units that follow certain rules, and came up with storing an id of each entity to an 2 dimensional array for proximity logic. This example here showed me in the end how naive my idea was, but damn i'm exited to apply this videos teachings into practice!!!

Thank you so much matthias... This is gold !

What you do is outstanding... Thank you 🙂

Thanks for this tutorial. Building an hash grid seems very affordable.

Thank you for the video!

This is the best explanation of neighbor search algorithms I've seen on youtube yet and you demystify really hard concepts for me. Thanks a ton! Now I understand a lot better :)

This is great if all the objects are the same size. But if you've got variable sized objects then things start to become increasingly more complicated fairly quickly with growing impact on performance.

Sweet! waiting for an upload for softbody+rigid body interaction :)

Thank you! This excellent video would be easier to find if the word "collision" was present in the title.

Thank you for sharing! How you handle collisions if other primitives mixed in PBD like spheres, boxes, capsules?

Great! Watched all your videos! How about fluids? Are your XPBD videos enough?

Hey matthias! how do you deal with input points that have negative values? i'm trying to sample a selection of points ranging from -10/10 xyz however the hashing function and querying seems alittle off. Many thanks!

Thank for the tutorial. You shared on slide 5 that you need to check 9 cells in 2D I dont understand why? from the image on slide 5, you have shown if the distance h=2r then u only need to test four cells to check for overlap/collision no?

So I implemented this algorithm in C++ and made it multithreaded using std::execution::par. I used _InterlockedIncrement and _InterlockedDecrement to prevent races. I could do a single pass constructing the structure ready for collision checks giving it an array of 1,000,000 entities with a 2048x2048 size grid in about 14ms. Pretty good. I didn't try quadtree. Something tells me it'll be way slower with way more contention (single threaded was about 47ms - the benefit of multithreading grows with the number of entities of course).

A couple of questions: 1) You say with naively checking 100 thousand objects you'd need ten billion tests. But surely it should be only half that, because you don't want to test pairs twice. Right? I know it's not important, but I just want to clarify. 2) For the hash cells that correspond to empty grid cells, why do they contain valid values? Shouldn't they contain -1 so you can skip them?

Could you please make us an HTML5 3D graphics engine as a single file... which I hope to build a Py2JS solution for very soon? Thanks.

ten billion --- (1:36) according to what's written.

This scheme seems easy to parallelize, but too many atomics ops I guess...

The movement of those balls proves that the universe was not formed by random evolution but was created by God