STL is not manifold

[danieltwagner]

First, thank you for building this amazing project!
I was trying to programmatically generate 3d-printable enclosures and came across sdfx and it seems like a very good fit.

I ran examples/box/main.go but when loading the resulting top.stl file in Cura I get a message saying that my model is not manifold, which I take to mean that it doesn't have closed surfaces all around.

I can't really see any marked areas so perhaps those are internal? Potentially related, I also notice that the resulting STL file is very large for the given geometry, which I take is because of the marching cubes algorithm used in sdfx?

The bottom is marked red but I believe that's different from Cura's way of marking non-manifold areas (red + green).
Any suggestions for how to address this?

[aevyrie]

FYI, the red surfaces in Cura are just overhangs - any surfaces within some angle of facing downward.
(I have no other helpful sdfx-related input 😄)

[kbrafford]

FYI, the red surfaces in Cura are just overhangs - any surfaces within some angle of facing downward.
(I have no other helpful sdfx-related input 😄)

In Cura red surfaces can also mean missing or improperly normaled surfaces as well.

There is an autodesk tool that can help you repair models like this but I can’t remember its name.

[aevyrie]

Meshmixer?

[danieltwagner]

Thanks for the helpful suggestions! It does indeed look like red is just an overhang as when I rotate the part the bottom is red and the red ridges in my screenshot are all solid yellow.

While I appreciate that there may be tools that fix the model I would prefer to understand how it got to be non-manifold in the first place and how to prevent that.

[deadsy]

You're quite right - I took a look at the model (per the repo) in meshlab - it reported "15 non manifold edges" and "45 faces over non-manifold eges" Bugger. I'll have to go back into the model and work out what's going on. Having said that... the red area you indicated is overhang. It's designed to be printable with the outer case face on the bed, ie - the XZ plane. You'll probably have to rotate it before printing, or just do a final transform in the code. If you can force your slicer to ignore the non-manifold edges it will print ok- I've printed quite a few. But yes - it should be manifold STL.

As for large STLs: See: #6

[danieltwagner]

I've had a quick look and am suspicious of mcToTriangles, as on the bottom part of the model I see this:
https://www.dropbox.com/s/nb1f86rwle1djmw/Screen%20Recording%202020-10-02%20at%209.36.23%20PM.mov?dl=0

[deadsy]

Try this:

diff --git i/examples/box/main.go w/examples/box/main.go
index 92b4353..d23b460 100644
--- i/examples/box/main.go
+++ w/examples/box/main.go
@@ -27,9 +27,9 @@ func box1() {
 
        box := PanelBox3D(&bp)
 
-       RenderSTL(box[0], 300, "panel.stl")
-       RenderSTL(box[1], 300, "top.stl")
-       RenderSTL(box[2], 300, "bottom.stl")
+       RenderSTLSlow(box[0], 300, "panel.stl")
+       RenderSTLSlow(box[1], 300, "top.stl")
+       RenderSTLSlow(box[2], 300, "bottom.stl")
 }

This gives a manifold object for my test case.

RenderSTL does an octree decomposition of space.
RenderSTLSlow decomposes space using the minimum cube size.
If the distance field is not quite right then RenderSTL will sometimes show problems where RenderSTLSlow does not.

I didn't think the objects in the box model had that problem - but I suppose they do.

In any case the mcToTriangles is common to both- so that appears to be ok.

[danieltwagner]

Sure enough, that does seem to create a manifold object. It does, however, use different points and more cubes than were specified.

RenderSTLSlow
rendering panel.stl (301x234x22)
rendering top.stl (251x201x301)
rendering bottom.stl (251x201x301)

RenderSTL
rendering panel.stl (300x232x20, resolution 0.15)
rendering top.stl (250x200x300, resolution 0.20)
rendering bottom.stl (250x200x300, resolution 0.20)

So it could be that the triangle in question just never appears in the RenderSTLSlow variant. Or it could be that something is up with the octtree.

It also seems that in my screen recording we see many more non-manifold parts of the object than Meshlab finds. Its definition is "edges with more than two incident faces", whereas we can see lots of edges with a single incident face also leading to a non-manifold object. Perhaps in a the more general case it can be valid to have a single face jutting into space but for marching cubes that is certainly never correct, so we might consider checking edges to have have always exactly 2 incident faces...

[danieltwagner]

Some progress in diagnosing, but also some bad news: The issue also appears with RenderSTLSlow, it's just that Meshlab doesn't correctly identify the non-manifoldness of the resulting shape. The following Python3 script will repro nicely both on the fast and slow render option.

import sys
import trimesh  # pip3 install trimesh networkx pyglet

from collections import defaultdict

def main(path):
    mesh = trimesh.load(path)
    if mesh.is_watertight:
        print("Model is manifold, nothing to see here...")
        return

    print("Model is non-manifold. Finding offending edges...")

    incident_faces_by_edge = defaultdict(list)

    for i, f in enumerate(mesh.faces):
        # build a map of faces incident to an edge
        edges = [
            (f[0], f[1]),
            (f[1], f[2]),
            (f[2], f[0]),
        ]
        for e in edges:
            incident_faces_by_edge[tuple(sorted(e))].append(i)

    # Compute the number of incident faces per edge and color any faces adjacent to edges with incidence != 2
    example_face = None
    example_face_incidence_cnt = 1  # 4 and 6 also exist

    incident_face_count = defaultdict(int)

    for edge, incident_faces in incident_faces_by_edge.items():
        incident_face_count[len(incident_faces)] += 1
        if len(incident_faces) != 2:
            for f in incident_faces:
                mesh.visual.face_colors[f] = trimesh.visual.random_color()

            if not example_face and len(incident_faces) == example_face_incidence_cnt:
                example_face = incident_faces[0]

    for n in sorted(incident_face_count.keys()):
        print("Number of edges with %d incident faces: %d" % (n, incident_face_count[n]))

    # construct a smaller mesh with only some example faces
    poi = mesh.vertices[mesh.faces[example_face][0]]  # the first vertice of our example face
    example_faces = set()
    example_face_distance = 0.5 # 0.0001 to get only faces touching poi

    # build our set of example faces that are near touch vertice (21.75, 0, 25.7)
    for i, f in enumerate(mesh.faces):
        for v in f:
            if (abs(mesh.vertices[v][0] - poi[0]) < example_face_distance and
                abs(mesh.vertices[v][1] - poi[1]) < example_face_distance and
                abs(mesh.vertices[v][2] - poi[2]) < example_face_distance):
                example_faces.add(i)

    print("Sample mesh contins %d faces" % len(example_faces))
    small = mesh.submesh([[f] for f in example_faces], append=True)
    for i in range(len(small.faces)):
        small.visual.face_colors[i] = trimesh.visual.random_color()

    small.show()  # press c to toggle backface culling, w for wireframe


    mesh.show()

if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Must specify a file to load")
        sys.exit(1)

    main(sys.argv[1])

[danieltwagner]

I've made some partial headway. What remains after PR #19 is to figure out why there are what appear to be degenerate triangles in the mesh.

In the debug subgraph produced by the script above (filtering for an example with 4 incident edges) I'm spotting faces that have only two unique vertices. How exactly those faces become part of an edge with multiple incident faces is as yet unclear...

[danieltwagner]

Thank you for merging my edits and subsequently improving them. The algorithm still produces non-manifold meshes in certain corner cases:

	size := 10.0
	length := 30.0

	// This makes it easier to have the edges join up than using a box
	p := NewPolygon()
	p.Add(-0.5*size, 0)
	p.Add(0, 0.5*size)
	p.Add(0.5*size, 0)
	p.Add(0, -0.5*size)

	inner := Extrude3D(Polygon2D(p.Vertices()), length)
	outer := Box3D(V3{size, size, length}, 0)

	// ask for a non-manifold mesh
	trouble := Difference3D(outer, inner)

	RenderSTL(trouble, 300, "trouble.stl")

It's not obvious to me what the best solution would be here, as we're explicitly asking for a non-manifold shape. Perhaps this is therefore as designed?

[deadsy]

As a practical matter, the correction for that case is pretty simple. ie- reduce the size of the inner marginally to clean up those knife edge issues. Or - increase it slightly if 4 wedges was really what you wanted. More generally marching cubes is a sampling process of finite precision and it runs into issues with features that require better spatial resolution to be turned into a good mesh. In this case dropping the resolution (E.g. 100) will get rid of the non-manifold edges, albeit with introduced gaps at the joins.

[danieltwagner]

That makes sense. I'll close the issue as mesh generation seems to be manifold now when one doesn't create a situation built specifically to tease out these special cases.