NotManifold error in difference() example, but works in CGAL

[DougPollard]

Describe the bug
Under BOSL2, here is a simple difference() example that renders fine under CGAL but produces a NotManifold error under Manifold running recent dev snapshots (ie, 2024.05.10). The geometry from BOSL2 appears clean/fine.

Code reproducing the issue

include <BOSL2/std.scad>

function f(i) =
  let(a=65*sin(720*i),b=360*i-25*sin(1440*i))
  [cos(a)*sin(b),cos(a)*cos(b),sin(a)]
;
  
steps = 120;
radius = 20;
face = [ [-1,-0.2],[-1,0.2],[1,0.2],[1,-0.2] ];
path = [ for (i=[0:steps-1]) radius*f(i/steps) ];
normals = [ for (i=[0:steps-1]) f(i/steps) ];
  
difference() {
  sphere(r=radius,$fn=360);
  vnf_polyhedron(path_sweep(face,path,normal=normals,method="manual",closed=true));
}

Environment and Version info (please complete the following information):

• OS: macOS 14
• System: M1 Max
• dev build 2024.05.10

[kintel]

Does it say WARNING: PolySet -> Manifold conversion failed: NotManifold Trying to repair and reconstruct mesh.. ?

Note that this is not an error, it's a warning, and if it ends up continuing without error, the repair succeeded.

Nevertheless, it's worth looking into.

[kintel]

This is a minimal polyhedron output by BOSL2 by a modification of your example with steps=3.
It shows that BOSL repeats the outline vertices of the first segment. This causes the model to not be a manifold topology, but we managed to repair it by merging the coincident vertices.

Ideally, I think BOSL2 should reuse the initial vertices rather than duplicating them.

polyhedron(points = [
  [2.02196e-17, 19.8, 1],
  [-2.02196e-17, 20.2, 1],
  [-2.02196e-17, 20.2, -1],
  [2.02196e-17, 19.8, -1],
  [10.8034, -1.52112, 1],
  [11.16, -1.70232, 1],
  [11.16, -1.70232, -1],
  [10.8034, -1.52112, -1],
  [-10.8034, -1.52112, 1],
  [-11.16, -1.70232, 1],
  [-11.16, -1.70232, -1],
  [-10.8034, -1.52112, -1],
  [2.02196e-17, 19.8, 1],
  [-2.02196e-17, 20.2, 1],
  [-2.02196e-17, 20.2, -1],
  [2.02196e-17, 19.8, -1]
],
  faces = [[0, 5, 4],
  [0, 1, 5],
  [1, 2, 5],
  [5, 2, 6],
  [2, 3, 6],
  [6, 3, 7],
  [3, 0, 7],
  [7, 0, 4],
  [4, 5, 8],
  [8, 5, 9],
  [5, 6, 9],
  [9, 6, 10],
  [6, 7, 10],
  [10, 7, 11],
  [7, 4, 11],
  [11, 4, 8],
  [8, 9, 12],
  [12, 9, 13],
  [9, 10, 13],
  [13, 10, 14],
  [10, 15, 14],
  [10, 11, 15],
  [11, 8, 15],
  [15, 8, 12]
],
  convexity = 2);

[DougPollard]

Does it say WARNING: PolySet -> Manifold conversion failed: NotManifold Trying to repair and reconstruct mesh.. ?
Note that this is not an error, it's a warning, and if it ends up continuing without error, the repair succeeded.

You were exactly right, of course. I thought of it as an error, since rendering actually stopped. But your comment got me thinking... and I looked and found the option to stop on first warning. Duh! Sorry about that.

I was just talking with someone at BOSL about this. I'll pass on your observation unless you'd prefer to talk directly with them?

[kintel]

Please pass on my observations :)

FYI: What changed in OpenSCAD lately is that we moved away from using "polygon soups" as an internal format, and we now use indexed polygon meshes. Each topological vertex must be specified at one unique index. If you specify the same vertex position twice, it's treated as two separate vertices, and you must hence construct a mesh to account for that.

One side effect of doing it the new way is that you could move any vertex without affecting the manifoldness of the topology.

This is the same definition of manifoldness used by e.g. the Manifold library and 3MF: https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition

[DougPollard]

Thanks for taking the time to investigate this and to explain it. I started looking at the Manifold link you supplied. Very interesting! I can feel it pulling me to learn more.

[adrianVmariano]

This is a pretty big change and will break stuff all over BOSL2---probably most or all of the more complicated operations in BOSL2 that make closed polyhedra. We've always assumed that pieces of a polyhedron could be gathered together to make a new polyhedron without worrying about duplicate vertices along the joints. This makes it easy to construct a polyhedron's parts independently. Changing this without a huge slow down searching for duplicate vertices will be difficult or maybe in some cases impossible.

[adrianVmariano]

How are unreferenced vertices treated by Manifold? Are they OK like they were before, or not any more?

[kintel]

Note that this is just a warning.

If the input mesh is not explicitly connected, we'll try connecting it for you, which involves reindexing all vertices and trying to merge very close vertices. This comes at some processing cost, but more importantly, it may disallow certain manifold constructs (think two boxes sharing an edge, which was problematic in the past, but works well now).

In the old world, we silently attempted to connect unconnected meshes, which was mostly successful, modulo some corner cases. The warning was introduced to make it easier to detect when the good path was not chosen, as that's an indicator that something is suboptimal in your polyhedron description (or the internal code generating a PolySet).

Unreferenced vertices are fine - they're simply unreferenced and will be dropped at some convenient point in the processing pipeline.

Perhaps we should rewrite the warning into some more innocent-looking notice.

[kintel]

Just for the record: We have no intentions of breaking any existing use-cases, so if you find any actual breakages, please open an issue. It's very important that the vast majority of existing designs keep working in new versions of OpenSCAD.

[adrianVmariano]

Well, to say "just a warning" is a little bit misleading because "stop on first warning" is pretty much essential to avoid being overwhelmed by cascading messages resulting from warnings that really should have been errors. But from our side, ultimately it's not great library behavior to produce output that generates warnings for a wide range of cases, even if they don't prevent the model from being rendered.

[kintel]

ok, sounds like a strong signal for degrading that warning to something which is technically not a warning.

[DougPollard]

What about a parameter/option on polyhedron() that basically indicates if duplicate vertices are expected or not? Default could be false, but BOSL2 could create their polyhedron with the option true. False behaves as now -- it generates a warning or whatever is appropriate, but true, from BOSL, means don't bother the user (at all). This would give BOSL the chance, if it even makes sense, to generate some cases that might be known to be "clean" and default to the rest of the cases using the current code and specify the option as appropriate. Again, I have no idea if that last part even makes sense in the BOSL code base.

[adrianVmariano]

There are definitely cases where the existing use of polyhedron doesn't use duplicate vertices, and there might be cases where it does but might not be particularly difficult to fix that could make use a "duplicate_vertices=true/false" option. We do have code for removing duplicate vertices---it's been a while since I worked on that code so I don't recall precisely how slow it is. I know we tried to beat O(N^2) with a tree algorithm, but I'm not sure how effective that is in the end.

[kintel]

Opened a feature request in #5135

[kintel]

Closing this as works-as-intended - let's continue any discussion in #5135