11 - Finding collisions among thousands of objects blazing fast

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

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

[@ahmedsalih2308]

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

[@WomboBraker]

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

[@toshi4186]

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

[@ssssos5155]

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

[@TenMinutePhysics]

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

[@barlex9113]

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

[@saivarunsanapala8199]

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

[@johnpelitidis6297]

What you do is outstanding... Thank you 🙂

[@7steelrainbow]

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

[@hommhommhomm]

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

[@pronotron]

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

[@odo432]

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.

[@joshuasonnen5982]

I wanted a table showing hashing speeds for different number of particles. I have my own collision detection written in Julia and can't tell which is faster.

[@444haluk]

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

[@TenMinutePhysics]

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

[@voxelltech]

Thank you for the video!

[@DasAntiNaziBroetchen]

Does anyone here have any information on how this compares to using a BVH to find colliding pairs? A BVH has obvious advantages like not caring about the size of elements.

[@Typhh]

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]

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

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

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

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

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

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

[@DasAntiNaziBroetchen]

@@sayochikun3288 And we never heard from them again...

[@sayochikun3288]

@@DasAntiNaziBroetchen I'm still working on the simulation 👍

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

[@LowLifeGraphicsProgrammer]

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

[@TenMinutePhysics]

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?

[@ThankYouESM]

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.

[@quillaja]

you could check out p5.js

[@drk7016]

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

[@phutureproof]

keep taking those pills brother

[@Pheubel]

Terry might be gone, but his spirit lives on.

[@atomictraveller]

ball movement. that's what i'm getting at. yeah. it's a part of you it's a part of me. deez

[@DasAntiNaziBroetchen]

I seriously did not expect to see a religious comment like this here. I'll let you in on a secret: Those balls are not moving around randomly. Here's another secret: Evolution isn't random.