Quadtrees: Blazingly Fast Collision Detection 

that's C

@@rustwithoutrust Indeed. C wasn't what I had in mind from Rust Without Rust!

same, lmao

kekw

@@DanDeebster Why not? It's right in the name: *without* Rust!

it's actually all a scam

Yes, if the cells overlap by 2 object radiuses, then collisions can be easily handled between several cells.

@@rustwithoutrust 🌌🧠

When I did my test implementation, I made it so that cells aren't split in half, they're split based on the bounds of the objects within them, so almost all cells overlap, but if two objects might be colliding then they're guaranteed to both be in at least one cell.

thanks!

relatable

do you think quadtrees are optimal for those 2d collision demonstrations?

​@@rustwithoutrust For 2D and 3D collision demos with almost similarly sized objects (for example particles), QuadTrees and Octrees are pretty solid and get the job done nicely 😊. They’re a good choice when everything’s about the same size, but for more complex physics, raycasting or different-sized objects, other approaches might work better 😉.

Hey, didn't expect to see you here! I wanted to thank you for your work on Kraft, it's been a pleasure to go through the source code and learn a thing or two! Why haven't you split up the source, since kraft.pas is a really long file? Are you aiming for having a unit-only physics engine?

@@BenjaminRosseaux Would there be a way to dynamically effect the radius of each object in the quad tree?

@@brickmasterhunt4561 Although it is possible to have objects with different radii in a Quadtree or Octree, this approach is not very optimal. The main issue is that objects would have to overlap into neighboring cells based on their new radius, complicating the structure. Additionally, neighboring cells would need to be constantly checked and updated based on the object's radius, increasing complexity and potentially leading to an O(n²) runtime in the worst case. This becomes particularly inefficient as the number of objects grows. Moreover, this approach introduces inefficiencies since Quadtrees and Octrees are designed more primarily for fixed bounding volumes, uniform element sizes, or otherwise purely static runtime lookups. Different radii and different object sizes (especially those larger than a Quadtree or Octree leaf cell) would negate the spatial partitioning benefits in the dynamic usage case. Alternatives like dynamic self-balancing AABB BVH/BIH trees or even loose Quadtrees/Octrees can handle varying object sizes and radii more efficiently.

ok, no need for an alarm clock

@@rustwithoutrust lol. Definitely face palmed when reflecting on my own novice attempts at collision detection. Great video. Subscribed.

thanks! yeah, most of those ways aren't that obvious initially

octrees or octonion trees?

real

I created map applications in my previous job. Having kilometres/miles of road polygons, buildings, forests, rivers, lakes, cables, lamp posts, side walks etc. a large region could consist of 5 gigabytes of vector data and having the quad trees in files with indexes to the vectors we could zoom anywhere on the map and draw the area in just 20ms. Large vectors would be clipped before drawing to optimise drawing speed. Also large polygons or lines would be stored on upper levels and these span multiple quads.

Even for uniformly distributed objects, splitting the test area reduces the total number of collision checks which need to be made, so it does help a lot. Where quad trees should be most helpful is when you have irregularly distributed objects, which allows some of the branches to just be ignored entirely.

The thing about Bound and Sweep is that it's only O(n) *after* the bounds have been sorted. Nearly all known sorting algorithms are O(nlogn), which quad trees are too, so while Bound and Sweep is a lot faster than a brute force approach (where you test every possible collision) would be, it's still slower than most spatial hashing algorithms, including the one featured in this video. I actually just spent some time implementing and testing in my collision test bench, and while it's competitive at

@@ClokworkGremlin use O(n) sorting algorithm, like radix binary tree sort, you can add and remove items from the tree super fast without a new sort also, I just also tested that sorting algorithm in java against Arrays.sort, holds up until like millions of elements, because of system sort native optimizations.

@@ClokworkGremlin yes you can modify the axis sort tree just like with 2d quad tree and 3d octree.

@@ClokworkGremlin in other words, you can separate the axes for the limit values completely, ie separately check x, y and z axes limit intersections. and use linear time sort. ironically radix binary tree sort is 1D binary tree.

You'd use octrees for that

kul-sudo/quadtrees on GitHub. Have it done with gravity.

You can check out kul-sudo/quadtrees on GitHub for the implementation

that's C

good question

blur

​@@rustwithoutrustvery avant-garde 🧐

@leeroyjenkins0 Yeah, have you seen the subtitles? I've been grinding French and decided it'd be good to make French subtitles. If that's what you mean.

@rustwithoutrust oh! 😂 No sorry I just picked an artsy word for fun Best of luck with that! It really is a crazy language..! I happen to speak it fluently, it's very understandable! Other than working on common idioms. Some notes as an aside "here's the point" would probably be "en résumé" in this context, and often point would be more "argument" than "point" even if it's usually understood, especially in Canada I'd guess. "Move into the cell" would be more "Dans" than "dedans" if you specify the object of "what is it moving into" you don't use the "de" as that's what "de" is referring to. "Utile pour des collisions" would be more "utile pour les collisions" mostly because you're talking about "collisions" as a concept. Small details like that. Also, for this type of video you'd probably address the audience as a plurality so sticking more towards "vous" (not necessarily as the polite form, just addressing all viewers at once), but that's nuanced by the target audience, including the fact that "tu" is more prevalent in french Canadian. That aside neat bite-sized video ^^ Cheers!

I'll probably make French subtitles for all my videos, because that could be good practice for me. Moreover, I'm soon starting to read a book in French that'll definitely boost me and give me more understanding of those little things!

Excuse me, what? That is simply a lie without any base under it. Moreover, you can run it all yourself and see that difference.

@@rustwithoutrust I assumed the numbers on the corner of the screen are the particle counts. Is that not what they are?

It's said it's the processor time

@@ClokworkGremlin you should maybe watch the video you're commenting on? He literally says what the number is in the video.

@@rustwithoutrust Ah. I missed where that was mentioned at 1:30-1:31. How many points were in this test sample? I've found the overall gain varies wildly based on the density of points being tested. At 1,000 points, varying from 1 and 5 units in radius, across a 1,000x1,000 unit square, I have both a sparse grid-based system and a quadtree based system that run close to 20x as fast as the brute force solution. At 10,000 or more points under the same conditions, the brute force solution is no longer viable due to both time and memory constraints. Working on a bounds sorting solution now, to see how it compares. The dense grid works about the same as the sparse grid, but takes up considerably more memory.