init_testtest3d

9 files changed, 901 insertions, 0 deletions

diff --git a/game/addons/zylann.hterrain/native/src/.gdignore b/game/addons/zylann.hterrain/native/src/.gdignore
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/.gdignore
diff --git a/game/addons/zylann.hterrain/native/src/gd_library.cpp b/game/addons/zylann.hterrain/native/src/gd_library.cpp
new file mode 100644
index 0000000..d39387f
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/gd_library.cpp
@@ -0,0 +1,30 @@
+#include "image_utils.h"
+#include "quad_tree_lod.h"
+
+extern "C" {
+
+void GDN_EXPORT godot_gdnative_init(godot_gdnative_init_options *o) {
+#ifdef _DEBUG
+    printf("godot_gdnative_init hterrain_native\n");
+#endif
+    godot::Godot::gdnative_init(o);
+}
+
+void GDN_EXPORT godot_gdnative_terminate(godot_gdnative_terminate_options *o) {
+#ifdef _DEBUG
+    printf("godot_gdnative_terminate hterrain_native\n");
+#endif
+    godot::Godot::gdnative_terminate(o);
+}
+
+void GDN_EXPORT godot_nativescript_init(void *handle) {
+#ifdef _DEBUG
+    printf("godot_nativescript_init hterrain_native\n");
+#endif
+    godot::Godot::nativescript_init(handle);
+
+    godot::register_tool_class<godot::ImageUtils>();
+    godot::register_tool_class<godot::QuadTreeLod>();
+}
+
+} // extern "C"
diff --git a/game/addons/zylann.hterrain/native/src/image_utils.cpp b/game/addons/zylann.hterrain/native/src/image_utils.cpp
new file mode 100644
index 0000000..9131307
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/image_utils.cpp
@@ -0,0 +1,364 @@
+#include "image_utils.h"
+#include "int_range_2d.h"
+#include "math_funcs.h"
+
+namespace godot {
+
+template <typename F>
+inline void generic_brush_op(Image &image, Image &brush, Vector2 p_pos, float factor, F op) {
+	IntRange2D range = IntRange2D::from_min_max(p_pos, brush.get_size());
+	int min_x_noclamp = range.min_x;
+	int min_y_noclamp = range.min_y;
+	range.clip(Vector2i(image.get_size()));
+
+	image.lock();
+	brush.lock();
+
+	for (int y = range.min_y; y < range.max_y; ++y) {
+		int by = y - min_y_noclamp;
+
+		for (int x = range.min_x; x < range.max_x; ++x) {
+			int bx = x - min_x_noclamp;
+
+			float b = brush.get_pixel(bx, by).r * factor;
+			op(image, x, y, b);
+		}
+	}
+
+	image.unlock();
+	brush.unlock();
+}
+
+ImageUtils::ImageUtils() {
+#ifdef _DEBUG
+	Godot::print("Constructing ImageUtils");
+#endif
+}
+
+ImageUtils::~ImageUtils() {
+#ifdef _DEBUG
+	// TODO Cannot print shit here, see https://github.com/godotengine/godot/issues/37417
+	// Means only the console will print this
+	//Godot::print("Destructing ImageUtils");
+	printf("Destructing ImageUtils\n");
+#endif
+}
+
+void ImageUtils::_init() {
+}
+
+Vector2 ImageUtils::get_red_range(Ref<Image> image_ref, Rect2 rect) const {
+	ERR_FAIL_COND_V(image_ref.is_null(), Vector2());
+	Image &image = **image_ref;
+
+	IntRange2D range(rect);
+	range.clip(Vector2i(image.get_size()));
+
+	image.lock();
+
+	float min_value = image.get_pixel(range.min_x, range.min_y).r;
+	float max_value = min_value;
+
+	for (int y = range.min_y; y < range.max_y; ++y) {
+		for (int x = range.min_x; x < range.max_x; ++x) {
+			float v = image.get_pixel(x, y).r;
+
+			if (v > max_value) {
+				max_value = v;
+			} else if (v < min_value) {
+				min_value = v;
+			}
+		}
+	}
+
+	image.unlock();
+
+	return Vector2(min_value, max_value);
+}
+
+float ImageUtils::get_red_sum(Ref<Image> image_ref, Rect2 rect) const {
+	ERR_FAIL_COND_V(image_ref.is_null(), 0.f);
+	Image &image = **image_ref;
+
+	IntRange2D range(rect);
+	range.clip(Vector2i(image.get_size()));
+
+	image.lock();
+
+	float sum = 0.f;
+
+	for (int y = range.min_y; y < range.max_y; ++y) {
+		for (int x = range.min_x; x < range.max_x; ++x) {
+			sum += image.get_pixel(x, y).r;
+		}
+	}
+
+	image.unlock();
+
+	return sum;
+}
+
+float ImageUtils::get_red_sum_weighted(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor) const {
+	ERR_FAIL_COND_V(image_ref.is_null(), 0.f);
+	ERR_FAIL_COND_V(brush_ref.is_null(), 0.f);
+	Image &image = **image_ref;
+	Image &brush = **brush_ref;
+
+	float sum = 0.f;
+	generic_brush_op(image, brush, p_pos, factor, [&sum](Image &image, int x, int y, float b) {
+		sum += image.get_pixel(x, y).r * b;
+	});
+
+	return sum;
+}
+
+void ImageUtils::add_red_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor) const {
+	ERR_FAIL_COND(image_ref.is_null());
+	ERR_FAIL_COND(brush_ref.is_null());
+	Image &image = **image_ref;
+	Image &brush = **brush_ref;
+
+	generic_brush_op(image, brush, p_pos, factor, [](Image &image, int x, int y, float b) {
+		float r = image.get_pixel(x, y).r + b;
+		image.set_pixel(x, y, Color(r, r, r));
+	});
+}
+
+void ImageUtils::lerp_channel_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor, float target_value, int channel) const {
+	ERR_FAIL_COND(image_ref.is_null());
+	ERR_FAIL_COND(brush_ref.is_null());
+	Image &image = **image_ref;
+	Image &brush = **brush_ref;
+
+	generic_brush_op(image, brush, p_pos, factor, [target_value, channel](Image &image, int x, int y, float b) {
+		Color c = image.get_pixel(x, y);
+		c[channel] = Math::lerp(c[channel], target_value, b);
+		image.set_pixel(x, y, c);
+	});
+}
+
+void ImageUtils::lerp_color_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor, Color target_value) const {
+	ERR_FAIL_COND(image_ref.is_null());
+	ERR_FAIL_COND(brush_ref.is_null());
+	Image &image = **image_ref;
+	Image &brush = **brush_ref;
+
+	generic_brush_op(image, brush, p_pos, factor, [target_value](Image &image, int x, int y, float b) {
+		const Color c = image.get_pixel(x, y).linear_interpolate(target_value, b);
+		image.set_pixel(x, y, c);
+	});
+}
+
+// TODO Smooth (each pixel being box-filtered, contrary to the existing smooth)
+
+float ImageUtils::generate_gaussian_brush(Ref<Image> image_ref) const {
+	ERR_FAIL_COND_V(image_ref.is_null(), 0.f);
+	Image &image = **image_ref;
+
+	int w = static_cast<int>(image.get_width());
+	int h = static_cast<int>(image.get_height());
+	Vector2 center(w / 2, h / 2);
+	float radius = Math::min(w, h) / 2;
+
+	ERR_FAIL_COND_V(radius <= 0.1f, 0.f);
+
+	float sum = 0.f;
+	image.lock();
+
+	for (int y = 0; y < h; ++y) {
+		for (int x = 0; x < w; ++x) {
+			float d = Vector2(x, y).distance_to(center) / radius;
+			float v = Math::clamp(1.f - d * d * d, 0.f, 1.f);
+			image.set_pixel(x, y, Color(v, v, v));
+			sum += v;
+		}
+	}
+
+	image.unlock();
+	return sum;
+}
+
+void ImageUtils::blur_red_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor) {
+	ERR_FAIL_COND(image_ref.is_null());
+	ERR_FAIL_COND(brush_ref.is_null());
+	Image &image = **image_ref;
+	Image &brush = **brush_ref;
+
+	factor = Math::clamp(factor, 0.f, 1.f);
+
+	// Relative to the image
+	IntRange2D buffer_range = IntRange2D::from_pos_size(p_pos, brush.get_size());
+	buffer_range.pad(1);
+
+	const int image_width = static_cast<int>(image.get_width());
+	const int image_height = static_cast<int>(image.get_height());
+
+	const int buffer_width = static_cast<int>(buffer_range.get_width());
+	const int buffer_height = static_cast<int>(buffer_range.get_height());
+	_blur_buffer.resize(buffer_width * buffer_height);
+
+	image.lock();
+
+	// Cache pixels, because they will be queried more than once and written to later
+	int buffer_i = 0;
+	for (int y = buffer_range.min_y; y < buffer_range.max_y; ++y) {
+		for (int x = buffer_range.min_x; x < buffer_range.max_x; ++x) {
+			const int ix = Math::clamp(x, 0, image_width - 1);
+			const int iy = Math::clamp(y, 0, image_height - 1);
+			_blur_buffer[buffer_i] = image.get_pixel(ix, iy).r;
+			++buffer_i;
+		}
+	}
+
+	IntRange2D range = IntRange2D::from_min_max(p_pos, brush.get_size());
+	const int min_x_noclamp = range.min_x;
+	const int min_y_noclamp = range.min_y;
+	range.clip(Vector2i(image.get_size()));
+
+	const int buffer_offset_left = -1;
+	const int buffer_offset_right = 1;
+	const int buffer_offset_top = -buffer_width;
+	const int buffer_offset_bottom = buffer_width;
+
+	brush.lock();
+
+	// Apply blur
+	for (int y = range.min_y; y < range.max_y; ++y) {
+		const int brush_y = y - min_y_noclamp;
+
+		for (int x = range.min_x; x < range.max_x; ++x) {
+			const int brush_x = x - min_x_noclamp;
+
+			const float brush_value = brush.get_pixel(brush_x, brush_y).r * factor;
+
+			buffer_i = (brush_x + 1) + (brush_y + 1) * buffer_width;
+
+			const float p10 = _blur_buffer[buffer_i + buffer_offset_top];
+			const float p01 = _blur_buffer[buffer_i + buffer_offset_left];
+			const float p11 = _blur_buffer[buffer_i];
+			const float p21 = _blur_buffer[buffer_i + buffer_offset_right];
+			const float p12 = _blur_buffer[buffer_i + buffer_offset_bottom];
+
+			// Average
+			float m = (p10 + p01 + p11 + p21 + p12) * 0.2f;
+			float p = Math::lerp(p11, m, brush_value);
+
+			image.set_pixel(x, y, Color(p, p, p));
+		}
+	}
+
+	image.unlock();
+	brush.unlock();
+}
+
+void ImageUtils::paint_indexed_splat(Ref<Image> index_map_ref, Ref<Image> weight_map_ref,
+		Ref<Image> brush_ref, Vector2 p_pos, int texture_index, float factor) {
+
+	ERR_FAIL_COND(index_map_ref.is_null());
+	ERR_FAIL_COND(weight_map_ref.is_null());
+	ERR_FAIL_COND(brush_ref.is_null());
+	Image &index_map = **index_map_ref;
+	Image &weight_map = **weight_map_ref;
+	Image &brush = **brush_ref;
+
+	ERR_FAIL_COND(index_map.get_size() != weight_map.get_size());
+
+	factor = Math::clamp(factor, 0.f, 1.f);
+
+	IntRange2D range = IntRange2D::from_min_max(p_pos, brush.get_size());
+	const int min_x_noclamp = range.min_x;
+	const int min_y_noclamp = range.min_y;
+	range.clip(Vector2i(index_map.get_size()));
+
+	const float texture_index_f = float(texture_index) / 255.f;
+	const Color all_texture_index_f(texture_index_f, texture_index_f, texture_index_f);
+	const int ci = texture_index % 3;
+	Color cm(-1, -1, -1);
+	cm[ci] = 1;
+
+	brush.lock();
+	index_map.lock();
+	weight_map.lock();
+
+	for (int y = range.min_y; y < range.max_y; ++y) {
+		const int brush_y = y - min_y_noclamp;
+
+		for (int x = range.min_x; x < range.max_x; ++x) {
+			const int brush_x = x - min_x_noclamp;
+
+			const float brush_value = brush.get_pixel(brush_x, brush_y).r * factor;
+
+			if (brush_value == 0.f) {
+				continue;
+			}
+
+			Color i = index_map.get_pixel(x, y);
+			Color w = weight_map.get_pixel(x, y);
+
+			// Decompress third weight to make computations easier
+			w[2] = 1.f - w[0] - w[1];
+
+			if (std::abs(i[ci] - texture_index_f) > 0.001f) {
+				// Pixel does not have our texture index,
+				// transfer its weight to other components first
+				if (w[ci] > brush_value) {
+					w[0] -= cm[0] * brush_value;
+					w[1] -= cm[1] * brush_value;
+					w[2] -= cm[2] * brush_value;
+
+				} else if (w[ci] >= 0.f) {
+					w[ci] = 0.f;
+					i[ci] = texture_index_f;
+				}
+
+			} else {
+				// Pixel has our texture index, increase its weight
+				if (w[ci] + brush_value < 1.f) {
+					w[0] += cm[0] * brush_value;
+					w[1] += cm[1] * brush_value;
+					w[2] += cm[2] * brush_value;
+
+				} else {
+					// Pixel weight is full, we can set all components to the same index.
+					// Need to nullify other weights because they would otherwise never reach
+					// zero due to normalization
+					w = Color(0, 0, 0);
+					w[ci] = 1.0;
+					i = all_texture_index_f;
+				}
+			}
+
+			// No `saturate` function in Color??
+			w[0] = Math::clamp(w[0], 0.f, 1.f);
+			w[1] = Math::clamp(w[1], 0.f, 1.f);
+			w[2] = Math::clamp(w[2], 0.f, 1.f);
+
+			// Renormalize
+			const float sum = w[0] + w[1] + w[2];
+			w[0] /= sum;
+			w[1] /= sum;
+			w[2] /= sum;
+
+			index_map.set_pixel(x, y, i);
+			weight_map.set_pixel(x, y, w);
+		}
+	}
+
+	brush.lock();
+	index_map.unlock();
+	weight_map.unlock();
+}
+
+void ImageUtils::_register_methods() {
+	register_method("get_red_range", &ImageUtils::get_red_range);
+	register_method("get_red_sum", &ImageUtils::get_red_sum);
+	register_method("get_red_sum_weighted", &ImageUtils::get_red_sum_weighted);
+	register_method("add_red_brush", &ImageUtils::add_red_brush);
+	register_method("lerp_channel_brush", &ImageUtils::lerp_channel_brush);
+	register_method("lerp_color_brush", &ImageUtils::lerp_color_brush);
+	register_method("generate_gaussian_brush", &ImageUtils::generate_gaussian_brush);
+	register_method("blur_red_brush", &ImageUtils::blur_red_brush);
+	register_method("paint_indexed_splat", &ImageUtils::paint_indexed_splat);
+}
+
+} // namespace godot
diff --git a/game/addons/zylann.hterrain/native/src/image_utils.h b/game/addons/zylann.hterrain/native/src/image_utils.h
new file mode 100644
index 0000000..5cbe399
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/image_utils.h
@@ -0,0 +1,38 @@
+#ifndef IMAGE_UTILS_H
+#define IMAGE_UTILS_H
+
+#include <core/Godot.hpp>
+#include <gen/Image.hpp>
+#include <gen/Reference.hpp>
+#include <vector>
+
+namespace godot {
+
+class ImageUtils : public Reference {
+    GODOT_CLASS(ImageUtils, Reference)
+public:
+    static void _register_methods();
+
+    ImageUtils();
+    ~ImageUtils();
+
+    void _init();
+
+    Vector2 get_red_range(Ref<Image> image_ref, Rect2 rect) const;
+    float get_red_sum(Ref<Image> image_ref, Rect2 rect) const;
+    float get_red_sum_weighted(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor) const;
+    void add_red_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor) const;
+    void lerp_channel_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor, float target_value, int channel) const;
+    void lerp_color_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor, Color target_value) const;
+    float generate_gaussian_brush(Ref<Image> image_ref) const;
+    void blur_red_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor);
+    void paint_indexed_splat(Ref<Image> index_map_ref, Ref<Image> weight_map_ref, Ref<Image> brush_ref, Vector2 p_pos, int texture_index, float factor);
+    //void erode_red_brush(Ref<Image> image_ref, Ref<Image> brush_ref, Vector2 p_pos, float factor);
+
+private:
+    std::vector<float> _blur_buffer;
+};
+
+} // namespace godot
+
+#endif // IMAGE_UTILS_H
diff --git a/game/addons/zylann.hterrain/native/src/int_range_2d.h b/game/addons/zylann.hterrain/native/src/int_range_2d.h
new file mode 100644
index 0000000..8072bea
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/int_range_2d.h
@@ -0,0 +1,59 @@
+#ifndef INT_RANGE_2D_H
+#define INT_RANGE_2D_H
+
+#include "math_funcs.h"
+#include "vector2i.h"
+#include <core/Rect2.hpp>
+
+struct IntRange2D {
+    int min_x;
+    int min_y;
+    int max_x;
+    int max_y;
+
+    static inline IntRange2D from_min_max(godot::Vector2 min_pos, godot::Vector2 max_pos) {
+        return IntRange2D(godot::Rect2(min_pos, max_pos));
+    }
+
+    static inline IntRange2D from_pos_size(godot::Vector2 min_pos, godot::Vector2 size) {
+        return IntRange2D(godot::Rect2(min_pos, size));
+    }
+
+    IntRange2D(godot::Rect2 rect) {
+        min_x = static_cast<int>(rect.position.x);
+        min_y = static_cast<int>(rect.position.y);
+        max_x = static_cast<int>(rect.position.x + rect.size.x);
+        max_y = static_cast<int>(rect.position.y + rect.size.y);
+    }
+
+    inline bool is_inside(Vector2i size) const {
+        return min_x >= size.x &&
+               min_y >= size.y &&
+               max_x <= size.x &&
+               max_y <= size.y;
+    }
+
+    inline void clip(Vector2i size) {
+        min_x = Math::clamp(min_x, 0, size.x);
+        min_y = Math::clamp(min_y, 0, size.y);
+        max_x = Math::clamp(max_x, 0, size.x);
+        max_y = Math::clamp(max_y, 0, size.y);
+    }
+
+    inline void pad(int p) {
+        min_x -= p;
+        min_y -= p;
+        max_x += p;
+        max_y += p;
+    }
+
+    inline int get_width() const {
+        return max_x - min_x;
+    }
+
+    inline int get_height() const {
+        return max_y - min_y;
+    }
+};
+
+#endif // INT_RANGE_2D_H
diff --git a/game/addons/zylann.hterrain/native/src/math_funcs.h b/game/addons/zylann.hterrain/native/src/math_funcs.h
new file mode 100644
index 0000000..34c9071
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/math_funcs.h
@@ -0,0 +1,28 @@
+#ifndef MATH_FUNCS_H
+#define MATH_FUNCS_H
+
+namespace Math {
+
+inline float lerp(float minv, float maxv, float t) {
+    return minv + t * (maxv - minv);
+}
+
+template <typename T>
+inline T clamp(T x, T minv, T maxv) {
+    if (x < minv) {
+        return minv;
+    }
+    if (x > maxv) {
+        return maxv;
+    }
+    return x;
+}
+
+template <typename T>
+inline T min(T a, T b) {
+    return a < b ? a : b;
+}
+
+} // namespace Math
+
+#endif // MATH_FUNCS_H
diff --git a/game/addons/zylann.hterrain/native/src/quad_tree_lod.cpp b/game/addons/zylann.hterrain/native/src/quad_tree_lod.cpp
new file mode 100644
index 0000000..592375e
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/quad_tree_lod.cpp
@@ -0,0 +1,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
diff --git a/game/addons/zylann.hterrain/native/src/quad_tree_lod.h b/game/addons/zylann.hterrain/native/src/quad_tree_lod.h
new file mode 100644
index 0000000..a4132ec
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/quad_tree_lod.h
@@ -0,0 +1,121 @@
+#ifndef QUAD_TREE_LOD_H
+#define QUAD_TREE_LOD_H
+
+#include <CanvasItem.hpp>
+#include <FuncRef.hpp>
+#include <Godot.hpp>
+
+#include <vector>
+
+namespace godot {
+
+class QuadTreeLod : public Reference {
+	GODOT_CLASS(QuadTreeLod, Reference)
+public:
+	static void _register_methods();
+
+	QuadTreeLod() {}
+	~QuadTreeLod() {}
+	
+	void _init() {}
+
+	void set_callbacks(Ref<FuncRef> make_cb, Ref<FuncRef> recycle_cb, Ref<FuncRef> vbounds_cb);
+	int get_lod_count();
+	int get_lod_factor(int lod);
+	int compute_lod_count(int base_size, int full_size);
+	void set_split_scale(real_t p_split_scale);
+	real_t get_split_scale();
+	void clear();
+	void create_from_sizes(int base_size, int full_size);
+	void update(Vector3 view_pos);
+	void debug_draw_tree(CanvasItem *ci);
+
+private:
+	static const unsigned int NO_CHILDREN = -1;
+	static const unsigned int ROOT = -1;
+
+	class Quad {
+	public:
+		unsigned int first_child = NO_CHILDREN;
+		int origin_x = 0;
+		int origin_y = 0;
+
+		Quad() {
+			init();
+		}
+
+		~Quad() {
+		}
+
+		inline void init() {
+			first_child = NO_CHILDREN;
+			origin_x = 0;
+			origin_y = 0;
+			clear_data();
+		}
+
+		inline void clear_data() {
+			_data = Variant();
+		}
+
+		inline bool has_children() {
+			return first_child != NO_CHILDREN;
+		}
+
+		inline bool is_null() {
+			return _data.get_type() == Variant::NIL;
+		}
+
+		inline bool is_valid() {
+			return _data.get_type() != Variant::NIL;
+		}
+
+		inline Variant get_data() {
+			return _data;
+		}
+
+		inline void set_data(Variant p_data) {
+			_data = p_data;
+		}
+
+	private:
+		Variant _data; // Type is HTerrainChunk.gd : Object
+	};
+
+	Quad _root;
+	std::vector<Quad> _node_pool;
+	std::vector<unsigned int> _free_indices;
+
+	int _max_depth = 0;
+	int _base_size = 16;
+	real_t _split_scale = 2.0f;
+
+	Ref<FuncRef> _make_func;
+	Ref<FuncRef> _recycle_func;
+	Ref<FuncRef> _vertical_bounds_func;
+
+	inline Quad *_get_root() {
+		return &_root;
+	}
+
+	inline Quad *_get_node(unsigned int index) {
+		if (index == ROOT) {
+			return &_root;
+		} else {
+			return &_node_pool[index];
+		}
+	}
+
+	void _clear_children(unsigned int index);
+	unsigned int _allocate_children();
+	void _recycle_children(unsigned int i0);
+	Variant _make_chunk(int lod, int origin_x, int origin_y);
+	void _recycle_chunk(unsigned int quad_index, int lod);
+	void _join_all_recursively(unsigned int quad_index, int lod);
+	void _update(unsigned int quad_index, int lod, Vector3 view_pos);
+	void _debug_draw_tree_recursive(CanvasItem *ci, unsigned int quad_index, int lod_index, int child_index);
+}; // class QuadTreeLod
+
+} // namespace godot
+
+#endif // QUAD_TREE_LOD_H
diff --git a/game/addons/zylann.hterrain/native/src/vector2i.h b/game/addons/zylann.hterrain/native/src/vector2i.h
new file mode 100644
index 0000000..3eb60d6
--- /dev/null
+++ b/game/addons/zylann.hterrain/native/src/vector2i.h
@@ -0,0 +1,19 @@
+#ifndef VECTOR2I_H
+#define VECTOR2I_H
+
+#include <core/Vector2.hpp>
+
+struct Vector2i {
+    int x;
+    int y;
+
+    Vector2i(godot::Vector2 v) :
+            x(static_cast<int>(v.x)),
+            y(static_cast<int>(v.y)) {}
+
+    bool any_zero() const {
+        return x == 0 || y == 0;
+    }
+};
+
+#endif // VECTOR2I_H