Game Basics Understanding Spatial Partitioning Algorithms: KD-Tree and BSP-Tree
Hello, everyone
This is Lee Deug-woo with Game Algorithms
In this lecture, we will cover something that is used for spatial partitioning in games
called the KD-Tree and BSP-Tree algorithms
The lecture on Spatial Partitioning Algorithms:
KD-Tree and BSP-Tree
is divided into three parts
First, I will explain the overview
and working principles of KD-Trees
Next, using a practical example project
I will introduce how to implement KD-Trees
Finally, I will explain the overview
and working principles of BSP-Trees
Overview and Working Principles of KD-Tree
The KD-Tree
first devised by Jon Bentley in 1975
is a spatial partitioning method
If you look at the title of the paper, it says
Multidimensional
Binary Search Trees
The term "multidimensional binary tree" is mentioned
used for
associative searching
and it is described as being used for associative searching
So, interpreting this title
it explains a method for constructing multidimensional binary trees
for associative searching
In this paper, the term "KD-Tree"
was introduced for the first time, referring to a K-dimensional tree
To summarize the paper: as seen in the illustration on the left below
we have a set of 2-dimensional point data scattered like this
In reality, this method can be applied to data in all dimensions
but 2D is used for simplicity
in the illustration
If we take these points
and arrange them as shown in the illustration on the right
in a tree structure
we can perform searches more efficiently
Just as we typically use binary trees
to effectively search for numerical data in 2D
the same logic applies here
To achieve this, however
we need what’s represented on the right
called a discriminator
This needs to be set
Here, you can see discriminators such as 0, 1, 0, 1,
set according to the depth
of the node
Let me explain how this is configured
and the method for building a KD-Tree
I will now explain
The rules for generating a KD-Tree are as follows
First, every node
stores K-dimensional data
Whether it’s 2D, 3D, or 4D
All types of data can be stored
Next, every non-leaf node
Except for leaf nodes,
divides the space into two parts
It uses its own data to do so
It splits the space into two parts
Nodes that divide the space
use specified dimensions
to partition the space
This is the rule that is defined
This specified dimension
is the Discriminator
as I mentioned earlier
Typically, it depends on the depth of the node
proceeding in the order of x, y, z, x
Earlier, it was specified as 0, 1, 0, 1,
which actually represents the sequence of dimensions
So, x is 0,
y is 1, and z is 2
If it’s in 2D
it proceeds in the order of x, y, x, y
So, the node will have 0, 1, 0, 1
as the dimension values
Nodes that partition space
use standard bases
The x-axis, y-axis, and z-axis are mutually orthogonal
and these standard bases are utilized
Once the nodes are configured
with K-dimensional data and their respective dimensions
they use this to partition the space
Using the dimension value set on the node
they partition the space using the node’s dimension value
For example, if a node contains
2D data such as (70, 30)
and the x-axis is specified
it uses the x-axis value of 70
to divide the node’s area
into two parts
So, this value of 70
becomes the basis for the dimensional data of the node
The left child node is assigned lower values,
and the right child node is assigned higher values
This is how it’s designed
When the area is divided using 70 as the criterion
points smaller than 70
are moved to the left child node
Points greater than 70
are moved to the right child node
Then, in the next depth node
The dimension is incremented by one step
Once all dimensions
have been used, it loops back
to the first dimension
starting again with x
For example, if the depth is 0
it means it refers to the first dimension
which corresponds to the x-axis
If the depth is 1, it corresponds to the y-axis
If the depth is 2, it corresponds to the z-axis
If the depth is 3, it cycles back to x
However, it’s not explicitly labeled as x, y, z
but rather assigned using index values 0, 1, and 2
These indices are used for assignment
Therefore, if we know the depth of a node
the dimension associated with that node
can be determined by performing a modulo operation
on the depth to get the dimension index
This is how the dimension is assigned
Now, using actual data
let’s see how to construct a KD-tree
using an example
First, we define an area from (0, 0)
to (100, 100)
which is arbitrarily defined
Let’s assume there are five points within this area
This area, in fact
doesn’t need to be explicitly defined
but to visualize the process
it is set like this
Using the five points within this area
we will construct a 2D KD-tree
Let’s see how to do it
The point data will be arranged
in the following order
First, insert (60, 40) as the first point
Second, (30, 60)
Third, (90, 80)
Fourth, (40, 10)
Finally, (50, 30)
We will construct a KD-tree using these points
When using (60, 40) as the first point
since it’s the first point,
it is assigned as the root node
It is designated as the root node
Since it’s both the root and a leaf node
no spatial division occurs initially
When the next data is inserted
a child node is created
and the division occurs along the x-axis
and spatial division is performed
Using (30, 60) as the second point
when (30, 60) is inserted
first, the x-axis
of the first root node
is used as the basis for division
So, for the root node (60, 40)
we only need to consider the x-value of 60
Comparing 60 with the x-value of (30, 60)
we don’t need to look at the y-value
only at the x-value 30
Comparing 30 and 60
since 30 is smaller than 60
as previously explained
it is inserted into the left child node
according to the rules
So, (30, 60) is inserted as the left child node
Here as well, (30, 60),
being a leaf node
does not cause further spatial division initially
If additional data is inserted
the space is divided using the discriminator
In other words, the division key
which in this case is the y-axis
Because previously, the first
root node at depth 0
uses the x-axis
The next depth node
should divide based on the y-axis
Let’s move on to the next step
Let’s examine the case where the third data point, (90, 80)
is inserted
When the third data point is inserted
the process starts at the root node
to perform a comparison
The root node’s dimension is
set to the x-axis
Therefore, we only compare the x-value 60
with the x-value of the third data point, 90
Only these two values are compared
Since 90 is greater than 60
by the rule, it is inserted
into the right child node of the root
The right child node was empty, correct?
So, it is inserted into the right child node
and this completes the step
This way, the tree is balanced
The tree is constructed in a balanced manner
Similarly, since it is a leaf node,
spatial division has not yet occurred
If data is inserted later, this space
will be divided based on the y-axis
This is how it works
Let’s add the next data point
Let’s add the fourth data point
We use (40, 10) as the fourth data point
At this point, the search starts from the root
We said the root node only considers the x-value
Thus, comparing 60 and 40
we only need to compare these two values
Since 40 is smaller than 60
it proceeds to the left child node
However, at this point
data already exists in the node
So, another comparison
needs to be performed
At this point, the discriminator,
or the axis value
has changed to a different dimension
It is now designated as the y-axis
So, instead of comparing the x-value 30,
we compare the y-value 60
The y-coordinate of the fourth data point, 10,
is smaller than 60
Thus, it proceeds to the left node
Since data is inserted
(30, 60) divides the space into two parts
This division occurs
perpendicular to the y-axis,
based on the x-axis
The space is divided accordingly
So, (40, 10) occupies the lower section
When viewed along the y-axis,
this is the region of the right node
while the left node occupies the other region
Currently,
(40, 10) is located in the left node
Through the modulo operation
the x-axis is reassigned
If data is inserted at this point
it will follow the same rules
and divide again based on the x-axis
The space will be divided into left and right
This division will be performed
Let’s add the next data point
Next, we added the fifth data point, (50, 30)
Starting at the root
since 50 is smaller than 60
it proceeds to the left child node
Then, considering only the y-value
since 30 is smaller than 60
it moves further left
However, since there is already a node on the left
we compare the x-values again
Since 50 is greater than 40
it is inserted into the right child node of (40, 10)
It is placed there
The process continues using the same rules
Since the depth has increased by one
for (50, 30)
the y-value 30 is used as the basis
to divide the space vertically
The final result of the constructed KD-tree
is shown in the next diagram
To make it easier to indicate distinctions
if the x-axis is set
the space is divided along the y-axis
and if the y-axis is set
the space is divided along the x-axis
This way, you can observe the results of the division
Based on the KD-tree constructed in this manner,
constructed in this manner,
you can perform searches
So, how do you utilize the KD-tree that’s been built
Let’s explore how to search in this tree
and the ways it can be applied
We will examine this now
First, the KD-tree is used
primarily for two purposes
First, for any given point
when a point is provided
it is used to find the closest
point to that given point
This is known as a "Nearest Neighbor Query"
Second, it is used
to find all points
that fall within a given range
It is used widely for this
This is often called a "Range Query"
As mentioned earlier,
instead of checking the entire dataset
the algorithm identifies regions
that don’t need to be searched
and excludes them from the query
If we want to find the nearest point
scanning everything
even though there are only 5 data points here
would become inefficient if there were, say, 100,000 points
The amount of searching would increase significantly
By using the tree
you can exclude unnecessary regions
and perform searches more efficiently
This is one of the advantages of the KD-tree
Now, let’s look at how
to find the closest point to a given point
Let’s examine this process
We already have the tree constructed
From this constructed tree
when a point (80, 90) is provided
how do we find the point closest
to (80, 90)
Let’s take a look
To find the nearest node
you start at the root node
and perform a depth-first search
For each node,
the steps to be performed are quite clear
First, measure the distance
between the node’s data and the given point
Checking whether it is the closest
should be determined, right?
The next thing that should be done is
measure the shortest distance between
the given point and the dividing line
created by the node’s designated dimension
This line divides the space into two regions
Measure the shortest distance
to this dividing line
This distance is measured
You measure these two things
If the distance to the current node
is the shortest so far,
that node becomes the nearest node
At least for now
Next, based on the specified dimension
perform comparisons
It’s the same as before
If the value is smaller, continue searching
the left node first
If it’s greater or equal
search the right node first
For example, if the given point is (10, 50),
and the current node’s value is
set to (30, 50)
and the node has a first dimension value
of 0
in this case,
you first calculate the distance between (10, 50) and (30, 50)
then measure this distance
Next, measure the distance from (10, 50)
to the dividing line at 30, which is 20
So, you measure 20
You measure these two distances
Then, according to the rule
since the given point is smaller than the first dimension value
you prioritize searching the left node
So, you search the left node first
After coming back and rechecking
if the shortest distance found so far
is shorter than the distance to the dividing line
you do not proceed with the search
You skip searching the right node
For example, in the previous case
if the shortest distance found by searching the left node
is 15, let’s assume this
However, since this is shorter than the shortest distance to the dividing line,
which is 20,
the region on the right side of the dividing line
is always farther than the shortest distance
This conclusion can be drawn
Therefore, the right node region
can be excluded from the search
Let’s explain this with an illustration
I will explain it to you step by step
Suppose we have a given point, (80, 90)
Using the KD-tree that has been built,
we will try to find the closest point
using this algorithm
Let’s run the algorithm
When we first input (80, 90)
we first compare it with the root node
The distance between (80, 90) and (60, 40)
should first be calculated
Next, from (80, 90)
the distance to the dividing line of (60, 40),
which has an x-value of 60, is measured
As shown in the diagram
since the x-value is 80
the shortest distance is 20
It becomes 20
but this is, of course
greater than the distance from the root node
Therefore, the current closest node
is initially set as the root node
upon entering
but first, we must perform a depth-first search
on the left region
According to the rule
since 80 is greater than 60,
we should search the right node
So, we proceed to the right node
and as we enter
we measure the distance between the given point (80, 90)
and the second node, (90, 80)
This distance is calculated
At this point, the distance to the root node
is longer than the distance to (90, 80)
so we determine that (90, 80)
has the shortest distance
Since there are no child nodes
we terminate the search here
and return to the root node
Now, upon returning to the root node
we must decide whether or not
to search the left node
The result of the right node search
is compared against 20
This determines the next step
Since the distance to (90, 80)
is smaller than 20
it shows that the right node region
does not need further exploration
So we can conclude that the closest point
is (90, 80)
The algorithm can now terminate
In summary,
only 2 nodes were visited in total
Instead of traversing all 5 nodes
only 2 were visited
to find the closest point
The closest point was identified as (90, 80),
which we were able to confirm
Thus, by using the KD-tree
we learned how to find the
closest point
Next, let’s look at an algorithm
to find nodes within a given range
This has been summarized
As with the previous algorithm
a depth-first search starting from the root node
is performed
A range essentially refers to
an AABB (Axis-Aligned Bounding Box)
The given AABB range
is checked for overlap with the node’s region
While performing overlap checks
the algorithm proceeds
If the given range
and the node’s AABB region
do not overlap, that region can be excluded from the search
However, if they overlap
then points within the node
are checked for containment
within the given range A
Points meeting this criterion
are added to the list of results
The node’s points are added to this list
If overlapping nodes continue to appear
the depth-first search continues
checking overlaps and containment
between regions and points
This creates a list of points to be returned
This allows you to find
points within the range
Let’s go through an example
Suppose we have a given range like this
First, we compare it with the root node’s region
We begin by performing this comparison
The root node’s region
represents the entire area
Naturally, it overlaps with the given range
Since they overlap
we need to check whether this region includes the point (60, 40)
This check is performed first
The point in the root node
is not currently within the given range
so we pass the operation to its children
The responsibility is handed over to the child nodes
Looking at the child nodes, the left region
overlaps with the given range
whereas the right region
is entirely separate from the given range
Thus, there’s no need to search the right region
We can exclude the right region from the search
So we only search the left region
Let’s proceed to
the second left region
Since it overlaps with the left region
we check whether the node point (30, 60) in this region
is within the given range
This inclusion check is performed
Since it is included, this point
is added to
our list of results
Next, as in previous steps
this is divided into two regions
The upper region
has no child nodes
so no operations are performed here
There’s no need to perform comparisons
Only the lower region
needs to be checked
The region defined by (40, 10)
is this region here
Since it overlaps with the given range
we descend further
When we descend again
we check whether (40, 10)
overlaps with the given range
We determine if they overlap
Since they do not overlap
no operations are performed
Next,
we divide into left and right regions
We divide and compare
Here, it overlaps with the left region
but not with the right region
So, we only search the left region
and bring it down
Since the left region has no nodes,
the search ends here
Thus, all search operations
conclude at this point
So if we organize the results
the total number of nodes visited
was only 3
These two nodes
did not actually need to be visited
Among the three nodes
the only point within the range
was (30, 60)
This was the conclusion
KD-Tree Implementation Method
Extract the provided sample project files
and run Unity
to open the project
The Unity version used for this project
was 201.3.
The project is structured as follows
It supports both 2D and 3D data
These two types of data
have been set up for use
First, let’s look at how 2D data is used
to implement the KD-tree
Let's take a look
Scene 1 includes an insertion scene for building the KD-tree
and a query scene for finding the nearest point
These two parts make up the scene
Let’s open the insertion scene first
and discuss its implementation
The overall structure of the scene
is very similar to the examples provided in
Understanding Spatial Division Algorithms 1
A manager game object has been created
to manage the KD-tree
A component called "KDTree Manager"
has been attached to it
The KDTree Manager component
sets the overall map size for visualizing the KD-tree
It defines the total map size
in this way
Since this is a 2D setup
the dimension value is set to 2
Within this KDTree Manager component
there are 9 objects
positioned as child objects
From 1 to 9,
let’s examine the positions one by one
These game objects
each have a tag called "Insert" assigned to them
Using this tag,
the script identifies objects to insert
in the designated order
Now, let’s press the play button
In the game view on the right
clicking the insert button
creates a KD-tree node to store the point
and proceeds with spatial partitioning
When we press the button to check
the spatial partitioning begins
Since the first point is assigned the x-axis
the y-axis, which is orthogonal to the x-axis
is used to divide the space into two regions
In the second node,
the depth increases by one level
so at this point,
the y-value is used again
and the x-axis, orthogonal to the y-axis,
is used for spatial partitioning
As we continue to insert points one by one,
the depth at which these points are located
determines whether the axis
is set to x or y
Based on the assigned axis
it decides whether to partition along the x-axis
or the y-axis
As shown here, one by one
the spatial partitioning is carried out
Now, let’s take a look at the code
This code is located under the "Scripts" folder
in a folder named "Kdtree"
The scripts related to this KD-tree
include KdtreeManager, Kdtree,
and the node used in the KD-tree
KNode, a total of three
C# scripts
Let’s first examine the KdtreeManager script
and check it out
The KdtreeManager script
is designed to manage the KD-tree in Unity
and is a custom-written C# script
It functions as a Unity component
by inheriting the MonoBehaviour class
This script itself
does not perform the actual KD-tree operations
Instead, it interacts with Unity
to handle input values
and communicates with the KDTree class,
which performs the actual KD-tree tasks
That is its primary role
Let’s examine the member variables
of the KDTreeManager
First, a member variable named dimension
was declared to define the dimensions of the KD-tree
This variable allows us to specify
the number of dimensions the KD-tree will use
It was designed with this purpose in mind
Next, I’ll demonstrate two functionalities
two functionalities
the process of inserting objects
to build the KD-tree,
as shown in the "Insert Scenes,"
and the process of finding
the nearest point in the built KD-tree, called "Query Scenes"
These two functionalities will be demonstrated
Since these need to be displayed differently
I declared a separate enumerator
called KDrawMode
This allows for distinct visual modes
Next, to visualize the entire space
I set up a bounding volume
called drawArea
This volume represents the overall area
Additionally, a member variable for the actual
KD-tree operations was also declared
Next, to manage
the insertion process
an array of game objects
tagged with "Insert"
to track the inserted objects
was declared
When inserting objects step by step,
the index of the currently inserted object
is stored in
a member variable called iIndex
This iIndex variable was added
The remaining variables below
will be used in the query scene later,
so I will explain them at that time
Next, let’s look at the Awake function
We will review it
When the play button is pressed
the Awake function will be executed
At this point, a KD-tree object
is created
and the specified dimension value
is passed as a constructor argument
If it already exists
it deletes all related data
This is explicitly set in the process
Next, it searches for tags
to find the objects required
for building the KD-tree
using the FindGameObjectsWithTag
API to retrieve them as an array
Storing these objects
completes the initialization process
For the actual operations
it uses the current insertion index
and the Transform component
that holds the position value
The reference to the Transform component
is passed as an argument
to the Add function of the tree object
to perform the insertion
The NearestQuery function below
is used during the query process
so I will explain it later
Next, the drawing process
in the OnDrawGizmos function
renders all node regions of the KD-tree
in gray
This is how the drawing regions are specified
This represents the entire area
Next, to show how the KD-tree
is partitioned
the KD-tree object
starts from the root node
drawing each divided line or plane
The DrawSplitPlane function
is called to handle the rendering
For the Insert mode,
it draws the area of the point to be inserted
using the DrawCube function
The sections below are related to queries,
so I will explain them later
I will cover this later
Next,
let’s examine the actual KD-tree construction
and the KD-tree class
I will explain this
For the KD-tree
a list variable was declared
to store nodes
in a List format
To check the dimensions currently used
by the KD-tree
a variable called Dimension was added
This takes the value declared in the manager
via the constructor
Additionally, the root object was specified
to enable searching from the root node
It was assigned as a member variable in the KD-tree
Now let’s examine the key function
the Add function
As mentioned earlier, in KDTreeManager
when performing Add
the location value of a game object
stored in the Transform component
is passed as a reference
When the reference of a Transform is received
a new node is created
based on the reference
The binary tree is then built according to the rules
If the root is null
a new root node is created
and added to the root node’s list
It is immediately returned
If the root is not null
a suitable insertion position must be found
The dimension value assigned to the node
determines whether the newly inserted
Transform value goes to the left node
or the right node
To determine this,
the comparison logic in the if clause
uses the GetkdValue function
This function takes the depth of the node
and the dimension value as arguments
For convenience
C#’s extension method feature
was used to implement this function
Before looking at the code
the value being compared
is not the entire dimension value
but the dimension value assigned to the node
This is determined based on the depth
of the node, as explained earlier
The total number of dimensions
handled by the current KD-tree
is stored in the Dimension member variable
as can be seen
The depth of the node to compare
is given as the depth value
Initially, this depth value
starts at the root node,
so it is 0
Every time the while loop runs
the depth increases by one
In any case, with the depth value
and the Dimension value
we can determine
which dimension value to use
from the Transform position
As explained earlier,
this value can be calculated
using the modulo operation
Let’s scroll up to see
the implemented extension method
In the GetkdValue function
when the Transform, dimension, and depth values
are provided
the current position value of the Transform
is calculated by determining
which indexed dimension value
is derived by using the depth
and the modulo operation
to get the index
This index is then applied
to retrieve the value using array indexing
Returning to the earlier code
the dimension value retrieved
for the current depth of the Transform
is then compared with
the dimension value of the node
in the same manner
Here, the property kdValue
is designed to retrieve it
If you press F12
you can check the implementation
The Transform assigned to the current node
the total dimension values
and the depth value of the current node
these three are used
to calculate the dimension value to retrieve
It returns this value
Press Ctrl+- to return to the original view
The two dimension values obtained in this way
are compared
If the value is smaller and the left node is available
it is added to the left node
If a node already exists in the left
you go in another level
and the process repeats
If the same value is encountered
nodes with identical values
cannot be added
An error is returned in such cases
The same logic applies to the right node
If the right node is available,
the node is added to the right
If there are children in the right node
the depth is incremented
and the loop continues
The loop iterates accordingly
This covers the addition logic
Next, let’s look at the class
that constructs the KD-tree: KNode
The KNode class, upon declaration
contains a reference
to store its position via a Transform
It also contains the depth value
the depth of the current node
and the total dimension value
This value is set for the KD-tree
There is also a reference to the parent,
although it’s not used practically
I added it for potential use
Next are references
to the left and right child nodes
These are included in the design
The drawing-related part
will be explained later
At the very bottom
the most crucial part previously explained
is how the kdValue is retrieved
This was explained
Going further up,
there are references for the left node
the right node
and checks for whether the left
or right nodes are empty
These are properties
declared for such evaluations
Internally, there isn't any special logic implemented
What you need to note here is
that using the depth and dimension values
the AABB areas of the left and right nodes
are drawn
through a function called DrawSplitPlane
I implemented this function
This is recursively set up so that
if there is a left child, depth-first
drawing is continuously performed
For nodes set as right children
the areas of all such nodes are also drawn
in this implementation
By adding objects one by one
I explained how the KD-tree
is constructed and
the code for drawing each divided area
was also explained
Next, let’s look into how to find
the nearest node
using the query feature
Returning to the Unity project
this time, let's open the Query Scenes
and give it a command
In the Query Scenes,
the setup is slightly different
There are 9 objects to be inserted
along with
3 objects that determine the nearest points
These were specified accordingly
Press the play button
to see it in action
When the play button is pressed
all 9 objects
are inserted
and the KD-tree is already complete
At this point, for the first object,
it is marked in red
The nearest object
is actually this point
We can verify this
While this is easy to see visually
if there is a large amount of data
or a situation where visuals are unavailable
it would be difficult to identify
So by pressing the button
you can confirm whether it correctly finds
the nearest object
We can see that it is able to correctly find it
For the second object,
the nearest object should be this one
Press the button to check
For the third case as well, pressing the button
shows that it is correctly found
Additionally,
what you should confirm is
how many nodes in the tree
were traversed during the search
If the KD-tree wasn’t used
all 9 objects
would have to be compared
However, by using the constructed KD-tree
the search process
for the first case
let’s run it again
for the first case
Only 4 nodes were traversed
to find the nearest object
For the second case, 5 nodes
For the third case, 7 nodes were traversed
to find the nearest object
Now let’s look at how the query feature
was implemented through the code
In KDTreeManager
I will explain only the parts related to the query functionality
During the initialization of KDTreeManager
in the Awake function,
if it is set to Query
it calls InsertAll
to add all objects
You can see this being called
To find the nearest object
the NearestQuery function
of the KD-tree object
is invoked
When calling NearestQuery
a list object called searchedNodes
is passed
to keep track of how many nodes
were traversed in the current tree structure
This allows us to check
by passing a reference parameter
The number of traversed nodes
is counted
through additional functionality
In the OnDrawGizmo function,
the tree area drawing
is performed similarly to the insertion feature
Query objects are drawn in red
and already queried objects
are drawn in yellow
Additionally, queried objects
and their nearest objects
are marked in purple
A line between the queried object
and its nearest object is also drawn
Now, let's take a look at
the NearestQuery function of the KD-tree,
to see how it is implemented
Press the F12 key to inspect it
In the case of the NearestQuery function,
it doesn’t do much directly here
The KD-tree itself doesn’t handle it here
Instead, it recursively calls the
CheckNearestNode function
on the root node,
using depth-first search
to find the nearest node
This is how the logic is designed
Similarly here,
we can press F12
to see how it’s implemented
This function takes the following inputs
a testTransform parameter for the point to compare
the currently
closest node identified so far
and information about the nearest node
to pass as an argument
Additionally,
to track the traversed nodes,
a list reference
created in the previous manager class
is passed as the third argument
Upon visiting a node
this list reference
is used to store
information about the current node
at the beginning of the function
Then, the currently known shortest distance
from the second argument
is measured
to determine
and compared with the distance to the current node
This determines which node is closer
If the current node being visited
is closer,
it becomes
the nearest node so far
If the current node is
a leaf node at the very end
no further search is necessary
The current node is returned
as the nearest node
Otherwise,
the search continues
There might be a closer node
in the child nodes
so a variable named NearestNodeSofar
is used to store
the information about the closest node
found so far, including the current node
Next,
a depth-first search is performed
Before that, it’s useful to calculate
the shortest distance to the non-overlapping region
either the left or right region
This distance
should be calculated in advance
To achieve this
the dimension value set in the current node
is measured to calculate the shortest distance
For example, if it’s on the right
it’s the shortest distance to the left region
If it’s on the left,
it’s the shortest distance to the right region
To compare these,
the distance is intentionally squared
This is because, when calculating the distance
we use a function called SquareDistanceTo
The reason for using this function
can be seen by pressing F12
It subtracts the position
of the node to compare
from the target position
to create a vector and uses the squared magnitude
As noted in the comments,
for performance optimization
a square root is intentionally not applied
Since comparisons are made with these values
distances are squared intentionally
The squared distance is calculated
and used in subsequent logic
Similar to the previous logic
the dimension value set in the current node
is compared; if smaller, it moves left
and if larger, it moves right
If it goes left first
it continues depth-first search
The CheckNearestNode function is
recursively called
to find the nearest node
from the left node
The distance to the nearest node
is then retrieved
This becomes the shortest distance within the region I'm located in
Within the area containing the point
I am comparing
However, there could be a shorter distance
in the right-hand region as well
Therefore, to account for that possibility
we also need to perform a depth-first traversal
on the right-hand side
If the currently measured shortest distance
is greater than the shortest distance to the opposite region
Which would be the right-hand side
If the shortest distance to the right-hand side is shorter
It is possible that a closer node
exists on the right
In such cases, the right child must also be
recursively explored
If the shortest distance to the right-hand region
is greater than the current shortest distance measured
the right side does not need to be searched
You can skip it
Similarly, for the right-hand side
proceed in the same manner
Recursively search through the right node
and measure the shortest distance
If the shortest distance to the left-hand region
is shorter than the shortest distance
I have currently measured
there is a possibility of a closer point on the left-hand side
Because there is such a possibility
the left side should also be
recursively explored as well
The KD-tree uses this logic
to identify the closest point
When executed, in some cases,
it traverses very few nodes to find the closest point
While in other cases
it may operate inefficiently
Traversing nearly all nodes
to find the closest node
Next,
using 3D data
we’ll examine how the KD-tree has been constructed
by viewing the screen
Under the Scenes folder,
go to the folder labeled K3dtree
After you run
the K3dtreeInsert Sceness file
disable the 2D option
and switch to the 3D option
In this state, press the play button
Inside the KDTreeManager
there is 3D spatial data
containing a total of 9 entries
As we add them one by one
the volume in this 3D space
we can observe how it is partitioned
As you can see, using nearly identical principles
the 3D space is divided into two sections
through a single plane
You can confirm this
The KDTreeManager component currently used
in Scenes
is the same as the one used for
2D data
Except that the Dimension value
has been changed from 2 to 3
Thus, if we
properly implement the KD-tree
we will be able to construct a KD tree
that operates universally in N-dimensional spaces
Next, let’s examine the second prepared Query Scenes
Let's take a look
Likewise, pressing the play button
will add all objects with the Insert tag
to the KD-tree
All of them will be added
Here, three pre-prepared points
for each of the points
looking for the closest nodes
When we execute the logic
we can confirm that in 3D space as well
it operates correctly
The Overview and Functionality of BSP Trees
Let’s first review the overview of BSP trees
The term BSP stands for Binary Space Partitioning
Binary Space Partitioning
It’s an abbreviation
It involves dividing a given space into two parts
and storing it in a tree structure
as a binary tree, right?
Storing it in a binary tree structure
to perform effective searches
It is a collective term for this technique
This method became famous
during the development of the classic game Doom
As shown on the left side here
when rendering a specific level
there was a significant slowdown problem
At that time, developers used BSP trees
to resolve the slowdown issue
and render levels effectively
After Doom, it was widely used
in the development of various games
The BSP tree can be utilized in various ways
As shown here
it can divide a 3D space level
by removing hidden surfaces
also known as hidden surfaces
By detecting the parts where hidden surfaces are removed
it is used to render effectively
Alternatively, in a 3D space
it is used for detecting collisions of half-lines
that is, by pre-exploring movement paths
to check if the character and a wall
will collide or not
This logic is also implemented using BSP trees
Furthermore, the BSP tree
can divide given terrain data
to create specific volume shapes
This is another application of BSP trees
To construct such a BSP tree
a plane must be defined
to divide the space into two
When this plane is defined,
the space is split
into two regions by the plane
The given terrain
is divided into the front and back parts
If any object spans the plane, it is split into two parts
This results in the space being split into two regions
These separated spaces are recursively
split further,
forming a binary tree
This is how it is designed
While forming the binary tree
if the following conditions are met
the process is designed to stop
If the number of polygons in the smallest node
is less than a specified value
or, depending on the situation
various other conditions can be applied
If the shape contained in the smallest node is convex
meaning it has no overlapping visibility
the splitting can be stopped here
If the depth of the constructed tree
reaches the specified maximum value
the process can also stop
Alternatively, if a suitable plane
to split the space cannot be found
the process can be stopped
The methods for constructing such BSP trees
are highly complex and varied
making it difficult to explain simply
However, as you can see here
when a rectangular space is given
a plane is defined
and this plane is set up
to divide the space into positive and negative directions
separating it into left and right regions
Then, in the divided plane
a new plane is defined again
Thus, the positive and negative directions are determined
and in the negative region, another new plane is defined
separating the positive and negative regions further
This creates a binary tree
as shown on the screen
So, by using this BSP tree
how rendering is implemented
can be roughly explained
I will explain now
Here, there is a certain level
This level contains single-sided walls and double-sided walls
which are the two types present
The walls on the outside are single-sided
and the walls on the inside are
double-sided
The player is assumed to always be
inside the single-sided walls
Let's make this assumption
So, walls A, B, C, and D are single-sided
while F, G, and H have double-sided properties
And these walls, as shown here
follow a certain sequence
as indicated
They follow the direction of the arrows
Let us imagine this
So, when such a space is given
using a BSP tree
we can effectively divide it
The condition for dividing is
that the divided space
should have a convex shape
that does not obstruct visibility
or the division continues
until the number of shapes
is at least one
When the number of shapes becomes one
the division stops
following these rules
Let's proceed with the division
For the first division
we will define a plane that passes through wall F
Such a division plane
will be specified
This division plane
does not follow a specific formula for definition
In some cases, the developer
can arbitrarily define this dividing plane
setting it however they wish
Manually defining each one
every time
can be very tedious if the map is large,
as the work becomes extensive
Thus, it is known to define
planes heuristically
In any case, we will use wall F as a reference
and set plane F to divide the space
Let’s assume this is how the division is done
Then, the node for wall F
is assigned as the root node
and using wall F as a basis
the space is divided into two regions
Let’s move on to the next step
Once the dividing plane has been defined
the space should be divided
into two parts accordingly
For walls A and C,
since they intersect plane F
they are divided into A1, A2, C1, and C2
Each is split into two parts
Here, the dividing plane
is currently facing downward
so this side becomes the positive region
and this side becomes the negative region
Thus, the negative region contains
walls forming the left node
which are A1, B, and C1
The remaining walls are placed
in the right node
Now, let’s examine
if each node can be further divided
This must be examined
As I mentioned earlier,
the region consisting of A1, B1, and C1
is convex when I am inside it,
ensuring that nothing obstructs the view
This forms a convex region
Thus, the left node
is complete, and now we examine
whether the right region
can be further divided
If something is located in the right region
for instance, here
A2 would be obstructed by G
Since this obstructs the view
it must be further divided
Let’s proceed to the next step
This time, using a new dividing plane
that aligns with wall G
we define plane G
to divide this right space
Let’s perform this division
The positive region of plane G will be here
and the negative region will be here
As done earlier,
for any regions intersecting plane G
we must further divide them
Moving on to the next step,
since wall D intersects plane G
we split wall D into D1 and D2
Thus, the shapes behind plane G
will be A2 and D1
In this case,
there is nothing obstructing the view
so we assign it to the left node
and terminate the division
Now, regarding the remaining right region
it contains H, C2, and D2
If the player is here
it obstructs the view
so further division is necessary
as can be seen
Let us move on to the next step
For the next space division,
we define a plane H that aligns with wall H
and set up plane H
to divide the space
Since the plane faces this direction
we examine the walls intersecting H
and divide them into two
In the next step, the intersection with H
is currently at D2, as mentioned earlier
By splitting D2 into D3 and D4
we can achieve the desired result
The space behind plane H
consists of D4 and C2
while the space in front of plane H
contains only D3
Both of these spaces
do not obstruct the view
so we have fully divided the space
to the extent needed
as can be seen
Thus, the final divided space structure
and the BST tree's data structure
are as follows
Now that the space is divided
and the data structure is built
if the player is positioned as shown
let’s see how the rendering
proceeds
As shown here, the player
has this line of sight
Currently, the player
is facing walls F, G, and H
This can be seen as the current state
First, identify the space the player occupies
to determine the rendering order
The player is in the positive space
of plane F
Thus, polygons in the negative region
must be rendered first
this should be done first
From the root node
the polygons A1, B, and C1
walls A1, B, and C1
should be queued first in the rendering order
To complete the rendering order,
the remaining steps must be defined
Returning to the root,
we examine wall F
Since wall F is double-sided
it consists of a front and a back side
Through visibility checks
we can skip rendering the back side
and set it to render only the front side
Thus, in the rendering order
the polygons from the negative space
A1, B, and C1 are rendered first,
followed by the front side of wall F
This is how the order is established
This is how the order can be set
Let’s move on to the next step
Next, for the plane at the next depth
we will perform a comparison for plane G
The player is in the positive space
of plane G
First, the polygons in the negative space
specifically walls A2 and D1
are rendered
Thus, the rendering order becomes A1, B, C1
followed by the front of wall F, and then A2 and D1
This completes the rendering process
Returning to the node, this time
as done with wall F,
we check whether the double-sided wall G
is facing the player
If they are facing each other,
the front side of wall G
is rendered,
and then we proceed to the right node
In the next step,
we analyze the space for wall H
Since the player is in the positive space
the walls D4 and C2 in the negative space
are rendered first
Then, the front side of wall H is rendered
and finally, wall D3 is rendered
This completes all rendering
By traversing the tree while the player
is in this space
we could determine
the final rendering order
To sum up again, it was A1, B, C1
followed by the front of F, then A2, D1, the front of G,
D4, C2, the front of H, and finally D3
This is the sequence in which rendering proceeds
Once the rendering order is decided
it is not always necessary
to strictly follow it
Rendering can be optimized further based on visibility checks
or by using techniques like Z-buffering
These approaches allow for
more efficient rendering
For instance, if the player
is in the negative space behind wall F
in such cases, instead of starting from the left
you would begin rendering from the right node
First, render all the right nodes
before moving to the left
This allows the rendering order to be adjusted
If the player is facing forward
and we know their orientation
then the positive space of wall F
does not need to be rendered
Rendering it is unnecessary
Thus, a significant number of objects
can be excluded from rendering
Only the walls A1, B
and C1 in front would need to be rendered
Similarly,
each wall can be checked for visibility
to ensure only visible walls are rendered
Rendering only the necessary walls
makes the process even more efficient
This leads to a more optimized rendering process
The pros and cons of BSP trees
can be summarized as follows
The advantages of BSP trees are
Before the advent of graphics cards,
everything had to be rendered using the CPU
Rendering relied solely on CPU processing
to minimize CPU workload
BSP trees were a crucial algorithm
However, as mentioned earlier
they are very complex to implement
Automatically detecting optimal planes
requires developing heuristic algorithms
Moreover, debugging whether the constructed level
is correctly set up is challenging
Additionally, BSP trees
are only applicable to static backgrounds
They are not suited for dynamic environments
Since BSP logic involves splitting static backgrounds
any changes in background layout
require a complete rebuild
of all levels
It would have to be rebuilt
So, for larger levels
building them consumes significant time
This lowers development productivity
Nowadays, all rendering tasks
utilize the power of graphics hardware
for high-speed computations
Thus, BSP trees are no longer used
Graphics card-based algorithms
have largely replaced them
As a result, BSP trees are no longer
widely used as they once were
This concludes today’s lecture
Thank you for attending
Thank you
Summary Technique for organizing k-D data into binary tree to enable efficient search Just as 1D numerical data can be searched through binary tree
k-D data can also be efficiently searched Rules for KD Tree Construction Each node stores k-D data All nodes (leaf nodes x) divide space into 2 parts
Nodes use specified dimension to divide given space Typically, dimensions are assigned to nodes in the order x, y, z, x based on depth
Nodes use standard basis vectors for space division + divide space based on dimension values of data they contain Lower values go to left child node
while higher values go to right child node, based on dimension data of node Next depth node assigned the next dimension, cycling back to x after used
Uses of KD Tree Finding nearest point to given point Finding points within specified range
By identifying areas that do not need to be examined, it excludes these areas from the search Overview and Working Principles of BSP Tree
Overview/principle of BSP Tree Technique that bisects given space and stores in tree structure to enable efficient search specify plane to divide spa
Separate terrain into front and back parts based on the plane and split geometry that intersects Recursively split separated spaces to form binary tr
Stop when any of following conditions are met Numb of polygons in leaf node is below specified threshold Tree depth reaches max suitable plane find x
Applications of BSP Tree Divide 3D levels for efficient rendering with hidden surface removal Detect ray collisions in 3D Divide terrain information
Pros and Cons of BSP Tree Pro Before graphics cards, crucial for minimizing CPU computation and was key algorithm Con Complex to implement/debug
Limited to static backgrounds Requires complete reconstruction if background layout changes Time-intensive for large levels, reducing productivity
With modern graphics cards enabling fast computations, it has largely been replaced and is no longer widely used