1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
#include "quad_tree_lod.h"
namespace godot {
void QuadTreeLod::set_callbacks(Ref<FuncRef> make_cb, Ref<FuncRef> recycle_cb, Ref<FuncRef> vbounds_cb) {
_make_func = make_cb;
_recycle_func = recycle_cb;
_vertical_bounds_func = vbounds_cb;
}
int QuadTreeLod::get_lod_count() {
// TODO make this a count, not max
return _max_depth + 1;
}
int QuadTreeLod::get_lod_factor(int lod) {
return 1 << lod;
}
int QuadTreeLod::compute_lod_count(int base_size, int full_size) {
int po = 0;
while (full_size > base_size) {
full_size = full_size >> 1;
po += 1;
}
return po;
}
// The higher, the longer LODs will spread and higher the quality.
// The lower, the shorter LODs will spread and lower the quality.
void QuadTreeLod::set_split_scale(real_t p_split_scale) {
real_t MIN = 2.0f;
real_t MAX = 5.0f;
// Split scale must be greater than a threshold,
// otherwise lods will decimate too fast and it will look messy
if (p_split_scale < MIN)
p_split_scale = MIN;
if (p_split_scale > MAX)
p_split_scale = MAX;
_split_scale = p_split_scale;
}
real_t QuadTreeLod::get_split_scale() {
return _split_scale;
}
void QuadTreeLod::clear() {
_join_all_recursively(ROOT, _max_depth);
_max_depth = 0;
_base_size = 0;
}
void QuadTreeLod::create_from_sizes(int base_size, int full_size) {
clear();
_base_size = base_size;
_max_depth = compute_lod_count(base_size, full_size);
// Total qty of nodes is (N^L - 1) / (N - 1). -1 for root, where N=num children, L=levels including the root
int node_count = ((static_cast<int>(pow(4, _max_depth+1)) - 1) / (4 - 1)) - 1;
_node_pool.resize(node_count); // e.g. ((4^6 -1) / 3 ) - 1 = 1364 excluding root
_free_indices.resize((node_count / 4)); // 1364 / 4 = 341
for (int i = 0; i < _free_indices.size(); i++) // i = 0 to 340, *4 = 0 to 1360
_free_indices[i] = 4 * i; // _node_pool[4*0 + i0] is first child, [4*340 + i3] is last
}
void QuadTreeLod::update(Vector3 view_pos) {
_update(ROOT, _max_depth, view_pos);
// This makes sure we keep seeing the lowest LOD,
// if the tree is cleared while we are far away
Quad *root = _get_root();
if (!root->has_children() && root->is_null())
root->set_data(_make_chunk(_max_depth, 0, 0));
}
void QuadTreeLod::debug_draw_tree(CanvasItem *ci) {
if (ci != nullptr)
_debug_draw_tree_recursive(ci, ROOT, _max_depth, 0);
}
// Intention is to only clear references to children
void QuadTreeLod::_clear_children(unsigned int index) {
Quad *quad = _get_node(index);
if (quad->has_children()) {
_recycle_children(quad->first_child);
quad->first_child = NO_CHILDREN;
}
}
// Returns the index of the first_child. Allocates from _free_indices.
unsigned int QuadTreeLod::_allocate_children() {
if (_free_indices.size() == 0) {
return NO_CHILDREN;
}
unsigned int i0 = _free_indices[_free_indices.size() - 1];
_free_indices.pop_back();
return i0;
}
// Pass the first_child index, not the parent index. Stores back in _free_indices.
void QuadTreeLod::_recycle_children(unsigned int i0) {
// Debug check, there is no use case in recycling a node which is not a first child
CRASH_COND(i0 % 4 != 0);
for (int i = 0; i < 4; ++i) {
_node_pool[i0 + i].init();
}
_free_indices.push_back(i0);
}
Variant QuadTreeLod::_make_chunk(int lod, int origin_x, int origin_y) {
if (_make_func.is_valid()) {
return _make_func->call_func(origin_x, origin_y, lod);
} else {
return Variant();
}
}
void QuadTreeLod::_recycle_chunk(unsigned int quad_index, int lod) {
Quad *quad = _get_node(quad_index);
if (_recycle_func.is_valid()) {
_recycle_func->call_func(quad->get_data(), quad->origin_x, quad->origin_y, lod);
}
}
void QuadTreeLod::_join_all_recursively(unsigned int quad_index, int lod) {
Quad *quad = _get_node(quad_index);
if (quad->has_children()) {
for (int i = 0; i < 4; i++) {
_join_all_recursively(quad->first_child + i, lod - 1);
}
_clear_children(quad_index);
} else if (quad->is_valid()) {
_recycle_chunk(quad_index, lod);
quad->clear_data();
}
}
void QuadTreeLod::_update(unsigned int quad_index, int lod, Vector3 view_pos) {
// This function should be called regularly over frames.
Quad *quad = _get_node(quad_index);
int lod_factor = get_lod_factor(lod);
int chunk_size = _base_size * lod_factor;
Vector3 world_center = static_cast<real_t>(chunk_size) * (Vector3(static_cast<real_t>(quad->origin_x), 0.f, static_cast<real_t>(quad->origin_y)) + Vector3(0.5f, 0.f, 0.5f));
if (_vertical_bounds_func.is_valid()) {
Variant result = _vertical_bounds_func->call_func(quad->origin_x, quad->origin_y, lod);
ERR_FAIL_COND(result.get_type() != Variant::VECTOR2);
Vector2 vbounds = static_cast<Vector2>(result);
world_center.y = (vbounds.x + vbounds.y) / 2.0f;
}
int split_distance = _base_size * lod_factor * static_cast<int>(_split_scale);
if (!quad->has_children()) {
if (lod > 0 && world_center.distance_to(view_pos) < split_distance) {
// Split
unsigned int new_idx = _allocate_children();
ERR_FAIL_COND(new_idx == NO_CHILDREN);
quad->first_child = new_idx;
for (int i = 0; i < 4; i++) {
Quad *child = _get_node(quad->first_child + i);
child->origin_x = quad->origin_x * 2 + (i & 1);
child->origin_y = quad->origin_y * 2 + ((i & 2) >> 1);
child->set_data(_make_chunk(lod - 1, child->origin_x, child->origin_y));
// If the quad needs to split more, we'll ask more recycling...
}
if (quad->is_valid()) {
_recycle_chunk(quad_index, lod);
quad->clear_data();
}
}
} else {
bool no_split_child = true;
for (int i = 0; i < 4; i++) {
_update(quad->first_child + i, lod - 1, view_pos);
if (_get_node(quad->first_child + i)->has_children())
no_split_child = false;
}
if (no_split_child && world_center.distance_to(view_pos) > split_distance) {
// Join
for (int i = 0; i < 4; i++) {
_recycle_chunk(quad->first_child + i, lod - 1);
}
_clear_children(quad_index);
quad->set_data(_make_chunk(lod, quad->origin_x, quad->origin_y));
}
}
} // _update
void QuadTreeLod::_debug_draw_tree_recursive(CanvasItem *ci, unsigned int quad_index, int lod_index, int child_index) {
Quad *quad = _get_node(quad_index);
if (quad->has_children()) {
int ch_index = quad->first_child;
for (int i = 0; i < 4; i++) {
_debug_draw_tree_recursive(ci, ch_index + i, lod_index - 1, i);
}
} else {
real_t size = static_cast<real_t>(get_lod_factor(lod_index));
int checker = 0;
if (child_index == 1 || child_index == 2)
checker = 1;
int chunk_indicator = 0;
if (quad->is_valid())
chunk_indicator = 1;
Rect2 rect2(Vector2(static_cast<real_t>(quad->origin_x), static_cast<real_t>(quad->origin_y)) * size,
Vector2(size, size));
Color color(1.0f - static_cast<real_t>(lod_index) * 0.2f, 0.2f * static_cast<real_t>(checker), static_cast<real_t>(chunk_indicator), 1.0f);
ci->draw_rect(rect2, color);
}
}
void QuadTreeLod::_register_methods() {
register_method("set_callbacks", &QuadTreeLod::set_callbacks);
register_method("get_lod_count", &QuadTreeLod::get_lod_count);
register_method("get_lod_factor", &QuadTreeLod::get_lod_factor);
register_method("compute_lod_count", &QuadTreeLod::compute_lod_count);
register_method("set_split_scale", &QuadTreeLod::set_split_scale);
register_method("get_split_scale", &QuadTreeLod::get_split_scale);
register_method("clear", &QuadTreeLod::clear);
register_method("create_from_sizes", &QuadTreeLod::create_from_sizes);
register_method("update", &QuadTreeLod::update);
register_method("debug_draw_tree", &QuadTreeLod::debug_draw_tree);
}
} // namespace godot
|
zaaarf