WEBVTT

1
00:00:06.073 --> 00:00:09.797
Game Basics
Understanding Spatial Partitioning Algorithms: KD-Tree and BSP-Tree

2
00:00:27.683 --> 00:00:29.255
Hello, everyone

3
00:00:29.255 --> 00:00:31.322
This is Lee Deug-woo with Game Algorithms

4
00:00:31.322 --> 00:00:34.905
In this lecture, we will cover something that is used for spatial partitioning in games

5
00:00:34.905 --> 00:00:39.170
called the KD-Tree and BSP-Tree algorithms

6
00:00:39.170 --> 00:00:40.546
The lecture on Spatial Partitioning Algorithms:

7
00:00:40.546 --> 00:00:42.953
KD-Tree and BSP-Tree

8
00:00:42.953 --> 00:00:45.298
is divided into three parts

9
00:00:45.298 --> 00:00:46.968
First, I will explain the overview

10
00:00:46.968 --> 00:00:49.166
and working principles of KD-Trees

11
00:00:49.166 --> 00:00:51.245
Next, using a practical example project

12
00:00:51.245 --> 00:00:54.845
I will introduce how to implement KD-Trees

13
00:00:54.845 --> 00:00:57.216
Finally, I will explain the overview

14
00:00:57.216 --> 00:00:59.867
 and working principles of BSP-Trees

15
00:00:59.867 --> 00:01:03.600
Overview and Working Principles of KD-Tree

16
00:01:03.600 --> 00:01:06.215
The KD-Tree

17
00:01:06.215 --> 00:01:08.396
first devised by Jon Bentley in 1975

18
00:01:08.396 --> 00:01:10.710
is a spatial partitioning method

19
00:01:10.710 --> 00:01:12.555
If you look at the title of the paper, it says

20
00:01:12.555 --> 00:01:14.275
Multidimensional

21
00:01:14.275 --> 00:01:16.138
Binary Search Trees

22
00:01:16.138 --> 00:01:18.996
The term "multidimensional binary tree" is mentioned

23
00:01:18.996 --> 00:01:20.503
used for

24
00:01:20.503 --> 00:01:21.901
associative searching

25
00:01:21.901 --> 00:01:24.818
and it is described as being used for associative searching

26
00:01:24.818 --> 00:01:26.518
So, interpreting this title

27
00:01:26.518 --> 00:01:31.396
it explains a method for constructing multidimensional binary trees

28
00:01:31.396 --> 00:01:35.035
for associative searching

29
00:01:35.035 --> 00:01:38.746
In this paper, the term "KD-Tree"

30
00:01:38.746 --> 00:01:41.993
was introduced for the first time, referring to a K-dimensional tree

31
00:01:41.993 --> 00:01:44.853
To summarize the paper: as seen in the illustration on the left below

32
00:01:44.853 --> 00:01:48.435
we have a set of 2-dimensional point data scattered like this

33
00:01:48.435 --> 00:01:51.887
In reality, this method can be applied to data in all dimensions

34
00:01:51.887 --> 00:01:53.680
but 2D is used for simplicity

35
00:01:53.680 --> 00:01:55.569
in the illustration

36
00:01:55.569 --> 00:01:57.981
If we take these points

37
00:01:57.981 --> 00:02:00.453
and arrange them as shown in the illustration on the right

38
00:02:00.453 --> 00:02:02.123
in a tree structure

39
00:02:02.123 --> 00:02:05.837
we can perform searches more efficiently

40
00:02:05.837 --> 00:02:08.480
Just as we typically use binary trees

41
00:02:08.480 --> 00:02:10.721
to effectively search for numerical data in 2D

42
00:02:10.721 --> 00:02:14.122
the same logic applies here

43
00:02:14.122 --> 00:02:15.919
To achieve this, however

44
00:02:15.919 --> 00:02:17.759
we need what’s represented on the right

45
00:02:17.759 --> 00:02:20.156
called a discriminator

46
00:02:20.156 --> 00:02:21.072
This needs to be set

47
00:02:21.072 --> 00:02:23.700
Here, you can see discriminators such as 0, 1, 0, 1,

48
00:02:23.700 --> 00:02:26.012
set according to the depth

49
00:02:26.012 --> 00:02:28.113
of the node

50
00:02:28.113 --> 00:02:30.175
Let me explain how this is configured

51
00:02:30.175 --> 00:02:32.303
and the method for building a KD-Tree

52
00:02:32.303 --> 00:02:34.340
I will now explain

53
00:02:34.340 --> 00:02:37.157
The rules for generating a KD-Tree are as follows

54
00:02:37.157 --> 00:02:38.470
First, every node

55
00:02:38.470 --> 00:02:40.713
stores K-dimensional data

56
00:02:40.713 --> 00:02:42.230
Whether it’s 2D, 3D, or 4D

57
00:02:42.230 --> 00:02:44.711
All types of data can be stored

58
00:02:44.711 --> 00:02:46.216
Next, every non-leaf node

59
00:02:46.216 --> 00:02:49.356
Except for leaf nodes,

60
00:02:49.356 --> 00:02:51.009
divides the space into two parts

61
00:02:51.009 --> 00:02:53.554
It uses its own data to do so

62
00:02:53.554 --> 00:02:56.037
It splits the space into two parts

63
00:02:56.037 --> 00:02:58.104
Nodes that divide the space

64
00:02:58.104 --> 00:03:01.052
use specified dimensions

65
00:03:01.052 --> 00:03:02.678
to partition the space

66
00:03:02.678 --> 00:03:04.701
This is the rule that is defined

67
00:03:04.701 --> 00:03:06.961
This specified dimension

68
00:03:06.961 --> 00:03:09.901
is the Discriminator

69
00:03:09.901 --> 00:03:12.277
as I mentioned earlier

70
00:03:12.277 --> 00:03:14.926
Typically, it depends on the depth of the node

71
00:03:14.926 --> 00:03:18.978
proceeding in the order of x, y, z, x

72
00:03:18.978 --> 00:03:21.535
Earlier, it was specified as 0, 1, 0, 1,

73
00:03:21.535 --> 00:03:24.176
which actually represents the sequence of dimensions

74
00:03:24.176 --> 00:03:26.269
So, x is 0,

75
00:03:26.269 --> 00:03:29.056
y is 1, and z is 2

76
00:03:29.056 --> 00:03:31.074
If it’s in 2D

77
00:03:31.074 --> 00:03:34.711
it proceeds in the order of x, y, x, y

78
00:03:34.711 --> 00:03:37.372
So, the node will have 0, 1, 0, 1

79
00:03:37.372 --> 00:03:40.446
as the dimension values

80
00:03:40.446 --> 00:03:42.349
Nodes that partition space

81
00:03:42.349 --> 00:03:43.760
use standard bases

82
00:03:43.760 --> 00:03:46.802
The x-axis, y-axis, and z-axis are mutually orthogonal

83
00:03:46.802 --> 00:03:48.695
and these standard bases are utilized

84
00:03:48.695 --> 00:03:50.417
Once the nodes are configured

85
00:03:50.417 --> 00:03:54.078
with K-dimensional data and their respective dimensions

86
00:03:54.078 --> 00:03:56.204
they use this to partition the space

87
00:03:56.204 --> 00:03:57.905
Using the dimension value set on the node

88
00:03:57.905 --> 00:04:00.604
they partition the space using the node’s dimension value

89
00:04:00.604 --> 00:04:02.043
For example, if a node contains

90
00:04:02.043 --> 00:04:05.943
2D data such as (70, 30)

91
00:04:05.943 --> 00:04:08.771
and the x-axis is specified

92
00:04:08.771 --> 00:04:11.721
it uses the x-axis value of 70

93
00:04:11.721 --> 00:04:13.659
to divide the node’s area

94
00:04:13.659 --> 00:04:14.949
into two parts

95
00:04:16.641 --> 00:04:18.019
So, this value of 70

96
00:04:18.019 --> 00:04:19.863
becomes the basis for the dimensional data of the node

97
00:04:19.863 --> 00:04:22.696
The left child node is assigned lower values,

98
00:04:22.696 --> 00:04:25.464
and the right child node is assigned higher values

99
00:04:25.464 --> 00:04:27.396
This is how it’s designed

100
00:04:27.396 --> 00:04:29.934
When the area is divided using 70 as the criterion

101
00:04:29.934 --> 00:04:31.604
points smaller than 70

102
00:04:31.604 --> 00:04:33.444
are moved to the left child node

103
00:04:33.444 --> 00:04:34.559
Points greater than 70

104
00:04:34.559 --> 00:04:37.546
are moved to the right child node

105
00:04:37.546 --> 00:04:40.181
Then, in the next depth node

106
00:04:40.181 --> 00:04:43.569
The dimension is incremented by one step

107
00:04:43.569 --> 00:04:44.449
Once all dimensions

108
00:04:44.449 --> 00:04:46.971
have been used, it loops back

109
00:04:46.971 --> 00:04:48.004
to the first dimension

110
00:04:48.004 --> 00:04:49.556
starting again with x

111
00:04:49.556 --> 00:04:53.328
For example, if the depth is 0

112
00:04:53.328 --> 00:04:55.710
it means it refers to the first dimension

113
00:04:55.710 --> 00:04:57.709
which corresponds to the x-axis

114
00:04:57.709 --> 00:04:59.609
If the depth is 1, it corresponds to the y-axis

115
00:04:59.609 --> 00:05:01.431
If the depth is 2, it corresponds to the z-axis

116
00:05:01.431 --> 00:05:04.541
If the depth is 3, it cycles back to x

117
00:05:04.541 --> 00:05:07.411
However, it’s not explicitly labeled as x, y, z

118
00:05:07.411 --> 00:05:09.420
but rather assigned using index values 0, 1, and 2

119
00:05:09.420 --> 00:05:11.143
These indices are used for assignment

120
00:05:11.143 --> 00:05:13.668
Therefore, if we know the depth of a node

121
00:05:13.668 --> 00:05:16.135
the dimension associated with that node

122
00:05:16.135 --> 00:05:17.781
can be determined by performing a modulo operation

123
00:05:17.781 --> 00:05:19.346
on the depth to get the dimension index

124
00:05:19.346 --> 00:05:21.942
This is how the dimension is assigned

125
00:05:21.942 --> 00:05:24.602
Now, using actual data

126
00:05:24.602 --> 00:05:27.496
let’s see how to construct a KD-tree

127
00:05:27.496 --> 00:05:30.190
using an example

128
00:05:30.190 --> 00:05:33.817
First, we define an area from (0, 0)

129
00:05:33.817 --> 00:05:36.190
to (100, 100)

130
00:05:36.190 --> 00:05:37.997
which is arbitrarily defined

131
00:05:37.997 --> 00:05:41.885
Let’s assume there are five points within this area

132
00:05:41.885 --> 00:05:43.762
This area, in fact

133
00:05:43.762 --> 00:05:45.988
doesn’t need to be explicitly defined

134
00:05:45.988 --> 00:05:47.930
but to visualize the process

135
00:05:47.930 --> 00:05:50.696
it is set like this

136
00:05:50.696 --> 00:05:54.358
Using the five points within this area

137
00:05:54.358 --> 00:05:55.923
we will construct a 2D KD-tree

138
00:05:55.923 --> 00:05:57.856
Let’s see how to do it

139
00:05:57.856 --> 00:05:59.591
The point data will be arranged

140
00:05:59.591 --> 00:06:00.927
in the following order

141
00:06:00.927 --> 00:06:05.859
First, insert (60, 40) as the first point

142
00:06:05.859 --> 00:06:08.305
Second, (30, 60)

143
00:06:08.305 --> 00:06:10.865
Third, (90, 80)

144
00:06:10.865 --> 00:06:12.936
Fourth, (40, 10)

145
00:06:12.936 --> 00:06:17.966
Finally, (50, 30)

146
00:06:17.966 --> 00:06:20.250
We will construct a KD-tree using these points

147
00:06:22.480 --> 00:06:25.843
When using (60, 40) as the first point

148
00:06:25.843 --> 00:06:29.075
since it’s the first point,

149
00:06:29.075 --> 00:06:31.500
it is assigned as the root node

150
00:06:31.500 --> 00:06:33.480
It is designated as the root node

151
00:06:33.480 --> 00:06:35.792
Since it’s both the root and a leaf node

152
00:06:35.792 --> 00:06:38.473
no spatial division occurs initially

153
00:06:38.473 --> 00:06:40.369
When the next data is inserted

154
00:06:40.369 --> 00:06:42.255
a child node is created

155
00:06:42.255 --> 00:06:44.061
and the division occurs along the x-axis

156
00:06:44.061 --> 00:06:45.753
and spatial division is performed

157
00:06:48.180 --> 00:06:53.242
Using (30, 60) as the second point

158
00:06:53.242 --> 00:06:55.967
when (30, 60) is inserted

159
00:06:55.967 --> 00:06:58.255
first, the x-axis

160
00:06:58.255 --> 00:07:00.741
of the first root node

161
00:07:00.741 --> 00:07:03.866
is used as the basis for division

162
00:07:03.866 --> 00:07:07.497
So, for the root node (60, 40)

163
00:07:07.497 --> 00:07:11.682
we only need to consider the x-value of 60

164
00:07:11.682 --> 00:07:15.783
Comparing 60 with the x-value of (30, 60)

165
00:07:15.783 --> 00:07:18.033
we don’t need to look at the y-value

166
00:07:18.033 --> 00:07:19.985
only at the x-value 30

167
00:07:19.985 --> 00:07:23.059
Comparing 30 and 60

168
00:07:23.059 --> 00:07:25.780
since 30 is smaller than 60

169
00:07:25.780 --> 00:07:27.684
as previously explained

170
00:07:27.684 --> 00:07:29.823
it is inserted into the left child node

171
00:07:29.823 --> 00:07:31.969
according to the rules

172
00:07:31.969 --> 00:07:35.914
So, (30, 60) is inserted as the left child node

173
00:07:35.914 --> 00:07:37.870
Here as well, (30, 60),

174
00:07:37.870 --> 00:07:38.805
being a leaf node

175
00:07:38.805 --> 00:07:40.561
does not cause further spatial division initially

176
00:07:40.561 --> 00:07:42.666
If additional data is inserted

177
00:07:42.666 --> 00:07:45.297
the space is divided using the discriminator

178
00:07:45.297 --> 00:07:46.640
In other words, the division key

179
00:07:46.640 --> 00:07:48.915
which in this case is the y-axis

180
00:07:48.915 --> 00:07:51.255
Because previously, the first

181
00:07:51.255 --> 00:07:53.818
root node at depth 0

182
00:07:53.818 --> 00:07:55.378
uses the x-axis

183
00:07:55.378 --> 00:07:57.100
The next depth node

184
00:07:57.100 --> 00:07:59.440
should divide based on the y-axis

185
00:07:59.440 --> 00:08:02.453
Let’s move on to the next step

186
00:08:02.453 --> 00:08:05.750
Let’s examine the case where the third data point, (90, 80)

187
00:08:05.750 --> 00:08:08.969
is inserted

188
00:08:08.969 --> 00:08:10.985
When the third data point is inserted

189
00:08:10.985 --> 00:08:12.938
the process starts at the root node

190
00:08:12.938 --> 00:08:14.547
to perform a comparison

191
00:08:14.547 --> 00:08:17.203
The root node’s dimension is

192
00:08:17.203 --> 00:08:19.334
set to the x-axis

193
00:08:19.334 --> 00:08:22.411
Therefore, we only compare the x-value 60

194
00:08:22.411 --> 00:08:24.438
with the x-value of the third data point, 90

195
00:08:24.438 --> 00:08:26.684
Only these two values are compared

196
00:08:26.684 --> 00:08:29.523
Since 90 is greater than 60

197
00:08:29.523 --> 00:08:31.154
by the rule, it is inserted

198
00:08:31.154 --> 00:08:34.127
into the right child node of the root

199
00:08:34.127 --> 00:08:36.450
The right child node was empty, correct?

200
00:08:36.450 --> 00:08:38.869
So, it is inserted into the right child node

201
00:08:38.869 --> 00:08:40.751
and this completes the step

202
00:08:40.751 --> 00:08:42.917
This way, the tree is balanced

203
00:08:42.917 --> 00:08:44.343
The tree is constructed in a balanced manner

204
00:08:44.343 --> 00:08:47.138
Similarly, since it is a leaf node,

205
00:08:47.138 --> 00:08:49.298
spatial division has not yet occurred

206
00:08:49.298 --> 00:08:51.908
If data is inserted later, this space

207
00:08:51.908 --> 00:08:54.365
will be divided based on the y-axis

208
00:08:54.365 --> 00:08:55.535
This is how it works

209
00:08:57.562 --> 00:09:00.292
Let’s add the next data point

210
00:09:00.292 --> 00:09:02.148
Let’s add the fourth data point

211
00:09:02.148 --> 00:09:05.441
We use (40, 10) as the fourth data point

212
00:09:05.441 --> 00:09:08.001
At this point, the search starts from the root

213
00:09:08.001 --> 00:09:09.946
We said the root node only considers the x-value

214
00:09:09.946 --> 00:09:12.031
Thus, comparing 60 and 40

215
00:09:12.031 --> 00:09:14.490
we only need to compare these two values

216
00:09:14.490 --> 00:09:16.483
Since 40 is smaller than 60

217
00:09:16.483 --> 00:09:19.848
it proceeds to the left child node

218
00:09:19.848 --> 00:09:21.077
However, at this point

219
00:09:21.077 --> 00:09:23.106
data already exists in the node

220
00:09:23.106 --> 00:09:24.978
So, another comparison

221
00:09:24.978 --> 00:09:26.561
needs to be performed

222
00:09:26.561 --> 00:09:28.577
At this point, the discriminator,

223
00:09:28.577 --> 00:09:30.872
or the axis value

224
00:09:30.872 --> 00:09:32.101
has changed to a different dimension

225
00:09:32.101 --> 00:09:34.273
It is now designated as the y-axis

226
00:09:34.273 --> 00:09:36.693
So, instead of comparing the x-value 30,

227
00:09:36.693 --> 00:09:39.702
we compare the y-value 60

228
00:09:39.702 --> 00:09:46.366
The y-coordinate of the fourth data point, 10,

229
00:09:46.366 --> 00:09:48.039
is smaller than 60

230
00:09:48.039 --> 00:09:50.400
Thus, it proceeds to the left node

231
00:09:50.400 --> 00:09:51.768
Since data is inserted

232
00:09:51.768 --> 00:09:55.386
(30, 60) divides the space into two parts

233
00:09:55.386 --> 00:09:56.982
This division occurs

234
00:09:56.982 --> 00:09:59.559
perpendicular to the y-axis,

235
00:09:59.559 --> 00:10:00.952
based on the x-axis

236
00:10:00.952 --> 00:10:03.211
The space is divided accordingly

237
00:10:03.211 --> 00:10:06.801
So, (40, 10) occupies the lower section

238
00:10:06.801 --> 00:10:09.876
When viewed along the y-axis,

239
00:10:09.876 --> 00:10:12.068
this is the region of the right node

240
00:10:12.068 --> 00:10:14.467
while the left node occupies the other region

241
00:10:14.467 --> 00:10:16.550
Currently,

242
00:10:16.550 --> 00:10:19.797
(40, 10) is located in the left node

243
00:10:19.797 --> 00:10:21.543
Through the modulo operation

244
00:10:21.543 --> 00:10:23.976
the x-axis is reassigned

245
00:10:23.976 --> 00:10:25.875
If data is inserted at this point

246
00:10:25.875 --> 00:10:27.699
it will follow the same rules

247
00:10:27.699 --> 00:10:31.115
and divide again based on the x-axis

248
00:10:31.115 --> 00:10:32.775
The space will be divided into left and right

249
00:10:32.775 --> 00:10:34.860
This division will be performed

250
00:10:34.860 --> 00:10:36.662
Let’s add the next data point

251
00:10:36.662 --> 00:10:40.690
Next, we added the fifth data point, (50, 30)

252
00:10:40.690 --> 00:10:43.037
Starting at the root

253
00:10:43.037 --> 00:10:45.742
since 50 is smaller than 60

254
00:10:45.742 --> 00:10:47.528
it proceeds to the left child node

255
00:10:47.528 --> 00:10:49.881
Then, considering only the y-value

256
00:10:49.881 --> 00:10:52.761
since 30 is smaller than 60

257
00:10:52.761 --> 00:10:54.806
it moves further left

258
00:10:54.806 --> 00:10:57.301
However, since there is already a node on the left

259
00:10:57.301 --> 00:10:59.270
we compare the x-values again

260
00:10:59.270 --> 00:11:02.571
Since 50 is greater than 40

261
00:11:02.571 --> 00:11:05.826
it is inserted into the right child node of (40, 10)

262
00:11:05.826 --> 00:11:09.220
It is placed there

263
00:11:09.220 --> 00:11:11.542
The process continues using the same rules

264
00:11:11.542 --> 00:11:14.619
Since the depth has increased by one

265
00:11:14.619 --> 00:11:16.769
for (50, 30)

266
00:11:16.769 --> 00:11:18.475
the y-value 30 is used as the basis

267
00:11:18.475 --> 00:11:21.505
to divide the space vertically

268
00:11:21.505 --> 00:11:24.348
The final result of the constructed KD-tree

269
00:11:24.348 --> 00:11:25.968
is shown in the next diagram

270
00:11:25.968 --> 00:11:28.332
To make it easier to indicate distinctions

271
00:11:28.332 --> 00:11:30.796
if the x-axis is set

272
00:11:30.796 --> 00:11:33.186
the space is divided along the y-axis

273
00:11:33.186 --> 00:11:34.976
and if the y-axis is set

274
00:11:34.976 --> 00:11:38.175
the space is divided along the x-axis

275
00:11:38.175 --> 00:11:41.328
This way, you can observe the results of the division

276
00:11:41.328 --> 00:11:42.712
Based on the KD-tree constructed in this manner,

277
00:11:42.712 --> 00:11:44.286
constructed in this manner,

278
00:11:44.286 --> 00:11:46.968
you can perform searches

279
00:11:48.221 --> 00:11:51.635
So, how do you utilize the KD-tree that’s been built

280
00:11:51.635 --> 00:11:53.629
Let’s explore how to search in this tree

281
00:11:53.629 --> 00:11:55.304
and the ways it can be applied

282
00:11:55.304 --> 00:11:57.514
We will examine this now

283
00:11:57.514 --> 00:11:59.914
First, the KD-tree is used

284
00:11:59.914 --> 00:12:01.419
primarily for two purposes

285
00:12:01.419 --> 00:12:03.373
First, for any given point

286
00:12:03.373 --> 00:12:05.213
when a point is provided

287
00:12:05.213 --> 00:12:08.016
it is used to find the closest

288
00:12:08.016 --> 00:12:10.035
point to that given point

289
00:12:10.035 --> 00:12:13.377
This is known as a "Nearest Neighbor Query"

290
00:12:13.377 --> 00:12:15.301
Second, it is used

291
00:12:15.301 --> 00:12:17.200
to find all points

292
00:12:17.200 --> 00:12:19.731
that fall within a given range

293
00:12:19.731 --> 00:12:21.995
It is used widely for this

294
00:12:21.995 --> 00:12:24.155
This is often called a "Range Query"

295
00:12:24.155 --> 00:12:26.574
As mentioned earlier,

296
00:12:26.574 --> 00:12:28.916
instead of checking the entire dataset

297
00:12:28.916 --> 00:12:32.209
the algorithm identifies regions

298
00:12:32.209 --> 00:12:34.417
that don’t need to be searched

299
00:12:34.417 --> 00:12:36.764
and excludes them from the query

300
00:12:36.764 --> 00:12:39.151
If we want to find the nearest point

301
00:12:39.151 --> 00:12:41.411
scanning everything

302
00:12:41.411 --> 00:12:43.828
even though there are only 5 data points here

303
00:12:43.828 --> 00:12:46.156
would become inefficient if there were, say, 100,000 points

304
00:12:46.156 --> 00:12:48.087
The amount of searching would increase significantly

305
00:12:48.087 --> 00:12:50.726
By using the tree

306
00:12:50.726 --> 00:12:52.503
you can exclude unnecessary regions

307
00:12:52.503 --> 00:12:56.036
and perform searches more efficiently

308
00:12:56.036 --> 00:12:59.298
This is one of the advantages of the KD-tree

309
00:12:59.298 --> 00:13:02.171
Now, let’s look at how

310
00:13:02.171 --> 00:13:04.199
to find the closest point to a given point

311
00:13:04.199 --> 00:13:05.833
Let’s examine this process

312
00:13:07.402 --> 00:13:10.738
We already have the tree constructed

313
00:13:10.738 --> 00:13:12.496
From this constructed tree

314
00:13:12.496 --> 00:13:15.463
when a point (80, 90) is provided

315
00:13:15.463 --> 00:13:17.740
how do we find the point closest

316
00:13:17.740 --> 00:13:18.939
to (80, 90)

317
00:13:18.939 --> 00:13:20.235
Let’s take a look

318
00:13:21.376 --> 00:13:23.734
To find the nearest node

319
00:13:23.734 --> 00:13:25.817
you start at the root node

320
00:13:25.817 --> 00:13:28.987
and perform a depth-first search

321
00:13:28.987 --> 00:13:31.047
For each node,

322
00:13:31.047 --> 00:13:33.619
the steps to be performed are quite clear

323
00:13:33.619 --> 00:13:36.439
First, measure the distance

324
00:13:36.439 --> 00:13:38.564
between the node’s data and the given point

325
00:13:38.564 --> 00:13:40.246
Checking whether it is the closest

326
00:13:40.246 --> 00:13:42.212
should be determined, right?

327
00:13:42.212 --> 00:13:43.641
The next thing that should be done is

328
00:13:43.641 --> 00:13:45.673
measure the shortest distance between

329
00:13:45.673 --> 00:13:48.173
the given point and the dividing line

330
00:13:48.173 --> 00:13:49.739
created by the node’s designated dimension

331
00:13:49.739 --> 00:13:51.882
This line divides the space into two regions

332
00:13:51.882 --> 00:13:54.658
Measure the shortest distance

333
00:13:54.658 --> 00:13:56.805
to this dividing line

334
00:13:56.805 --> 00:13:58.567
This distance is measured

335
00:13:58.567 --> 00:14:00.696
You measure these two things

336
00:14:00.696 --> 00:14:03.278
If the distance to the current node

337
00:14:03.278 --> 00:14:05.012
is the shortest so far,

338
00:14:05.012 --> 00:14:06.922
that node becomes the nearest node

339
00:14:06.922 --> 00:14:08.843
At least for now

340
00:14:08.843 --> 00:14:11.218
Next, based on the specified dimension

341
00:14:11.218 --> 00:14:12.883
perform comparisons

342
00:14:12.883 --> 00:14:13.789
It’s the same as before

343
00:14:13.789 --> 00:14:17.912
If the value is smaller, continue searching

344
00:14:17.912 --> 00:14:20.118
the left node first

345
00:14:20.118 --> 00:14:22.114
If it’s greater or equal

346
00:14:22.114 --> 00:14:24.412
search the right node first

347
00:14:24.412 --> 00:14:27.715
For example, if the given point is (10, 50),

348
00:14:27.715 --> 00:14:29.223
and the current node’s value is

349
00:14:29.223 --> 00:14:31.919
set to (30, 50)

350
00:14:31.919 --> 00:14:34.395
and the node has a first dimension value

351
00:14:34.395 --> 00:14:36.331
of 0

352
00:14:36.331 --> 00:14:37.894
in this case,

353
00:14:37.894 --> 00:14:41.239
you first calculate the distance between (10, 50) and (30, 50)

354
00:14:41.239 --> 00:14:43.181
then measure this distance

355
00:14:43.181 --> 00:14:47.425
Next, measure the distance from (10, 50)

356
00:14:47.425 --> 00:14:51.127
to the dividing line at 30, which is 20

357
00:14:51.127 --> 00:14:53.795
So, you measure 20

358
00:14:53.795 --> 00:14:55.843
You measure these two distances

359
00:14:55.843 --> 00:14:58.508
Then, according to the rule

360
00:14:58.508 --> 00:15:03.225
since the given point is smaller than the first dimension value

361
00:15:03.225 --> 00:15:06.747
you prioritize searching the left node

362
00:15:06.747 --> 00:15:09.071
So, you search the left node first

363
00:15:09.071 --> 00:15:11.564
After coming back and rechecking

364
00:15:11.564 --> 00:15:13.814
if the shortest distance found so far

365
00:15:13.814 --> 00:15:16.898
is shorter than the distance to the dividing line

366
00:15:16.898 --> 00:15:17.884
you do not proceed with the search

367
00:15:17.884 --> 00:15:20.421
You skip searching the right node

368
00:15:20.421 --> 00:15:22.663
For example, in the previous case

369
00:15:22.663 --> 00:15:25.296
if the shortest distance found by searching the left node

370
00:15:25.296 --> 00:15:27.443
is 15, let’s assume this

371
00:15:27.443 --> 00:15:30.538
However, since this is shorter than the shortest distance to the dividing line,

372
00:15:30.538 --> 00:15:32.724
which is 20,

373
00:15:32.724 --> 00:15:36.505
the region on the right side of the dividing line

374
00:15:36.505 --> 00:15:39.341
is always farther than the shortest distance

375
00:15:39.341 --> 00:15:40.332
This conclusion can be drawn

376
00:15:40.332 --> 00:15:42.823
Therefore, the right node region

377
00:15:42.823 --> 00:15:45.617
can be excluded from the search

378
00:15:45.617 --> 00:15:47.417
Let’s explain this with an illustration

379
00:15:47.417 --> 00:15:48.982
I will explain it to you step by step

380
00:15:51.014 --> 00:15:53.805
Suppose we have a given point, (80, 90)

381
00:15:53.805 --> 00:15:56.232
Using the KD-tree that has been built,

382
00:15:56.232 --> 00:15:58.337
we will try to find the closest point

383
00:15:58.337 --> 00:15:59.436
using this algorithm

384
00:15:59.436 --> 00:16:01.466
Let’s run the algorithm

385
00:16:01.466 --> 00:16:06.206
When we first input (80, 90)

386
00:16:06.206 --> 00:16:08.328
we first compare it with the root node

387
00:16:08.328 --> 00:16:13.302
The distance between (80, 90) and (60, 40)

388
00:16:13.302 --> 00:16:15.844
should first be calculated

389
00:16:15.844 --> 00:16:19.188
Next, from (80, 90)

390
00:16:19.188 --> 00:16:22.478
the distance to the dividing line of (60, 40),

391
00:16:22.478 --> 00:16:25.935
which has an x-value of 60, is measured

392
00:16:25.935 --> 00:16:28.710
As shown in the diagram

393
00:16:28.710 --> 00:16:30.310
since the x-value is 80

394
00:16:30.310 --> 00:16:32.770
the shortest distance is 20

395
00:16:32.770 --> 00:16:34.395
It becomes 20

396
00:16:34.395 --> 00:16:37.474
but this is, of course

397
00:16:37.474 --> 00:16:42.774
greater than the distance from the root node

398
00:16:42.774 --> 00:16:46.180
Therefore, the current closest node

399
00:16:46.180 --> 00:16:48.739
is initially set as the root node

400
00:16:48.739 --> 00:16:51.681
upon entering

401
00:16:51.681 --> 00:16:55.065
but first, we must perform a depth-first search

402
00:16:55.065 --> 00:16:58.940
on the left region

403
00:16:58.940 --> 00:17:01.405
According to the rule

404
00:17:01.405 --> 00:17:03.915
since 80 is greater than 60,

405
00:17:03.915 --> 00:17:06.504
we should search the right node

406
00:17:06.504 --> 00:17:09.383
So, we proceed to the right node

407
00:17:09.383 --> 00:17:11.243
and as we enter

408
00:17:11.243 --> 00:17:14.060
we measure the distance between the given point (80, 90)

409
00:17:14.060 --> 00:17:16.301
and the second node, (90, 80)

410
00:17:16.301 --> 00:17:17.722
This distance is calculated

411
00:17:17.722 --> 00:17:19.590
At this point, the distance to the root node

412
00:17:19.590 --> 00:17:21.204
is longer than the distance to (90, 80)

413
00:17:21.204 --> 00:17:25.471
so we determine that (90, 80)

414
00:17:25.471 --> 00:17:27.941
has the shortest distance

415
00:17:27.941 --> 00:17:30.243
Since there are no child nodes

416
00:17:30.243 --> 00:17:31.898
we terminate the search here

417
00:17:31.898 --> 00:17:34.312
and return to the root node

418
00:17:35.459 --> 00:17:37.830
Now, upon returning to the root node

419
00:17:37.830 --> 00:17:40.169
we must decide whether or not

420
00:17:40.169 --> 00:17:42.122
to search the left node

421
00:17:42.122 --> 00:17:45.210
The result of the right node search

422
00:17:45.210 --> 00:17:48.004
is compared against 20

423
00:17:48.004 --> 00:17:49.804
This determines the next step

424
00:17:49.804 --> 00:17:53.125
Since the distance to (90, 80)

425
00:17:53.125 --> 00:17:55.334
is smaller than 20

426
00:17:55.334 --> 00:17:57.844
it shows that the right node region

427
00:17:57.844 --> 00:18:01.076
does not need further exploration

428
00:18:01.076 --> 00:18:03.409
So we can conclude that the closest point

429
00:18:03.409 --> 00:18:06.448
is (90, 80)

430
00:18:06.448 --> 00:18:08.464
The algorithm can now terminate

431
00:18:10.080 --> 00:18:11.873
In summary,

432
00:18:11.873 --> 00:18:14.738
only 2 nodes were visited in total

433
00:18:14.738 --> 00:18:16.354
Instead of traversing all 5 nodes

434
00:18:16.354 --> 00:18:18.468
only 2 were visited

435
00:18:18.468 --> 00:18:20.881
to find the closest point

436
00:18:20.881 --> 00:18:24.178
The closest point was identified as (90, 80),

437
00:18:24.178 --> 00:18:26.923
which we were able to confirm

438
00:18:26.923 --> 00:18:29.539
Thus, by using the KD-tree

439
00:18:29.539 --> 00:18:31.629
we learned how to find the

440
00:18:31.629 --> 00:18:33.714
closest point

441
00:18:35.830 --> 00:18:38.723
Next, let’s look at an algorithm

442
00:18:38.723 --> 00:18:40.725
to find nodes within a given range

443
00:18:40.725 --> 00:18:42.570
This has been summarized

444
00:18:42.570 --> 00:18:45.684
As with the previous algorithm

445
00:18:45.684 --> 00:18:47.606
a depth-first search starting from the root node

446
00:18:47.606 --> 00:18:50.445
is performed

447
00:18:50.445 --> 00:18:52.016
A range essentially refers to

448
00:18:52.016 --> 00:18:55.781
an AABB (Axis-Aligned Bounding Box)

449
00:18:55.781 --> 00:18:58.084
The given AABB range

450
00:18:58.084 --> 00:19:00.860
is checked for overlap with the node’s region

451
00:19:00.860 --> 00:19:03.333
While performing overlap checks

452
00:19:03.333 --> 00:19:04.238
the algorithm proceeds

453
00:19:04.238 --> 00:19:07.445
If the given range

454
00:19:07.445 --> 00:19:10.785
and the node’s AABB region

455
00:19:10.785 --> 00:19:14.599
do not overlap, that region can be excluded from the search

456
00:19:14.599 --> 00:19:16.663
However, if they overlap

457
00:19:16.663 --> 00:19:19.117
then points within the node

458
00:19:19.117 --> 00:19:21.663
are checked for containment

459
00:19:21.663 --> 00:19:24.359
within the given range A

460
00:19:24.359 --> 00:19:27.455
Points meeting this criterion

461
00:19:27.455 --> 00:19:29.537
are added to the list of results

462
00:19:29.537 --> 00:19:31.910
The node’s points are added to this list

463
00:19:31.910 --> 00:19:36.568
If overlapping nodes continue to appear

464
00:19:36.568 --> 00:19:39.170
the depth-first search continues

465
00:19:39.170 --> 00:19:43.916
checking overlaps and containment

466
00:19:43.916 --> 00:19:45.736
between regions and points

467
00:19:45.736 --> 00:19:48.837
This creates a list of points to be returned

468
00:19:48.837 --> 00:19:50.368
This allows you to find

469
00:19:50.368 --> 00:19:51.781
points within the range

470
00:19:53.950 --> 00:19:57.033
Let’s go through an example

471
00:19:57.033 --> 00:20:00.997
Suppose we have a given range like this

472
00:20:00.997 --> 00:20:03.640
First, we compare it with the root node’s region

473
00:20:03.640 --> 00:20:05.138
We begin by performing this comparison

474
00:20:05.138 --> 00:20:07.012
The root node’s region

475
00:20:07.012 --> 00:20:09.143
represents the entire area

476
00:20:09.143 --> 00:20:11.687
Naturally, it overlaps with the given range

477
00:20:11.687 --> 00:20:15.958
Since they overlap

478
00:20:15.958 --> 00:20:19.630
we need to check whether this region includes the point (60, 40)

479
00:20:19.630 --> 00:20:21.251
This check is performed first

480
00:20:21.251 --> 00:20:23.144
The point in the root node

481
00:20:23.144 --> 00:20:25.610
is not currently within the given range

482
00:20:25.610 --> 00:20:27.776
so we pass the operation to its children

483
00:20:27.776 --> 00:20:31.030
The responsibility is handed over to the child nodes

484
00:20:31.030 --> 00:20:34.073
Looking at the child nodes, the left region

485
00:20:34.073 --> 00:20:37.227
overlaps with the given range

486
00:20:37.227 --> 00:20:39.840
whereas the right region

487
00:20:39.840 --> 00:20:42.316
is entirely separate from the given range

488
00:20:42.316 --> 00:20:44.764
Thus, there’s no need to search the right region

489
00:20:44.764 --> 00:20:47.624
We can exclude the right region from the search

490
00:20:47.624 --> 00:20:49.958
So we only search the left region

491
00:20:52.752 --> 00:20:54.508
Let’s proceed to

492
00:20:54.508 --> 00:20:55.853
the second left region

493
00:20:55.853 --> 00:20:58.860
Since it overlaps with the left region

494
00:20:58.860 --> 00:21:01.875
we check whether the node point (30, 60) in this region

495
00:21:01.875 --> 00:21:02.874
is within the given range

496
00:21:02.874 --> 00:21:04.951
This inclusion check is performed

497
00:21:04.951 --> 00:21:07.935
Since it is included, this point

498
00:21:07.935 --> 00:21:10.046
is added to

499
00:21:10.046 --> 00:21:11.929
our list of results

500
00:21:11.929 --> 00:21:14.806
Next, as in previous steps

501
00:21:14.806 --> 00:21:18.068
this is divided into two regions

502
00:21:18.068 --> 00:21:20.309
The upper region

503
00:21:20.309 --> 00:21:21.584
has no child nodes

504
00:21:21.584 --> 00:21:23.741
so no operations are performed here

505
00:21:23.741 --> 00:21:26.066
There’s no need to perform comparisons

506
00:21:26.066 --> 00:21:27.351
Only the lower region

507
00:21:27.351 --> 00:21:28.978
needs to be checked

508
00:21:28.978 --> 00:21:33.644
The region defined by (40, 10)

509
00:21:33.644 --> 00:21:35.340
is this region here

510
00:21:35.340 --> 00:21:36.947
Since it overlaps with the given range

511
00:21:36.947 --> 00:21:39.194
we descend further

512
00:21:41.050 --> 00:21:43.081
When we descend again

513
00:21:43.081 --> 00:21:45.305
we check whether (40, 10)

514
00:21:45.305 --> 00:21:46.393
overlaps with the given range

515
00:21:46.393 --> 00:21:48.605
We determine if they overlap

516
00:21:48.605 --> 00:21:50.501
Since they do not overlap

517
00:21:50.501 --> 00:21:53.256
no operations are performed

518
00:21:53.256 --> 00:21:54.850
Next,

519
00:21:54.850 --> 00:21:58.086
we divide into left and right regions

520
00:21:58.086 --> 00:22:00.236
We divide and compare

521
00:22:00.236 --> 00:22:03.219
Here, it overlaps with the left region

522
00:22:03.219 --> 00:22:06.538
but not with the right region

523
00:22:06.538 --> 00:22:09.286
So, we only search the left region

524
00:22:09.286 --> 00:22:11.545
and bring it down

525
00:22:11.545 --> 00:22:13.562
Since the left region has no nodes,

526
00:22:13.562 --> 00:22:14.808
the search ends here

527
00:22:14.808 --> 00:22:18.595
Thus, all search operations

528
00:22:18.595 --> 00:22:20.406
conclude at this point

529
00:22:20.406 --> 00:22:22.536
So if we organize the results

530
00:22:22.536 --> 00:22:24.099
the total number of nodes visited

531
00:22:24.099 --> 00:22:25.978
was only 3

532
00:22:25.978 --> 00:22:27.427
These two nodes

533
00:22:27.427 --> 00:22:30.274
did not actually need to be visited

534
00:22:30.274 --> 00:22:32.368
Among the three nodes

535
00:22:32.368 --> 00:22:33.716
the only point within the range

536
00:22:33.716 --> 00:22:37.247
was (30, 60)

537
00:22:37.247 --> 00:22:40.643
This was the conclusion

538
00:22:40.643 --> 00:22:44.478
KD-Tree Implementation Method

539
00:22:44.478 --> 00:22:47.457
Extract the provided sample project files

540
00:22:47.457 --> 00:22:48.761
and run Unity

541
00:22:48.761 --> 00:22:51.021
to open the project

542
00:22:51.021 --> 00:22:52.907
The Unity version used for this project

543
00:22:52.907 --> 00:22:57.011
was 201.3.

544
00:22:57.011 --> 00:22:59.462
The project is structured as follows

545
00:22:59.462 --> 00:23:02.579
It supports both 2D and 3D data

546
00:23:02.579 --> 00:23:03.974
These two types of data

547
00:23:03.974 --> 00:23:06.206
have been set up for use

548
00:23:06.206 --> 00:23:09.071
First, let’s look at how 2D data is used

549
00:23:09.071 --> 00:23:10.732
to implement the KD-tree

550
00:23:10.732 --> 00:23:13.578
Let's take a look

551
00:23:13.578 --> 00:23:18.651
Scene 1 includes an insertion scene for building the KD-tree

552
00:23:18.651 --> 00:23:21.905
and a query scene for finding the nearest point

553
00:23:21.905 --> 00:23:24.930
These two parts make up the scene

554
00:23:24.930 --> 00:23:27.379
Let’s open the insertion scene first

555
00:23:27.379 --> 00:23:31.253
and discuss its implementation

556
00:23:31.253 --> 00:23:34.386
The overall structure of the scene

557
00:23:34.386 --> 00:23:36.280
is very similar to the examples provided in

558
00:23:36.280 --> 00:23:39.890
Understanding Spatial Division Algorithms 1

559
00:23:39.890 --> 00:23:41.916
A manager game object has been created

560
00:23:41.916 --> 00:23:44.855
to manage the KD-tree

561
00:23:44.855 --> 00:23:47.288
A component called "KDTree Manager"

562
00:23:47.288 --> 00:23:49.526
has been attached to it

563
00:23:49.526 --> 00:23:52.003
The KDTree Manager component

564
00:23:52.003 --> 00:23:54.933
sets the overall map size for visualizing the KD-tree

565
00:23:54.933 --> 00:23:57.114
It defines the total map size

566
00:23:57.114 --> 00:23:58.933
in this way

567
00:23:58.933 --> 00:24:00.993
Since this is a 2D setup

568
00:24:00.993 --> 00:24:04.451
the dimension value is set to 2

569
00:24:04.451 --> 00:24:07.520
Within this KDTree Manager component

570
00:24:07.520 --> 00:24:09.082
there are 9 objects

571
00:24:09.082 --> 00:24:11.210
positioned as child objects

572
00:24:11.210 --> 00:24:12.988
From 1 to 9,

573
00:24:12.988 --> 00:24:15.580
let’s examine the positions one by one

574
00:24:18.313 --> 00:24:20.345
These game objects

575
00:24:20.345 --> 00:24:23.640
each have a tag called "Insert" assigned to them

576
00:24:23.640 --> 00:24:25.435
Using this tag,

577
00:24:25.435 --> 00:24:28.374
the script identifies objects to insert

578
00:24:28.374 --> 00:24:31.161
in the designated order

579
00:24:31.161 --> 00:24:33.109
Now, let’s press the play button

580
00:24:34.869 --> 00:24:36.458
In the game view on the right

581
00:24:36.458 --> 00:24:38.494
clicking the insert button

582
00:24:38.494 --> 00:24:42.205
creates a KD-tree node to store the point

583
00:24:42.205 --> 00:24:44.121
and proceeds with spatial partitioning

584
00:24:44.121 --> 00:24:46.451
When we press the button to check

585
00:24:46.451 --> 00:24:49.020
the spatial partitioning begins

586
00:24:49.020 --> 00:24:53.024
Since the first point is assigned the x-axis

587
00:24:53.024 --> 00:24:55.987
the y-axis, which is orthogonal to the x-axis

588
00:24:55.987 --> 00:24:59.581
is used to divide the space into two regions

589
00:24:59.581 --> 00:25:01.530
In the second node,

590
00:25:01.530 --> 00:25:03.160
the depth increases by one level

591
00:25:03.160 --> 00:25:04.280
so at this point,

592
00:25:04.280 --> 00:25:08.094
the y-value is used again

593
00:25:08.094 --> 00:25:12.196
and the x-axis, orthogonal to the y-axis,

594
00:25:12.196 --> 00:25:14.671
is used for spatial partitioning

595
00:25:14.671 --> 00:25:17.571
As we continue to insert points one by one,

596
00:25:17.571 --> 00:25:20.909
the depth at which these points are located

597
00:25:20.909 --> 00:25:23.319
determines whether the axis

598
00:25:23.319 --> 00:25:26.314
is set to x or y

599
00:25:26.314 --> 00:25:29.144
Based on the assigned axis

600
00:25:29.144 --> 00:25:32.186
it decides whether to partition along the x-axis

601
00:25:32.186 --> 00:25:35.674
or the y-axis

602
00:25:35.674 --> 00:25:37.797
As shown here, one by one

603
00:25:37.797 --> 00:25:41.386
the spatial partitioning is carried out

604
00:25:41.386 --> 00:25:43.642
Now, let’s take a look at the code

605
00:25:43.642 --> 00:25:50.207
This code is located under the "Scripts" folder

606
00:25:50.207 --> 00:25:53.127
in a folder named "Kdtree"

607
00:25:53.127 --> 00:25:55.374
The scripts related to this KD-tree

608
00:25:55.374 --> 00:25:58.259
include KdtreeManager, Kdtree,

609
00:25:58.259 --> 00:26:01.121
and the node used in the KD-tree

610
00:26:01.121 --> 00:26:02.903
KNode, a total of three

611
00:26:02.903 --> 00:26:05.464
C# scripts

612
00:26:05.464 --> 00:26:08.207
Let’s first examine the KdtreeManager script

613
00:26:08.207 --> 00:26:09.266
and check it out

614
00:26:11.308 --> 00:26:13.453
The KdtreeManager script

615
00:26:13.453 --> 00:26:15.774
is designed to manage the KD-tree in Unity

616
00:26:15.774 --> 00:26:18.778
and is a custom-written C# script

617
00:26:18.778 --> 00:26:20.668
It functions as a Unity component

618
00:26:20.668 --> 00:26:23.993
by inheriting the MonoBehaviour class

619
00:26:23.993 --> 00:26:25.287
This script itself

620
00:26:25.287 --> 00:26:29.094
does not perform the actual KD-tree operations

621
00:26:29.094 --> 00:26:30.655
Instead, it interacts with Unity

622
00:26:30.655 --> 00:26:33.430
to handle input values

623
00:26:33.430 --> 00:26:35.826
and communicates with the KDTree class,

624
00:26:35.826 --> 00:26:39.544
which performs the actual KD-tree tasks

625
00:26:39.544 --> 00:26:42.404
That is its primary role

626
00:26:42.404 --> 00:26:43.990
Let’s examine the member variables

627
00:26:43.990 --> 00:26:46.420
of the KDTreeManager

628
00:26:46.420 --> 00:26:49.575
First, a member variable named dimension

629
00:26:49.575 --> 00:26:52.947
was declared to define the dimensions of the KD-tree

630
00:26:52.947 --> 00:26:56.213
This variable allows us to specify

631
00:26:56.213 --> 00:26:57.868
the number of dimensions the KD-tree will use

632
00:26:57.868 --> 00:27:00.371
It was designed with this purpose in mind

633
00:27:00.371 --> 00:27:03.127
Next, I’ll demonstrate two functionalities

634
00:27:03.127 --> 00:27:05.633
two functionalities

635
00:27:05.633 --> 00:27:08.895
the process of inserting objects

636
00:27:08.895 --> 00:27:11.747
to build the KD-tree,

637
00:27:11.747 --> 00:27:13.737
as shown in the "Insert Scenes,"

638
00:27:13.737 --> 00:27:16.403
and the process of finding

639
00:27:16.403 --> 00:27:19.305
the nearest point in the built KD-tree, called "Query Scenes"

640
00:27:19.305 --> 00:27:21.452
These two functionalities will be demonstrated

641
00:27:21.452 --> 00:27:24.819
Since these need to be displayed differently

642
00:27:24.819 --> 00:27:27.831
I declared a separate enumerator

643
00:27:27.831 --> 00:27:29.946
called KDrawMode

644
00:27:29.946 --> 00:27:32.489
This allows for distinct visual modes

645
00:27:32.489 --> 00:27:34.487
Next, to visualize the entire space

646
00:27:34.487 --> 00:27:35.838
I set up a bounding volume

647
00:27:35.838 --> 00:27:37.783
called drawArea

648
00:27:37.783 --> 00:27:40.802
This volume represents the overall area

649
00:27:40.802 --> 00:27:46.016
Additionally, a member variable for the actual

650
00:27:46.016 --> 00:27:48.878
KD-tree operations was also declared

651
00:27:48.878 --> 00:27:53.033
Next, to manage

652
00:27:53.033 --> 00:27:54.788
the insertion process

653
00:27:54.788 --> 00:27:57.598
an array of game objects

654
00:27:57.598 --> 00:28:00.182
tagged with "Insert"

655
00:28:00.182 --> 00:28:01.861
to track the inserted objects

656
00:28:01.861 --> 00:28:04.517
was declared

657
00:28:04.517 --> 00:28:07.535
When inserting objects step by step,

658
00:28:07.535 --> 00:28:12.023
the index of the currently inserted object

659
00:28:12.023 --> 00:28:14.712
is stored in

660
00:28:14.712 --> 00:28:15.737
a member variable called iIndex

661
00:28:15.737 --> 00:28:19.448
This iIndex variable was added

662
00:28:19.448 --> 00:28:22.514
The remaining variables below

663
00:28:22.514 --> 00:28:24.901
will be used in the query scene later,

664
00:28:24.901 --> 00:28:27.228
so I will explain them at that time

665
00:28:27.228 --> 00:28:29.432
Next, let’s look at the Awake function

666
00:28:29.432 --> 00:28:30.383
We will review it

667
00:28:30.383 --> 00:28:32.178
When the play button is pressed

668
00:28:32.178 --> 00:28:34.590
the Awake function will be executed

669
00:28:34.590 --> 00:28:37.684
At this point, a KD-tree object

670
00:28:37.684 --> 00:28:39.308
is created

671
00:28:39.308 --> 00:28:41.609
and the specified dimension value

672
00:28:41.609 --> 00:28:44.394
is passed as a constructor argument

673
00:28:44.394 --> 00:28:46.052
If it already exists

674
00:28:46.052 --> 00:28:48.149
it deletes all related data

675
00:28:48.149 --> 00:28:51.083
This is explicitly set in the process

676
00:28:51.083 --> 00:28:54.223
Next, it searches for tags

677
00:28:54.223 --> 00:28:56.669
to find the objects required

678
00:28:56.669 --> 00:28:59.936
for building the KD-tree

679
00:28:59.936 --> 00:29:02.517
using the FindGameObjectsWithTag

680
00:29:02.517 --> 00:29:05.330
API to retrieve them as an array

681
00:29:05.330 --> 00:29:06.870
Storing these objects

682
00:29:06.870 --> 00:29:09.841
completes the initialization process

683
00:29:11.028 --> 00:29:14.675
For the actual operations

684
00:29:14.675 --> 00:29:18.352
it uses the current insertion index

685
00:29:18.352 --> 00:29:20.087
and the Transform component

686
00:29:20.087 --> 00:29:21.808
that holds the position value

687
00:29:21.808 --> 00:29:24.586
The reference to the Transform component

688
00:29:24.586 --> 00:29:27.170
is passed as an argument

689
00:29:27.170 --> 00:29:31.222
to the Add function of the tree object

690
00:29:31.222 --> 00:29:34.016
to perform the insertion

691
00:29:34.016 --> 00:29:36.688
The NearestQuery function below

692
00:29:36.688 --> 00:29:38.535
is used during the query process

693
00:29:38.535 --> 00:29:41.052
so I will explain it later

694
00:29:41.052 --> 00:29:42.958
Next, the drawing process

695
00:29:42.958 --> 00:29:45.884
in the OnDrawGizmos function

696
00:29:45.884 --> 00:29:49.382
renders all node regions of the KD-tree

697
00:29:49.382 --> 00:29:51.283
in gray

698
00:29:51.283 --> 00:29:53.421
This is how the drawing regions are specified

699
00:29:53.421 --> 00:29:55.367
This represents the entire area

700
00:29:55.367 --> 00:29:57.945
Next, to show how the KD-tree

701
00:29:57.945 --> 00:30:01.387
is partitioned

702
00:30:01.387 --> 00:30:04.963
the KD-tree object

703
00:30:04.963 --> 00:30:08.878
starts from the root node

704
00:30:08.878 --> 00:30:12.790
drawing each divided line or plane

705
00:30:12.790 --> 00:30:14.888
The DrawSplitPlane function

706
00:30:14.888 --> 00:30:17.401
is called to handle the rendering

707
00:30:19.460 --> 00:30:22.676
For the Insert mode,

708
00:30:22.676 --> 00:30:25.868
it draws the area of the point to be inserted

709
00:30:25.868 --> 00:30:28.697
using the DrawCube function

710
00:30:30.238 --> 00:30:32.559
The sections below are related to queries,

711
00:30:32.559 --> 00:30:33.879
so I will explain them later

712
00:30:33.879 --> 00:30:35.864
I will cover this later

713
00:30:37.370 --> 00:30:39.717
Next,

714
00:30:39.717 --> 00:30:42.515
let’s examine the actual KD-tree construction

715
00:30:42.515 --> 00:30:44.418
and the KD-tree class

716
00:30:44.418 --> 00:30:45.950
I will explain this

717
00:30:49.143 --> 00:30:52.196
For the KD-tree

718
00:30:52.196 --> 00:30:55.223
a list variable was declared

719
00:30:55.223 --> 00:30:58.004
to store nodes

720
00:30:58.004 --> 00:31:00.471
in a List format

721
00:31:00.471 --> 00:31:03.276
To check the dimensions currently used

722
00:31:03.276 --> 00:31:05.355
by the KD-tree

723
00:31:05.355 --> 00:31:07.388
a variable called Dimension was added

724
00:31:07.388 --> 00:31:10.372
This takes the value declared in the manager

725
00:31:10.372 --> 00:31:13.821
via the constructor

726
00:31:13.821 --> 00:31:17.169
Additionally, the root object was specified

727
00:31:17.169 --> 00:31:20.020
to enable searching from the root node

728
00:31:20.020 --> 00:31:22.406
It was assigned as a member variable in the KD-tree

729
00:31:23.543 --> 00:31:26.736
Now let’s examine the key function

730
00:31:26.736 --> 00:31:28.968
the Add function

731
00:31:28.968 --> 00:31:31.049
As mentioned earlier, in KDTreeManager

732
00:31:31.049 --> 00:31:32.849
when performing Add

733
00:31:32.849 --> 00:31:35.591
the location value of a game object

734
00:31:35.591 --> 00:31:37.777
stored in the Transform component

735
00:31:37.777 --> 00:31:39.982
is passed as a reference

736
00:31:39.982 --> 00:31:42.595
When the reference of a Transform is received

737
00:31:42.595 --> 00:31:45.490
a new node is created

738
00:31:45.490 --> 00:31:46.998
based on the reference

739
00:31:46.998 --> 00:31:51.150
The binary tree is then built according to the rules

740
00:31:51.150 --> 00:31:54.855
If the root is null

741
00:31:54.855 --> 00:31:57.956
a new root node is created

742
00:31:57.956 --> 00:32:00.156
and added to the root node’s list

743
00:32:00.156 --> 00:32:01.985
It is immediately returned

744
00:32:01.985 --> 00:32:04.803
If the root is not null

745
00:32:04.803 --> 00:32:08.277
a suitable insertion position must be found

746
00:32:08.277 --> 00:32:12.489
The dimension value assigned to the node

747
00:32:12.489 --> 00:32:15.406
determines whether the newly inserted

748
00:32:15.406 --> 00:32:18.900
Transform value goes to the left node

749
00:32:18.900 --> 00:32:20.668
or the right node

750
00:32:20.668 --> 00:32:22.146
To determine this,

751
00:32:22.146 --> 00:32:24.915
the comparison logic in the if clause

752
00:32:24.915 --> 00:32:28.456
uses the GetkdValue function

753
00:32:28.456 --> 00:32:31.867
This function takes the depth of the node

754
00:32:31.867 --> 00:32:35.640
and the dimension value as arguments

755
00:32:35.640 --> 00:32:37.896
For convenience

756
00:32:37.896 --> 00:32:39.416
C#’s extension method feature

757
00:32:39.416 --> 00:32:43.079
was used to implement this function

758
00:32:43.079 --> 00:32:45.041
Before looking at the code

759
00:32:45.041 --> 00:32:47.370
the value being compared

760
00:32:47.370 --> 00:32:49.471
is not the entire dimension value

761
00:32:49.471 --> 00:32:52.939
but the dimension value assigned to the node

762
00:32:52.939 --> 00:32:55.387
This is determined based on the depth

763
00:32:55.387 --> 00:32:58.012
of the node, as explained earlier

764
00:32:58.012 --> 00:32:59.674
The total number of dimensions

765
00:32:59.674 --> 00:33:01.385
handled by the current KD-tree

766
00:33:01.385 --> 00:33:03.170
is stored in the Dimension member variable

767
00:33:03.170 --> 00:33:04.785
as can be seen

768
00:33:04.785 --> 00:33:07.139
The depth of the node to compare

769
00:33:07.139 --> 00:33:09.620
is given as the depth value

770
00:33:09.620 --> 00:33:11.093
Initially, this depth value

771
00:33:11.093 --> 00:33:12.986
starts at the root node,

772
00:33:12.986 --> 00:33:14.619
so it is 0

773
00:33:14.619 --> 00:33:16.834
Every time the while loop runs

774
00:33:16.834 --> 00:33:18.906
the depth increases by one

775
00:33:18.906 --> 00:33:20.457
In any case, with the depth value

776
00:33:20.457 --> 00:33:22.532
and the Dimension value

777
00:33:22.532 --> 00:33:26.051
we can determine

778
00:33:26.051 --> 00:33:28.786
which dimension value to use

779
00:33:28.786 --> 00:33:32.319
from the Transform position

780
00:33:32.319 --> 00:33:36.233
As explained earlier,

781
00:33:36.233 --> 00:33:37.465
this value can be calculated

782
00:33:37.465 --> 00:33:40.564
using the modulo operation

783
00:33:40.564 --> 00:33:42.673
Let’s scroll up to see

784
00:33:42.673 --> 00:33:44.676
the implemented extension method

785
00:33:44.676 --> 00:33:47.981
In the GetkdValue function

786
00:33:47.981 --> 00:33:51.620
when the Transform, dimension, and depth values

787
00:33:51.620 --> 00:33:53.661
are provided

788
00:33:53.661 --> 00:33:57.791
the current position value of the Transform

789
00:33:57.791 --> 00:34:00.550
is calculated by determining

790
00:34:00.550 --> 00:34:02.600
which indexed dimension value

791
00:34:02.600 --> 00:34:06.521
is derived by using the depth

792
00:34:06.521 --> 00:34:09.054
and the modulo operation

793
00:34:09.054 --> 00:34:11.715
to get the index

794
00:34:11.715 --> 00:34:13.913
This index is then applied

795
00:34:13.913 --> 00:34:16.193
to retrieve the value using array indexing

796
00:34:16.193 --> 00:34:20.311
Returning to the earlier code

797
00:34:20.311 --> 00:34:22.592
the dimension value retrieved

798
00:34:22.592 --> 00:34:26.085
for the current depth of the Transform

799
00:34:26.085 --> 00:34:28.760
is then compared with

800
00:34:28.760 --> 00:34:31.228
the dimension value of the node

801
00:34:31.228 --> 00:34:33.132
in the same manner

802
00:34:33.132 --> 00:34:35.482
Here, the property kdValue

803
00:34:35.482 --> 00:34:38.267
is designed to retrieve it

804
00:34:38.267 --> 00:34:41.249
If you press F12

805
00:34:41.249 --> 00:34:43.269
you can check the implementation

806
00:34:43.269 --> 00:34:46.583
The Transform assigned to the current node

807
00:34:46.583 --> 00:34:47.964
the total dimension values

808
00:34:47.964 --> 00:34:50.337
and the depth value of the current node

809
00:34:50.337 --> 00:34:52.863
these three are used

810
00:34:52.863 --> 00:34:55.344
to calculate the dimension value to retrieve

811
00:34:55.344 --> 00:34:57.662
It returns this value

812
00:34:57.662 --> 00:35:02.251
Press Ctrl+- to return to the original view

813
00:35:02.251 --> 00:35:03.591
The two dimension values obtained in this way

814
00:35:03.591 --> 00:35:06.240
are compared

815
00:35:06.240 --> 00:35:09.799
If the value is smaller and the left node is available

816
00:35:09.799 --> 00:35:12.186
it is added to the left node

817
00:35:12.186 --> 00:35:15.624
If a node already exists in the left

818
00:35:15.624 --> 00:35:19.206
you go in another level

819
00:35:19.206 --> 00:35:21.149
and the process repeats

820
00:35:21.149 --> 00:35:23.897
If the same value is encountered

821
00:35:23.897 --> 00:35:25.504
nodes with identical values

822
00:35:25.504 --> 00:35:27.798
cannot be added

823
00:35:27.798 --> 00:35:31.678
An error is returned in such cases

824
00:35:31.678 --> 00:35:34.886
The same logic applies to the right node

825
00:35:34.886 --> 00:35:37.927
If the right node is available,

826
00:35:37.927 --> 00:35:40.006
the node is added to the right

827
00:35:40.006 --> 00:35:42.218
If there are children in the right node

828
00:35:42.218 --> 00:35:44.201
the depth is incremented

829
00:35:44.201 --> 00:35:46.021
and the loop continues

830
00:35:46.021 --> 00:35:48.004
The loop iterates accordingly

831
00:35:48.004 --> 00:35:52.287
This covers the addition logic

832
00:35:52.287 --> 00:35:54.475
Next, let’s look at the class

833
00:35:54.475 --> 00:35:58.134
that constructs the KD-tree: KNode

834
00:35:58.134 --> 00:36:01.758
The KNode class, upon declaration

835
00:36:01.758 --> 00:36:04.227
contains a reference

836
00:36:04.227 --> 00:36:05.912
to store its position via a Transform

837
00:36:05.912 --> 00:36:07.675
It also contains the depth value

838
00:36:07.675 --> 00:36:10.324
the depth of the current node

839
00:36:10.324 --> 00:36:12.867
and the total dimension value

840
00:36:12.867 --> 00:36:17.692
This value is set for the KD-tree

841
00:36:17.692 --> 00:36:19.282
There is also a reference to the parent,

842
00:36:19.282 --> 00:36:20.995
although it’s not used practically

843
00:36:20.995 --> 00:36:23.181
I added it for potential use

844
00:36:23.181 --> 00:36:25.814
Next are references

845
00:36:25.814 --> 00:36:27.760
to the left and right child nodes

846
00:36:27.760 --> 00:36:29.925
These are included in the design

847
00:36:29.925 --> 00:36:32.221
The drawing-related part

848
00:36:32.221 --> 00:36:34.248
will be explained later

849
00:36:34.248 --> 00:36:36.193
At the very bottom

850
00:36:36.193 --> 00:36:38.166
the most crucial part previously explained

851
00:36:38.166 --> 00:36:40.285
is how the kdValue is retrieved

852
00:36:40.285 --> 00:36:41.864
This was explained

853
00:36:41.864 --> 00:36:43.977
Going further up,

854
00:36:43.977 --> 00:36:46.355
there are references for the left node

855
00:36:46.355 --> 00:36:49.136
the right node

856
00:36:49.136 --> 00:36:51.837
and checks for whether the left

857
00:36:51.837 --> 00:36:53.602
or right nodes are empty

858
00:36:53.602 --> 00:36:57.153
These are properties

859
00:36:57.153 --> 00:36:59.872
declared for such evaluations

860
00:36:59.872 --> 00:37:03.521
Internally, there isn't any special logic implemented

861
00:37:03.521 --> 00:37:06.501
What you need to note here is

862
00:37:06.501 --> 00:37:08.711
that using the depth and dimension values

863
00:37:08.711 --> 00:37:10.853
the AABB areas of the left and right nodes

864
00:37:10.853 --> 00:37:12.797
are drawn

865
00:37:12.797 --> 00:37:15.048
through a function called DrawSplitPlane

866
00:37:15.048 --> 00:37:16.640
I implemented this function

867
00:37:16.640 --> 00:37:18.823
This is recursively set up so that

868
00:37:18.823 --> 00:37:23.520
if there is a left child, depth-first

869
00:37:23.520 --> 00:37:25.357
drawing is continuously performed

870
00:37:25.357 --> 00:37:27.496
For nodes set as right children

871
00:37:27.496 --> 00:37:29.802
the areas of all such nodes are also drawn

872
00:37:29.802 --> 00:37:31.708
in this implementation

873
00:37:31.708 --> 00:37:34.685
By adding objects one by one

874
00:37:34.685 --> 00:37:37.520
I explained how the KD-tree

875
00:37:37.520 --> 00:37:38.553
 is constructed and

876
00:37:38.553 --> 00:37:40.705
the code for drawing each divided area

877
00:37:40.705 --> 00:37:43.186
was also explained

878
00:37:43.186 --> 00:37:45.404
Next, let’s look into how to find

879
00:37:45.404 --> 00:37:47.514
the nearest node

880
00:37:47.514 --> 00:37:50.675
using the query feature

881
00:37:50.675 --> 00:37:52.899
Returning to the Unity project

882
00:37:52.899 --> 00:37:56.241
this time, let's open the Query Scenes

883
00:37:56.241 --> 00:37:58.770
and give it a command

884
00:37:58.770 --> 00:38:00.090
In the Query Scenes,

885
00:38:00.090 --> 00:38:02.129
the setup is slightly different

886
00:38:02.129 --> 00:38:05.738
There are 9 objects to be inserted

887
00:38:05.738 --> 00:38:07.850
along with

888
00:38:07.850 --> 00:38:11.259
3 objects that determine the nearest points

889
00:38:11.259 --> 00:38:14.007
These were specified accordingly

890
00:38:14.007 --> 00:38:15.455
Press the play button

891
00:38:15.455 --> 00:38:17.654
to see it in action

892
00:38:17.654 --> 00:38:20.375
When the play button is pressed

893
00:38:20.375 --> 00:38:22.712
all 9 objects

894
00:38:22.712 --> 00:38:24.481
are inserted

895
00:38:24.481 --> 00:38:28.288
and the KD-tree is already complete

896
00:38:28.288 --> 00:38:32.637
At this point, for the first object,

897
00:38:32.637 --> 00:38:35.671
it is marked in red

898
00:38:35.671 --> 00:38:38.130
The nearest object

899
00:38:38.130 --> 00:38:39.978
is actually this point

900
00:38:39.978 --> 00:38:41.649
We can verify this

901
00:38:41.649 --> 00:38:43.752
While this is easy to see visually

902
00:38:43.752 --> 00:38:45.814
if there is a large amount of data

903
00:38:45.814 --> 00:38:47.696
or a situation where visuals are unavailable

904
00:38:47.696 --> 00:38:50.534
it would be difficult to identify

905
00:38:50.534 --> 00:38:51.935
So by pressing the button

906
00:38:51.935 --> 00:38:54.345
you can confirm whether it correctly finds

907
00:38:54.345 --> 00:38:56.512
the nearest object

908
00:38:56.512 --> 00:38:59.195
We can see that it is able to correctly find it

909
00:38:59.195 --> 00:39:02.672
For the second object,

910
00:39:02.672 --> 00:39:05.801
the nearest object should be this one

911
00:39:05.801 --> 00:39:07.770
Press the button to check

912
00:39:07.770 --> 00:39:11.259
For the third case as well, pressing the button

913
00:39:11.259 --> 00:39:13.454
shows that it is correctly found

914
00:39:13.454 --> 00:39:15.070
Additionally,

915
00:39:15.070 --> 00:39:16.223
what you should confirm is

916
00:39:16.223 --> 00:39:18.420
how many nodes in the tree

917
00:39:18.420 --> 00:39:20.274
were traversed during the search

918
00:39:20.274 --> 00:39:23.164
If the KD-tree wasn’t used

919
00:39:23.164 --> 00:39:24.994
all 9 objects

920
00:39:24.994 --> 00:39:26.781
would have to be compared

921
00:39:26.781 --> 00:39:31.589
However, by using the constructed KD-tree

922
00:39:31.589 --> 00:39:33.388
the search process

923
00:39:33.388 --> 00:39:35.399
for the first case

924
00:39:35.399 --> 00:39:37.039
let’s run it again

925
00:39:37.039 --> 00:39:39.670
for the first case

926
00:39:39.670 --> 00:39:42.164
Only 4 nodes were traversed

927
00:39:42.164 --> 00:39:44.848
to find the nearest object

928
00:39:44.848 --> 00:39:46.989
For the second case, 5 nodes

929
00:39:46.989 --> 00:39:49.879
For the third case, 7 nodes were traversed

930
00:39:49.879 --> 00:39:52.935
to find the nearest object

931
00:39:52.935 --> 00:39:56.391
Now let’s look at how the query feature

932
00:39:56.391 --> 00:39:58.821
was implemented through the code

933
00:40:00.286 --> 00:40:02.034
In KDTreeManager

934
00:40:02.034 --> 00:40:05.235
I will explain only the parts related to the query functionality

935
00:40:05.235 --> 00:40:07.935
During the initialization of KDTreeManager

936
00:40:07.935 --> 00:40:10.055
in the Awake function,

937
00:40:10.055 --> 00:40:12.225
if it is set to Query

938
00:40:12.225 --> 00:40:14.367
it calls InsertAll

939
00:40:14.367 --> 00:40:16.419
to add all objects

940
00:40:16.419 --> 00:40:18.971
You can see this being called

941
00:40:18.971 --> 00:40:22.671
To find the nearest object

942
00:40:22.671 --> 00:40:24.165
the NearestQuery function

943
00:40:24.165 --> 00:40:26.137
of the KD-tree object

944
00:40:26.137 --> 00:40:28.055
is invoked

945
00:40:29.441 --> 00:40:33.165
When calling NearestQuery

946
00:40:33.165 --> 00:40:34.584
a list object called searchedNodes

947
00:40:34.584 --> 00:40:36.660
is passed

948
00:40:36.660 --> 00:40:38.828
to keep track of how many nodes

949
00:40:38.828 --> 00:40:40.930
were traversed in the current tree structure

950
00:40:40.930 --> 00:40:42.389
This allows us to check

951
00:40:42.389 --> 00:40:45.729
by passing a reference parameter

952
00:40:45.729 --> 00:40:48.374
The number of traversed nodes

953
00:40:48.374 --> 00:40:49.749
is counted

954
00:40:49.749 --> 00:40:51.568
through additional functionality

955
00:40:52.827 --> 00:40:55.168
In the OnDrawGizmo function,

956
00:40:55.168 --> 00:40:57.265
the tree area drawing

957
00:40:57.265 --> 00:41:00.846
is performed similarly to the insertion feature

958
00:41:00.846 --> 00:41:03.690
Query objects are drawn in red

959
00:41:03.690 --> 00:41:06.969
and already queried objects

960
00:41:06.969 --> 00:41:09.430
are drawn in yellow

961
00:41:09.430 --> 00:41:12.031
Additionally, queried objects

962
00:41:12.031 --> 00:41:14.364
and their nearest objects

963
00:41:14.364 --> 00:41:16.959
are marked in purple

964
00:41:16.959 --> 00:41:20.796
A line between the queried object

965
00:41:20.796 --> 00:41:23.423
and its nearest object is also drawn

966
00:41:23.423 --> 00:41:26.335
Now, let's take a look at

967
00:41:26.335 --> 00:41:29.229
the NearestQuery function of the KD-tree,

968
00:41:29.229 --> 00:41:31.270
to see how it is implemented

969
00:41:31.270 --> 00:41:34.869
Press the F12 key to inspect it

970
00:41:34.869 --> 00:41:37.945
In the case of the NearestQuery function,

971
00:41:37.945 --> 00:41:40.038
it doesn’t do much directly here

972
00:41:40.038 --> 00:41:42.372
The KD-tree itself doesn’t handle it here

973
00:41:42.372 --> 00:41:45.488
Instead, it recursively calls the

974
00:41:45.488 --> 00:41:47.214
CheckNearestNode function

975
00:41:47.214 --> 00:41:48.975
on the root node,

976
00:41:48.975 --> 00:41:51.427
using depth-first search

977
00:41:51.427 --> 00:41:53.837
to find the nearest node

978
00:41:53.837 --> 00:41:55.732
This is how the logic is designed

979
00:41:55.732 --> 00:41:57.165
Similarly here,

980
00:41:57.165 --> 00:41:59.465
we can press F12

981
00:41:59.465 --> 00:42:02.474
to see how it’s implemented

982
00:42:02.474 --> 00:42:05.245
This function takes the following inputs

983
00:42:05.245 --> 00:42:07.262
a testTransform parameter for the point to compare

984
00:42:07.262 --> 00:42:09.490
the currently

985
00:42:09.490 --> 00:42:11.767
closest node identified so far

986
00:42:11.767 --> 00:42:14.591
and information about the nearest node

987
00:42:14.591 --> 00:42:17.114
to pass as an argument

988
00:42:17.114 --> 00:42:18.800
Additionally,

989
00:42:18.800 --> 00:42:20.888
to track the traversed nodes,

990
00:42:20.888 --> 00:42:23.665
a list reference

991
00:42:23.665 --> 00:42:27.065
created in the previous manager class

992
00:42:27.065 --> 00:42:29.453
is passed as the third argument

993
00:42:29.453 --> 00:42:31.355
Upon visiting a node

994
00:42:31.355 --> 00:42:34.585
this list reference

995
00:42:34.585 --> 00:42:36.472
is used to store

996
00:42:36.472 --> 00:42:38.135
information about the current node

997
00:42:38.135 --> 00:42:39.447
at the beginning of the function

998
00:42:39.447 --> 00:42:42.776
Then, the currently known shortest distance

999
00:42:42.776 --> 00:42:46.131
from the second argument

1000
00:42:46.131 --> 00:42:48.719
is measured

1001
00:42:48.719 --> 00:42:50.458
to determine

1002
00:42:50.458 --> 00:42:54.147
and compared with the distance to the current node

1003
00:42:54.147 --> 00:42:58.069
This determines which node is closer

1004
00:42:58.069 --> 00:43:01.186
If the current node being visited

1005
00:43:01.186 --> 00:43:03.046
is closer,

1006
00:43:03.046 --> 00:43:04.393
it becomes

1007
00:43:04.393 --> 00:43:06.166
the nearest node so far

1008
00:43:07.313 --> 00:43:10.290
If the current node is

1009
00:43:10.290 --> 00:43:14.316
a leaf node at the very end

1010
00:43:14.316 --> 00:43:16.497
no further search is necessary

1011
00:43:16.497 --> 00:43:19.821
The current node is returned

1012
00:43:19.821 --> 00:43:22.022
as the nearest node

1013
00:43:22.022 --> 00:43:24.465
Otherwise,

1014
00:43:24.465 --> 00:43:26.200
the search continues

1015
00:43:26.200 --> 00:43:28.771
There might be a closer node

1016
00:43:28.771 --> 00:43:31.424
in the child nodes

1017
00:43:31.424 --> 00:43:34.990
so a variable named NearestNodeSofar

1018
00:43:34.990 --> 00:43:36.460
is used to store

1019
00:43:36.460 --> 00:43:39.267
the information about the closest node

1020
00:43:39.267 --> 00:43:42.526
found so far, including the current node

1021
00:43:42.526 --> 00:43:43.869
Next,

1022
00:43:43.869 --> 00:43:46.222
a depth-first search is performed

1023
00:43:46.222 --> 00:43:50.212
Before that, it’s useful to calculate

1024
00:43:50.212 --> 00:43:53.904
the shortest distance to the non-overlapping region

1025
00:43:53.904 --> 00:43:56.488
either the left or right region

1026
00:43:56.488 --> 00:43:59.163
This distance

1027
00:43:59.163 --> 00:44:00.670
should be calculated in advance

1028
00:44:00.670 --> 00:44:03.399
To achieve this

1029
00:44:03.399 --> 00:44:06.789
the dimension value set in the current node

1030
00:44:06.789 --> 00:44:10.962
is measured to calculate the shortest distance

1031
00:44:10.962 --> 00:44:13.771
For example, if it’s on the right

1032
00:44:13.771 --> 00:44:16.469
it’s the shortest distance to the left region

1033
00:44:16.469 --> 00:44:18.029
If it’s on the left,

1034
00:44:18.029 --> 00:44:20.903
it’s the shortest distance to the right region

1035
00:44:20.903 --> 00:44:23.627
To compare these,

1036
00:44:23.627 --> 00:44:26.433
the distance is intentionally squared

1037
00:44:26.433 --> 00:44:29.091
This is because, when calculating the distance

1038
00:44:29.091 --> 00:44:32.098
we use a function called SquareDistanceTo

1039
00:44:32.098 --> 00:44:34.234
The reason for using this function

1040
00:44:34.234 --> 00:44:36.791
can be seen by pressing F12

1041
00:44:36.791 --> 00:44:39.731
It subtracts the position

1042
00:44:39.731 --> 00:44:41.699
of the node to compare

1043
00:44:41.699 --> 00:44:43.305
from the target position

1044
00:44:43.305 --> 00:44:46.231
to create a vector and uses the squared magnitude

1045
00:44:46.231 --> 00:44:47.533
As noted in the comments,

1046
00:44:47.533 --> 00:44:48.659
for performance optimization

1047
00:44:48.659 --> 00:44:51.651
a square root is intentionally not applied

1048
00:44:51.651 --> 00:44:54.142
Since comparisons are made with these values

1049
00:44:54.142 --> 00:44:57.244
distances are squared intentionally

1050
00:44:57.244 --> 00:45:00.487
The squared distance is calculated

1051
00:45:00.487 --> 00:45:03.243
and used in subsequent logic

1052
00:45:03.243 --> 00:45:06.399
Similar to the previous logic

1053
00:45:06.399 --> 00:45:09.240
the dimension value set in the current node

1054
00:45:09.240 --> 00:45:12.781
is compared; if smaller, it moves left

1055
00:45:12.781 --> 00:45:15.200
and if larger, it moves right

1056
00:45:15.200 --> 00:45:18.229
If it goes left first

1057
00:45:18.229 --> 00:45:21.056
it continues depth-first search

1058
00:45:21.056 --> 00:45:23.711
The CheckNearestNode function is

1059
00:45:23.711 --> 00:45:25.030
recursively called

1060
00:45:25.030 --> 00:45:27.769
to find the nearest node

1061
00:45:27.769 --> 00:45:30.676
from the left node

1062
00:45:30.676 --> 00:45:32.317
The distance to the nearest node

1063
00:45:32.317 --> 00:45:34.785
is then retrieved

1064
00:45:34.785 --> 00:45:37.701
This becomes the shortest distance within the region I'm located in

1065
00:45:37.701 --> 00:45:40.898
Within the area containing the point

1066
00:45:40.898 --> 00:45:43.488
I am comparing

1067
00:45:43.488 --> 00:45:46.490
However, there could be a shorter distance

1068
00:45:46.490 --> 00:45:49.464
in the right-hand region as well

1069
00:45:49.464 --> 00:45:52.528
Therefore, to account for that possibility

1070
00:45:52.528 --> 00:45:54.816
we also need to perform a depth-first traversal

1071
00:45:54.816 --> 00:45:57.157
on the right-hand side

1072
00:45:57.157 --> 00:46:02.149
If the currently measured shortest distance

1073
00:46:02.149 --> 00:46:05.208
is greater than the shortest distance to the opposite region

1074
00:46:05.208 --> 00:46:06.327
Which would be the right-hand side

1075
00:46:06.327 --> 00:46:10.802
If the shortest distance to the right-hand side is shorter

1076
00:46:10.802 --> 00:46:13.092
It is possible that a closer node

1077
00:46:13.092 --> 00:46:16.209
exists on the right

1078
00:46:16.209 --> 00:46:18.966
In such cases, the right child must also be

1079
00:46:18.966 --> 00:46:21.334
recursively explored

1080
00:46:21.334 --> 00:46:24.775
If the shortest distance to the right-hand region

1081
00:46:24.775 --> 00:46:28.555
is greater than the current shortest distance measured

1082
00:46:28.555 --> 00:46:31.755
the right side does not need to be searched

1083
00:46:31.755 --> 00:46:33.305
You can skip it

1084
00:46:34.766 --> 00:46:36.851
Similarly, for the right-hand side

1085
00:46:36.851 --> 00:46:38.464
proceed in the same manner

1086
00:46:38.464 --> 00:46:42.411
Recursively search through the right node

1087
00:46:42.411 --> 00:46:44.825
and measure the shortest distance

1088
00:46:44.825 --> 00:46:48.581
If the shortest distance to the left-hand region

1089
00:46:48.581 --> 00:46:51.356
is shorter than the shortest distance

1090
00:46:51.356 --> 00:46:53.724
I have currently measured

1091
00:46:53.724 --> 00:46:55.956
there is a possibility of a closer point on the left-hand side

1092
00:46:55.956 --> 00:46:57.497
Because there is such a possibility

1093
00:46:57.497 --> 00:47:00.039
the left side should also be

1094
00:47:00.039 --> 00:47:03.173
recursively explored as well

1095
00:47:03.173 --> 00:47:05.477
The KD-tree uses this logic

1096
00:47:05.477 --> 00:47:08.986
to identify the closest point

1097
00:47:08.986 --> 00:47:13.135
When executed, in some cases,

1098
00:47:13.135 --> 00:47:16.048
it traverses very few nodes to find the closest point

1099
00:47:16.048 --> 00:47:18.638
While in other cases

1100
00:47:18.638 --> 00:47:21.804
it may operate inefficiently

1101
00:47:21.804 --> 00:47:23.998
Traversing nearly all nodes

1102
00:47:23.998 --> 00:47:27.250
to find the closest node

1103
00:47:27.250 --> 00:47:28.547
Next,

1104
00:47:28.547 --> 00:47:30.455
using 3D data

1105
00:47:30.455 --> 00:47:33.396
we’ll examine how the KD-tree has been constructed

1106
00:47:33.396 --> 00:47:35.125
by viewing the screen

1107
00:47:35.125 --> 00:47:36.979
Under the Scenes folder,

1108
00:47:36.979 --> 00:47:41.053
go to the folder labeled K3dtree

1109
00:47:41.053 --> 00:47:43.024
After you run

1110
00:47:43.024 --> 00:47:44.486
the K3dtreeInsert Sceness file

1111
00:47:44.486 --> 00:47:45.992
disable the 2D option

1112
00:47:45.992 --> 00:47:49.750
and switch to the 3D option

1113
00:47:49.750 --> 00:47:52.918
In this state, press the play button

1114
00:47:54.549 --> 00:47:56.766
Inside the KDTreeManager

1115
00:47:56.766 --> 00:47:58.635
there is 3D spatial data

1116
00:47:58.635 --> 00:48:00.645
containing a total of 9 entries

1117
00:48:00.645 --> 00:48:03.083
As we add them one by one

1118
00:48:03.083 --> 00:48:04.585
the volume in this 3D space

1119
00:48:04.585 --> 00:48:07.497
we can observe how it is partitioned

1120
00:48:11.261 --> 00:48:15.180
As you can see, using nearly identical principles

1121
00:48:15.180 --> 00:48:17.609
the 3D space is divided into two sections

1122
00:48:17.609 --> 00:48:19.371
through a single plane

1123
00:48:19.371 --> 00:48:21.921
You can confirm this

1124
00:48:21.921 --> 00:48:23.879
The KDTreeManager component currently used

1125
00:48:23.879 --> 00:48:26.314
 in Scenes

1126
00:48:26.314 --> 00:48:28.682
is the same as the one used for

1127
00:48:28.682 --> 00:48:30.563
2D data

1128
00:48:30.563 --> 00:48:32.550
Except that the Dimension value

1129
00:48:32.550 --> 00:48:35.322
has been changed from 2 to 3

1130
00:48:35.322 --> 00:48:36.585
Thus, if we

1131
00:48:36.585 --> 00:48:39.392
properly implement the KD-tree

1132
00:48:39.392 --> 00:48:42.735
we will be able to construct a KD tree

1133
00:48:42.735 --> 00:48:46.456
that operates universally in N-dimensional spaces

1134
00:48:46.456 --> 00:48:49.179
Next, let’s examine the second prepared Query Scenes

1135
00:48:49.179 --> 00:48:51.252
Let's take a look

1136
00:48:51.252 --> 00:48:53.915
Likewise, pressing the play button

1137
00:48:53.915 --> 00:48:55.832
will add all objects with the Insert tag

1138
00:48:55.832 --> 00:48:57.300
to the KD-tree

1139
00:48:57.300 --> 00:48:59.639
All of them will be added

1140
00:49:01.424 --> 00:49:05.018
Here, three pre-prepared points

1141
00:49:05.018 --> 00:49:07.291
for each of the points

1142
00:49:07.291 --> 00:49:10.844
looking for the closest nodes

1143
00:49:10.844 --> 00:49:12.603
When we execute the logic

1144
00:49:12.603 --> 00:49:14.443
we can confirm that in 3D space as well

1145
00:49:14.443 --> 00:49:17.255
it operates correctly

1146
00:49:18.518 --> 00:49:22.387
The Overview and Functionality of BSP Trees

1147
00:49:22.387 --> 00:49:25.883
Let’s first review the overview of BSP trees

1148
00:49:25.883 --> 00:49:29.349
The term BSP stands for Binary Space Partitioning

1149
00:49:29.349 --> 00:49:31.504
Binary Space Partitioning

1150
00:49:31.504 --> 00:49:33.170
It’s an abbreviation

1151
00:49:33.170 --> 00:49:36.850
It involves dividing a given space into two parts

1152
00:49:36.850 --> 00:49:38.422
and storing it in a tree structure

1153
00:49:38.422 --> 00:49:39.441
as a binary tree, right?

1154
00:49:39.441 --> 00:49:41.208
Storing it in a binary tree structure

1155
00:49:41.208 --> 00:49:44.149
to perform effective searches

1156
00:49:44.149 --> 00:49:45.810
It is a collective term for this technique

1157
00:49:47.084 --> 00:49:50.362
This method became famous

1158
00:49:50.362 --> 00:49:53.961
during the development of the classic game Doom

1159
00:49:53.961 --> 00:49:56.751
As shown on the left side here

1160
00:49:56.751 --> 00:49:58.831
when rendering a specific level

1161
00:49:58.831 --> 00:50:02.325
there was a significant slowdown problem

1162
00:50:02.325 --> 00:50:05.237
At that time, developers used BSP trees

1163
00:50:05.237 --> 00:50:07.136
to resolve the slowdown issue

1164
00:50:07.136 --> 00:50:09.829
and render levels effectively

1165
00:50:09.829 --> 00:50:12.393
After Doom, it was widely used

1166
00:50:12.393 --> 00:50:14.220
in the development of various games

1167
00:50:14.220 --> 00:50:17.731
The BSP tree can be utilized in various ways

1168
00:50:17.731 --> 00:50:19.227
As shown here

1169
00:50:19.227 --> 00:50:22.819
it can divide a 3D space level

1170
00:50:22.819 --> 00:50:24.715
by removing hidden surfaces

1171
00:50:24.715 --> 00:50:28.135
also known as hidden surfaces

1172
00:50:28.135 --> 00:50:30.762
By detecting the parts where hidden surfaces are removed

1173
00:50:30.762 --> 00:50:34.739
it is used to render effectively

1174
00:50:34.739 --> 00:50:36.689
Alternatively, in a 3D space

1175
00:50:36.689 --> 00:50:38.729
it is used for detecting collisions of half-lines

1176
00:50:38.729 --> 00:50:42.674
that is, by pre-exploring movement paths

1177
00:50:42.674 --> 00:50:44.202
to check if the character and a wall

1178
00:50:44.202 --> 00:50:46.685
will collide or not

1179
00:50:46.685 --> 00:50:49.664
This logic is also implemented using BSP trees

1180
00:50:49.664 --> 00:50:51.538
Furthermore, the BSP tree

1181
00:50:51.538 --> 00:50:53.523
can divide given terrain data

1182
00:50:53.523 --> 00:50:55.652
to create specific volume shapes

1183
00:50:55.652 --> 00:50:56.844
This is another application of BSP trees

1184
00:50:57.898 --> 00:51:00.647
To construct such a BSP tree

1185
00:51:00.647 --> 00:51:02.493
a plane must be defined

1186
00:51:02.493 --> 00:51:04.504
to divide the space into two

1187
00:51:04.504 --> 00:51:06.632
When this plane is defined,

1188
00:51:06.632 --> 00:51:08.244
the space is split

1189
00:51:08.244 --> 00:51:10.896
into two regions by the plane

1190
00:51:10.896 --> 00:51:12.758
The given terrain

1191
00:51:12.758 --> 00:51:15.367
is divided into the front and back parts

1192
00:51:15.367 --> 00:51:18.116
If any object spans the plane, it is split into two parts

1193
00:51:18.116 --> 00:51:20.815
This results in the space being split into two regions

1194
00:51:20.815 --> 00:51:22.916
These separated spaces are recursively

1195
00:51:22.916 --> 00:51:24.404
split further,

1196
00:51:24.404 --> 00:51:26.266
forming a binary tree

1197
00:51:26.266 --> 00:51:28.340
This is how it is designed

1198
00:51:28.340 --> 00:51:30.355
While forming the binary tree

1199
00:51:30.355 --> 00:51:32.691
if the following conditions are met

1200
00:51:32.691 --> 00:51:34.706
the process is designed to stop

1201
00:51:34.706 --> 00:51:38.387
If the number of polygons in the smallest node

1202
00:51:38.387 --> 00:51:40.440
is less than a specified value

1203
00:51:40.440 --> 00:51:42.633
or, depending on the situation

1204
00:51:42.633 --> 00:51:45.223
various other conditions can be applied

1205
00:51:45.223 --> 00:51:49.673
If the shape contained in the smallest node is convex

1206
00:51:49.673 --> 00:51:54.280
meaning it has no overlapping visibility

1207
00:51:54.280 --> 00:51:56.760
the splitting can be stopped here

1208
00:51:56.760 --> 00:51:59.334
If the depth of the constructed tree

1209
00:51:59.334 --> 00:52:02.055
reaches the specified maximum value

1210
00:52:02.055 --> 00:52:03.823
the process can also stop

1211
00:52:03.823 --> 00:52:05.458
Alternatively, if a suitable plane

1212
00:52:05.458 --> 00:52:07.560
to split the space cannot be found

1213
00:52:07.560 --> 00:52:09.019
the process can be stopped

1214
00:52:09.019 --> 00:52:11.730
The methods for constructing such BSP trees

1215
00:52:11.730 --> 00:52:14.791
are highly complex and varied

1216
00:52:14.791 --> 00:52:17.369
making it difficult to explain simply

1217
00:52:17.369 --> 00:52:18.909
However, as you can see here

1218
00:52:18.909 --> 00:52:21.585
when a rectangular space is given

1219
00:52:21.585 --> 00:52:24.148
a plane is defined

1220
00:52:24.148 --> 00:52:26.530
and this plane is set up

1221
00:52:26.530 --> 00:52:29.615
to divide the space into positive and negative directions

1222
00:52:29.615 --> 00:52:32.784
separating it into left and right regions

1223
00:52:32.784 --> 00:52:35.098
Then, in the divided plane

1224
00:52:35.098 --> 00:52:37.619
a new plane is defined again

1225
00:52:37.619 --> 00:52:41.719
Thus, the positive and negative directions are determined

1226
00:52:41.719 --> 00:52:44.149
and in the negative region, another new plane is defined

1227
00:52:44.149 --> 00:52:47.097
separating the positive and negative regions further

1228
00:52:47.097 --> 00:52:49.701
This creates a binary tree

1229
00:52:49.701 --> 00:52:51.866
as shown on the screen

1230
00:52:51.866 --> 00:52:54.770
So, by using this BSP tree

1231
00:52:54.770 --> 00:52:57.072
how rendering is implemented

1232
00:52:57.072 --> 00:52:59.591
can be roughly explained

1233
00:52:59.591 --> 00:53:01.903
I will explain now

1234
00:53:01.903 --> 00:53:03.729
Here, there is a certain level

1235
00:53:03.729 --> 00:53:07.317
This level contains single-sided walls and double-sided walls

1236
00:53:07.317 --> 00:53:08.898
which are the two types present

1237
00:53:08.898 --> 00:53:12.109
The walls on the outside are single-sided

1238
00:53:12.109 --> 00:53:14.031
and the walls on the inside are

1239
00:53:14.031 --> 00:53:16.282
double-sided

1240
00:53:16.282 --> 00:53:19.455
The player is assumed to always be

1241
00:53:19.455 --> 00:53:21.351
inside the single-sided walls

1242
00:53:21.351 --> 00:53:23.205
Let's make this assumption

1243
00:53:23.205 --> 00:53:27.954
So, walls A, B, C, and D are single-sided

1244
00:53:27.954 --> 00:53:33.427
while F, G, and H have double-sided properties

1245
00:53:33.427 --> 00:53:35.223
And these walls, as shown here

1246
00:53:35.223 --> 00:53:36.569
follow a certain sequence

1247
00:53:36.569 --> 00:53:38.773
as indicated

1248
00:53:38.773 --> 00:53:41.639
They follow the direction of the arrows

1249
00:53:41.639 --> 00:53:43.640
Let us imagine this

1250
00:53:43.640 --> 00:53:45.851
So, when such a space is given

1251
00:53:45.851 --> 00:53:47.552
using a BSP tree

1252
00:53:47.552 --> 00:53:50.506
we can effectively divide it

1253
00:53:50.506 --> 00:53:52.664
The condition for dividing is

1254
00:53:52.664 --> 00:53:54.717
that the divided space

1255
00:53:54.717 --> 00:53:56.218
should have a convex shape

1256
00:53:56.218 --> 00:53:58.039
that does not obstruct visibility

1257
00:53:58.039 --> 00:54:00.126
or the division continues

1258
00:54:00.126 --> 00:54:02.134
until the number of shapes

1259
00:54:02.134 --> 00:54:04.335
is at least one

1260
00:54:04.335 --> 00:54:06.666
When the number of shapes becomes one

1261
00:54:06.666 --> 00:54:08.856
the division stops

1262
00:54:08.856 --> 00:54:10.718
following these rules

1263
00:54:10.718 --> 00:54:13.654
Let's proceed with the division

1264
00:54:13.654 --> 00:54:15.971
For the first division

1265
00:54:15.971 --> 00:54:18.809
we will define a plane that passes through wall F

1266
00:54:18.809 --> 00:54:20.726
Such a division plane

1267
00:54:20.726 --> 00:54:22.258
will be specified

1268
00:54:22.258 --> 00:54:24.269
This division plane

1269
00:54:24.269 --> 00:54:26.963
does not follow a specific formula for definition

1270
00:54:26.963 --> 00:54:28.594
In some cases, the developer

1271
00:54:28.594 --> 00:54:30.876
can arbitrarily define this dividing plane

1272
00:54:30.876 --> 00:54:33.503
setting it however they wish

1273
00:54:33.503 --> 00:54:35.499
Manually defining each one

1274
00:54:35.499 --> 00:54:37.112
every time

1275
00:54:37.112 --> 00:54:38.321
can be very tedious if the map is large,

1276
00:54:38.321 --> 00:54:40.562
as the work becomes extensive

1277
00:54:40.562 --> 00:54:42.937
Thus, it is known to define

1278
00:54:42.937 --> 00:54:44.331
 planes heuristically

1279
00:54:44.331 --> 00:54:47.003
In any case, we will use wall F as a reference

1280
00:54:47.003 --> 00:54:48.804
and set plane F to divide the space

1281
00:54:48.804 --> 00:54:50.621
Let’s assume this is how the division is done

1282
00:54:50.621 --> 00:54:54.727
Then, the node for wall F

1283
00:54:54.727 --> 00:54:56.435
is assigned as the root node

1284
00:54:56.435 --> 00:54:58.135
and using wall F as a basis

1285
00:54:58.135 --> 00:55:00.969
the space is divided into two regions

1286
00:55:00.969 --> 00:55:02.813
Let’s move on to the next step

1287
00:55:02.813 --> 00:55:05.613
Once the dividing plane has been defined

1288
00:55:05.613 --> 00:55:07.210
the space should be divided

1289
00:55:07.210 --> 00:55:09.062
into two parts accordingly

1290
00:55:09.062 --> 00:55:11.361
For walls A and C,

1291
00:55:11.361 --> 00:55:15.394
since they intersect plane F

1292
00:55:15.394 --> 00:55:18.393
they are divided into A1, A2, C1, and C2

1293
00:55:18.393 --> 00:55:21.198
Each is split into two parts

1294
00:55:21.198 --> 00:55:22.685
Here, the dividing plane

1295
00:55:22.685 --> 00:55:25.171
is currently facing downward

1296
00:55:25.171 --> 00:55:27.488
so this side becomes the positive region

1297
00:55:27.488 --> 00:55:30.572
and this side becomes the negative region

1298
00:55:30.572 --> 00:55:33.433
Thus, the negative region contains

1299
00:55:33.433 --> 00:55:35.868
walls forming the left node

1300
00:55:35.868 --> 00:55:39.299
which are A1, B, and C1

1301
00:55:39.299 --> 00:55:41.984
The remaining walls are placed

1302
00:55:41.984 --> 00:55:44.229
in the right node

1303
00:55:44.229 --> 00:55:46.149
Now, let’s examine

1304
00:55:46.149 --> 00:55:47.696
if each node can be further divided

1305
00:55:47.696 --> 00:55:49.002
This must be examined

1306
00:55:49.002 --> 00:55:51.390
As I mentioned earlier,

1307
00:55:51.390 --> 00:55:54.629
the region consisting of A1, B1, and C1

1308
00:55:54.629 --> 00:55:56.369
is convex when I am inside it,

1309
00:55:56.369 --> 00:55:59.984
ensuring that nothing obstructs the view

1310
00:55:59.984 --> 00:56:00.968
This forms a convex region

1311
00:56:00.968 --> 00:56:03.239
Thus, the left node

1312
00:56:03.239 --> 00:56:04.915
is complete, and now we examine

1313
00:56:04.915 --> 00:56:07.128
whether the right region

1314
00:56:07.128 --> 00:56:09.832
can be further divided

1315
00:56:09.832 --> 00:56:13.412
If something is located in the right region

1316
00:56:13.412 --> 00:56:15.189
for instance, here

1317
00:56:15.189 --> 00:56:18.037
A2 would be obstructed by G

1318
00:56:18.037 --> 00:56:21.659
Since this obstructs the view

1319
00:56:21.659 --> 00:56:23.720
it must be further divided

1320
00:56:23.720 --> 00:56:27.541
Let’s proceed to the next step

1321
00:56:27.541 --> 00:56:30.518
This time, using a new dividing plane

1322
00:56:30.518 --> 00:56:32.482
that aligns with wall G

1323
00:56:32.482 --> 00:56:34.389
we define plane G

1324
00:56:34.389 --> 00:56:36.290
to divide this right space

1325
00:56:36.290 --> 00:56:38.628
Let’s perform this division

1326
00:56:38.628 --> 00:56:41.883
The positive region of plane G will be here

1327
00:56:41.883 --> 00:56:44.189
and the negative region will be here

1328
00:56:44.189 --> 00:56:46.285
As done earlier,

1329
00:56:46.285 --> 00:56:50.013
for any regions intersecting plane G

1330
00:56:50.013 --> 00:56:51.815
we must further divide them

1331
00:56:53.142 --> 00:56:55.078
Moving on to the next step,

1332
00:56:55.078 --> 00:56:58.850
since wall D intersects plane G

1333
00:56:58.850 --> 00:57:02.794
we split wall D into D1 and D2

1334
00:57:02.794 --> 00:57:06.991
Thus, the shapes behind plane G

1335
00:57:06.991 --> 00:57:09.808
will be A2 and D1

1336
00:57:09.808 --> 00:57:11.431
In this case,

1337
00:57:11.431 --> 00:57:14.020
there is nothing obstructing the view

1338
00:57:14.020 --> 00:57:16.747
so we assign it to the left node

1339
00:57:16.747 --> 00:57:18.847
and terminate the division

1340
00:57:18.847 --> 00:57:21.810
Now, regarding the remaining right region

1341
00:57:21.810 --> 00:57:24.734
it contains H, C2, and D2

1342
00:57:24.734 --> 00:57:27.544
If the player is here

1343
00:57:27.544 --> 00:57:29.443
it obstructs the view

1344
00:57:29.443 --> 00:57:31.469
so further division is necessary

1345
00:57:31.469 --> 00:57:33.330
as can be seen

1346
00:57:33.330 --> 00:57:35.883
Let us move on to the next step

1347
00:57:35.883 --> 00:57:37.772
For the next space division,

1348
00:57:37.772 --> 00:57:39.616
we define a plane H that aligns with wall H

1349
00:57:39.616 --> 00:57:41.571
and set up plane H

1350
00:57:41.571 --> 00:57:44.100
to divide the space

1351
00:57:44.100 --> 00:57:47.034
Since the plane faces this direction

1352
00:57:47.034 --> 00:57:51.099
we examine the walls intersecting  H

1353
00:57:51.099 --> 00:57:53.646
and divide them into two

1354
00:57:53.646 --> 00:57:56.724
In the next step, the intersection with H

1355
00:57:56.724 --> 00:58:00.816
is currently at D2, as mentioned earlier

1356
00:58:00.816 --> 00:58:05.093
By splitting D2 into D3 and D4

1357
00:58:05.093 --> 00:58:07.984
we can achieve the desired result

1358
00:58:07.984 --> 00:58:13.717
The space behind plane H

1359
00:58:13.717 --> 00:58:16.227
consists of D4 and C2

1360
00:58:16.227 --> 00:58:18.144
while the space in front of plane H

1361
00:58:18.144 --> 00:58:19.636
contains only D3

1362
00:58:19.636 --> 00:58:21.363
Both of these spaces

1363
00:58:21.363 --> 00:58:24.176
do not obstruct the view

1364
00:58:24.176 --> 00:58:26.235
so we have fully divided the space

1365
00:58:26.235 --> 00:58:27.774
to the extent needed

1366
00:58:27.774 --> 00:58:29.733
as can be seen

1367
00:58:29.733 --> 00:58:33.122
Thus, the final divided space structure

1368
00:58:33.122 --> 00:58:34.897
and the BST tree's data structure

1369
00:58:34.897 --> 00:58:36.658
are as follows

1370
00:58:36.658 --> 00:58:39.912
Now that the space is divided

1371
00:58:39.912 --> 00:58:41.784
and the data structure is built

1372
00:58:41.784 --> 00:58:44.472
if the player is positioned as shown

1373
00:58:44.472 --> 00:58:46.592
let’s see how the rendering

1374
00:58:46.592 --> 00:58:48.714
 proceeds

1375
00:58:48.714 --> 00:58:50.330
As shown here, the player

1376
00:58:50.330 --> 00:58:52.998
has this line of sight

1377
00:58:52.998 --> 00:58:54.400
Currently, the player

1378
00:58:54.400 --> 00:58:57.213
is facing walls F, G, and H

1379
00:58:57.213 --> 00:58:59.984
This can be seen as the current state

1380
00:59:01.281 --> 00:59:03.977
First, identify the space the player occupies

1381
00:59:03.977 --> 00:59:06.791
to determine the rendering order

1382
00:59:06.791 --> 00:59:11.153
The player is in the positive space

1383
00:59:11.153 --> 00:59:12.685
of plane F

1384
00:59:12.685 --> 00:59:15.389
Thus, polygons in the negative region

1385
00:59:15.389 --> 00:59:17.483
must be rendered first

1386
00:59:17.483 --> 00:59:18.856
this should be done first

1387
00:59:18.856 --> 00:59:21.444
From the root node

1388
00:59:21.444 --> 00:59:26.056
the polygons A1, B, and C1

1389
00:59:26.056 --> 00:59:28.425
walls A1, B, and C1

1390
00:59:28.425 --> 00:59:32.241
should be queued first in the rendering order

1391
00:59:32.241 --> 00:59:34.706
To complete the rendering order,

1392
00:59:34.706 --> 00:59:36.377
the remaining steps must be defined

1393
00:59:36.377 --> 00:59:38.196
Returning to the root,

1394
00:59:38.196 --> 00:59:41.636
we examine wall F

1395
00:59:41.636 --> 00:59:44.901
Since wall F is double-sided

1396
00:59:44.901 --> 00:59:47.375
it consists of a front and a back side

1397
00:59:47.375 --> 00:59:49.306
Through visibility checks

1398
00:59:49.306 --> 00:59:51.406
we can skip rendering the back side

1399
00:59:51.406 --> 00:59:53.840
and set it to render only the front side

1400
00:59:53.840 --> 00:59:56.871
Thus, in the rendering order

1401
00:59:56.871 --> 00:59:58.757
the polygons from the negative space

1402
00:59:58.757 --> 01:00:01.365
A1, B, and C1 are rendered first,

1403
01:00:01.365 --> 01:00:04.264
followed by the front side of wall F

1404
01:00:04.264 --> 01:00:05.896
This is how the order is established

1405
01:00:05.896 --> 01:00:09.262
This is how the order can be set

1406
01:00:09.262 --> 01:00:12.488
Let’s move on to the next step

1407
01:00:12.488 --> 01:00:15.469
Next, for the plane at the next depth

1408
01:00:15.469 --> 01:00:18.690
we will perform a comparison for plane G

1409
01:00:18.690 --> 01:00:20.532
The player is in the positive space

1410
01:00:20.532 --> 01:00:21.979
of plane G

1411
01:00:21.979 --> 01:00:24.200
First, the polygons in the negative space

1412
01:00:24.200 --> 01:00:27.577
specifically walls A2 and D1

1413
01:00:27.577 --> 01:00:29.564
are rendered

1414
01:00:29.564 --> 01:00:33.540
Thus, the rendering order becomes A1, B, C1

1415
01:00:33.540 --> 01:00:37.828
followed by the front of wall F, and then A2 and D1

1416
01:00:37.828 --> 01:00:39.344
This completes the rendering process

1417
01:00:41.761 --> 01:00:44.320
Returning to the node, this time

1418
01:00:44.320 --> 01:00:47.142
as done with wall F,

1419
01:00:47.142 --> 01:00:50.264
we check whether the double-sided wall G

1420
01:00:50.264 --> 01:00:53.046
is facing the player

1421
01:00:53.046 --> 01:00:55.360
If they are facing each other,

1422
01:00:55.360 --> 01:00:57.288
the front side of wall G

1423
01:00:57.288 --> 01:00:58.748
is rendered,

1424
01:00:58.748 --> 01:01:01.504
and then we proceed to the right node

1425
01:01:02.763 --> 01:01:04.544
In the next step,

1426
01:01:04.544 --> 01:01:08.038
we analyze the space for wall H

1427
01:01:08.038 --> 01:01:09.785
Since the player is in the positive space

1428
01:01:09.785 --> 01:01:13.031
the walls D4 and C2 in the negative space

1429
01:01:13.031 --> 01:01:16.179
are rendered first

1430
01:01:16.179 --> 01:01:19.867
Then, the front side of wall H is rendered

1431
01:01:19.867 --> 01:01:23.823
and finally, wall D3 is rendered

1432
01:01:23.823 --> 01:01:26.252
This completes all rendering

1433
01:01:28.060 --> 01:01:29.952
By traversing the tree while the player

1434
01:01:29.952 --> 01:01:33.491
is in this space

1435
01:01:33.491 --> 01:01:34.926
we could determine

1436
01:01:34.926 --> 01:01:36.894
 the final rendering order

1437
01:01:36.894 --> 01:01:40.739
To sum up again, it was A1, B, C1

1438
01:01:40.739 --> 01:01:45.520
followed by the front of F, then A2, D1, the front of G,

1439
01:01:45.520 --> 01:01:49.797
D4, C2, the front of H, and finally D3

1440
01:01:49.797 --> 01:01:52.013
This is the sequence in which rendering proceeds

1441
01:01:52.013 --> 01:01:55.082
Once the rendering order is decided

1442
01:01:55.082 --> 01:01:56.616
it is not always necessary

1443
01:01:56.616 --> 01:01:58.530
to strictly follow it

1444
01:01:58.530 --> 01:02:01.955
Rendering can be optimized further based on visibility checks

1445
01:02:01.955 --> 01:02:04.316
or by using techniques like Z-buffering

1446
01:02:04.316 --> 01:02:06.774
These approaches allow for

1447
01:02:06.774 --> 01:02:08.982
more efficient rendering

1448
01:02:10.467 --> 01:02:11.963
For instance, if the player

1449
01:02:11.963 --> 01:02:14.963
is in the negative space behind wall F

1450
01:02:14.963 --> 01:02:17.066
in such cases, instead of starting from the left

1451
01:02:17.066 --> 01:02:19.201
you would begin rendering from the right node

1452
01:02:19.201 --> 01:02:21.317
First, render all the right nodes

1453
01:02:21.317 --> 01:02:22.405
before moving to the left

1454
01:02:22.405 --> 01:02:25.458
This allows the rendering order to be adjusted

1455
01:02:25.458 --> 01:02:28.369
If the player is facing forward

1456
01:02:28.369 --> 01:02:31.196
and we know their orientation

1457
01:02:31.196 --> 01:02:33.933
then the positive space of wall F

1458
01:02:33.933 --> 01:02:37.143
does not need to be rendered

1459
01:02:37.143 --> 01:02:39.272
Rendering it is unnecessary

1460
01:02:39.272 --> 01:02:42.088
Thus, a significant number of objects

1461
01:02:42.088 --> 01:02:43.736
can be excluded from rendering

1462
01:02:43.736 --> 01:02:46.922
Only the walls A1, B

1463
01:02:46.922 --> 01:02:49.508
and C1 in front would need to be rendered

1464
01:02:49.508 --> 01:02:50.856
Similarly,

1465
01:02:50.856 --> 01:02:52.600
each wall can be checked for visibility

1466
01:02:52.600 --> 01:02:54.569
to ensure only visible walls are rendered

1467
01:02:54.569 --> 01:02:56.528
Rendering only the necessary walls

1468
01:02:56.528 --> 01:02:57.785
makes the process even more efficient

1469
01:02:57.785 --> 01:03:00.111
This leads to a more optimized rendering process

1470
01:03:01.349 --> 01:03:03.451
The pros and cons of BSP trees

1471
01:03:03.451 --> 01:03:05.438
can be summarized as follows

1472
01:03:05.438 --> 01:03:07.866
The advantages of BSP trees are

1473
01:03:07.866 --> 01:03:10.484
Before the advent of graphics cards,

1474
01:03:10.484 --> 01:03:12.481
everything had to be rendered using the CPU

1475
01:03:12.481 --> 01:03:14.125
Rendering relied solely on CPU processing

1476
01:03:14.125 --> 01:03:16.816
to minimize CPU workload

1477
01:03:16.816 --> 01:03:20.030
BSP trees were a crucial algorithm

1478
01:03:20.030 --> 01:03:23.036
However, as mentioned earlier

1479
01:03:23.036 --> 01:03:25.323
they are very complex to implement

1480
01:03:25.323 --> 01:03:27.650
Automatically detecting optimal planes

1481
01:03:27.650 --> 01:03:31.080
requires developing heuristic algorithms

1482
01:03:31.080 --> 01:03:34.628
Moreover, debugging whether the constructed level

1483
01:03:34.628 --> 01:03:37.102
is correctly set up is challenging

1484
01:03:37.102 --> 01:03:38.514
Additionally, BSP trees

1485
01:03:38.514 --> 01:03:40.795
are only applicable to static backgrounds

1486
01:03:40.795 --> 01:03:42.214
They are not suited for dynamic environments

1487
01:03:42.214 --> 01:03:44.069
Since BSP logic involves splitting static backgrounds

1488
01:03:44.069 --> 01:03:46.678
any changes in background layout

1489
01:03:46.678 --> 01:03:49.050
require a complete rebuild

1490
01:03:49.050 --> 01:03:50.352
of all levels

1491
01:03:50.352 --> 01:03:51.851
It would have to be rebuilt

1492
01:03:52.874 --> 01:03:55.736
So, for larger levels

1493
01:03:55.736 --> 01:03:58.095
building them consumes significant time

1494
01:03:58.095 --> 01:04:02.105
This lowers development productivity

1495
01:04:02.105 --> 01:04:04.194
Nowadays, all rendering tasks

1496
01:04:04.194 --> 01:04:07.681
utilize the power of graphics hardware

1497
01:04:07.681 --> 01:04:10.189
for high-speed computations

1498
01:04:10.189 --> 01:04:13.119
Thus, BSP trees are no longer used

1499
01:04:13.119 --> 01:04:15.576
Graphics card-based algorithms

1500
01:04:15.576 --> 01:04:17.400
have largely replaced them

1501
01:04:17.400 --> 01:04:20.423
As a result, BSP trees are no longer

1502
01:04:20.423 --> 01:04:23.208
widely used as they once were

1503
01:04:23.208 --> 01:04:25.201
This concludes today’s lecture

1504
01:04:25.201 --> 01:04:27.041
Thank you for attending

1505
01:04:27.041 --> 01:04:27.897
Thank you

1506
01:04:28.549 --> 01:04:29.551
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

1507
01:04:29.551 --> 01:04:30.542
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

1508
01:04:30.542 --> 01:04:31.474
Nodes use specified dimension to divide given space
Typically, dimensions are assigned to nodes in the order x, y, z, x based on depth

1509
01:04:31.474 --> 01:04:32.401
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

1510
01:04:32.401 --> 01:04:33.361
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

1511
01:04:33.361 --> 01:04:36.155
Uses of KD Tree
Finding nearest point to given point
Finding points within specified range

1512
01:04:36.155 --> 01:04:38.371
By identifying areas that do not need to be examined,
it excludes these areas from the search
Overview and Working Principles of BSP Tree

1513
01:04:38.371 --> 01:04:40.312
Overview/principle of BSP Tree 
Technique that bisects given space and stores in tree structure
to enable efficient search
specify plane to divide spa

1514
01:04:40.312 --> 01:04:41.906
Separate terrain into front and back parts based on the plane
and split geometry that intersects
Recursively split separated spaces to form binary tr

1515
01:04:41.906 --> 01:04:43.371
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

1516
01:04:43.371 --> 01:04:44.730
Applications of BSP Tree
Divide 3D levels for efficient rendering with hidden surface removal
Detect ray collisions in 3D
Divide terrain information

1517
01:04:44.730 --> 01:04:46.143
Pros and Cons of BSP Tree
Pro
Before graphics cards, crucial for minimizing CPU computation
and was key algorithm
Con
Complex to implement/debug

1518
01:04:46.143 --> 01:04:47.317
Limited to static backgrounds
Requires complete reconstruction if background layout changes
Time-intensive for large levels, reducing productivity

1519
01:04:47.317 --> 01:04:48.312
With modern graphics cards enabling fast computations,
it has largely been replaced and is no longer widely used