GIProbe now generates a distance field on bake using CPU, for better compatibility

4 files changed, 136 insertions, 5 deletions

diff --git a/scene/3d/gi_probe.cpp b/scene/3d/gi_probe.cpp
index 52c4efb7f1..5f7f24a75d 100644
--- a/scene/3d/gi_probe.cpp
+++ b/scene/3d/gi_probe.cpp
@@ -41,6 +41,7 @@ void GIProbeData::_set_data(const Dictionary &p_data) {
 	ERR_FAIL_COND(!p_data.has("octree_size"));
 	ERR_FAIL_COND(!p_data.has("octree_cells"));
 	ERR_FAIL_COND(!p_data.has("octree_data"));
+	ERR_FAIL_COND(!p_data.has("octree_df"));
 	ERR_FAIL_COND(!p_data.has("level_counts"));
 	ERR_FAIL_COND(!p_data.has("to_cell_xform"));
 
@@ -48,10 +49,11 @@ void GIProbeData::_set_data(const Dictionary &p_data) {
 	Vector3 octree_size = p_data["octree_size"];
 	PoolVector<uint8_t> octree_cells = p_data["octree_cells"];
 	PoolVector<uint8_t> octree_data = p_data["octree_data"];
+	PoolVector<uint8_t> octree_df = p_data["octree_df"];
 	PoolVector<int> octree_levels = p_data["level_counts"];
 	Transform to_cell_xform = p_data["to_cell_xform"];
 
-	allocate(to_cell_xform, bounds, octree_size, octree_cells, octree_data, octree_levels);
+	allocate(to_cell_xform, bounds, octree_size, octree_cells, octree_data, octree_df, octree_levels);
 }
 
 Dictionary GIProbeData::_get_data() const {
@@ -60,13 +62,14 @@ Dictionary GIProbeData::_get_data() const {
 	d["octree_size"] = get_octree_size();
 	d["octree_cells"] = get_octree_cells();
 	d["octree_data"] = get_data_cells();
+	d["octree_df"] = get_distance_field();
 	d["level_counts"] = get_level_counts();
 	d["to_cell_xform"] = get_to_cell_xform();
 	return d;
 }
 
-void GIProbeData::allocate(const Transform &p_to_cell_xform, const AABB &p_aabb, const Vector3 &p_octree_size, const PoolVector<uint8_t> &p_octree_cells, const PoolVector<uint8_t> &p_data_cells, const PoolVector<int> &p_level_counts) {
-	VS::get_singleton()->gi_probe_allocate(probe, p_to_cell_xform, p_aabb, p_octree_size, p_octree_cells, p_data_cells, p_level_counts);
+void GIProbeData::allocate(const Transform &p_to_cell_xform, const AABB &p_aabb, const Vector3 &p_octree_size, const PoolVector<uint8_t> &p_octree_cells, const PoolVector<uint8_t> &p_data_cells, const PoolVector<uint8_t> &p_distance_field, const PoolVector<int> &p_level_counts) {
+	VS::get_singleton()->gi_probe_allocate(probe, p_to_cell_xform, p_aabb, p_octree_size, p_octree_cells, p_data_cells, p_distance_field, p_level_counts);
 	bounds = p_aabb;
 	to_cell_xform = p_to_cell_xform;
 	octree_size = p_octree_size;
@@ -84,6 +87,10 @@ PoolVector<uint8_t> GIProbeData::get_octree_cells() const {
 PoolVector<uint8_t> GIProbeData::get_data_cells() const {
 	return VS::get_singleton()->gi_probe_get_data_cells(probe);
 }
+PoolVector<uint8_t> GIProbeData::get_distance_field() const {
+	return VS::get_singleton()->gi_probe_get_distance_field(probe);
+}
+
 PoolVector<int> GIProbeData::get_level_counts() const {
 	return VS::get_singleton()->gi_probe_get_level_counts(probe);
 }
@@ -406,7 +413,13 @@ void GIProbe::bake(Node *p_from_node, bool p_create_visual_debug) {
 		if (probe_data.is_null())
 			probe_data.instance();
 
-		probe_data->allocate(baker.get_to_cell_space_xform(), AABB(-extents, extents * 2.0), baker.get_giprobe_octree_size(), baker.get_giprobe_octree_cells(), baker.get_giprobe_data_cells(), baker.get_giprobe_level_cell_count());
+		if (bake_step_function) {
+			bake_step_function(pmc++, RTR("Generating Distance Field"));
+		}
+
+		PoolVector<uint8_t> df = baker.get_sdf_3d_image();
+
+		probe_data->allocate(baker.get_to_cell_space_xform(), AABB(-extents, extents * 2.0), baker.get_giprobe_octree_size(), baker.get_giprobe_octree_cells(), baker.get_giprobe_data_cells(), df, baker.get_giprobe_level_cell_count());
 
 		set_probe_data(probe_data);
 		probe_data->set_edited(true); //so it gets saved
diff --git a/scene/3d/gi_probe.h b/scene/3d/gi_probe.h
index 7cb4b435c5..3d4ee52469 100644
--- a/scene/3d/gi_probe.h
+++ b/scene/3d/gi_probe.h
@@ -61,11 +61,12 @@ protected:
 	void _validate_property(PropertyInfo &property) const;
 
 public:
-	void allocate(const Transform &p_to_cell_xform, const AABB &p_aabb, const Vector3 &p_octree_size, const PoolVector<uint8_t> &p_octree_cells, const PoolVector<uint8_t> &p_data_cells, const PoolVector<int> &p_level_counts);
+	void allocate(const Transform &p_to_cell_xform, const AABB &p_aabb, const Vector3 &p_octree_size, const PoolVector<uint8_t> &p_octree_cells, const PoolVector<uint8_t> &p_data_cells, const PoolVector<uint8_t> &p_distance_field, const PoolVector<int> &p_level_counts);
 	AABB get_bounds() const;
 	Vector3 get_octree_size() const;
 	PoolVector<uint8_t> get_octree_cells() const;
 	PoolVector<uint8_t> get_data_cells() const;
+	PoolVector<uint8_t> get_distance_field() const;
 	PoolVector<int> get_level_counts() const;
 	Transform get_to_cell_xform() const;
 
diff --git a/scene/3d/voxelizer.cpp b/scene/3d/voxelizer.cpp
index 2aa2f79f43..0e20f606d6 100644
--- a/scene/3d/voxelizer.cpp
+++ b/scene/3d/voxelizer.cpp
@@ -981,6 +981,122 @@ PoolVector<int> Voxelizer::get_giprobe_level_cell_count() const {
 	return level_count;
 }
 
+// euclidean distance computation based on:
+// https://prideout.net/blog/distance_fields/
+
+#define square(m_s) ((m_s) * (m_s))
+#define INF 1e20
+
+/* dt of 1d function using squared distance */
+static void edt(float *f, int stride, int n) {
+
+	float *d = (float *)alloca(sizeof(float) * n + sizeof(int) * n + sizeof(float) * (n + 1));
+	int *v = (int *)&(d[n]);
+	float *z = (float *)&v[n];
+
+	int k = 0;
+	v[0] = 0;
+	z[0] = -INF;
+	z[1] = +INF;
+	for (int q = 1; q <= n - 1; q++) {
+		float s = ((f[q * stride] + square(q)) - (f[v[k] * stride] + square(v[k]))) / (2 * q - 2 * v[k]);
+		while (s <= z[k]) {
+			k--;
+			s = ((f[q * stride] + square(q)) - (f[v[k] * stride] + square(v[k]))) / (2 * q - 2 * v[k]);
+		}
+		k++;
+		v[k] = q;
+
+		z[k] = s;
+		z[k + 1] = +INF;
+	}
+
+	k = 0;
+	for (int q = 0; q <= n - 1; q++) {
+		while (z[k + 1] < q)
+			k++;
+		d[q] = square(q - v[k]) + f[v[k] * stride];
+	}
+
+	for (int i = 0; i < n; i++) {
+		f[i * stride] = d[i];
+	}
+}
+
+#undef square
+
+PoolVector<uint8_t> Voxelizer::get_sdf_3d_image() const {
+
+	Vector3i octree_size = get_giprobe_octree_size();
+
+	uint32_t float_count = octree_size.x * octree_size.y * octree_size.z;
+	float *work_memory = memnew_arr(float, float_count);
+	for (uint32_t i = 0; i < float_count; i++) {
+		work_memory[i] = INF;
+	}
+
+	uint32_t y_mult = octree_size.x;
+	uint32_t z_mult = y_mult * octree_size.y;
+
+	//plot solid cells
+	{
+		const Cell *cells = bake_cells.ptr();
+		uint32_t cell_count = bake_cells.size();
+
+		for (uint32_t i = 0; i < cell_count; i++) {
+
+			if (cells[i].level < (cell_subdiv - 1)) {
+				continue; //do not care about this level
+			}
+
+			work_memory[cells[i].x + cells[i].y * y_mult + cells[i].z * z_mult] = 0;
+		}
+	}
+
+	//process in each direction
+
+	//xy->z
+
+	for (int i = 0; i < octree_size.x; i++) {
+		for (int j = 0; j < octree_size.y; j++) {
+			edt(&work_memory[i + j * y_mult], z_mult, octree_size.z);
+		}
+	}
+
+	//xz->y
+
+	for (int i = 0; i < octree_size.x; i++) {
+		for (int j = 0; j < octree_size.z; j++) {
+			edt(&work_memory[i + j * z_mult], y_mult, octree_size.y);
+		}
+	}
+
+	//yz->x
+	for (int i = 0; i < octree_size.y; i++) {
+		for (int j = 0; j < octree_size.z; j++) {
+			edt(&work_memory[i * y_mult + j * z_mult], 1, octree_size.x);
+		}
+	}
+
+	PoolVector<uint8_t> image3d;
+	image3d.resize(float_count);
+	{
+		PoolVector<uint8_t>::Write w = image3d.write();
+		for (uint32_t i = 0; i < float_count; i++) {
+			uint32_t d = uint32_t(Math::sqrt(work_memory[i]));
+			if (d == 0) {
+				w[i] = 0;
+			} else {
+				w[i] = CLAMP(d, 0, 254) + 1;
+			}
+		}
+	}
+
+	return image3d;
+}
+
+#undef INF
+
 void Voxelizer::_debug_mesh(int p_idx, int p_level, const AABB &p_aabb, Ref<MultiMesh> &p_multimesh, int &idx) {
 
 	if (p_level == cell_subdiv - 1) {
diff --git a/scene/3d/voxelizer.h b/scene/3d/voxelizer.h
index 37de6b782e..5016ff029f 100644
--- a/scene/3d/voxelizer.h
+++ b/scene/3d/voxelizer.h
@@ -135,6 +135,7 @@ public:
 	PoolVector<uint8_t> get_giprobe_octree_cells() const;
 	PoolVector<uint8_t> get_giprobe_data_cells() const;
 	PoolVector<int> get_giprobe_level_cell_count() const;
+	PoolVector<uint8_t> get_sdf_3d_image() const;
 
 	Ref<MultiMesh> create_debug_multimesh();