Lost faces when creating manifold

[ramcdona]

I am trying to create a 'thin' manifold surface by duplicating a non-manifold surface, changing its orientation, and then stitching the two together.

This results in 'lost' triangles at some of the corners as seen below...

Here, the blue lines are the mesh as fed into the manifold constructor. The gold is a shaded view of the mesh returned by GetMesh() immediately after construction. No operations have been performed, just a round-trip through manifold.

The attached zip file contains a .obj and .ply file for this example case. Both contain the 'full' connectivity -- but the *.obj does not include FaceID's. Every face was assigned a unique integer FaceID.

Archive.zip

[ramcdona]

I've spent a little time digging into this. As expected, SimplifyTopology() is flagging edges for collapse.

Pictured below, we have the thin manifold -- but where I've offset the surface to make it thick and allow us to visualize the connected topology.

In this case, 32 short edges are collapsed. This corresponds to all of the vertical edges. Each one is flagged twice, once as it appears from each triangle. I've instrumented SimplifyTopology() and have verified this behavior.

Unfortunately, this leaves us back where we were before -- after the collapse, those outer triangles share all three nodes, which leads to the vanishing tris.

It seems to me like SimplifyTopology() is working as intended. We either need to change one of the assumptions somewhere else, or find a workaround.

Is there really a problem if we make the 'short edge' test optional? In my very preliminary testing, things seem to still work if I change the condition to if (false && bflags[i])

I'm not entirely opposed to simply flipping the diagonals on some of the quads to prevent this from happening. I'm a little concerned that it will be a challenge to ensure this is a robust solution for all possible topologies in my program, but I can work with that.

The current approach was designed to provide as much symmetry as possible. We change diagonal orientation four times as we go around a cylinder in the V direction -- but we never change the orientation in the U direction. I could come up with some approach to flipping the diagonals to work around this immediate problem.

Symmetry in mesh was desired to avoid any artificial asymmetry in an otherwise symmetrical aerodynamic simulation. Even with a symmetrical geometry and flow condition, an asymmetrical mesh would result in rolling moments, side forces, and other asymmetrical results in the final solution.

[pca006132]

I think it is fine to disable the mesh simplification phase, but iirc the boolean algorithm will create quite a lot of degenerate triangles and simplification can help a lot.

Maybe we should selectively disable mesh simplification for some edges? iirc the vert properties API can do it, but not sure if it is suitable for this case.

[elalish]

Thanks for looking into this, your analysis makes sense. I guess this is what I meant by "thin manifolds should work, but haven't been tested much" - as you see the algorithm wasn't really designed with them in mind. I'd like to see how far you can get with your workaround. I don't really want to optimize this library for something it wasn't designed for (objects with no volume), but I'll consider it as I understand the problem space better.

For instance, could you make your wing thick enough that the edges aren't short, then extract the part of the result corresponding to the top surface?

[ramcdona]

Making the wing finite thickness will introduce a hole at the side of body where the intersection occurs. When a flat plane exactly intersects along a mesh line, the hole will be to one side. I think it will get messy.

Much easier for me to just set up the topology of the mesh such that corners aren't drawn like that.

I'll see how much progress I can make that way.

[ramcdona]

I think I've worked around this issue by simply making my program excessively clever about which diagonal it inserts.

However, I'm now seeing a case where a boolean operation drops some tris that it shouldn't. This is a case of a thin manifold exactly intersecting along the mesh line of a thick body. It usually works, but I can find cases where it doesn't.

What is the best way to submit such a test case? There is a lot of build infrastructure required to set up a full MWE in Manifold.

Perhaps this already exists, but if the Manifold project included a simple command-line CSG application, I could probably submit a MWE as two files and a command line to execute replicating the issue. Such an application could also become a platform for more complex tools to be built -- I'm thinking along the lines of Unix's philosophy of a bunch of command line tools that each do one thing, but can be chained together with pipes and redirects.

I'm thinking something with a command line like...

manifoldCSG file1 -union file2 -output file3

It could be simple and just work with two files -- or one could get fancy and make the command line a RPN-style stack of boolean operations file1 file2 -union file3 -output or something that could handle an arbitrary tree of operations.

I know about https://manifoldcad.org/, but I'm looking for something fundamentally simpler. I.e. that doesn't require setting up a web server to provide a MWE.

In any case, it could serve as 1) an example of Manifold best practice programming. 2) a little-work MWE for bug reports. 3) a useful tool in its own right.

It probably already exists and I'm just missing it...

[ramcdona]

Just to follow up my last comment. Here is an image of a CSG operation gone wrong (missing triangles in result)

The black line at the leading edge of the wing indicates a triangle that is inadvertently getting dropped.

The wing is a thin surface manifold that intersects the pod exactly along a mesh line (of the pod). I can make slight changes to the wing's mesh resolution that make this case work fine. None of those changes 'should' add/remove degeneracy.

[elalish]

The two main ways to create MWE are indeed manifoldCAD.org (no web server needed, just paste in here whatever JS you used) and writing a TEST and submitting it as a PR (so we can see the CI fail). Our web app is easy, but doesn't always repro a given edge case due to compilation differences, and critically, it doesn't support loading external models yet (though you can paste in lists of verts and tris). With a TEST we do have a function for loading models (which you can include in your PR) and it'll get checked on all the compilation targets automatically.

As to your test case, again, I'm not terribly surprised; technically the solution given is correct, as the winding number of all points in R3 at least precision away from a surface is the same as in the expected output. The reason these get clipped is that if you e.g. subtract an object from itself (or partially) you don't really want a bunch of zero-thickness surfaces hanging around, so we make some effort to clip them out. In this case, the zero-thickness surfaces are what you want. I need to think about this some more, but there may be a fairly simple fix.

[elalish]

Here's an example of someone who wants the opposite: https://github.com/openscad/openscad/issues/4769

[ramcdona]

I certainly understand the other situation -- when you subtract a body from another, you probably don't want infinitely thin surfaces added.

However, I started out with this shape and took a union with it. The situation seems very different, but I don't know how the code should be able to tell the difference.

In my case, both faces originate from the same mesh. In the subtractive face, the faces originate from different meshes.

In my case, I've intentionally made the triangulations of both sides of the thin manifold the same. While this could be true in the subtractive case (subtract something from itself), it does not have to be. If you want to get rid of the thin triangles when doing a Boolean difference, you'd have to handle the case where the two coincident surfaces have very different triangulations....

The current behavior feels very inconsistent -- if it is going to clip the zero thickness surface, then the whole thing should get blown away. If it is going to allow the union, then it should work the same every time -- right now it sometimes works and sometimes doesn't just because.

I understand the finicky nature of floating point error, but consistency of results despite floating point behavior is exactly one of the goals a robust tool should be seeking.

I don't know if it will help track things down, but this wing should lie exactly in the Z=0 plane. It is possible that it isn't perfect due to the way everything is constructed and processed to this point, but we're at least in the neighborhood where eps is very small because our values are nearly (if not exactly) zero.

[elalish]

Yeah, I've largely been coming to the same conclusion - I don't think it's possible for us to remove thin surfaces in general, so we probably shouldn't remove any (at least not in our post-process). I need to experiment and see if that causes unexpected problems.

[ramcdona]

I've updated to the v2.2.1 release and it seems to have made an improvement in this case.

Is that plausible? Or do you think it is just the luck of the draw?

If we think it is plausible, then I'll spend a little more time looking for a failure case like this, but I'll be optimistic that we're good to go.

If it seems highly unlikely, then I'll work harder at isolating another failure case.

Thanks for all the effort -- and congrats on the release either way.

[ramcdona]

Oops, I spoke too soon. I'm still seeing this behavior as usual.

I had changed something in my test case and had not changed it back.

[elalish]

I believe the problem here is that the decimator removes short edges, creating a 4-manifold edge (exactly like your original input). It then duplicates the verts in order to separate the objects and the one that's now separate is just a two-triangle manifold, so it's removed. Considering this library is about volume, that feels like good behavior. This thin manifolds thing still feel like a hack to me - can you work around it by cutting the lower surface quads on the opposite bisector?

[ramcdona]

I like this idea -- it is devious. It will take some work for me to implement, but I'll give it a try.

[ramcdona]

Unfortunately, this does not seem to have worked. On one example, it fixed the trailing edge, but made no change to the leading edge.

Here are some before and after intersections shown both wireframe and hidden line.

and after.

The thin surface does have a row of degenerate tris running around its boundary tying the 'top' and 'bottom' surfaces (for fun, I tried it without this row of degenerate tris -- same result).

[elalish]

Yeah, the same thing is happening, just after polygon triangulation now. Honestly, I bet a lot of other strange topological things could happen with these thin surfaces anyway, since it's completely marginal whether they self-intersect or not, so you're basically flipping a coin if you have any rounding errors. I think you may just be looking for a non-manifold library.

[ramcdona]

You aren't going to get rid of me that easily (:

I still have the fallback of being able to add a finite thickness to these surfaces to 'puff' them up. I've tried this and it seems to work well. It leaves a thin hole that I will have to seal up at the intersection when I throw away the bottom surface. I'll also have to wrestle with how much to puff the geometry up, but these are challenges that can be overcome.

However, even the truly thin surface doesn't appear to guarantee the same topology on the top/bottom surfaces -- so I have to seal up a topological hole either way. By using the true zero thickness surface, I'm just trying to avoid the geometric hole.

I still think it would be good to have some user controllable way of disabling certain cleanup passes. No matter what, I'm going to have to do my own cleanup passes later, so I'm not really worried about you leaving me with some ugly triangles.

In this particular code path, I go through and remove diagonals in order to recover the original quads. My data structure can handle arbitrary sided polygons, so I end up merging tris into polygons and then doing an almost co-linear pass to eliminate redundant vertices along the boundaries.

I've been down the road with other libraries. If there where a bunch of good choices out there, you wouldn't have created this library. We also have our home-grown library that we've been developing for 20 years -- but given the choice of making it truly robust or trying to incorporate someone else's library -- well, here I am.

[elalish]

I appreciate your candor 😄. Okay, technically SimplifyTopology should be just an optimization/nicety. Well, technically we do have to do the even-manifold edge fixes, though those are quite rare anyway. I suppose we could add something to our global ExecutionParameters to disable the rest of the simplification. That would be very simple at least, and honestly it may be useful for debug as well. Be warned - you will get a lot of degenerate triangles.

[ramcdona]

Thanks, I'll poke around a bit and see what I can find.

[ramcdona]

Ok, I've made a crude cut at making the steps in SimplifyTopology() optional. This is posted as PR 603.

In my particular example, changing either collapseShortEdges or swapEdges to false seems to improve the test case I'm looking at (I need to consider a lot more test cases, but it is a start).

If you were to disable one or the other of these two steps (but not both), which would you prefer to skip?

[elalish]

I would skip everything after DedupeEdges - any of the remaining steps could delete faces (it happens in CollapseEdge), though it may be hard to generate the examples that cause it.

[elalish]

I believe this was fixed by #603