One of our individual requirements for studio 2 is being able to design and implement a spatial partitioning system.

   

What we were given:

//update this at uni tomorrow errors with my home visual studio

 

Updated Process:

We broke down together in class the essential design of a quadtree spatial partitioning system and what we needed it to achieve in our context.

We would start by creating a node class:
Node Class
– Bounding Box (AABBf)
– Layer/level/depth
– Parent pointer
– Children
– Contents

Functions for the node:
– Add a relevant object
– Find potentially relevant tiles

Process for creating:
– Create the root node
– Add all of the relevant objects to the root node
– Inside “Add a relevant object” on the node:
– If we already have children:
– Find the children that the object overlaps
– Call “Add a relevant object” on those children
– Otherwise:
– Add the relevant object to our contents
– If number of objects being tracked over threshold AND our size is > some threshold
– Split
– Create the children (and track them)
– Distribute all relevant objects to the children

Process for using:
– Inputs
– Location
– Output
– List of potentially relevant tiles
– What it actually does?
– Runs “Find potentially relevant tiles” on the root node
– If we have no children
– Return the contents
– If we have children
– Find which one the point is in
– Run “Find potential relevant tiles” on that child and return the result

Implementation:

First things first, creating variables and a constructor for the node in the header

Define Constructor / destructor in the cpp file

Create AddRelevantTile function:

We check first if the tiles field Strength is zero and if it is ignore it (as the data isnt relevant)

If the node has children, check to see if the tiles bounding box intersects with the current child pointer, if it does add that relevant tile to the current child pointer.

If the node doesn’t have children, check to see if the contents is greater than the bounding box size, if it is split and define the areas into quadrants.
Each quadrant becomes a child node of that node.
Now for each child we check the contents, if the two intersect then we add that relevant tile to the current child pointer.

Create FindRelevantTile function:

for each child, check to see if its bounding box contains the location, if it does return that location to the child pointer

Results:

Our updated process finishes in 0.027967 seconds, which is a significant improvement from the old methods 17.361025 seconds.