manifold projection may produce bad geometry

[ali1234]

Describe the bug projection() takes a very long time on certain STL files generated by OpenSCAD. The example here takes over a minute to preview with manifold. The file where I originally found this bug takes at least an hour and possibly a lot longer - I never waited for it to finish.

To Reproduce Steps to reproduce the behavior:

1. Open shape.scad and export as STL (ascii).
2. Open proj.scad.

Expected behavior The preview should not take forever.

Code reproducing the issue

File: shape.scad

$fa = 1;
$fs = 0.1;

rotate([0, -90, 90])
rotate([-2, 0, 0])
linear_extrude(height=2.5)
offset(2) offset(4) {
    offset(6) offset(-6) square([54, 39], center=true);
    square([23, 53], center=true);
}

File: proj.scad

projection() import("shape.stl");

Environment and Version info (please complete the following information): Xubuntu 24.10, Nightly 2.19 (appimage)

Additional context It happens with both manifold and cgal. If you remove the outermost rotation from shape.scad and instead apply it in proj.scad (between import and projection), the problem still happens. If you make pretty much any other change to shape.scad, the preview completes in a fraction of a second with manifold, about 1 second with cgal. ~~If you apply the projection directly in shape.scad, the problem does not happen - with or without wrapping the shape in render()~~ - actually it seems like sometimes it does? Applying even a tiny bit of extra rotation also makes the problem go away.

[jordanbrown0]

The import seems unnecessary; wrapping projection() around the original object (around the outer rotate()) yields the pathological case.

I see the problem only with Manifold, not with CGAL. (Don't forget to flush caches when switching.)

This is with 2024.12.26 on Windows.

Perhaps the stacked offsets are generating a huge number of tiny segments.

[jordanbrown0]

It did finally complete, after ~7m.

When I unioned the base object (without the projection()) with a cube(), CGAL said:

WARNING: Object may not be a valid 2-manifold and may need repair!

It had ~6000 facets and ~4000 vertexes.

Preview with Show Edges shows a lot of very small triangles:

The lighter areas are densely packed very narrow triangles.

Zooming in on the top right corner...

[jordanbrown0]

And those thicker diagonal lines are themselves very narrow triangles:

[pca006132]

Ah, this is triggering the slow case for triangulation in manifold.

[pca006132]

For some reason it treats the polygon as something with many holes, and the keyhole function is taking a long time.

65794 outlines...

[pca006132]

It feels to me that this is caused by manifold's project function somehow not returning the correct output. Maybe the triangles are too small? I don't have much idea about this.

[pca006132]

I think there are two problems here:

1. Manifold projection may produce bad geometry. For openscad, the simplest way to fix this might be to use the other backend to do the projection until this is fixed upstream.
2. Manifold triangulation is slow when you have thousands of holes in the polygon... This is probably not that important but still something the upstream should probably look into later.

[elalish]

Hmm, Manifold's Project() method doesn't do any triangulation. It only returns the polygons, which it says should be run through a positive rill rule pass as they are likely to contain lots of self-intersections. Is it possible that step is being skipped in OpenSCAD?

Or more likely (since the result is lots of holes), is it using the even-odd fill rule instead? I've noticed from some of the test cases in OpenSCAD that it seems to like defaulting to even-odd instead of positive, for reasons I cannot comprehend. Even-odd fill rule will give pathological results in pretty much all cases.

[pca006132]

OpenSCAD does pass the polygons to CrossSection with the positive fill rule (default), but it doesn't perform simplification on it. I tried simplification, it helps in some cases, but for the complex case here it ~~doesn't work~~ is not enough

[elalish]

Yeah, given the crazy amount of degenerate geometry in this object, I'd say this is fairly expected behavior, but we should look and see if the simplification pass can be improved. Perhaps this shape has accrued more rounding error than it's reporting.

Hmm, is OpenSCAD using manifold's exact rotation transformations? This shape looks like it should have a lot of exactly vertical triangles, which should give face normals with exactly 0 zero Z components. Any floating point error in those Z values will cause this ugliness, but Manifold's transforms are designed to be exact for 90-degree rotations for exactly this reason. Is OpenSCAD introducing any rounding error, or is Manifold's face normal calculation unstable?

[pca006132]

The mesh is rotated by 2 degrees, so we cannot use the exact transform.

[ali1234]

Yes, that 2 degree rotation was a necessary part of the original thing I was making. It is basically flat with a sloped top. I removed all the unnecessary parts and just the sloped part was left. I can show the original if you want - it takes an unknown amount of time to process, and I also saw occasional segfaults but I couldn't reproduce those easily.

[elalish]

Well, the 2 degrees is around the Z-axis, then 90's around the Y and then Z again. That should leave the original top and bottom surfaces of the extrusion exactly vertical, right? I'm curious if that's precisely true.

[pca006132]

I looked at the code, openscad is maintaining its own transform matrix, so it is not using manifold's rotation function.

[elalish]

If you export that horrible polygon, but then do the rest of the operations in Manifold directly, does it still have the problem? If not, we'll know the transforms are the problem. I'm sure OpenSCAD could benefit from making them exact if they aren't now.

[nophead]

I think OpenSCAD has had exact transforms for 90 degrees for a long time.

[elalish]

I just converted this example into a pure ManifoldCAD.org version: https://tinyurl.com/79weamet

It's working no problem in 0.03 seconds. If anyone can manipulate my example into something that shows the slowness, I'll be happy to investigate. However, I believe the problem is rounding error introduced in steps outside of the Manifold library.

[pca006132]

I tried CGAL with the exported mesh from manifold, i.e.

openscad shape.scad --backend=manifold -o shape.stl
openscad proj.scad -o test.png

The second command still takes very long. I don't think this is a manifold issue. If we remove the backend selection for the first command, it generates the following mesh that is considerably simpler because it does not have to use triangles:

At least I don't think this is an issue with projection.

[pca006132]

ah, the stl is still in triangles, but I guess cgal does a better job in triangulation.

[pca006132]

@elalish I think this is probably related to our triangulator. We should get something close to a Delaunay triangulation like CGAL does, but we got

[pca006132]

or maybe this is an artifact from ear-clipping? The outer triangles in the CGAL triangulation are mostly degenerates...

[elalish]

was there intended to be an image included above? I'm not quite following the logic here. How is this triangulation related? I thought the problem was all with vertical faces getting projected down to a line, and floating-point issues creating lots of cruft that's slow to sort through.

[pca006132]

CGAL's triangulation:

Our triangulation:

It is not related to our projection code. If we export the mesh produced by manifold (with the triangulation in the second image), import it, and do a project with manifold disabled, there is the same issue. Instead, if we export the first one, import it, and do a project with manifold disabled, it works fine. (probably because most triangles are simplified to nothing by clipper).

[kintel]

The initial example seems to work well with Manifold as of v3.2.1 - can we close this as fixed, or are there other corner cases which should be highlighted in this issue?

[elalish]

Glad to hear it - if anyone finds a corner case with a Manifold-only repro, please file it upstream and we'll take a look.

[kintel]

Closing as fixed by Manifold v3.2.1