Implement automatic LOD (Level of Detail)

-Happens on import by default for all models
-Just works (tm)
-Biasing can be later adjusted per node or per viewport (as well as globally)
-Disabled AABB.get_support test because its broken

4 files changed, 133 insertions, 7 deletions

diff --git a/thirdparty/README.md b/thirdparty/README.md
index e420872475..1db7f5d583 100644
--- a/thirdparty/README.md
+++ b/thirdparty/README.md
@@ -355,15 +355,20 @@ File extracted from upstream release tarball:
 - Added 2 files `godot_core_mbedtls_platform.{c,h}` providing configuration
   for light bundling with core.
 
+
 ## meshoptimizer
 
 - Upstream: https://github.com/zeux/meshoptimizer
-- Version: 0.15(2020)
+- Version: 0.15 (2020)
 - License: MIT
 
 File extracted from upstream release tarball:
 
-- Files in src/ go to thirdparty/meshoptimizer
+- All files in `src/`.
+
+Important: Some files have Godot-made changes.
+They can be applied with the patch in the `patches` folder, but are meant to be superseded
+by upstream API changes.
 
 
 ## miniupnpc
diff --git a/thirdparty/meshoptimizer/meshoptimizer.h b/thirdparty/meshoptimizer/meshoptimizer.h
index a442d103c8..fde00f9c82 100644
--- a/thirdparty/meshoptimizer/meshoptimizer.h
+++ b/thirdparty/meshoptimizer/meshoptimizer.h
@@ -266,7 +266,10 @@ MESHOPTIMIZER_EXPERIMENTAL void meshopt_decodeFilterExp(void* buffer, size_t ver
  * destination must contain enough space for the *source* index buffer (since optimization is iterative, this means index_count elements - *not* target_index_count!)
  * vertex_positions should have float3 position in the first 12 bytes of each vertex - similar to glVertexPointer
  */
-MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error);
+// -- GODOT start --
+//MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error);
+MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_resulting_error);
+// -- GODOT end --
 
 /**
  * Experimental: Mesh simplifier (sloppy)
diff --git a/thirdparty/meshoptimizer/patches/simplifier_get_resulting_error.patch b/thirdparty/meshoptimizer/patches/simplifier_get_resulting_error.patch
new file mode 100644
index 0000000000..1be38e45d2
--- /dev/null
+++ b/thirdparty/meshoptimizer/patches/simplifier_get_resulting_error.patch
@@ -0,0 +1,96 @@
+diff --git a/thirdparty/meshoptimizer/meshoptimizer.h b/thirdparty/meshoptimizer/meshoptimizer.h
+index a442d103c8..fde00f9c82 100644
+--- a/thirdparty/meshoptimizer/meshoptimizer.h
++++ b/thirdparty/meshoptimizer/meshoptimizer.h
+@@ -266,7 +266,10 @@ MESHOPTIMIZER_EXPERIMENTAL void meshopt_decodeFilterExp(void* buffer, size_t ver
+  * destination must contain enough space for the *source* index buffer (since optimization is iterative, this means index_count elements - *not* target_index_count!)
+  * vertex_positions should have float3 position in the first 12 bytes of each vertex - similar to glVertexPointer
+  */
+-MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error);
++// -- GODOT start --
++//MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error);
++MESHOPTIMIZER_EXPERIMENTAL size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_resulting_error);
++// -- GODOT end --
+ 
+ /**
+  * Experimental: Mesh simplifier (sloppy)
+diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp
+index bd523275ce..51cf634186 100644
+--- a/thirdparty/meshoptimizer/simplifier.cpp
++++ b/thirdparty/meshoptimizer/simplifier.cpp
+@@ -1143,7 +1143,10 @@ unsigned int* meshopt_simplifyDebugLoop = 0;
+ unsigned int* meshopt_simplifyDebugLoopBack = 0;
+ #endif
+ 
+-size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error)
++// -- GODOT start --
++//size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error)
++size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_resulting_error)
++// -- GODOT end --
+ {
+ 	using namespace meshopt;
+ 
+@@ -1198,10 +1201,13 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
+ 	if (result != indices)
+ 		memcpy(result, indices, index_count * sizeof(unsigned int));
+ 
++// -- GODOT start --
+ #if TRACE
+ 	size_t pass_count = 0;
+-	float worst_error = 0;
++	//float worst_error = 0;
+ #endif
++	float worst_error = 0;
++// -- GODOT end --
+ 
+ 	Collapse* edge_collapses = allocator.allocate<Collapse>(index_count);
+ 	unsigned int* collapse_order = allocator.allocate<unsigned int>(index_count);
+@@ -1213,6 +1219,12 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
+ 	// target_error input is linear; we need to adjust it to match quadricError units
+ 	float error_limit = target_error * target_error;
+ 
++// -- GODOT start --
++	if (r_resulting_error) {
++		*r_resulting_error = 1.0;
++	}
++// -- GODOT end --
++
+ 	while (result_count > target_index_count)
+ 	{
+ 		size_t edge_collapse_count = pickEdgeCollapses(edge_collapses, result, result_count, remap, vertex_kind, loop);
+@@ -1257,7 +1269,8 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
+ 		size_t new_count = remapIndexBuffer(result, result_count, collapse_remap);
+ 		assert(new_count < result_count);
+ 
+-#if TRACE
++// -- GODOT start --
++//#if TRACE
+ 		float pass_error = 0.f;
+ 		for (size_t i = 0; i < edge_collapse_count; ++i)
+ 		{
+@@ -1267,15 +1280,24 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
+ 				pass_error = c.error;
+ 		}
+ 
+-		pass_count++;
++		//pass_count++;
+ 		worst_error = (worst_error < pass_error) ? pass_error : worst_error;
+ 
++#if TRACE
++		pass_count++;
+ 		printf("pass %d: triangles: %d -> %d, collapses: %d/%d (goal: %d), error: %e (limit %e goal %e)\n", int(pass_count), int(result_count / 3), int(new_count / 3), int(collapses), int(edge_collapse_count), int(edge_collapse_goal), pass_error, error_limit, error_goal);
+ #endif
++// -- GODOT end --
+ 
+ 		result_count = new_count;
+ 	}
+ 
++// -- GODOT start --
++	if (r_resulting_error) {
++		*r_resulting_error = sqrt(worst_error);
++	}
++// -- GODOT end --
++
+ #if TRACE
+ 	printf("passes: %d, worst error: %e\n", int(pass_count), worst_error);
+ #endif
diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp
index bd523275ce..51cf634186 100644
--- a/thirdparty/meshoptimizer/simplifier.cpp
+++ b/thirdparty/meshoptimizer/simplifier.cpp
@@ -1143,7 +1143,10 @@ unsigned int* meshopt_simplifyDebugLoop = 0;
 unsigned int* meshopt_simplifyDebugLoopBack = 0;
 #endif
 
-size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error)
+// -- GODOT start --
+//size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error)
+size_t meshopt_simplify(unsigned int *destination, const unsigned int *indices, size_t index_count, const float *vertex_positions_data, size_t vertex_count, size_t vertex_positions_stride, size_t target_index_count, float target_error, float *r_resulting_error)
+// -- GODOT end --
 {
 	using namespace meshopt;
 
@@ -1198,10 +1201,13 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
 	if (result != indices)
 		memcpy(result, indices, index_count * sizeof(unsigned int));
 
+// -- GODOT start --
 #if TRACE
 	size_t pass_count = 0;
-	float worst_error = 0;
+	//float worst_error = 0;
 #endif
+	float worst_error = 0;
+// -- GODOT end --
 
 	Collapse* edge_collapses = allocator.allocate<Collapse>(index_count);
 	unsigned int* collapse_order = allocator.allocate<unsigned int>(index_count);
@@ -1213,6 +1219,12 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
 	// target_error input is linear; we need to adjust it to match quadricError units
 	float error_limit = target_error * target_error;
 
+// -- GODOT start --
+	if (r_resulting_error) {
+		*r_resulting_error = 1.0;
+	}
+// -- GODOT end --
+
 	while (result_count > target_index_count)
 	{
 		size_t edge_collapse_count = pickEdgeCollapses(edge_collapses, result, result_count, remap, vertex_kind, loop);
@@ -1257,7 +1269,8 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
 		size_t new_count = remapIndexBuffer(result, result_count, collapse_remap);
 		assert(new_count < result_count);
 
-#if TRACE
+// -- GODOT start --
+//#if TRACE
 		float pass_error = 0.f;
 		for (size_t i = 0; i < edge_collapse_count; ++i)
 		{
@@ -1267,15 +1280,24 @@ size_t meshopt_simplify(unsigned int* destination, const unsigned int* indices,
 				pass_error = c.error;
 		}
 
-		pass_count++;
+		//pass_count++;
 		worst_error = (worst_error < pass_error) ? pass_error : worst_error;
 
+#if TRACE
+		pass_count++;
 		printf("pass %d: triangles: %d -> %d, collapses: %d/%d (goal: %d), error: %e (limit %e goal %e)\n", int(pass_count), int(result_count / 3), int(new_count / 3), int(collapses), int(edge_collapse_count), int(edge_collapse_goal), pass_error, error_limit, error_goal);
 #endif
+// -- GODOT end --
 
 		result_count = new_count;
 	}
 
+// -- GODOT start --
+	if (r_resulting_error) {
+		*r_resulting_error = sqrt(worst_error);
+	}
+// -- GODOT end --
+
 #if TRACE
 	printf("passes: %d, worst error: %e\n", int(pass_count), worst_error);
 #endif