WEBVTT

1
00:00:06.292 --> 00:00:09.886
Game Basics
Understanding Space Partitioning Algorithms: Quadtrees and Octrees, Part 2

2
00:00:27.540 --> 00:00:28.959
Hello, everyone

3
00:00:28.959 --> 00:00:31.240
This is Lee Deuk-woo from Game Algorithms

4
00:00:31.240 --> 00:00:32.829
This is the second lecture on space partitioning algorithms

5
00:00:32.829 --> 00:00:36.240
Quadtrees and Octrees

6
00:00:36.240 --> 00:00:38.762
In this lecture, I will introduce optimization techniques for quadtrees

7
00:00:38.762 --> 00:00:41.680
and their implementation methods

8
00:00:41.680 --> 00:00:45.015
I’ll also cover an overview of octrees, which extend from quadtrees

9
00:00:45.015 --> 00:00:47.279
and their implementation methods

10
00:00:48.157 --> 00:00:51.801
optimization for quadtrees

11
00:00:52.480 --> 00:00:55.480
In the previous lectures,

12
00:00:55.480 --> 00:00:59.880
I explained the basic implementation methods for quadtrees

13
00:00:59.880 --> 00:01:02.720
In a standard quadtree implementation,

14
00:01:02.720 --> 00:01:06.639
as shown here, objects overlapping boundary lines

15
00:01:06.639 --> 00:01:09.279
are not subdivided further

16
00:01:09.279 --> 00:01:13.199
and are instead included in the object list of the corresponding node

17
00:01:13.199 --> 00:01:15.400
Thus, as shown in the diagram

18
00:01:15.400 --> 00:01:18.440
all objects marked in blue

19
00:01:18.440 --> 00:01:21.040
because they overlap boundary lines

20
00:01:21.040 --> 00:01:23.181
regardless of size

21
00:01:23.181 --> 00:01:27.559
are included in the root node’s object list

22
00:01:27.559 --> 00:01:29.225
As discussed in the first lecture

23
00:01:29.225 --> 00:01:32.040
on quadtree querying

24
00:01:32.040 --> 00:01:34.480
the object list in the root node

25
00:01:34.480 --> 00:01:37.040
is always included in the list

26
00:01:37.040 --> 00:01:42.360
of potentially colliding objects

27
00:01:42.360 --> 00:01:46.360
This inevitably increases the search load

28
00:01:46.360 --> 00:01:50.360
To address this

29
00:01:50.360 --> 00:01:53.010
one solution is to record overlapping regions

30
00:01:53.010 --> 00:01:55.639
more precisely

31
00:01:55.639 --> 00:01:59.519
limiting collision detection to relevant areas

32
00:01:59.519 --> 00:02:02.879
and reducing the search load

33
00:02:02.879 --> 00:02:04.289
For example

34
00:02:04.289 --> 00:02:07.760
when performing collision detection in the upper-right region

35
00:02:07.760 --> 00:02:12.559
objects overlapping the left and lower regions

36
00:02:12.559 --> 00:02:15.616
if information exists indicating

37
00:02:15.616 --> 00:02:18.080
that they belong to the left or lower regions

38
00:02:18.080 --> 00:02:22.119
can be excluded from

39
00:02:22.119 --> 00:02:26.000
the collision detection list

40
00:02:26.000 --> 00:02:30.160
This approach reduces the search load slightly

41
00:02:30.160 --> 00:02:34.036
but isn’t a definitive solution, is it?

42
00:02:36.600 --> 00:02:38.550
The technique I’ll introduce today

43
00:02:38.550 --> 00:02:40.479
is the Loose Quadtree

44
00:02:40.479 --> 00:02:43.360
This method was introduced in a classic book

45
00:02:43.360 --> 00:02:44.875
titled Game Programming Gems

46
00:02:44.875 --> 00:02:47.399
published in 2000

47
00:02:47.399 --> 00:02:51.479
It was contributed by someone named Ulrich

48
00:02:51.479 --> 00:02:53.198
The section is titled

49
00:02:53.198 --> 00:02:56.759
"Loose Octrees"

50
00:02:56.759 --> 00:03:00.639
but the technique I’ll explain later pertains to octrees

51
00:03:00.639 --> 00:03:04.360
Since the implementation is nearly identical to that of quadtrees

52
00:03:04.360 --> 00:03:08.119
this technique can also be applied to quadtrees

53
00:03:08.119 --> 00:03:10.361
In this article, the previously mentioned issue

54
00:03:10.361 --> 00:03:13.039
caused by objects located on boundaries

55
00:03:13.039 --> 00:03:16.919
and the resulting complexity in data structure distribution

56
00:03:16.919 --> 00:03:20.360
is referred to as "Sticky Planes"

57
00:03:20.360 --> 00:03:22.381
To address the Sticky Planes problem

58
00:03:22.381 --> 00:03:24.679
temporary solutions include

59
00:03:24.679 --> 00:03:26.733
classifying overlapping information

60
00:03:26.733 --> 00:03:29.679
in greater detail

61
00:03:29.679 --> 00:03:34.240
or passing management of overlapping nodes

62
00:03:34.240 --> 00:03:37.160
to child nodes instead of the parent

63
00:03:37.160 --> 00:03:39.000
However, these methods

64
00:03:39.000 --> 00:03:42.839
make quadtree structures more complex

65
00:03:42.839 --> 00:03:44.915
and serve only as temporary fixes

66
00:03:44.915 --> 00:03:48.119
failing to fully resolve the issue

67
00:03:48.119 --> 00:03:51.360
They can be applied to statically placed objects

68
00:03:51.360 --> 00:03:53.210
but are unsuitable for objects

69
00:03:53.210 --> 00:03:57.199
that move dynamically across regions

70
00:03:57.199 --> 00:03:59.039
They are not fit

71
00:03:59.039 --> 00:04:01.880
This is because, as the rules grow more complex

72
00:04:01.880 --> 00:04:03.926
frequent additions and deletions

73
00:04:03.926 --> 00:04:07.306
occur in lists of varying depths

74
00:04:09.039 --> 00:04:11.720
To address this, Ulrich proposed

75
00:04:11.720 --> 00:04:14.171
loosely increasing the size of quadrants

76
00:04:14.171 --> 00:04:16.829
during subdivision

77
00:04:16.829 --> 00:04:18.675
Let’s take a closer look at this

78
00:04:20.279 --> 00:04:21.857
In the quadtree, as previously explained

79
00:04:21.857 --> 00:04:25.079
the length of each subdivided node’s side

80
00:04:25.079 --> 00:04:27.828
decreases by a factor of 2^depth

81
00:04:27.828 --> 00:04:30.409
based on the depth

82
00:04:30.409 --> 00:04:32.609
Ulrich introduces

83
00:04:32.609 --> 00:04:36.760
a constant k to multiply this value

84
00:04:36.760 --> 00:04:40.438
If k=1, it remains the same as before

85
00:04:40.438 --> 00:04:43.640
so a value greater than 1 must be specified

86
00:04:43.640 --> 00:04:46.079
Here, Ulrich recommends a value of 2

87
00:04:46.079 --> 00:04:49.077
When you multiply by 2

88
00:04:49.077 --> 00:04:50.643
as shown in the diagram on the right

89
00:04:50.643 --> 00:04:53.906
the area managed by each quadrant expands

90
00:04:55.559 --> 00:04:56.856
Under these conditions,

91
00:04:56.856 --> 00:05:00.064
let’s examine how to implement a loose quadtree

92
00:05:01.509 --> 00:05:03.933
When implementing a loose quadtree

93
00:05:03.933 --> 00:05:07.119
unlike a standard quadtree

94
00:05:07.119 --> 00:05:12.839
you first measure the maximum radius of the object to be inserted

95
00:05:12.839 --> 00:05:14.878
Based on this radius,

96
00:05:14.878 --> 00:05:18.760
you determine the appropriate depth for insertion

97
00:05:18.760 --> 00:05:21.204
Thus, regardless of the location

98
00:05:21.204 --> 00:05:24.530
you calculate the depth first

99
00:05:24.530 --> 00:05:26.672
If the object’s radius

100
00:05:26.672 --> 00:05:30.486
is smaller than one-fourth of the side length

101
00:05:30.486 --> 00:05:33.279
you add one more level of depth

102
00:05:33.279 --> 00:05:37.423
If the radius is even smaller,

103
00:05:37.423 --> 00:05:40.556
less than one-eighth of the side length

104
00:05:40.556 --> 00:05:42.320
you further reduce the depth by one level

105
00:05:42.320 --> 00:05:44.723
Each time the radius decreases by half,

106
00:05:44.723 --> 00:05:47.540
you increase the depth

107
00:05:47.540 --> 00:05:51.760
and designate the node for insertion

108
00:05:51.760 --> 00:05:54.527
As mentioned earlier, the side length in a loose quadtree

109
00:05:54.527 --> 00:05:56.885
is calculated by dividing the root node’s side W

110
00:05:56.885 --> 00:05:59.478
by 2^depth

111
00:05:59.478 --> 00:06:01.008
This value was multiplied by k

112
00:06:02.770 --> 00:06:05.440
For example, in a quadtree

113
00:06:05.440 --> 00:06:08.364
where the side length of the root node is 64

114
00:06:08.364 --> 00:06:12.139
if an object with a radius larger than 16 is inserted

115
00:06:12.139 --> 00:06:14.567
since the radius is 16

116
00:06:14.567 --> 00:06:17.934
the diameter of the circle would be 32

117
00:06:17.934 --> 00:06:20.254
If it’s larger than this

118
00:06:20.254 --> 00:06:22.680
 it means it won’t fit into a single quadrant

119
00:06:22.680 --> 00:06:27.048
Therefore, it is stored in the root node

120
00:06:27.048 --> 00:06:29.922
However, if the radius is smaller than 16

121
00:06:29.922 --> 00:06:33.258
it will be stored in the first-depth node

122
00:06:33.258 --> 00:06:36.160
If the radius is smaller than 8

123
00:06:36.160 --> 00:06:37.553
it will be stored in the second-depth node

124
00:06:37.553 --> 00:06:39.650
If it’s smaller than 4, it will be stored in the third-depth node

125
00:06:39.650 --> 00:06:42.521
In this way, the depth is incremented

126
00:06:42.521 --> 00:06:44.814
by multiples of 2

127
00:06:44.814 --> 00:06:49.799
to determine which node the object will be stored in

128
00:06:49.799 --> 00:06:52.005
When k=2 in a loose quadtree

129
00:06:52.005 --> 00:06:55.440
the formula for calculating depth is as follows

130
00:06:55.440 --> 00:06:58.010
Here, since

131
00:06:58.010 --> 00:07:01.596
the object’s radius is smaller than one-fourth of the side length

132
00:07:01.596 --> 00:07:06.588
this formula determines the depth for such cases

133
00:07:06.588 --> 00:07:10.058
If we calculate this in reverse

134
00:07:10.058 --> 00:07:14.520
2^depth equals the root node’s side length

135
00:07:14.520 --> 00:07:16.771
divided by the maximum radius,

136
00:07:16.771 --> 00:07:19.490
then divided by 1

137
00:07:19.490 --> 00:07:21.352
Using a log

138
00:07:21.352 --> 00:07:24.274
we can estimate the depth value

139
00:07:24.274 --> 00:07:26.400
Where W

140
00:07:26.400 --> 00:07:28.634
is the root node’s side length

141
00:07:28.634 --> 00:07:31.679
Take the log of W

142
00:07:31.679 --> 00:07:33.729
divided by the maximum radius

143
00:07:33.729 --> 00:07:35.542
and apply the floor function

144
00:07:35.542 --> 00:07:37.880
to convert it to an integer

145
00:07:37.880 --> 00:07:39.346
Once this depth value

146
00:07:39.346 --> 00:07:41.518
is confirmed

147
00:07:41.518 --> 00:07:43.896
you calculate the object’s center

148
00:07:43.896 --> 00:07:46.491
to determine which quadrant

149
00:07:46.491 --> 00:07:50.050
 it belongs to

150
00:07:50.050 --> 00:07:52.406
Let’s take a look through a diagram

151
00:07:54.160 --> 00:07:57.644
The first subdivision of the root node

152
00:07:57.644 --> 00:07:59.879
will have a depth of 1

153
00:07:59.879 --> 00:08:03.400
This creates loose quadrants like these

154
00:08:03.400 --> 00:08:06.448
The radius of objects that can fit here

155
00:08:06.448 --> 00:08:11.230
must be smaller than one-fourth of the root node’s side length

156
00:08:11.230 --> 00:08:14.425
Let’s assume such an object is inserted

157
00:08:16.320 --> 00:08:18.212
An object is inserted

158
00:08:18.212 --> 00:08:20.263
and although it overlaps with the boundary

159
00:08:20.263 --> 00:08:24.519
its center is located in the top-left quadrant

160
00:08:24.519 --> 00:08:27.059
Whether or not it overlaps is irrelevant here

161
00:08:27.059 --> 00:08:30.496
What matters is the object’s maximum radius

162
00:08:30.496 --> 00:08:35.264
Let’s assume the radius is smaller than one-fourth

163
00:08:35.264 --> 00:08:37.558
but larger than one-eighth of the side length

164
00:08:37.558 --> 00:08:39.518
In this case, the object

165
00:08:39.518 --> 00:08:43.450
is stored in the first-depth quadrant

166
00:08:43.450 --> 00:08:45.703
The, as shown earlier

167
00:08:45.703 --> 00:08:48.570
since it’s located in the top-left quadrant

168
00:08:48.570 --> 00:08:51.362
it will be placed in the top-left child node

169
00:08:51.362 --> 00:08:53.805
child node of the root node’s four subdivisions

170
00:08:53.805 --> 00:08:57.186
Add the object to the object list

171
00:08:57.186 --> 00:08:58.976
of the top-left child node

172
00:09:02.598 --> 00:09:05.239
Now, let’s look at another example

173
00:09:05.239 --> 00:09:07.254
In this example

174
00:09:07.254 --> 00:09:12.259
the object’s radius is smaller than one-eighth of the root node’s side length

175
00:09:12.259 --> 00:09:15.688
but larger than one-sixteenth

176
00:09:15.688 --> 00:09:17.307
Then this object

177
00:09:17.307 --> 00:09:22.849
will be stored in a second-depth quadrant

178
00:09:22.849 --> 00:09:25.159
Since the object’s center

179
00:09:25.159 --> 00:09:27.200
is in the bottom-right quadrant

180
00:09:27.200 --> 00:09:29.885
add it to the object list

181
00:09:29.885 --> 00:09:32.011
of the bottom-right node

182
00:09:32.011 --> 00:09:33.826
at depth 2

183
00:09:39.281 --> 00:09:41.901
By implementing a loose quadtree

184
00:09:41.901 --> 00:09:43.755
unlike a standard quadtree,

185
00:09:43.755 --> 00:09:45.402
you can obtain consistent data

186
00:09:45.402 --> 00:09:47.328
with uniform depths

187
00:09:47.328 --> 00:09:50.499
based on object sizes

188
00:09:50.499 --> 00:09:52.912
The diagram below, from 2009

189
00:09:52.912 --> 00:09:55.104
compares 10,000 objects

190
00:09:55.104 --> 00:09:57.315
between standard

191
00:09:57.315 --> 00:10:00.179
and loose quadtree implementations

192
00:10:00.179 --> 00:10:01.790
It is comparing the charts

193
00:10:01.790 --> 00:10:03.603
In the left image,

194
00:10:03.603 --> 00:10:05.768
objects with the same radius

195
00:10:05.768 --> 00:10:07.050
were tested

196
00:10:07.050 --> 00:10:08.808
In the right image

197
00:10:08.808 --> 00:10:12.318
objects with varying radii

198
00:10:12.318 --> 00:10:14.039
were tested

199
00:10:14.039 --> 00:10:16.951
The navy-blue bars represent

200
00:10:16.951 --> 00:10:18.633
the standard implementation

201
00:10:18.633 --> 00:10:20.700
discussed in previous lectures

202
00:10:20.700 --> 00:10:24.330
As a result, objects overlapping boundaries

203
00:10:24.330 --> 00:10:26.399
are concentrated in nodes

204
00:10:26.399 --> 00:10:29.123
with higher depths

205
00:10:29.123 --> 00:10:33.149
In contrast, in the loose structure

206
00:10:33.149 --> 00:10:35.146
the depth is assigned based on

207
00:10:35.146 --> 00:10:38.479
the object’s actual radius

208
00:10:38.479 --> 00:10:42.358
resulting in uniformly distributed depths

209
00:10:44.348 --> 00:10:47.039
Similarly, in the second case,

210
00:10:47.039 --> 00:10:52.030
for spheres with varying diameters

211
00:10:52.030 --> 00:10:54.795
a uniform distribution can be observed

212
00:10:54.795 --> 00:10:57.002
According to the study

213
00:10:57.002 --> 00:10:59.921
collision detection operations

214
00:10:59.921 --> 00:11:01.697
with the loose structure

215
00:11:01.697 --> 00:11:04.619
were 40 times faster

216
00:11:04.619 --> 00:11:05.681
However,

217
00:11:05.681 --> 00:11:09.212
since this result applies to specific scenarios

218
00:11:09.212 --> 00:11:12.014
it’s difficult to generalize

219
00:11:12.014 --> 00:11:15.178
that loose quadtrees are always better

220
00:11:15.178 --> 00:11:17.274
Analyzing the current situation

221
00:11:17.274 --> 00:11:19.775
and applying the appropriate solution

222
00:11:19.775 --> 00:11:21.907
is crucial

223
00:11:21.907 --> 00:11:24.672
Now, let’s look at a sample project

224
00:11:24.672 --> 00:11:27.444
to compare the distribution differences

225
00:11:27.444 --> 00:11:31.263
between loose and standard quadtrees

226
00:11:31.263 --> 00:11:32.844
In the Scenes folder, open folder 2

227
00:11:32.844 --> 00:11:35.785
LooseQuadtree

228
00:11:35.785 --> 00:11:38.946
You’ll find the scene named LooseQuadtree Insert

229
00:11:38.946 --> 00:11:42.454
Here, you’ll see four buttons in total

230
00:11:42.454 --> 00:11:44.260
The top button,

231
00:11:44.260 --> 00:11:47.202
Insert All General,

232
00:11:47.202 --> 00:11:51.599
uses the standard quadtree implementation from the previous lecture

233
00:11:51.599 --> 00:11:53.338
to insert

234
00:11:53.338 --> 00:11:55.900
30 different objects

235
00:11:55.900 --> 00:11:57.955
and examine their distribution

236
00:11:57.955 --> 00:12:00.128
To examine the distribution

237
00:12:00.128 --> 00:12:02.919
a Stat button has been added

238
00:12:02.919 --> 00:12:06.188
The button below it, Insert All Loose

239
00:12:06.188 --> 00:12:08.353
uses the loose quadtree implementation

240
00:12:08.353 --> 00:12:11.369
to add 30 objects

241
00:12:11.369 --> 00:12:13.675
Then, by pressing the Stat button

242
00:12:13.675 --> 00:12:17.248
you can check how the 30 objects

243
00:12:17.248 --> 00:12:19.280
are distributed

244
00:12:19.280 --> 00:12:21.924
Let’s test this by running the program

245
00:12:25.686 --> 00:12:28.090
First, using the standard quadtree

246
00:12:28.090 --> 00:12:31.239
let’s place 30 objects

247
00:12:31.239 --> 00:12:36.718
As a result, objects overlapping boundary lines

248
00:12:36.718 --> 00:12:39.959
are added, as you can see

249
00:12:39.959 --> 00:12:43.081
Here, even if the radius is small

250
00:12:43.081 --> 00:12:44.574
if the object overlaps a boundary

251
00:12:44.574 --> 00:12:46.605
it gets added to a higher-depth node

252
00:12:46.605 --> 00:12:48.759
You can see, right?

253
00:12:48.759 --> 00:12:49.883
These are the examples

254
00:12:49.883 --> 00:12:52.279
Looking at these examples

255
00:12:52.279 --> 00:12:54.682
you can see that they’ve been added to the higher depths

256
00:12:55.900 --> 00:12:59.115
Now, let’s rerun it

257
00:12:59.115 --> 00:13:01.955
and try pressing the button below

258
00:13:05.017 --> 00:13:08.394
When using the loose quadtree structure below,

259
00:13:08.394 --> 00:13:10.050
as you can see

260
00:13:10.050 --> 00:13:13.039
even though they overlap the higher nodes

261
00:13:13.039 --> 00:13:16.580
you can see that they’re included

262
00:13:16.580 --> 00:13:18.123
in the lower node’s item list

263
00:13:18.123 --> 00:13:20.239
This applies to other cases as well

264
00:13:20.239 --> 00:13:23.647
As a result, you can see

265
00:13:23.647 --> 00:13:29.052
that small-radius objects,

266
00:13:29.052 --> 00:13:30.664
are not added

267
00:13:30.664 --> 00:13:32.709
to the higher nodes

268
00:13:32.709 --> 00:13:35.780
All items are placed in the lower nodes

269
00:13:35.780 --> 00:13:39.734
In the case of this object, if it were implemented with a standard quadtree

270
00:13:39.734 --> 00:13:42.105
it would have been placed in the root node

271
00:13:42.105 --> 00:13:45.034
But now, you can see it’s placed in this node instead

272
00:13:46.618 --> 00:13:49.036
Now, let’s take a look at

273
00:13:49.036 --> 00:13:51.604
the distribution statistics for each case

274
00:13:55.440 --> 00:13:57.878
Let’s rerun it

275
00:13:57.878 --> 00:13:59.799
press the first button,

276
00:13:59.799 --> 00:14:02.010
and then press the second button

277
00:14:02.010 --> 00:14:03.979
When you press the second button

278
00:14:03.979 --> 00:14:08.870
the related statistics will appear in the Console window

279
00:14:08.870 --> 00:14:11.280
It displays the nodes

280
00:14:11.280 --> 00:14:15.119
As you can see here,

281
00:14:15.119 --> 00:14:16.968
 the first root node

282
00:14:16.968 --> 00:14:18.621
which is at depth 0

283
00:14:18.621 --> 00:14:22.808
and the nodes at the first, second, third, fourth, and fifth depths

284
00:14:22.808 --> 00:14:25.902
show objects

285
00:14:25.902 --> 00:14:29.840
distributed evenly across them

286
00:14:29.840 --> 00:14:33.497
Since all the objects are the same size,

287
00:14:33.497 --> 00:14:36.195
this even distribution

288
00:14:36.195 --> 00:14:38.325
as searches require

289
00:14:38.325 --> 00:14:40.619
jumping around nodes,

290
00:14:40.619 --> 00:14:43.559
can actually hinder performance

291
00:14:43.559 --> 00:14:45.715
Now, let’s look at the second case

292
00:14:53.396 --> 00:14:56.084
Using the loose quadtree,

293
00:14:56.084 --> 00:14:58.206
let’s examine the statistics

294
00:14:58.206 --> 00:15:00.086
Looking at the statistics,

295
00:15:00.086 --> 00:15:04.582
the first, second, third, and fourth depths can be ignored,

296
00:15:04.582 --> 00:15:07.210
and you can see that

297
00:15:07.210 --> 00:15:10.013
all the objects are added

298
00:15:10.013 --> 00:15:11.557
to the fifth depth

299
00:15:14.164 --> 00:15:16.963
Next, I’ll explain how the loose quadtree

300
00:15:16.963 --> 00:15:19.817
is implemented by looking at the code

301
00:15:19.817 --> 00:15:21.748
I will explain this

302
00:15:21.748 --> 00:15:24.222
The loose quadtree classes

303
00:15:24.222 --> 00:15:27.797
are prefixed with LQ

304
00:15:27.797 --> 00:15:31.005
Let’s first examine the Quadtree Manager

305
00:15:31.005 --> 00:15:34.651
Open the LooseQuadtree project

306
00:15:34.651 --> 00:15:39.441
and look at the LQuadtreeManager script

307
00:15:39.441 --> 00:15:44.936
The overall code is very similar to what we covered in the previous lecture

308
00:15:44.936 --> 00:15:48.702
However, the way nodes are added

309
00:15:48.702 --> 00:15:52.194
is slightly different

310
00:15:52.194 --> 00:15:54.310
As mentioned earlier,

311
00:15:54.310 --> 00:15:56.713
when implementing a loose quadtree

312
00:15:56.713 --> 00:16:00.026
you first determine the depth information

313
00:16:00.026 --> 00:16:03.603
and then decide on the quadrant information

314
00:16:03.603 --> 00:16:07.411
by comparing it to the center

315
00:16:07.411 --> 00:16:08.295
before adding the object

316
00:16:08.295 --> 00:16:11.991
Thus, there aren’t many changes

317
00:16:11.991 --> 00:16:14.880
to the Quadtree Manager itself

318
00:16:14.880 --> 00:16:20.776
The differences lie mainly in the Insert function

319
00:16:20.776 --> 00:16:23.840
of the LQNode class

320
00:16:23.840 --> 00:16:26.484
On the quadtree

321
00:16:26.484 --> 00:16:29.184
when you call the Insert function

322
00:16:29.184 --> 00:16:31.840
instead of directly running the Insert function,

323
00:16:31.840 --> 00:16:35.345
I’ve modified the code to execute a function called InsertAtDepth

324
00:16:35.345 --> 00:16:38.226
on the root node

325
00:16:38.226 --> 00:16:41.057
This function calls another function, GetTargetDepth,

326
00:16:41.057 --> 00:16:44.834
to determine the added region

327
00:16:44.834 --> 00:16:48.691
and pass the corresponding depth value for the AABB region

328
00:16:48.691 --> 00:16:52.733
as the second parameter

329
00:16:52.733 --> 00:16:54.566
So, let’s take a look at how the GetTargetDepth function

330
00:16:54.566 --> 00:16:57.366
is implemented

331
00:16:57.366 --> 00:17:01.067
First, I retrieve the side length of the root node,

332
00:17:01.067 --> 00:17:05.634
referred to as W

333
00:17:05.634 --> 00:17:09.597
Next, I find the larger value

334
00:17:09.597 --> 00:17:14.259
between the x and y dimensions of the item’s bounding volume

335
00:17:14.259 --> 00:17:16.734
Instead of using the size,

336
00:17:16.734 --> 00:17:19.058
I use the extents

337
00:17:19.058 --> 00:17:23.031
which represent half the side length

338
00:17:23.031 --> 00:17:26.823
I named this variable maxHalfValue

339
00:17:26.823 --> 00:17:30.108
Using this maxHalfValue,

340
00:17:30.108 --> 00:17:33.634
I divide it by the side length of the root node

341
00:17:33.634 --> 00:17:36.646
apply a log, and calculate the result

342
00:17:36.646 --> 00:17:41.660
Then, as mentioned earlier, I round it down to an integer

343
00:17:41.660 --> 00:17:44.051
This gives us the appropriate

344
00:17:44.051 --> 00:17:47.636
targetDepth for the object

345
00:17:47.636 --> 00:17:51.877
If the targetDepth is too large

346
00:17:51.877 --> 00:17:55.059
I cap it

347
00:17:55.059 --> 00:17:57.113
at the maximum depth

348
00:17:57.113 --> 00:18:00.461
The obtained targetDepth value

349
00:18:00.461 --> 00:18:02.714
is passed as the second argument

350
00:18:02.714 --> 00:18:06.222
when adding it to the root node

351
00:18:06.222 --> 00:18:09.125
Here, there’s no need to compare each node individually

352
00:18:09.125 --> 00:18:11.303
You just need to check

353
00:18:11.303 --> 00:18:13.948
whether the current node

354
00:18:13.948 --> 00:18:16.848
matches the targetDepth

355
00:18:16.848 --> 00:18:18.274
You just need to check that

356
00:18:18.274 --> 00:18:21.424
As the depth increases downward

357
00:18:21.424 --> 00:18:23.490
if the current node’s depth

358
00:18:23.490 --> 00:18:27.333
is less than the target depth

359
00:18:27.333 --> 00:18:32.137
you simply divide it

360
00:18:32.137 --> 00:18:34.561
and recursively call the function for the relevant region

361
00:18:34.561 --> 00:18:36.859
This recursion continues

362
00:18:36.859 --> 00:18:41.315
until it reaches the specified child depth

363
00:18:41.315 --> 00:18:44.721
At that point, you just add the object to the appropriate region

364
00:18:47.424 --> 00:18:51.582
In fact, the implementation becomes simpler this way

365
00:18:53.434 --> 00:18:56.800
The remaining functionality is nearly identical

366
00:18:56.800 --> 00:19:00.196
Next, I’ll briefly explain the functionality used

367
00:19:00.196 --> 00:19:02.988
for generating statistics

368
00:19:02.988 --> 00:19:05.592
To generate statistics,

369
00:19:05.592 --> 00:19:08.959
I implemented a function called Stat

370
00:19:08.959 --> 00:19:11.583
I created this Stat function,

371
00:19:11.583 --> 00:19:13.619
This Stat function

372
00:19:13.619 --> 00:19:17.576
is bound to buttons in the Unity project

373
00:19:17.576 --> 00:19:20.781
Each button is linked to this function

374
00:19:20.781 --> 00:19:22.435
Looking at the Stat function,

375
00:19:22.435 --> 00:19:25.289
the second button in the QuadTreeManager is linked to

376
00:19:25.289 --> 00:19:28.939
the Stat function of the standard Quadtree Manager

377
00:19:28.939 --> 00:19:30.666
Meanwhile, the fourth button

378
00:19:30.666 --> 00:19:34.277
is linked to the Stat function of the LooseQuadtree Manager

379
00:19:34.277 --> 00:19:38.465
Since both implementations are identical

380
00:19:38.465 --> 00:19:42.119
I’ll explain using the LooseQuadtree code

381
00:19:42.119 --> 00:19:47.456
I declared a dictionary map structure

382
00:19:47.456 --> 00:19:53.119
where the key is an integer and the value is a list of nodes

383
00:19:53.119 --> 00:19:55.619
This map contains

384
00:19:55.619 --> 00:19:57.924
key-value pair objects

385
00:19:57.924 --> 00:20:00.359
I named it allNodes

386
00:20:00.359 --> 00:20:02.190
On the quadtree root

387
00:20:02.190 --> 00:20:05.240
I call a function named GetAllNodes

388
00:20:05.240 --> 00:20:08.280
to retrieve the list

389
00:20:08.280 --> 00:20:10.458
Here, after retrieving all values,

390
00:20:10.458 --> 00:20:14.181
I concatenate strings based on their depths

391
00:20:14.181 --> 00:20:18.226
Each depth is represented by one line

392
00:20:18.226 --> 00:20:21.844
showing how many nodes exist at that depth

393
00:20:21.844 --> 00:20:24.871
and how many objects are within them

394
00:20:24.871 --> 00:20:27.646
This function generates these statistics

395
00:20:27.646 --> 00:20:30.254
The GetAllNodes function, which retrieves all nodes

396
00:20:30.254 --> 00:20:34.964
is the core logic here

397
00:20:34.964 --> 00:20:38.479
Pressing F12 to navigate to it,

398
00:20:38.479 --> 00:20:43.677
this function also creates a dictionary named allNodes

399
00:20:43.677 --> 00:20:47.984
It then calls a function named CollectAllNodes on the root node

400
00:20:47.984 --> 00:20:51.637
The role of the CollectAllNodes function is to

401
00:20:51.637 --> 00:20:57.245
continuously add itself

402
00:20:57.245 --> 00:20:58.599
and all its child nodes

403
00:20:58.599 --> 00:21:04.322
So, the number of items in each node

404
00:21:04.322 --> 00:21:05.650
is retrieved for all nodes

405
00:21:05.650 --> 00:21:08.807
through recursive calls, and then

406
00:21:08.807 --> 00:21:11.910
strings are concatenated in the manager

407
00:21:11.910 --> 00:21:13.757
to generate statistics

408
00:21:14.519 --> 00:21:18.251
Octree Overview and Implementation

409
00:21:18.503 --> 00:21:22.641
The octree can be considered an extended version of the quadtree

410
00:21:22.641 --> 00:21:27.027
While the quadtree divides a 2D space

411
00:21:27.027 --> 00:21:28.735
the octree extends this concept

412
00:21:28.735 --> 00:21:32.364
to divide a 3D space

413
00:21:32.364 --> 00:21:34.237
To describe 3D space division

414
00:21:34.237 --> 00:21:37.067
the term "octree" was first used by

415
00:21:37.067 --> 00:21:41.056
Donald Meagher in his 1980 paper,

416
00:21:41.056 --> 00:21:43.710
Octree Encoding

417
00:21:43.710 --> 00:21:46.944
Below is a comparison image

418
00:21:46.944 --> 00:21:48.851
of an octree and a quadtree

419
00:21:48.851 --> 00:21:50.355
As you can see, the quadtree

420
00:21:50.355 --> 00:21:53.088
has a square structure

421
00:21:53.088 --> 00:21:55.940
while the octree has a cubic shape

422
00:21:58.544 --> 00:22:00.731
If you’ve understood the quadtree

423
00:22:00.731 --> 00:22:02.729
understanding the octree

424
00:22:02.729 --> 00:22:04.484
won’t be too challenging

425
00:22:04.484 --> 00:22:07.435
The implementation methods are largely the same

426
00:22:07.435 --> 00:22:11.792
The key difference is that the quadtree

427
00:22:11.792 --> 00:22:15.762
uses 2 axes and divides into 4 regions,

428
00:22:15.762 --> 00:22:17.917
while the octree operates in 3D

429
00:22:17.917 --> 00:22:19.881
using 3 axes

430
00:22:19.881 --> 00:22:23.673
and dividing into 8 regions, not 4

431
00:22:23.673 --> 00:22:26.264
These 8 regions here

432
00:22:26.264 --> 00:22:29.831
are divided into upper and lower sections

433
00:22:29.831 --> 00:22:32.898
Think of it as having two quadtrees stacked vertically

434
00:22:32.898 --> 00:22:35.744
which might make it easier to understand

435
00:22:35.744 --> 00:22:37.380
This octree can also

436
00:22:37.380 --> 00:22:39.355
utilize the loose quadtree method

437
00:22:39.355 --> 00:22:41.793
described earlier

438
00:22:43.457 --> 00:22:46.551
Octrees expand the 2D volume

439
00:22:46.551 --> 00:22:51.051
into 3D volume regions

440
00:22:51.051 --> 00:22:53.572
However, using 3D graphics doesn’t always

441
00:22:53.572 --> 00:22:56.467
necessitate using octrees

442
00:22:56.467 --> 00:22:58.768
For example, when creating

443
00:22:58.768 --> 00:23:01.549
a terrain system like the one below

444
00:23:01.549 --> 00:23:06.677
and applying effective spatial partitioning

445
00:23:06.677 --> 00:23:08.903
the height of the terrain

446
00:23:08.903 --> 00:23:12.192
is constrained by the height map

447
00:23:12.192 --> 00:23:14.431
so instead of using octrees,

448
00:23:14.431 --> 00:23:16.539
it’s more common to treat it as a plane

449
00:23:16.539 --> 00:23:20.133
and use quadtrees for division

450
00:23:24.312 --> 00:23:26.306
When building an octree

451
00:23:26.306 --> 00:23:29.006
8 child nodes are used

452
00:23:29.006 --> 00:23:31.004
Having this many child nodes

453
00:23:31.004 --> 00:23:33.768
can significantly increase memory usage

454
00:23:33.768 --> 00:23:37.501
requiring more optimization compared to quadtrees

455
00:23:37.501 --> 00:23:40.165
Octrees can also be used to determine ranges

456
00:23:40.165 --> 00:23:42.619
within a 3D space

457
00:23:42.619 --> 00:23:46.738
They are also utilized for encoding and compressing data

458
00:23:46.738 --> 00:23:50.332
In such cases, the octree manages

459
00:23:50.332 --> 00:23:52.353
points instead of ranges

460
00:23:52.353 --> 00:23:54.423
and these points

461
00:23:54.423 --> 00:23:57.719
in 3D space are referred to as voxels

462
00:23:57.719 --> 00:24:00.630
When managing voxels with an octree

463
00:24:00.630 --> 00:24:04.868
unnecessary regions are omitted and only the detailed regions are stored

464
00:24:04.868 --> 00:24:07.024
using a method that unevenly

465
00:24:07.024 --> 00:24:09.967
compresses data

466
00:24:09.967 --> 00:24:13.868
This is called a Sparse Voxel Octree

467
00:24:13.868 --> 00:24:17.494
This data structure is used in ray tracing algorithms

468
00:24:17.494 --> 00:24:20.095
and for implementing LOD in voxel-based

469
00:24:20.095 --> 00:24:22.910
terrain systems

470
00:24:22.910 --> 00:24:25.613
Now, let’s briefly examine

471
00:24:25.613 --> 00:24:28.486
how quadtrees and octrees can be used

472
00:24:28.486 --> 00:24:29.979
as compression algorithms

473
00:24:31.999 --> 00:24:36.425
As you can see, the original image in the upper-left corner

474
00:24:36.425 --> 00:24:40.274
can be encoded into the lower image using a quadtree

475
00:24:40.274 --> 00:24:41.872
like shown

476
00:24:41.872 --> 00:24:47.139
Through this video, we’ll explore the process directly

477
00:24:47.139 --> 00:24:51.040
As the quadtree divides the image

478
00:24:51.040 --> 00:24:53.921
you can see that identical colors

479
00:24:53.921 --> 00:24:57.842
are assigned to uniform pixel regions

480
00:24:57.842 --> 00:25:00.293
As the image depth increases,

481
00:25:00.293 --> 00:25:03.684
more detailed images are generated

482
00:25:03.684 --> 00:25:06.832
resulting in a closer approximation of the original image

483
00:25:06.832 --> 00:25:09.368
The example shown here

484
00:25:09.368 --> 00:25:12.466
demonstrates 2D image compression

485
00:25:12.466 --> 00:25:15.694
For instance, if there’s a 3D voxel terrain system

486
00:25:15.694 --> 00:25:17.825
a similar method can be used

487
00:25:17.825 --> 00:25:20.645
to build an LOD system

488
00:25:20.645 --> 00:25:23.387
With this, we conclude the explanation of octrees

489
00:25:23.387 --> 00:25:26.272
Next, we’ll look at

490
00:25:26.272 --> 00:25:28.516
how the quadtree source code

491
00:25:28.516 --> 00:25:32.882
was extended to implement octrees in a project

492
00:25:36.021 --> 00:25:39.070
Open the prepared sample project

493
00:25:39.070 --> 00:25:40.856
and navigate to the folder labeled

494
00:25:40.856 --> 00:25:43.844
3_Octree under the Scenes folder

495
00:25:43.844 --> 00:25:48.765
Double-click the Octree Insert scene to open it

496
00:25:48.765 --> 00:25:52.052
Since this expands into 3D space,

497
00:25:52.052 --> 00:25:57.032
you can press the 2D button to see the root node’s area

498
00:25:57.032 --> 00:26:01.032
drawn as a cube

499
00:26:01.032 --> 00:26:03.814
Press the play button

500
00:26:06.599 --> 00:26:09.153
to add the insert items

501
00:26:09.153 --> 00:26:11.164
here one by one

502
00:26:11.164 --> 00:26:17.520
The distribution has been adjusted to spread across the 3D space

503
00:26:17.520 --> 00:26:20.015
and when you press the insert button

504
00:26:20.015 --> 00:26:25.728
the first object is inserted

505
00:26:25.728 --> 00:26:29.579
and as you can see, the 3D space is further divided

506
00:26:29.579 --> 00:26:33.116
to accommodate the overlapping parts

507
00:26:33.116 --> 00:26:36.621
of this node

508
00:26:36.621 --> 00:26:40.937
Next, if you insert another item here

509
00:26:40.937 --> 00:26:44.066
you can see that since it overlaps the boundary,

510
00:26:44.066 --> 00:26:47.512
it follows the standard implementation method

511
00:26:47.512 --> 00:26:51.086
You can see it has been added to the root node

512
00:26:51.086 --> 00:26:55.344
In this way, let’s add a total of 9 items

513
00:26:55.344 --> 00:26:57.661
as game objects

514
00:26:59.483 --> 00:27:02.839
In this case as well, since it overlapped the boundary

515
00:27:02.839 --> 00:27:04.839
it was added either at the first depth

516
00:27:04.839 --> 00:27:07.522
or the root node

517
00:27:07.522 --> 00:27:09.321
It was added at the first depth here,

518
00:27:09.321 --> 00:27:10.675
and you can see it added

519
00:27:10.675 --> 00:27:12.344
at the root node there

520
00:27:14.690 --> 00:27:17.339
Thus, implementation methods

521
00:27:17.339 --> 00:27:19.562
can be expanded further as needed

522
00:27:19.562 --> 00:27:21.879
so it’s not particularly difficult

523
00:27:21.879 --> 00:27:24.205
If you fully understand quadtrees,

524
00:27:24.205 --> 00:27:27.059
implementing octrees should also be straightforward

525
00:27:27.059 --> 00:27:28.707
Let’s first look at how

526
00:27:28.707 --> 00:27:31.079
it was implemented through the project

527
00:27:34.109 --> 00:27:37.564
For the octree solution, open the second project

528
00:27:37.564 --> 00:27:40.495
and open the Octree Manager

529
00:27:40.495 --> 00:27:46.307
to check only the differences

530
00:27:46.307 --> 00:27:49.813
Since it’s a 3D space, of course

531
00:27:49.813 --> 00:27:53.091
the totalArea member variable

532
00:27:53.091 --> 00:27:59.140
was extended using Vector3 to define the cubic area

533
00:28:01.279 --> 00:28:06.526
The other parts don’t differ much

534
00:28:06.526 --> 00:28:10.655
For the rendering part,  for the 3D space

535
00:28:10.655 --> 00:28:14.516
the main difference is using Vector3

536
00:28:14.516 --> 00:28:18.362
Even the object that handles the actual octree operations

537
00:28:18.362 --> 00:28:19.796
is nearly the same

538
00:28:19.796 --> 00:28:21.746
So there’s no difference there

539
00:28:21.746 --> 00:28:24.735
The differences lie in the nodes,

540
00:28:24.735 --> 00:28:28.606
specifically in the Onode.cs file

541
00:28:28.606 --> 00:28:31.115
where, as explained earlier,

542
00:28:31.115 --> 00:28:33.685
it is divided into 8 nodes

543
00:28:33.685 --> 00:28:38.124
Thus, enumeration values for the 8 nodes

544
00:28:38.124 --> 00:28:40.715
need to be defined

545
00:28:40.715 --> 00:28:43.765
and their order must be carefully assigned

546
00:28:43.765 --> 00:28:45.129
Top and Bottom

547
00:28:45.129 --> 00:28:49.578
were previously described as two stacked quadtrees

548
00:28:49.578 --> 00:28:52.043
So, there are 4 nodes for the Top

549
00:28:52.043 --> 00:28:54.063
and 4 for the Bottom

550
00:28:54.063 --> 00:28:57.278
The order is the same: TopUpperLeft, UpperRight

551
00:28:57.278 --> 00:28:59.400
LowerRight, LowerLeft

552
00:28:59.400 --> 00:29:03.776
The octree was implemented using this sequence

553
00:29:06.162 --> 00:29:08.776
When implementing the octree

554
00:29:08.776 --> 00:29:11.696
the previously used GetQuads function

555
00:29:11.696 --> 00:29:14.600
was replaced with GetOctants

556
00:29:14.600 --> 00:29:21.878
Here, netZ and pasZ were added

557
00:29:21.878 --> 00:29:23.718
to identify all

558
00:29:23.718 --> 00:29:28.026
8 overlapping regions, as shown

559
00:29:28.026 --> 00:29:30.719
The original function was expanded

560
00:29:30.719 --> 00:29:34.734
Using the GetOctants function,

561
00:29:34.734 --> 00:29:38.422
the lists obtained

562
00:29:38.422 --> 00:29:41.939
indicate full inclusion if there’s only one region

563
00:29:41.939 --> 00:29:44.735
and the function continues to add

564
00:29:44.735 --> 00:29:47.651
recursively to that included region

565
00:29:47.651 --> 00:29:52.592
In the Insert function, recursive additions continue

566
00:29:52.592 --> 00:29:57.612
For the Split function, it should divide into 8 parts

567
00:29:57.612 --> 00:29:59.800
When splitting into 8 parts

568
00:30:01.295 --> 00:30:05.946
follow the previously described enumeration order

569
00:30:05.946 --> 00:30:07.285
to add them to the array

570
00:30:07.285 --> 00:30:11.028
For example, in the case of TopUpperLeft,

571
00:30:11.028 --> 00:30:16.474
since the bounding size is generally positive

572
00:30:16.474 --> 00:30:20.959
you only need to set x to negative to get TopUpperLeft

573
00:30:20.959 --> 00:30:23.464
If the z-value remains unchanged,

574
00:30:23.464 --> 00:30:27.830
it will belong to the top quadtree

575
00:30:27.830 --> 00:30:30.137
so the existing logic can be reused as is

576
00:30:30.137 --> 00:30:34.810
So, change the negative x back to positive,

577
00:30:34.810 --> 00:30:37.772
then modify the y-value

578
00:30:37.772 --> 00:30:40.317
and then modify the x-value again

579
00:30:40.317 --> 00:30:44.139
to complete the top quadtree

580
00:30:44.139 --> 00:30:46.782
Next, we need to move downward

581
00:30:46.782 --> 00:30:51.772
To do this, reverse the y and z values once

582
00:30:51.772 --> 00:30:54.531
to create the area for BottomUpperLeft

583
00:30:54.531 --> 00:30:55.812
We can create this area

584
00:30:55.812 --> 00:30:59.961
Here, follow the same sequence as the top quadtree

585
00:30:59.961 --> 00:31:03.169
to create the bottom quadtree

586
00:31:03.169 --> 00:31:05.042
By adding nodes this way

587
00:31:05.042 --> 00:31:07.528
you can implement the octree

588
00:31:11.488 --> 00:31:14.349
Next, let’s immediately look into

589
00:31:14.349 --> 00:31:17.528
how to perform queries

590
00:31:19.716 --> 00:31:23.627
Double-click the second Octree Query scene in the Scenes folder

591
00:31:23.627 --> 00:31:26.419
to open it

592
00:31:26.419 --> 00:31:28.746
We’ll proceed with the query scene

593
00:31:28.746 --> 00:31:31.795
Here, as you can see,

594
00:31:31.795 --> 00:31:36.518
we have designated three regions in 3D space

595
00:31:36.518 --> 00:31:40.013
These three regions have been prepared in advance

596
00:31:40.013 --> 00:31:44.588
to check how these regions overlap with the 9 objects added earlier

597
00:31:44.588 --> 00:31:47.885
and we’ll use the Query button

598
00:31:47.885 --> 00:31:50.251
Let us check

599
00:31:50.251 --> 00:31:52.825
When you press the play button

600
00:31:52.825 --> 00:31:57.112
all 9 objects

601
00:31:57.112 --> 00:31:59.238
9 objects will be inserted at the start

602
00:31:59.238 --> 00:32:03.584
Here, we’ll check how the region marked in red

603
00:32:03.584 --> 00:32:06.317
which is the first Query region

604
00:32:06.317 --> 00:32:09.386
overlaps

605
00:32:09.386 --> 00:32:11.921
by using the Query button

606
00:32:11.921 --> 00:32:14.564
When you press the Query button

607
00:32:14.564 --> 00:32:16.594
the current region is highlighted in yellow

608
00:32:16.911 --> 00:32:20.970
and the AABB regions of the game objects

609
00:32:20.970 --> 00:32:23.958
inside it are marked in purple

610
00:32:23.958 --> 00:32:27.413
To search within that region,

611
00:32:27.413 --> 00:32:31.463
all possible nodes related to the yellow region

612
00:32:31.463 --> 00:32:33.443
these nodes

613
00:32:33.443 --> 00:32:36.849
are marked in purple, as can be seen

614
00:32:36.849 --> 00:32:39.988
Next, let’s check the second region

615
00:32:39.988 --> 00:32:42.176
When you press the Query button

616
00:32:42.176 --> 00:32:45.176
the overlapping areas are evaluated

617
00:32:45.176 --> 00:32:47.899
and the same structure is created

618
00:32:47.899 --> 00:32:51.370
You can see the third region

619
00:32:51.370 --> 00:32:53.965
 being processed similarly

620
00:32:59.420 --> 00:33:01.440
This functionality

621
00:33:01.440 --> 00:33:05.054
was essentially explained earlier with the quadtree

622
00:33:05.054 --> 00:33:08.648
The Query function

623
00:33:08.648 --> 00:33:10.994
is identical to the one in the quadtree

624
00:33:10.994 --> 00:33:13.430
In the case of queries,

625
00:33:13.430 --> 00:33:15.232
it’s exactly the same as in quadtrees

626
00:33:15.232 --> 00:33:20.475
just with an increased number of nodes

627
00:33:20.475 --> 00:33:26.049
Therefore, refer to the second lecture video

628
00:33:26.049 --> 00:33:28.891
where I explained this in detail

629
00:33:28.891 --> 00:33:30.435
and compare it

630
00:33:30.435 --> 00:33:34.000
with the code provided here

631
00:33:34.000 --> 00:33:37.079
to understand how it was implemented

632
00:33:37.079 --> 00:33:40.059
without much difficulty

633
00:33:41.228 --> 00:33:43.247
That concludes this lecture

634
00:33:43.247 --> 00:33:45.208
Thank you for your attention

635
00:33:45.208 --> 00:33:46.079
Thank you

636
00:33:46.845 --> 00:33:48.853
Summary
ptimization techniques for quadtrees
Implementation method of standard quadtree
Objects with same range may be placed in different depth nodes

637
00:33:48.853 --> 00:33:50.604
When multiple objects overlap in a quadrant region,
unnecessary searches occur in the root node

638
00:33:50.604 --> 00:33:52.211
Loose quadtree
Solves the Sticky Planes problem by expanding area of each subdivided quadrant
L depth=k 2depth/W to define loose areas

639
00:33:52.211 --> 00:33:53.899
Using k=2 is standard
loose quadtree structure provides uniform depth values
1. Calculate depth based on object size

640
00:33:53.899 --> 00:33:55.434
Depth is determined only if object's radius is smaller than 1/4 of side length
For every halving of object’s radius, add one depth level

641
00:33:55.434 --> 00:33:56.835
Once the depth is confirmed, calculate the object's center to determine its quadrant

642
00:33:56.845 --> 00:33:59.245
Overview of Octree
Method of extending quadtree to divide 3D space
Octree space partitioning method
Overall identical to the quadtree

643
00:33:59.245 --> 00:34:02.241
Divides into 8 regions, 2 quadtrees for top and bottom sections
Applications of Octree Algorithm
For encoding points in space
For point data managemen

644
00:34:02.241 --> 00:34:05.100
Ray tracing algorithm
LOD implement for voxel-based 3D terrain system
Used as compression algorithm
For compressing point dat

645
00:34:05.100 --> 00:34:06.815
Compresses image data to pixel data at required depths
Uses an octree structure in voxel terrain systems to build an LOD system