Quirky Quad Trees Part1: Static Spatial Acceleration

[@mr_noodler]

The brilliance of javidx9 is his humility, not once does he tell anyone that he has a PhD in computer science, and the head engineer of a major robotics company, he just wants to share the beauty of his craft with others in a gentle and kind way. I really like and respect people like him, thank you for making great videos!

[@vid2422]

Wow that's truly impressive assuming it's true (no offence I just can't believe anything I hear)

[@bravefastrabbit770]

@@vid2422 That’s right you shouldn’t just believe whatever is thrown your way, but instead make inductive inferences. If this Very knowledgeable tech guy who clearly operates on a level of abstraction way beyond the average person, says he had a PhD, and not just shows off but shares & teaches his knowledge on a far higher level than others within the same domain. I think its pretty fukken safe to assume he is being truthful, especially when everything about him just reeks of congruence 🤦🏼‍♂️

[@tomkirbygreen]

He’s all these things and a rather awesome human being too! 😀

[@ArnaudMEURET]

@@bravefastrabbit770The whole point is precisely that he does NOT say it. Another rando says it!?! Help me follow your reasoning here!

[@BarbarianGod]

4:05 I will *not* stop giggling! lol

[@jhfoleiss]

I'm not sure why people think that recursion is "bad". As long as the time and space complexity of the recursive algorithm is logarithmic, it is guaranteed to run efficiently. When the problem is inherently recursive, like the one brilliantly explained in this video, the code is absolutely more elegant and usually shorter. Great video BTW!

[@ThankYouESM]

I found out the really painful way that the recursive can run out of memory.

[@jhfoleiss]

@@ThankYouESM When we're starting out learning recursive algorithms this happens more often than we care to admit! It's ok! As you gain more experience, you come to realize the patterns that are associated with efficient recursive algorithms (and the ones that are not!).

[@quentinquadrat9389]

Recursion is bad with languages that does not know how to deal with recursively such as C, C++, Java ... (no tail recursion elimination) If you use language made for recursively (such as OCaml) this of course make algorithm simpler and code optimized (recusion becomes and iteration). And quadtree is not always an logarithmic algorithm: you can obtain "degenerated" quadtree: for example, an empty scene with highly detail house with plenty of rooms in the corner of your scene. You quadtree will looks like a list. Ok in this case you fire the graphical designer :D

[@MrVinicius5000]

Such a coincidence! I was implementing, experiencing and burning my brain with quad trees and moving particles, I tink I will have a iconic OLC help :D

[@kunedroid3446]

"I will assume this space is a square... and I am illustrating that perfectly with this rectangle..." -- Javidx9 hahahahahahha

[@SassyToll]

GREAT!!!! to see you back making videos my friend! John in Ireland, I have learn so much from you, thank you

[@Max_Stupa]

David, I would like to give you so much appreciation for your tutorials, especially this one.

[@smallbluemachine]

Like many have already said, the format of these "lessons" is invaluable, it so practical to comprehend. I've been mulling quad trees for an upcoming project and this is a great way to get the additional insight I need to make better technical decisions. -Really going to enjoy this, thank you.

[@TheKhalamar]

As you said there are multiple ways of implementing quadtrees and you picked one. I think the main flaw with this approach is that if an object overlaps children 1 and 2, and I am only looking at child 4, the overlapping objects will be rendered as part of the parent, even though they are not visible. The alternative is to add objects to all the children they overlap, but in that case they will be rendered multiple times, which can also have bad side effects (especially when using transparency). In that case, your container can help if you store each item as a pair (object, rendered). You set that Boolean to true if the search determined the object must be rendered. However that requires you to clean those booleans on each frame. What you can also do is store the frame counter instead. This approach also breaks your quadtree's implementation of size. That is fixed by your container, but one could also keep track of the counter on each node and increment that counter when inserting an object. Finally, your approach automatically builds a tree of depth 8 if an object doesn't cross any edge. What I like to do is to split a node only if it reaches a critical amount of objects (say, if there is more than 20 objects, then I start splitting them). This is best for static trees though, as managing that gets quite hairy when working with dynamic trees. As always, it really depends on what you need. Thanks for the great vid!

[@wubalubadubdub1116]

your videos are a goldmine of information, thank you

[@boondocksripoff2237]

Ah the channel that made me love c++

[@thecakeredux]

One of your best videos, this was a real treat.

[@BudgiePanic]

great video, reminds me of the data structures and algorithms course I took last year. One assignment was putting map data into a quadtree to speed up location selection.

[@VoidloniXaarii]

This was quite brilliantly mind-blowing, and you handling it in a modern c++ stl like workflow made it even more so. Thank you so much! This is such a powerful data structure! Also thank you for touching on the dirty word of recusing, hope u do more of this boundary crossing as I've since uni felt there's a lot of potential there... Just one i don't intuitively get

[@javidx9]

Thanks buddy! Part 2 does indeed cover moving objects.

[@0xoldschool17]

javidx9: pans the camera youtube compression: goodbye

[@mycotina6438]

This got my attention right away, because I happens to muse about the same exact problems a couple years ago when I was creating my game during a college project. Unable to find a proper keyword back then, I ended up with a custom made algorithm. Quite effective and fast but with a lot of limitations, it only works for tiled maps and definitely doesn't support dynamic movement of objects. So I'm very excited how you'll make this dynamic!

[@jhonrodriguez213]

im glad to have you back, im not even a native english speaker or program in c#/c++ this days but i learned more with you that my my college professors.

[@SantoLucasST]

25:04 this right mr. officer

[@smartito_97]

Yes!!!! Finally!!! Spatital partition video!!! Thanks David!¡¡¡¡¡!!

[@JamesClarkUK]

At university I used oct-trees (3d quad trees) to speed up some n-body simulations for galaxy formation. They're pretty cool!

[@rishitsingh6621]

Can I get the source code?

[@JamesClarkUK]

@@rishitsingh6621 afraid not, I haven't had access to it for a long time

[@jamilaelkadia6630]

how does octree work? since models have 3 dimensions, it's not easy areas

[@JamesClarkUK]

@@jamilaelkadia6630 you use the volume of the node instead of the area

[@TheMrDemonized]

​@@jamilaelkadia6630it works the same as quad tree but with 8 octants representing cubes

[@nerdrage562]

Good video, explains in an easy way how quad trees work! I have some optimization thoughts anyway :) The first thing, it's that list, I understand that iterators not getting invalidated is a big advantage, but I'm not sure that it makes up for the speed that vector gives while iterating millions of objects. In this case, contiguous memory becomes huge. The other thing, but this is purely a design choice, I would have directly stored pointers (I think this could be a good place for raw pointers) in the tree, and used an external container to keep the objects. The idea is that the tree is purely a search structure and doesn't "own" the objects.

[@samarthtandale9121]

Amazing !!! Can't thank you enough for the amount of stuff I learned in this 1 hr 🔥🙌🏼

[@piotrwyrw]

Yayy another javid video!

[@miladhashemzadeh5626]

Such a gr8 and usefull and fun this channel has thank you a lot my friend.

[@Ethanthegrand]

I have been following along your channel for awhile now and its great! Cool thing is that your way of teaching is so efficient that I can remake these programs in completely different languages and pixel engines while creating the same thing! Can't wait to see what you have next for us. I quite like the game engine series too. They are great fun!

[@francescobottino3892]

At 25:15, you first calculate if the item fits inside the child and then check if you can actually create a child. If you are actually at max depth, it's useless to check if the child can fit the item, you won't be using it anyway. So, as a small performance improvement you should put the check on max depth BEFORE the calculations for the child fit.

[@Ferenc-Racz]

Ty for your deep and quality videos!

[@fudgeracoon2529]

Great tutorial as always

[@AlessandroBria]

Wonderful explanation, thanks! I will show this to my CS students. I am looking forward to see part 2 :-)

[@capability-snob]

Very cool. Another data structure that I like for spatial data is the gist index. These are a type of btree where subtrees may overlap. This helps to deal with the problem that the centre lines in world space probably intersect a lot of shapes. Why should the centre be special, anyway? The drawback is that a single shape may appear in more than one subtree, so the final filter is a little more involved than just checking the bounding box.

[@GregoryTheGr8ster]

Don't forget that you can use a deque instead of a list. The vector is a poor choice if you don't know how many items to allocate (or reserve) in advance and you want to store pointers to the items in the container. The deque gives you a good compromise between a vector and a list in this situation. Another alternative is to use a vector as your main container, but to store indexes rather than pointers to the objects in your quad tree.

[@brynyard]

Fun fact: Because nodes in a list is "scattered", require memory allocation and node data is addressed indirectly, it is so slow that storing the data in a vector us usually quite a bit faster, even when you have 1mill elements. TLDR; Always check.

[@wjrasmussen666]

Hey Javidx9, nice to see you posting again. Hope all is well with the family. I am wondering, what would we need to do if we were to allow the rotation of our canvas?

[@jhfoleiss]

I would use a bounding box to represent the area of the shape.. thus the search/insertion logic would remain the same.

[@bone0]

I had this on in the background while I was playing wow lol so I could be wrong as I wasn't paying full attention but you're already storing objects in shared pointers which means you can get away with having a vector instead of a list anyway? you then get the speed advantage of a vector as apposed to a list with little drawback (unless you're constantly adding and removing items of course)

[@mehulajax21]

Maybe octrees next...would a great to look into 3d partitioning... Big thumbs up for this one...

[@shinobuoshino5066]

What's interesting to me the most is that while these data structures are cool and all, taking the idea and applying it to your specific project is going to be objectively better, for example, platformer that's limited to either vertical or horizontal levels with little space in orthogonal direction, can work better if you have a vector of vectors, and in some less dynamic cases, vector of ranges into some static data structure, and if you can ahead of time limit the maximum size of a given level, you may aswell have statically allocated array, blazingly fast and no risk of memory leaks no matter what terrible programmer touches it. For example, let's say you're making a mario clone, and you subdivide each world into 32 tile wide chunks, and each of those chunks can have up to 16 objects (enemies) that aren't terrain... You can take player's coordinate, and use it to index into this array of chunks simply by using x / 32, which is very fast because power of two division is just a bitshift. Search is also fast, because you only ever need to check up to 16 objects in a given chunk, linear search will more than suffice. There, it's definitely not an octree, it's something faster and more cache coherent than octree, and fits this style of game perfectly. For vertical levels, you'd use y coordinate... For levels that have both you could have a matrix and divide into chunks by x and y and index into linear array directly via x * width + y... It's a bit less local but in the end will still be faster than an octree unless that octree is designed to have limited recursion which again, is just specialization for a structure that's in its idea, generic. Instead of an octree which has a lot of indirection, it's just dumb array that minimizes indirection. In the end, it all boils down into setting up your data in a way that makes binary search as easy as possible. For a very big world, ideally, you'd have a chunk system, and loaded chunks would be in a virtual matrix that follows the player, once again you can index into individual chunk by simply dividing up coordinates of object of interest to check which chunk you should look in. Games like minecraft seem to do it this way. Not to say that octrees aren't useful... After all, the idea behind them is how I came up with more efficient implementations when problem is well defined.

[@SylphDS]

I see you store the subtrees using shared_ptr. Is that just a matter of habit or are there use-cases where you'd want to share ownership of these subtrees with other entities?

[@jonatanlind5408]

An interesting use case should be 'persistant data structures' though in this video it is probably a force of habit. These are typically characterised by how each node is read-only after construction. This allows for large datastructures to share internal data with other permutations of itself with minimal data duplication. As an example a simulation can use a quadtree to keep track of objects and this quadtree is a permutation of itself from the previous iteration. More interestingly perhaps is how such a quadtree can be copied for, say, serialization to disk with no data duplication and without introducing data races.

[@quentinquadrat9389]

If shared_ptr are purely internals (not exposed by public methods) it's indeed better to use unique_ptr (lighter but you need C++14 since make_unique is not given with C++11). If your class have getters on smart pointers, I prefer returning the reference of their content since the issue of shared pointer is who is the real owner ? At 21:58 deleting smart pointers (the root node) will implicitly delete children node, but we have to care that this implicit recursion does not make stack overflow like any recursive functions. In all cases, I would have tried a quadtree implementation without any allocations at all if possible: array

[@ronnybrzeski7558]

Great video, this and other ressources helped me to implement and understand a quad tree, but i dont get such insane result changes. I think it is because i test against 100-300 units rigth now. I believe a quad tree is better the more stuff is going on, so here i will test it soon with around 10k things and will see if it makes a difference. But nice video and nice dude, really nice to watch.

[@RogerisNatlia]

I love you, for what you do!

[@TheGlmaster]

Great video!

[@xeridea]

You could use a vector, just need to clear quadtree if vector resizing causes a reallocation. If you initialize vector larger than you would need, you only need to clear quadtree if inserting will cause reallocation. If you check vector size vs allocated amount before inserting, you will avoid glitches. If code is multithreaded, need to mutex insertions. A cheap price to pay on inserts, compared to always allocating on new insert with list.

[@chriss9611]

Enjoyable video. Would like to mention that you COULD use a vector instead of a list, if you referred to items in the vector by index instead of by their address (pointer or iterator). Then, even if objects in the vector are relocated due to reallocation, their offset from the beginning (wherever it is or becomes) remains the same.

[@ItIsYouAreNotYour]

When is the 2nd part coming out? I like when quadtree examples have the rectangles appear and you can see it subdivide. I think it demonstrates the point better than tracking the numbers.

[@Jkauppa]

if you store the previous search results, frame by frame, you can get even faster "cached" results, because assumption the view point will not change much

[@Jkauppa]

if you want a static draw order, then store the draw order in the pointer list, ie, z-order depth, then paint into z-buffer

[@Jkauppa]

epic dude!

[@ThanhNguyen-rz4tf]

Hope you upload part 2 soon

[@SchalaArchives2023ish]

Quad trees can be useful also when pixelating an image. I did this manually for Minecraft art by drawing grid lines to subdivide various parts of a non-blocky image. Its 3D sister, octrees, are good for voxelising 3D meshes. I'm not sure if Minecraft does the octree approach or the more complicated Marching Cubes algorithm.

[@MCSteve_]

no the game is completely rasterized. with a chunk loading system

[@SchalaArchives2023ish]

@@MCSteve_ oh, I see

[@Otakutaru]

Hey Javid, a nice follow up for a quadtree is the generalized KD tree, just saying... :)

[@davep7176]

3:32 ...what is "Space Thing on Twitch" lol. I am very curious now :D

[@javidx9]

Well you can start here, and watch all the mission logs on javidx9 extra channel! kzbin.info/www/bejne/hGrQn6uHgZmfbpI

[@Ash_18037]

Nice information. However for 2d spatial acceleration I've never needed to use a quad tree. Instead the simpler spatial map has always done the job and is quicker then a quad tree to implement and at runtime. So it would have been good to hear what a spatial tree gives you over a simple spatial map, if anything. By spatial map I simply mean adding a reference to all objects to one large array where the objects X and Y coordinates are divided by some 'cell size' and that produces an index into the array (each array location is an array or list of objects at the location). If your world is absolutely huge with big areas on empty space, I believe spatial maps are more memory efficient (no need for any cells covering these empty spaces) , but apart from that are there any other benefits?

[@jmscreator]

I agree here, but it really does depend on the size of the world and the density of the objects, as well as the grid cell size.

[@spacewad8745]

hey nice to see you back my man

[@sevryb]

Hello! I have long been interested in developing applications with a graphical interface, tried many GUI libraries (Qt, FLTK, WxWidgets, etc.) in C ++. I have always been interested in how the above-mentioned frameworks work (drawing queues, event processing). I tried to use the SFML graphics library and create a set of widget classes, but there were many questions about their effective rendering, event handling, and organization of the main program loop. So I have a question. Can you suggest some resources where I can get acquainted with the architecture of GUI libraries (with retained mode) and examples of their creation, because there is a great desire to try to create something of your own to gain new experience in this field? Sorry that it's not related to this topic) Thank you in advance!

[@anonymoussloth6687]

This might be a stupid question but at 37:38 why did you write typename there? Don't we write typename when we create the template and not when we use it?

[@javidx9]

Templates of templates of templates can start to look a little ambiguous to the compiler. Typename helps it along.

[@PleegWat]

Doesn't C++ allow adding custom iterators on your arbitrary data structures?

[@badasahog]

This reminds me of bounding box hierarchy traversal in ray tracing

[@BudgiePanic]

QuadTrees Oct trees Binary space partitions K-d trees The four spatial partitioning data structures you should be aware of.

[@Redmat527]

What about bounding volume hierarchy?

[@BudgiePanic]

@@Redmat527 I haven’t encountered that one before. Add it to list.

[@Ash_18037]

You also completely missed the simplest (and often best) partitioning data structure: spatial maps (bins). So many people completely overlook these in favor of cooler sounding Quad trees etc when they only need bins.

[@boggo3848]

Probably that's later in this video or a future one (haven't finished yet), but I had to write one of these for something recently and ultimately I ended up using Morton curve encoding which achieves almost the same result implicitly with a fraction of the memory and CPU cost.

[@javidx9]

Morton curves work well when combined with a hashmap and give great performance, if you can reduce your problem to the integer domain easily enough. Adding floating point area into the mix makes it a little more complicated however. Still people should read up on Morton for their implementations.

[@rijenkii]

4:01 I love you.

[@mr.fishfish570]

Awesome

[@churchchurch2367]

All this time and the grape soda is still on the desk untouched...

[@dynamics9000]

How wonderful video and channel this is. found it very informative channel, subbed and liked . a fellow creator

[@Janokins]

I was wondering why you were dividing the size by two when it should a quarter of the area, then I realised that size is a vector2, so you're doing 2 divide by twos :D

[@javidx9]

Lol yeah I guess you get used to working with coordinates that little oddities like that become second nature 😄

[@christianwaldmann7256]

How on Earth can I get this to work with a remove function? I've been trying for hours but there's this type conversion error and I can't figure it out. Has anyone gotten a working remove function?

[@__top_5250]

hello i got the vita3k emulator code so i want to make it for android HOW I CAN MAKE THAT POSSIBLE?

[@__top_5250]

I ASKED HERE BECAUSE WHEN I GO TO REDDIT OR QUORA I CAN't pass throw verification of any browset

[@chair547]

why are the pointers to the subtrees shared_ptr instead of unique_ptr

[@TimothyChapman]

Are you going to do a tutorial on how to generate a dynamic mesh from a quad tree?

[@nicoautiavlogs7308]

It would be funny to imagine an artist (non-programmer) who only knows the audio track and has to illustrate it. ("I want to calculate the area of any children I might potentially have")

[@CB66941]

Question, during the last part of the video, where you changed the linear search from a vector to a list, do you then also need to change it from Debug to Release? Because I tried it with Debug and the screen was just plain white without showing anything, but for Release it worked fine. Why is that?

[@javidx9]

Because debug on a slowish machine is very very slow! It probably never even drew the first frame

[@CB66941]

@@javidx9 thank you for the explanation~

[@vladalex9556]

Literally did the same mistake, but in my case I forgot to call initialize so I didn't have the size initialized :)))

[@ashwinalagiri-rajan1180]

Hello Javid, I've recently been exploring graphs visualization for various graphs and trees. I was wondering if you can perhaps do something similar with Pixel Game Engine. I like your explanations and I'd like to see how you think through a problem like visualizing (eg. Binary Search Trees).

[@jmscreator]

A binary tree can be represented in nodes, where each child node rotates based on the parent connection.

[@ashwinalagiri-rajan1180]

@@jmscreator ok?

[@twobob]

"It's called Root because it's the top level of the tree." Zero irony, straight-faced. :D

[@samuelecanale5463]

You killed me with the balls joke

[@Alex-fp2sx]

where is the second part

[@goshisanniichi]

43:40 But what about spatial acceleration structures through the medium of dance?

[@sephirothbahamut245]

Wouldn't deques instead of lists solve all the issues you're using lists for, while still being faster to iterate?

[@haikamu3864]

Can i use quadtree for more efficient tilemap rendering?

[@javidx9]

If all your tiles are same size, no, you always know where you are in a such a tilemap anyway. If they vary in size then quadtree is perfect for it.

[@HCPP20334]

C++ One Love❤️❤️❤️

[@Solarbonite]

Thanks for the video! I love the use of modern C++. Selfish idea: a series on WGS84 could be fun (totally nothing to do with me having to learn it soon 😉).

[@danielegurizzan]

The Quad Trees get a bit quirky at night...

[@novemberdev8292]

I wonder what is being used in 3D these days... In 2D it's quad trees, in 3D it used to be oct-trees, but now it seems to be bounding volume hierarchies

[@GameBacardi]

Nice, long time no see

[@DaveLeCompte]

8:16 "Rather than fiddling about with the standard random library..." float(rand()) / float(RAND_MAX) * (b - a) + a; Seems like TWO uses of the standard random implementation. I was hoping for some sort of fancy modulo hack.

[@anter176]

the random library has more advanced RNG than rand, which are better but more fiddly than just using rand.

[@AJMansfield1]

Why `std:shared_ptr` for the quadtree children rather than `std:unique_ptr`?

[@tunit6458]

You very smart man

[@ArnaudMEURET]

The more modern C++ crawls to get the more ugly its syntax gets… 😩 If only you could learn Rust. Thanks for the primer on Quad 🌳s.

[@javidx9]

I agree that "modern c++" syntax gets messy, well the template stuff does, but I have absolutely zero interest in Rust.

[@dandymcgee]

It might be worth the memory savings to just re-calculate the child rects every single time rather than storing them. If this performance matters to you, benchmark your own implementation and find out!

[@jw200]

Part 2 when? Are you ok? Lost motivation?

[@javidx9]

Quite soon actually. All will be explained in the video, but I needed some emergency surgery from which I've been recovering! Much better now though.

[@frankhaug1517]

balls. kek.

[@dandymcgee]

Quad trees are cool, but why does nobody talk about R-trees? They're so much cooler.

[@dandymcgee]

I found out why.. because they're wayyyyyyy harder to implement. 😅 But still way cooler!

[@ExCyberino]

those arent balls, those are circle, i think

[@OscarSommerbo]

This is at the edge of my understanding but Quad trees as implemented in this video seems like "just" binary trees. Well two of them.

[@wes8190]

Spatial acceleration structure? I barely know her.

[@esepecesito]

Would you ever consider stop using Hungarian notation for variable names?

[@javidx9]

Nope

[@tcoder4610]

Why does this algorithm remind me so much of the classical Doom algorithm for fast rendering.

[@TheBOSS-cd7ck]

first

[@MaxCE]

yo

[@T3RRY_T3RR0R]

Stop laughing you say. I made it as far as Balls for everybody...

[@felipedorosario4793]

Idk what I'm watching

[@aston.6487]

J

[@EximiusDux]

Stop giggling!

[@kallewirsch2263]

There is something in your coding style that bothers me since a number of episodes and I think I should address it. And this something is your light hearted use of "float" The short story is: unless there is a very good reason, you DO NOT WANT to use "float". The data type of choice for floating point variables is "double". float has1 very important drawback. It is only 4 bytes in size. Which means, that the mantissa is accurate only to an average of 5 to 6 decimal signifikant digits. Which means that in a number like 10000.00f, you have already used up 5 decimal digits to the left of the decimal point. The first digit after the decimal point is somewhat accurate (mostly because you have not done arithemtic with it) but the secnd digit is already a guess work (for not to say "a lie"), You get away with it, because 10000.00f is a whole number and a float can do that. But try that with something else. Eg. #include int main() { float frst = 12345.67f; double scnd = 12345.67; if( frst == scnd ) std::cout

[@HansUhlig]

Cool Story bro... However if you're going to go this route you might want to start using a multiprecision library exclusively as double has the same problem with only a smaller epsilon. Either that or realize the same thing most data scientists do, that despite introduction of small levels of error, statistically it doesn't matter. Dealing with real numbers in base 2 will always have some level of error at some precision and you should tune your precision to the level of accuracy needed by your problem. Floats are smaller, less precise, but good enough for most problems. Plus most hardware is designed for fast 32 bit floating point arithmetic, far less so for 64-bit, 128-bit or 256-bit floating point arithmetic. As for it being a serious flaw in most libraries, most libraries offer both. 32-bit for those who want speed and a little inaccuracy doesn't matter and 64-bit for scientific work that requires high precision even at the cost of speed.

[@capability-snob]

The rule of thumb has generally been floats for input and output, and doubles for intermediate calculation. The idea is that you can comfortably lose some accuracy at rest, but in a situation where small errors may compound, having the extra detail is totally worth it.