As a physics engine developer, I want to point out that while QuadTrees and Octrees are often praised for their performance, they aren't always ideal for certain tasks, especially in physics engines that require advanced features like raycasting or shape/sphere casting. These data structures struggle with irregularly sized objects that exceed the size of a cell, and there's significant overhead when performing raycasting because of the DDA-style stepping required through the Quadtree or Octree cells. Physics engines like Bullet, Box2D, Jolt, and my own full-featured 3D physics engine KRAFT (written in Object Pascal) all use dynamic, self-balancing AABB BVH (Axis-Aligned Bounding Box Bounding Volume Hierarchies) trees for optimal performance. PhysX, on the other hand, relies on Sweep and Prune (S&P) for broad-phase pair management and also uses AABB BVH trees for efficient raycasting.
@@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?
@@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.
6 years ago I did a physics collision system using quadtrees where I generified the node to have any number of leaves. Turns out adding way more leaves into a single node was tonnes faster, and reducing depth. I ended up with an optimal solution having just a depth of 2: chunks and cells. So my recommendation to have a super fast grid of bins would be to just have a hashmap of chunk coordinates to chunks, where each chunk is an array of cells. Its super simple to implement and very very fast, while retaining a lot of the space saving, since empty chunks can be removed from the hashmap.
Those last 10 seconds was something I never quite got with quad trees, until I saw this video. So like… because cells overlap, an object can be in multiple cells? That’s subtle but genius!
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.
Can you implement this on scratch so I can see this more clearly? When working on quad-trees, I noticed that it is impossible to make it work when you have a dense map of small and big objects I just don't understand 2:02 to the end
One huge optimization is making your grid scale suit it's purpose. What's the smallest and largest item? Some game engines have a stroke with many large or small items.
Cool! I'd like to hear what you think about implementing QuadTrees implicitly using BTrees and Z-Order curves, if you've tested it or have a benchmark, the implementation might be much simpler and simplicity is definitely a plus! What happens is that each two bits in the Z-Order key will represent a position in a layer of the QuadTree. So you can use a modified QuadTree function (which generates the next z order index within a range) and iterate over a BTree, doing a new range search with the next valid index when the iterator falls outside of our query rectangle. It does improve data locality in memory and reduces allocations, and the branching factor of a BTree (rust uses 11) is better than that of a QuadTree (4), but it restarts the search from the root for every quadrant. I don't have a benchmark in hand, unfortunately.
@@rustwithoutrust The k-dimensional data structures, like space filling indexes, can do queries for things that are not points: Rectangles (a, b, c, d) and (e, f, g, h) intersect if (0, 0, a, b)
Hm dynamic area codes. Is this optimal for uniformly sized objects like you have here? Since they are all the same size you could scale the area the objects are located such that the radius of the objects you are testing is so small it might as well just be a location in space. Then you don't have to worry if any object is overlapping more than one area code and you can simplify the collision to two coordinate equality tests.
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.
How well do quadtrees adapt to three dimensions? I have a project that handles hundreds of thousands of particle interactions in 3D space, the approach I used was fixed grid where particles only talk to other particles in their own or adjacent grid slots. But because the grid is fixed, it can still have fairly substantial performance slowdowns if the particles are forced to congregate.
@@lanata64 Well, if an object moves, it can always potentially collide, so this is the most natural approach to check for a collision on every position change.
@@rustwithoutrust well yeah, but i was wondering if a continuous cd method that doesn't use 'overlap-checking' in the same way might be faster if you can lower the tick rate (since the max tolerable movement per tick could be far higher)
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 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.
Bro, how would you recommend to learn rust, I have tried plenty of times but I just can't get over it's syntax. I find golang syntax easy and works for me.
I think overcoming syntax mistakes takes making a couple of relatively big projects. What you could have even bigger problems with is the borrow checker, but most of the time fixing errors related to it includes changing the structure or the logic for it to be memory-safe; that also takes a couple of projects to overcome. But you aren't forced to use Rust, so if Go works for you, keep in mind it's garbage-collected, which is its disadvantage. The way I see it, if you need a company-level codebase that never segfaults and is easy to maintain for years, Rust is your option.
Very nice! I want to use something similar but on GPUs, basically render all these points interacting with each other through gravity (or charge repulsion), I was wondering how fast a Rust implementation would be to render them in real time. How many points did you have in this video and how fast was the simulation? I was wondering what would it be like for ~10k points, and also whether you multithreaded this, I think quadtrees might be a bit hard to parallelize but the spatial partitioning idea seems simpler.
@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!
[Edit] Correction: the number in the corner is processor time, not point count, as per 1:30 [Original post]1:35 FOUL! Your brute force implementation used 500,000 points, but your quadtree implementation used only 50,000. It's easy to get a massive speedup when you reduce the test size by 90%.
@@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.
As a physics engine developer, I want to point out that while QuadTrees and Octrees are often praised for their performance, they aren't always ideal for certain tasks, especially in physics engines that require advanced features like raycasting or shape/sphere casting. These data structures struggle with irregularly sized objects that exceed the size of a cell, and there's significant overhead when performing raycasting because of the DDA-style stepping required through the Quadtree or Octree cells.
Physics engines like Bullet, Box2D, Jolt, and my own full-featured 3D physics engine KRAFT (written in Object Pascal) all use dynamic, self-balancing AABB BVH (Axis-Aligned Bounding Box Bounding Volume Hierarchies) trees for optimal performance. PhysX, on the other hand, relies on Sweep and Prune (S&P) for broad-phase pair management and also uses AABB BVH trees for efficient raycasting.
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.
6 years ago I did a physics collision system using quadtrees where I generified the node to have any number of leaves. Turns out adding way more leaves into a single node was tonnes faster, and reducing depth. I ended up with an optimal solution having just a depth of 2: chunks and cells. So my recommendation to have a super fast grid of bins would be to just have a hashmap of chunk coordinates to chunks, where each chunk is an array of cells. Its super simple to implement and very very fast, while retaining a lot of the space saving, since empty chunks can be removed from the hashmap.
That's cool. Thanks for sharing
this I understand. I did not get the quad tree. not the creators fault. im slow and not too bright.
BLAZINGLY FAST 🔥🔥🔥
it's actually all a scam
Those last 10 seconds was something I never quite got with quad trees, until I saw this video. So like… because cells overlap, an object can be in multiple cells? That’s subtle but genius!
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.
it's like that with a lot of data structures, like spatial hash maps too.
That's some weird looking Rust code.
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!
this will be a great channel to follow as im making my own game engine haha, great content! I never thought of this approach, this is very nice :3
thanks!
quadtrees make me happy
relatable
It could be expanded to use octrees for 3D environments :)
I've implemented this during a research internship.
Wake me up when it’s oct trees
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?
Octtree is exactly the same but in 3d. Instead of 4 leaves in node you have 8.
0:26 i see 2 balls intersecting 👀
Nice video, I'll have to try this out as a project soon.
Yeah, that was a glitch I've fixed already lol
Thats craaazy
real
Can you implement this on scratch so I can see this more clearly? When working on quad-trees, I noticed that it is impossible to make it work when you have a dense map of small and big objects
I just don't understand 2:02 to the end
You can check out kul-sudo/quadtrees on GitHub for the implementation
One huge optimization is making your grid scale suit it's purpose. What's the smallest and largest item? Some game engines have a stroke with many large or small items.
Cool! I'd like to hear what you think about implementing QuadTrees implicitly using BTrees and Z-Order curves, if you've tested it or have a benchmark, the implementation might be much simpler and simplicity is definitely a plus!
What happens is that each two bits in the Z-Order key will represent a position in a layer of the QuadTree. So you can use a modified QuadTree function (which generates the next z order index within a range) and iterate over a BTree, doing a new range search with the next valid index when the iterator falls outside of our query rectangle.
It does improve data locality in memory and reduces allocations, and the branching factor of a BTree (rust uses 11) is better than that of a QuadTree (4), but it restarts the search from the root for every quadrant. I don't have a benchmark in hand, unfortunately.
Hey, I'll take a look at it and maybe do a video.
@@rustwithoutrust The k-dimensional data structures, like space filling indexes, can do queries for things that are not points:
Rectangles (a, b, c, d) and (e, f, g, h) intersect if (0, 0, a, b)
Very nice
Hm dynamic area codes. Is this optimal for uniformly sized objects like you have here? Since they are all the same size you could scale the area the objects are located such that the radius of the objects you are testing is so small it might as well just be a location in space. Then you don't have to worry if any object is overlapping more than one area code and you can simplify the collision to two coordinate equality tests.
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.
Amazing thank you
hell yeah
How well do quadtrees adapt to three dimensions? I have a project that handles hundreds of thousands of particle interactions in 3D space, the approach I used was fixed grid where particles only talk to other particles in their own or adjacent grid slots. But because the grid is fixed, it can still have fairly substantial performance slowdowns if the particles are forced to congregate.
You'd use octrees for that
what kind of collision detection are you using? just checking if two bodies overlap/touch, or is it something else?
@@lanata64 Yes, whether they overlap.
@@rustwithoutrust i wonder if it'd be faster to do some sort of continuous/'event based' CD, and then lower the tick rate.
@@lanata64 Well, if an object moves, it can always potentially collide, so this is the most natural approach to check for a collision on every position change.
@@rustwithoutrust well yeah, but i was wondering if a continuous cd method that doesn't use 'overlap-checking' in the same way might be faster if you can lower the tick rate (since the max tolerable movement per tick could be far higher)
sometimes you only need to sort bounding volume axis limits to get the collisions in O(n) time, faster than quadtrees.
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.
Bro, how would you recommend to learn rust, I have tried plenty of times but I just can't get over it's syntax. I find golang syntax easy and works for me.
I think overcoming syntax mistakes takes making a couple of relatively big projects. What you could have even bigger problems with is the borrow checker, but most of the time fixing errors related to it includes changing the structure or the logic for it to be memory-safe; that also takes a couple of projects to overcome.
But you aren't forced to use Rust, so if Go works for you, keep in mind it's garbage-collected, which is its disadvantage. The way I see it, if you need a company-level codebase that never segfaults and is easy to maintain for years, Rust is your option.
@@rustwithoutrust so what would you recommend ? I start with a rust book and build project after that :) ?
Yes, I recommend to read the official book and go through a few unofficial ones. But ultimately, you'll learn the most from building a project.
@@rustwithoutrust thank u so much !!
Very nice! I want to use something similar but on GPUs, basically render all these points interacting with each other through gravity (or charge repulsion), I was wondering how fast a Rust implementation would be to render them in real time.
How many points did you have in this video and how fast was the simulation? I was wondering what would it be like for ~10k points, and also whether you multithreaded this, I think quadtrees might be a bit hard to parallelize but the spatial partitioning idea seems simpler.
kul-sudo/quadtrees on GitHub. Have it done with gravity.
where can I find the code for this project?
the repo is in the description
Does blazingly fast refer to the algorithm or the video??
good question
Interval trees
what is that weird effect where it looks like text is jittering
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!
probably would have been better to do this in either C++ or Python, as the Rust code is clearly not comprehensible.
that's C
[Edit] Correction: the number in the corner is processor time, not point count, as per 1:30
[Original post]1:35 FOUL! Your brute force implementation used 500,000 points, but your quadtree implementation used only 50,000. It's easy to get a massive speedup when you reduce the test size by 90%.
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.
YYYY