11 - Finding collisions among thousands of objects blazing fast

Рет қаралды 22,763

Күн бұрын

For the source html code and all other tutorials see matthias-research.github.io/p...
In this tutorial I show how to find overlaps among thousands of objects using spatial hashing. In addition to explaining the method, I also show how to implement it in a very efficient way.

Пікірлер: 36

@kiaranr Жыл бұрын

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

@nolram 2 жыл бұрын

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

@toshi4186 2 жыл бұрын

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

@WomboBraker 8 ай бұрын

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

@ahmedsalih2308 5 ай бұрын

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

@7steelrainbow 2 жыл бұрын

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

@johnpelitidis6297 5 ай бұрын

What you do is outstanding... Thank you 🙂

@voxelltech 2 жыл бұрын

Thank you for the video!

@ssssos5155 2 жыл бұрын

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

@TenMinutePhysics 2 жыл бұрын

I will certainly do a tutorial on this once I have introduced XPBD rigid bodies.

@barlex9113 8 ай бұрын

@@TenMinutePhysics Any status on the progress of the XPBD rigid bodies? Do you maybe have a written resource somewhere?

@saivarunsanapala8199 6 ай бұрын

@@barlex9113 he hasn't released in his channel yet, but he gave a talk about it in 2020. you can see his paper there

@pronotron Жыл бұрын

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

@hommhommhomm 11 ай бұрын

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

@odo432 11 ай бұрын

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.

@444haluk 2 жыл бұрын

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

@TenMinutePhysics 2 жыл бұрын

I am glad you like the videos. I won't restrict the content in any way within the field of real-time physics.

@Typhh 2 жыл бұрын

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!

@Typhh 2 жыл бұрын

ah turns out it was fine all along, just needed to use a better table size :)

@mmmovania Жыл бұрын

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?

@sayochikun3288 Жыл бұрын

Yes. Worse case scenario is a ball, overlapping with 4 cells but calculating "which 4 cells" is worse than just checking 9 of them in most cases.

@neonmarblerust 7 ай бұрын

@@sayochikun3288 No, you need to check 9 cells because you need to check all cells where another ball might be able to overlap. You need to query more than just the cells the ball can touch, you need all of the cells that can contain a ball that touches the queried ball.

@sayochikun3288 7 ай бұрын

@@neonmarblerust you might be right. Ill make a quick sim to fiddle my thoughts then come back to you

@robbie_ Жыл бұрын

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

@Pheubel 6 ай бұрын

Have you also tried playing around with hardware acceleration where you use a single instruction to handle multiple bits of data. With the locality, i would imagine it could speed it up by a fair bit

@PaleyDaley Жыл бұрын

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?

@TenMinutePhysics Жыл бұрын

You are right, only half. Here we are just looking at the order of magnitude though The entries have the same first and last value so we don't do anything without the need of doing a special check.

@fizixx Жыл бұрын

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

@user-ef3ej4pq4f 2 жыл бұрын

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

@TenMinutePhysics 2 жыл бұрын

For the GPU there is a better algorithm: documents.pub/document/particle-based-fluid-simulationbased-fluid-fluid-simulationbased-fluid-simulation.html

@alengm Жыл бұрын

@@TenMinutePhysics isn't this the same one as in the video?