Repository: zeux/meshoptimizer (language: cpp)

Issue:
gltfpack produces broken result for skinned parts of mesh
1. Download https://github.com/prefrontalcortex/glTF-Sample-Models/raw/carbon-frame-bike/2.0/CarbonFrameBike/glTF-Binary/CarbonFrameBike.glb
2. See reference images at https://github.com/prefrontalcortex/glTF-Sample-Models/tree/carbon-frame-bike/2.0/CarbonFrameBike
3. Run `gltfpack -i CarbonFrameBike.glb -o CarbonFrameBike.packed.glb`
4. Open the result in e.g. [Babylon Sandbox](https://sandbox.babylonjs.com/) or Gestaltor
5. Note that the wires don't survive packing well:
  ![image](https://user-images.githubusercontent.com/2693840/178118767-575834d6-8445-408a-8025-00618e8fcf6c.png)

Reference: 
![image](https://user-images.githubusercontent.com/2693840/178118964-dd1a972b-553c-49a7-82f5-e639de0e53b7.png)


Using `-noq` works around the problem, but I thought it would be worth still raising an issue since the result looks relatively broken with default parameters.


Discussion / hints:
fwiw this looks as if the default number of bits (14) gltfpack uses for quantization isn't sufficient for this model. In certain cases this can be avoided by recentering the mesh, which gltfpack doesn't do automatically, but sometimes it's just something that needs to be raised via `-vp` command line flag.

I'll keep this open for a bit because I need to check if gltfpack can improve this automatically by changing the mesh internally (which may be difficult for skinned model because right now gltfpack avoids doing any transforms on the skinned nodes due to three.js issues with culling), but using something like `-vp 16` is likely to improve this noticeably.
Right, so:

1. This can be improved via `-vp 16`
2. This happens because the wires in question have a very large internal scale value (of 100 - this looks like an improper coordinate system conversion somewhere; probably the inverse scale of 1/100 was baked into the vertex data). Since quantization is done in local space, but using a single global quantization grid (relaxing this is difficult because eg several meshes can reuse skin objects and the quantization scale needs to be corrected via skinning transforms), the vertices end up being quantized with suboptimal values.

I think you don't see the issue in glTF-Transform because it's not quantizing the values, either because it just doesn't support quantization on skinned meshes, or because it requires an explicit command line instruction to enable that.

Either way, I don't think this can realistically be fixed in quantization code, and propagating the scale value "into" mesh vertices would result in different bone transforms which may be important for other applications.
P.S. The node with an abnormally high scale (100) that causes all this is Armature_S1/S2/S3. Maybe this is an artifact of a Blender export judging by the name, or maybe the source model is just configured in an odd way.
I guess the one thing that gltfpack could do is compute two quantization grids, one for skinned meshes and one for non-skinned meshes... but it's a little silly to do that as it assumes that all or none of the skinned meshes in the model are poorly quantized due to abnormal scale values. If this example comes up in the future that could be a possible option but for now it feels like this shouldn't be handled by gltfpack.
@zeux glTF Transform does quantize the vertex positions to 14 bits as well. I think the difference is that glTF Transform offers two quantization grids:

```
    --quantization-volume <volume>       Bounds for quantization grid.
                                         one of "mesh","scene", default: "mesh"
```

While 'mesh' may occasionally introduce seams where meshes are expected to align, I've found it mostly fine as a default. Comparing the two modes in glTF Transform:


| mesh | scene |
|---|---|
| <img width="489" alt="Screenshot 2023-10-27 at 11 12 17 PM" src="https://github.com/zeux/meshoptimizer/assets/1848368/7c066f53-d991-4254-8a07-b8179c2a4590"> | <img width="529" alt="Screenshot 2023-10-27 at 11 10 12 PM" src="https://github.com/zeux/meshoptimizer/assets/1848368/a9b342e1-581b-458f-9dd5-fc6ac1774bac"> |


I've exposed that flag to the CLI on the standalone `quantize` command, but not the `meshopt` command, which was an oversight...

> EDIT: To be fixed in https://github.com/donmccurdy/glTF-Transform/pull/1144.
Yeah, seams are one reason why I've avoided per-mesh quantization. There's also issues with volume thickness (... this is really a spec issue in hindsight but oh well) in that if two meshes use the same material that has the extension, they need to use the same quantization scale. This also applies to skinning - since skinning matrices need to be adjusted, using a single skin for two meshes with different grids must also tie them together.

This is all doable but cumbersome which is part of why I've been avoiding fixing this :)
> the one thing that gltfpack could do is compute two quantization grids, one for skinned meshes and one for non-skinned meshes

Upon closer inspection this doesn't solve this scene fully, as it has 2 unskinned meshes in addition to skinned meshes that have scale 100; they are smaller and harder to see but it would still be an issue.

So besides using `-vpf` the only way to solve this appears to be per-mesh quantization scale which requires a fairly large change and some thought as to whether this changes the defaults, which would need a lot of testing... I think this will not happen for the upcoming version as it's too significant of a change for a fairly core part of gltfpack, so I'm removing this from consideration for 0.20.

Fix patch:
diff --git a/gltf/stream.cpp b/gltf/stream.cpp
index 1ed7276f9..04278ba7a 100644
--- a/gltf/stream.cpp
+++ b/gltf/stream.cpp
@@ -24,10 +24,25 @@ struct Bounds
 	{
 		return min.f[0] <= max.f[0] && min.f[1] <= max.f[1] && min.f[2] <= max.f[2] && min.f[3] <= max.f[3];
 	}
+
+	float getExtent() const
+	{
+		return std::max(max.f[0] - min.f[0], std::max(max.f[1] - min.f[1], max.f[2] - min.f[2]));
+	}
+
+	void merge(const Bounds& other)
+	{
+		for (int k = 0; k < 4; ++k)
+		{
+			min.f[k] = std::min(min.f[k], other.min.f[k]);
+			max.f[k] = std::max(max.f[k], other.max.f[k]);
+		}
+	}
 };
 
-static void updateAttributeBounds(const Mesh& mesh, cgltf_attribute_type type, Bounds& b)
+static Bounds computeBounds(const Mesh& mesh, cgltf_attribute_type type)
 {
+	Bounds b;
 	Attr pad = {};
 
 	for (size_t j = 0; j < mesh.streams.size(); ++j)
@@ -73,6 +88,8 @@ static void updateAttributeBounds(const Mesh& mesh, cgltf_attribute_type type, B
 		b.min.f[k] -= pad.f[k];
 		b.max.f[k] += pad.f[k];
 	}
+
+	return b;
 }
 
 QuantizationPosition prepareQuantizationPosition(const std::vector<Mesh>& meshes, const Settings& settings)
@@ -82,19 +99,34 @@ QuantizationPosition prepareQuantizationPosition(const std::vector<Mesh>& meshes
 	result.bits = settings.pos_bits;
 	result.normalized = settings.pos_normalized;
 
-	Bounds b;
+	std::vector<Bounds> bounds(meshes.size());
 
 	for (size_t i = 0; i < meshes.size(); ++i)
-	{
-		updateAttributeBounds(meshes[i], cgltf_attribute_type_position, b);
-	}
+		bounds[i] = computeBounds(meshes[i], cgltf_attribute_type_position);
+
+	Bounds b;
+	for (size_t i = 0; i < meshes.size(); ++i)
+		b.merge(bounds[i]);
 
 	if (b.isValid())
 	{
 		result.offset[0] = b.min.f[0];
 		result.offset[1] = b.min.f[1];
 		result.offset[2] = b.min.f[2];
-		result.scale = std::max(b.max.f[0] - b.min.f[0], std::max(b.max.f[1] - b.min.f[1], b.max.f[2] - b.min.f[2]));
+		result.scale = b.getExtent();
+	}
+
+	if (b.isValid() && settings.quantize && !settings.pos_float)
+	{
+		float error = result.scale * 0.5f / (1 << (result.bits - 1));
+		float max_rel_error = 0;
+
+		for (size_t i = 0; i < meshes.size(); ++i)
+			if (bounds[i].isValid() && bounds[i].getExtent() > 1e-2f)
+				max_rel_error = std::max(max_rel_error, error / bounds[i].getExtent());
+
+		if (max_rel_error > 5e-2f)
+			fprintf(stderr, "Warning: position data has significant error (%.0f%%); consider using floating-point quantization (-vpf) or more bits (-vp N)\n", max_rel_error * 100);
 	}
 
 	result.node_scale = result.scale / float((1 << result.bits) - 1) * (result.normalized ? 65535.f : 1.f);
@@ -154,7 +186,9 @@ void prepareQuantizationTexture(cgltf_data* data, std::vector<QuantizationTextur
 			continue;
 
 		indices[i] = follow(parents, indices[i]);
-		updateAttributeBounds(mesh, cgltf_attribute_type_texcoord, bounds[indices[i]]);
+
+		Bounds mb = computeBounds(mesh, cgltf_attribute_type_texcoord);
+		bounds[indices[i]].merge(mb);
 	}
 
 	// update all material data using canonical bounds


Test patch: