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
|
@tool
# Independent quad tree designed to handle LOD
class HT_QTLQuad:
# Optional array of 4 HT_QTLQuad
var children = null
# TODO Use Vector2i
var origin_x : int = 0
var origin_y : int = 0
var data = null
func _init():
pass
func clear():
clear_children()
data = null
func clear_children():
children = null
func has_children() -> bool:
return children != null
var _tree := HT_QTLQuad.new()
var _max_depth : int = 0
var _base_size : int = 16
var _split_scale : float = 2.0
var _make_func : Callable
var _recycle_func : Callable
var _vertical_bounds_func : Callable
func set_callbacks(make_cb: Callable, recycle_cb: Callable, vbounds_cb: Callable):
_make_func = make_cb
_recycle_func = recycle_cb
_vertical_bounds_func = vbounds_cb
func clear():
_join_all_recursively(_tree, _max_depth)
_max_depth = 0
_base_size = 0
static func compute_lod_count(base_size: int, full_size: int) -> int:
var po : int = 0
while full_size > base_size:
full_size = full_size >> 1
po += 1
return po
func create_from_sizes(base_size: int, full_size: int):
clear()
_base_size = base_size
_max_depth = compute_lod_count(base_size, full_size)
func get_lod_count() -> int:
# TODO _max_depth is a maximum, not a count. Would be better for it to be a count (+1)
return _max_depth + 1
# The higher, the longer LODs will spread and higher the quality.
# The lower, the shorter LODs will spread and lower the quality.
func set_split_scale(p_split_scale: float):
var MIN := 2.0
var MAX := 5.0
# Split scale must be greater than a threshold,
# otherwise lods will decimate too fast and it will look messy
_split_scale = clampf(p_split_scale, MIN, MAX)
func get_split_scale() -> float:
return _split_scale
func update(view_pos: Vector3):
_update(_tree, _max_depth, view_pos)
# This makes sure we keep seeing the lowest LOD,
# if the tree is cleared while we are far away
if not _tree.has_children() and _tree.data == null:
_tree.data = _make_chunk(_max_depth, 0, 0)
func get_lod_factor(lod: int) -> int:
return 1 << lod
func _update(quad: HT_QTLQuad, lod: int, view_pos: Vector3):
# This function should be called regularly over frames.
var lod_factor : int = get_lod_factor(lod)
var chunk_size : int = _base_size * lod_factor
var world_center := \
chunk_size * (Vector3(quad.origin_x, 0, quad.origin_y) + Vector3(0.5, 0, 0.5))
if _vertical_bounds_func.is_valid():
var vbounds : Vector2 = _vertical_bounds_func.call(quad.origin_x, quad.origin_y, lod)
world_center.y = (vbounds.x + vbounds.y) / 2.0
var split_distance := _base_size * lod_factor * _split_scale
if not quad.has_children():
if lod > 0 and world_center.distance_to(view_pos) < split_distance:
# Split
quad.children = [null, null, null, null]
for i in 4:
var child := HT_QTLQuad.new()
child.origin_x = quad.origin_x * 2 + (i & 1)
child.origin_y = quad.origin_y * 2 + ((i & 2) >> 1)
quad.children[i] = child
child.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.data != null:
_recycle_chunk(quad.data, quad.origin_x, quad.origin_y, lod)
quad.data = null
else:
var no_split_child := true
for child in quad.children:
_update(child, lod - 1, view_pos)
if child.has_children():
no_split_child = false
if no_split_child and world_center.distance_to(view_pos) > split_distance:
# Join
for i in 4:
var child : HT_QTLQuad = quad.children[i]
_recycle_chunk(child.data, child.origin_x, child.origin_y, lod - 1)
quad.clear_children()
quad.data = _make_chunk(lod, quad.origin_x, quad.origin_y)
func _join_all_recursively(quad: HT_QTLQuad, lod: int):
if quad.has_children():
for i in 4:
_join_all_recursively(quad.children[i], lod - 1)
quad.clear_children()
elif quad.data != null:
_recycle_chunk(quad.data, quad.origin_x, quad.origin_y, lod)
quad.data = null
func _make_chunk(lod: int, origin_x: int, origin_y: int):
var chunk = null
if _make_func.is_valid():
chunk = _make_func.call(origin_x, origin_y, lod)
return chunk
func _recycle_chunk(chunk, origin_x: int, origin_y: int, lod: int):
if _recycle_func.is_valid():
_recycle_func.call(chunk, origin_x, origin_y, lod)
func debug_draw_tree(ci: CanvasItem):
var quad := _tree
_debug_draw_tree_recursive(ci, quad, _max_depth, 0)
func _debug_draw_tree_recursive(ci: CanvasItem, quad: HT_QTLQuad, lod_index: int, child_index: int):
if quad.has_children():
for i in 4:
_debug_draw_tree_recursive(ci, quad.children[i], lod_index - 1, i)
else:
var size : int = get_lod_factor(lod_index)
var checker : int = 0
if child_index == 1 or child_index == 2:
checker = 1
var chunk_indicator : int = 0
if quad.data != null:
chunk_indicator = 1
var r := Rect2(Vector2(quad.origin_x, quad.origin_y) * size, Vector2(size, size))
ci.draw_rect(r, Color(1.0 - lod_index * 0.2, 0.2 * checker, chunk_indicator, 1))
|
zaaarf