Simplification failure on flat surfaces

[snowbldr]

I had opened a PR for this issue, but after receiving feedback from @zeux, switching to doubles are not an acceptable solution.

example_stls.zip

There's a test that reproduces this issue on that PR:
https://github.com/zeux/meshoptimizer/pull/1062/changes#diff-8388a4114e325ed357a660cc215d5a1281f1d0977714e8b52f15e55261bee5d0R1802

I've also attached a repro stl, and the result of the meshopt simplify call.

Here's a visual representation of the issue:

Here's the code I used to generate the failure output.

// Minimal STL -> meshopt_simplify -> STL round trip.
// Usage: ./simplify_stl input.stl output.stl target_index_count target_error

#include <cstdio>
#include <cstring>
#include <vector>

#include "src/meshoptimizer.h"

int main(int argc, char** argv)
{
	if (argc != 5)
	{
		fprintf(stderr, "usage: %s input.stl output.stl target_index_count target_error\n", argv[0]);
		return 1;
	}

	// --- read binary STL as triangle soup (3 unindexed verts per triangle) ---
	FILE* in = fopen(argv[1], "rb");
	char header[80];
	fread(header, 1, 80, in);

	unsigned int triCount;
	fread(&triCount, sizeof(triCount), 1, in);

	std::vector<float> soup(triCount * 3 * 3);
	for (unsigned int i = 0; i < triCount; ++i)
	{
		float normal[3];
		fread(normal, sizeof(float), 3, in);
		fread(&soup[i * 9], sizeof(float), 9, in);
		unsigned short attr;
		fread(&attr, sizeof(attr), 1, in);
	}
	fclose(in);

	size_t indexCount = triCount * 3;

	// --- weld duplicate positions into an indexed mesh ---
	std::vector<unsigned int> remap(indexCount);
	size_t vertexCount = meshopt_generateVertexRemap(&remap[0], NULL, indexCount, &soup[0], indexCount, 12);

	std::vector<unsigned int> indices(indexCount);
	std::vector<float> vertices(vertexCount * 3);
	meshopt_remapIndexBuffer(&indices[0], NULL, indexCount, &remap[0]);
	meshopt_remapVertexBuffer(&vertices[0], &soup[0], indexCount, 12, &remap[0]);

	printf("loaded: %zu triangles, %zu unique vertices\n", indexCount / 3, vertexCount);

	// --- simplify ---
	size_t targetIndexCount = atoi(argv[3]);
	float targetError = atof(argv[4]);

	std::vector<unsigned int> result(indexCount);
	float error = 0;
	size_t resultCount = meshopt_simplify(&result[0], &indices[0], indexCount, &vertices[0], vertexCount, 12,
	                                       targetIndexCount, targetError, 0, &error);
	result.resize(resultCount);

	printf("simplified: %zu triangles, error=%g\n", resultCount / 3, error);

	// --- write result back out as binary STL (triangle soup, zero normals) ---
	FILE* out = fopen(argv[2], "wb");
	memset(header, 0, 80);
	fwrite(header, 1, 80, out);

	unsigned int outTriCount = (unsigned int)(resultCount / 3);
	fwrite(&outTriCount, sizeof(outTriCount), 1, out);

	for (size_t i = 0; i < resultCount; i += 3)
	{
		float normal[3] = {0, 0, 0};
		fwrite(normal, sizeof(float), 3, out);
		for (int k = 0; k < 3; ++k)
			fwrite(&vertices[result[i + k] * 3], sizeof(float), 3, out);
		unsigned short attr = 0;
		fwrite(&attr, sizeof(attr), 1, out);
	}
	fclose(out);

	return 0;
}

[zeux]

The input here is 3 separate components: two tessellated planes and a stray triangle. Simplifying it to 4 triangles (12 indices) is "expensive" in terms of error because it requires the triangle to be collapsed fully:

If I assume that the target should be 15 indices / 5 triangles (two quads and one stray triangle), the simplification error where this is reached is ~5e-4; so it should simplify correctly with a 10x higher error budget vs what seems to be used in the repro.

There are two components to this, they are a little related because of how the reg. factor was tuned: quadric precision, and regularization. They are related because regularization (with a low weight) is always enabled, and the factor was tweaked to roughly speaking be large enough that it has an effect even by default (both in terms of slightly higher triangulation quality, and in terms of stabilizing the quadric solve for simplifyWithUpdate), but small enough that rotated tesselated planes still simplify at roughly the same floor. See this comment #914 (comment)

Either way: the two planes here are a little different because neither is rotated (generally good for precision...), but one is displaced away from zero which increases the floating point drift. I looked briefly at the effect floating-point precision has here separate from regularization for individual planes:

Plane A (Z=0) error:

.	float	double
reg 1e-7	4.5e-5	3.5e-5
reg 0	3.7e-5	7.5e-10

Plane B (Z=900) error:

.	float	double
reg 1e-7	4.8e-4	3.0e-5
reg 0	5.5e-4	1.6e-8

The fact that errors are close for Z=0 plane between all 3 quadrants (except for double/0) is quite intentional and reflects the tuning mentioned above. The second plane shows the same tuning working correctly (similar errors in the first column), but I guess the reg. factor was a little too low once we account for "true" error.

Regardless: technically, using double precision here would drop the error to under the "5e-5" threshold from the repro, but the results are likely to be different for non-axis-aligned planes, and the example is quite artificial - notably, rotated planes have inherent wobble in the input coordinates (floats), which is absent here but would be present in more realistic inputs.

So based on this file alone my conclusion is just, "error limit should be adjusted for this asset to simplify" :) A perhaps more interesting test would be a finely tessellated polyhedron. It would also not have the additional interaction this test runs into against border quadrics.

I'll leave this issue open for reference for now, but I currently don't plan to act on this in any way; double precision quadrics are much more expensive and don't really solve the problem here as far as I'm concerned. There are formulations around relative quadrics that I looked into in the past but on typical game/realtime content they didn't produce enough of a benefit; they are cheaper than double precision quadrics so I might explore it at some point in the future. But overall I'm more interested in cases where the error is far away enough from zero that the precision concerns aren't that critical anyway.