Game Basics Understanding Space Partitioning Algorithms: Quadtrees and Octrees, Part 2
Hello, everyone
This is Lee Deuk-woo from Game Algorithms
This is the second lecture on space partitioning algorithms
Quadtrees and Octrees
In this lecture, I will introduce optimization techniques for quadtrees
and their implementation methods
I’ll also cover an overview of octrees, which extend from quadtrees
and their implementation methods
optimization for quadtrees
In the previous lectures,
I explained the basic implementation methods for quadtrees
In a standard quadtree implementation,
as shown here, objects overlapping boundary lines
are not subdivided further
and are instead included in the object list of the corresponding node
Thus, as shown in the diagram
all objects marked in blue
because they overlap boundary lines
regardless of size
are included in the root node’s object list
As discussed in the first lecture
on quadtree querying
the object list in the root node
is always included in the list
of potentially colliding objects
This inevitably increases the search load
To address this
one solution is to record overlapping regions
more precisely
limiting collision detection to relevant areas
and reducing the search load
For example
when performing collision detection in the upper-right region
objects overlapping the left and lower regions
if information exists indicating
that they belong to the left or lower regions
can be excluded from
the collision detection list
This approach reduces the search load slightly
but isn’t a definitive solution, is it?
The technique I’ll introduce today
is the Loose Quadtree
This method was introduced in a classic book
titled Game Programming Gems
published in 2000
It was contributed by someone named Ulrich
The section is titled
"Loose Octrees"
but the technique I’ll explain later pertains to octrees
Since the implementation is nearly identical to that of quadtrees
this technique can also be applied to quadtrees
In this article, the previously mentioned issue
caused by objects located on boundaries
and the resulting complexity in data structure distribution
is referred to as "Sticky Planes"
To address the Sticky Planes problem
temporary solutions include
classifying overlapping information
in greater detail
or passing management of overlapping nodes
to child nodes instead of the parent
However, these methods
make quadtree structures more complex
and serve only as temporary fixes
failing to fully resolve the issue
They can be applied to statically placed objects
but are unsuitable for objects
that move dynamically across regions
They are not fit
This is because, as the rules grow more complex
frequent additions and deletions
occur in lists of varying depths
To address this, Ulrich proposed
loosely increasing the size of quadrants
during subdivision
Let’s take a closer look at this
In the quadtree, as previously explained
the length of each subdivided node’s side
decreases by a factor of 2^depth
based on the depth
Ulrich introduces
a constant k to multiply this value
If k=1, it remains the same as before
so a value greater than 1 must be specified
Here, Ulrich recommends a value of 2
When you multiply by 2
as shown in the diagram on the right
the area managed by each quadrant expands
Under these conditions,
let’s examine how to implement a loose quadtree
When implementing a loose quadtree
unlike a standard quadtree
you first measure the maximum radius of the object to be inserted
Based on this radius,
you determine the appropriate depth for insertion
Thus, regardless of the location
you calculate the depth first
If the object’s radius
is smaller than one-fourth of the side length
you add one more level of depth
If the radius is even smaller,
less than one-eighth of the side length
you further reduce the depth by one level
Each time the radius decreases by half,
you increase the depth
and designate the node for insertion
As mentioned earlier, the side length in a loose quadtree
is calculated by dividing the root node’s side W
by 2^depth
This value was multiplied by k
For example, in a quadtree
where the side length of the root node is 64
if an object with a radius larger than 16 is inserted
since the radius is 16
the diameter of the circle would be 32
If it’s larger than this
it means it won’t fit into a single quadrant
Therefore, it is stored in the root node
However, if the radius is smaller than 16
it will be stored in the first-depth node
If the radius is smaller than 8
it will be stored in the second-depth node
If it’s smaller than 4, it will be stored in the third-depth node
In this way, the depth is incremented
by multiples of 2
to determine which node the object will be stored in
When k=2 in a loose quadtree
the formula for calculating depth is as follows
Here, since
the object’s radius is smaller than one-fourth of the side length
this formula determines the depth for such cases
If we calculate this in reverse
2^depth equals the root node’s side length
divided by the maximum radius,
then divided by 1
Using a log
we can estimate the depth value
Where W
is the root node’s side length
Take the log of W
divided by the maximum radius
and apply the floor function
to convert it to an integer
Once this depth value
is confirmed
you calculate the object’s center
to determine which quadrant
it belongs to
Let’s take a look through a diagram
The first subdivision of the root node
will have a depth of 1
This creates loose quadrants like these
The radius of objects that can fit here
must be smaller than one-fourth of the root node’s side length
Let’s assume such an object is inserted
An object is inserted
and although it overlaps with the boundary
its center is located in the top-left quadrant
Whether or not it overlaps is irrelevant here
What matters is the object’s maximum radius
Let’s assume the radius is smaller than one-fourth
but larger than one-eighth of the side length
In this case, the object
is stored in the first-depth quadrant
The, as shown earlier
since it’s located in the top-left quadrant
it will be placed in the top-left child node
child node of the root node’s four subdivisions
Add the object to the object list
of the top-left child node
Now, let’s look at another example
In this example
the object’s radius is smaller than one-eighth of the root node’s side length
but larger than one-sixteenth
Then this object
will be stored in a second-depth quadrant
Since the object’s center
is in the bottom-right quadrant
add it to the object list
of the bottom-right node
at depth 2
By implementing a loose quadtree
unlike a standard quadtree,
you can obtain consistent data
with uniform depths
based on object sizes
The diagram below, from 2009
compares 10,000 objects
between standard
and loose quadtree implementations
It is comparing the charts
In the left image,
objects with the same radius
were tested
In the right image
objects with varying radii
were tested
The navy-blue bars represent
the standard implementation
discussed in previous lectures
As a result, objects overlapping boundaries
are concentrated in nodes
with higher depths
In contrast, in the loose structure
the depth is assigned based on
the object’s actual radius
resulting in uniformly distributed depths
Similarly, in the second case,
for spheres with varying diameters
a uniform distribution can be observed
According to the study
collision detection operations
with the loose structure
were 40 times faster
However,
since this result applies to specific scenarios
it’s difficult to generalize
that loose quadtrees are always better
Analyzing the current situation
and applying the appropriate solution
is crucial
Now, let’s look at a sample project
to compare the distribution differences
between loose and standard quadtrees
In the Scenes folder, open folder 2
LooseQuadtree
You’ll find the scene named LooseQuadtree Insert
Here, you’ll see four buttons in total
The top button,
Insert All General,
uses the standard quadtree implementation from the previous lecture
to insert
30 different objects
and examine their distribution
To examine the distribution
a Stat button has been added
The button below it, Insert All Loose
uses the loose quadtree implementation
to add 30 objects
Then, by pressing the Stat button
you can check how the 30 objects
are distributed
Let’s test this by running the program
First, using the standard quadtree
let’s place 30 objects
As a result, objects overlapping boundary lines
are added, as you can see
Here, even if the radius is small
if the object overlaps a boundary
it gets added to a higher-depth node
You can see, right?
These are the examples
Looking at these examples
you can see that they’ve been added to the higher depths
Now, let’s rerun it
and try pressing the button below
When using the loose quadtree structure below,
as you can see
even though they overlap the higher nodes
you can see that they’re included
in the lower node’s item list
This applies to other cases as well
As a result, you can see
that small-radius objects,
are not added
to the higher nodes
All items are placed in the lower nodes
In the case of this object, if it were implemented with a standard quadtree
it would have been placed in the root node
But now, you can see it’s placed in this node instead
Now, let’s take a look at
the distribution statistics for each case
Let’s rerun it
press the first button,
and then press the second button
When you press the second button
the related statistics will appear in the Console window
It displays the nodes
As you can see here,
the first root node
which is at depth 0
and the nodes at the first, second, third, fourth, and fifth depths
show objects
distributed evenly across them
Since all the objects are the same size,
this even distribution
as searches require
jumping around nodes,
can actually hinder performance
Now, let’s look at the second case
Using the loose quadtree,
let’s examine the statistics
Looking at the statistics,
the first, second, third, and fourth depths can be ignored,
and you can see that
all the objects are added
to the fifth depth
Next, I’ll explain how the loose quadtree
is implemented by looking at the code
I will explain this
The loose quadtree classes
are prefixed with LQ
Let’s first examine the Quadtree Manager
Open the LooseQuadtree project
and look at the LQuadtreeManager script
The overall code is very similar to what we covered in the previous lecture
However, the way nodes are added
is slightly different
As mentioned earlier,
when implementing a loose quadtree
you first determine the depth information
and then decide on the quadrant information
by comparing it to the center
before adding the object
Thus, there aren’t many changes
to the Quadtree Manager itself
The differences lie mainly in the Insert function
of the LQNode class
On the quadtree
when you call the Insert function
instead of directly running the Insert function,
I’ve modified the code to execute a function called InsertAtDepth
on the root node
This function calls another function, GetTargetDepth,
to determine the added region
and pass the corresponding depth value for the AABB region
as the second parameter
So, let’s take a look at how the GetTargetDepth function
is implemented
First, I retrieve the side length of the root node,
referred to as W
Next, I find the larger value
between the x and y dimensions of the item’s bounding volume
Instead of using the size,
I use the extents
which represent half the side length
I named this variable maxHalfValue
Using this maxHalfValue,
I divide it by the side length of the root node
apply a log, and calculate the result
Then, as mentioned earlier, I round it down to an integer
This gives us the appropriate
targetDepth for the object
If the targetDepth is too large
I cap it
at the maximum depth
The obtained targetDepth value
is passed as the second argument
when adding it to the root node
Here, there’s no need to compare each node individually
You just need to check
whether the current node
matches the targetDepth
You just need to check that
As the depth increases downward
if the current node’s depth
is less than the target depth
you simply divide it
and recursively call the function for the relevant region
This recursion continues
until it reaches the specified child depth
At that point, you just add the object to the appropriate region
In fact, the implementation becomes simpler this way
The remaining functionality is nearly identical
Next, I’ll briefly explain the functionality used
for generating statistics
To generate statistics,
I implemented a function called Stat
I created this Stat function,
This Stat function
is bound to buttons in the Unity project
Each button is linked to this function
Looking at the Stat function,
the second button in the QuadTreeManager is linked to
the Stat function of the standard Quadtree Manager
Meanwhile, the fourth button
is linked to the Stat function of the LooseQuadtree Manager
Since both implementations are identical
I’ll explain using the LooseQuadtree code
I declared a dictionary map structure
where the key is an integer and the value is a list of nodes
This map contains
key-value pair objects
I named it allNodes
On the quadtree root
I call a function named GetAllNodes
to retrieve the list
Here, after retrieving all values,
I concatenate strings based on their depths
Each depth is represented by one line
showing how many nodes exist at that depth
and how many objects are within them
This function generates these statistics
The GetAllNodes function, which retrieves all nodes
is the core logic here
Pressing F12 to navigate to it,
this function also creates a dictionary named allNodes
It then calls a function named CollectAllNodes on the root node
The role of the CollectAllNodes function is to
continuously add itself
and all its child nodes
So, the number of items in each node
is retrieved for all nodes
through recursive calls, and then
strings are concatenated in the manager
to generate statistics
Octree Overview and Implementation
The octree can be considered an extended version of the quadtree
While the quadtree divides a 2D space
the octree extends this concept
to divide a 3D space
To describe 3D space division
the term "octree" was first used by
Donald Meagher in his 1980 paper,
Octree Encoding
Below is a comparison image
of an octree and a quadtree
As you can see, the quadtree
has a square structure
while the octree has a cubic shape
If you’ve understood the quadtree
understanding the octree
won’t be too challenging
The implementation methods are largely the same
The key difference is that the quadtree
uses 2 axes and divides into 4 regions,
while the octree operates in 3D
using 3 axes
and dividing into 8 regions, not 4
These 8 regions here
are divided into upper and lower sections
Think of it as having two quadtrees stacked vertically
which might make it easier to understand
This octree can also
utilize the loose quadtree method
described earlier
Octrees expand the 2D volume
into 3D volume regions
However, using 3D graphics doesn’t always
necessitate using octrees
For example, when creating
a terrain system like the one below
and applying effective spatial partitioning
the height of the terrain
is constrained by the height map
so instead of using octrees,
it’s more common to treat it as a plane
and use quadtrees for division
When building an octree
8 child nodes are used
Having this many child nodes
can significantly increase memory usage
requiring more optimization compared to quadtrees
Octrees can also be used to determine ranges
within a 3D space
They are also utilized for encoding and compressing data
In such cases, the octree manages
points instead of ranges
and these points
in 3D space are referred to as voxels
When managing voxels with an octree
unnecessary regions are omitted and only the detailed regions are stored
using a method that unevenly
compresses data
This is called a Sparse Voxel Octree
This data structure is used in ray tracing algorithms
and for implementing LOD in voxel-based
terrain systems
Now, let’s briefly examine
how quadtrees and octrees can be used
as compression algorithms
As you can see, the original image in the upper-left corner
can be encoded into the lower image using a quadtree
like shown
Through this video, we’ll explore the process directly
As the quadtree divides the image
you can see that identical colors
are assigned to uniform pixel regions
As the image depth increases,
more detailed images are generated
resulting in a closer approximation of the original image
The example shown here
demonstrates 2D image compression
For instance, if there’s a 3D voxel terrain system
a similar method can be used
to build an LOD system
With this, we conclude the explanation of octrees
Next, we’ll look at
how the quadtree source code
was extended to implement octrees in a project
Open the prepared sample project
and navigate to the folder labeled
3_Octree under the Scenes folder
Double-click the Octree Insert scene to open it
Since this expands into 3D space,
you can press the 2D button to see the root node’s area
drawn as a cube
Press the play button
to add the insert items
here one by one
The distribution has been adjusted to spread across the 3D space
and when you press the insert button
the first object is inserted
and as you can see, the 3D space is further divided
to accommodate the overlapping parts
of this node
Next, if you insert another item here
you can see that since it overlaps the boundary,
it follows the standard implementation method
You can see it has been added to the root node
In this way, let’s add a total of 9 items
as game objects
In this case as well, since it overlapped the boundary
it was added either at the first depth
or the root node
It was added at the first depth here,
and you can see it added
at the root node there
Thus, implementation methods
can be expanded further as needed
so it’s not particularly difficult
If you fully understand quadtrees,
implementing octrees should also be straightforward
Let’s first look at how
it was implemented through the project
For the octree solution, open the second project
and open the Octree Manager
to check only the differences
Since it’s a 3D space, of course
the totalArea member variable
was extended using Vector3 to define the cubic area
The other parts don’t differ much
For the rendering part, for the 3D space
the main difference is using Vector3
Even the object that handles the actual octree operations
is nearly the same
So there’s no difference there
The differences lie in the nodes,
specifically in the Onode.cs file
where, as explained earlier,
it is divided into 8 nodes
Thus, enumeration values for the 8 nodes
need to be defined
and their order must be carefully assigned
Top and Bottom
were previously described as two stacked quadtrees
So, there are 4 nodes for the Top
and 4 for the Bottom
The order is the same: TopUpperLeft, UpperRight
LowerRight, LowerLeft
The octree was implemented using this sequence
When implementing the octree
the previously used GetQuads function
was replaced with GetOctants
Here, netZ and pasZ were added
to identify all
8 overlapping regions, as shown
The original function was expanded
Using the GetOctants function,
the lists obtained
indicate full inclusion if there’s only one region
and the function continues to add
recursively to that included region
In the Insert function, recursive additions continue
For the Split function, it should divide into 8 parts
When splitting into 8 parts
follow the previously described enumeration order
to add them to the array
For example, in the case of TopUpperLeft,
since the bounding size is generally positive
you only need to set x to negative to get TopUpperLeft
If the z-value remains unchanged,
it will belong to the top quadtree
so the existing logic can be reused as is
So, change the negative x back to positive,
then modify the y-value
and then modify the x-value again
to complete the top quadtree
Next, we need to move downward
To do this, reverse the y and z values once
to create the area for BottomUpperLeft
We can create this area
Here, follow the same sequence as the top quadtree
to create the bottom quadtree
By adding nodes this way
you can implement the octree
Next, let’s immediately look into
how to perform queries
Double-click the second Octree Query scene in the Scenes folder
to open it
We’ll proceed with the query scene
Here, as you can see,
we have designated three regions in 3D space
These three regions have been prepared in advance
to check how these regions overlap with the 9 objects added earlier
and we’ll use the Query button
Let us check
When you press the play button
all 9 objects
9 objects will be inserted at the start
Here, we’ll check how the region marked in red
which is the first Query region
overlaps
by using the Query button
When you press the Query button
the current region is highlighted in yellow
and the AABB regions of the game objects
inside it are marked in purple
To search within that region,
all possible nodes related to the yellow region
these nodes
are marked in purple, as can be seen
Next, let’s check the second region
When you press the Query button
the overlapping areas are evaluated
and the same structure is created
You can see the third region
being processed similarly
This functionality
was essentially explained earlier with the quadtree
The Query function
is identical to the one in the quadtree
In the case of queries,
it’s exactly the same as in quadtrees
just with an increased number of nodes
Therefore, refer to the second lecture video
where I explained this in detail
and compare it
with the code provided here
to understand how it was implemented
without much difficulty
That concludes this lecture
Thank you for your attention
Thank you
Summary ptimization techniques for quadtrees Implementation method of standard quadtree Objects with same range may be placed in different depth nodes
When multiple objects overlap in a quadrant region, unnecessary searches occur in the root node
Loose quadtree Solves the Sticky Planes problem by expanding area of each subdivided quadrant L depth=k 2depth/W to define loose areas
Using k=2 is standard loose quadtree structure provides uniform depth values 1. Calculate depth based on object size
Depth is determined only if object's radius is smaller than 1/4 of side length For every halving of object’s radius, add one depth level
Once the depth is confirmed, calculate the object's center to determine its quadrant
Overview of Octree Method of extending quadtree to divide 3D space Octree space partitioning method Overall identical to the quadtree
Divides into 8 regions, 2 quadtrees for top and bottom sections Applications of Octree Algorithm For encoding points in space For point data managemen
Ray tracing algorithm LOD implement for voxel-based 3D terrain system Used as compression algorithm For compressing point dat
Compresses image data to pixel data at required depths Uses an octree structure in voxel terrain systems to build an LOD system