Improve mesh simplification and mesh ID handling

pca006132 commented 5 months ago

Outline

Improve mesh operation performance by improving the mesh simplification algorithm and making mesh ID tracking opt-in.

Details

Mesh Simplification

See https://github.com/elalish/manifold/issues/675. We should be able to only perform simplification for newly added vertices, and use a worklist to ensure that mesh simplification reaches a fixed-point.

Mesh ID Tracking

We currently track mesh id for boolean operations and compose, which allows users to figure out where a particular triangle comes from and reapply certain properties. Triangles from different meshes will not be collapsed, so in some cases tracking this information can have significant overhead (https://github.com/elalish/manifold/pull/671).

We can make mesh ID tracking an opt-in feature.

Default mesh ID is 0.
IncrementMeshIDs will only remap non-zero IDs.
We treat meshes with mesh ID 0 as from the same mesh, and coplanar triangles can be collapsed.
To opt-out from this behavior, the user should call AsOriginal for the boolean operands to give the mesh some non-zero initial ID, and future boolean operations will give the result different mesh IDs due to calls to IncrementMeshIDs.
Also, AsOriginal can accept an optional parameter to only update specific IDs.

// cubes have mesh ID 0, so result also have mesh ID 0
Manifold result = Cube() + Cube();
// give result2 mesh ID 1
Manifold result2 = result.AsOriginal();
// result3 has mesh ID 2 and 0, where ID 2 is from ID1 from result2, and 0 is from Cube.
Manifold result3 = result2 + Cube();

Expected Outcome

Designed mesh ID behavior as above, and good performance.

Project Properties

Skills

C++
Basic algorithm knowledge.

Difficulty

Medium

Size

Medium (175h)

Additional Information

Potential mentor(s): @pca006132 @elalish
Organization website: https://manifoldcad.org
Communication channels: https://github.com/elalish/manifold/discussions

MJ2021 commented 4 months ago

Hi @elalish for improving the existing algorithms are ideas already available or we need to come up with new ideas ?

pca006132 commented 4 months ago

the ideas are there, but the implementation may still need you to come up with some ideas to bridge the gaps.

MJ2021 commented 4 months ago

Oh okay, so can you a give an idea what should I study if I want to implement this ? Also I assume this project has 2 parts of which first is mesh simplification and then the mesh ID tracking so are these 2 independent or they will be done in parallel ?

pca006132 commented 4 months ago

you should just study the existing codebase. They are not independent, they should be done in parallel.

elalish commented 3 months ago

These are certainly related, but I'm not sure their implementations will overlap too much. You should study SimplyTopology() and anywhere meshID is used.

@pca006132 I wonder if by default it should be opt-in for our primitive constructors, but opt-out for constructing from MeshGL? And I was thinking AsOriginal(int id), where if id is specified, it updates the manifold to that ID, and if you use 0, then it effectively opts-out again. Does that sound like what you had in mind?