Move manifold out of experimental

[kintel]

This is a meta issue collecting everything needed or wanted to be able to move Manifold out of experimental and make it the default/preferred/only geometry backend in OpenSCAD.
We may want to ship with Manifold before all of these issues are addressed, in which case we should split out the unsolved topics into separate issues.

• Make CGAL optional (undefine ENABLE_CGAL), with severe loss of functionality, as a way of identifying all CGAL code paths: Allow building without CGAL #4840
• Diagnose and fix convexity issue (Manifold doesn't support Minkowskis convexity #4934)
• Some manifold objects fail to import into Manifold (Some Manifold objects fail to import into Manifold #5022)
• Support wireframe rendering of Manifold geometries
• We use the following pattern a lot, can we make that more elegant?

  if (const auto geomlist = dynamic_pointer_cast<const GeometryList>(geom)) { ... }
#ifdef ENABLE_CGAL
  else if (const auto N = dynamic_pointer_cast<const CGAL_Nef_polyhedron>(geom)) { ... }
  else if (const auto hybrid = dynamic_pointer_cast<const CGALHybridPolyhedron>(geom)) { ... }
#endif
#ifdef ENABLE_MANIFOLD
  else if (const auto mani = dynamic_pointer_cast<const ManifoldGeometry>(geom)) { ... }
#endif
  else if (const auto ps = dynamic_pointer_cast<const PolySet>(geom)) { ... }
  else if (dynamic_pointer_cast<const Polygon2d>(geom)) { ... }
  else { assert(false && "Not implemented"); }

• Go through all code using CGAL and identify why it needs CGAL
• Go through all cases where using PolySetBuilder may yield a non-manifold geometry
  • linear_extrude (Bypass PolySetBuilder for rotate- and linear extrude #5046)
  • rotate_extrude (Bypass PolySetBuilder for rotate- and linear extrude #5046)
  • 3MF import
  • TODO: Others?
• Go through all code using CGAL and update as much of it as possible to use an alternative in no-CGAL mode
  • minkowski():
    • Concave objects: Needs convex decomposition
    • Convex objects: is_convex() requires CGAL
  • hull(): 3D hull requires CGAL
  • roof(): Needs straight skeleton
  • projection(cut=true): Use Manifold's Slice() feature: Use Manifold's Slice() and Project() to implement projection() #5076
  • Polygon2D triangulation: Needs CGAL's constrained delaunay triangulator. Could be solved as part of Bypass PolySetBuilder for rotate- and linear extrude #5046
  • --render=cgal: Forces usage of Nef3 polyhedrons: Rename --render=cgal to --render=force to force-convert to the current backend-specific geometry #4822
  • AMF export: Converts to Nef3 polyhedrons before exporting
  • NEF3 and NEFDBG export requires Nef3 polyhedrons
  • NEF3 import requires Nef3 polyhedrons
  • AMF import: Performs a CGAL union if multiple objects
  • OFF import: File I/O is implemented by CGAL (Rewrite OFF import #4960)
  • 3MF import: Performs CGAL union of imported objects
  • MainWindow::canExport(): Manifold check only implemented in CGAL
  • ManifoldUtils::createMutableManifoldFromPolySet(): Requires CGAL for is_convex and hull
  • GUI check validity converts to Nef yielding bad results in some cases.
• Establish a better caching strategy for partial Manifold results. To meaningfully insert Manifold objects into the cache, we need some sort of resoruce limit, and manifold currently doesn't give us much insight into memory usage. We may want to avoid caching Manifold nodes if feasible, and rather cache PolySets instead.
• Look through the 2D backend to make sure it's well understood how it interacts with Manifold
• Consider moving all our Clipper V1 code to Clipper V2 and use the same Clipper build as Manifold -> Update to Clipper2 #4974
• Look into our libtess usage and see if it's possible to use the same tessellator as Manifold
• Find a way of running a larger scale test of OpenSCAD with CGAL vs. Manifold backends to attempt to exercise more cases than the test framework currently does (e.g. download some SCAD collections and run against both backends)
• Consider making the CGAL and Manifold backends co-exist and add UI + cmd-line features to choose which one to prefer
• If feasible, look into whether CGALRenderer could be split into separate components for Nef polyhedrons, fast-csg and manifold
• If feasible, look into whether CGALRenderer could highlight negative regions in a similar way as for Nef polyhedrons, as demoed on https://manifoldcad.org
• If feasible, look into whether GeometryEvaluator could be split into separate components for Nef polyhedrons, fast-csg and manifold
• Color scheme changes after rendering doesn't work for ManifoldGeometry or PolySets, only for Nef Polyhedrons: Bugfix: Color scheme changes didn't affect rendered polysets #5077
• Make sure Manifold failures and exceptions don't crash the OpenSCAD process: catch and report (manifold) #4824

[pca006132]

I think one important missing feature would be minkowski sum. We are not very interested in implementing the convex decomposition algorithm required because we think there are better algorithms for 3D offsetting, but we do accept PRs if anyone is willing to do it.

[kintel]

Good point about minkowski. A very common use-case for minkowski is indeed 3d offset, but there may be other use-cases for which 3d offset wouldn't suffice. We're kind of committed to supporting minkowski forever, but we could use Manifold for the resulting large union of convex objects (unless we already do that, and the CGAL API gives us easy access to those objects). We also have a special-case already which optimizes the case for which all minkowski operands are convex.

[kintel]

Updated text to mention minkowski

[pca006132]

I think the current minkowski already uses manifold if possible: https://github.com/openscad/openscad/blob/master/src/geometry/manifold/manifold-applyops-minkowski.cc#L196

[ochafik]

I think the current minkowski already uses manifold if possible: https://github.com/openscad/openscad/blob/master/src/geometry/manifold/manifold-applyops-minkowski.cc#L196

Yes it does, and hopefully soon it will also use Manifold's Hull (incubating this here BTW)

The convex decomposition is a tough one. And currently if it fails we also use CGAL's Nef minkowski as a fallback, even when Manifold backend is enabled.

TBH I wouldn't necessarily make it a strict goal to wean ourselves off of CGAL. We could just progressively restrict its use to what it's still the best at (e.g. use it to repair meshes or for minkowski), and ensure it progressively becomes the exception rather than the rule.

@kintel To answer your open question from #4646 (comment), I think it might soon be time to promote Manifold to the default (if only, to increase the amount of feedback / bug reports from users), and decide what should be the fallback behaviour: we could have a no-manifold experimental feature that uses fast-csg or Nef, depending which one we think is most preferable / backwards compatible (as a first step we could keep both of course). Maybe the fallback could be a non-experimental flag, so we could ship a release with the two backends if we really fear regressions. In all cases some Nef will remain necessary for minkowski for a while, so if binary size is a factor we could just save a lot by having just Manifold + Nef (+ some bits of surface mesh for repair purposes).

Also, not sure if we also need some OpenGL work to make Manifold (or fast-csg) a 1st class citizen, I remember cutting some corners / converting to PolySet or CGAL_Polyhedron a bit aggressively there.

[kintel]

For the record, I agree that completely weaning off CGAL isn't an explicit goal, but being able to isolate it could be a way of improving code health. Both your suggestions are already in my list above. Feel free to edit/reword/split into separate issues once you think anything is well-defined enough to explore as separate efforts.

The rendering pieces may benefit from waiting for #4782

[pca006132]

Btw there are some weird issues regarding geometry cache, #4732 and #4753.

[kintel]

We have similar geometry cache issues for CGAL. I believe the issue is that we can cache geometry as Nef polyhedrons or PolySets, but since PolySets are lossy, correctness of the final result may depend on avoiding cached PolySets. ..and sometimes, doing preview before render primes the cache with non-Nef3 data, or smth.
I don't think we have a cache for Manifold objects, so we convert to/from PolySet for caching purposes, which may also be lossy. I haven't read the Manifold-related code in detail.

[pca006132]

Thinking about it, we will get self-intersecting polygons when we try to get the projection of a mesh that is not a valid mesh but only ε-valid (e.g. the touching cubes example), or attempt to slice the mesh. Not sure if clipper works fine with self-intersecting inputs.

[nophead]

Clipper can fix self intersections if you offset by a minute amount. I have never tried 0, so I don't know if that works. It depends if it gets ignored completely or is still passed through clipper.

[pca006132]

The problem is that if manifoldness (each point is connected to 2 other points) is maintained and we keep the exact coordinates, the polygon will be self-intersecting. Just consider the case in which two triangles share a vertex, it is considered self-intesecting in the shared vertex if you duplicate it, so offset by 0 cannot possibly fix the issue. Maybe should check clipper(2) to make sure it is supported.

Btw I think this will also happen when you use CGAL's Nef Polyhedron, it is a general issue.

[elalish]

I wrote a straight skeleton algorithm years ago that I've been meaning to put into C++ for Manifold - that would give us roof().