Implement 3D mesh offset

[pca006132]

Outline

Implement efficient 3D mesh offset, instead of using minkowski sum with high resolution spheres. (elalish/manifold#192)

Details

3D mesh offset is a useful feature that many users asked for, but is difficult to implement efficiently. Many users use minkowski sum with sphere to perform positive offset, but this can be very slow due to the need for exact convex decomposition.

Our approach will only work for positive offset, negative offset can be implemented by performing additional mesh boolean operations, so this is not an issue. The approach has four phases:

1. Figure out all pairs of faces that do not share any vertex and may overlap after offsetting. (let's call them conflict pairs)
2. Cut the mesh in a way such that for each part, no two faces are in the same conflict pair. (decomposition step, requires monte carlo tree search)
3. Perform the positive offset on each part, using a modified algorithm from Offset Triangular Mesh Using the Multiple Normal Vectors of a Vertex. Note that we need to figure out how to blend the surfaces for smooth results.
4. Union the parts.

Expected Outcome

A fast 3D mesh decomposition algorithm!

Project Properties

Skills

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

Difficulty

• Hard.

Size

• Long.

Additional Information

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

[zalo]

It might be worth observing previous attempts at Mesh Offsetting:

My Convex Decomposition PoC (Slow, Unclean Topology, Offset is just Minkowski Sum):
elalish/manifold#663

Emmet’s Pure Offsetting PoC (Slow, Rough Seams):
elalish/manifold#668

My Pure Offsetting Attempt (Slow, Smooth Seams, Brittle):
elalish/manifold#669

Minkowski Sums (Very Slow, Smooth Seams, Robust):
elalish/manifold#666

Ideally the offsetting solution should be fast, with smooth seams, and robust to multiple repeated applications. 😄

I’m still actively thinking about my Convex Decomposition algorithm; the next step will be to add merging between the Voronoi cells to simplify the resulting structure when possible 🤔

[hyunjinku]

I was looking for the exact function, and found that meshlib supports it!
Check this example!

[pca006132]

@hyunjinku they are using voxels for offset, which works but have drawbacks, e.g. losing fine details if the resolution is not high enough.

[MJ2021]

Hi @zalo @pca006132 are there any plans already available for this project or do we need to come up ourselves with some new ideas for the algorithm ?

[pca006132]

there are some ideas, but we don't know how well they will work, and this can be quite challenging to implement

[MJ2021]

Oh okay I understand