Auto LOD fixes and improvements

* Fixed LODs for shadow meshes.
* Added a merging step before simplification. This helps with tesselated
  meshes that were previously left untouched. The angle difference at
  wich edges ar considered "hard" can be tweaked as an import setting.
* LODs will now start with the highest decimation possible and keep
  doubling (approximately) the number of triangles from there. This
  makes sure that very low triangle counts are included when possible.
* Given more weight to normal preservation.
* Modified MeshOptimizer to report distance-based error instead of
  including attributes in the reported metrics.
* Added attribute transference between the original mesh and the
  various LODs. Right now only normals are taken into account,
  but it could be expanded to other attributes in the future.

2 files changed, 228 insertions, 10 deletions

diff --git a/thirdparty/meshoptimizer/patches/attribute-aware-simplify-distance-only-metric.patch b/thirdparty/meshoptimizer/patches/attribute-aware-simplify-distance-only-metric.patch
new file mode 100644
index 0000000000..54132a6c86
--- /dev/null
+++ b/thirdparty/meshoptimizer/patches/attribute-aware-simplify-distance-only-metric.patch
@@ -0,0 +1,176 @@
+diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp
+index 0f10ebef4b..cf5db4e119 100644
+--- a/thirdparty/meshoptimizer/simplifier.cpp
++++ b/thirdparty/meshoptimizer/simplifier.cpp
+@@ -20,7 +20,7 @@
+ #define TRACESTATS(i) (void)0
+ #endif
+ 
+-#define ATTRIBUTES 8
++#define ATTRIBUTES 3
+ 
+ // This work is based on:
+ // Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. 1997
+@@ -445,6 +445,7 @@ struct Collapse
+ 		float error;
+ 		unsigned int errorui;
+ 	};
++	float distance_error;
+ };
+ 
+ static float normalize(Vector3& v)
+@@ -525,6 +526,34 @@ static float quadricError(const Quadric& Q, const Vector3& v)
+ 	return fabsf(r) * s;
+ }
+ 
++static float quadricErrorNoAttributes(const Quadric& Q, const Vector3& v)
++{
++	float rx = Q.b0;
++	float ry = Q.b1;
++	float rz = Q.b2;
++
++	rx += Q.a10 * v.y;
++	ry += Q.a21 * v.z;
++	rz += Q.a20 * v.x;
++
++	rx *= 2;
++	ry *= 2;
++	rz *= 2;
++
++	rx += Q.a00 * v.x;
++	ry += Q.a11 * v.y;
++	rz += Q.a22 * v.z;
++
++	float r = Q.c;
++	r += rx * v.x;
++	r += ry * v.y;
++	r += rz * v.z;
++
++	float s = Q.w == 0.f ? 0.f : 1.f / Q.w;
++
++	return fabsf(r) * s;
++}
++
+ static void quadricFromPlane(Quadric& Q, float a, float b, float c, float d, float w)
+ {
+ 	float aw = a * w;
+@@ -680,7 +709,7 @@ static void quadricUpdateAttributes(Quadric& Q, const Vector3& p0, const Vector3
+ }
+ #endif
+ 
+-static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap)
++static void fillFaceQuadrics(Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap)
+ {
+ 	for (size_t i = 0; i < index_count; i += 3)
+ 	{
+@@ -690,6 +719,9 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
+ 
+ 		Quadric Q;
+ 		quadricFromTriangle(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], 1.f);
++		quadricAdd(vertex_no_attrib_quadrics[remap[i0]], Q);
++		quadricAdd(vertex_no_attrib_quadrics[remap[i1]], Q);
++		quadricAdd(vertex_no_attrib_quadrics[remap[i2]], Q);
+ 
+ #if ATTRIBUTES
+ 		quadricUpdateAttributes(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], Q.w);
+@@ -700,7 +732,7 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
+ 	}
+ }
+ 
+-static void fillEdgeQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap, const unsigned char* vertex_kind, const unsigned int* loop, const unsigned int* loopback)
++static void fillEdgeQuadrics(Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap, const unsigned char* vertex_kind, const unsigned int* loop, const unsigned int* loopback)
+ {
+ 	for (size_t i = 0; i < index_count; i += 3)
+ 	{
+@@ -744,6 +776,9 @@ static void fillEdgeQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
+ 
+ 			quadricAdd(vertex_quadrics[remap[i0]], Q);
+ 			quadricAdd(vertex_quadrics[remap[i1]], Q);
++
++			quadricAdd(vertex_no_attrib_quadrics[remap[i0]], Q);
++			quadricAdd(vertex_no_attrib_quadrics[remap[i1]], Q);
+ 		}
+ 	}
+ }
+@@ -848,7 +883,7 @@ static size_t pickEdgeCollapses(Collapse* collapses, const unsigned int* indices
+ 	return collapse_count;
+ }
+ 
+-static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const Vector3* vertex_positions, const Quadric* vertex_quadrics, const unsigned int* remap)
++static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const Vector3* vertex_positions, const Quadric* vertex_quadrics, const Quadric* vertex_no_attrib_quadrics, const unsigned int* remap)
+ {
+ 	for (size_t i = 0; i < collapse_count; ++i)
+ 	{
+@@ -868,10 +903,14 @@ static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const
+ 		float ei = quadricError(qi, vertex_positions[i1]);
+ 		float ej = quadricError(qj, vertex_positions[j1]);
+ 
++		const Quadric& naqi = vertex_no_attrib_quadrics[remap[i0]];
++		const Quadric& naqj = vertex_no_attrib_quadrics[remap[j0]];
++
+ 		// pick edge direction with minimal error
+ 		c.v0 = ei <= ej ? i0 : j0;
+ 		c.v1 = ei <= ej ? i1 : j1;
+ 		c.error = ei <= ej ? ei : ej;
++		c.distance_error = ei <= ej ? quadricErrorNoAttributes(naqi, vertex_positions[i1]) :  quadricErrorNoAttributes(naqj, vertex_positions[j1]);
+ 	}
+ }
+ 
+@@ -968,7 +1007,7 @@ static void sortEdgeCollapses(unsigned int* sort_order, const Collapse* collapse
+ 	}
+ }
+ 
+-static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, const Vector3* vertex_positions, const EdgeAdjacency& adjacency, size_t triangle_collapse_goal, float error_limit, float& result_error)
++static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, const Vector3* vertex_positions, const EdgeAdjacency& adjacency, size_t triangle_collapse_goal, float error_limit, float& result_error)
+ {
+ 	size_t edge_collapses = 0;
+ 	size_t triangle_collapses = 0;
+@@ -1030,6 +1069,7 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char*
+ 		assert(collapse_remap[r1] == r1);
+ 
+ 		quadricAdd(vertex_quadrics[r1], vertex_quadrics[r0]);
++		quadricAdd(vertex_no_attrib_quadrics[r1], vertex_no_attrib_quadrics[r0]);
+ 
+ 		if (vertex_kind[i0] == Kind_Complex)
+ 		{
+@@ -1067,7 +1107,7 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char*
+ 		triangle_collapses += (vertex_kind[i0] == Kind_Border) ? 1 : 2;
+ 		edge_collapses++;
+ 
+-		result_error = result_error < c.error ? c.error : result_error;
++		result_error = result_error < c.distance_error ? c.distance_error : result_error;
+ 	}
+ 
+ #if TRACE
+@@ -1455,9 +1495,11 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
+ 
+ 	Quadric* vertex_quadrics = allocator.allocate<Quadric>(vertex_count);
+ 	memset(vertex_quadrics, 0, vertex_count * sizeof(Quadric));
++	Quadric* vertex_no_attrib_quadrics = allocator.allocate<Quadric>(vertex_count);
++	memset(vertex_no_attrib_quadrics, 0, vertex_count * sizeof(Quadric));
+ 
+-	fillFaceQuadrics(vertex_quadrics, indices, index_count, vertex_positions, remap);
+-	fillEdgeQuadrics(vertex_quadrics, indices, index_count, vertex_positions, remap, vertex_kind, loop, loopback);
++	fillFaceQuadrics(vertex_quadrics, vertex_no_attrib_quadrics, indices, index_count, vertex_positions, remap);
++	fillEdgeQuadrics(vertex_quadrics, vertex_no_attrib_quadrics, indices, index_count, vertex_positions, remap, vertex_kind, loop, loopback);
+ 
+ 	if (result != indices)
+ 		memcpy(result, indices, index_count * sizeof(unsigned int));
+@@ -1488,7 +1530,7 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
+ 		if (edge_collapse_count == 0)
+ 			break;
+ 
+-		rankEdgeCollapses(edge_collapses, edge_collapse_count, vertex_positions, vertex_quadrics, remap);
++		rankEdgeCollapses(edge_collapses, edge_collapse_count, vertex_positions, vertex_quadrics, vertex_no_attrib_quadrics, remap);
+ 
+ #if TRACE > 1
+ 		dumpEdgeCollapses(edge_collapses, edge_collapse_count, vertex_kind);
+@@ -1507,7 +1549,7 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
+ 		printf("pass %d: ", int(pass_count++));
+ #endif
+ 
+-		size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, vertex_positions, adjacency, triangle_collapse_goal, error_limit, result_error);
++		size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, vertex_no_attrib_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, vertex_positions, adjacency, triangle_collapse_goal, error_limit, result_error);
+ 
+ 		// no edges can be collapsed any more due to hitting the error limit or triangle collapse limit
+ 		if (collapses == 0)
diff --git a/thirdparty/meshoptimizer/simplifier.cpp b/thirdparty/meshoptimizer/simplifier.cpp
index 0f10ebef4b..cf5db4e119 100644
--- a/thirdparty/meshoptimizer/simplifier.cpp
+++ b/thirdparty/meshoptimizer/simplifier.cpp
@@ -20,7 +20,7 @@
 #define TRACESTATS(i) (void)0
 #endif
 
-#define ATTRIBUTES 8
+#define ATTRIBUTES 3
 
 // This work is based on:
 // Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. 1997
@@ -445,6 +445,7 @@ struct Collapse
 		float error;
 		unsigned int errorui;
 	};
+	float distance_error;
 };
 
 static float normalize(Vector3& v)
@@ -525,6 +526,34 @@ static float quadricError(const Quadric& Q, const Vector3& v)
 	return fabsf(r) * s;
 }
 
+static float quadricErrorNoAttributes(const Quadric& Q, const Vector3& v)
+{
+	float rx = Q.b0;
+	float ry = Q.b1;
+	float rz = Q.b2;
+
+	rx += Q.a10 * v.y;
+	ry += Q.a21 * v.z;
+	rz += Q.a20 * v.x;
+
+	rx *= 2;
+	ry *= 2;
+	rz *= 2;
+
+	rx += Q.a00 * v.x;
+	ry += Q.a11 * v.y;
+	rz += Q.a22 * v.z;
+
+	float r = Q.c;
+	r += rx * v.x;
+	r += ry * v.y;
+	r += rz * v.z;
+
+	float s = Q.w == 0.f ? 0.f : 1.f / Q.w;
+
+	return fabsf(r) * s;
+}
+
 static void quadricFromPlane(Quadric& Q, float a, float b, float c, float d, float w)
 {
 	float aw = a * w;
@@ -680,7 +709,7 @@ static void quadricUpdateAttributes(Quadric& Q, const Vector3& p0, const Vector3
 }
 #endif
 
-static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap)
+static void fillFaceQuadrics(Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap)
 {
 	for (size_t i = 0; i < index_count; i += 3)
 	{
@@ -690,6 +719,9 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
 
 		Quadric Q;
 		quadricFromTriangle(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], 1.f);
+		quadricAdd(vertex_no_attrib_quadrics[remap[i0]], Q);
+		quadricAdd(vertex_no_attrib_quadrics[remap[i1]], Q);
+		quadricAdd(vertex_no_attrib_quadrics[remap[i2]], Q);
 
 #if ATTRIBUTES
 		quadricUpdateAttributes(Q, vertex_positions[i0], vertex_positions[i1], vertex_positions[i2], Q.w);
@@ -700,7 +732,7 @@ static void fillFaceQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
 	}
 }
 
-static void fillEdgeQuadrics(Quadric* vertex_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap, const unsigned char* vertex_kind, const unsigned int* loop, const unsigned int* loopback)
+static void fillEdgeQuadrics(Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const unsigned int* indices, size_t index_count, const Vector3* vertex_positions, const unsigned int* remap, const unsigned char* vertex_kind, const unsigned int* loop, const unsigned int* loopback)
 {
 	for (size_t i = 0; i < index_count; i += 3)
 	{
@@ -744,6 +776,9 @@ static void fillEdgeQuadrics(Quadric* vertex_quadrics, const unsigned int* indic
 
 			quadricAdd(vertex_quadrics[remap[i0]], Q);
 			quadricAdd(vertex_quadrics[remap[i1]], Q);
+
+			quadricAdd(vertex_no_attrib_quadrics[remap[i0]], Q);
+			quadricAdd(vertex_no_attrib_quadrics[remap[i1]], Q);
 		}
 	}
 }
@@ -848,7 +883,7 @@ static size_t pickEdgeCollapses(Collapse* collapses, const unsigned int* indices
 	return collapse_count;
 }
 
-static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const Vector3* vertex_positions, const Quadric* vertex_quadrics, const unsigned int* remap)
+static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const Vector3* vertex_positions, const Quadric* vertex_quadrics, const Quadric* vertex_no_attrib_quadrics, const unsigned int* remap)
 {
 	for (size_t i = 0; i < collapse_count; ++i)
 	{
@@ -868,10 +903,14 @@ static void rankEdgeCollapses(Collapse* collapses, size_t collapse_count, const
 		float ei = quadricError(qi, vertex_positions[i1]);
 		float ej = quadricError(qj, vertex_positions[j1]);
 
+		const Quadric& naqi = vertex_no_attrib_quadrics[remap[i0]];
+		const Quadric& naqj = vertex_no_attrib_quadrics[remap[j0]];
+
 		// pick edge direction with minimal error
 		c.v0 = ei <= ej ? i0 : j0;
 		c.v1 = ei <= ej ? i1 : j1;
 		c.error = ei <= ej ? ei : ej;
+		c.distance_error = ei <= ej ? quadricErrorNoAttributes(naqi, vertex_positions[i1]) :  quadricErrorNoAttributes(naqj, vertex_positions[j1]);
 	}
 }
 
@@ -968,7 +1007,7 @@ static void sortEdgeCollapses(unsigned int* sort_order, const Collapse* collapse
 	}
 }
 
-static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, const Vector3* vertex_positions, const EdgeAdjacency& adjacency, size_t triangle_collapse_goal, float error_limit, float& result_error)
+static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char* collapse_locked, Quadric* vertex_quadrics, Quadric* vertex_no_attrib_quadrics, const Collapse* collapses, size_t collapse_count, const unsigned int* collapse_order, const unsigned int* remap, const unsigned int* wedge, const unsigned char* vertex_kind, const Vector3* vertex_positions, const EdgeAdjacency& adjacency, size_t triangle_collapse_goal, float error_limit, float& result_error)
 {
 	size_t edge_collapses = 0;
 	size_t triangle_collapses = 0;
@@ -1030,6 +1069,7 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char*
 		assert(collapse_remap[r1] == r1);
 
 		quadricAdd(vertex_quadrics[r1], vertex_quadrics[r0]);
+		quadricAdd(vertex_no_attrib_quadrics[r1], vertex_no_attrib_quadrics[r0]);
 
 		if (vertex_kind[i0] == Kind_Complex)
 		{
@@ -1067,7 +1107,7 @@ static size_t performEdgeCollapses(unsigned int* collapse_remap, unsigned char*
 		triangle_collapses += (vertex_kind[i0] == Kind_Border) ? 1 : 2;
 		edge_collapses++;
 
-		result_error = result_error < c.error ? c.error : result_error;
+		result_error = result_error < c.distance_error ? c.distance_error : result_error;
 	}
 
 #if TRACE
@@ -1455,9 +1495,11 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
 
 	Quadric* vertex_quadrics = allocator.allocate<Quadric>(vertex_count);
 	memset(vertex_quadrics, 0, vertex_count * sizeof(Quadric));
+	Quadric* vertex_no_attrib_quadrics = allocator.allocate<Quadric>(vertex_count);
+	memset(vertex_no_attrib_quadrics, 0, vertex_count * sizeof(Quadric));
 
-	fillFaceQuadrics(vertex_quadrics, indices, index_count, vertex_positions, remap);
-	fillEdgeQuadrics(vertex_quadrics, indices, index_count, vertex_positions, remap, vertex_kind, loop, loopback);
+	fillFaceQuadrics(vertex_quadrics, vertex_no_attrib_quadrics, indices, index_count, vertex_positions, remap);
+	fillEdgeQuadrics(vertex_quadrics, vertex_no_attrib_quadrics, indices, index_count, vertex_positions, remap, vertex_kind, loop, loopback);
 
 	if (result != indices)
 		memcpy(result, indices, index_count * sizeof(unsigned int));
@@ -1488,7 +1530,7 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
 		if (edge_collapse_count == 0)
 			break;
 
-		rankEdgeCollapses(edge_collapses, edge_collapse_count, vertex_positions, vertex_quadrics, remap);
+		rankEdgeCollapses(edge_collapses, edge_collapse_count, vertex_positions, vertex_quadrics, vertex_no_attrib_quadrics, remap);
 
 #if TRACE > 1
 		dumpEdgeCollapses(edge_collapses, edge_collapse_count, vertex_kind);
@@ -1507,7 +1549,7 @@ size_t meshopt_simplifyWithAttributes(unsigned int* destination, const unsigned
 		printf("pass %d: ", int(pass_count++));
 #endif
 
-		size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, vertex_positions, adjacency, triangle_collapse_goal, error_limit, result_error);
+		size_t collapses = performEdgeCollapses(collapse_remap, collapse_locked, vertex_quadrics, vertex_no_attrib_quadrics, edge_collapses, edge_collapse_count, collapse_order, remap, wedge, vertex_kind, vertex_positions, adjacency, triangle_collapse_goal, error_limit, result_error);
 
 		// no edges can be collapsed any more due to hitting the error limit or triangle collapse limit
 		if (collapses == 0)