Improve mesh simplification and mesh ID handling

[pca006132]

Outline

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

Details

Mesh Simplification

See elalish/manifold#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 (elalish/manifold#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]

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

[pca006132]

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

[MJ2021]

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]

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

[elalish]

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?

[MJ2021]

Okay and how I should I start contributing now and prepare for my application ?

[elalish]

Probably start by asking specific code questions and proposing how to make your change, like what files and functions need work - you can either do that here or you can start a draft PR, which lets us have multiple discussion threads for different parts of the code. You want the application to be detailed enough to make it clear you've familiarized yourself with our code base and you understand where the easy and hard parts of the work will be.

[MJ2021]

Sure can you provide me the link that exactly where is this code, I am not able to find that
Thanks

[elalish]

No, this is good practice for you. Both VSCode and Github allow you to search an entire code base. See what you can find.

[MJ2021]

Hi, sorry for the late reply I got a bit busy with some academic commitments. I have looked at the code base and I think the main changes that we need to do is in the "meshIO" folder where there are 2 files namely meshIO.h and meshIO.cpp, can you guide if I am going in the right direction ?

[pca006132]

No, mesh simplification is run after boolean operation, not only when doing imports/exports.

[MJ2021]

Hi, I have created a draft PR can we have more discussion there about the code ?
elalish/manifold#779
Thanks

[MJ2021]

Hi, can you provide some information how I should prepare my proposal for this project ? Also being a beginner I was not able to do much in this project till now so will this be a problem ?

[pca006132]

I think the guideline is just the generic one, show your interest as well as past experience in courses/other work. It is fine that you was not able to do much in this project until now, but to be honest it will put you in slight disadvantage, there is no way for us to see your understanding on the subject, so you should show it in your proposal..

[MJ2021]

Can you provide some suggestions on how I can improve my proposal and increase my chances of learning more https://docs.google.com/document/d/1nbpG2qp6sLyp4vVg3LaIYWKqhQTKWQMinds9pmI3qss/edit

[MJ2021]

Is there an official discussion channel for the project ?

[elalish]

This is it!