Quirky Quad Trees Part1: Static Spatial Acceleration

hello and welcome to the first of a two-parter about spatial acceleration structures in particular i'm going to be discussing the quad tree when i originally thought about making this video it was just going to be a one part video but as i was developing the code for my quadtree there was lots of interesting asides and and performance profiling things that i thought were worth discussing so i've turned it into a two-parter but don't worry the second part has already been filmed as well so why might you need a spatial acceleration structure well let's take a look at the example as with all of my videos that focus on an algorithm specifically there's always a bit of an out of context rather bizarre demo that needs explaining and this one is no different here i have a sea of rectangles you can see them all different shapes and sizes and colors in fact there's one million rectangles in this display the frame rate will tank if i attempt to try and display them all but they are there all one million off and along the top here i display how many rectangles are actually visible out of the 1 million on the screen at any one time and i display how long it took to decide which rectangles are actually visible so as you can see if i zoom in there's less rectangles but it takes about 20 milliseconds to work out which ones out of the 1 million available are visible at any one time in fact i can zoom right in and we see that that 20 milliseconds figure doesn't really change and that's because i've got no other alternative other than to test all one million possible rectangles against the viewing area of the screen we start to see this time increase because i'm also timing rather crudely the drawing time as well i probably shouldn't do that but as you will see it doesn't really make a difference when i compare it to a quad tree implementation of the same thing and so in this scene here my linear approach of testing all one million rectangles against the screen displays about three thousand of them in 20 milliseconds if i press the tab key i'm going to use a spatial acceleration structure called a quad tree to give me the same result the same rectangles are discovered but we can see that the time taken to determine which rectangles are visible well it's an order of magnitude faster even better if we zoom in particularly on a region of rectangles we can see that the time taken decreases it's even better i press the tab key again to compare that to the linear it still takes about 20 milliseconds we have to test all one million rectangles against the screen but the quad tree allows us to bypass most of those tests very rapidly there are some limitations to quad trees and that's why this particular mini series is interesting and we'll discuss the pros and cons of how this particular implementation of a quad tree works for example if the search area starts to get very large the quadtree performs about the same as the linear here it's about twice as fast if we keep zooming out so now we're displaying about a hundred thousand objects we can see they're roughly the same so the apparatus of actually implementing the quad tree starts to have an effect well so what javid i hear you crying we've definitely made applications where we've had large expansive worlds filled with things before what's different this time round well firstly our objects in the world are not necessarily tiles and that makes a big difference because we don't know where these tiles are in space we can't calculate the tile in the top left corner and the bottom right corner and draw only the tiles we can see secondly our objects are all different sizes and so some will overlap with the viewing field and some won't and so consider a project where you might have a vast array of space filled with asteroids and spaceships and satellites and planets and space thing on twitch and suddenly being able to quickly determine what is visible on the screen is actually an important thing in the first part of this series we're going to be looking at purely a static quadtree implementation the idea is we can fill the quadtree with information and query it very quickly in the second part we're going to look at dynamic quad trees and i'll just give you a sneaky preview of why that's a different thing and why it's a much more impressive thing ah yes we've reached that time of year again where i get my balls out and start playing with them stop giggling in the previous videos about balls we've had about 100 to 200 balls on display all interacting with each other but now with a dynamic quad tree accelerating space we can have hundreds of thousands of balls balls for everybody as before you might think well okay we've got some rectangles here in the shape of circles and we can determine which circles are visible on the screen well that's one nice thing but we can also have dynamic interactions going on at horribly obscenely large scales and if you follow along on twitter you'll see that i occasionally post little updates of the things i'm building for videos so if you want sort of sneaky previews uh have a look on twitter so you can see this is the standard ball simulation that i've shown in several videos in the past but just now on a huge scale i call it the mega ball simulation being able to rapidly search space allows us to do some quite large simulations and lots of fun things for the future but before we can do that we need to understand the basic implementation of a static quad tree first so let's get started as usual i'm going to be using my olc pixel game engine along with the transformed vue pegx which is becoming something i'm doing in pretty much every video now i'm starting with an empty derived class of the pixel game engine and i've included the transformed view object which i initialized to be the size of the screen and i handle the pan and zoom capabilities that allows me by default to use the middle mouse button to pan and zoom around the world i'm creating quite a high resolution one this time because i'm going to be using the gpu to do most of the drawing after all we're drawing lots of things drawing it pixel by pixel doesn't make much sense regardless of the end result the one thing that we know we're going to be working with is rectangles it is by no coincidence that it's called a quad tree it is fundamentally based on the rectangle the objects stored within the quad tree are rectangular in area and so i'm going to quickly whip up a class called an olc rect and i think this might make its way into the pixel game engine in the future in preparation for that i'm going to create a namespace olc to which i'm going to add a structure called rect and a rect consists of two vectors a pos which is the top left corner of the rect in space and size which are the dimensions of the rectangle i'm also going to add in some convenience functions so we'll give it a default constructor which initializes it to be a rectangle with a unit area and it's quite useful to interact with the rectangles in various ways so i'm going to add a function to see if a rectangle contains a point we've actually done these sort of functions before in my video all about rectangles i'm going to add another function to check if the rectangle wholly contains another rectangle and finally a function to see if this rectangle overlaps another rectangle before i implement the quad tree i want to implement the linear version of our demonstration so i'm going to create an object that stores one million rectangles and displays them on the screen depending on where we are in the world according to the transformed view i'm going to make an assumption that the objects within our world are more than just a rectangle they could be for example an asteroid it could have properties associated with it so i'm going to create a structure called some object with area and this object may have various properties of its own a position the size a velocity maybe and a colour in this instance i could use the rect struct that we've just created but i'm keeping these separate just for clarity to my class i'm going to add a standard vector of my sum object with area struct called vec objects and i'm also going to add a variable called f area and set that to 100 000 this is the size of one side of my world in the on user create function which is called once at the start of the application i'm going to create one million objects i'm simply going to have a for loop create an instance of my sum object with area and what's that object right into the back of the vector i want to randomize the position size and color and rather than fiddling about with the standard random library i'm just going to create a quick little dirty lambda function to give me a random float between two values so now i can initialize the object's position the object's size and the object's color so this loop will add 1 million objects to my vector in on user update i have a utility function to handle the panning and zooming but i need to decide which of my 1 million rectangles is visible at any given time in the highly naive and dumb way i'm about to do this all i can do is iterate through all of the objects in my vector and test them to see if the object's rectangle overlaps with the screen rectangle we can get the screen rectangle by interrogating the transformed view to get the top left visible coordinate of the world and the size of the screen in well world space if the rectangle does indeed overlap with the screen then i'm going to use the fill rect decal function to draw that rectangle of its appropriate position its size and its colour and i'm also going to keep a utility count of how many rectangles were drawn i'm going to crudely measure how long this routine takes to be performed so using a time point from the standard chrono library the rather wordy standard chrono library i'm going to take a time point before and a time point after and calculate the duration now i did mention before that this also includes the drawing uh i'm okay with that because when we compare this to the quad tree implementation later i'm also including the drawing and given that they're going to draw the same number of objects they kind of just disappear in the wash once the loop is finished i'm going to draw to the screen some results i'm going to construct this string that tells me i'm doing a linear search this is the number of objects that have been found this is the number of objects in total and this was the time it took to do it i'm using draw string decal this time and you'll see this is quite a common pattern that i use whenever i've got to draw text on different colored backgrounds i draw a shadowed text just so it always stands out depending on the intensity of the background and that's all there is to this quick demonstration so let's take a look so here we can see the rectangles being drawn i can use my middle mouse button to pan around the world and we can see the time taken to draw those rectangles unsurprisingly as we've got more rectangles in the field of view it's taking more time in this case approximately seven or eight milliseconds to get about ten thousand rectangles out of the space zooming really far in we can see that the actual time is about five milliseconds to do any kind of search at all so it's approximately five milliseconds to iterate through that entire array of one million objects that's different to the 20 milliseconds i showed at the start of the video and i'll explain why a little later because it's quite interesting now before i get stuck into describing how the quad tree works the one lone coder studio lawyers have advised me to issue a disclaimer to satisfy all of the patents out there as with all computer science algorithm type things there are many ways to implement the same result and i make no claim that mine is the fastest swiftest bestest most fantastic implementation of a quad tree that there has ever been in fact i already am aware that there are better implementations than the way i do it but i have chosen to implement my quad tree in a way that explains how quad trees fundamentally work i'm also going to be leaning on templates and some so-called modern c plus which no doubt will only disappoint the most hardcore c-plus plus aficionados out there i'm sorry but life's too short to worry about such things and i actually like to get things done now my quad tree has some specific requirements firstly i want it to operate in the floating point domain secondly i'm going to add some limits to stop my quad tree getting out of control and that will become more apparent when we start describing the quad tree thirdly and we'll look at this towards the end of this video i want my quad tree to look and feel like a normal standard container and finally i want it to be agnostic to the type of thing that it is storing and well obviously i want it to be easy to use and fast too so assuming i have a space and i'm going to also assume that this space is square and i'm illustrating that perfectly with this rectangle as i showed in the code before i've defined some limits to the size of this space with my f area variable which implies this space has some sort of width and some sort of height and typically 0 0 in the top left somewhere in this space exists an object and that object also has an area it has its own width and height and i also assume the object's position is the top left of the object whereas before my vector of objects just stored them all in any order and we had to test them all the quad tree allows me to store them with a degree of spatial information let's examine this crudely i could take my existing vector of all of the objects and decide which objects are on the left hand side of the area and which are on the right that would give me two vectors but if i define my viewing area as this blue rectangle and i check that my blue rectangle is on the left hand side of my space i never ever need to check anything on the right hand side i've halved my search i could half my search again by seeing if i'm in the top or the bottom half this could potentially yield four vectors containing my objects and by seeing that my viewing area is in the top left quadrant of my space i don't even need to check any of the others rather than splitting in halves i might as well just split into quadrants straight away so this gives me four quadrants one two three and four these quadrants give rise to the name quad tree the first level of my quad tree could be the entire space the second level of my quad tree could be these four quadrants and the third level of my quad tree could be taking one of these quadrants and splitting it into four quadrants so let's do that so now i have additional quadrants one two three and four my viewing space covers all four of these quadrants but i can now quickly discount quadrants i can ask my quad tree well does this quadrant contain any objects it can quickly return no i don't well does this quadrant contain any objects it does not does this quadrant contain any objects nope but this quadrant does so now i know that only this bottom left quadrant is relevant i can check this quadrant to see if it's got any quadrants of its own and again i will ask these quadrants do you contain any objects well the first one yes it does but this one's a big no this one's a big no and this one's a big no we've quickly discounted a large region of space with only a handful of checks so far the quad tree allows us to continuously subdivide space in this manner until we get to well the smallest size that we're representing in our world or some other stopping criteria specific to your needs it is effectively a 2d binary search to find the things that we're looking for now things get a bit trickier because we're not working with just a point we're working with an object that has area and as we can see here my green object actually occupies four small quadrants since the object itself is larger than any of the quadrants at that stage in the quad tree then i'm going to say that the object actually belongs to this quadrant here so this quadrant here will maintain a container of its own that contains that object if my object happened to overlap here well then this container contains the object if the object happens to fit in one of the child nodes of this particular stage in the quad tree then that child node contains the object what we see here is lots of recursive behavior and indeed that's how we will implement this quad tree another advantage of the quadtree is it can grow dynamically to hold the number of objects that we're interested in holding i'm going to crudely try and draw some 3d stuff here so here is our top level space and here is an object when we add this object to the quad tree we can determine in this space which quadrant the object lies within well it's only then do we need to create a child node for that quadrant the object still exists in the same location and again we divvy up that child node to work out which quadrant the object exists within and we can keep doing this recursively until we reach the maximum number of layers we're going to allow our tree to be in this crude example here i've limited my quad tree to be four levels deep therefore any objects that end up in this region of space all get put into some container there's no further subdivision than this level here we can start to see this recursive structure whatever this happens to be and i'm actually going to call this one layer a static quad tree it potentially has four children which are also static quad trees and they potentially have four children that are also static quad trees and so insertion and searching for things are also recursive as one quad tree layer can evaluate which of its children it needs to interrogate further let's start coding this and i'm going to be using a template because i don't know what the user's object is going to be in this example it's some object with area but of course it could be whatever you need it to be and i'm going to create a simple template class called static quad tree and the type of the object this quadtree is going to hold is going to be stored in this template argument which is passed when we construct the static quad tree we'll start populating some of the methods in a moment but let's add some of the guts i know that in my world space this particular level or layer of my quad tree has an area i know that it will also have four children well it has the potential to have four children and i'm going to cash the areas of those four children here too so i don't need to calculate those every time so this is just an array of rectangles which subdivide the whole quad tree into four evenly spaced children since i want my quad tree to be able to grow dynamically as we add things to it this is where things get a bit exciting going to create a standard array of shared pointers of the type static quadtree and because static water is a template i need to pass that in two there are of course potentially four children and i'm going to call this mp child so only if we need a child are we going to construct one now if an object inserted into the quad tree doesn't necessarily fit into any of the children then it's got to belong to this quad tree's layer so i need a container to store these objects and for now i'm going to use a standard vector now this is going to change in the future and my vector is going to contain standard pairs because i'm too lazy to construct another type and these pairs are going to consist of our rectangle which defines the area of the object we're storing and the object itself and i'll call this mp items so this variable here is the container which fundamentally holds the things that our quad tree is storing i want to limit the number of layers available in our quad tree because my quad tree exists in floating point space it could potentially go on forever and ever and ever which is no good so i'm going to add another variable which just keeps track of the depth and that's all that the quad tree contains a variable that describes the size of this layer an array of variables that describe the size of the children a second array of variables that describe the children themselves these will be pointers to any child layers that exist and finally a container of the objects stored in this level with this i can now create my constructor and it's a default constructor where i specify the area the size of this layer and by default i'm choosing some numbers it's going to be 0 is the position and 100 by 100 is the size and also the depth at this particular level i'm going to store the depth here and because i want my quad tree to be fairly user-friendly it's possible the user might want to resize it later on so i'm going to create a resize function which will go and calculate things accordingly let's implement this now resizing a quad tree layer of course sets the size of that area however that's quite a destructive thing to the tree so i'm going to make a policy assumption here that if you do resize you invalidate the whole tree which means before we can do any resizing i'm going to actually clear the tree so we'll need to implement a clear function in a moment as well as storing my own area i want to calculate the area of any potential children i might have well that's just my area size divided by two which would give me four areas i can then populate my child area array with the top left quadrant top right quadrant bottom left quadrant and bottom right quadrant this array is purely for convenience so we don't have to calculate this every time we start adding things to work out which child it should exist within so we've added a clear function let's go and implement that clear should demolish the tree and all of its contents so firstly we'll erase the container of items stored in this layer and then for each child we need to clear the child and reset the smart pointer to the child so if the child exists and is active we're to recursively call its clear function which will in turn clear the items and start cleaning up any of that child's children once the child is clear i'm then going to erase the child when working with containers it's often useful to know what the size is hey how many elements are contained within so let's add a size function i start by counting the number of items in this layer's container then i check all four children and if the child exists i recursively call this size function and add that into my running accumulation therefore this layer's size function can return its count now we're ready to start implementing the fun functions this is my insert function it takes a reference to the type of object that we're storing here but it also requires an area that that object occupies within the layer i need to see if the object being inserted will fit into any of the child layers for this layer and in this instance i'm only interested if the object being inserted can exist wholly within one of the child layers so i'm going to use the contains function on the rectangle if the object does exist within that particular child's area i want to make sure that i've not exceeded the maximum number of layers i'm allowing now rather crudely and this is where all the aficionados will start to groan at me i'm just going to store that max depth as a global constant there are more elegant ways to do this i'm sure but for now this will suffice if we haven't reached the maximum depth limit then we need to make sure does the child exist has that shared pointer already been created if it hasn't then i need to create this child so i call make sured on a static quad tree of type object type and pass along the following arguments for the constructor which happen to be the size of that child in space and the depth of that child layer so since we know that the object being inserted does actually exist wholly within a child area and we know that that child area now must exist we can insert it recursively into that child and simply return from the function it may well be that this child will be subdivided into four further children and the appropriate child will be selected for the item's insertion it seems of late that recursion is a bit of a dirty word in programming but i think it's the perfect solution and design pattern for implementations like this it just keeps the code simple and elegant if we get to this return statement then we know that the item must exist somewhere within the tree if we don't then we know that the item didn't fit in any of the child areas therefore the item must exist to this layer we know that the item being inserted must actually fit in this layer because of the recursion we wouldn't have got this far if the item was actually larger than this layer this is a pretty important function so we'll just have a quick recap when we're inserting an item we also specify a size we then go and check all four children to see does the item wholly fit within that child's area if it does we make a couple of checks firstly to make sure we're not exceeding the level of the tree that we're allowing in this case i'm only allowing the tree to be eight layers deep and if the child doesn't exist we go and create it we then recursively insert the items into that child layer if none of that has been possible then the item purely doesn't fit into the child's area so we when we know that the item must belong to this layer now that we have a method of inserting items into the tree we need a way of extracting them when we supply an area now this means that we could potentially be returning a multitude of items i don't know in advance how many items we're going to be returning so i'm going to use a container that doesn't have a large cost if we need to add more items to it in this case it's a list and i'm going to create a function called search to which we specify an area and i want it to return all of the items within that area again i want this to be recursive so this implementation of the search function is actually going to do something a bit different within it i'm going to create my standard list of the objects i'm then going to call a secondary search function which gives in the area and also passes in a reference to this list and finally this function returns the completed list this makes it nice for the user they can just specify a search with an area but the search can go away and recursively do something clever using the same list for each layer this avoids us needing to do things like splicing containers together which in fairness isn't that difficult with lists but if you chose to use something else then it could be quite a costly operation so knowing that we have a second implementation of the search function which takes in the area we're interested in searching for objects and a reference to the list the first stage of the search is to check the items that belong to this layer so i'm going to use a little auto for loop to scroll through my local container of items and i'm going to check if the area was searching for overlaps with those items now my container of items don't forget was a container of pairs the first element of the pair was the area of the item the second element of the pair was the item itself so simply if the two areas overlap i'm going to push that item onto my list of items now some of you may already be raising an eyebrow here and yes you are right and we'll come to that later in this video once we've dealt with this layer's items we need to deal with this layer's children so again we iterate through all four children if the child exists i need to check if the child's items can be added to the list of items now i can make an optimization here too for my rectangles i have my overlaps and my contains functions overlaps just checks is one rectangle overlap another but the contain function checks to see if a rectangle is wholly contained within another if the child's area is wholly contained within the search area then i don't want to do any more checking or anything i just want to dump the child's items into my list of items so this requires a little function which we've not yet created which just returns the items of that child however if the area we are searching overlaps the child's area it's not wholly contained within then i recursively call this search function again for that child searching for things is a bit costly so having an optimization like this will actually save us a significant amount of time this means that my static quadtree layer needs an additional function items and this is no questions asked just simply push the child's items onto the list of items that we provide and since we know that this child's items are all valid the entire child area must be valid we can also push all of this child's children's items too so we can recursively call the items function on the children should they exist no more searching or checking is required we're just returning everything contained within that child and finally one last function just because i forgot to add it before it's useful to actually get the area of this quad tree now i know that that's been a big chunk of code to digest all in one go and as usual the code i've provided on the github will have some comments describing its function i wrongly cap it here but i'd just like to emphasize that we have used recursion to actually save us a lot of effort now that we have our static quad tree defined we can go and test it the fun stuff so let's go and implement one static quad tree we know that the type of the object is some object with area and this time i'm going to call it tree objects i'm going to keep this all the same as before but as well as maintaining the vector of object i'm going to insert into our tree of objects now we've got the item that's easy enough we also need to specify the size of the item unfortunately we've got that up here we can easily construct a rectangle with the position and size elements of the sum object with area structure to make the demonstration interactable i'm just going to add a bit of housekeeping code that allows us to switch between the linear mode or the quadtree mode and i'm going to make that toggleable by pressing the tab key regardless of the mode we still need to capture this screen rectangle but i'm going to throw this in here if we're using quadtree we're going to do that bit or else we're going to do the linear mode and in fact the two are quite similar so i'm going to take this code i'm going to copy it and paste it up here and just change it a little bit so instead of outputting linear we output quadtree now previously we iterated through every object in our vector of objects don't want to do that for the quad tree instead i'm going to call our search function and pass in the our screen rectangle i think this is quite neat because our tree object search function returns a list we can just iterate through the items in that list i no longer need to check if the screen overlaps with the rectangle that's returned because that's what our search function has done right so let's take a look at how the two perform well here i've got my quadtree mode and if i press the tab key i'll see my linear mode oh hmm well it looks like so far the quad tree is well at least twice as slow as linear mode that's not ideal is it look at that that's rubbish what have we done wrong i'm keen to try this in the debugger just to see what our search function is returning well it's returning 127 elements and that kind of feels accurate if we allow it to run yeah that looks about right and if we look at in linear mode well it's 127 there too interestingly in debug mode our quad tree is actually a lot faster than linear mode this is all very bizarre what have i done wrong well it turns out after quite a bit of digging i must confess that i've forgotten a very important line of code i don't actually set the size of the quad tree so i need to call our resize function and specify the area this means that when we were searching before it was defaulting to the 100 by 100 not the 100 000 by 100 000 this would have confused the structure of the tree no end so now we've actually defined the size of the tree properly let's go back into release mode and try this again this feels much better 127 elements have been found and we can see that we are timing things in the micro second domain for these options and we can also quickly look at the frame rate it's a crude metric but it's over a thousand frames per second if without moving the camera i go into linear mode well we see straight away we're now in the millisecond domain we have an order of magnitude performance decrease and the frame rate has gone to about 370 frames per second as we zoom out we can see that the linear mode well as there's more things for it to find let's say about 13 000 here it's taking about 10 milliseconds but the quad tree is taking about seven milliseconds not a huge improvement but don't forget this is also recording the drawing time quad trees excel when they're not working with super dense things because the quad tree itself the apparatus that implements the quad tree is a bit time consuming so if you've got some sort of sparse population like i have now then the quad tree really excels so with that back down to about 0.1 milliseconds here whereas the linear search is about three milliseconds that's quite significant in terms of computing so i'm quite pleased that our very simple static quad tree is outperforming just a simple search through a vector however things are not as rosy as they appear i'm currently treating the tree like a container so let's assume for example i have all of my objects with some sort of physics that need updating for every object at every frame if i stored all of my objects in a vector or a list i can simply iterate through them however in my tree i would have to cast a search rectangle the size of the tree and let it do quite a complicated set of recursive searches to deliver a list of all of the items for me that's going to be very very time consuming not ideal at all and we've also noticed i said some people might have raised their eyebrows we're currently copying things around quite a bit so the the items that are stored per layer in those vectors are being copied into the list that's ultimately delivered with the search results into the tree this means doing transformations and operations on every element in the tree is very very costly but fortunately there's something we can do about it and i'm going to create a very lightweight wrapper for our static quad tree that will solve all of these problems for us when we call the search function on our tree it creates a list that copies all of the objects that's stored within that search area right now those objects are very small they're these simple strokes but they could potentially be quite large things this is not good to have this duplication everywhere i'd also like to have fast access to absolutely everything in the tree going back to our dirty schematic of the tree here recall that the green dot actually is the physical item stored in some container at some layer in the tree what if instead we turn things on its head just a little bit and we have a wrapper and this wrapper contains some other container that contains all of the objects that are inserted into the tree instead of storing the object and its area in the tree we're going to insert objects into this regular container and insert a pointer to this location in the container into the tree along with the area this means that all we're ever storing in the tree are pointers and these are relatively small and lightweight objects they're easy enough to copy and move about but we're also left with a relatively normal container with a begin and an end that we can iterate through all of the objects with no search cost at all this is win-win well almost win-win the only downside is when we do a search into the tree what will return is a list of pointers to objects in this container so operating on those objects has one layer of indirection i'm going to classify that as acceptable because we gain so much in return and don't forget nothing is free in computing to make this wrapper class i'm going to create another template class called static quadtree container again it's going to need the object type passing to it and just to keep things a little bit sane and just adding a bit of syntactic sugar here that fundamentally the container that will store all of the objects in the tree will be a list now that's quite an important distinction to make why have i not chosen a vector well don't forget i'm now going to be adding pointers to objects in this container into the tree now should the contents of this container change in a list those pointers aren't invalidated but in a vector they are so using a vector here runs the risk of me adding something to the tree and then completely messing it up because all of my objects become well invalid this wrapper is going to store this standard list and i can use this quad tree container alias i'm going to call that all items that's where the items are stored the quad tree will now store pointers to items in that container and when we're working with containers we don't really work with pointers we work with iterators so i'm going to use my static quadtree implementation we've just created and instead of passing in the object i'm going to pass in an iterator to the location in the list where we've stored that object i'm going to call that root and now we can add some public facing functions that make this look like a normal container firstly let's add a constructor the constructor is very similar to the static quad tree constructor it takes a size and a depth and simply populates the quad tree with that information we need to pass through quite a number of the functions to the underlying quad tree don't forget we've not inherited here we've wrapped so we had a resize function well we just pass in the area and we call the resize function on the root which is the tree in this instance it's called root because it's the top level of the tree typically containers also have functions for size and whether they're empty or not now instead of recursively calculating the size i know the size is also going to be the same size as the list in this wrapper because there's parity between items in the wrappers list and items within the tree this will be much quicker to calculate than recursively going through the tree and adding up items the same applies for determining whether there are any items in the tree at all if there's no items in the tree there's no items in this wrapper's container the clear function has two jobs to do it has to clear the tree of all the pointers we're storing in it but it also has to clear the list of items these next four functions i'm adding in so we can use this container in a ranged for loop i call them little auto for loops it just allows us to have that sort of nice syntax this leaves us with our big two functions insert which has the same parameters as before will now actually store the item in the wrappers list it just pushes it to the back we can take a pointer to the back of the list which contains that newly inserted item associate that with the area of that item and insert that into the tree the search function is very simple too but instead of returning a list of the items themselves this is now a list of pointers to the items and that's a little distinction that becomes quite important we'll create the list of item pointers here and we'll pass that list of item pointers into the search function of the tree and as before it will go and recursively populate that based on the search area and that's all there is to it we've taken the tree that we created earlier wrapped it up made its functions accessible but this time in the tree we're storing pointers to items within a list and that list is maintained by this wrapper let's go and throw this into our application so this type instead of it being static quad tree it's static quad tree container our search function no longer returns the objects themselves it returns pointers to the objects so now let's run the code well in quad tree mode again we've got very very small numbers we're perhaps in the tens of microseconds now and this is because we're not moving things around well as we compare that to the linear version we're back in milliseconds so perhaps potentially dare i say it almost two orders of magnitude curiously as you can see as i flick between the two different modes some of the rectangles are drawn in a different z order well that's because the tree will return things in a slightly different order to the vector that might be a consideration you need to think about if you're going to store stuff in this haphazard way now i just want to demonstrate one final thing and i'm just going to keep a static screen here so we can see what's going on uh just recall these numbers so for the quad tree we're looking at about 100 microseconds on the startup page and for the linear we're looking at about 1.5 milliseconds we've just created a quadtree wrapper which is storing the items using a standard list and that was necessary because we don't want to invalidate pointers as we're adding things to the list however we're comparing that with a linear search to things stored in a standard vector technically we're comparing apples with oranges here so i thought it might just be quite interesting to have a look at what happens if we change this to a standard list so fundamentally the objects are both stored now as lists let's take a look so here we've got the quad tree implementation as before it's just hovering about 100 microseconds but if i go to the linear implementation we're already up now in the 20 milliseconds by changing from a vector to a list we've significantly affected the performance of the linear behavior and i just thought that this was a nice demonstration of how cache influences your algorithms vectors by design are going to be contiguous in memory that means you access one thing you know the next thing you access will also be next to it in memory and the computer can help you with that however big lists are going to be scattered all over your memory so it takes a bit of time to get those things into the processor and i think this is quite an interesting thing because it means that there isn't a black and white distinction as to what the best construction for your application is at the moment we've got just a static quad tree we can add items to it and we can search it very quickly but it's important to keep in mind the fundamental containers used in this quadtree it may be the case that you know you can get away with using vectors all over the place in which case great use the added advantages of speed that that gives you but the limitations of flexibility in the next part of this series i'm going to be looking at dynamic quad trees where we can change the contents of the quad tree in terms of its location but still maintain some good performance for example here i've got things moving about all over the place different sizes and i can erase them from the tree in fact in this term it's it's a million i've called them bugs but they're actually little flowers but the objects can move around the quad tree and we don't sacrifice too much performance and so there you have it spatial acceleration structures through the medium of quad trees if you've enjoyed this video give me a big thumbs up please have a think about subscribing come and have a chat on the discord all of the source code for this will be on the github very shortly and i'll see you next time take care