Overlap removal

[pca006132]

Outline

Remove overlaps in meshes that contain self-intersection, assuming the mesh is a manifold.

Details

Basically, a valid solid mesh should be both manifold and has no self-intersection. However, models from the internet may contain defects. This project is about coming up with an algorithm that removes self-intersections.

See elalish/manifold#289 for details about ideas for the algorithm.

Expected Outcome

Implementation of said algorithm.

Future Possibilities

Project Properties

Skills

• C++
• Graph data structure.
• Algorithms.

Difficulty

Hard.

Size

Long (350h)

Additional Information

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

[vinayakjeet]

Hi @elalish @pca006132 and team,

I've reviewed the discussion in #289 and the overall objectives for overlap removal (#96), and I'm excited to begin tackling this feature.
🚀

[vinayakjeet]

With respect to the discussion in #289, how does the triangulator deal with polygons, like bowtie or star-shaped polygons with nested holes? Is this an area for improvement?

[pca006132]

With respect to the discussion in #289, how does the triangulator deal with polygons, like bowtie or star-shaped polygons with nested holes? Is this an area for improvement?

No, it works fine with these polygons. I think you can try to look at the regular triangulation algorithms first, understand how they work with non-convex polygons and polygons with holes, and then come back to this.

[elalish]

Here's some info on our triangulator: https://github.com/elalish/manifold/wiki/Manifold-Library#polygon-triangulation

What's your background? Have you written computational geometry algorithms before?

[vinayakjeet]

I've explored curve approximations but haven't written full geometry algorithms. I'll study triangulation methods and Manifold's approach—thanks for the reference!

[vinayakjeet]

Do you have an IRC channel where I can ask questions?

[pca006132]

There is an unofficial discord: https://discord.gg/22kHZVpKBP, manifold channel.

[elalish]

You're also welcome to ask questions here or make a github discussion thread - I haven't gotten in the habit of checking discord yet, though I can if necessary.

[vinayakjeet]

No issues, I'll ask here if needed.

[wasup-yash]

Hey, This feature seems fascinating to work on, I read the discussion on overlap removal and would be starting to draft a proposal with a formulated structure on how to go about this, Need to go through the methods too, and about their implementation meanwhile :)
also, can you inviteme again ? cause the above invite of discord seems to be expired.

[pca006132]

Hey, This feature seems fascinating to work on, I read the discussion on overlap removal and would be starting to draft a proposal with a formulated structure on how to go about this, Need to go through the methods too, and about their implementation meanwhile :) also, can you inviteme again ? cause the above invite of discord seems to be expired.

Weird, it seems that it is not expired:

Anyway, here is another link that hopefully is not yet expired: https://discord.gg/6PB7qZ4HC7

[wasup-yash]

Hey, This feature seems fascinating to work on, I read the discussion on overlap removal and would be starting to draft a proposal with a formulated structure on how to go about this, Need to go through the methods too, and about their implementation meanwhile :) also, can you inviteme again ? cause the above invite of discord seems to be expired.

Weird, it seems that it is not expired:

Anyway, here is another link that hopefully is not yet expired: https://discord.gg/6PB7qZ4HC7

thank you, Joined