Corrupted union of seemingly simple large models

[ochafik]

Manifold seems to explode with large inputs that seem valid.

$fn=1500;
sphere(100);
translate([50, 0, 0]) sphere(100);

Here's a repro case:

echo 'sphere(100, $fn=1500);' | openscad - -o a.stl --export-format=binstl
echo 'translate([50, 0, 0]) sphere(100, $fn=1500);' | openscad - -o b.stl --export-format=binstl

// cmake -DCMAKE_BUILD_TYPE=Release -DMANIFOLD_PAR=NONE -DMANIFOLD_EXPORT=1 ..
#include "manifold.h"
#include "meshIO.h"

using namespace manifold;

int main(int argc, char **argv) {
  auto forceCleanup = false; // true gives same output
  Manifold a = Manifold(ImportMesh("a.stl", forceCleanup));
  Manifold b = Manifold(ImportMesh("b.stl", forceCleanup));
  ExportMesh("out.stl", (a + b).GetMesh(), {});
}

For bonus points, pushing to '$fn=2000' the above example gives:

[pca006132]

Sounds like integer overflow somewhere in the code. Maybe we can use address sanitizer for debugging.

[ochafik]

Note that the spheres w/ $fn=2000 have ~4M vertices each

[elalish]

Interesting. I tried it in manifoldCAD.org (our sphere is a bit different than OpenSCAD's, but same idea):

const ball = sphere(100, 1600);
const result = ball.add(ball.translate([50,0,0]));

This works fine in 3 seconds, but at 1700 it throws an out of memory error (WASM). I haven't managed to repro the broken geometry yet though.

[kintel]

Perhaps we should build a manifoldCAD exporter from OpenSCAD, to make it easier to report issues like this :) Shouldn't be too hard. Main job is to decide (or parametrize) which nodes makes it into our .csg export, then lower our internal representation to that subset of nodes (e.g. if we don't specify sphere as a valid node, we would yield a polyhedron instead). Converting from .csg to ManifoldCAD (or any other CSG data format) should be relatively easy after that.

[pca006132]

I tried debugging but still cannot figure out the reason for the bug. I managed to get a correct result with manifold sphere function, but get the same failure for OpenSCAD generated sphere stl. The vector size are relatively small comparing to INT_MAX, so overflow seems unlikely. Changing execution policy to sequential also doesn't help. However, I discovered another bug:

TEST(Boolean, LargeSpheres) {
  auto a = Manifold::Sphere(100, 2000);
  auto b = a + a.Translate({30, 0, 0});
  a.GetMesh();
}

When compiled with address sanitizer and using TBB as backend, it will complain that the sorting function performs illegal memory access in

manifold/src/utilities/include/sparse.h

Line 75 in 9a79516

unique<decltype(beginPQ())>(policy, beginPQ(), endPQ()) - beginPQ();

Forcing the policy to sequential fixes that, and it seems that there is no such bug report over for thrust (they do have a couple undefined behavior or problem handling collections of size larger than INT_MAX). I am starting to concern about the correctness of other thrust functions...

[ochafik]

@pca006132 TBC but the parallel failure could potentially be related to openscad/openscad#4564 (intermittent failure, which hasn't been confirmed whether it's happening in sequential mode yet). In any case you should probably open a different parallel-specific bug since this one isn't.

Also, if you open that other bug can you explain the steps you took to build w/ asan? I've never used it but I wonder if that specific failure you got could be a red herring (delayed failures often happen when non-guilty code accesses memory corrupted by another piece of code).

[pca006132]

@ochafik I opened #391. Yeah this may cause intermittent failure.

And thrust in general has quite a lot of UB if you enable UBSan, I think they already have a couple of bug reports about this and they seems not very concerned about it.

[pca006132]

Interestingly, I found that importing and exporting the a.stl model will produce something like this:

So perhaps we did something weird when importing the model.

[elalish]

@pca006132 Would you mind attaching this a.stl file? This looks like it could be a problem where Assimp is trying to merge the STL verts, but the verts are so close together that they're merging the wrong ones. @ochafik This is why I hate STL - can we repro this problem with a format that saves indexed geometry (basically anything but STL - 3MF might be ideal)? I want to ensure we at least have reproducible input.

[pca006132]

Ah github doesn't allow attaching stl/3mf files. But I used the exact same openscad command as above, i.e. echo 'sphere(100, $fn=1500);' | openscad - -o a.stl --export-format=binstl. I also tried 3mf and the output file is the same, so I don't think the issue is related to the file format.

[elalish]

Okay, I have the repro. I made a little utility to make these easier to debug. The problem is that the facets are close enough to coplanar across an edge that huge swaths are being marked as coplanar, and then getting collapsed. I kind of expected this might become a problem eventually, since coplanar regions are just connected components where neighbor-wise coplanarity is true. This means if you add enough neighbor differences together, you can end up with a very large difference from coplanarity overall.

Should be fixable, but I need to think about what the best approach is.

[pca006132]

Interesting. But does this also indicate that the collapse logic is buggy? It seems that the collapse logic somehow split the sphere into two. Also note that the sphere generated by calling Sphere directly from manifold is fine.

[elalish]

Believe it or not, that's working as intended. The decimator is capable of cutting objects apart and removing handles to simplify the topology. However, if it's collapsing edges that aren't really colinear, then obviously the result gets pretty hideous.

[t-paul]

The result certainly looks good, thanks!. I just hit an issue and it looks like this fixed the problem where the curved part of the 2 cutouts vanished.