Mesh Simplification is incomplete after one pass

[zalo]

@elalish It seems like there's room for additional simplification after one pass; perhaps topology should be simplified until no changes are made?

    general_offset = nonConvex.minkowski_sum(nonConvex.scale([0.5, 0.5, 0.5]))
    for i in range(5):
        save_mesh(general_offset, "general_offset_"+str(i), "stl")
        general_offset = general_offset.as_original()

Pass 0:

Pass 1:

Pass 2:

[elalish]

Yeah, that's probably a good idea for a stand-alone Simplify method - the internal one is aimed more at being fast dealing with what a single Boolean op creates.

[pca006132]

This is due to the order in which we perform edge collapses. We currently only do one pass over the list of halfedges in the order in the vector, but collapsing a halfedge with index i can cause halfedge j < i to be eligible for further simplification. Ideally we should have some kind of a worklist/set, when an edge is collapsed we check its neighbors to discover edges that can be further simplified. A worklist will be more efficient when the number of edges require collapsing is low (comparing with the total number of edges). I think this can combine with the optimization we mention in #679, i.e. only look for edge collapses among the newly-created verts in a Boolean, and will probably be faster than the current one we have.

[elalish]

Yeah, agreed. Currently EdgeCollapse is recursively checking neighboring edges for potential collapse, but I may be missing some cases.

[zalo]

Another interesting wrinkle... the slivers left over from some of the Minkowski operations appear to be cleaned up by the simplifications in asOriginal(), which also changes the Genus:

Before (Genus 4):

After calling as_original() 10 times (settled on Genus 5 after the first call):

Also worth noting the nearby triangle that is not getting simplified...

[pca006132]

Wonder what the black thing in your first photo is. Is this a bug in our boolean impl? And yeah, the lump of triangles not being simplified at the end is also interesting.

[elalish]

I would guess the black thing is a thin, disconnected mesh that's likely responsible for the genus being 1 low (an extra separate mesh will do that). On a second pass, I'm guessing it got simplified down to nothing.

[zalo]

Yep; that’s right! This is the same bug that was seen with Offset with the sliver meshes.

Simplify can often eliminate them (but not always).

[yxdragon]

is there any method to simplify mesh to polyhedron? (list of polygons, not only tri_verts, and tri_faces)

[elalish]

MeshGL contains that data, but you'll need to to use it to produce whatever polygon data structure you prefer. Any triangles that have the same faceID and are part of the same run are part of the same coplanar face and can be merged back together into polygons.

[yxdragon]

I got the face_id, I want a structure just like mesh. vert is n x 3, but faces is 2d list. not tri_face. I had got the faces id, so Is there a simple method to produce the face list? or need I do some geometry analysis? (I just deal with face without holes)

[pca006132]

Just triVerts. It is a flattened list of vertex IDs, [3*i, 3*i + 1, 3*i+2] defines a face.

[yxdragon]

import manifold3d as mfd
cube = mfd.Manifold.cube((1,1,1))
mesh = cube.to_mesh()


out:
mesh.vert_properties
array([[0., 0., 0.],
       [0., 0., 1.],
       [0., 1., 0.],
       [0., 1., 1.],
       [1., 0., 0.],
       [1., 0., 1.],
       [1., 1., 0.],
       [1., 1., 1.]], dtype=float32)
mesh.tri_verts
array([[1, 0, 4],
       [2, 4, 0],
       [1, 3, 0],
       [3, 1, 5],
       [3, 2, 0],
       [3, 7, 2],
       [5, 4, 6],
       [5, 1, 4],
       [6, 4, 2],
       [7, 6, 2],
       [7, 3, 5],
       [7, 5, 6]], dtype=int32)
mesh.face_id
[0, 1, 2, 3, 2, 5, 6, 0, 1, 5, 3, 6]

I want to trans the tri-mesh to polyhedron. (for a cube, I need 4 index to describe a face)
the face_id is the tri_verts's group id, but I need to merge the same group to polygon.

[elalish]

That's right, you'll need to merge them back into a polygon(s) by removing interior edges. Best you do that yourself, since naively they may produce concave polygons or polygons with holes, which you may want to avoid.

[yxdragon]

ok, I will process it myself. but is there an simple method to get the face polygon, when assuming the mesh is convex.

[elalish]

Lots of ways - e.g. find the half edges without pairs and assemble them into a loop.

[pca006132]

@elalish if you can verify if this is fixed or not, we can close this issue.

[elalish]

Fixed by #894 - SimplifyTopology now runs in a loop until it can't find anything to collapse.

[zalo]

This might be an interesting time to consider the Offset and Minkowski operations again… I think a great number of the failure cases of the Minkowski algorithm will be fixed/helped by the improved precision and improved simplification heuristic…

#666
#669

[elalish]

Yeah, certainly worth a look. We've got a bunch of breaking changes to close out for v3.0, but if you'd like to take another look, that would be great.