Improve performance of weld() function

[timknip]

Describe the bug document transform "weld" function never finishes, or takes a very, very long time.

To Reproduce Steps to reproduce the behavior:

1. Load attached GLB: const doc = await io.read( 'weld-problem.glb' );
2. await doc.transform( weld() );

Expected behavior The weld should finish after a reasonable time.

Versions:

• 2.4.4
• Win 10, node 16.17,0

Additional context weld-problem.glb.zip

[donmccurdy]

Trying this in web and node.js now and I'm having trouble reproducing. Completes in about 1.5s, which isn't super fast, but also isn't the indefinite freeze you're seeing.

If you're using a Node.js environment, does it let you see anything about memory pressure?

[donmccurdy]

Not sure what action to take on this one sorry. The weld implementation here is slower than the one in three.js, but it also does a better job of handling per-attribute precision, in a way that is important for some other operations like compression. If meshoptimizer added a weld operation (which has been discussed I think), I would consider replacing my own with that. Or I'd be open to PRs that improve the current implementation too.

[donmccurdy]

Update – working on improving performance of weld() in https://github.com/donmccurdy/glTF-Transform/pull/803.

[bigrig2212]

Just tried gltf-transform CLI for the first time. Was about to post an issue about it hanging and not completing and not throwing errors. But after waiting long enough, i see that it was stuck on weld. But holy moly from 7megs to 42k, it was worth it, except that some of the mesh is missing (windows on the bus)... got to figure that part out.

[donmccurdy]

Thanks @bigrig2212! I'll reopen this issue until #803 is complete.

[donmccurdy]

Should be much faster in v3.1.3. :)

[donmccurdy]

Reopening, for some larger examples (https://sketchfab.com/3d-models/plant-3-5ecd9744ff6f4aa09766d796eec161ee) there are more optimizations that I think would be worthwhile. Changing compareAttributes to take a flat array as input helps a lot (–50%). Could even be worth moving this chunk of code to WASM.

[donmccurdy]

Welding has been a difficult function to optimize, with two main constraints:

1. avoid seams at quadtree / grid / bvh borders
2. allow meaningful 'tolerance' options

I've also seen welding exceed the maximum size of JavaScript's Map object, somewhere around 16M entries, which is not a problem I had encountered elsewhere.

Possibly constraint (2) could be relaxed in favor of something like binary equivalence (as meshopt does), but it's not obvious to me whether that would improve performance much.

This would probably be a good addition to the new benchmark suite, see #1214 and #1202.

[donmccurdy]

Proposed approach for a faster weld: Implement a custom hash table (see: MurmurHash) and hash prim vertices by all vertex attributes, i.e. binary equivalence. This would effectively mean a merge tolerance of 0 for all attribute types.

If that's sufficient in a majority of cases (I'll need to research this) then the older implementation (which is slower and more complex) can be removed. If not then maintaining both implementations would probably be necessary.

References:

• https://github.com/zeux/meshoptimizer/blob/e47e1be6d3d9513153188216455bdbed40a206ef/src/indexgenerator.cpp#L201
• https://developer.download.nvidia.com/whitepapers/2010/PN-AEN-Triangles-Whitepaper.pdf
• https://github.com/mikolalysenko/murmurhash-js/blob/master/murmurhash3_gc.js

[donmccurdy]

Performance of weld() will be improved further in glTF Transform v4.0, by:

• https://github.com/donmccurdy/glTF-Transform/pull/1237

[donmccurdy]

For anyone interested in trying it, I've made an alpha release of glTF Transform v4 with performance improvements to weld() from #1237. To test:

npm install --global @gltf-transform/cli@next

gltf-transform optimize input.glb output.glb

I expect v4 to be stable in the next few months.