Add API to specify which vertices to lock when simplifying

[oisyn]

trafficstars

Hi,

We are using the meshoptimizer to simplify parts of a mesh, but I needed to be able to manually specify which vertices to lock. From #432 I gathered that the ABI of mesh_simplify was finalized, so I added a mesh_simplifyWithLocks variant that takes an extra array of vertex indices of vertices to lock. I've also added it to mesh_simplifyWithAttributes since that one is still experimental.

[zeux]

Two quick questions:

• I assume you are aware of meshopt_SimplifyLockBorder flag, and that doesn't work as you need more fine-grained control?
• Thoughts of passing a vertex-indexed array instead? I've been thinking about this capability for a bit now, but mostly resisted it as it expands the interface; when I thought about this I was hoping to combine two similar functions, per-vertex weight and per-vertex locking, into one API that's just a per-vertex weight/priority (could be u8). One extra advantage is there's no need for an extra count parameter or index validation for external APIs from memory-safe languages.

Obviously as an experimental feature this could be adjusted in the future, but ideally I try not to break experimental APIs so it would be good to settle on something that won't need to be adjusted.

[oisyn]

I assume you are aware of meshopt_SimplifyLockBorder flag, and that doesn't work as you need more fine-grained control?

Indeed. In our use case, the mesh is divided up into multiple meshlets and repeatedly joined and simplified. We want the borders of these meshlets to stay intact to avoid visible seams when adjacent meshlets are rendered at different lod levels.

However, the border edges of the original mesh can be simplified because they're never shared. So we need to be able to explicitely specify which edges (or vertices) can't be touched.

Thoughts of passing a vertex-indexed array instead?

Well that's definitely a possibility. Our own usecase doesn't have much use for a weight though, so I'll leave that judgement up to you 😉. In terms of interface itself, I would agree that the number of parameters is already huge. Perhaps group them all together into a struct and pass that instead? If you let the struct start with bitflags denoting which properties are filled in, you can add other members later on and still be ABI compatible.

[oisyn]

I was wondering, would a similar feature be able to work on simplifySloppy as well? I haven't done a deep dive through the algorithm yet, but I did saw that it doesn't use the classifyVertices function. I don't think it's possible to lock vertices at all, or is it?

[zeux]

It's a completely different algorithm but it should be possible to implement. I think if you change computeVertexIds to assign an id to locked vertices that is (1u << 31) | unsigned(i), everything else would just work: that will make sure that the algorithm finds a grid size that will result in the correct number of triangles if the remapping is done properly, and for each unique id it allocates a cell (which will contain just that vertex for locked vertices), this will result in that one vertex being selected as representative, which should then make the remap keep that vertex in place.

[gents83]

@zeux do you think this PR (or some kind of refactored form of this) will be merged?

[zeux]

Yes, I plan to look into this in the future. This PR currently can't be merged as is - there's API questions that we haven't resolved and it breaks various builds in its current form.

[oisyn]

I'll definitely be up for refactoring this PR if we can flesh out a favorable API.

[Makio64]

This feature looks awesome! I was looking to something similar, thanks @oisyn +1 to pass a struct instead of so many parameters

[gents83]

@oisyn out of curiosity did you already tried just playing with the meshopt_SimplifyLockBorder flag working on meshlets and "merged meshlets"?

[oisyn]

@gents83 Yes, the thing is that the original mesh might not be a closed manifold and has borders of its own. It's perfectly fine, even required, that this original border gets simplified along with the rest of the mesh. I only want the actual edges that join the meshlets together to stay intact. With meshopt_SimplifyLockBorder, that original border will remain in its original resolution.

[JMS55]

@zeux @oisyn any plans to push this forward? I would love to use this for generating hierarchical LODs for my meshlet renderer: https://github.com/bevyengine/bevy/pull/10164, and it would be awesome if the API I needed could be part of upstream.

[zeux]

Yes I plan to look into this further soon; you can probably use SimplifyLockBorder flag in the meantime (it will restrict simplification of meshes with open borders, but it will be sufficient for correctness).

[gents83]

Adding link to this discussion, that can bring some ideas using SimplifyLockBorder flag: #569

[zeux]

Coming back to this, my proposal would be to adjust the change as follows:

• Only extend meshopt_simplifyWithAttributes (don't provide extra functions)
• Extend it by adding an optional pointer parameter, something like unsigned char* vertex_locked - probably after attribute_count - which is 1 for each vertex that needs to be locked.

Rationale:

• meshopt_simplifyWithAttributes is still experimental and will probably stay experimental for a couple releases; it's ok to make backwards incompatible changes to it, and this change requires that anyway
• meshopt_simplifyWithAttributes is a super-set of meshopt_simplify - you can always pass no vertex attributes, that's equivalent to calling simplify. As locking in context of Nanite-style clustering is a very advanced use case it seems fine to require that.
• A per-vertex locked flag is more in line with the rest of the APIs than a separate vertex list; this can be extended to a per-vertex bit-set in the future without breaking compatibility if there's other good use cases
• Adopting a structure to reduce parameter count is orthogonal, could be done separately, is not how all other APIs work and has some complex ABI questions anyhow, so we should not do this as part of this change.

In JS interface we can probably just pass 0 for now to keep tests running.

@oisyn let me know if this would work for you and whether you'd be up for adjusting the PR accordingly; alternatively I can also take a look at making this change myself in the next week or so.

[oisyn]

Hi @zeux, yes this would work for me. I'll pick this up right now.

[oisyn]

Ok, I've made the necessary changes

• mesh_simplifyWithLocks was removed
• A vertex_lock argument was added to mesh_simplifyWithAttributes, taking an const unsigned char* of length vertex_count, which indicates whether a vertex can be simplified (0) or locked (1).

EDIT: hold on, fixing the tests... 😉

[JMS55]

Might want to allow passing a nullptr for vertex_lock to avoid allocation for cases where users don't want to lock anything.

[oisyn]

@JMS55 That is in fact allowed, but I see I have not specified that in the comments 👍

[oisyn]

Alright I have fixed all the native tests.

As for JS, I implemented it to the best of my abilities. I think the missing part is the WASM binary generation that needs to go in the meshopt_simplifier.js file (and module), I'm not sure how to do that.

[zeux]

I can push the updated binaries, I think this checkbox might not be set though which prevents me from doing that.

[oisyn]

I'm not seeing that checkbox 😬

[oisyn]

According to this github issue: https://github.com/orgs/community/discussions/5634, it won't work for cross-organizational repos 😐

[zeux]

git was built for email patches after all.

meshopt_simplifier_js.zip

[oisyn]

Thanks! All tests appear to pass.

[zeux]

Thanks!