Merge branch 'main' into perf/slicing-optimizations

Since main moved to Clipper2, parts of this branch no longer gave the same
G-code as main:

- bridge_over_infill dropped expand(limiting_area, 0.3 * flow.spacing()) as
  a no-op. The offset is below one unit, but Clipper2 still unites its
  result, which splits and merges touching polygons and so changes the
  anchor lines. Running it on the polygons next to the bridge gives main's
  anchors without the whole-layer pass.
- tsp_remove_crossings stopped at the first repeated ordering, where main
  runs on to its pn * pn cap. The loop is periodic from that point, so it
  now takes only the steps to the ordering main stops on.
- With a single tile, the tiled booleans now make the plain call instead of
  cutting the clip to the tile first.

The tiled boolean test compared rings exactly. With the safety offset a tile
unites only the clip polygons near it, and Clipper2 can then round a
crossing 1 unit differently, so that case allows 1 unit.

Comments that named ClipperLib now say Clipper, and
docs/HLSD/polygon-clipping.md describes the tiled booleans.

G-code of the five handy models in four configurations and of a baked
texture relief is byte-identical to main. Colour-painted models still
differ: segmenting each island on its own splits a colour's region into
different pieces than one diagram over the layer, which on one model also
changes the first layer's tool order.

docs/HLSD/polygon-clipping.md

@@ -62,6 +62,23 @@ Clipper2 behaves differently by default, the wrapper adjusts it.
   clip do not leave slivers.
 - Open polylines are clipped with the non-zero rule and keep their direction.
 
+### Tiled booleans
+
+The sweep slows down with the number of edges crossing a scan line, so a layer
+cut into thousands of pieces makes every whole-layer boolean expensive.
+`diff_ex_by_piece()` and `intersection_ex_by_piece()` take a subject of
+non-overlapping `ExPolygons`, group them into tiles with
+`ClipperUtils::tile_expolygons()`, and run each tile in parallel against only
+the clip polygons near it, cut to the tile's box. Below 128 pieces there is a
+single tile, and they are the plain `diff_ex()` / `intersection_ex()`.
+
+The result covers the same area as the plain call. Without the safety offset
+the rings are the same. With it, each tile unites only the clip polygons near
+it, so a clip edge that the whole-layer union splits where it crosses a distant
+clip polygon stays whole, and a crossing with the subject can round 1 unit
+differently. The tiles' results are concatenated in tile order, so the order of
+the output `ExPolygons` differs from the plain call.
+
 ### Offsets
 
 - Before offsetting, input vertices closer than

localization/i18n/list.txt

@@ -74,8 +74,11 @@ src/slic3r/GUI/Gizmos/GizmoObjectManipulation.cpp
 src/slic3r/GUI/Gizmos/GLGizmoCut.cpp
 src/slic3r/GUI/Gizmos/GLGizmoCut.hpp
 src/slic3r/GUI/Gizmos/GLGizmoSimplify.cpp
+src/slic3r/GUI/Gizmos/GLGizmoFaceDetector.cpp
 src/slic3r/GUI/Gizmos/GLGizmoSeam.cpp
 src/slic3r/GUI/Gizmos/GLGizmoSeam.hpp
+src/slic3r/GUI/Gizmos/GLGizmoText.cpp
+src/slic3r/GUI/Gizmos/GLGizmoText.hpp
 src/slic3r/GUI/Gizmos/GLGizmoEmboss.cpp
 src/slic3r/GUI/Gizmos/GLGizmoSVG.cpp
 src/slic3r/GUI/Gizmos/GLGizmoMeasure.cpp
@@ -255,6 +258,7 @@ src/slic3r/Utils/MKS.cpp
 src/slic3r/Utils/Moonraker.cpp
 src/slic3r/Utils/OctoPrint.cpp
 src/slic3r/Utils/Repetier.cpp
+src/slic3r/Utils/ProfileDescription.hpp
 src/slic3r/GUI/SendMultiMachinePage.cpp
 src/slic3r/GUI/MultiMachinePage.cpp
 src/slic3r/GUI/MultiMachineManagerPage.cpp

src/libslic3r/CSGMesh/VoxelizeCSGMesh.hpp

@@ -0,0 +1,116 @@
+#ifndef VOXELIZECSGMESH_HPP
+#define VOXELIZECSGMESH_HPP
+
+#include <functional>
+#include <stack>
+
+#include "CSGMesh.hpp"
+#include "libslic3r/OpenVDBUtils.hpp"
+#include "libslic3r/Execution/ExecutionTBB.hpp"
+
+namespace Slic3r { namespace csg {
+
+using VoxelizeParams = MeshToGridParams;
+
+// This method can be overriden when a specific CSGPart type supports caching
+// of the voxel grid
+template<class CSGPartT>
+VoxelGridPtr get_voxelgrid(const CSGPartT &csgpart, VoxelizeParams params)
+{
+    const indexed_triangle_set *its = csg::get_mesh(csgpart);
+    VoxelGridPtr ret;
+
+    params.trafo(params.trafo() * csg::get_transform(csgpart));
+
+    if (its)
+        ret = mesh_to_grid(*its, params);
+
+    return ret;
+}
+
+namespace detail {
+
+inline void perform_csg(CSGType op, VoxelGridPtr &dst, VoxelGridPtr &src)
+{
+    if (!dst || !src)
+        return;
+
+    switch (op) {
+    case CSGType::Union:
+        if (is_grid_empty(*dst) && !is_grid_empty(*src))
+            dst = clone(*src);
+        else
+            grid_union(*dst, *src);
+
+        break;
+    case CSGType::Difference:
+        grid_difference(*dst, *src);
+        break;
+    case CSGType::Intersection:
+        grid_intersection(*dst, *src);
+        break;
+    }
+}
+
+} // namespace detail
+
+template<class It>
+VoxelGridPtr voxelize_csgmesh(const Range<It>      &csgrange,
+                              const VoxelizeParams &params = {})
+{
+    using namespace detail;
+
+    VoxelGridPtr ret;
+
+    std::vector<VoxelGridPtr> grids (csgrange.size());
+
+    execution::for_each(ex_tbb, size_t(0), csgrange.size(), [&](size_t csgidx) {
+        if (params.statusfn() && params.statusfn()(-1))
+            return;
+
+        auto it = csgrange.begin();
+        std::advance(it, csgidx);
+        auto &csgpart = *it;
+        grids[csgidx] = get_voxelgrid(csgpart, params);
+    }, execution::max_concurrency(ex_tbb));
+
+    size_t csgidx = 0;
+    struct Frame { CSGType op = CSGType::Union; VoxelGridPtr grid; };
+    std::stack opstack{std::vector<Frame>{}};
+
+    opstack.push({CSGType::Union, mesh_to_grid({}, params)});
+
+    for (auto &csgpart : csgrange) {
+        if (params.statusfn() && params.statusfn()(-1))
+            break;
+
+        auto &partgrid = grids[csgidx++];
+
+        auto op = get_operation(csgpart);
+
+        if (get_stack_operation(csgpart) == CSGStackOp::Push) {
+            opstack.push({op, mesh_to_grid({}, params)});
+            op = CSGType::Union;
+        }
+
+        Frame *top = &opstack.top();
+
+        perform_csg(get_operation(csgpart), top->grid, partgrid);
+
+        if (get_stack_operation(csgpart) == CSGStackOp::Pop) {
+            VoxelGridPtr popgrid = std::move(top->grid);
+            auto popop = opstack.top().op;
+            opstack.pop();
+            VoxelGridPtr &grid = opstack.top().grid;
+            perform_csg(popop, grid, popgrid);
+        }
+    }
+
+    ret = std::move(opstack.top().grid);
+
+    return ret;
+}
+
+}} // namespace Slic3r::csg
+
+#endif // VOXELIZECSGMESH_HPP

src/libslic3r/ClipperUtils.cpp

@@ -9,6 +9,8 @@
 #include <numeric>
 #include <unordered_map>
 
+#include <tbb/parallel_for.h>
+
 #include "ClipperUtils.hpp"
 #include "BoundingBox.hpp"
 #include "ExPolygon.hpp"
@@ -800,6 +802,72 @@ Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r
     { return _clipper_ex(ctIntersection, ClipperUtils::SurfacesProvider(subject), ClipperUtils::SurfacesProvider(clip), do_safety_offset); }
 Slic3r::ExPolygons intersection_ex(const Slic3r::SurfacesPtr &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset)
     { return _clipper_ex(ctIntersection, ClipperUtils::SurfacesPtrProvider(subject), ClipperUtils::ExPolygonsProvider(clip), do_safety_offset); }
+
+namespace ClipperUtils {
+    std::vector<ExPolygonsTile> tile_expolygons(const ExPolygons &expolygons, size_t per_tile)
+    {
+        BoundingBox              extent;
+        std::vector<BoundingBox> bboxes;
+        bboxes.reserve(expolygons.size());
+        for (const ExPolygon &expoly : expolygons) {
+            bboxes.emplace_back(get_extents(expoly));
+            extent.merge(bboxes.back());
+        }
+        if (! extent.defined)
+            return {};
+        const int     tiles  = std::clamp(int(std::sqrt(double(expolygons.size()) / double(std::max<size_t>(per_tile, 1)))), 1, 32);
+        const Point   size   = extent.size();
+        const coord_t tile_w = std::max<coord_t>(1, size.x() / tiles + 1), tile_h = std::max<coord_t>(1, size.y() / tiles + 1);
+        std::vector<ExPolygonsTile> out(size_t(tiles * tiles));
+        for (size_t i = 0; i < expolygons.size(); ++ i) {
+            const Point c = bboxes[i].center();
+            ExPolygonsTile &tile = out[size_t(std::clamp(int((c.y() - extent.min.y()) / tile_h), 0, tiles - 1) * tiles +
+                                              std::clamp(int((c.x() - extent.min.x()) / tile_w), 0, tiles - 1))];
+            tile.members.emplace_back(i);
+            tile.bbox.merge(bboxes[i]);
+        }
+        out.erase(std::remove_if(out.begin(), out.end(), [](const ExPolygonsTile &tile) { return tile.members.empty(); }), out.end());
+        return out;
+    }
+}
+
+static Slic3r::ExPolygons clipper_ex_by_piece(ClipType clipType, const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+{
+    // A few dozen subject ExPolygons to a tile, each tile one Clipper call with the clip cut to the tile's box.
+    const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(subject, 32);
+    // One tile is the plain call: cutting the clip would only cost time.
+    if (tiles.size() <= 1)
+        return _clipper_ex(clipType, ClipperUtils::ExPolygonsProvider(subject), ClipperUtils::PolygonsProvider(clip), do_safety_offset);
+    std::vector<BoundingBox> clip_bboxes;
+    clip_bboxes.reserve(clip.size());
+    for (const Polygon &polygon : clip)
+        clip_bboxes.emplace_back(get_extents(polygon));
+
+    std::vector<Slic3r::ExPolygons> out_tiles(tiles.size());
+    tbb::parallel_for(size_t(0), tiles.size(), [&](size_t tile_idx) {
+        const ClipperUtils::ExPolygonsTile &tile = tiles[tile_idx];
+        Slic3r::ExPolygons local_subject;
+        local_subject.reserve(tile.members.size());
+        for (size_t i : tile.members)
+            local_subject.emplace_back(subject[i]);
+        // Grown so that the cut edges of the clip stay clear of the subject, also after the safety offset.
+        const BoundingBox bbox = tile.bbox.inflated(SCALED_EPSILON);
+        Polygons local_clip;
+        for (size_t i = 0; i < clip.size(); ++i)
+            if (clip_bboxes[i].overlap(bbox))
+                if (Polygon clipped = ClipperUtils::clip_clipper_polygon_with_subject_bbox(clip[i], bbox); ! clipped.empty())
+                    local_clip.emplace_back(std::move(clipped));
+        out_tiles[tile_idx] = _clipper_ex(clipType, ClipperUtils::ExPolygonsProvider(local_subject), ClipperUtils::PolygonsProvider(local_clip), do_safety_offset);
+    });
+    Slic3r::ExPolygons out;
+    for (Slic3r::ExPolygons &out_tile : out_tiles)
+        append(out, std::move(out_tile));
+    return out;
+}
+Slic3r::ExPolygons diff_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+    { return clipper_ex_by_piece(ctDifference, subject, clip, do_safety_offset); }
+Slic3r::ExPolygons intersection_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+    { return clipper_ex_by_piece(ctIntersection, subject, clip, do_safety_offset); }
 // May be used to "heal" unusual models (3DLabPrints etc.) by providing fill_type (pftEvenOdd, pftNonZero, pftPositive, pftNegative).
 Slic3r::ExPolygons union_ex(const Slic3r::Polygons &subject, PolyFillType fill_type)
     { return _clipper_ex(ctUnion, ClipperUtils::PolygonsProvider(subject), ClipperUtils::EmptyPathsProvider(), ApplySafetyOffset::No, fill_type); }

src/libslic3r/ClipperUtils.hpp

@@ -5,6 +5,7 @@
 #include "Polyline.hpp"
 #include "Line.hpp"
 #include "libslic3r.h"
+#include "BoundingBox.hpp"
 #include "ExPolygon.hpp"
 #include "Polygon.hpp"
 #include "Surface.hpp"
@@ -337,6 +338,15 @@ namespace ClipperUtils {
     [[nodiscard]] Polygons clip_clipper_polygons_with_subject_bbox(const ExPolygon &src, const BoundingBox &bbox, const bool get_entire_polygons = false);
     [[nodiscard]] Polygons clip_clipper_polygons_with_subject_bbox(const ExPolygons &src, const BoundingBox &bbox, const bool get_entire_polygons = false);
 
+    // Splits ExPolygons into tiles by the centres of their boxes, about `per_tile` of them to a tile, to run Clipper on a
+    // layer of many pieces tile by tile. Returns the non-empty tiles, each with the indices of its ExPolygons and their box.
+    struct ExPolygonsTile
+    {
+        BoundingBox         bbox;
+        std::vector<size_t> members;
+    };
+    [[nodiscard]] std::vector<ExPolygonsTile> tile_expolygons(const ExPolygons &expolygons, size_t per_tile);
+
     }
 
 // offset Polygons
@@ -532,6 +542,11 @@ Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r
 Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r::Surfaces &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::ExPolygons intersection_ex(const Slic3r::SurfacesPtr &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
+// diff_ex() / intersection_ex() of the subject split into tiles, each against only the part of the clip near it, the tiles in
+// parallel. The same area as the operation on the whole subject when its ExPolygons do not overlap, and much faster for a
+// subject of thousands of pieces spread over a layer: Clipper slows down with the number of edges crossing a scan line.
+Slic3r::ExPolygons diff_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
+Slic3r::ExPolygons intersection_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::Polygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polyline &subject, const Slic3r::ExPolygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::ExPolygon &clip);

src/libslic3r/Fill/Fill.cpp

@@ -22,6 +22,8 @@
 #include "../PrintConfig.hpp"
 #include "../Surface.hpp"
 
+#include <tbb/parallel_for.h>
+
 #include "AABBTreeLines.hpp"
 #include "libslic3r/Config.hpp"
 #include "libslic3r/ExPolygon.hpp"
@@ -652,24 +654,28 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
     if (!line_based_pattern) {
         const coord_t scaled_spacing = scaled<coord_t>(fill.params.spacing);
 
-        for (const ExPolygon &expolygon : fill.expolygons) {
+        // Each expolygon is split on its own, so they run in parallel and are collected in their original order.
+        std::vector<std::pair<ExPolygons, ExPolygons>> split_parts(fill.expolygons.size()); // normal, narrow
+        tbb::parallel_for(size_t(0), fill.expolygons.size(), [&](size_t idx) {
+            const ExPolygon &expolygon = fill.expolygons[idx];
             Polygons filled_area = to_polygons(expolygon);
 
             // "Core" area: open (erode+dilate) to drop thin features, then clamp back to the original polygon.
             Polygons inner_area  = intersection(filled_area, opening(filled_area, scaled_spacing, scaled_spacing));
 
             if (inner_area.empty()) {
-                narrow_infill.emplace_back(expolygon);
-                continue;
+                split_parts[idx].second.emplace_back(expolygon);
+                return;
             }
 
             ExPolygons inner_ex = union_ex(inner_area);
             ExPolygons expolys{expolygon};
-            ExPolygons narrow_ex = diff_ex(expolys, inner_ex);
-            ExPolygons normal_ex = intersection_ex(expolys, inner_ex);
-
-            append(normal_infill, normal_ex); // normal infill area
-            append(narrow_infill, narrow_ex); // narrow infill area
+            split_parts[idx].second = diff_ex(expolys, inner_ex);         // narrow infill area
+            split_parts[idx].first  = intersection_ex(expolys, inner_ex); // normal infill area
+        });
+        for (auto &[normal_ex, narrow_ex] : split_parts) {
+            append(normal_infill, std::move(normal_ex));
+            append(narrow_infill, std::move(narrow_ex));
         }
 
         return;
@@ -691,7 +697,10 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
     }
     const double aligning_angle = -base_angle + PI;
 
-	for (const ExPolygon &expolygon : fill.expolygons) {
+    // Each expolygon is reconstructed on its own, so they run in parallel and are collected in their original order.
+    std::vector<Polygons> split_reconstructed(fill.expolygons.size());
+    tbb::parallel_for(size_t(0), fill.expolygons.size(), [&](size_t expolygon_idx) {
+        const ExPolygon &expolygon = fill.expolygons[expolygon_idx];
         Polygons filled_area = to_polygons(expolygon);
         polygons_rotate(filled_area, aligning_angle);
         BoundingBox bb = get_extents(filled_area);
@@ -822,8 +831,10 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
             }
         }
 
-        polygons_append(normal_fill_areas, reconstructed_area);
-    }
+        split_reconstructed[expolygon_idx] = std::move(reconstructed_area);
+    });
+    for (Polygons &reconstructed_area : split_reconstructed)
+        polygons_append(normal_fill_areas, std::move(reconstructed_area));
 
     polygons_rotate(normal_fill_areas, -aligning_angle);
 
@@ -1431,7 +1442,15 @@ void Layer::make_fills(FillAdaptive::Octree* adaptive_fill_octree, FillAdaptive:
             // Orca: Reuse the body origin used for bridge anchoring, resetting it for each surface.
             f->set_bounding_box(infill_bounding_box(*this, surface_fill, expoly, bbox));
 
-            f->no_overlap_expolygons = intersection_ex(surface_fill.no_overlap_expolygons, ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
+            // Only the part of the layer-wide no-overlap area under this expolygon matters, so clip it to the
+            // expolygon's box first (padded past the safety offset, which grows the clip side). The result is
+            // identical; the cost is not: a layer split into many small fills, e.g. by colour painting,
+            // otherwise intersects every one of them with the whole layer.
+            BoundingBox no_overlap_bbox = get_extents(expoly);
+            no_overlap_bbox.offset(SCALED_EPSILON);
+            f->no_overlap_expolygons = intersection_ex(
+                ClipperUtils::clip_clipper_polygons_with_subject_bbox(surface_fill.no_overlap_expolygons, no_overlap_bbox),
+                ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
             if (params.symmetric_infill_y_axis) {
                 params.symmetric_y_axis = f->extended_object_bounding_box().center().x();
                 expoly.symmetric_y(params.symmetric_y_axis);

src/libslic3r/GCode/OrderingStrategies.cpp

@@ -139,15 +139,87 @@ bool tsp_remove_crossings(std::vector<size_t>& path, const Points& centers)
         return {std::numeric_limits<size_t>::max(), std::numeric_limits<size_t>::max()};
     };
 
+    // For many islands, the same scan with the edges binned in a uniform grid over their boxes, so each edge is only tested against the edges sharing a
+    // cell with it - two edges whose boxes overlap always do. It returns the same crossing as the all-pairs scan
+    // (smallest i, then smallest j), so the result is unchanged. The all-pairs scan is quadratic in the edge count and
+    // runs again after every reversal; rebuilding the grid costs more than it saves below the threshold.
+    constexpr size_t grid_min_size = 500;
+    BoundingBox extent;
+    for (size_t idx : path)
+        extent.merge(centers[idx]);
+    const int     grid_n = std::clamp(int(std::sqrt(double(pn))), 1, 256);
+    const coord_t cell_w = std::max<coord_t>(1, (extent.max.x() - extent.min.x()) / grid_n + 1);
+    const coord_t cell_h = std::max<coord_t>(1, (extent.max.y() - extent.min.y()) / grid_n + 1);
+    const auto    for_cells = [&](const Point& a, const Point& b, auto&& fn) {
+        const int x0 = int((std::min(a.x(), b.x()) - extent.min.x()) / cell_w), x1 = int((std::max(a.x(), b.x()) - extent.min.x()) / cell_w);
+        const int y0 = int((std::min(a.y(), b.y()) - extent.min.y()) / cell_h), y1 = int((std::max(a.y(), b.y()) - extent.min.y()) / cell_h);
+        for (int y = y0; y <= y1; ++y)
+            for (int x = x0; x <= x1; ++x)
+                fn(y * grid_n + x);
+    };
+    std::vector<std::vector<size_t>> edge_cells(size_t(grid_n) * grid_n);
+
+    auto find_crossing_grid = [&]() -> std::pair<size_t, size_t> {
+        for (std::vector<size_t>& cell : edge_cells)
+            cell.clear();
+        for (size_t j = 0; j < n_edges; ++j)
+            for_cells(centers[path[j]], centers[path[(j + 1) % pn]], [&](int cell) { edge_cells[cell].emplace_back(j); });
+
+        for (size_t i = 0; i < n_edges; ++i) {
+            const Point& ai = centers[path[i]];
+            const Point& bi = centers[path[(i + 1) % pn]];
+
+            size_t first_j = std::numeric_limits<size_t>::max();
+            for_cells(ai, bi, [&](int cell) {
+                for (size_t j : edge_cells[cell]) {
+                    if (j < i + 2 || j >= first_j) continue;
+                    // Skip the (0, pn-1) pair: edges (0,1) and (pn-1,0) share node 0.
+                    if (i == 0 && j == pn - 1) continue;
+
+                    const Point& aj = centers[path[j]];
+                    const Point& bj = centers[path[(j + 1) % pn]];
+
+                    if (!bboxes_overlap(ai, bi, aj, bj)) continue;
+                    if (Geometry::segments_intersect(ai, bi, aj, bj))
+                        first_j = j;
+                }
+            });
+            if (first_j != std::numeric_limits<size_t>::max())
+                return {i, first_j};
+        }
+        return {std::numeric_limits<size_t>::max(), std::numeric_limits<size_t>::max()};
+    };
+
     // Process crossings one at a time: find first, reverse it, restart scan.
     // Cap iterations to prevent infinite loops on collinear/overlapping segments.
-    int max_iters = static_cast<int>(pn * pn);
+    const int max_iters = static_cast<int>(pn * pn);
     bool improved = false;
-    while (max_iters-- > 0) {
-        auto [ci, cj] = find_crossing();
-        if (ci == std::numeric_limits<size_t>::max()) break;
-        improved = true;
+    // Reversing between two segments that only touch or overlap along a line need not remove the intersection, so on
+    // islands laid out on a regular grid (a tiled texture, an array of parts) the loop can cycle through the same
+    // orderings until the pn * pn cap. Once an ordering repeats the rest of the loop is periodic, so only the steps
+    // to the ordering the capped loop would have stopped on are taken.
+    std::unordered_map<uint64_t, int> seen_paths; // path hash -> reversals done when it was reached
+    const auto path_hash = [&path]() {
+        uint64_t h = 1469598103934665603ull; // FNV-1a
+        for (size_t idx : path)
+            h = (h ^ uint64_t(idx)) * 1099511628211ull;
+        return h;
+    };
+    const auto reverse_first_crossing = [&]() {
+        auto [ci, cj] = pn >= grid_min_size ? find_crossing_grid() : find_crossing();
+        if (ci == std::numeric_limits<size_t>::max())
+            return false;
         std::reverse(path.begin() + ci + 1, path.begin() + cj + 1);
+        return true;
+    };
+    seen_paths.emplace(path_hash(), 0);
+    for (int iter = 1; iter <= max_iters && reverse_first_crossing(); ++iter) {
+        improved = true;
+        if (auto [it, inserted] = seen_paths.emplace(path_hash(), iter); !inserted) {
+            for (int steps = (max_iters - iter) % (iter - it->second); steps > 0; --steps)
+                reverse_first_crossing();
+            break;
+        }
     }
     return improved;
 }

src/libslic3r/GCode/SeamPlacer.cpp

@@ -28,6 +28,7 @@
 #include <memory>
 #include <random>
 #include <algorithm>
+#include <limits>
 #include <queue>
 #include <string>
 #include <unordered_map>
@@ -1201,21 +1202,21 @@ std::optional<std::pair<size_t, size_t>> SeamPlacer::find_next_seam_in_layer(
     const size_t layer_idx, const float max_distance,
     const SeamPlacerImpl::SeamComparator &comparator) const {
   using namespace SeamPlacerImpl;
-  std::vector<size_t> nearby_points_indices = find_nearby_points(*layers[layer_idx].points_tree, projected_position,
-                                                                 max_distance);
-
-  if (nearby_points_indices.empty()) {
-    return {};
-  }
-
-  size_t best_nearby_point_index = nearby_points_indices[0];
-  size_t nearest_point_index = nearby_points_indices[0];
-
-  // Now find best nearby point, nearest point, and corresponding indices
-  for (const size_t &nearby_point_index : nearby_points_indices) {
+  // Find the best nearby point and the nearest one. A layer of a fine relief has tens of thousands of candidates within
+  // the radius, so they are looked at as the search finds them rather than collected into a vector first.
+  constexpr size_t none = std::numeric_limits<size_t>::max();
+  size_t best_nearby_point_index = none;
+  size_t nearest_point_index = none;
+  visit_nearby_points(*layers[layer_idx].points_tree, projected_position, max_distance,
+                      [&layers, &comparator, &projected_position, layer_idx, &best_nearby_point_index, &nearest_point_index]
+                      (size_t nearby_point_index) {
+    if (best_nearby_point_index == none) {
+      // The first point found starts both, as the first of the collected ones did.
+      best_nearby_point_index = nearest_point_index = nearby_point_index;
+    }
     const SeamCandidate &point = layers[layer_idx].points[nearby_point_index];
     if (point.perimeter.finalized) {
-      continue; // skip over finalized perimeters, try to find some that is not finalized
+      return; // skip over finalized perimeters, try to find some that is not finalized
     }
     if (comparator.is_first_better(point, layers[layer_idx].points[best_nearby_point_index],
                                    projected_position.head<2>())
@@ -1227,6 +1228,10 @@ std::optional<std::pair<size_t, size_t>> SeamPlacer::find_next_seam_in_layer(
         || layers[layer_idx].points[nearest_point_index].perimeter.finalized) {
       nearest_point_index = nearby_point_index;
     }
+  });
+
+  if (best_nearby_point_index == none) {
+    return {};
   }
 
   const SeamCandidate &best_nearby_point = layers[layer_idx].points[best_nearby_point_index];

src/libslic3r/KDTreeIndirect.hpp

@@ -318,6 +318,36 @@ std::vector<size_t> find_nearby_points(const KDTreeIndirectType &kdtree, const P
     return visitor.result;
 }
 
+// Visits the points within max_distance of center, in the order find_nearby_points() would collect them, and hands
+// each of them to `visitor_fn` instead of returning them all: a search over a dense set spends more on collecting the
+// points into a vector than on the search itself, and its caller usually keeps only a few of them.
+template<typename KDTreeIndirectType, typename PointType, typename VisitorFn>
+void visit_nearby_points(const KDTreeIndirectType &kdtree, const PointType &center,
+                         const typename KDTreeIndirectType::CoordType &max_distance, VisitorFn visitor_fn)
+{
+    using CoordType = typename KDTreeIndirectType::CoordType;
+
+    struct Visitor {
+        const KDTreeIndirectType &kdtree;
+        const PointType           center;
+        const CoordType           max_distance_squared;
+        VisitorFn                 visitor_fn;
+
+        unsigned int operator()(size_t idx, size_t dimension) {
+            auto dist = CoordType(0);
+            for (size_t i = 0; i < KDTreeIndirectType::NumDimensions; ++i) {
+                CoordType d = center[i] - kdtree.coordinate(idx, i);
+                dist += d * d;
+            }
+            if (dist < max_distance_squared)
+                visitor_fn(idx);
+            return kdtree.descent_mask(center[dimension], max_distance_squared, idx, dimension);
+        }
+    } visitor { kdtree, center, max_distance * max_distance, visitor_fn };
+
+    kdtree.visit(visitor);
+}
+
 template<typename KDTreeIndirectType, typename PointType>
 std::vector<size_t> find_nearby_points(const KDTreeIndirectType &kdtree, const PointType &center,
                                        const typename KDTreeIndirectType::CoordType& max_distance)

src/libslic3r/LayerRegion.cpp

@@ -96,10 +96,11 @@ void LayerRegion::slices_to_fill_surfaces_clipped()
         by_surface[size_t(surface.surface_type)].emplace_back(&surface);
     // Trim surfaces by the fill_boundaries.
     this->fill_surfaces.surfaces.clear();
+    const Polygons fill_boundaries = to_polygons(this->fill_expolygons);
     for (size_t surface_type = 0; surface_type < size_t(stCount); ++ surface_type) {
         const SurfacesPtr &this_surfaces = by_surface[surface_type];
         if (! this_surfaces.empty())
-            this->fill_surfaces.append(intersection_ex(this_surfaces, this->fill_expolygons), SurfaceType(surface_type));
+            this->fill_surfaces.append(intersection_ex_by_piece(to_expolygons(this_surfaces), fill_boundaries), SurfaceType(surface_type));
     }
 }
 

src/libslic3r/MultiMaterialSegmentation.cpp

@@ -24,6 +24,7 @@
 #include "format.hpp"
 #include "libslic3r.h"
 
+#include <numeric>
 #include <cmath>
 #include <cstddef>
 #include <list>
@@ -1353,10 +1354,15 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
     }
 #endif // MM_SEGMENTATION_DEBUG_TOP_BOTTOM
 
-    // When the upper surface of an object is occluded, it should no longer be considered the upper surface
+    // When the upper surface of an object is occluded, it should no longer be considered the upper surface.
+    // Every (colour, layer) pair is trimmed on its own, so they all run at once: the painted faces of a finely
+    // textured part project hundreds of thousands of triangles onto one layer, which used to be trimmed serially.
     {
-        for (size_t extruder_idx = 0; extruder_idx < num_facets_states; ++extruder_idx) {
-            for (size_t layer_idx = 0; layer_idx < layers.size(); ++layer_idx) {
+        const size_t occluded_pairs = num_facets_states * layers.size();
+        tbb::parallel_for(tbb::blocked_range<size_t>(0, occluded_pairs), [&](const tbb::blocked_range<size_t> &range) {
+            for (size_t pair_idx = range.begin(); pair_idx < range.end(); ++pair_idx) {
+                const size_t extruder_idx = pair_idx / layers.size();
+                const size_t layer_idx    = pair_idx % layers.size();
                 if (!top_raw[extruder_idx].empty() && !top_raw[extruder_idx][layer_idx].empty() && layer_idx + 1 < layers.size()) {
                     top_raw[extruder_idx][layer_idx] = diff(top_raw[extruder_idx][layer_idx], input_expolygons[layer_idx + 1]);
                 }
@@ -1364,7 +1370,7 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                     bottom_raw[extruder_idx][layer_idx] = diff(bottom_raw[extruder_idx][layer_idx], input_expolygons[layer_idx - 1]);
                 }
             }
-        }
+        });
     }
 
     std::vector<std::vector<ExPolygons>> triangles_by_color_bottom(num_facets_states);
@@ -1422,11 +1428,58 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
         return out;
     };
 
+    // Projects a painted top or bottom face `ex` of layer `layer_idx` onto the shell layers below or above it (in
+    // `shell_layers`, nearest first), one more perimeter in on each, stopping at the first layer where nothing is left.
+    // Only the slices within the deepest offset of `ex` (three times that with the miter joins) decide the result, so the
+    // work is done per tile of `ex`'s ExPolygons on the slices cut to the tile's box grown by that much: the same result, but
+    // each Clipper call stays the size of a tile rather than of a layer cut through a fine relief, and the tiles run in
+    // parallel.
+    const auto project_to_shells = [&input_expolygons](const ExPolygons &ex, size_t layer_idx, const std::vector<size_t> &shell_layers,
+                                                       const LayerColorStat &stat, ShellProjections &dst) {
+        std::vector<float> offsets(shell_layers.size());
+        float              offset = 0.f;
+        for (size_t i = 0; i < shell_layers.size(); ++i) {
+            //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+            offset -= (stat.extrusion_spacing + stat.extrusion_width);
+            offsets[i] = offset;
+        }
+        if (offsets.empty())
+            return;
+        const coord_t reach = coord_t(std::ceil(DefaultMiterLimit * std::abs(offsets.back()))) + 10 * SCALED_EPSILON;
+        const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(ex, 16);
+        // [shell layer][tile]
+        std::vector<std::vector<ExPolygons>> shells(shell_layers.size(), std::vector<ExPolygons>(tiles.size()));
+        tbb::parallel_for(size_t(0), tiles.size(), [&](size_t tile_idx) {
+            const ClipperUtils::ExPolygonsTile &tile = tiles[tile_idx];
+            const BoundingBox                   bbox = tile.bbox.inflated(reach);
+            ExPolygons                          tile_ex;
+            tile_ex.reserve(tile.members.size());
+            for (size_t i : tile.members)
+                tile_ex.emplace_back(ex[i]);
+            Polygons layer_slices_trimmed = ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[layer_idx], bbox);
+            for (size_t i = 0; i < shell_layers.size() && ! layer_slices_trimmed.empty(); ++i) {
+                const ExPolygons trimmed = intersection_ex(layer_slices_trimmed, ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[shell_layers[i]], bbox));
+                shells[i][tile_idx]  = opening_ex(intersection_ex(tile_ex, offset_ex(trimmed, offsets[i])), stat.small_region_threshold);
+                layer_slices_trimmed = to_polygons(trimmed);
+            }
+        });
+        for (size_t i = 0; i < shell_layers.size(); ++i) {
+            ExPolygons shell;
+            for (ExPolygons &tile_shell : shells[i])
+                append(shell, std::move(tile_shell));
+            if (shell.empty())
+                break;
+            dst.emplace_back(shell_layers[i], std::move(shell));
+        }
+    };
+
     tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&num_layers, &num_facets_states, &layer_color_stat, &top_raw, &triangles_by_color_top,
-                                                                  &throw_on_cancel_callback, &input_expolygons, &bottom_raw, &triangles_by_color_bottom,
+                                                                  &throw_on_cancel_callback, &bottom_raw, &triangles_by_color_bottom, &project_to_shells,
                                                                   &shell_triangles_by_color_top, &shell_triangles_by_color_bottom](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
-            for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx) {
+            // Each colour writes only its own vectors, so the colours run in parallel: a painted top or bottom face
+            // projects onto a single layer, which otherwise did all of its colours on one thread.
+            tbb::parallel_for(size_t(0), size_t(num_facets_states), [&](size_t color_idx) {
                 throw_on_cancel_callback();
                 LayerColorStat stat = layer_color_stat(layer_idx, color_idx);
                 if (std::vector<Polygons> &top = top_raw[color_idx]; ! top.empty() && ! top[layer_idx].empty())
@@ -1435,18 +1488,10 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                         top_ex = opening_ex(top_ex, stat.small_region_threshold);
                         if (! top_ex.empty()) {
                             append(triangles_by_color_top[color_idx][layer_idx], top_ex);
-                            float offset = 0.f;
-                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
-                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx) {
-                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
-                                //offset -= stat.extrusion_width ;
-                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
-                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
-                                ExPolygons last = opening_ex(intersection_ex(top_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
-                                if (last.empty())
-                                    break;
-                                shell_triangles_by_color_top[color_idx][layer_idx].emplace_back(size_t(last_idx), std::move(last));
-                            }
+                            std::vector<size_t> shell_layers;
+                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx)
+                                shell_layers.emplace_back(size_t(last_idx));
+                            project_to_shells(top_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_top[color_idx][layer_idx]);
                         }
                     }
                 if (std::vector<Polygons> &bottom = bottom_raw[color_idx]; ! bottom.empty() && ! bottom[layer_idx].empty())
@@ -1455,21 +1500,13 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                         bottom_ex = opening_ex(bottom_ex, stat.small_region_threshold);
                         if (! bottom_ex.empty()) {
                             append(triangles_by_color_bottom[color_idx][layer_idx], bottom_ex);
-                            float offset = 0.f;
-                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
-                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx) {
-                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
-                                //offset -= stat.extrusion_width;
-                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
-                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
-                                ExPolygons last = opening_ex(intersection_ex(bottom_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
-                                if (last.empty())
-                                    break;
-                                shell_triangles_by_color_bottom[color_idx][layer_idx].emplace_back(last_idx, std::move(last));
-                            }
+                            std::vector<size_t> shell_layers;
+                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx)
+                                shell_layers.emplace_back(last_idx);
+                            project_to_shells(bottom_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_bottom[color_idx][layer_idx]);
                         }
                     }
-            }
+            });
         }
     });
 
@@ -1490,20 +1527,23 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                                                                   &shell_top_by_layer, &shell_bottom_by_layer](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
             throw_on_cancel_callback();
-            ExPolygons painted_exploys;
-            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
+            // The per-colour unions below are independent of each other, so they run in parallel (a painted top or
+            // bottom face puts all of its colours on one layer); whatever combines the colours stays in colour order.
+            const auto merge_colour_union = [&](size_t color_idx) {
                 auto &self = triangles_by_color_merged[color_idx][layer_idx];
                 append(self, std::move(triangles_by_color_bottom[color_idx][layer_idx]));
                 append(self, std::move(triangles_by_color_top[color_idx][layer_idx]));
                 self = union_ex(self);
+            };
+            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), merge_colour_union);
 
-                append(painted_exploys, self);
-            }
-
+            ExPolygons painted_exploys;
+            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx)
+                append(painted_exploys, triangles_by_color_merged[color_idx][layer_idx]);
             painted_exploys = union_ex(painted_exploys);
 
             //BBS: merge the top and bottom shell layers
-            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
+            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), [&](size_t color_idx) {
                 auto &self = triangles_by_color_merged[color_idx][layer_idx];
 
                 auto top_area    = diff_ex(union_ex(shell_top_by_layer[color_idx][layer_idx]), painted_exploys);
@@ -1512,7 +1552,7 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                 append(self, top_area);
                 append(self, bottom_area);
                 self = union_ex(self);
-            }
+            });
             // Trim one region by the other if some of the regions overlap.
             ExPolygons painted_regions;
             for (size_t color_idx = 1; color_idx < triangles_by_color_merged.size(); ++color_idx) {
@@ -1879,7 +1919,69 @@ static void remove_multiple_edges_in_vertices(MMU_Graph &graph, const std::vecto
     }
 }
 
-static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::vector<std::vector<ExPolygons>> &segmented_regions,
+
+// Finds the islands (layer ExPolygons) a region piece overlaps. A top or bottom region is projected from the neighbouring
+// layers and may reach past the island it belongs to, or over several islands.
+class IslandLocator
+{
+public:
+    explicit IslandLocator(const ExPolygons &islands) : m_islands(islands)
+    {
+        m_bboxes.reserve(islands.size());
+        for (const ExPolygon &island : islands) {
+            m_bboxes.emplace_back(get_extents(island));
+            m_extent.merge(m_bboxes.back());
+        }
+        if (!m_extent.defined)
+            return;
+        const Point size = m_extent.size();
+        m_cell_w = std::max<coord_t>(1, size.x() / GRID + 1);
+        m_cell_h = std::max<coord_t>(1, size.y() / GRID + 1);
+        m_grid.assign(GRID * GRID, {});
+        for (size_t i = 0; i < m_bboxes.size(); ++i)
+            for_cells(m_bboxes[i], [&](int cell) { m_grid[cell].emplace_back(i); });
+    }
+
+    void find(const ExPolygon &piece, std::vector<size_t> &out) const
+    {
+        out.clear();
+        const BoundingBox bbox = get_extents(piece);
+        if (!m_extent.defined || !m_extent.overlap(bbox))
+            return;
+        for_cells(bbox, [&](int cell) {
+            for (size_t i : m_grid[cell])
+                if (m_bboxes[i].overlap(bbox))
+                    out.emplace_back(i);
+        });
+        sort_remove_duplicates(out);
+        if (out.size() > 1)
+            out.erase(std::remove_if(out.begin(), out.end(), [&](size_t i) {
+                const BoundingBox common(m_bboxes[i].min.cwiseMax(bbox.min), m_bboxes[i].max.cwiseMin(bbox.max));
+                return intersection(ClipperUtils::clip_clipper_polygons_with_subject_bbox(piece, common.inflated(SCALED_EPSILON)),
+                                    ClipperUtils::clip_clipper_polygons_with_subject_bbox(m_islands[i], common.inflated(SCALED_EPSILON))).empty();
+            }), out.end());
+    }
+
+private:
+    static constexpr int GRID = 64;
+    template<typename Fn> void for_cells(const BoundingBox &bb, Fn &&fn) const
+    {
+        const int x0 = std::clamp(int((bb.min.x() - m_extent.min.x()) / m_cell_w), 0, GRID - 1), x1 = std::clamp(int((bb.max.x() - m_extent.min.x()) / m_cell_w), 0, GRID - 1);
+        const int y0 = std::clamp(int((bb.min.y() - m_extent.min.y()) / m_cell_h), 0, GRID - 1), y1 = std::clamp(int((bb.max.y() - m_extent.min.y()) / m_cell_h), 0, GRID - 1);
+        for (int y = y0; y <= y1; ++y)
+            for (int x = x0; x <= x1; ++x)
+                fn(y * GRID + x);
+    }
+
+    const ExPolygons                &m_islands;
+    std::vector<BoundingBox>         m_bboxes;
+    BoundingBox                      m_extent;
+    coord_t                          m_cell_w = 1, m_cell_h = 1;
+    std::vector<std::vector<size_t>> m_grid;
+};
+
+static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::vector<ExPolygons>              &input_expolygons,
+                                                                   const std::vector<std::vector<ExPolygons>> &segmented_regions,
                                                                    std::vector<std::vector<ExPolygons>>      &&top_and_bottom_layers,
                                                                    const size_t                                num_facets_states,
                                                                    const std::function<void()>                &throw_on_cancel_callback)
@@ -1890,33 +1992,91 @@ static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::ve
     assert(!top_and_bottom_layers.size() || num_facets_states == top_and_bottom_layers.size());
 
     BOOST_LOG_TRIVIAL(debug) << "Print object segmentation - Merging segmented layers in parallel - Begin";
-    tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&segmented_regions, &top_and_bottom_layers, &segmented_regions_merged, &num_facets_states, &throw_on_cancel_callback](const tbb::blocked_range<size_t> &range) {
+    // Every region of a layer is merged together with the regions of the islands it overlaps, and the islands are further
+    // apart than the dimple removal below reaches, so this gives the same result as merging the layer at once. On a layer
+    // cut through a fine relief every region shares thousands of hole contours with every other, and Clipper, splitting
+    // and re-linking one huge polygon over and over, took anything up to half an hour for a layer; per island each operation
+    // stays the size of the island, and the islands run in parallel.
+    tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++layer_idx) {
             assert(segmented_regions[layer_idx].size() == num_facets_states);
-            // Zero is skipped because it is the default color of the volume
+            throw_on_cancel_callback();
+            // Group the islands joined by a region overlapping several of them; the last group takes the regions lying
+            // outside every island.
+            const ExPolygons   &islands = input_expolygons[layer_idx];
+            const IslandLocator locator(islands);
+            std::vector<size_t> parent(islands.size() + 1);
+            std::iota(parent.begin(), parent.end(), 0);
+            const auto root = [&parent](size_t i) {
+                while (parent[i] != i)
+                    i = parent[i] = parent[parent[i]];
+                return i;
+            };
+            // Islands of every piece: side regions of colours 1.., then top/bottom regions of colours 0..
+            std::vector<const ExPolygon *> pieces;
+            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                for (const ExPolygon &piece : segmented_regions[layer_idx][extruder_id])
+                    pieces.emplace_back(&piece);
+            if (!top_and_bottom_layers.empty())
+                for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx)
+                    for (const ExPolygon &piece : top_and_bottom_layers[color_idx][layer_idx])
+                        pieces.emplace_back(&piece);
+            std::vector<std::vector<size_t>> overlapped(pieces.size());
+            tbb::parallel_for(size_t(0), pieces.size(), [&](size_t i) { locator.find(*pieces[i], overlapped[i]); });
+            std::vector<size_t> piece_island(pieces.size());
+            for (size_t i = 0; i < pieces.size(); ++i) {
+                piece_island[i] = overlapped[i].empty() ? islands.size() : overlapped[i].front();
+                for (size_t island : overlapped[i])
+                    parent[root(island)] = root(piece_island[i]);
+            }
+            std::vector<size_t> bucket_of(parent.size(), size_t(-1));
+            size_t              num_buckets = 0;
+            for (size_t i = 0; i < parent.size(); ++i)
+                if (size_t &b = bucket_of[root(i)]; b == size_t(-1))
+                    b = num_buckets++;
+
+            // [bucket][colour]
+            std::vector<std::vector<ExPolygons>> sides(num_buckets, std::vector<ExPolygons>(num_facets_states));
+            std::vector<std::vector<ExPolygons>> tops(num_buckets, std::vector<ExPolygons>(num_facets_states));
+            size_t                               piece_idx = 0;
+            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                for (const ExPolygon &piece : segmented_regions[layer_idx][extruder_id])
+                    sides[bucket_of[root(piece_island[piece_idx++])]][extruder_id].emplace_back(piece);
+            if (!top_and_bottom_layers.empty())
+                for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx)
+                    for (const ExPolygon &piece : top_and_bottom_layers[color_idx][layer_idx])
+                        tops[bucket_of[root(piece_island[piece_idx++])]][color_idx].emplace_back(piece);
+
+            // Side regions minus the top/bottom regions of every colour.
+            std::vector<std::vector<ExPolygons>> merged(num_buckets, std::vector<ExPolygons>(num_facets_states));
+            tbb::parallel_for(size_t(0), num_buckets, [&](size_t bucket) {
+                Polygons tops_all;
+                for (const ExPolygons &t : tops[bucket])
+                    polygons_append(tops_all, t);
+                for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                    if (!sides[bucket][extruder_id].empty())
+                        merged[bucket][extruder_id] = tops_all.empty() ? std::move(sides[bucket][extruder_id]) :
+                                                                         diff_ex_by_piece(sides[bucket][extruder_id], tops_all);
+            });
+
+            // Then this colour's top/bottom regions, with the dimples removed (#7235) when the layer has side regions left.
             for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id) {
-                throw_on_cancel_callback();
-                if (!segmented_regions[layer_idx][extruder_id].empty()) {
-                    ExPolygons segmented_regions_trimmed = segmented_regions[layer_idx][extruder_id];
-                    if (!top_and_bottom_layers.empty()) {
-                        for (const std::vector<ExPolygons> &top_and_bottom_by_extruder : top_and_bottom_layers) {
-                            if (!top_and_bottom_by_extruder[layer_idx].empty() && !segmented_regions_trimmed.empty()) {
-                                segmented_regions_trimmed = diff_ex(segmented_regions_trimmed, top_and_bottom_by_extruder[layer_idx]);
-                            }
-                        }
-                    }
-
-                    segmented_regions_merged[layer_idx][extruder_id - 1] = std::move(segmented_regions_trimmed);
-                }
-
-                if (!top_and_bottom_layers.empty() && !top_and_bottom_layers[extruder_id][layer_idx].empty()) {
-                    bool was_top_and_bottom_empty = segmented_regions_merged[layer_idx][extruder_id - 1].empty();
-                    append(segmented_regions_merged[layer_idx][extruder_id - 1], top_and_bottom_layers[extruder_id][layer_idx]);
-
-                    // Remove dimples (#7235) appearing after merging side segmentation of the model with tops and bottoms painted layers.
-                    if (!was_top_and_bottom_empty)
-                        segmented_regions_merged[layer_idx][extruder_id - 1] = offset2_ex(union_ex(segmented_regions_merged[layer_idx][extruder_id - 1]), float(SCALED_EPSILON), -float(SCALED_EPSILON));
+                if (top_and_bottom_layers.empty() || top_and_bottom_layers[extruder_id][layer_idx].empty()) {
+                    for (size_t bucket = 0; bucket < num_buckets; ++bucket)
+                        append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
+                    continue;
                 }
+                bool was_top_and_bottom_empty = true;
+                for (size_t bucket = 0; bucket < num_buckets && was_top_and_bottom_empty; ++bucket)
+                    was_top_and_bottom_empty = merged[bucket][extruder_id].empty();
+                tbb::parallel_for(size_t(0), num_buckets, [&](size_t bucket) {
+                    ExPolygons &region = merged[bucket][extruder_id];
+                    append(region, tops[bucket][extruder_id]);
+                    if (!was_top_and_bottom_empty && !region.empty())
+                        region = offset2_ex(union_ex(region), float(SCALED_EPSILON), -float(SCALED_EPSILON));
+                });
+                for (size_t bucket = 0; bucket < num_buckets; ++bucket)
+                    append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
             }
         }
     }); // end of parallel_for
@@ -2203,16 +2363,56 @@ std::vector<std::vector<ExPolygons>> segmentation_by_painting(const PrintObject
 
                 assert(!color_poly.empty());
                 assert(!color_poly.front().empty());
-                if (has_layer_only_one_color(color_poly)) {
-                    // If the whole layer is painted using the same color, it is not needed to construct a Voronoi diagram for the segmentation of this layer.
-                    segmented_regions[layer_idx][size_t(color_poly.front().front().color)] = input_expolygons[layer_idx];
-                } else {
-                    MMU_Graph graph = build_graph(layer_idx, color_poly);
-                    remove_multiple_edges_in_vertices(graph, color_poly);
-                    graph.remove_nodes_with_one_arc();
-                    segmented_regions[layer_idx] = extract_colored_segments(graph, num_facets_states);
-                    //segmented_regions[layer_idx] = extract_colored_segments(color_poly, num_extruders, layer_idx);
+                // Each island (an ExPolygon with its holes) is segmented on its own. Any point of an island is closer to
+                // that island's contours than to any other island's - the way out crosses its own boundary first - so its
+                // Voronoi cells, and with them its colour regions, depend on nothing else. A layer cut through a fine relief
+                // has thousands of islands, and one Voronoi diagram over all of them degenerated into overlapping regions
+                // that every boolean afterwards had to untangle. Per island the diagrams stay small and the islands run in
+                // parallel; an island in a single colour needs no diagram at all.
+                const ExPolygons                      &islands = input_expolygons[layer_idx];
+                std::vector<std::pair<size_t, size_t>> island_contours(islands.size()); // [first, last) into color_poly
+                {
+                    // The same order EdgeGrid::Grid::create() lists the contours in, and so colorize_contours().
+                    size_t idx = 0;
+                    for (size_t island_idx = 0; island_idx < islands.size(); ++island_idx) {
+                        const size_t first = idx;
+                        if (!islands[island_idx].contour.empty())
+                            ++idx;
+                        for (const Polygon &hole : islands[island_idx].holes)
+                            if (!hole.empty())
+                                ++idx;
+                        island_contours[island_idx] = {first, idx};
+                    }
+                    assert(idx == color_poly.size());
                 }
+                std::vector<std::vector<ExPolygons>> island_regions(islands.size());
+                tbb::parallel_for(size_t(0), islands.size(), [&](size_t island_idx) {
+                    const auto [first, last] = island_contours[island_idx];
+                    if (first == last)
+                        return;
+                    const std::vector<ColoredLines> island_poly(color_poly.begin() + first, color_poly.begin() + last);
+                    std::vector<ExPolygons>        &regions = island_regions[island_idx];
+                    if (has_layer_only_one_color(island_poly)) {
+                        regions.assign(num_facets_states, ExPolygons());
+                        regions[size_t(island_poly.front().front().color)].emplace_back(islands[island_idx]);
+                    } else {
+                        MMU_Graph graph = build_graph(layer_idx, island_poly);
+                        remove_multiple_edges_in_vertices(graph, island_poly);
+                        graph.remove_nodes_with_one_arc();
+                        regions = extract_colored_segments(graph, num_facets_states);
+                        // The faces of one colour tile it without overlapping; merged here, where an island is small,
+                        // every later boolean gets a few regions instead of thousands of faces sharing their edges. An
+                        // island with many holes keeps its faces: merged, each colour would be one region with thousands
+                        // of holes, and subtracting from that is far slower than from the faces one at a time.
+                        if (island_poly.size() <= 64)
+                            for (ExPolygons &faces : regions)
+                                if (faces.size() > 1)
+                                    faces = union_ex(faces);
+                    }
+                });
+                for (std::vector<ExPolygons> &regions : island_regions)
+                    for (size_t color_idx = 0; color_idx < regions.size(); ++color_idx)
+                        append(segmented_regions[layer_idx][color_idx], std::move(regions[color_idx]));
 
 #ifdef MM_SEGMENTATION_DEBUG_REGIONS
                 export_regions_to_svg(debug_out_path("3-mm-regions-sides-%d-%d.svg", layer_idx, iRun), segmented_regions[layer_idx], input_expolygons[layer_idx]);
@@ -2235,7 +2435,7 @@ std::vector<std::vector<ExPolygons>> segmentation_by_painting(const PrintObject
         throw_on_cancel_callback();
     }
 
-    std::vector<std::vector<ExPolygons>> segmented_regions_merged = merge_segmented_layers(segmented_regions, std::move(top_and_bottom_layers), num_facets_states, throw_on_cancel_callback);
+    std::vector<std::vector<ExPolygons>> segmented_regions_merged = merge_segmented_layers(input_expolygons, segmented_regions, std::move(top_and_bottom_layers), num_facets_states, throw_on_cancel_callback);
     throw_on_cancel_callback();
 
 #ifdef MM_SEGMENTATION_DEBUG_REGIONS

src/libslic3r/MultiPoint.hpp

@@ -23,11 +23,15 @@ public:
     
     MultiPoint() {}
     MultiPoint(const MultiPoint &other) : points(other.points) {}
-    MultiPoint(MultiPoint &&other) : points(std::move(other.points)) {}
+    MultiPoint(MultiPoint &&other) noexcept : points(std::move(other.points)) {}
     MultiPoint(std::initializer_list<Point> list) : points(list) {}
     explicit MultiPoint(const Points &_points) : points(_points) {}
+    // Without it, the derived classes' move constructors passing std::move(points) here copied them, which
+    // also means a moved-from Polygon or Polyline is now really empty where it used to silently keep its
+    // points: a use-after-move anywhere in the tree that happened to work before now sees nothing.
+    explicit MultiPoint(Points &&_points) noexcept : points(std::move(_points)) {}
     MultiPoint& operator=(const MultiPoint &other) { points = other.points; return *this; }
-    MultiPoint& operator=(MultiPoint &&other) { points = std::move(other.points); return *this; }
+    MultiPoint& operator=(MultiPoint &&other) noexcept { points = std::move(other.points); return *this; }
     virtual ~MultiPoint() = default;
     void scale(double factor);
     void scale(double factor_x, double factor_y);

src/libslic3r/PerimeterGenerator.cpp

@@ -33,6 +33,8 @@
 #include <tuple>
 #include <unordered_set>
 #include <thread>
+#include <tbb/blocked_range.h>
+#include <tbb/parallel_for.h>
 #include <vector>
 #include "libslic3r.h"
 #include <utility>
@@ -2491,421 +2493,444 @@ void PerimeterGenerator::process_arachne()
     const bool only_one_wall_first_layer = this->config->only_one_wall_first_layer && has_bottom_shell_layers(*this->config);
     // we need to process each island separately because we might have different
     // extra perimeters for each one
-    for (const Surface& surface : all_surfaces) {
-        coord_t bead_width_0 = ext_perimeter_spacing;
-        // detect how many perimeters must be generated for this island
-        int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
-        int sparse_infill_density = this->config->sparse_infill_density.value;
-        if (this->config->alternate_extra_wall && this->layer_id % 2 == 1 && !m_spiral_vase && sparse_infill_density > 0) // add alternating extra wall
-            loop_number++;
+    // Each island is independent up to its outputs, so they are generated in parallel - a layer split into thousands
+    // of islands (e.g. by colour painting) otherwise ran on one thread - and the outputs are then committed in the
+    // original island order, which is what the extra overhang perimeters (applied to the last island's loops and to
+    // all fill surfaces so far) depend on.
+    struct ArachneSurfaceResult
+    {
+        ExtrusionEntityCollection loops;
+        bool                      has_loops = false;
+        ExPolygons                infill;
+        ExPolygons                no_overlap;
+    };
+    std::vector<ArachneSurfaceResult> results(all_surfaces.size());
+    tbb::parallel_for(tbb::blocked_range<size_t>(0, all_surfaces.size()), [&](const tbb::blocked_range<size_t> &range) {
+      for (size_t surface_idx = range.begin(); surface_idx < range.end(); ++surface_idx) {
+        const Surface        &surface = all_surfaces[surface_idx];
+        ArachneSurfaceResult &result  = results[surface_idx];
+            coord_t bead_width_0 = ext_perimeter_spacing;
+            // detect how many perimeters must be generated for this island
+            int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
+            int sparse_infill_density = this->config->sparse_infill_density.value;
+            if (this->config->alternate_extra_wall && this->layer_id % 2 == 1 && !m_spiral_vase && sparse_infill_density > 0) // add alternating extra wall
+                loop_number++;
 
-        // Set the bottommost layer to be one wall
-        const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
-        if (is_bottom_layer && only_one_wall_first_layer)
-            loop_number = 0;
+            // Set the bottommost layer to be one wall
+            const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
+            if (is_bottom_layer && only_one_wall_first_layer)
+                loop_number = 0;
 
-        // Orca: set the topmost layer to be one wall according to the config
-        const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
-        if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
-            loop_number = 0;
+            // Orca: set the topmost layer to be one wall according to the config
+            const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
+            if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
+                loop_number = 0;
         
-        auto apply_precise_outer_wall = config->precise_outer_wall && config->wall_sequence == WallSequence::InnerOuter;
-        // Orca: properly adjust offset for the outer wall if precise_outer_wall is enabled.
-        ExPolygons last = offset_ex(surface.expolygon.simplify_p(surface_simplify_resolution),
-                       apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
-                                                 : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
+            auto apply_precise_outer_wall = config->precise_outer_wall && config->wall_sequence == WallSequence::InnerOuter;
+            // Orca: properly adjust offset for the outer wall if precise_outer_wall is enabled.
+            ExPolygons last = offset_ex(surface.expolygon.simplify_p(surface_simplify_resolution),
+                           apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
+                                                     : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
         
-        Arachne::WallToolPathsParams input_params = Arachne::make_paths_params(this->layer_id, *object_config, *print_config);
-        // Set params is_top_or_bottom_layer for adjusting short-wall removal sensitivity.
-        input_params.is_top_or_bottom_layer = (is_bottom_layer || is_topmost_layer) ? true : false;
+            Arachne::WallToolPathsParams input_params = Arachne::make_paths_params(this->layer_id, *object_config, *print_config);
+            // Set params is_top_or_bottom_layer for adjusting short-wall removal sensitivity.
+            input_params.is_top_or_bottom_layer = (is_bottom_layer || is_topmost_layer) ? true : false;
 
-        coord_t wall_0_inset = 0;
-        if (apply_precise_outer_wall)
-           wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
+            coord_t wall_0_inset = 0;
+            if (apply_precise_outer_wall)
+               wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
 
-        //PS: One wall top surface for Arachne
-        ExPolygons top_expolygons;
-        // Calculate how many inner loops remain when TopSurfaces is selected.
-        const int inner_loop_number = (only_one_wall_top && upper_slices != nullptr) ? loop_number - 1 : -1;
+            //PS: One wall top surface for Arachne
+            ExPolygons top_expolygons;
+            // Calculate how many inner loops remain when TopSurfaces is selected.
+            const int inner_loop_number = (only_one_wall_top && upper_slices != nullptr) ? loop_number - 1 : -1;
 
-        // Set one perimeter when TopSurfaces is selected.
-        if (only_one_wall_top && loop_number > 0)
-            loop_number = 0;
+            // Set one perimeter when TopSurfaces is selected.
+            if (only_one_wall_top && loop_number > 0)
+                loop_number = 0;
 
-        Arachne::WallToolPathsParams input_params_tmp = input_params;
+            Arachne::WallToolPathsParams input_params_tmp = input_params;
         
-        Polygons   last_p = to_polygons(last);
-        Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
-                                               wall_0_inset, layer_height, input_params_tmp);
-        std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
-        ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
+            Polygons   last_p = to_polygons(last);
+            Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
+                                                   wall_0_inset, layer_height, input_params_tmp);
+            std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
+            ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
 
-        // Check if there are some remaining perimeters to generate (the number of perimeters
-        // is greater than one together with enabled the single perimeter on top surface feature).
-        if (inner_loop_number >= 0) {
-            assert(upper_slices != nullptr);
+            // Check if there are some remaining perimeters to generate (the number of perimeters
+            // is greater than one together with enabled the single perimeter on top surface feature).
+            if (inner_loop_number >= 0) {
+                assert(upper_slices != nullptr);
 
-            // Infill contour bounding box.
-            BoundingBox infill_contour_bbox = get_extents(infill_contour);
-            infill_contour_bbox.offset(SCALED_EPSILON);
+                // Infill contour bounding box.
+                BoundingBox infill_contour_bbox = get_extents(infill_contour);
+                infill_contour_bbox.offset(SCALED_EPSILON);
             
-            coord_t perimeter_width = this->perimeter_flow.scaled_width();
+                coord_t perimeter_width = this->perimeter_flow.scaled_width();
 
-            // Get top ExPolygons from current infill contour.
-            Polygons upper_slices_clipped;
-            if (object_config->interface_shells) {
-                auto upper_slicer_same_region = to_expolygons(this->upper_slices_same_region->surfaces);
-                upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(upper_slicer_same_region, infill_contour_bbox);
-            } else
-                upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*upper_slices, infill_contour_bbox);
+                // Get top ExPolygons from current infill contour.
+                Polygons upper_slices_clipped;
+                if (object_config->interface_shells) {
+                    auto upper_slicer_same_region = to_expolygons(this->upper_slices_same_region->surfaces);
+                    upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(upper_slicer_same_region, infill_contour_bbox);
+                } else
+                    upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*upper_slices, infill_contour_bbox);
 
-            top_expolygons = diff_ex(infill_contour, upper_slices_clipped);
+                top_expolygons = diff_ex(infill_contour, upper_slices_clipped);
 
-            if (!top_expolygons.empty()) {
-                if (lower_slices != nullptr) {
-                    const float      bridge_offset          = float(std::max<coord_t>(ext_perimeter_spacing, perimeter_width));
-                    const Polygons   lower_slices_clipped   = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*lower_slices, infill_contour_bbox);
-                    const ExPolygons current_slices_bridges = offset_ex(diff_ex(top_expolygons, lower_slices_clipped), bridge_offset);
+                if (!top_expolygons.empty()) {
+                    if (lower_slices != nullptr) {
+                        const float      bridge_offset          = float(std::max<coord_t>(ext_perimeter_spacing, perimeter_width));
+                        const Polygons   lower_slices_clipped   = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*lower_slices, infill_contour_bbox);
+                        const ExPolygons current_slices_bridges = offset_ex(diff_ex(top_expolygons, lower_slices_clipped), bridge_offset);
 
-                    // Remove bridges from top surface polygons.
-                    top_expolygons = diff_ex(top_expolygons, current_slices_bridges);
+                        // Remove bridges from top surface polygons.
+                        top_expolygons = diff_ex(top_expolygons, current_slices_bridges);
+                    }
+
+                    // Filter out areas that are too thin and expand top surface polygons a bit to hide the wall line.
+                    // ORCA: skip if the top surface area is smaller than "min_width_top_surface"
+                    const float top_surface_min_width = std::max<float>(float(ext_perimeter_spacing) / 4.f + scaled<float>(0.00001), float(scale_(config->min_width_top_surface.get_abs_value(unscale_(perimeter_width)))) / 4.f);
+                    // Shrink the polygon to remove the small areas, then expand it back out plus a maragin to hide the wall line a little.
+                    // ORCA: Expand the polygon with half the perimeter width in addition to the contracted amount,
+                    // not the full perimeter width as PS does, to enable thin lettering to print on the top surface without nozzle collisions
+                    // due to thin lines being generated
+                    top_expolygons = offset2_ex(top_expolygons, -top_surface_min_width, top_surface_min_width + float(perimeter_width * 0.85));
+
+                    // Get final top ExPolygons (bridges were excluded above, so they stay walled).
+                    top_expolygons = intersection_ex(top_expolygons, infill_contour);
+
+                    // ORCA: onion the real region (inside the outer wall) so the remaining walls follow the actual
+                    // geometry, then cut away the parts over the top surface. Re-onioning the non-top complement
+                    // instead - the fallback when there is no top fill - walls the top/non-top interface and rings
+                    // top-surface islands with inner walls that don't exist when the feature is disabled.
+                    const bool     clip_walls_over_top = top_fill_replaces_inner_walls(*this->config);
+                    const Polygons inner_region        = to_polygons(offset_ex(clip_walls_over_top ? infill_contour
+                                                                                                   : diff_ex(infill_contour, top_expolygons),
+                                                                              wall_0_inset));
+                    Arachne::WallToolPaths inner_wall_tool_paths(inner_region, perimeter_spacing, perimeter_spacing, coord_t(inner_loop_number + 1), 0, layer_height, input_params_tmp);
+                    std::vector<Arachne::VariableWidthLines> inner_perimeters = inner_wall_tool_paths.getToolPaths();
+
+                    if (clip_walls_over_top) {
+                        Polygons kept_over_top;
+                        clip_inner_walls_over_top(inner_perimeters, top_expolygons, perimeter_width, kept_over_top);
+                        // Route the top fill around the walls kept despite grazing the top.
+                        if (! kept_over_top.empty())
+                            top_expolygons = diff_ex(top_expolygons, kept_over_top);
+                    }
+
+                    // Recalculate indexes of inner perimeters before merging them: they come after the single outer wall.
+                    if (!perimeters.empty())
+                        for (Arachne::VariableWidthLines &inner_perimeter : inner_perimeters)
+                            for (Arachne::ExtrusionLine &el : inner_perimeter)
+                                ++el.inset_idx;
+
+                    perimeters.insert(perimeters.end(), inner_perimeters.begin(), inner_perimeters.end());
+                    infill_contour = union_ex(top_expolygons, inner_wall_tool_paths.getInnerContour());
+                } else {
+                    // There is no top surface ExPolygon, so we call Arachne again with parameters
+                    // like when the single perimeter feature is disabled.
+                    Arachne::WallToolPaths no_single_perimeter_tool_paths(last_p, bead_width_0, perimeter_spacing, coord_t(inner_loop_number + 2), wall_0_inset, layer_height, input_params_tmp);
+                    perimeters     = no_single_perimeter_tool_paths.getToolPaths();
+                    infill_contour = union_ex(no_single_perimeter_tool_paths.getInnerContour());
                 }
-
-                // Filter out areas that are too thin and expand top surface polygons a bit to hide the wall line.
-                // ORCA: skip if the top surface area is smaller than "min_width_top_surface"
-                const float top_surface_min_width = std::max<float>(float(ext_perimeter_spacing) / 4.f + scaled<float>(0.00001), float(scale_(config->min_width_top_surface.get_abs_value(unscale_(perimeter_width)))) / 4.f);
-                // Shrink the polygon to remove the small areas, then expand it back out plus a maragin to hide the wall line a little.
-                // ORCA: Expand the polygon with half the perimeter width in addition to the contracted amount,
-                // not the full perimeter width as PS does, to enable thin lettering to print on the top surface without nozzle collisions
-                // due to thin lines being generated
-                top_expolygons = offset2_ex(top_expolygons, -top_surface_min_width, top_surface_min_width + float(perimeter_width * 0.85));
-
-                // Get final top ExPolygons (bridges were excluded above, so they stay walled).
-                top_expolygons = intersection_ex(top_expolygons, infill_contour);
-
-                // ORCA: onion the real region (inside the outer wall) so the remaining walls follow the actual
-                // geometry, then cut away the parts over the top surface. Re-onioning the non-top complement
-                // instead - the fallback when there is no top fill - walls the top/non-top interface and rings
-                // top-surface islands with inner walls that don't exist when the feature is disabled.
-                const bool     clip_walls_over_top = top_fill_replaces_inner_walls(*this->config);
-                const Polygons inner_region        = to_polygons(offset_ex(clip_walls_over_top ? infill_contour
-                                                                                               : diff_ex(infill_contour, top_expolygons),
-                                                                          wall_0_inset));
-                Arachne::WallToolPaths inner_wall_tool_paths(inner_region, perimeter_spacing, perimeter_spacing, coord_t(inner_loop_number + 1), 0, layer_height, input_params_tmp);
-                std::vector<Arachne::VariableWidthLines> inner_perimeters = inner_wall_tool_paths.getToolPaths();
-
-                if (clip_walls_over_top) {
-                    Polygons kept_over_top;
-                    clip_inner_walls_over_top(inner_perimeters, top_expolygons, perimeter_width, kept_over_top);
-                    // Route the top fill around the walls kept despite grazing the top.
-                    if (! kept_over_top.empty())
-                        top_expolygons = diff_ex(top_expolygons, kept_over_top);
-                }
-
-                // Recalculate indexes of inner perimeters before merging them: they come after the single outer wall.
-                if (!perimeters.empty())
-                    for (Arachne::VariableWidthLines &inner_perimeter : inner_perimeters)
-                        for (Arachne::ExtrusionLine &el : inner_perimeter)
-                            ++el.inset_idx;
-
-                perimeters.insert(perimeters.end(), inner_perimeters.begin(), inner_perimeters.end());
-                infill_contour = union_ex(top_expolygons, inner_wall_tool_paths.getInnerContour());
-            } else {
-                // There is no top surface ExPolygon, so we call Arachne again with parameters
-                // like when the single perimeter feature is disabled.
-                Arachne::WallToolPaths no_single_perimeter_tool_paths(last_p, bead_width_0, perimeter_spacing, coord_t(inner_loop_number + 2), wall_0_inset, layer_height, input_params_tmp);
-                perimeters     = no_single_perimeter_tool_paths.getToolPaths();
-                infill_contour = union_ex(no_single_perimeter_tool_paths.getInnerContour());
             }
-        }
-        //PS
+            //PS
 
-        loop_number = int(perimeters.size()) - 1;
+            loop_number = int(perimeters.size()) - 1;
 
-        #ifdef ARACHNE_DEBUG
-        {
-            static int iRun = 0;
-            export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
-        }
-#endif
+            #ifdef ARACHNE_DEBUG
+            {
+                static int iRun = 0;
+                export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
+            }
+    #endif
 
-        // All closed ExtrusionLine should have the same the first and the last point.
-        // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
-        // equal the first and the last point.
-        assert([&perimeters = std::as_const(perimeters)]() -> bool {
-            for (const Arachne::VariableWidthLines& perimeter : perimeters)
-                for (const Arachne::ExtrusionLine& el : perimeter)
-                    if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
-                        return false;
-            return true;
-        }());
+            // All closed ExtrusionLine should have the same the first and the last point.
+            // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
+            // equal the first and the last point.
+            assert([&perimeters = std::as_const(perimeters)]() -> bool {
+                for (const Arachne::VariableWidthLines& perimeter : perimeters)
+                    for (const Arachne::ExtrusionLine& el : perimeter)
+                        if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
+                            return false;
+                return true;
+            }());
 
-        int start_perimeter = int(perimeters.size()) - 1;
-        int end_perimeter = -1;
-        int direction = -1;
+            int start_perimeter = int(perimeters.size()) - 1;
+            int end_perimeter = -1;
+            int direction = -1;
 
-		bool is_outer_wall_first =
-            	this->config->wall_sequence == WallSequence::OuterInner ||
-            	this->config->wall_sequence == WallSequence::InnerOuterInner;
+    		bool is_outer_wall_first =
+                	this->config->wall_sequence == WallSequence::OuterInner ||
+                	this->config->wall_sequence == WallSequence::InnerOuterInner;
         
-        if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
-        	is_outer_wall_first =
-            	this->config->wall_sequence == WallSequence::OuterInner;
-        }
-        if (is_outer_wall_first) {
-            start_perimeter = 0;
-            end_perimeter = int(perimeters.size());
-            direction = 1;
-        }
-
-        std::vector<Arachne::ExtrusionLine*> all_extrusions;
-        for (int perimeter_idx = start_perimeter; perimeter_idx != end_perimeter; perimeter_idx += direction) {
-            if (perimeters[perimeter_idx].empty())
-                continue;
-            for (Arachne::ExtrusionLine& wall : perimeters[perimeter_idx])
-                all_extrusions.emplace_back(&wall);
-        }
-
-        // Find topological order with constraints from extrusions_constrains.
-        std::vector<size_t>              blocked(all_extrusions.size(), 0); // Value indicating how many extrusions it is blocking (preceding extrusions) an extrusion.
-        std::vector<std::vector<size_t>> blocking(all_extrusions.size());   // Each extrusion contains a vector of extrusions that are blocked by this extrusion.
-        std::unordered_map<const Arachne::ExtrusionLine*, size_t> map_extrusion_to_idx;
-        for (size_t idx = 0; idx < all_extrusions.size(); idx++)
-            map_extrusion_to_idx.emplace(all_extrusions[idx], idx);
-
-        auto extrusions_constrains = Arachne::WallToolPaths::getRegionOrder(all_extrusions, is_outer_wall_first);
-        for (auto [before, after] : extrusions_constrains) {
-            auto after_it = map_extrusion_to_idx.find(after);
-            ++blocked[after_it->second];
-            blocking[map_extrusion_to_idx.find(before)->second].emplace_back(after_it->second);
-        }
-
-        std::vector<bool> processed(all_extrusions.size(), false);          // Indicate that the extrusion was already processed.
-        Point             current_position = all_extrusions.empty() ? Point::Zero() : all_extrusions.front()->junctions.front().p; // Some starting position.
-        std::vector<PerimeterGeneratorArachneExtrusion> ordered_extrusions;         // To store our result in. At the end we'll std::swap.
-        ordered_extrusions.reserve(all_extrusions.size());
-
-        while (ordered_extrusions.size() < all_extrusions.size()) {
-            size_t best_candidate = 0;
-            double best_distance_sqr = std::numeric_limits<double>::max();
-            bool   is_best_closed = false;
-
-            std::vector<size_t> available_candidates;
-            for (size_t candidate = 0; candidate < all_extrusions.size(); ++candidate) {
-                if (processed[candidate] || blocked[candidate])
-                    continue; // Not a valid candidate.
-                available_candidates.push_back(candidate);
+            if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
+            	is_outer_wall_first =
+                	this->config->wall_sequence == WallSequence::OuterInner;
+            }
+            if (is_outer_wall_first) {
+                start_perimeter = 0;
+                end_perimeter = int(perimeters.size());
+                direction = 1;
             }
 
-            std::sort(available_candidates.begin(), available_candidates.end(), [&all_extrusions](const size_t a_idx, const size_t b_idx) -> bool {
-                return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
-                });
-
-            for (const size_t candidate_path_idx : available_candidates) {
-                auto& path = all_extrusions[candidate_path_idx];
-
-                if (path->junctions.empty()) { // No vertices in the path. Can't find the start position then or really plan it in. Put that at the end.
-                    if (best_distance_sqr == std::numeric_limits<double>::max()) {
-                        best_candidate = candidate_path_idx;
-                        is_best_closed = path->is_closed;
-                    }
+            std::vector<Arachne::ExtrusionLine*> all_extrusions;
+            for (int perimeter_idx = start_perimeter; perimeter_idx != end_perimeter; perimeter_idx += direction) {
+                if (perimeters[perimeter_idx].empty())
                     continue;
+                for (Arachne::ExtrusionLine& wall : perimeters[perimeter_idx])
+                    all_extrusions.emplace_back(&wall);
+            }
+
+            // Find topological order with constraints from extrusions_constrains.
+            std::vector<size_t>              blocked(all_extrusions.size(), 0); // Value indicating how many extrusions it is blocking (preceding extrusions) an extrusion.
+            std::vector<std::vector<size_t>> blocking(all_extrusions.size());   // Each extrusion contains a vector of extrusions that are blocked by this extrusion.
+            std::unordered_map<const Arachne::ExtrusionLine*, size_t> map_extrusion_to_idx;
+            for (size_t idx = 0; idx < all_extrusions.size(); idx++)
+                map_extrusion_to_idx.emplace(all_extrusions[idx], idx);
+
+            auto extrusions_constrains = Arachne::WallToolPaths::getRegionOrder(all_extrusions, is_outer_wall_first);
+            for (auto [before, after] : extrusions_constrains) {
+                auto after_it = map_extrusion_to_idx.find(after);
+                ++blocked[after_it->second];
+                blocking[map_extrusion_to_idx.find(before)->second].emplace_back(after_it->second);
+            }
+
+            std::vector<bool> processed(all_extrusions.size(), false);          // Indicate that the extrusion was already processed.
+            Point             current_position = all_extrusions.empty() ? Point::Zero() : all_extrusions.front()->junctions.front().p; // Some starting position.
+            std::vector<PerimeterGeneratorArachneExtrusion> ordered_extrusions;         // To store our result in. At the end we'll std::swap.
+            ordered_extrusions.reserve(all_extrusions.size());
+
+            while (ordered_extrusions.size() < all_extrusions.size()) {
+                size_t best_candidate = 0;
+                double best_distance_sqr = std::numeric_limits<double>::max();
+                bool   is_best_closed = false;
+
+                std::vector<size_t> available_candidates;
+                for (size_t candidate = 0; candidate < all_extrusions.size(); ++candidate) {
+                    if (processed[candidate] || blocked[candidate])
+                        continue; // Not a valid candidate.
+                    available_candidates.push_back(candidate);
                 }
 
-                const Point candidate_position = path->junctions.front().p;
-                double      distance_sqr = (current_position - candidate_position).cast<double>().norm();
-                if (distance_sqr < best_distance_sqr) { // Closer than the best candidate so far.
-                    if (path->is_closed || (!path->is_closed && best_distance_sqr != std::numeric_limits<double>::max()) || (!path->is_closed && !is_best_closed)) {
-                        best_candidate = candidate_path_idx;
-                        best_distance_sqr = distance_sqr;
-                        is_best_closed = path->is_closed;
+                std::sort(available_candidates.begin(), available_candidates.end(), [&all_extrusions](const size_t a_idx, const size_t b_idx) -> bool {
+                    return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
+                    });
+
+                for (const size_t candidate_path_idx : available_candidates) {
+                    auto& path = all_extrusions[candidate_path_idx];
+
+                    if (path->junctions.empty()) { // No vertices in the path. Can't find the start position then or really plan it in. Put that at the end.
+                        if (best_distance_sqr == std::numeric_limits<double>::max()) {
+                            best_candidate = candidate_path_idx;
+                            is_best_closed = path->is_closed;
+                        }
+                        continue;
                     }
+
+                    const Point candidate_position = path->junctions.front().p;
+                    double      distance_sqr = (current_position - candidate_position).cast<double>().norm();
+                    if (distance_sqr < best_distance_sqr) { // Closer than the best candidate so far.
+                        if (path->is_closed || (!path->is_closed && best_distance_sqr != std::numeric_limits<double>::max()) || (!path->is_closed && !is_best_closed)) {
+                            best_candidate = candidate_path_idx;
+                            best_distance_sqr = distance_sqr;
+                            is_best_closed = path->is_closed;
+                        }
+                    }
+                }
+
+                auto& best_path = all_extrusions[best_candidate];
+                ordered_extrusions.push_back({ best_path, best_path->is_contour() });
+                processed[best_candidate] = true;
+                for (size_t unlocked_idx : blocking[best_candidate])
+                    blocked[unlocked_idx]--;
+
+                if (!best_path->junctions.empty()) { //If all paths were empty, the best path is still empty. We don't upate the current position then.
+                    if (best_path->is_closed)
+                        current_position = best_path->junctions[0].p; //We end where we started.
+                    else
+                        current_position = best_path->junctions.back().p; //Pick the other end from where we started.
                 }
             }
 
-            auto& best_path = all_extrusions[best_candidate];
-            ordered_extrusions.push_back({ best_path, best_path->is_contour() });
-            processed[best_candidate] = true;
-            for (size_t unlocked_idx : blocking[best_candidate])
-                blocked[unlocked_idx]--;
+           // printf("New Layer: Layer ID %d\n",layer_id); //debug - new layer
+            if (this->config->wall_sequence == WallSequence::InnerOuterInner && layer_id > 0) { // only enable inner outer inner algorithm after first layer
+                if (ordered_extrusions.size() > 2) { // 3 walls minimum needed to do inner outer inner ordering
+                    int position = 0; // index to run the re-ordering for multiple external perimeters in a single island.
+                    int arr_i, arr_j = 0;    // indexes to run through the walls in the for loops
+                    int outer, first_internal, second_internal, max_internal, current_perimeter; // allocate index values
+                
+                    // To address any remaining scenarios where the outer perimeter contour is not first on the list as arachne sometimes reorders the perimeters when clustering
+                    // for OI mode that is used the basis for IOI
+                    bringContoursToFront(ordered_extrusions);
+                    std::vector<PerimeterGeneratorArachneExtrusion> reordered_extrusions;
+                
+                    // Debug statement to print spacing values:
+                    //printf("External threshold - Ext perimeter: %d Ext spacing: %d Int perimeter: %d Int spacing: %d\n", this->ext_perimeter_flow.scaled_width(),this->ext_perimeter_flow.scaled_spacing(),this->perimeter_flow.scaled_width(), this->perimeter_flow.scaled_spacing());
 
-            if (!best_path->junctions.empty()) { //If all paths were empty, the best path is still empty. We don't upate the current position then.
-                if (best_path->is_closed)
-                    current_position = best_path->junctions[0].p; //We end where we started.
-                else
-                    current_position = best_path->junctions.back().p; //Pick the other end from where we started.
-            }
-        }
-
-       // printf("New Layer: Layer ID %d\n",layer_id); //debug - new layer
-        if (this->config->wall_sequence == WallSequence::InnerOuterInner && layer_id > 0) { // only enable inner outer inner algorithm after first layer
-            if (ordered_extrusions.size() > 2) { // 3 walls minimum needed to do inner outer inner ordering
-                int position = 0; // index to run the re-ordering for multiple external perimeters in a single island.
-                int arr_i, arr_j = 0;    // indexes to run through the walls in the for loops
-                int outer, first_internal, second_internal, max_internal, current_perimeter; // allocate index values
+                    // Get searching thresholds. For an external perimeter we take the external perimeter spacing/2 plus the internal perimeter spacing/2 and expand by the factor
+                    // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
+                    coord_t threshold_external = (apply_precise_outer_wall)
+                        // Precise outer wall: use the full external spacing
+                        ? ( this->ext_perimeter_flow.scaled_spacing()
+                            + this->perimeter_flow.scaled_spacing()/2.0 )
+                        // Normal: half ext spacing plus half int spacing
+                        : ( this->ext_perimeter_flow.scaled_spacing()/2.0
+                            + this->perimeter_flow.scaled_spacing()/2.0 );
                 
-                // To address any remaining scenarios where the outer perimeter contour is not first on the list as arachne sometimes reorders the perimeters when clustering
-                // for OI mode that is used the basis for IOI
-                bringContoursToFront(ordered_extrusions);
-                std::vector<PerimeterGeneratorArachneExtrusion> reordered_extrusions;
+                    // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
+                    coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
                 
-                // Debug statement to print spacing values:
-                //printf("External threshold - Ext perimeter: %d Ext spacing: %d Int perimeter: %d Int spacing: %d\n", this->ext_perimeter_flow.scaled_width(),this->ext_perimeter_flow.scaled_spacing(),this->perimeter_flow.scaled_width(), this->perimeter_flow.scaled_spacing());
-
-                // Get searching thresholds. For an external perimeter we take the external perimeter spacing/2 plus the internal perimeter spacing/2 and expand by the factor
-                // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
-                coord_t threshold_external = (apply_precise_outer_wall)
-                    // Precise outer wall ⇒ use “full external spacing”
-                    ? ( this->ext_perimeter_flow.scaled_spacing()
-                        + this->perimeter_flow.scaled_spacing()/2.0 )
-                    // Normal ⇒ half ext spacing + half int spacing
-                    : ( this->ext_perimeter_flow.scaled_spacing()/2.0
-                        + this->perimeter_flow.scaled_spacing()/2.0 );
+                    // Re-order extrusions based on distance
+                    // Alorithm will aggresively optimise for the appearance of the outermost perimeter
+                    ordered_extrusions = reorderPerimetersByProximity(ordered_extrusions,threshold_external,threshold_internal );
+                    reordered_extrusions = ordered_extrusions; // copy them into the reordered extrusions vector to allow for IOI operations to be performed below without altering the base ordered extrusions list.
                 
-                // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
-                coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
-                
-                // Re-order extrusions based on distance
-                // Alorithm will aggresively optimise for the appearance of the outermost perimeter
-                ordered_extrusions = reorderPerimetersByProximity(ordered_extrusions,threshold_external,threshold_internal );
-                reordered_extrusions = ordered_extrusions; // copy them into the reordered extrusions vector to allow for IOI operations to be performed below without altering the base ordered extrusions list.
-                
-                // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
-                // scan to find the external perimeter, first internal, second internal and last perimeter in the island.
-                // We then advance the position index to move to the second island and continue until there are no more
-                // perimeters left.
-                while (position < reordered_extrusions.size()) {
-                    outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
-                    max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
-                    // run through the walls to get the index values that need re-ordering until the first one for each
-                    // is found. Start at "position" index to enable the for loop to iterate for multiple external
-                    // perimeters in a single island
-                    // printf("Reorder Loop. Position %d, extrusion list size: %d, Outer index %d, inner index %d, second inner index %d\n", position, reordered_extrusions.size(),outer,first_internal,second_internal);
-                    for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
-                        // printf("Perimeter: extrusion inset index %d, ordered extrusions array position %d\n",reordered_extrusions[arr_i].extrusion->inset_idx, arr_i);
-                        switch (reordered_extrusions[arr_i].extrusion->inset_idx) {
-                            case 0: // external perimeter
-                                if (outer == -1)
-                                    outer = arr_i;
-                                break;
-                            case 1: // first internal wall
-                                if (first_internal==-1 && arr_i>outer && outer!=-1){
-                                    first_internal = arr_i;
-                                }
-                                break;
-                            case 2: // second internal wall
-                                if (second_internal == -1 && arr_i > first_internal && outer!=-1){
-                                    second_internal = arr_i;
-                                }
-                                break;
-                        }
-                        if(outer >-1 && first_internal>-1 && reordered_extrusions[arr_i].extrusion->inset_idx == 0){  // found a new external perimeter after we've found at least a first internal perimeter to re-order.
-                                                                                                                      // This means we entered a new island.
-                            arr_i=arr_i-1; //step back one perimeter
-                            max_internal = arr_i; // new maximum internal perimeter is now this as we have found a new external perimeter, hence a new island.
-                            break; // exit the for loop
-                        }
-                    }
-                    
-                    // printf("Layer ID %d, Outer index %d, inner index %d, second inner index %d, maximum internal perimeter %d \n",layer_id,outer,first_internal,second_internal, max_internal);
-                    if (outer > -1 && first_internal > -1 && second_internal > -1) { // found all three perimeters to re-order? If not the perimeters will be processed outside in.
-                        std::vector<PerimeterGeneratorArachneExtrusion> inner_outer_extrusions; // temporary array to hold extrusions for reordering
-                        inner_outer_extrusions.resize(max_internal - position + 1); // reserve array containing the number of perimeters before a new island. Variables are array indexes hence need to add +1 to convert to position allocations
-                        // printf("Allocated array size %d, max_internal index %d, start position index %d \n",max_internal-position+1,max_internal,position);
-                        
-                        for (arr_j = max_internal; arr_j >=position; --arr_j){ // go inside out towards the external perimeter (perimeters in reverse order) and store all internal perimeters until the first one identified with inset index 2
-                            if(arr_j >= second_internal){
-                                //printf("Inside out loop: Mapped perimeter index %d to array position %d\n", arr_j, max_internal-arr_j);
-                                inner_outer_extrusions[max_internal-arr_j] = reordered_extrusions[arr_j];
-                                current_perimeter++; 
+                    // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
+                    // scan to find the external perimeter, first internal, second internal and last perimeter in the island.
+                    // We then advance the position index to move to the second island and continue until there are no more
+                    // perimeters left.
+                    while (position < reordered_extrusions.size()) {
+                        outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
+                        max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
+                        // run through the walls to get the index values that need re-ordering until the first one for each
+                        // is found. Start at "position" index to enable the for loop to iterate for multiple external
+                        // perimeters in a single island
+                        // printf("Reorder Loop. Position %d, extrusion list size: %d, Outer index %d, inner index %d, second inner index %d\n", position, reordered_extrusions.size(),outer,first_internal,second_internal);
+                        for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
+                            // printf("Perimeter: extrusion inset index %d, ordered extrusions array position %d\n",reordered_extrusions[arr_i].extrusion->inset_idx, arr_i);
+                            switch (reordered_extrusions[arr_i].extrusion->inset_idx) {
+                                case 0: // external perimeter
+                                    if (outer == -1)
+                                        outer = arr_i;
+                                    break;
+                                case 1: // first internal wall
+                                    if (first_internal==-1 && arr_i>outer && outer!=-1){
+                                        first_internal = arr_i;
+                                    }
+                                    break;
+                                case 2: // second internal wall
+                                    if (second_internal == -1 && arr_i > first_internal && outer!=-1){
+                                        second_internal = arr_i;
+                                    }
+                                    break;
+                            }
+                            if(outer >-1 && first_internal>-1 && reordered_extrusions[arr_i].extrusion->inset_idx == 0){  // found a new external perimeter after we've found at least a first internal perimeter to re-order.
+                                                                                                                          // This means we entered a new island.
+                                arr_i=arr_i-1; //step back one perimeter
+                                max_internal = arr_i; // new maximum internal perimeter is now this as we have found a new external perimeter, hence a new island.
+                                break; // exit the for loop
                             }
                         }
+                    
+                        // printf("Layer ID %d, Outer index %d, inner index %d, second inner index %d, maximum internal perimeter %d \n",layer_id,outer,first_internal,second_internal, max_internal);
+                        if (outer > -1 && first_internal > -1 && second_internal > -1) { // found all three perimeters to re-order? If not the perimeters will be processed outside in.
+                            std::vector<PerimeterGeneratorArachneExtrusion> inner_outer_extrusions; // temporary array to hold extrusions for reordering
+                            inner_outer_extrusions.resize(max_internal - position + 1); // reserve array containing the number of perimeters before a new island. Variables are array indexes hence need to add +1 to convert to position allocations
+                            // printf("Allocated array size %d, max_internal index %d, start position index %d \n",max_internal-position+1,max_internal,position);
                         
-                        for (arr_j = position; arr_j < second_internal; ++arr_j){ // go outside in and map the remaining perimeters (external and first internal wall(s)) using the outside in wall order
-                            // printf("Outside in loop: Mapped perimeter index %d to array position %d\n", arr_j, current_perimeter+1);
-                            inner_outer_extrusions[++current_perimeter] = reordered_extrusions[arr_j];
+                            for (arr_j = max_internal; arr_j >=position; --arr_j){ // go inside out towards the external perimeter (perimeters in reverse order) and store all internal perimeters until the first one identified with inset index 2
+                                if(arr_j >= second_internal){
+                                    //printf("Inside out loop: Mapped perimeter index %d to array position %d\n", arr_j, max_internal-arr_j);
+                                    inner_outer_extrusions[max_internal-arr_j] = reordered_extrusions[arr_j];
+                                    current_perimeter++; 
+                                }
+                            }
+                        
+                            for (arr_j = position; arr_j < second_internal; ++arr_j){ // go outside in and map the remaining perimeters (external and first internal wall(s)) using the outside in wall order
+                                // printf("Outside in loop: Mapped perimeter index %d to array position %d\n", arr_j, current_perimeter+1);
+                                inner_outer_extrusions[++current_perimeter] = reordered_extrusions[arr_j];
+                            }
+                        
+                            for(arr_j = position; arr_j <= max_internal; ++arr_j) // replace perimeter array with the new re-ordered array
+                                ordered_extrusions[arr_j] = inner_outer_extrusions[arr_j-position];
                         }
-                        
-                        for(arr_j = position; arr_j <= max_internal; ++arr_j) // replace perimeter array with the new re-ordered array
-                            ordered_extrusions[arr_j] = inner_outer_extrusions[arr_j-position];
+                        // go to the next perimeter from the current position to continue scanning for external walls in the same island
+                        position = arr_i + 1;
                     }
-                    // go to the next perimeter from the current position to continue scanning for external walls in the same island
-                    position = arr_i + 1;
                 }
             }
-        }
         
-        bool steep_overhang_contour = false;
-        bool steep_overhang_hole    = false;
-        if (!config->overhang_reverse) {
-            // Skip steep overhang detection no reverse is specified
-            steep_overhang_contour = true;
-            steep_overhang_hole    = true;
-        }
-        if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
-            if (config->overhang_reverse) {
-                reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
-                                    this->config->overhang_reverse_internal_only);
+            bool steep_overhang_contour = false;
+            bool steep_overhang_hole    = false;
+            if (!config->overhang_reverse) {
+                // Skip steep overhang detection no reverse is specified
+                steep_overhang_contour = true;
+                steep_overhang_hole    = true;
+            }
+            if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
+                if (config->overhang_reverse) {
+                    reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
+                                        this->config->overhang_reverse_internal_only);
+                }
+                defer_unsupported_loops(*this, extrusion_coll);
+                result.loops     = std::move(extrusion_coll);
+                result.has_loops = true;
             }
-            defer_unsupported_loops(*this, extrusion_coll);
-            this->loops->append(extrusion_coll);
-        }
 
-        const coord_t spacing = (perimeters.size() == 1) ? ext_perimeter_spacing2 : perimeter_spacing;
+            const coord_t spacing = (perimeters.size() == 1) ? ext_perimeter_spacing2 : perimeter_spacing;
 
-        if (offset_ex(infill_contour, -float(spacing / 2.)).empty())
-            infill_contour.clear(); // Infill region is too small, so let's filter it out.
+            if (offset_ex(infill_contour, -float(spacing / 2.)).empty())
+                infill_contour.clear(); // Infill region is too small, so let's filter it out.
 
-        // create one more offset to be used as boundary for fill
-        // we offset by half the perimeter spacing (to get to the actual infill boundary)
-        // and then we offset back and forth by half the infill spacing to only consider the
-        // non-collapsing regions
-        coord_t inset =
-            (loop_number < 0) ? 0 :
-            (loop_number == 0) ?
-            // one loop
-            ext_perimeter_spacing :
-            // two or more loops?
-            perimeter_spacing;
-        coord_t top_inset = inset;
+            // create one more offset to be used as boundary for fill
+            // we offset by half the perimeter spacing (to get to the actual infill boundary)
+            // and then we offset back and forth by half the infill spacing to only consider the
+            // non-collapsing regions
+            coord_t inset =
+                (loop_number < 0) ? 0 :
+                (loop_number == 0) ?
+                // one loop
+                ext_perimeter_spacing :
+                // two or more loops?
+                perimeter_spacing;
+            coord_t top_inset = inset;
         
-        top_inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
-        if(is_topmost_layer || is_bottom_layer)
-            inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
-        else
-            inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+            top_inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+            if(is_topmost_layer || is_bottom_layer)
+                inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+            else
+                inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
         
-        // simplify infill contours according to resolution
-        Polygons pp;
-        for (ExPolygon& ex : infill_contour)
-            ex.simplify_p(m_scaled_resolution, &pp);
-        ExPolygons not_filled_exp = union_ex(pp);
-        // collapse too narrow infill areas
-        const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
+            // simplify infill contours according to resolution
+            Polygons pp;
+            for (ExPolygon& ex : infill_contour)
+                ex.simplify_p(m_scaled_resolution, &pp);
+            ExPolygons not_filled_exp = union_ex(pp);
+            // collapse too narrow infill areas
+            const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
 
-        ExPolygons infill_exp = offset2_ex(
-            not_filled_exp,
-            float(-min_perimeter_infill_spacing / 2.),
-            float(inset + min_perimeter_infill_spacing / 2.));
-        // append infill areas to fill_surfaces
-        if (!top_expolygons.empty()) {
-            infill_exp = union_ex(infill_exp, offset_ex(top_expolygons, double(top_inset)));
-        }
-        this->fill_surfaces->append(infill_exp, stInternal);
-
-        apply_extra_perimeters(infill_exp);
-
-        // BBS: get the no-overlap infill expolygons
-        {
-            ExPolygons polyWithoutOverlap;
-            polyWithoutOverlap = offset2_ex(
+            ExPolygons infill_exp = offset2_ex(
                 not_filled_exp,
                 float(-min_perimeter_infill_spacing / 2.),
-                float(+min_perimeter_infill_spacing / 2.));
-            if (!top_expolygons.empty())
-                polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
-            this->fill_no_overlap->insert(this->fill_no_overlap->end(), polyWithoutOverlap.begin(), polyWithoutOverlap.end());
-        }
+                float(inset + min_perimeter_infill_spacing / 2.));
+            // append infill areas to fill_surfaces
+            if (!top_expolygons.empty()) {
+                infill_exp = union_ex(infill_exp, offset_ex(top_expolygons, double(top_inset)));
+            }
+            result.infill = std::move(infill_exp);
+
+            // BBS: get the no-overlap infill expolygons
+            {
+                ExPolygons polyWithoutOverlap;
+                polyWithoutOverlap = offset2_ex(
+                    not_filled_exp,
+                    float(-min_perimeter_infill_spacing / 2.),
+                    float(+min_perimeter_infill_spacing / 2.));
+                if (!top_expolygons.empty())
+                    polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
+                result.no_overlap = std::move(polyWithoutOverlap);
+            }
+      }
+    });
+    for (ArachneSurfaceResult &result : results) {
+        if (result.has_loops)
+            // Moved, not copied: append(const ExtrusionEntity &) clones the whole wall tree of the island.
+            this->loops->append(std::move(result.loops));
+        this->fill_surfaces->append(result.infill, stInternal);
+        apply_extra_perimeters(result.infill);
+        append(*this->fill_no_overlap, std::move(result.no_overlap));
     }
 }
 

src/libslic3r/Polygon.hpp

@@ -34,7 +34,7 @@ public:
     explicit Polygon(const Points &points) : MultiPoint(points) {}
 	Polygon(std::initializer_list<Point> points) : MultiPoint(points) {}
     Polygon(const Polygon &other) : MultiPoint(other.points) {}
-    Polygon(Polygon &&other) : MultiPoint(std::move(other.points)) {}
+    Polygon(Polygon &&other) noexcept : MultiPoint(std::move(other.points)) {}
 	static Polygon new_scale(const std::vector<Vec2d> &points) { 
         Polygon pgn;
         pgn.points.reserve(points.size());
@@ -43,7 +43,7 @@ public:
 		return pgn;
 	}
     Polygon& operator=(const Polygon &other) { points = other.points; return *this; }
-    Polygon& operator=(Polygon &&other) { points = std::move(other.points); return *this; }
+    Polygon& operator=(Polygon &&other) noexcept { points = std::move(other.points); return *this; }
 
     Point& operator[](Points::size_type idx) { return this->points[idx]; }
     const Point& operator[](Points::size_type idx) const { return this->points[idx]; }

src/libslic3r/Polyline.hpp

@@ -26,7 +26,7 @@ class Polyline : public MultiPoint {
 public:
     Polyline() {};
     Polyline(const Polyline& other) : MultiPoint(other.points), fitting_result(other.fitting_result) {}
-    Polyline(Polyline &&other) : MultiPoint(std::move(other.points)), fitting_result(std::move(other.fitting_result))  {}
+    Polyline(Polyline &&other) noexcept : MultiPoint(std::move(other.points)), fitting_result(std::move(other.fitting_result))  {}
     Polyline(std::initializer_list<Point> list) : MultiPoint(list) { 
         fitting_result.clear();
     }
@@ -47,7 +47,7 @@ public:
         fitting_result = other.fitting_result;
         return *this;
     }
-    Polyline& operator=(Polyline&& other) {
+    Polyline& operator=(Polyline&& other) noexcept {
         points = std::move(other.points);
         fitting_result = std::move(other.fitting_result);
         return *this;

src/libslic3r/PrintObject.cpp

@@ -47,6 +47,7 @@
 #include <cstdlib>
 #include <cstdint>
 #include <float.h>
+#include <array>
 #include <functional>
 #include <ios>
 #include <iomanip>
@@ -72,6 +73,7 @@
 #include <boost/log/trivial.hpp>
 
 #include <tbb/parallel_for.h>
+#include <tbb/parallel_invoke.h>
 #include <tbb/spin_mutex.h>
 #include <tbb/concurrent_unordered_set.h>
 
@@ -1695,7 +1697,9 @@ void PrintObject::detect_surfaces_type()
     bool interface_shells = ! spiral_mode && m_config.interface_shells.value;
     size_t num_layers     = spiral_mode ? std::min(size_t(this->printing_region(0).config().bottom_shell_layers), m_layers.size()) : m_layers.size();
 
-    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
+    // others, so the regions run next to each other instead of one after another, each still over all layers.
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [&](size_t region_id) {
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " in parallel - start";
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
         for (Layer *layer : m_layers)
@@ -1753,7 +1757,7 @@ void PrintObject::detect_surfaces_type()
                     if (upper_layer) {
                         ExPolygons upper_slices = interface_shells ?
                             diff_ex(layerm_slices_surfaces, upper_layer->m_regions[region_id]->slices.surfaces, ApplySafetyOffset::Yes) :
-                            diff_ex(layerm_slices_surfaces, upper_layer->lslices, ApplySafetyOffset::Yes);
+                            diff_ex_by_piece(layerm_slices_surfaces, to_polygons(upper_layer->lslices), ApplySafetyOffset::Yes);
                         surfaces_append(top, opening_ex(upper_slices, offset), stTop);
                     } else {
                         // if no upper layer, all surfaces of this one are solid
@@ -1779,7 +1783,7 @@ void PrintObject::detect_surfaces_type()
                         surfaces_append(
                             bottom,
                             opening_ex(
-                                diff_ex(layerm_slices_surfaces, lower_layer->lslices, ApplySafetyOffset::Yes),
+                                diff_ex_by_piece(layerm_slices_surfaces, to_polygons(lower_layer->lslices), ApplySafetyOffset::Yes),
                                 offset),
                             surface_type_bottom_other);
                         // if user requested internal shells, we need to identify surfaces
@@ -1810,34 +1814,44 @@ void PrintObject::detect_surfaces_type()
                     // and top surfaces; let's do an intersection to discover them and consider them
                     // as bottom surfaces (to allow for bridge detection)
                     if (! top.empty() && ! bottom.empty()) {
-                        const auto cracks = intersection_ex(top, bottom);
+                        const auto cracks = intersection_ex_by_piece(to_expolygons(top), to_polygons(bottom));
                         if (!cracks.empty()) {
                             if (lower_layer) { // Only detect small cracks for non-first layer, because first layer should always be bottom
                                 const float small_crack_threshold = -layerm->flow(frExternalPerimeter).scaled_width() * 1.5;
                                 
+                                // Only the bottom surfaces near a crack can take part: one that contains it must contain its box,
+                                // and one whose box misses the grown crack is left unchanged by removing it. A layer cut through
+                                // a fine relief has thousands of both, which made this loop quadratic.
                                 for (const auto& crack : cracks) {
                                     if (offset_ex(crack, small_crack_threshold).empty()) {
                                         // For small cracks, if it's part of a large bottom surface, then it should be added to bottom as well
-                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, small_crack_threshold](const Surface& s) {
+                                        const BoundingBox crack_bbox = get_extents(crack);
+                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, &crack_bbox, small_crack_threshold](const Surface& s) {
                                                 const auto& se = s.expolygon;
-                                                return diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
+                                                return get_extents(se).inflated(SCALED_EPSILON).contains(crack_bbox)
+                                                    && diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
                                                     && se.area() > crack.area() * 2
                                                     && !offset_ex(diff_ex(se, crack), small_crack_threshold).empty();
                                         })) continue;
 
                                         // Crack too small, leave it as part of the top surface, remove it from bottom surfaces
+                                        const ExPolygons  grown_crack = offset_ex(crack, -small_crack_threshold);
+                                        const BoundingBox grown_bbox  = get_extents(grown_crack);
                                         Surfaces bot_tmp;
                                         for (auto& b : bottom) {
-                                            surfaces_append(bot_tmp, diff_ex(b.expolygon, offset_ex(crack, -small_crack_threshold)), b.surface_type);
+                                            if (get_extents(b.expolygon).overlap(grown_bbox))
+                                                surfaces_append(bot_tmp, diff_ex(b.expolygon, grown_crack), b.surface_type);
+                                            else
+                                                bot_tmp.emplace_back(std::move(b));
                                         }
                                         bottom = std::move(bot_tmp);
                                     }
                                 }
                             }
 
-                            Polygons top_polygons = to_polygons(std::move(top));
+                            ExPolygons top_expolygons = to_expolygons(std::move(top));
                             top.clear();
-                            surfaces_append(top, diff_ex(top_polygons, bottom), stTop);
+                            surfaces_append(top, diff_ex_by_piece(top_expolygons, to_polygons(bottom)), stTop);
                         }
                     }
 
@@ -1928,7 +1942,7 @@ void PrintObject::detect_surfaces_type()
                     {
                         Polygons topbottom = to_polygons(top);
                         polygons_append(topbottom, to_polygons(bottom));
-                        surfaces_append(surfaces_out, diff_ex(surfaces_prev_expolys, topbottom), stInternal);
+                        surfaces_append(surfaces_out, diff_ex_by_piece(surfaces_prev_expolys, topbottom), stInternal);
                     }
 
                     surfaces_append(surfaces_out, std::move(top));
@@ -2105,29 +2119,31 @@ void PrintObject::detect_surfaces_type()
                 }
             }
             );
-            // ==============================================================================================================
-            // === ORCA: Interim workaround - for now the new stInternalAfterExternalBridge surfaace is re-classified  ==============
-            // === back to a bottom bridge. As a starting point, this improves bridging reliability as it extrudes ==========
-            // === two external bridge layers. However, TODO: Implement a new surface type throughout the codebase ==========
-            // ==============================================================================================================
-            for (size_t region_id = 0; region_id < this->num_printing_regions(); ++region_id) {
-                tbb::parallel_for( tbb::blocked_range<size_t>(0, m_layers.size()), [this, region_id](const tbb::blocked_range<size_t> &range) {
-                    for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++idx_layer) {
-                        Surfaces &surfs = m_layers[idx_layer]->m_regions[region_id]->slices.surfaces;
-                        for (Surface &s : surfs) {
-                            if (s.surface_type == stInternalAfterExternalBridge) {
-                                s.surface_type = stBottomBridge;
-                            }
-                        }
-                    }
-                }
-              );
-            }
         }
         // ==============================================================================================================
         // === ORCA: End of second external bridge layer changes  =======================================================
         // ==============================================================================================================
         
+    }); // for each this->print->region_count
+
+    // ==============================================================================================================
+    // === ORCA: Interim workaround - for now the new stInternalAfterExternalBridge surfaace is re-classified  ==============
+    // === back to a bottom bridge. As a starting point, this improves bridging reliability as it extrudes ==========
+    // === two external bridge layers. However, TODO: Implement a new surface type throughout the codebase ==========
+    // ==============================================================================================================
+    // Once all the regions have their second bridge layer, and before their slices are trimmed into fill surfaces below.
+    if ((this->config().enable_extra_bridge_layer.value == eblApplyToAll) || (this->config().enable_extra_bridge_layer.value == eblExternalBridgeOnly)) {
+        tbb::parallel_for(tbb::blocked_range<size_t>(0, m_layers.size()), [this](const tbb::blocked_range<size_t> &range) {
+            for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++idx_layer)
+                for (LayerRegion *layerm : m_layers[idx_layer]->regions())
+                    for (Surface &s : layerm->slices.surfaces)
+                        if (s.surface_type == stInternalAfterExternalBridge)
+                            s.surface_type = stBottomBridge;
+        });
+        m_print->throw_if_canceled();
+    }
+
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [&](size_t region_id) {
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " - clipping in parallel - start";
         // Fill in layerm->fill_surfaces by trimming the layerm->slices by the cummulative layerm->fill_surfaces.
         tbb::parallel_for(
@@ -2144,7 +2160,7 @@ void PrintObject::detect_surfaces_type()
             });
         m_print->throw_if_canceled();
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " - clipping in parallel - end";
-    } // for each this->print->region_count
+    });
 
     // Mark the object to have the region slices classified (typed, which also means they are split based on whether they are supported, bridging, top layers etc.)
     m_typed_slices = true;
@@ -2211,8 +2227,10 @@ void PrintObject::process_external_surfaces()
 	    BOOST_LOG_TRIVIAL(debug) << "Collecting surfaces covered with extrusions in parallel - end";
 	}
 
-	for (size_t region_id = 0; region_id < this->num_printing_regions(); ++region_id) {
-        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - start";
+    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - start";
+    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
+    // others, so the regions run next to each other instead of one after another, each still over all layers.
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [this, &surfaces_covered](size_t region_id) {
         tbb::parallel_for(
             tbb::blocked_range<size_t>(0, m_layers.size()),
             [this, &surfaces_covered, region_id](const tbb::blocked_range<size_t>& range) {
@@ -2227,9 +2245,9 @@ void PrintObject::process_external_surfaces()
                 }
             }
         );
-        m_print->throw_if_canceled();
-        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - end";
-    }
+    });
+    m_print->throw_if_canceled();
+    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - end";
 }
 
 void PrintObject::discover_vertical_shells()
@@ -2268,10 +2286,10 @@ void PrintObject::discover_vertical_shells()
             // The "ensure vertical wall thickness" feature is not applicable to any of the regions. Quit.
             return;
         BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells in parallel - start : cache top / bottom";
-        //FIXME Improve the heuristics for a grain size.
-        size_t grain_size = std::max(num_layers / 16, size_t(1));
+        // One layer per task: on a layer cut through a fine relief the unions below take far longer than elsewhere, and a
+        // few such layers next to each other must not end up in one task.
         tbb::parallel_for(
-            tbb::blocked_range<size_t>(0, num_layers, grain_size),
+            tbb::blocked_range<size_t>(0, num_layers, 1),
             [this, &cache_top_botom_regions](const tbb::blocked_range<size_t>& range) {
                 const std::initializer_list<SurfaceType> surfaces_bottom { stBottom, stBottomBridge };
                 const size_t num_regions = this->num_printing_regions();
@@ -2279,67 +2297,198 @@ void PrintObject::discover_vertical_shells()
                     m_print->throw_if_canceled();
                     const Layer                      &layer = *m_layers[idx_layer];
                     DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[idx_layer];
-                    // Simulate single set of perimeters over all merged regions.
-                    float                             perimeter_offset = 0.f;
-                    float                             perimeter_min_spacing = FLT_MAX;
+                    const auto top_bottom_expansion = [&layer](size_t region_id) {
+                        return float(layer.m_regions[region_id]->flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
+                    };
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     static size_t debug_idx = 0;
                     ++ debug_idx;
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
-                        LayerRegion &layerm               = *layer.m_regions[region_id];
-                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
-                        // Top surfaces.
-                        append(cache.top_surfaces, offset(layerm.slices.filter_by_type(stTop), top_bottom_expansion));
-//                        append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
-                        // Bottom surfaces.
-                        append(cache.bottom_surfaces, offset(layerm.slices.filter_by_types(surfaces_bottom), top_bottom_expansion));
-//                        append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
-                        // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
-                        // First find the maxium number of perimeters per region slice.
-                        unsigned int perimeters = 0;
-                        for (Surface &s : layerm.slices.surfaces)
-                            perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
-                        perimeters += layerm.region().config().wall_loops.value;
-                        // Then calculate the infill offset.
-                        if (perimeters > 0) {
-                            Flow extflow = layerm.flow(frExternalPerimeter);
-                            Flow flow    = layerm.flow(frPerimeter);
-                            perimeter_offset = std::max(perimeter_offset,
-                                0.5f * float(extflow.scaled_width() + extflow.scaled_spacing()) + (float(perimeters) - 1.f) * flow.scaled_spacing());
-                            perimeter_min_spacing = std::min(perimeter_min_spacing, float(std::min(extflow.scaled_spacing(), flow.scaled_spacing())));
-                        }
-                        polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
-                    }
-                    // Save some computing time by reducing the number of polygons.
-                    cache.top_surfaces    = union_(cache.top_surfaces);
-                    cache.bottom_surfaces = union_(cache.bottom_surfaces);
-                    // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
-                    if (perimeter_offset > 0.) {
-                        // The layer.lslices are forced to merge by expanding them first.
-                        polygons_append(cache.holes, offset2(layer.lslices, 0.3f * perimeter_min_spacing, - perimeter_offset - 0.3f * perimeter_min_spacing));
+                    // The top surfaces, the bottom surfaces and the holes are independent of each other.
+                    tbb::parallel_invoke(
+                        [&]() {
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
+                                append(cache.top_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_type(stTop), top_bottom_expansion(region_id)));
+//                              append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
+                            // Save some computing time by reducing the number of polygons.
+                            cache.top_surfaces = union_(cache.top_surfaces);
+                        },
+                        [&]() {
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
+                                append(cache.bottom_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_types(surfaces_bottom), top_bottom_expansion(region_id)));
+//                              append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                            cache.bottom_surfaces = union_(cache.bottom_surfaces);
+                        },
+                        [&]() {
+                            // Simulate single set of perimeters over all merged regions.
+                            float perimeter_offset      = 0.f;
+                            float perimeter_min_spacing = FLT_MAX;
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
+                                const LayerRegion &layerm = *layer.m_regions[region_id];
+                                // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
+                                // First find the maxium number of perimeters per region slice.
+                                unsigned int perimeters = 0;
+                                for (const Surface &s : layerm.slices.surfaces)
+                                    perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
+                                perimeters += layerm.region().config().wall_loops.value;
+                                // Then calculate the infill offset.
+                                if (perimeters > 0) {
+                                    Flow extflow = layerm.flow(frExternalPerimeter);
+                                    Flow flow    = layerm.flow(frPerimeter);
+                                    perimeter_offset = std::max(perimeter_offset,
+                                        0.5f * float(extflow.scaled_width() + extflow.scaled_spacing()) + (float(perimeters) - 1.f) * flow.scaled_spacing());
+                                    perimeter_min_spacing = std::min(perimeter_min_spacing, float(std::min(extflow.scaled_spacing(), flow.scaled_spacing())));
+                                }
+                                polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
+                            }
+                            // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
+                            if (perimeter_offset > 0.) {
+                                // The layer.lslices are forced to merge by expanding them first.
+                                polygons_append(cache.holes, offset2(layer.lslices, 0.3f * perimeter_min_spacing, - perimeter_offset - 0.3f * perimeter_min_spacing));
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
-                        {
-                            Slic3r::SVG svg(debug_out_path("discover_vertical_shells-extra-holes-%d.svg", debug_idx), get_extents(layer.lslices));
-                            svg.draw(layer.lslices, "blue");
-                            svg.draw(union_ex(cache.holes), "red");
-                            svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
-                            svg.Close();
-                        }
+                                {
+                                    Slic3r::SVG svg(debug_out_path("discover_vertical_shells-extra-holes-%d.svg", debug_idx), get_extents(layer.lslices));
+                                    svg.draw(layer.lslices, "blue");
+                                    svg.draw(union_ex(cache.holes), "red");
+                                    svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
+                                    svg.Close();
+                                }
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    }
-                    cache.holes = union_(cache.holes);
+                            }
+                            cache.holes = union_(cache.holes);
+                        });
                 }
             });
         m_print->throw_if_canceled();
         BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells in parallel - end : cache top / bottom";
     }
 
-    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+    // With one top/bottom cache for all regions, the shell and hole accumulation in the loop below depends on nothing
+    // region-specific but the shell settings and the external perimeter spacing, so a region sharing them with an earlier
+    // one reuses its result instead of repeating it: that accumulation is a union over several layers of top/bottom
+    // surfaces, and a multi-material print has a region per filament.
+    using AccumulationKey = std::array<double, 5>;
+    struct ShellAccumulation
+    {
+        AccumulationKey key;
+        Polygons        shell;
+        Polygons        holes;
+    };
+    const auto accumulation_key = [](const PrintRegionConfig &region_config, const LayerRegion *layerm) {
+        return AccumulationKey{ double(region_config.top_shell_layers.value), region_config.top_shell_thickness.value,
+                                double(region_config.bottom_shell_layers.value), region_config.bottom_shell_thickness.value,
+                                double(layerm->flow(frExternalPerimeter).scaled_spacing()) };
+    };
+    const auto accumulate_shell = [this, &cache_top_botom_regions](size_t idx_layer, const PrintRegionConfig &region_config,
+                                                                   const LayerRegion *layerm, Polygons &shell, Polygons &holes) {
+        const Layer *layer = m_layers[idx_layer];
+    			        polygons_append(holes, cache_top_botom_regions[idx_layer].holes);
+                        auto combine_holes = [&holes](const Polygons &holes2) {
+                            if (holes.empty() || holes2.empty())
+                                holes.clear();
+                            else
+                                holes = intersection(holes, holes2);
+                        };
+                        auto combine_shells = [&shell](const Polygons &shells2) {
+                            if (shell.empty())
+                                shell = std::move(shells2);
+                            else if (! shells2.empty()) {
+                                polygons_append(shell, shells2);
+                                // Running the union_ using the Clipper library piece by piece is cheaper
+                                // than running the union_ all at once.
+                                shell = union_(shell);
+                            }
+                        };
+                        static constexpr const bool one_more_layer_below_top_bottom_surfaces = false;
+    			        if (int n_top_layers = region_config.top_shell_layers.value; n_top_layers > 0) {
+                            // Gather top regions projected to this layer.
+                            coordf_t print_z = layer->print_z;
+                            int i = int(idx_layer) + 1;
+                            int itop = int(idx_layer) + n_top_layers;
+                            bool at_least_one_top_projected = false;
+    	                    for (; i < int(cache_top_botom_regions.size()) &&
+    	                         (i < itop || m_layers[i]->print_z - print_z < region_config.top_shell_thickness - EPSILON);
+    	                        ++ i) {
+                                at_least_one_top_projected = true;
+    	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
+                                combine_holes(cache.holes);
+                                combine_shells(cache.top_surfaces);
+    	                    }
+                            if (!at_least_one_top_projected && i < int(cache_top_botom_regions.size())) {
+                                // Lets consider this a special case - with only 1 top solid and minimal shell thickness settings, the
+                                // boundaries of solid layers are not anchored over/under perimeters, so lets fix it by adding at least one
+                                // perimeter width of area
+                                Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].top_surfaces,
+                                                                           layerm->flow(frExternalPerimeter).scaled_spacing()),
+                                                                    to_polygons(m_layers[i]->lslices));
+                                combine_shells(anchor_area);
+                            }
+
+                            if (one_more_layer_below_top_bottom_surfaces)
+                                if (i < int(cache_top_botom_regions.size()) &&
+                                    (i <= itop || m_layers[i]->bottom_z() - print_z < region_config.top_shell_thickness - EPSILON))
+                                    combine_holes(cache_top_botom_regions[i].holes);
+    	                }
+    	                if (int n_bottom_layers = region_config.bottom_shell_layers.value; n_bottom_layers > 0) {
+                            // Gather bottom regions projected to this layer.
+                            coordf_t bottom_z = layer->bottom_z();
+                            int i = int(idx_layer) - 1;
+                            int ibottom = int(idx_layer) - n_bottom_layers;
+                            bool at_least_one_bottom_projected = false;
+    	                    for (; i >= 0 &&
+    	                         (i > ibottom || bottom_z - m_layers[i]->bottom_z() < region_config.bottom_shell_thickness - EPSILON);
+    	                        -- i) {
+                                    at_least_one_bottom_projected = true;
+    	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
+    							combine_holes(cache.holes);
+                                combine_shells(cache.bottom_surfaces);
+    	                    }
+
+                            if (!at_least_one_bottom_projected && i >= 0) {
+                                Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].bottom_surfaces,
+                                                                           layerm->flow(frExternalPerimeter).scaled_spacing()),
+                                                                    to_polygons(m_layers[i]->lslices));
+                                combine_shells(anchor_area);
+                            }
+
+                            if (one_more_layer_below_top_bottom_surfaces)
+                                if (i >= 0 &&
+                                    (i > ibottom || bottom_z - m_layers[i]->print_z < region_config.bottom_shell_thickness - EPSILON))
+                                    combine_holes(cache_top_botom_regions[i].holes);
+    	                }
+    };
+    std::vector<std::vector<ShellAccumulation>> shell_accumulations(top_bottom_surfaces_all_regions ? num_layers : 0);
+    if (! shell_accumulations.empty()) {
+        // Every (layer, key) pair is accumulated once, before the regions, so that nothing in the loop below is shared
+        // between them and they can run next to each other.
+        std::vector<std::array<size_t, 3>> todo; // layer, its slot, a region holding the key
+        for (size_t idx_layer = 0; idx_layer < num_layers; ++ idx_layer) {
+            std::vector<ShellAccumulation> &accumulations = shell_accumulations[idx_layer];
+            for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+                if (this->printing_region(region_id).config().ensure_vertical_shell_thickness.value != evstAll)
+                    continue;
+                const LayerRegion    *layerm = m_layers[idx_layer]->m_regions[region_id];
+                const AccumulationKey key    = accumulation_key(layerm->region().config(), layerm);
+                if (std::none_of(accumulations.begin(), accumulations.end(), [&key](const ShellAccumulation &a) { return a.key == key; })) {
+                    todo.push_back({ idx_layer, accumulations.size(), region_id });
+                    accumulations.push_back({ key, {}, {} });
+                }
+            }
+        }
+        tbb::parallel_for(size_t(0), todo.size(), [this, &todo, &shell_accumulations, &accumulate_shell](size_t i) {
+            m_print->throw_if_canceled();
+            const LayerRegion *layerm = m_layers[todo[i][0]]->m_regions[todo[i][2]];
+            ShellAccumulation &out    = shell_accumulations[todo[i][0]][todo[i][1]];
+            accumulate_shell(todo[i][0], layerm->region().config(), layerm, out.shell, out.holes);
+        });
+        m_print->throw_if_canceled();
+    }
+
+    const auto process_region = [&](size_t region_id) {
         const PrintRegion &region = this->printing_region(region_id);
         if (region.config().ensure_vertical_shell_thickness.value != evstAll )
             // This region will be handled by discover_horizontal_shells().
-            continue;
+            return;
 
         //FIXME Improve the heuristics for a grain size.
         size_t grain_size = std::max(num_layers / 16, size_t(1));
@@ -2379,7 +2528,7 @@ void PrintObject::discover_vertical_shells()
         grain_size = 1;
         tbb::parallel_for(
             tbb::blocked_range<size_t>(0, num_layers, grain_size),
-            [this, region_id, &cache_top_botom_regions]
+            [this, region_id, &shell_accumulations, &accumulation_key, &accumulate_shell]
             (const tbb::blocked_range<size_t>& range) {
                 // printf("discover_vertical_shells from %d to %d\n", range.begin(), range.end());
                 for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
@@ -2429,80 +2578,19 @@ void PrintObject::discover_vertical_shells()
                         }
                     }
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-			        polygons_append(holes, cache_top_botom_regions[idx_layer].holes);
-                    auto combine_holes = [&holes](const Polygons &holes2) {
-                        if (holes.empty() || holes2.empty())
-                            holes.clear();
-                        else
-                            holes = intersection(holes, holes2);
-                    };
-                    auto combine_shells = [&shell](const Polygons &shells2) {
-                        if (shell.empty())
-                            shell = std::move(shells2);
-                        else if (! shells2.empty()) {
-                            polygons_append(shell, shells2);
-                            // Running the union_ using the Clipper library piece by piece is cheaper
-                            // than running the union_ all at once.
-                            shell = union_(shell);
-                        }
-                    };
-                    static constexpr const bool one_more_layer_below_top_bottom_surfaces = false;
-			        if (int n_top_layers = region_config.top_shell_layers.value; n_top_layers > 0) {
-                        // Gather top regions projected to this layer.
-                        coordf_t print_z = layer->print_z;
-                        int i = int(idx_layer) + 1;
-                        int itop = int(idx_layer) + n_top_layers;
-                        bool at_least_one_top_projected = false;
-	                    for (; i < int(cache_top_botom_regions.size()) &&
-	                         (i < itop || m_layers[i]->print_z - print_z < region_config.top_shell_thickness - EPSILON);
-	                        ++ i) {
-                            at_least_one_top_projected = true;
-	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
-                            combine_holes(cache.holes);
-                            combine_shells(cache.top_surfaces);
-	                    }
-                        if (!at_least_one_top_projected && i < int(cache_top_botom_regions.size())) {
-                            // Lets consider this a special case - with only 1 top solid and minimal shell thickness settings, the
-                            // boundaries of solid layers are not anchored over/under perimeters, so lets fix it by adding at least one
-                            // perimeter width of area
-                            Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].top_surfaces,
-                                                                       layerm->flow(frExternalPerimeter).scaled_spacing()),
-                                                                to_polygons(m_layers[i]->lslices));
-                            combine_shells(anchor_area);
-                        }
-
-                        if (one_more_layer_below_top_bottom_surfaces)
-                            if (i < int(cache_top_botom_regions.size()) &&
-                                (i <= itop || m_layers[i]->bottom_z() - print_z < region_config.top_shell_thickness - EPSILON))
-                                combine_holes(cache_top_botom_regions[i].holes);
-	                }
-	                if (int n_bottom_layers = region_config.bottom_shell_layers.value; n_bottom_layers > 0) {
-                        // Gather bottom regions projected to this layer.
-                        coordf_t bottom_z = layer->bottom_z();
-                        int i = int(idx_layer) - 1;
-                        int ibottom = int(idx_layer) - n_bottom_layers;
-                        bool at_least_one_bottom_projected = false;
-	                    for (; i >= 0 &&
-	                         (i > ibottom || bottom_z - m_layers[i]->bottom_z() < region_config.bottom_shell_thickness - EPSILON);
-	                        -- i) {
-                                at_least_one_bottom_projected = true;
-	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
-							combine_holes(cache.holes);
-                            combine_shells(cache.bottom_surfaces);
-	                    }
-
-                        if (!at_least_one_bottom_projected && i >= 0) {
-                            Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].bottom_surfaces,
-                                                                       layerm->flow(frExternalPerimeter).scaled_spacing()),
-                                                                to_polygons(m_layers[i]->lslices));
-                            combine_shells(anchor_area);
-                        }
-
-                        if (one_more_layer_below_top_bottom_surfaces)
-                            if (i >= 0 &&
-                                (i > ibottom || bottom_z - m_layers[i]->print_z < region_config.bottom_shell_thickness - EPSILON))
-                                combine_holes(cache_top_botom_regions[i].holes);
-	                }
+                    const AccumulationKey key = accumulation_key(region_config, layerm);
+                    const ShellAccumulation *reused = shell_accumulations.empty() ? nullptr :
+                        [&]() -> const ShellAccumulation * {
+                            for (const ShellAccumulation &a : shell_accumulations[idx_layer])
+                                if (a.key == key)
+                                    return &a;
+                            return nullptr;
+                        }();
+                    if (reused != nullptr) {
+                        shell = reused->shell;
+                        holes = reused->holes;
+                    } else
+                        accumulate_shell(idx_layer, region_config, layerm, shell, holes);
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
         				Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-%d.svg", debug_idx), get_extents(shell));
@@ -2596,11 +2684,8 @@ void PrintObject::discover_vertical_shells()
                         Polygons object_volume;
                         Polygons internal_volume;
                         {
-                            Polygons shrinked_bottom_slice = idx_layer > 0 ? to_polygons(m_layers[idx_layer - 1]->lslices) : Polygons{};
-                            Polygons shrinked_upper_slice  = (idx_layer + 1) < m_layers.size() ?
-                                                                 to_polygons(m_layers[idx_layer + 1]->lslices) :
-                                                                 Polygons{};
-                            object_volume = intersection(shrinked_bottom_slice, shrinked_upper_slice);
+                            if (idx_layer > 0 && idx_layer + 1 < m_layers.size())
+                                object_volume = to_polygons(intersection_ex_by_piece(m_layers[idx_layer - 1]->lslices, to_polygons(m_layers[idx_layer + 1]->lslices)));
                             internal_volume = closing(polygonsInternal, SCALED_EPSILON);
                         }
 
@@ -2611,15 +2696,34 @@ void PrintObject::discover_vertical_shells()
                         //      the in-model condition is there due to small sloping surfaces, e.g. top of the hull of the benchy
                         //   2. the area does not fully cover an internal polygon
                         //         This is there mainly for a very thin parts, where the solid layers would be missing if the part area is quite small
+                        // Both tests below compare a small piece against the whole layer. Done literally, that is
+                        // quadratic in the number of pieces, which is what a layer split up by colour painting has,
+                        // so each is restricted to the part of the layer near the piece with an identical result:
+                        // object_volume is clipped to the piece's box, and only the internal polygons whose box meets
+                        // the expanded piece take part in the count, since the others pass through the difference
+                        // unchanged and add the same number to both sides of it.
+                        std::vector<BoundingBox> internal_bboxes;
+                        internal_bboxes.reserve(internal_volume.size());
+                        for (const Polygon &poly : internal_volume)
+                            internal_bboxes.emplace_back(get_extents(poly));
                         regularized_shell.erase(std::remove_if(regularized_shell.begin(), regularized_shell.end(),
-                                                               [&internal_volume, &min_perimeter_infill_spacing,
+                                                               [&internal_volume, &internal_bboxes, &min_perimeter_infill_spacing,
                                                                 &object_volume](const ExPolygon &p) {
-                                                                   return (p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
-                                                                           (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
-                                                                            diff(to_polygons(p), object_volume).empty())) &&
-                                                                          diff(internal_volume,
-                                                                               expand(to_polygons(p), min_perimeter_infill_spacing))
-                                                                                  .size() >= internal_volume.size();
+                                                                   const bool small = p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
+                                                                                      (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
+                                                                                       diff(to_polygons(p),
+                                                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                                                                object_volume, get_extents(p).inflated(SCALED_EPSILON)))
+                                                                                           .empty());
+                                                                   if (!small)
+                                                                       return false;
+                                                                   const Polygons    expanded = expand(to_polygons(p), min_perimeter_infill_spacing);
+                                                                   const BoundingBox bbox     = get_extents(expanded);
+                                                                   Polygons          nearby;
+                                                                   for (size_t i = 0; i < internal_volume.size(); ++i)
+                                                                       if (internal_bboxes[i].overlap(bbox))
+                                                                           nearby.emplace_back(internal_volume[i]);
+                                                                   return diff(nearby, expanded).size() >= nearby.size();
                                                                }),
                                                 regularized_shell.end());
                     }
@@ -2641,8 +2745,9 @@ void PrintObject::discover_vertical_shells()
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
 
                     // Trim the internal & internalvoid by the shell.
-                    Slic3r::ExPolygons new_internal = diff_ex(layerm->fill_surfaces.filter_by_type(stInternal), regularized_shell);
-                    Slic3r::ExPolygons new_internal_void = diff_ex(layerm->fill_surfaces.filter_by_type(stInternalVoid), regularized_shell);
+                    const Polygons     regularized_shell_polygons = to_polygons(regularized_shell);
+                    Slic3r::ExPolygons new_internal = diff_ex_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternal)), regularized_shell_polygons);
+                    Slic3r::ExPolygons new_internal_void = diff_ex_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternalVoid)), regularized_shell_polygons);
 
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
@@ -2669,7 +2774,15 @@ void PrintObject::discover_vertical_shells()
 			layerm->export_region_fill_surfaces_to_svg_debug("3_discover_vertical_shells-final");
 		}
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-    } // for each region
+    }; // for each region
+    if (top_bottom_surfaces_all_regions)
+        // Nothing is shared between the regions, and a layer cut through a fine relief takes far longer than the others,
+        // so they run next to each other instead of one after another.
+        tbb::parallel_for(size_t(0), this->num_printing_regions(), process_region);
+    else
+        // Here every region fills the one top/bottom cache with its own surfaces first.
+        for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id)
+            process_region(region_id);
 } // void PrintObject::discover_vertical_shells()
 
 // #define DEBUG_BRIDGE_OVER_INFILL
@@ -3190,6 +3303,16 @@ void PrintObject::bridge_over_infill()
                 vertical_lines[i].b = Point{x, y_max};
             }
 
+            // The vertical lines only span the bridged area's x range, so anchors entirely outside it can never be
+            // hit. Leaving them out gives the same intersections without building a tree over the whole layer's
+            // boundary for every bridge.
+            const coord_t scan_x_min = bb_x.min.x();
+            const coord_t scan_x_max = bb_x.min.x() + coord_t(n_vlines) * scan_spacing;
+            anchors.erase(std::remove_if(anchors.begin(), anchors.end(),
+                                         [scan_x_min, scan_x_max](const Line &l) {
+                                             return std::max(l.a.x(), l.b.x()) < scan_x_min || std::min(l.a.x(), l.b.x()) > scan_x_max;
+                                         }),
+                          anchors.end());
             auto anchors_and_walls_tree = AABBTreeLines::LinesDistancer<Line>{std::move(anchors)};
             auto bridged_area_tree      = AABBTreeLines::LinesDistancer<Line>{to_lines(bridged_area)};
 
@@ -3434,28 +3557,62 @@ void PrintObject::bridge_over_infill()
 
                 std::vector<CandidateSurface> expanded_surfaces;
                 expanded_surfaces.reserve(surfaces_by_layer[lidx].size());
+                // The expanded fill boundary depends only on the bridging flow, and total_fill_area is not
+                // modified below, so build it once per spacing rather than once per candidate. A layer split
+                // into many candidates (e.g. by colour painting) otherwise repeats a layer-wide offset for each.
+                std::map<coord_t, Polylines> boundary_by_spacing;
+                // expansion_area is a clean, non-overlapping set, so uniting it with a bridge or cutting a bridge
+                // out of it only changes the polygons near that bridge. The rest are passed through untouched
+                // instead of being fed to Clipper with the whole layer again for every candidate.
+                // Not `near`/`far`: the Windows headers still define those as macros, and they expand to
+                // nothing, which turns the declaration below into an empty one.
+                const auto split_near = [](const Polygons &polys, const BoundingBox &bbox, Polygons &rest) {
+                    Polygons nearby;
+                    for (const Polygon &p : polys)
+                        (get_extents(p).overlap(bbox) ? nearby : rest).emplace_back(p);
+                    return nearby;
+                };
                 for (const CandidateSurface &candidate : surfaces_by_layer[lidx]) {
                     const auto &region_config = candidate.region->region().config();
                     const bool turning_pattern = region_config.sparse_infill_pattern == ipHilbertCurve ||
                                                  region_config.sparse_infill_pattern == ipOctagramSpiral;
                     const Flow &flow              = candidate.region->bridging_flow(frSolidInfill, true);
                     Polygons    area_to_be_bridge = expand(candidate.new_polys, flow.scaled_spacing());
-                    area_to_be_bridge             = intersection(area_to_be_bridge, deep_infill_area);
+                    // deep_infill_area and internal_unsupported_area cover the whole layer; only their part under
+                    // this candidate can change the results, so they are clipped to its box first.
+                    if (!area_to_be_bridge.empty())
+                        area_to_be_bridge = intersection(area_to_be_bridge,
+                                                         ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                             deep_infill_area, get_extents(area_to_be_bridge).inflated(SCALED_EPSILON)));
 
                     area_to_be_bridge.erase(std::remove_if(area_to_be_bridge.begin(), area_to_be_bridge.end(),
-                                                           [internal_unsupported_area](const Polygon &p) {
-                                                               return intersection({p}, internal_unsupported_area).empty();
+                                                           [&internal_unsupported_area](const Polygon &p) {
+                                                               return intersection({p}, ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                                                            internal_unsupported_area,
+                                                                                            get_extents(p).inflated(SCALED_EPSILON)))
+                                                                   .empty();
                                                            }),
                                             area_to_be_bridge.end());
 
-                    Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
-
                     if (area_to_be_bridge.empty())
                         continue;
 
-                    Polylines boundary_plines = to_polylines(expand(total_fill_area, 1.3 * flow.scaled_spacing()));
+                    Polygons       limiting_area;
+                    const Polygons near_expansion = split_near(expansion_area, get_extents(area_to_be_bridge).inflated(SCALED_EPSILON),
+                                                               limiting_area);
+                    const size_t   num_far        = limiting_area.size();
+                    append(limiting_area, union_(area_to_be_bridge, near_expansion));
+
+                    auto boundary_it = boundary_by_spacing.find(flow.scaled_spacing());
+                    if (boundary_it == boundary_by_spacing.end())
+                        boundary_it = boundary_by_spacing
+                                          .emplace(flow.scaled_spacing(), to_polylines(expand(total_fill_area, 1.3 * flow.scaled_spacing())))
+                                          .first;
+                    Polylines boundary_plines = boundary_it->second;
                     {
-                        Polylines limiting_plines = to_polylines(expand(limiting_area, 0.3*flow.spacing()));
+                        // The sub-unit offset (spacing is in mm) still re-unites touching polygons by the bridge, which the anchors depend on.
+                        Polylines limiting_plines = to_polylines(Polygons(limiting_area.begin(), limiting_area.begin() + num_far));
+                        append(limiting_plines, to_polylines(expand(Polygons(limiting_area.begin() + num_far, limiting_area.end()), 0.3 * flow.spacing())));
                         boundary_plines.insert(boundary_plines.end(), limiting_plines.begin(), limiting_plines.end());
                     }
 
@@ -3529,9 +3686,12 @@ void PrintObject::bridge_over_infill()
                     // Check collision with other expanded surfaces
                     {
                         bool     reconstruct       = false;
-                        Polygons tmp_expanded_area = expand(bridging_area, 3.0 * flow.scaled_spacing());
+                        Polygons          tmp_expanded_area = expand(bridging_area, 3.0 * flow.scaled_spacing());
+                        const BoundingBox tmp_expanded_bbox = get_extents(tmp_expanded_area);
                         for (const CandidateSurface &s : expanded_surfaces) {
-                            if (!intersection(s.new_polys, tmp_expanded_area).empty()) {
+                            // Surfaces whose boxes miss each other cannot intersect, which is most pairs on a busy layer.
+                            if (get_extents(s.new_polys).overlap(tmp_expanded_bbox) &&
+                                !intersection(s.new_polys, tmp_expanded_area).empty()) {
                                 bridging_angle = s.bridge_angle;
                                 reconstruct    = true;
                                 break;
@@ -3555,10 +3715,20 @@ void PrintObject::bridge_over_infill()
                         bridging_area = union_(bridging_area, construct_anchored_polygon(bridging_area, to_lines(boundary_plines), flow,
                                                                                        bridging_angle, scan_spacing, true));
                     }
-                    bridging_area          = intersection(bridging_area, limiting_area);
-                    bridging_area          = intersection(bridging_area, total_fill_area);
-                    bridging_area          = diff(bridging_area, total_top_area);
-                    expansion_area         = diff(expansion_area, bridging_area);
+                    // Each of these meets one bridge with the whole layer, so the layer side is first cut down to the
+                    // bridge's box (and expansion_area split as above); the result is the same.
+                    if (!bridging_area.empty()) {
+                        const BoundingBox bridging_bbox = get_extents(bridging_area).inflated(SCALED_EPSILON);
+                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(limiting_area, bridging_bbox));
+                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_fill_area, bridging_bbox));
+                        bridging_area = diff(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_top_area, bridging_bbox));
+                    }
+                    if (!bridging_area.empty()) {
+                        Polygons       kept;
+                        const Polygons cut = split_near(expansion_area, get_extents(bridging_area).inflated(SCALED_EPSILON), kept);
+                        append(kept, diff(cut, bridging_area));
+                        expansion_area = std::move(kept);
+                    }
 
 #ifdef DEBUG_BRIDGE_OVER_INFILL
                     debug_draw(std::to_string(lidx) + "_" + std::to_string(cluster_idx) + "_" + std::to_string(job_idx) + "_" + "_expanded_bridging" +  std::to_string(r),

src/libslic3r/SLA/bicubic.h

@@ -0,0 +1,186 @@
+#ifndef BICUBIC_HPP
+#define BICUBIC_HPP
+
+#include <algorithm>
+#include <vector>
+#include <cmath>
+
+#include <Eigen/Dense>
+
+namespace Slic3r {
+
+namespace BicubicInternal {
+	// Linear kernel, to be able to test cubic methods with hat kernels.
+	template<typename T>
+	struct LinearKernel
+	{
+		typedef T	FloatType;
+
+		static T a00() { return T(0.); }
+		static T a01() { return T(0.); }
+		static T a02() { return T(0.); }
+		static T a03() { return T(0.); }
+		static T a10() { return T(1.); }
+		static T a11() { return T(-1.); }
+		static T a12() { return T(0.); }
+		static T a13() { return T(0.); }
+		static T a20() { return T(0.); }
+		static T a21() { return T(1.); }
+		static T a22() { return T(0.); }
+		static T a23() { return T(0.); }
+		static T a30() { return T(0.); }
+		static T a31() { return T(0.); }
+		static T a32() { return T(0.); }
+		static T a33() { return T(0.); }
+	};
+
+	// Interpolation kernel aka Catmul-Rom aka Keyes kernel.
+	template<typename T>
+	struct CubicCatmulRomKernel
+	{
+		typedef T	FloatType;
+
+		static T a00() { return     0;     }
+		static T a01() { return (T)-0.5;   }
+		static T a02() { return (T) 1.;    }
+		static T a03() { return (T)-0.5;   }
+		static T a10() { return (T) 1.;    }
+		static T a11() { return     0;     }
+		static T a12() { return (T)-5./2.; }
+		static T a13() { return (T) 3./2.; }
+		static T a20() { return     0;     }
+		static T a21() { return (T) 0.5;   }
+		static T a22() { return (T) 2.;    }
+		static T a23() { return (T)-3./2.; }
+		static T a30() { return     0;     }
+		static T a31() { return     0;     }
+		static T a32() { return (T)-0.5;   }
+		static T a33() { return (T) 0.5;   }
+	};
+
+	// B-spline kernel
+	template<typename T>
+	struct CubicBSplineKernel
+	{
+		typedef T	FloatType;
+
+		static T a00() { return (T)  1./6.; }
+		static T a01() { return (T) -3./6.; }
+		static T a02() { return (T)  3./6.; }
+		static T a03() { return (T) -1./6.; }
+		static T a10() { return (T)  4./6.; }
+		static T a11() { return      0;     }
+		static T a12() { return (T) -6./6.; }
+		static T a13() { return (T)  3./6.; }
+		static T a20() { return (T)  1./6.; }
+		static T a21() { return (T)  3./6.; }
+		static T a22() { return (T)  3./6.; }
+		static T a23() { return (T)- 3./6.; }
+		static T a30() { return      0;     }
+		static T a31() { return      0;     }
+		static T a32() { return      0;     }
+		static T a33() { return (T)  1./6.; }
+	};
+
+	template<class T>
+	inline T clamp(T a, T lower, T upper)
+	{
+		return (a < lower) ? lower : 
+	   		   (a > upper) ? upper : a;
+	}
+}
+
+template<typename KERNEL>
+struct CubicKernel
+{
+	typedef typename KERNEL					KernelInternal;
+	typedef typename KERNEL::FloatType		FloatType;
+
+	static FloatType kernel(FloatType x)
+	{
+		x = fabs(x);
+		if (x >= (FloatType)2.)
+			return 0.0f;
+		if (x <= (FloatType)1.) {
+			FloatType x2 = x * x;
+			FloatType x3 = x2 * x;
+			return KERNEL::a10() + KERNEL::a11() * x + KERNEL::a12() * x2 + KERNEL::a13() * x3;
+		}
+		assert(x > (FloatType)1. && x < (FloatType)2.);
+		x -= (FloatType)1.;
+		FloatType x2 = x * x;
+		FloatType x3 = x2 * x;
+		return KERNEL::a00() + KERNEL::a01() * x + KERNEL::a02() * x2 + KERNEL::a03() * x3;
+	}
+
+	static FloatType interpolate(FloatType f0, FloatType f1, FloatType f2, FloatType f3, FloatType x)
+	{
+		const FloatType  x2 = x*x;
+		const FloatType  x3 = x*x*x;
+		return f0*(KERNEL::a00() + KERNEL::a01() * x + KERNEL::a02() * x2 + KERNEL::a03() * x3) +
+			   f1*(KERNEL::a10() + KERNEL::a11() * x + KERNEL::a12() * x2 + KERNEL::a13() * x3) +
+			   f2*(KERNEL::a20() + KERNEL::a21() * x + KERNEL::a22() * x2 + KERNEL::a23() * x3) + 
+			   f3*(KERNEL::a30() + KERNEL::a31() * x + KERNEL::a32() * x2 + KERNEL::a33() * x3);
+	}
+};
+
+// Linear splines
+typedef CubicKernel<BicubicInternal::LinearKernel<float>>					LinearKernelf;
+typedef CubicKernel<BicubicInternal::LinearKernel<double>>					LinearKerneld;
+// Catmul-Rom splines
+typedef CubicKernel<BicubicInternal::CubicCatmulRomKernel<float>>			CubicCatmulRomKernelf;
+typedef CubicKernel<BicubicInternal::CubicCatmulRomKernel<double>>			CubicCatmulRomKerneld;
+typedef CubicKernel<BicubicInternal::CubicCatmulRomKernel<float>>			CubicInterpolationKernelf;
+typedef CubicKernel<BicubicInternal::CubicCatmulRomKernel<double>>			CubicInterpolationKerneld;
+// Cubic B-splines
+typedef CubicKernel<BicubicInternal::CubicBSplineKernel<float>>				CubicBSplineKernelf;
+typedef CubicKernel<BicubicInternal::CubicBSplineKernel<double>>			CubicBSplineKerneld;
+
+template<typename KERNEL, typename Derived>
+static float cubic_interpolate(const Eigen::ArrayBase<Derived> &F, const typename KERNEL::FloatType pt, const typename KERNEL::FloatType dx)
+{
+	typedef typename KERNEL::FloatType T;
+	const int w  = int(F.size());
+	const int ix = (int)floor(pt);
+	const T   s  = pt - (T)ix;
+
+	if (ix > 1 && ix + 2 < w) {
+		// Inside the fully interpolated region.
+		return KERNEL::interpolate(F[ix - 1], F[ix], F[ix + 1], F[ix + 2], s);
+	}
+	// Transition region. Extend with a constant function.
+	auto f = [&F, w](x) { return F[BicubicInternal::clamp(x, 0, w - 1)]; }
+	return KERNEL::interpolate(f(ix - 1), f(ix), f(ix + 1), f(ix + 2), s);
+}
+
+template<typename KERNEL, typename Derived>
+static float bicubic_interpolate(const Eigen::MatrixBase<Derived> &F, const Eigen::Matrix<typename KERNEL::FloatType, 2, 1, Eigen::DontAlign> &pt, const typename KERNEL::FloatType dx)
+{
+	typedef typename KERNEL::FloatType T;
+	const int w  = F.cols();
+	const int h  = F.rows();
+	const int ix = (int)floor(pt[0]);
+	const int iy = (int)floor(pt[1]);
+	const T   s  = pt[0] - (T)ix;
+	const T   t  = pt[1] - (T)iy;
+
+	if (ix > 1 && ix + 2 < w && iy > 1 && iy + 2 < h) {
+		// Inside the fully interpolated region.
+		return KERNEL::interpolate(
+			KERNEL::interpolate(F(ix-1,iy-1),F(ix  ,iy-1),F(ix+1,iy-1),F(ix+2,iy-1),s),
+			KERNEL::interpolate(F(ix-1,iy  ),F(ix  ,iy  ),F(ix+1,iy  ),F(ix+2,iy  ),s),
+			KERNEL::interpolate(F(ix-1,iy+1),F(ix  ,iy+1),F(ix+1,iy+1),F(ix+2,iy+1),s),
+			KERNEL::interpolate(F(ix-1,iy+2),F(ix  ,iy+2),F(ix+1,iy+2),F(ix+2,iy+2),s),t);
+	}
+	// Transition region. Extend with a constant function.
+	auto f = [&f, w, h](int x, int y) { return F(BicubicInternal::clamp(x,0,w-1),BicubicInternal::clamp(y,0,h-1)); }
+	return KERNEL::interpolate(
+		KERNEL::interpolate(f(ix-1,iy-1),f(ix  ,iy-1),f(ix+1,iy-1),f(ix+2,iy-1),s),
+		KERNEL::interpolate(f(ix-1,iy  ),f(ix  ,iy  ),f(ix+1,iy  ),f(ix+2,iy  ),s),
+		KERNEL::interpolate(f(ix-1,iy+1),f(ix  ,iy+1),f(ix+1,iy+1),f(ix+2,iy+1),s),
+		KERNEL::interpolate(f(ix-1,iy+2),f(ix  ,iy+2),f(ix+1,iy+2),f(ix+2,iy+2),s),t);
+}
+
+} // namespace Slic3r
+
+#endif /* BICUBIC_HPP */

src/libslic3r/Support/SupportMaterial.cpp

@@ -955,9 +955,9 @@ public:
                 ::fread(&y, sizeof(coord_t), 1, file);
                 poly.points.emplace_back(Point(x * scale, y * scale));
             }
+            printf("Polygon %d, area: %lf\n", i, area(poly.points));
             if (which == -1 || which == i)
                 m_support_polygons_deserialized.emplace_back(std::move(poly));
-            printf("Polygon %d, area: %lf\n", i, area(poly.points));
         }
         ::fread(&n_polygons, 4, 1, file);
         m_trimming_polygons_deserialized.reserve(n_polygons);

src/libslic3r/Support/TreeSupport.cpp

@@ -891,11 +891,41 @@ void TreeSupport::detect_overhangs(bool check_support_necessity/* = false*/)
                 if (is_auto(stype) && config_detect_sharp_tails)
                 {
                     // BBS detect sharp tail
+                    // Each island is tested only against the lower islands whose box meets its own; overlaps() tries
+                    // every pair, which is quadratic in the island counts of the two layers.
+                    std::vector<BoundingBox> lower_bboxes;
+                    lower_bboxes.reserve(lower_polys.size());
+                    for (const ExPolygon &lower : lower_polys)
+                        lower_bboxes.emplace_back(get_extents(lower));
                     for (const ExPolygon& expoly : curr_polys) {
                         bool  is_sharp_tail = false;
                         // 1. nothing below
                         // this is a sharp tail region if it's floating and non-ignorable
-                        if (!overlaps(offset_ex(expoly, 0.1 * extrusion_width_scaled), lower_polys)) {
+                        const ExPolygons  expanded = offset_ex(expoly, 0.1 * extrusion_width_scaled);
+                        const BoundingBox bbox     = get_extents(expanded);
+                        ExPolygons        lower_nearby;
+                        for (size_t i = 0; i < lower_polys.size(); ++i)
+                            if (lower_bboxes[i].overlap(bbox))
+                                lower_nearby.emplace_back(lower_polys[i]);
+                        // As overlaps(expanded, lower_nearby), with each lower island cut to the island's box first:
+                        // below a fine relief the lower layer is a few islands with thousands of holes, and the whole
+                        // of that boundary would otherwise be intersected once per island above.
+                        const auto overlaps_nearby = [&]() {
+                            for (const ExPolygon &a : expanded) {
+                                if (a.empty())
+                                    continue;
+                                const BoundingBox a_bbox = get_extents(a);
+                                for (const ExPolygon &b : lower_nearby) {
+                                    if (b.empty() || !get_extents(b).overlap(a_bbox))
+                                        continue;
+                                    const Polygons b_near = ClipperUtils::clip_clipper_polygons_with_subject_bbox(b, a_bbox.inflated(SCALED_EPSILON));
+                                    if (!intersection_pl(to_polylines(b_near), a).empty() || b.contains(a.contour.points.front()))
+                                        return true;
+                                }
+                            }
+                            return false;
+                        };
+                        if (!overlaps_nearby()) {
                             is_sharp_tail = !offset_ex(expoly, -0.1 * extrusion_width_scaled).empty();
                         }
 

src/libslic3r/Surface.hpp

@@ -69,7 +69,7 @@ public:
             thickness(other.thickness), thickness_layers(other.thickness_layers),
             bridge_angle(other.bridge_angle), extra_perimeters(other.extra_perimeters)
         {};
-    Surface(Surface &&rhs)
+    Surface(Surface &&rhs) noexcept
         : surface_type(rhs.surface_type), expolygon(std::move(rhs.expolygon)),
             thickness(rhs.thickness), thickness_layers(rhs.thickness_layers),
             bridge_angle(rhs.bridge_angle), extra_perimeters(rhs.extra_perimeters)
@@ -95,7 +95,7 @@ public:
         return *this;
     }
 
-    Surface& operator=(Surface &&rhs)
+    Surface& operator=(Surface &&rhs) noexcept
     {
         surface_type     = rhs.surface_type;
         expolygon        = std::move(rhs.expolygon);

src/libslic3r/libslic3r.h

@@ -168,10 +168,10 @@ inline void append(std::vector<T, Alloc> &dest, std::vector<T, Alloc> &&src)
 {
     if (dest.empty())
         dest = std::move(src);
-    else {
-        dest.reserve(dest.size() + src.size());
-        std::move(std::begin(src), std::end(src), std::back_inserter(dest));
-    }
+    else
+        // insert() grows the capacity geometrically; reserving exactly the new size reallocated on every call, which
+        // made appending piece by piece quadratic.
+        dest.insert(dest.end(), std::make_move_iterator(src.begin()), std::make_move_iterator(src.end()));
     src.clear();
     src.shrink_to_fit();
 }

src/slic3r/CMakeLists.txt

@@ -178,12 +178,16 @@ set(SLIC3R_GUI_SOURCES
     GUI/Gizmos/GLGizmoCut.hpp
     GUI/Gizmos/GLGizmoEmboss.cpp
     GUI/Gizmos/GLGizmoEmboss.hpp
+    #GUI/Gizmos/GLGizmoFaceDetector.cpp
+    #GUI/Gizmos/GLGizmoFaceDetector.hpp
     GUI/Gizmos/GLGizmoFdmSupports.cpp
     GUI/Gizmos/GLGizmoFdmSupports.hpp
     GUI/Gizmos/GLGizmoFlatten.cpp
     GUI/Gizmos/GLGizmoFlatten.hpp
     GUI/Gizmos/GLGizmoFuzzySkin.cpp
     GUI/Gizmos/GLGizmoFuzzySkin.hpp
+    #GUI/Gizmos/GLGizmoHollow.cpp
+    #GUI/Gizmos/GLGizmoHollow.hpp
     GUI/Gizmos/GLGizmoMeasure.cpp
     GUI/Gizmos/GLGizmoMeasure.hpp
     GUI/Gizmos/GLGizmoMeshBoolean.cpp
@@ -204,6 +208,8 @@ set(SLIC3R_GUI_SOURCES
     GUI/Gizmos/GLGizmoSeam.hpp
     GUI/Gizmos/GLGizmoSimplify.cpp
     GUI/Gizmos/GLGizmoSimplify.hpp
+    #GUI/Gizmos/GLGizmoSlaSupports.cpp
+    #GUI/Gizmos/GLGizmoSlaSupports.hpp
     GUI/Gizmos/GLGizmosManager.cpp
     GUI/Gizmos/GLGizmosManager.hpp
     GUI/Gizmos/GLGizmoSVG.cpp
@@ -212,6 +218,8 @@ set(SLIC3R_GUI_SOURCES
     GUI/Gizmos/GLGizmoTextureDisplacement.hpp
     GUI/Gizmos/GLGizmoUtils.cpp
     GUI/Gizmos/GLGizmoUtils.hpp
+    #GUI/Gizmos/GLGizmoText.cpp
+    #GUI/Gizmos/GLGizmoText.hpp
     GUI/GLCanvas3D.cpp
     GUI/GLCanvas3D.hpp
     GUI/GLModel.cpp
@@ -800,6 +808,7 @@ set(SLIC3R_GUI_SOURCES
     Utils/PrintHost.hpp
     Utils/Process.cpp
     Utils/Process.hpp
+    Utils/ProfileDescription.hpp
     Utils/Profile.hpp
     Utils/RaycastManager.cpp
     Utils/RaycastManager.hpp

src/slic3r/GUI/Gizmos/GLGizmoAdvancedCut.hpp

@@ -0,0 +1,222 @@
+#ifndef slic3r_GLGizmoAdvancedCut_hpp_
+#define slic3r_GLGizmoAdvancedCut_hpp_
+
+#include "GLGizmoBase.hpp"
+#include "GLGizmoRotate.hpp"
+#include "libslic3r/Model.hpp"
+
+namespace Slic3r {
+enum class CutConnectorType : int;
+class ModelVolume;
+struct CutConnectorAttributes;
+
+namespace GUI {
+enum class SLAGizmoEventType : unsigned char;
+
+class GLGizmoAdvancedCut : public GLGizmoRotate3D
+{
+struct Rotate_data {
+    double  angle;
+    Axis    ax;
+
+    Rotate_data(double an, Axis a)
+        : angle(an), ax(a)
+    {
+    }
+};
+private:
+    static const double Offset;
+    static const double Margin;
+    static const ColorRGBA GrabberColor;
+    static const ColorRGBA GrabberHoverColor;
+
+    mutable double m_movement;
+    mutable double m_height;  // height of cut plane to heatbed
+    mutable double m_height_delta;  // height of cut plane to heatbed
+    double m_start_movement;
+    double m_start_height;
+
+    Vec3d m_rotation;
+    //Vec3d m_current_base_rotation;
+    std::vector<Rotate_data> m_rotate_cmds;
+
+    Vec3d m_buffered_rotation;
+    double m_buffered_movement;
+    double m_buffered_height;
+
+    Vec3d m_drag_pos;
+
+    bool m_keep_upper;
+    bool m_keep_lower;
+    bool m_cut_to_parts;
+    bool m_place_on_cut_upper{true};
+    bool m_place_on_cut_lower{false};
+    bool m_rotate_upper{false};
+    bool m_rotate_lower{false};
+    GLModel m_plane;
+    GLModel m_grabber_connection;
+    GLModel m_cut_line;
+
+    bool m_do_segment;
+    double m_segment_smoothing_alpha;
+    int m_segment_number;
+
+    std::array<Vec3d, 4> m_cut_plane_points;
+
+    mutable Grabber m_move_grabber;
+
+    unsigned int m_last_active_id;
+
+    bool m_connectors_editing{false};
+    bool m_show_shortcuts{false};
+
+    std::vector<std::pair<wxString, wxString>> m_shortcuts;
+    double m_label_width{150.0};
+    double m_control_width{ 200.0 };
+    double m_editing_window_width;
+
+    CutConnectorType         m_connector_type;
+    size_t                   m_connector_style;
+    size_t                   m_connector_shape_id;
+
+    float m_connector_depth_ratio{3.f};
+    float m_connector_depth_ratio_tolerance{0.1f};
+
+    float m_connector_size{2.5f};
+    float m_connector_size_tolerance{0.f};
+
+    TriangleMesh m_connector_mesh;
+    bool         m_has_invalid_connector{false};
+
+    // remember the connectors which is selected
+    mutable std::vector<bool> m_selected;
+    int                       m_selected_count{0};
+
+    Vec3d m_cut_plane_center{Vec3d::Zero()};
+    Vec3d m_cut_plane_normal{Vec3d::UnitZ()};
+
+    Vec3d m_cut_line_begin{Vec3d::Zero()};
+    Vec3d m_cut_line_end{Vec3d::Zero()};
+
+    Transform3d m_rotate_matrix{Transform3d::Identity()};
+
+    std::map<CutConnectorAttributes, GLModel> m_shapes;
+
+    struct InvalidConnectorsStatistics
+    {
+        unsigned int outside_cut_contour;
+        unsigned int outside_bb;
+        bool         is_overlap;
+
+        void invalidate()
+        {
+            outside_cut_contour = 0;
+            outside_bb          = 0;
+            is_overlap          = false;
+        }
+    } m_info_stats;
+
+    //GLSelectionRectangle m_selection_rectangle;
+
+public:
+    GLGizmoAdvancedCut(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id);
+
+    bool gizmo_event(SLAGizmoEventType action, const Vec2d &mouse_position, bool shift_down, bool alt_down, bool control_down);
+    bool on_key(wxKeyEvent &evt);
+
+    double get_movement() const { return m_movement; }
+    void set_movement(double movement) const;
+    void finish_rotation();
+    std::string get_tooltip() const override;
+
+    BoundingBoxf3 bounding_box() const;
+    //BoundingBoxf3 transformed_bounding_box(const Vec3d &plane_center, bool revert_move = false) const;
+
+    bool is_looking_forward() const;
+
+    bool unproject_on_cut_plane(const Vec2d &mouse_pos, Vec3d &pos, Vec3d &pos_world);
+    
+    virtual bool apply_clipping_plane() { return m_connectors_editing; }
+
+    void data_changed(bool is_serializing) override;
+
+protected:
+    bool on_init() override;
+    void on_load(cereal::BinaryInputArchive &ar) override;
+    void on_save(cereal::BinaryOutputArchive &ar) const override;
+    std::string on_get_name() const override;
+    void on_set_state() override;
+    bool on_is_activable() const override;
+    CommonGizmosDataID on_get_requirements() const override;
+    void on_start_dragging() override;
+    void on_stop_dragging() override;
+    void on_dragging(const UpdateData& data) override;
+    void on_render() override;
+    virtual void on_render_input_window(float x, float y, float bottom_limit);
+
+    void show_tooltip_information(float x, float y);
+
+private:
+    void perform_cut(const Selection& selection);
+    bool can_perform_cut() const;
+    void apply_connectors_in_model(ModelObject *mo, bool &create_dowels_as_separate_object);
+
+    bool is_selection_changed(bool alt_down, bool shift_down);
+    void select_connector(int idx, bool select);
+
+    double calc_projection(const Linef3& mouse_ray) const;
+    Vec3d calc_plane_normal(const std::array<Vec3d, 4>& plane_points) const;
+    Vec3d calc_plane_center(const std::array<Vec3d, 4>& plane_points) const;
+    Vec3d get_plane_normal() const;
+    Vec3d get_plane_center() const;
+    void update_plane_points();
+    std::array<Vec3d, 4> get_plane_points() const;
+    std::array<Vec3d, 4> get_plane_points_world_coord() const;
+    void reset_cut_plane();
+    void reset_all();
+
+    // update the connectors position so that the connectors are on the cut plane
+    void put_connectors_on_cut_plane(const Vec3d &cp_normal, double cp_offset);
+    void update_clipper();
+    // on render
+    void render_cut_plane_and_grabbers();
+    void render_connectors();
+    void render_clipper_cut();
+    void render_cut_line();
+    void render_connector_model(GLModel &model, const ColorRGBA& color, Transform3d model_matrix, bool for_picking = false);
+
+    void clear_selection();
+    void init_connector_shapes();
+    void set_connectors_editing(bool connectors_editing);
+    void reset_connectors();
+    void update_connector_shape();
+    void apply_selected_connectors(std::function<void(size_t idx)> apply_fn);
+    void select_all_connectors();
+    void unselect_all_connectors();
+    void validate_connector_settings();
+    bool add_connector(CutConnectors &connectors, const Vec2d &mouse_position);
+    bool delete_selected_connectors();
+    bool is_outside_of_cut_contour(size_t idx, const CutConnectors &connectors, const Vec3d cur_pos);
+    bool is_conflict_for_connector(size_t idx, const CutConnectors &connectors, const Vec3d cur_pos);
+    void check_conflict_for_all_connectors();
+
+    // render input window
+    void render_cut_plane_input_window(float x, float y, float bottom_limit);
+    void init_connectors_input_window_data();
+    void render_connectors_input_window(float x, float y, float bottom_limit);
+    void render_input_window_warning() const;
+    bool render_reset_button(const std::string &label_id, const std::string &tooltip) const;
+    bool render_connect_type_radio_button(CutConnectorType type);
+
+    bool render_combo(const std::string &label, const std::vector<std::string> &lines, size_t &selection_idx);
+    bool render_slider_double_input(const std::string &label, float &value_in, float &tolerance_in);
+
+    bool cut_line_processing() const;
+    void discard_cut_line_processing();
+    bool process_cut_line(SLAGizmoEventType action, const Vec2d &mouse_position);
+};
+
+} // namespace GUI
+} // namespace Slic3r
+
+#endif // slic3r_GLGizmoAdvancedCut_hpp_

src/slic3r/GUI/Gizmos/GLGizmoFaceDetector.cpp

@@ -0,0 +1,133 @@
+#include "GLGizmoFaceDetector.hpp"
+
+#include "libslic3r/Model.hpp"
+#include "libslic3r/SLA/IndexedMesh.hpp"
+#include "libslic3r/FaceDetector.hpp"
+
+#include "slic3r/GUI/GLCanvas3D.hpp"
+#include "slic3r/GUI/GUI_App.hpp"
+#include "slic3r/GUI/ImGuiWrapper.hpp"
+#include "slic3r/GUI/Plater.hpp"
+
+#include <glad/gl.h>
+
+#ifdef __WINDOWS__
+#include <windows.h>
+#include <stdio.h>
+#endif
+
+namespace Slic3r {
+
+namespace GUI {
+
+bool GLGizmoFaceDetector::on_init()
+{
+    return true;
+}
+
+std::string GLGizmoFaceDetector::on_get_name() const
+{
+    return (_L("Face recognition") + " [P]").ToUTF8().data();
+}
+
+void GLGizmoFaceDetector::on_render()
+{
+    if (model.is_initialized()) {
+        model.set_color({0.f, 0.f, 1.f, 0.4f});
+        model.render();
+    }
+}
+
+void GLGizmoFaceDetector::on_render_input_window(float x, float y, float bottom_limit)
+{
+#if 0
+    if (!m_c->selection_info() || !m_c->selection_info()->model_object())
+        return;
+
+    const float approx_height = m_imgui->scaled(14.0f);
+    y = std::min(y, bottom_limit - approx_height);
+    //BBS: GUI refactor: move gizmo to the right
+#if BBS_TOOLBAR_ON_TOP
+    m_imgui->set_next_window_pos(x, y, ImGuiCond_Always, 0.5f, 0.0f);
+#else
+    m_imgui->set_next_window_pos(x, y, ImGuiCond_Always, 1.0f, 0.0f);
+#endif
+
+    ImGuiWrapper::push_toolbar_style();
+    m_imgui->begin(on_get_name(), ImGuiWindowFlags_NoMove | ImGuiWindowFlags_AlwaysAutoResize | ImGuiWindowFlags_NoCollapse);
+
+    ImGui::PushItemWidth(m_imgui->get_style_scaling() * 150);
+    ImGui::InputDouble("Sample interval", &m_sample_interval, 0.0f, 0.0f, "%.2f");
+
+    bool btn_clicked = m_imgui->button(_L("Perform Recognition"));
+    if (btn_clicked) {
+        perform_recognition(m_parent.get_selection());
+    }
+
+    m_imgui->end();
+    ImGuiWrapper::pop_toolbar_style();
+#endif
+}
+
+void GLGizmoFaceDetector::on_set_state()
+{
+    if (get_state() == On) {
+        model.reset();
+        display_exterior_face();
+    }
+}
+
+bool GLGizmoFaceDetector::on_is_activable() const
+{
+    const Selection& selection = m_parent.get_selection();
+    return selection.is_single_full_instance() && !selection.is_wipe_tower();
+}
+
+void GLGizmoFaceDetector::perform_recognition(const Selection& selection)
+{
+    ModelObject* mo = m_c->selection_info()->model_object();
+    //FaceDetector face_detector(mo, m_sample_interval);
+
+    //face_detector.detect_exterior_face();
+}
+
+void GLGizmoFaceDetector::display_exterior_face()
+{
+    int cnt = 0;
+    model.reset();
+
+    GLModel::Geometry init_data;
+    init_data.format = { GLModel::Geometry::EPrimitiveType::Triangles, GLModel::Geometry::EVertexLayout::P3N3, GLModel::Geometry::EIndexType::UINT };
+
+    const ModelObjectPtrs& objects = wxGetApp().model().objects;
+    for (ModelObject* mo : objects) {
+        const ModelInstance* mi = mo->instances[0];
+        Transform3d inst_transfo = mi->get_matrix();
+        for (ModelVolume* mv : mo->volumes) {
+            TriangleMesh mesh_temp = mv->mesh();
+            mesh_temp.transform(mv->get_matrix() * inst_transfo);
+            indexed_triangle_set& mv_its = mesh_temp.its;
+            for (int facet_idx = 0; facet_idx < mv_its.indices.size(); facet_idx++) {
+                const stl_triangle_vertex_indices& facet_vert_idxs = mv_its.indices[facet_idx];
+                if (mv_its.get_property(facet_idx).type != eExteriorAppearance)
+                    continue;
+
+                for (int i = 0; i < 3; ++i) {
+                    init_data.add_vertex((Vec3f) mv_its.vertices[facet_vert_idxs[i]].cast<float>(), Vec3f{0.0f, 0.0f, 1.0f});
+                }
+
+                init_data.add_uint_triangle(cnt, cnt + 1, cnt + 2);
+                cnt += 3;
+            }
+        }
+    }
+    model.init_from(std::move(init_data));
+}
+
+CommonGizmosDataID GLGizmoFaceDetector::on_get_requirements() const
+{
+    return CommonGizmosDataID::SelectionInfo;
+}
+
+} // namespace GUI
+} // namespace Slic3r

src/slic3r/GUI/Gizmos/GLGizmoFaceDetector.hpp

@@ -0,0 +1,39 @@
+#ifndef slic3r_GLGizmoFaceDetector_hpp_
+#define slic3r_GLGizmoFaceDetector_hpp_
+
+#include "GLGizmoBase.hpp"
+#include "slic3r/GUI/3DScene.hpp"
+
+namespace Slic3r {
+
+namespace GUI {
+
+class GLGizmoFaceDetector : public GLGizmoBase
+{
+public:
+    GLGizmoFaceDetector(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id)
+        : GLGizmoBase(parent, icon_filename, sprite_id) {}
+
+protected:
+    void on_render() override;
+    void on_render_for_picking() override {}
+    void on_render_input_window(float x, float y, float bottom_limit) override;
+    std::string on_get_name() const override;
+    void on_set_state() override;
+    bool on_is_activable() const override;
+    CommonGizmosDataID on_get_requirements() const override;
+
+private:
+    bool on_init() override;
+    void perform_recognition(const Selection& selection);
+    void display_exterior_face();
+
+    GUI::GLModel model;
+    double m_sample_interval = {0.5};
+};
+
+} // namespace GUI
+} // namespace Slic3r
+
+
+#endif // slic3r_GLGizmoFaceDetector_hpp_

src/slic3r/GUI/Gizmos/GLGizmoHollow.cpp

@@ -0,0 +1,872 @@
+#include "GLGizmoHollow.hpp"
+#include "slic3r/GUI/GLCanvas3D.hpp"
+#include "slic3r/GUI/Camera.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmosCommon.hpp"
+
+#include <glad/gl.h>
+
+#include "slic3r/GUI/GUI_App.hpp"
+#include "slic3r/GUI/GUI_ObjectSettings.hpp"
+#include "slic3r/GUI/GUI_ObjectList.hpp"
+#include "slic3r/GUI/Plater.hpp"
+#include "libslic3r/PresetBundle.hpp"
+
+#include "libslic3r/Model.hpp"
+
+
+namespace Slic3r {
+namespace GUI {
+
+GLGizmoHollow::GLGizmoHollow(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id)
+    : GLGizmoBase(parent, icon_filename, sprite_id)
+{
+}
+
+
+bool GLGizmoHollow::on_init()
+{
+    m_desc["enable"]           = _(L("Hollow this object"));
+    m_desc["preview"]          = _(L("Preview hollowed and drilled model"));
+    m_desc["offset"]           = _(L("Offset")) + ": ";
+    m_desc["quality"]          = _(L("Quality")) + ": ";
+    m_desc["closing_distance"] = _(L("Closing distance")) + ": ";
+    m_desc["hole_diameter"]    = _(L("Hole diameter")) + ": ";
+    m_desc["hole_depth"]       = _(L("Hole depth")) + ": ";
+    m_desc["remove_selected"]  = _(L("Remove selected holes"));
+    m_desc["remove_all"]       = _(L("Remove all holes"));
+    m_desc["clipping_of_view"] = _(L("Clipping of view"))+ ": ";
+    m_desc["reset_direction"]  = _(L("Reset direction"));
+    m_desc["show_supports"]    = _(L("Show supports"));
+
+    return true;
+}
+
+void GLGizmoHollow::set_sla_support_data(ModelObject*, const Selection&)
+{
+    if (! m_c->selection_info())
+        return;
+
+    const ModelObject* mo = m_c->selection_info()->model_object();
+    if (m_state == On && mo) {
+        if (m_old_mo_id != mo->id()) {
+            reload_cache();
+            m_old_mo_id = mo->id();
+        }
+        if (m_c->hollowed_mesh() && m_c->hollowed_mesh()->get_hollowed_mesh())
+            m_holes_in_drilled_mesh = mo->sla_drain_holes;
+    }
+}
+
+
+
+void GLGizmoHollow::on_render()
+{
+    if (!m_cylinder.is_initialized())
+        m_cylinder.init_from(its_make_cylinder(1.0, 1.0));
+
+    const Selection& selection = m_parent.get_selection();
+    const CommonGizmosDataObjects::SelectionInfo* sel_info = m_c->selection_info();
+
+    // If current m_c->m_model_object does not match selection, ask GLCanvas3D to turn us off
+    if (m_state == On
+     && (sel_info->model_object() != selection.get_model()->objects[selection.get_object_idx()]
+      || sel_info->get_active_instance() != selection.get_instance_idx())) {
+        m_parent.post_event(SimpleEvent(EVT_GLCANVAS_RESETGIZMOS));
+        return;
+    }
+
+    glsafe(::glEnable(GL_BLEND));
+    glsafe(::glEnable(GL_DEPTH_TEST));
+
+    if (selection.is_from_single_instance())
+        render_points(selection, false);
+
+    m_selection_rectangle.render(m_parent);
+    m_c->object_clipper()->render_cut();
+    m_c->supports_clipper()->render_cut();
+
+    glsafe(::glDisable(GL_BLEND));
+}
+
+void GLGizmoHollow::render_points(const Selection& selection, bool picking)
+{
+    GLShaderProgram* shader = picking ? wxGetApp().get_shader("flat") : wxGetApp().get_shader("gouraud_light");
+    if (shader == nullptr)
+        return;
+
+    shader->start_using();
+    ScopeGuard guard([shader]() { shader->stop_using(); });
+
+    const GLVolume* vol = selection.get_volume(*selection.get_volume_idxs().begin());
+    const Transform3d instance_scaling_matrix_inverse = vol->get_instance_transformation().get_matrix(true, true, false, true).inverse();
+    const Transform3d instance_matrix = Geometry::assemble_transform(m_c->selection_info()->get_sla_shift() * Vec3d::UnitZ()) * vol->get_instance_transformation().get_matrix();
+
+    const Camera& camera = wxGetApp().plater()->get_camera();
+    const Transform3d& view_matrix = camera.get_view_matrix();
+    const Transform3d& projection_matrix = camera.get_projection_matrix();
+
+    shader->set_uniform("projection_matrix", projection_matrix);
+
+    ColorRGBA render_color;
+    const sla::DrainHoles& drain_holes = m_c->selection_info()->model_object()->sla_drain_holes;
+    const size_t cache_size = drain_holes.size();
+
+    for (size_t i = 0; i < cache_size; ++i) {
+        const sla::DrainHole& drain_hole = drain_holes[i];
+        const bool point_selected = m_selected[i];
+
+        if (is_mesh_point_clipped(drain_hole.pos.cast<double>()))
+            continue;
+
+        // First decide about the color of the point.
+        if (picking)
+            render_color = picking_color_component(i);
+        else {
+            if (size_t(m_hover_id) == i)
+                render_color = ColorRGBA::CYAN();
+            else if (m_c->hollowed_mesh() &&
+                       i < m_c->hollowed_mesh()->get_drainholes().size() &&
+                       m_c->hollowed_mesh()->get_drainholes()[i].failed) {
+                render_color = { 1.0f, 0.0f, 0.0f, 0.5f };
+            }
+            else  // neither hover nor picking
+                render_color = point_selected ? ColorRGBA(1.0f, 0.3f, 0.3f, 0.5f) : ColorRGBA(1.0f, 1.0f, 1.0f, 0.5f);
+        }
+
+        m_cylinder.set_color(render_color);
+
+        // Inverse matrix of the instance scaling is applied so that the mark does not scale with the object.
+        const Transform3d hole_matrix = Geometry::assemble_transform(drain_hole.pos.cast<double>()) * instance_scaling_matrix_inverse;
+
+        if (vol->is_left_handed())
+            glFrontFace(GL_CW);
+
+        // Matrices set, we can render the point mark now.
+        Eigen::Quaterniond q;
+        q.setFromTwoVectors(Vec3d::UnitZ(), instance_scaling_matrix_inverse * (-drain_hole.normal).cast<double>());
+        const Eigen::AngleAxisd aa(q);
+        const Transform3d model_matrix = instance_matrix * hole_matrix * Transform3d(aa.toRotationMatrix()) *
+            Geometry::assemble_transform(-drain_hole.height * Vec3d::UnitZ(), Vec3d::Zero(), Vec3d(drain_hole.radius, drain_hole.radius, drain_hole.height + sla::HoleStickOutLength));
+        shader->set_uniform("view_model_matrix", view_matrix * model_matrix);
+        const Matrix3d view_normal_matrix = view_matrix.matrix().block(0, 0, 3, 3) * model_matrix.matrix().block(0, 0, 3, 3).inverse().transpose();
+        shader->set_uniform("view_normal_matrix", view_normal_matrix);
+        m_cylinder.render();
+
+        if (vol->is_left_handed())
+            glFrontFace(GL_CCW);
+    }
+}
+
+bool GLGizmoHollow::is_mesh_point_clipped(const Vec3d& point) const
+{
+    if (m_c->object_clipper()->get_position() == 0.)
+        return false;
+
+    auto sel_info = m_c->selection_info();
+    int active_inst = m_c->selection_info()->get_active_instance();
+    const ModelInstance* mi = sel_info->model_object()->instances[active_inst];
+    const Transform3d& trafo = mi->get_transformation().get_matrix();
+
+    Vec3d transformed_point =  trafo * point;
+    transformed_point(2) += sel_info->get_sla_shift();
+    return m_c->object_clipper()->get_clipping_plane()->is_point_clipped(transformed_point);
+}
+
+
+
+// Unprojects the mouse position on the mesh and saves hit point and normal of the facet into pos_and_normal
+// Return false if no intersection was found, true otherwise.
+bool GLGizmoHollow::unproject_on_mesh(const Vec2d& mouse_pos, std::pair<Vec3f, Vec3f>& pos_and_normal)
+{
+    if (! m_c->raycaster()->raycaster())
+        return false;
+
+    const Camera& camera = wxGetApp().plater()->get_camera();
+    const Selection& selection = m_parent.get_selection();
+    const GLVolume* volume = selection.get_volume(*selection.get_volume_idxs().begin());
+    Geometry::Transformation trafo = volume->get_instance_transformation();
+    trafo.set_offset(trafo.get_offset() + Vec3d(0., 0., m_c->selection_info()->get_sla_shift()));
+
+    double clp_dist = m_c->object_clipper()->get_position();
+    const ClippingPlane* clp = m_c->object_clipper()->get_clipping_plane();
+
+    // The raycaster query
+    Vec3f hit;
+    Vec3f normal;
+    if (m_c->raycaster()->raycaster()->unproject_on_mesh(
+            mouse_pos,
+            trafo.get_matrix(),
+            camera,
+            hit,
+            normal,
+            clp_dist != 0. ? clp : nullptr))
+    {
+        if (m_c->hollowed_mesh() && m_c->hollowed_mesh()->get_hollowed_mesh()) {
+            // in this case the raycaster sees the hollowed and drilled mesh.
+            // if the point lies on the surface created by the hole, we want
+            // to ignore it.
+            for (const sla::DrainHole& hole : m_holes_in_drilled_mesh) {
+                sla::DrainHole outer(hole);
+                outer.radius *= 1.001f;
+                outer.height *= 1.001f;
+                if (outer.is_inside(hit))
+                    return false;
+            }
+        }
+
+        // Return both the point and the facet normal.
+        pos_and_normal = std::make_pair(hit, normal);
+        return true;
+    }
+    else
+        return false;
+}
+
+// Following function is called from GLCanvas3D to inform the gizmo about a mouse/keyboard event.
+// The gizmo has an opportunity to react - if it does, it should return true so that the Canvas3D is
+// aware that the event was reacted to and stops trying to make different sense of it. If the gizmo
+// concludes that the event was not intended for it, it should return false.
+bool GLGizmoHollow::gizmo_event(SLAGizmoEventType action, const Vec2d& mouse_position, bool shift_down, bool alt_down, bool control_down)
+{
+    ModelObject* mo = m_c->selection_info()->model_object();
+    int active_inst = m_c->selection_info()->get_active_instance();
+
+
+    // left down with shift - show the selection rectangle:
+    if (action == SLAGizmoEventType::LeftDown && (shift_down || alt_down || control_down)) {
+        if (m_hover_id == -1) {
+            if (shift_down || alt_down) {
+                m_selection_rectangle.start_dragging(mouse_position, shift_down ? GLSelectionRectangle::Select : GLSelectionRectangle::Deselect);
+            }
+        }
+        else {
+            if (m_selected[m_hover_id])
+                unselect_point(m_hover_id);
+            else {
+                if (!alt_down)
+                    select_point(m_hover_id);
+            }
+        }
+
+        return true;
+    }
+
+    // left down without selection rectangle - place point on the mesh:
+    if (action == SLAGizmoEventType::LeftDown && !m_selection_rectangle.is_dragging() && !shift_down) {
+        // If any point is in hover state, this should initiate its move - return control back to GLCanvas:
+        if (m_hover_id != -1)
+            return false;
+
+        // If there is some selection, don't add new point and deselect everything instead.
+        if (m_selection_empty) {
+            std::pair<Vec3f, Vec3f> pos_and_normal;
+            if (unproject_on_mesh(mouse_position, pos_and_normal)) { // we got an intersection
+                Plater::TakeSnapshot snapshot(wxGetApp().plater(), "Add drainage hole");
+
+                mo->sla_drain_holes.emplace_back(pos_and_normal.first,
+                                                -pos_and_normal.second, m_new_hole_radius, m_new_hole_height);
+                m_selected.push_back(false);
+                assert(m_selected.size() == mo->sla_drain_holes.size());
+                m_parent.set_as_dirty();
+                m_wait_for_up_event = true;
+            }
+            else
+                return false;
+        }
+        else
+            select_point(NoPoints);
+
+        return true;
+    }
+
+    // left up with selection rectangle - select points inside the rectangle:
+    if ((action == SLAGizmoEventType::LeftUp || action == SLAGizmoEventType::ShiftUp || action == SLAGizmoEventType::AltUp) && m_selection_rectangle.is_dragging()) {
+        // Is this a selection or deselection rectangle?
+        GLSelectionRectangle::EState rectangle_status = m_selection_rectangle.get_state();
+
+        // First collect positions of all the points in world coordinates.
+        Geometry::Transformation trafo = mo->instances[active_inst]->get_transformation();
+        trafo.set_offset(trafo.get_offset() + Vec3d(0., 0., m_c->selection_info()->get_sla_shift()));
+        std::vector<Vec3d> points;
+        for (unsigned int i=0; i<mo->sla_drain_holes.size(); ++i)
+            points.push_back(trafo.get_matrix() * mo->sla_drain_holes[i].pos.cast<double>());
+
+        // Now ask the rectangle which of the points are inside.
+        std::vector<Vec3f> points_inside;
+        std::vector<unsigned int> points_idxs = m_selection_rectangle.stop_dragging(m_parent, points);
+        for (size_t idx : points_idxs)
+            points_inside.push_back(points[idx].cast<float>());
+
+        // Only select/deselect points that are actually visible
+        for (size_t idx : m_c->raycaster()->raycaster()->get_unobscured_idxs(
+                 trafo, wxGetApp().plater()->get_camera(), points_inside,
+                 m_c->object_clipper()->get_clipping_plane()))
+        {
+            if (rectangle_status == GLSelectionRectangle::Deselect)
+                unselect_point(points_idxs[idx]);
+            else
+                select_point(points_idxs[idx]);
+        }
+        return true;
+    }
+
+    // left up with no selection rectangle
+    if (action == SLAGizmoEventType::LeftUp) {
+        if (m_wait_for_up_event) {
+            m_wait_for_up_event = false;
+        }
+        return true;
+    }
+
+    // dragging the selection rectangle:
+    if (action == SLAGizmoEventType::Dragging) {
+        if (m_wait_for_up_event)
+            return true; // point has been placed and the button not released yet
+                         // this prevents GLCanvas from starting scene rotation
+
+        if (m_selection_rectangle.is_dragging())  {
+            m_selection_rectangle.dragging(mouse_position);
+            return true;
+        }
+
+        return false;
+    }
+
+    if (action == SLAGizmoEventType::Delete) {
+        // delete key pressed
+        delete_selected_points();
+        return true;
+    }
+
+    if (action == SLAGizmoEventType::RightDown) {
+        if (m_hover_id != -1) {
+            select_point(NoPoints);
+            select_point(m_hover_id);
+            delete_selected_points();
+            return true;
+        }
+        return false;
+    }
+
+    if (action == SLAGizmoEventType::SelectAll) {
+        select_point(AllPoints);
+        return true;
+    }
+
+    if (action == SLAGizmoEventType::MouseWheelUp && control_down) {
+        double pos = m_c->object_clipper()->get_position();
+        pos = std::min(1., pos + 0.01);
+        m_c->object_clipper()->set_position(pos, true);
+        return true;
+    }
+
+    if (action == SLAGizmoEventType::MouseWheelDown && control_down) {
+        double pos = m_c->object_clipper()->get_position();
+        pos = std::max(0., pos - 0.01);
+        m_c->object_clipper()->set_position(pos, true);
+        return true;
+    }
+
+    if (action == SLAGizmoEventType::ResetClippingPlane) {
+        m_c->object_clipper()->set_position(-1., false);
+        return true;
+    }
+
+    return false;
+}
+
+void GLGizmoHollow::delete_selected_points()
+{
+    Plater::TakeSnapshot snapshot(wxGetApp().plater(), "Delete drainage hole");
+    sla::DrainHoles& drain_holes = m_c->selection_info()->model_object()->sla_drain_holes;
+
+    for (unsigned int idx=0; idx<drain_holes.size(); ++idx) {
+        if (m_selected[idx]) {
+            m_selected.erase(m_selected.begin()+idx);
+            drain_holes.erase(drain_holes.begin() + (idx--));
+        }
+    }
+
+    select_point(NoPoints);
+}
+
+void GLGizmoHollow::on_update(const UpdateData& data)
+{
+    sla::DrainHoles& drain_holes = m_c->selection_info()->model_object()->sla_drain_holes;
+
+    if (m_hover_id != -1) {
+        std::pair<Vec3f, Vec3f> pos_and_normal;
+        if (! unproject_on_mesh(data.mouse_pos.cast<double>(), pos_and_normal))
+            return;
+        drain_holes[m_hover_id].pos = pos_and_normal.first;
+        drain_holes[m_hover_id].normal = -pos_and_normal.second;
+    }
+}
+
+
+void GLGizmoHollow::hollow_mesh(bool postpone_error_messages)
+{
+    wxGetApp().CallAfter([this, postpone_error_messages]() {
+        wxGetApp().plater()->reslice_SLA_hollowing(
+            *m_c->selection_info()->model_object(), postpone_error_messages);
+    });
+}
+
+
+std::vector<std::pair<const ConfigOption*, const ConfigOptionDef*>>
+GLGizmoHollow::get_config_options(const std::vector<std::string>& keys) const
+{
+    std::vector<std::pair<const ConfigOption*, const ConfigOptionDef*>> out;
+    const ModelObject* mo = m_c->selection_info()->model_object();
+
+    if (! mo)
+        return out;
+
+    const DynamicPrintConfig& object_cfg = mo->config.get();
+    const DynamicPrintConfig& print_cfg = wxGetApp().preset_bundle->sla_prints.get_edited_preset().config;
+    std::unique_ptr<DynamicPrintConfig> default_cfg = nullptr;
+
+    for (const std::string& key : keys) {
+        if (object_cfg.has(key))
+            out.emplace_back(object_cfg.option(key), &object_cfg.def()->options.at(key)); // at() needed for const map
+        else
+            if (print_cfg.has(key))
+                out.emplace_back(print_cfg.option(key), &print_cfg.def()->options.at(key));
+            else { // we must get it from defaults
+                if (default_cfg == nullptr)
+                    default_cfg.reset(DynamicPrintConfig::new_from_defaults_keys(keys));
+                out.emplace_back(default_cfg->option(key), &default_cfg->def()->options.at(key));
+            }
+    }
+
+    return out;
+}
+
+
+void GLGizmoHollow::on_render_input_window(float x, float y, float bottom_limit)
+{
+    ModelObject* mo = m_c->selection_info()->model_object();
+    if (! mo)
+        return;
+
+    bool first_run = true; // This is a hack to redraw the button when all points are removed,
+                           // so it is not delayed until the background process finishes.
+
+    ConfigOptionMode current_mode = wxGetApp().get_mode();
+
+    std::vector<std::string> opts_keys = {"hollowing_min_thickness", "hollowing_quality", "hollowing_closing_distance"};
+    auto opts = get_config_options(opts_keys);
+    auto* offset_cfg = static_cast<const ConfigOptionFloat*>(opts[0].first);
+    float offset = offset_cfg->value;
+    double offset_min = opts[0].second->min;
+    double offset_max = opts[0].second->max;
+
+    auto* quality_cfg = static_cast<const ConfigOptionFloat*>(opts[1].first);
+    float quality = quality_cfg->value;
+    double quality_min = opts[1].second->min;
+    double quality_max = opts[1].second->max;
+    ConfigOptionMode quality_mode = opts[1].second->mode;
+
+    auto* closing_d_cfg = static_cast<const ConfigOptionFloat*>(opts[2].first);
+    float closing_d = closing_d_cfg->value;
+    double closing_d_min = opts[2].second->min;
+    double closing_d_max = opts[2].second->max;
+    ConfigOptionMode closing_d_mode = opts[2].second->mode;
+
+    m_desc["offset"] = _(opts[0].second->label) + ":";
+    m_desc["quality"] = _(opts[1].second->label) + ":";
+    m_desc["closing_distance"] = _(opts[2].second->label) + ":";
+
+
+RENDER_AGAIN:
+    const float approx_height = m_imgui->scaled(20.0f);
+    y = std::min(y, bottom_limit - approx_height);
+    m_imgui->set_next_window_pos(x, y, ImGuiCond_Always);
+
+    m_imgui->begin(get_name(), ImGuiWindowFlags_NoMove | ImGuiWindowFlags_AlwaysAutoResize | ImGuiWindowFlags_NoCollapse);
+
+    // First calculate width of all the texts that are could possibly be shown. We will decide set the dialog width based on that:
+    const float clipping_slider_left = std::max(m_imgui->calc_text_size(m_desc.at("clipping_of_view")).x,
+                                                m_imgui->calc_text_size(m_desc.at("reset_direction")).x) + m_imgui->scaled(0.5f);
+
+    const float settings_sliders_left =
+        std::max(std::max({m_imgui->calc_text_size(m_desc.at("offset")).x,
+                           m_imgui->calc_text_size(m_desc.at("quality")).x,
+                           m_imgui->calc_text_size(m_desc.at("closing_distance")).x,
+                           m_imgui->calc_text_size(m_desc.at("hole_diameter")).x,
+                           m_imgui->calc_text_size(m_desc.at("hole_depth")).x}) + m_imgui->scaled(0.5f), clipping_slider_left);
+
+    const float diameter_slider_left = settings_sliders_left; //m_imgui->calc_text_size(m_desc.at("hole_diameter")).x + m_imgui->scaled(1.f);
+    const float minimal_slider_width = m_imgui->scaled(4.f);
+
+    const float button_preview_width = m_imgui->calc_button_size(m_desc.at("preview")).x;
+
+    float window_width = minimal_slider_width + std::max({settings_sliders_left, clipping_slider_left, diameter_slider_left});
+    window_width = std::max(window_width, button_preview_width);
+
+    if (m_imgui->button(m_desc["preview"]))
+        hollow_mesh();
+    
+    bool config_changed = false;
+
+    ImGui::Separator();
+
+    {
+        auto opts = get_config_options({"hollowing_enable"});
+        m_enable_hollowing = static_cast<const ConfigOptionBool*>(opts[0].first)->value;
+        if (m_imgui->checkbox(m_desc["enable"], m_enable_hollowing)) {
+            mo->config.set("hollowing_enable", m_enable_hollowing);
+            wxGetApp().obj_list()->update_and_show_object_settings_item();
+            config_changed = true;
+        }
+    }
+
+    m_imgui->disabled_begin(! m_enable_hollowing);
+    ImGui::AlignTextToFramePadding();
+    m_imgui->text(m_desc.at("offset"));
+    ImGui::SameLine(settings_sliders_left, m_imgui->get_item_spacing().x);
+    ImGui::PushItemWidth(window_width - settings_sliders_left);
+    m_imgui->slider_float("##offset", &offset, offset_min, offset_max, "%.1f mm", 1.0f, true, _L(opts[0].second->tooltip));
+
+    bool slider_clicked = m_imgui->get_last_slider_status().clicked; // someone clicked the slider
+    bool slider_edited =m_imgui->get_last_slider_status().edited; // someone is dragging the slider
+    bool slider_released =m_imgui->get_last_slider_status().deactivated_after_edit; // someone has just released the slider
+
+    if (current_mode >= quality_mode) {
+        ImGui::AlignTextToFramePadding();
+        m_imgui->text(m_desc.at("quality"));
+        ImGui::SameLine(settings_sliders_left, m_imgui->get_item_spacing().x);
+        m_imgui->slider_float("##quality", &quality, quality_min, quality_max, "%.1f", 1.0f, true, _L(opts[1].second->tooltip));
+
+        slider_clicked |= m_imgui->get_last_slider_status().clicked;
+        slider_edited |= m_imgui->get_last_slider_status().edited;
+        slider_released |= m_imgui->get_last_slider_status().deactivated_after_edit;
+    }
+
+    if (current_mode >= closing_d_mode) {
+        ImGui::AlignTextToFramePadding();
+        m_imgui->text(m_desc.at("closing_distance"));
+        ImGui::SameLine(settings_sliders_left, m_imgui->get_item_spacing().x);
+        m_imgui->slider_float("##closing_distance", &closing_d, closing_d_min, closing_d_max, "%.1f mm", 1.0f, true, _L(opts[2].second->tooltip));
+
+        slider_clicked |= m_imgui->get_last_slider_status().clicked;
+        slider_edited |= m_imgui->get_last_slider_status().edited;
+        slider_released |= m_imgui->get_last_slider_status().deactivated_after_edit;
+    }
+
+    if (slider_clicked) {
+        m_offset_stash = offset;
+        m_quality_stash = quality;
+        m_closing_d_stash = closing_d;
+    }
+    if (slider_edited || slider_released) {
+        if (slider_released) {
+            mo->config.set("hollowing_min_thickness", m_offset_stash);
+            mo->config.set("hollowing_quality", m_quality_stash);
+            mo->config.set("hollowing_closing_distance", m_closing_d_stash);
+            Plater::TakeSnapshot snapshot(wxGetApp().plater(), "Hollowing parameter change");
+        }
+        mo->config.set("hollowing_min_thickness", offset);
+        mo->config.set("hollowing_quality", quality);
+        mo->config.set("hollowing_closing_distance", closing_d);
+        if (slider_released) {
+            wxGetApp().obj_list()->update_and_show_object_settings_item();
+            config_changed = true;
+        }
+    }
+
+    m_imgui->disabled_end();
+
+    bool force_refresh = false;
+    bool remove_selected = false;
+    bool remove_all = false;
+
+    ImGui::Separator();
+
+    float diameter_upper_cap = 60.;
+    if (m_new_hole_radius * 2.f > diameter_upper_cap)
+        m_new_hole_radius = diameter_upper_cap / 2.f;
+    ImGui::AlignTextToFramePadding();
+    m_imgui->text(m_desc.at("hole_diameter"));
+    ImGui::SameLine(diameter_slider_left, m_imgui->get_item_spacing().x);
+    ImGui::PushItemWidth(window_width - diameter_slider_left);
+
+    float diam = 2.f * m_new_hole_radius;
+    m_imgui->slider_float("##hole_diameter", &diam, 1.f, 25.f, "%.1f mm", 1.f, false);
+    // Let's clamp the value (which could have been entered by keyboard) to a larger range
+    // than the slider. This allows entering off-scale values and still protects against
+    //complete non-sense.
+    diam = std::clamp(diam, 0.1f, diameter_upper_cap);
+    m_new_hole_radius = diam / 2.f;
+    bool clicked = m_imgui->get_last_slider_status().clicked;
+    bool edited = m_imgui->get_last_slider_status().edited;
+    bool deactivated = m_imgui->get_last_slider_status().deactivated_after_edit;
+
+    ImGui::AlignTextToFramePadding();
+    m_imgui->text(m_desc["hole_depth"]);
+    ImGui::SameLine(diameter_slider_left, m_imgui->get_item_spacing().x);
+    m_imgui->slider_float("##hole_depth", &m_new_hole_height, 0.f, 10.f, "%.1f mm", 1.f, false);
+    // Same as above:
+    m_new_hole_height = std::clamp(m_new_hole_height, 0.f, 100.f);
+
+    clicked |= m_imgui->get_last_slider_status().clicked;
+    edited |= m_imgui->get_last_slider_status().edited;
+    deactivated |= m_imgui->get_last_slider_status().deactivated_after_edit;;
+
+    // Following is a nasty way to:
+    //  - save the initial value of the slider before one starts messing with it
+    //  - keep updating the head radius during sliding so it is continuosly refreshed in 3D scene
+    //  - take correct undo/redo snapshot after the user is done with moving the slider
+    if (! m_selection_empty) {
+        if (clicked) {
+            m_holes_stash = mo->sla_drain_holes;
+        }
+        if (edited) {
+            for (size_t idx=0; idx<m_selected.size(); ++idx)
+                if (m_selected[idx]) {
+                    mo->sla_drain_holes[idx].radius = m_new_hole_radius;
+                    mo->sla_drain_holes[idx].height = m_new_hole_height;
+                }
+        }
+        if (deactivated) {
+            // momentarily restore the old value to take snapshot
+            sla::DrainHoles new_holes = mo->sla_drain_holes;
+            mo->sla_drain_holes = m_holes_stash;
+            float backup_rad = m_new_hole_radius;
+            float backup_hei = m_new_hole_height;
+            for (size_t i=0; i<m_holes_stash.size(); ++i) {
+                if (m_selected[i]) {
+                    m_new_hole_radius = m_holes_stash[i].radius;
+                    m_new_hole_height = m_holes_stash[i].height;
+                    break;
+                }
+            }
+            Plater::TakeSnapshot snapshot(wxGetApp().plater(), "Change drainage hole diameter");
+            m_new_hole_radius = backup_rad;
+            m_new_hole_height = backup_hei;
+            mo->sla_drain_holes = new_holes;
+        }
+    }
+
+    m_imgui->disabled_begin(m_selection_empty);
+    remove_selected = m_imgui->button(m_desc.at("remove_selected"));
+    m_imgui->disabled_end();
+
+    m_imgui->disabled_begin(mo->sla_drain_holes.empty());
+    remove_all = m_imgui->button(m_desc.at("remove_all"));
+    m_imgui->disabled_end();
+
+    // Following is rendered in both editing and non-editing mode:
+   // m_imgui->text("");
+    ImGui::Separator();
+    if (m_c->object_clipper()->get_position() == 0.f) {
+        ImGui::AlignTextToFramePadding();
+        m_imgui->text(m_desc.at("clipping_of_view"));
+    }
+    else {
+        if (m_imgui->button(m_desc.at("reset_direction"))) {
+            wxGetApp().CallAfter([this](){
+                    m_c->object_clipper()->set_position(-1., false);
+                });
+        }
+    }
+
+    ImGui::SameLine(settings_sliders_left, m_imgui->get_item_spacing().x);
+    ImGui::PushItemWidth(window_width - settings_sliders_left);
+    float clp_dist = m_c->object_clipper()->get_position();
+    if (m_imgui->slider_float("##clp_dist", &clp_dist, 0.f, 1.f, "%.2f"))
+        m_c->object_clipper()->set_position(clp_dist, true);
+
+    // make sure supports are shown/hidden as appropriate
+    bool show_sups = m_c->instances_hider()->are_supports_shown();
+    if (m_imgui->checkbox(m_desc["show_supports"], show_sups)) {
+        m_c->instances_hider()->show_supports(show_sups);
+        force_refresh = true;
+    }
+
+    m_imgui->end();
+
+
+    if (remove_selected || remove_all) {
+        force_refresh = false;
+        m_parent.set_as_dirty();
+
+        if (remove_all) {
+            select_point(AllPoints);
+            delete_selected_points();
+        }
+        if (remove_selected)
+            delete_selected_points();
+
+        if (first_run) {
+            first_run = false;
+            goto RENDER_AGAIN;
+        }
+    }
+
+    if (force_refresh)
+        m_parent.set_as_dirty();
+
+    if (config_changed)
+        m_parent.post_event(SimpleEvent(EVT_GLCANVAS_FORCE_UPDATE));
+}
+
+bool GLGizmoHollow::on_is_activable() const
+{
+    const Selection& selection = m_parent.get_selection();
+
+    if (wxGetApp().preset_bundle->printers.get_edited_preset().printer_technology() != ptSLA
+        || !selection.is_from_single_instance())
+        return false;
+
+    // Check that none of the selected volumes is outside. Only SLA auxiliaries (supports) are allowed outside.
+    const Selection::IndicesList& list = selection.get_volume_idxs();
+    for (const auto& idx : list)
+        if (selection.get_volume(idx)->is_outside && selection.get_volume(idx)->composite_id.volume_id >= 0)
+            return false;
+
+    return true;
+}
+
+bool GLGizmoHollow::on_is_selectable() const
+{
+    return (wxGetApp().preset_bundle->printers.get_edited_preset().printer_technology() == ptSLA);
+}
+
+std::string GLGizmoHollow::on_get_name() const
+{
+    return _u8L("Hollow and drill");
+}
+
+
+CommonGizmosDataID GLGizmoHollow::on_get_requirements() const
+{
+    return CommonGizmosDataID(
+                int(CommonGizmosDataID::SelectionInfo)
+              | int(CommonGizmosDataID::InstancesHider)
+              | int(CommonGizmosDataID::Raycaster)
+              | int(CommonGizmosDataID::HollowedMesh)
+              | int(CommonGizmosDataID::ObjectClipper)
+              | int(CommonGizmosDataID::SupportsClipper));
+}
+
+
+void GLGizmoHollow::on_set_state()
+{
+    if (m_state == m_old_state)
+        return;
+
+    if (m_state == Off && m_old_state != Off) // the gizmo was just turned Off
+        m_parent.post_event(SimpleEvent(EVT_GLCANVAS_FORCE_UPDATE));
+    m_old_state = m_state;
+}
+
+
+
+void GLGizmoHollow::on_start_dragging()
+{
+    if (m_hover_id != -1) {
+        select_point(NoPoints);
+        select_point(m_hover_id);
+        m_hole_before_drag = m_c->selection_info()->model_object()->sla_drain_holes[m_hover_id].pos;
+    }
+    else
+        m_hole_before_drag = Vec3f::Zero();
+}
+
+
+void GLGizmoHollow::on_stop_dragging()
+{
+    sla::DrainHoles& drain_holes = m_c->selection_info()->model_object()->sla_drain_holes;
+    if (m_hover_id != -1) {
+        Vec3f backup = drain_holes[m_hover_id].pos;
+
+        if (m_hole_before_drag != Vec3f::Zero() // some point was touched
+         && backup != m_hole_before_drag) // and it was moved, not just selected
+        {
+            drain_holes[m_hover_id].pos = m_hole_before_drag;
+            Plater::TakeSnapshot snapshot(wxGetApp().plater(), "Move drainage hole");
+            drain_holes[m_hover_id].pos = backup;
+        }
+    }
+    m_hole_before_drag = Vec3f::Zero();
+}
+
+
+
+void GLGizmoHollow::on_load(cereal::BinaryInputArchive& ar)
+{
+    ar(m_new_hole_radius,
+       m_new_hole_height,
+       m_selected,
+       m_selection_empty
+    );
+}
+
+
+
+void GLGizmoHollow::on_save(cereal::BinaryOutputArchive& ar) const
+{
+    ar(m_new_hole_radius,
+       m_new_hole_height,
+       m_selected,
+       m_selection_empty
+    );
+}
+
+
+
+void GLGizmoHollow::select_point(int i)
+{
+    const sla::DrainHoles& drain_holes = m_c->selection_info()->model_object()->sla_drain_holes;
+
+    if (i == AllPoints || i == NoPoints) {
+        m_selected.assign(m_selected.size(), i == AllPoints);
+        m_selection_empty = (i == NoPoints);
+
+        if (i == AllPoints) {
+            m_new_hole_radius = drain_holes[0].radius;
+            m_new_hole_height = drain_holes[0].height;
+        }
+    }
+    else {
+        while (size_t(i) >= m_selected.size())
+            m_selected.push_back(false);
+        m_selected[i] = true;
+        m_selection_empty = false;
+        m_new_hole_radius = drain_holes[i].radius;
+        m_new_hole_height = drain_holes[i].height;
+    }
+}
+
+
+void GLGizmoHollow::unselect_point(int i)
+{
+    m_selected[i] = false;
+    m_selection_empty = true;
+    for (const bool sel : m_selected) {
+        if (sel) {
+            m_selection_empty = false;
+            break;
+        }
+    }
+}
+
+void GLGizmoHollow::reload_cache()
+{
+    m_selected.clear();
+    m_selected.assign(m_c->selection_info()->model_object()->sla_drain_holes.size(), false);
+}
+
+
+void GLGizmoHollow::on_set_hover_id()
+{
+    if (int(m_c->selection_info()->model_object()->sla_drain_holes.size()) <= m_hover_id)
+        m_hover_id = -1;
+}
+
+
+
+
+} // namespace GUI
+} // namespace Slic3r

src/slic3r/GUI/Gizmos/GLGizmoHollow.hpp

@@ -0,0 +1,111 @@
+#ifndef slic3r_GLGizmoHollow_hpp_
+#define slic3r_GLGizmoHollow_hpp_
+
+#include "GLGizmoBase.hpp"
+#include "slic3r/GUI/GLSelectionRectangle.hpp"
+
+#include <libslic3r/SLA/Hollowing.hpp>
+#include <libslic3r/ObjectID.hpp>
+#include <wx/dialog.h>
+
+#include <cereal/types/vector.hpp>
+
+
+namespace Slic3r {
+
+class ConfigOption;
+class ConfigOptionDef;
+
+namespace GUI {
+
+enum class SLAGizmoEventType : unsigned char;
+
+class GLGizmoHollow : public GLGizmoBase
+{
+private:
+    bool unproject_on_mesh(const Vec2d& mouse_pos, std::pair<Vec3f, Vec3f>& pos_and_normal);
+
+
+public:
+    GLGizmoHollow(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id);
+    virtual ~GLGizmoHollow() = default;
+    void set_sla_support_data(ModelObject* model_object, const Selection& selection);
+    bool gizmo_event(SLAGizmoEventType action, const Vec2d& mouse_position, bool shift_down, bool alt_down, bool control_down);
+    void delete_selected_points();    
+    bool is_selection_rectangle_dragging() const {
+        return m_selection_rectangle.is_dragging();
+    }
+
+private:
+    bool on_init() override;
+    void on_update(const UpdateData& data) override;
+    void on_render() override;
+
+    void render_points(const Selection& selection, bool picking = false);
+    void hollow_mesh(bool postpone_error_messages = false);
+    bool unsaved_changes() const;
+
+    ObjectID m_old_mo_id = -1;
+
+    GLModel m_cylinder;
+
+    float m_new_hole_radius = 2.f;        // Size of a new hole.
+    float m_new_hole_height = 6.f;
+    mutable std::vector<bool> m_selected; // which holes are currently selected
+
+    bool m_enable_hollowing = true;
+
+    // Stashes to keep data for undo redo. Is taken after the editing
+    // is done, the data are updated continuously.
+    float m_offset_stash = 3.0f;
+    float m_quality_stash = 0.5f;
+    float m_closing_d_stash = 2.f;
+    Vec3f m_hole_before_drag = Vec3f::Zero();
+    sla::DrainHoles m_holes_in_drilled_mesh;
+
+    sla::DrainHoles m_holes_stash;
+    
+    // This map holds all translated description texts, so they can be easily referenced during layout calculations
+    // etc. When language changes, GUI is recreated and this class constructed again, so the change takes effect.
+    std::map<std::string, wxString> m_desc;
+
+    GLSelectionRectangle m_selection_rectangle;
+
+    bool m_wait_for_up_event = false;
+    bool m_selection_empty = true;
+    EState m_old_state = Off; // to be able to see that the gizmo has just been closed (see on_set_state)
+
+    std::vector<std::pair<const ConfigOption*, const ConfigOptionDef*>> get_config_options(const std::vector<std::string>& keys) const;
+    bool is_mesh_point_clipped(const Vec3d& point) const;
+
+    // Methods that do the model_object and editing cache synchronization,
+    // editing mode selection, etc:
+    enum {
+        AllPoints = -2,
+        NoPoints,
+    };
+    void select_point(int i);
+    void unselect_point(int i);
+    void reload_cache();
+
+protected:
+    void on_set_state() override;
+    void on_set_hover_id() override;
+    void on_start_dragging() override;
+    void on_stop_dragging() override;
+    void on_render_input_window(float x, float y, float bottom_limit) override;
+    virtual CommonGizmosDataID on_get_requirements() const override;
+
+    std::string on_get_name() const override;
+    bool on_is_activable() const override;
+    bool on_is_selectable() const override;
+    void on_load(cereal::BinaryInputArchive& ar) override;
+    void on_save(cereal::BinaryOutputArchive& ar) const override;
+};
+
+
+
+} // namespace GUI
+} // namespace Slic3r
+
+#endif // slic3r_GLGizmoHollow_hpp_

src/slic3r/GUI/Gizmos/GLGizmoSlaSupports.hpp

@@ -0,0 +1,159 @@
+#ifndef slic3r_GLGizmoSlaSupports_hpp_
+#define slic3r_GLGizmoSlaSupports_hpp_
+
+#include "GLGizmoBase.hpp"
+#include "slic3r/GUI/GLSelectionRectangle.hpp"
+
+#include "libslic3r/SLA/SupportPoint.hpp"
+#include "libslic3r/ObjectID.hpp"
+#include <wx/dialog.h>
+
+#include <cereal/types/vector.hpp>
+
+
+namespace Slic3r {
+
+class ConfigOption;
+
+namespace GUI {
+
+enum class SLAGizmoEventType : unsigned char;
+
+class GLGizmoSlaSupports : public GLGizmoBase
+{
+private:
+
+    bool unproject_on_mesh(const Vec2d& mouse_pos, std::pair<Vec3f, Vec3f>& pos_and_normal);
+
+    const float RenderPointScale = 1.f;
+
+    class CacheEntry {
+    public:
+        CacheEntry() :
+            support_point(sla::SupportPoint()), selected(false), normal(Vec3f::Zero()) {}
+
+        CacheEntry(const sla::SupportPoint& point, bool sel = false, const Vec3f& norm = Vec3f::Zero()) :
+            support_point(point), selected(sel), normal(norm) {}
+
+        bool operator==(const CacheEntry& rhs) const {
+            return (support_point == rhs.support_point);
+        }
+
+        bool operator!=(const CacheEntry& rhs) const {
+            return ! ((*this) == rhs);
+        }
+
+        sla::SupportPoint support_point;
+        bool selected; // whether the point is selected
+        Vec3f normal;
+
+        template<class Archive>
+        void serialize(Archive & ar)
+        {
+            ar(support_point, selected, normal);
+        }
+    };
+
+public:
+    GLGizmoSlaSupports(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id);
+    virtual ~GLGizmoSlaSupports() = default;
+    void set_sla_support_data(ModelObject* model_object, const Selection& selection);
+    bool gizmo_event(SLAGizmoEventType action, const Vec2d& mouse_position, bool shift_down, bool alt_down, bool control_down);
+    void delete_selected_points(bool force = false);
+    //ClippingPlane get_sla_clipping_plane() const;
+
+    bool is_in_editing_mode() const { return m_editing_mode; }
+    bool is_selection_rectangle_dragging() const { return m_selection_rectangle.is_dragging(); }
+    bool has_backend_supports() const;
+    void reslice_SLA_supports(bool postpone_error_messages = false) const;
+
+    bool wants_enter_leave_snapshots() const override { return true; }
+    std::string get_gizmo_entering_text() const override { return "Entering SLA support points"; }
+    std::string get_gizmo_leaving_text() const override { return "Leaving SLA support points"; }
+
+private:
+    bool on_init() override;
+    void on_update(const UpdateData& data) override;
+    void on_render() override;
+
+    void render_points(const Selection& selection, bool picking = false);
+    bool unsaved_changes() const;
+
+    bool m_lock_unique_islands = false;
+    bool m_editing_mode = false;            // Is editing mode active?
+    float m_new_point_head_diameter;        // Size of a new point.
+    CacheEntry m_point_before_drag;         // undo/redo - so we know what state was edited
+    float m_old_point_head_diameter = 0.;   // the same
+    float m_minimal_point_distance_stash = 0.f; // and again
+    float m_density_stash = 0.f;                // and again
+    mutable std::vector<CacheEntry> m_editing_cache; // a support point and whether it is currently selected
+    std::vector<sla::SupportPoint> m_normal_cache; // to restore after discarding changes or undo/redo
+    ObjectID m_old_mo_id;
+
+    GLModel m_cone;
+    GLModel m_cylinder;
+    GLModel m_sphere;
+
+    // This map holds all translated description texts, so they can be easily referenced during layout calculations
+    // etc. When language changes, GUI is recreated and this class constructed again, so the change takes effect.
+    std::map<std::string, wxString> m_desc;
+
+    GLSelectionRectangle m_selection_rectangle;
+
+    bool m_wait_for_up_event = false;
+    bool m_selection_empty = true;
+    EState m_old_state = Off; // to be able to see that the gizmo has just been closed (see on_set_state)
+
+    std::vector<const ConfigOption*> get_config_options(const std::vector<std::string>& keys) const;
+    bool is_mesh_point_clipped(const Vec3d& point) const;
+    bool is_point_in_hole(const Vec3f& pt) const;
+    //void find_intersecting_facets(const igl::AABB<Eigen::MatrixXf, 3>* aabb, const Vec3f& normal, double offset, std::vector<unsigned int>& out) const;
+
+    // Methods that do the model_object and editing cache synchronization,
+    // editing mode selection, etc:
+    enum {
+        AllPoints = -2,
+        NoPoints,
+    };
+    void select_point(int i);
+    void unselect_point(int i);
+    void editing_mode_apply_changes();
+    void editing_mode_discard_changes();
+    void reload_cache();
+    void get_data_from_backend();
+    void auto_generate();
+    void switch_to_editing_mode();
+    void disable_editing_mode();
+    void ask_about_changes_call_after(std::function<void()> on_yes, std::function<void()> on_no);
+
+protected:
+    void on_set_state() override;
+    void on_set_hover_id() override
+
+    {
+        if (! m_editing_mode || (int)m_editing_cache.size() <= m_hover_id)
+            m_hover_id = -1;
+    }
+    void on_start_dragging() override;
+    void on_stop_dragging() override;
+    void on_render_input_window(float x, float y, float bottom_limit) override;
+
+    std::string on_get_name() const override;
+    bool on_is_activable() const override;
+    bool on_is_selectable() const override;
+    virtual CommonGizmosDataID on_get_requirements() const override;
+    void on_load(cereal::BinaryInputArchive& ar) override;
+    void on_save(cereal::BinaryOutputArchive& ar) const override;
+};
+
+
+class SlaGizmoHelpDialog : public wxDialog
+{
+public:
+    SlaGizmoHelpDialog();
+};
+
+} // namespace GUI
+} // namespace Slic3r
+
+#endif // slic3r_GLGizmoSlaSupports_hpp_

src/slic3r/GUI/Gizmos/GLGizmoText.hpp

@@ -0,0 +1,126 @@
+#ifndef slic3r_GLGizmoText_hpp_
+#define slic3r_GLGizmoText_hpp_
+
+#include "GLGizmoBase.hpp"
+#include "slic3r/GUI/3DScene.hpp"
+#include "../GLTexture.hpp"
+#include "../Camera.hpp"
+#include "libslic3r/Model.hpp"
+
+namespace Slic3r {
+
+enum class ModelVolumeType : int;
+class ModelVolume;
+
+namespace GUI {
+
+enum class SLAGizmoEventType : unsigned char;
+class GLGizmoText : public GLGizmoBase
+{
+private:
+    std::vector<std::string> m_avail_font_names;
+    char m_text[1024] = { 0 };
+    std::string m_font_name;
+    float m_font_size = 16.f;
+    int m_curr_font_idx = 0;
+    bool m_bold = true;
+    bool m_italic = false;
+    float m_thickness = 2.f;
+    float m_embeded_depth = 0.f;
+    float m_rotate_angle = 0;
+    float m_text_gap = 0.f;
+    bool m_is_surface_text = false;
+    bool m_keep_horizontal = false;
+    mutable RaycastResult    m_rr;
+
+    float m_combo_height = 0.0f;
+    float m_combo_width = 0.0f;
+    float m_scale;
+
+    Vec2d m_mouse_position = Vec2d::Zero();
+    Vec2d m_origin_mouse_position = Vec2d::Zero();
+    bool  m_shift_down     = false;
+
+    class TextureInfo {
+    public:
+        GLTexture* texture { nullptr };
+        int h;
+        int w;
+        int hl;
+
+        std::string font_name;
+    };
+
+    std::vector<TextureInfo> m_textures;
+
+    std::vector<std::string> m_font_names;
+
+    bool m_is_modify = false;
+    bool m_need_update_text = false;
+
+    int  m_object_idx = -1;
+    int  m_volume_idx = -1;
+
+    int m_preview_text_volume_id = -1;
+
+    Vec3d m_mouse_position_world = Vec3d::Zero();
+    Vec3d m_mouse_normal_world   = Vec3d::Zero();
+
+    Vec3d m_cut_plane_dir = Vec3d::UnitZ();
+
+    std::vector<Vec3d> m_position_points;
+    std::vector<Vec3d> m_normal_points;
+
+    // This map holds all translated description texts, so they can be easily referenced during layout calculations
+    // etc. When language changes, GUI is recreated and this class constructed again, so the change takes effect.
+    std::map<std::string, wxString> m_desc;
+
+public:
+    GLGizmoText(GLCanvas3D& parent, const std::string& icon_filename, unsigned int sprite_id);
+    ~GLGizmoText();
+
+    void update_font_texture();
+
+    bool gizmo_event(SLAGizmoEventType action, const Vec2d &mouse_position, bool shift_down, bool alt_down, bool control_down);
+
+    bool on_mouse(const wxMouseEvent &mouse_event) override;
+
+    bool is_mesh_point_clipped(const Vec3d &point, const Transform3d &trafo) const;
+    BoundingBoxf3 bounding_box() const;
+
+protected:
+    virtual bool on_init() override;
+    virtual std::string on_get_name() const override;
+    virtual bool on_is_activable() const override;
+    virtual void on_render() override;
+    virtual void on_dragging(const UpdateData &data) override;
+    void push_combo_style(const float scale);
+    void pop_combo_style();
+    void push_button_style(bool pressed);
+    void pop_button_style();
+    virtual void on_set_state() override;
+    virtual CommonGizmosDataID on_get_requirements() const override;
+    virtual void on_render_input_window(float x, float y, float bottom_limit);
+    virtual void on_register_raycasters_for_picking() override;
+    virtual void on_unregister_raycasters_for_picking() override;
+
+    void show_tooltip_information(float x, float y);
+
+private:
+    ModelVolume *get_selected_single_volume(int& out_object_idx, int& out_volume_idx) const;
+    void reset_text_info();
+    bool update_text_positions(const std::vector<std::string>& texts);
+    TriangleMesh get_text_mesh(const char* text_str, const Vec3d &position, const Vec3d &normal, const Vec3d &text_up_dir);
+
+    bool update_raycast_cache(const Vec2d &mouse_position, const Camera &camera, const std::vector<Transform3d> &trafo_matrices);
+    void generate_text_volume(bool is_temp = true);
+    void delete_temp_preview_text_volume();
+
+    TextInfo get_text_info();
+    void     load_from_text_info(const TextInfo &text_info);
+};
+
+} // namespace GUI
+} // namespace Slic3r
+
+#endif // slic3r_GLGizmoText_hpp_

src/slic3r/GUI/Gizmos/GLGizmos.hpp

@@ -0,0 +1,41 @@
+#ifndef slic3r_GLGizmos_hpp_
+#define slic3r_GLGizmos_hpp_
+
+// this describes events being passed from GLCanvas3D to SlaSupport gizmo
+namespace Slic3r {
+namespace GUI {
+
+enum class SLAGizmoEventType : unsigned char {
+    LeftDown = 1,
+    LeftUp,
+    RightDown,
+    Dragging,
+    Delete,
+    SelectAll,
+    ShiftUp,
+    AltUp,
+    ApplyChanges,
+    DiscardChanges,
+    AutomaticGeneration,
+    ManualEditing,
+    MouseWheelUp,
+    MouseWheelDown,
+    ResetClippingPlane
+};
+
+} // namespace GUI
+} // namespace Slic3r
+
+// BBS
+#include "slic3r/GUI/Gizmos/GLGizmoMoveScale.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoRotate.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoFlatten.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoSlaSupports.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoFdmSupports.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoFuzzySkin.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoMmuSegmentation.hpp"
+// BBS
+#include "slic3r/GUI/Gizmos/GLGizmoAdvancedCut.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoHollow.hpp"
+
+#endif //slic3r_GLGizmos_hpp_

src/slic3r/Utils/ProfileDescription.hpp

@@ -0,0 +1,60 @@
+#include <I18N.hpp>
+#include <wx/string.h>
+#ifndef _L
+#define _L(s) Slic3r::I18N::translate(s)
+#endif
+
+namespace ProfileDescrption {
+    const std::string PROFILE_DESCRIPTION_0  = _L("It has a small layer height. This results in almost negligible layer lines and high print quality. It is suitable for most printing cases.");
+    const std::string PROFILE_DESCRIPTION_1  = _L("Compared with the default profile of a 0.2 mm nozzle, it has lower speeds and acceleration, and the sparse infill pattern is Gyroid. This results in much higher print quality but a much longer print time.");
+    const std::string PROFILE_DESCRIPTION_2  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a slightly bigger layer height. This results in almost negligible layer lines and slightly shorter print time.");
+    const std::string PROFILE_DESCRIPTION_3  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a bigger layer height. This results in slightly visible layer lines but shorter print time.");
+    const std::string PROFILE_DESCRIPTION_4  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a smaller layer height. This results in almost invisible layer lines and higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_5  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a smaller layer lines, lower speeds and acceleration, and the sparse infill pattern is Gyroid. This results in almost invisible layer lines and much higher print quality but much longer print time.");
+    const std::string PROFILE_DESCRIPTION_6  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a smaller layer height. This results in minimal layer lines and higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_7  = _L("Compared with the default profile of a 0.2 mm nozzle, it has a smaller layer lines, lower speeds and acceleration, and the sparse infill pattern is Gyroid. This results in minimal layer lines and much higher print quality but much longer print time.");
+    const std::string PROFILE_DESCRIPTION_8  = _L("It has a normal layer height. This results in average layer lines and print quality. It is suitable for most printing cases.");
+    const std::string PROFILE_DESCRIPTION_9  = _L("Compared with the default profile of a 0.4 mm nozzle, it has more wall loops and a higher sparse infill density. This results in higher print strength but more filament consumption and longer print time.");
+    const std::string PROFILE_DESCRIPTION_10 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a bigger layer height. This results in more apparent layer lines and lower print quality, but slightly shorter print time.");
+    const std::string PROFILE_DESCRIPTION_11 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a bigger layer height. This results in more apparent layer lines and lower print quality, but shorter print time.");
+    const std::string PROFILE_DESCRIPTION_12 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a smaller layer height. This results in less apparent layer lines and higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_13 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a smaller layer height, lower speeds and acceleration, and the sparse infill pattern is Gyroid. This results in less apparent layer lines and much higher print quality but much longer print time.");
+    const std::string PROFILE_DESCRIPTION_14 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a smaller layer height. This results in almost negligible layer lines and higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_15 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a smaller layer height, lower speeds and acceleration, and the sparse infill pattern is Gyroid. This results in almost negligible layer lines and much higher print quality but much longer print time.");
+    const std::string PROFILE_DESCRIPTION_16 = _L("Compared with the default profile of a 0.4 mm nozzle, it has a smaller layer height. This results in almost negligible layer lines and longer print time.");
+    const std::string PROFILE_DESCRIPTION_17 = _L("It has a big layer height. This results in apparent layer lines and ordinary print quality and print time.");
+    const std::string PROFILE_DESCRIPTION_18 = _L("Compared with the default profile of a 0.6 mm nozzle, it has more wall loops and a higher sparse infill density. This results in higher print strength but more filament consumption and longer print time.");
+    const std::string PROFILE_DESCRIPTION_19 = _L("Compared with the default profile of a 0.6 mm nozzle, it has a bigger layer height. This results in more apparent layer lines and lower print quality, but shorter print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_20 = _L("Compared with the default profile of a 0.6 mm nozzle, it has a bigger layer height. This results in much more apparent layer lines and much lower print quality, but shorter print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_21 = _L("Compared with the default profile of a 0.6 mm nozzle, it has a smaller layer height. This results in less apparent layer lines and slight higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_22 = _L("Compared with the default profile of a 0.6 mm nozzle, it has a smaller layer height. This results in less apparent layer lines and higher print quality but longer print time.");
+    const std::string PROFILE_DESCRIPTION_23 = _L("It has a very big layer height. This results in very apparent layer lines, low print quality and shorter print time.");
+    const std::string PROFILE_DESCRIPTION_24 = _L("Compared with the default profile of a 0.8 mm nozzle, it has a bigger layer height. This results in very apparent layer lines and much lower print quality, but shorter print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_25 = _L("Compared with the default profile of a 0.8 mm nozzle, it has a much bigger layer height. This results in extremely apparent layer lines and much lower print quality, but much shorter print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_26 = _L("Compared with the default profile of a 0.8 mm nozzle, it has a slightly smaller layer height. This results in slightly less but still apparent layer lines and slightly higher print quality but longer print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_27 = _L("Compared with the default profile of a 0.8 mm nozzle, it has a smaller layer height. This results in less but still apparent layer lines and slightly higher print quality but longer print time in some cases.");
+    const std::string PROFILE_DESCRIPTION_28 = _L("This is neither a commonly used filament, nor one of Bambu filaments, and it varies a lot from brand to brand. So, it's highly recommended to ask its vendor for suitable profile before printing and adjust some parameters according to its performances.");
+    const std::string PROFILE_DESCRIPTION_29 = _L("When printing this filament, there's a risk of warping and low layer adhesion strength. To get better results, please refer to this wiki: Printing Tips for High Temp / Engineering materials.");
+    const std::string PROFILE_DESCRIPTION_30 = _L("When printing this filament, there's a risk of nozzle clogging, oozing, warping and low layer adhesion strength. To get better results, please refer to this wiki: Printing Tips for High Temp / Engineering materials.");
+    const std::string PROFILE_DESCRIPTION_31 = _L("To get better transparent or translucent results with the corresponding filament, please refer to this wiki: Printing tips for transparent PETG.");
+    const std::string PROFILE_DESCRIPTION_32 = _L("To make the prints get higher gloss, please dry the filament before use, and set the outer wall speed to be 40 to 60 mm/s when slicing.");
+    const std::string PROFILE_DESCRIPTION_33 = _L("This filament is only used to print models with a low density usually, and some special parameters are required. To get better printing quality, please refer to this wiki: Instructions for printing RC model with foaming PLA (PLA Aero).");
+    const std::string PROFILE_DESCRIPTION_34 = _L("This filament is only used to print models with a low density usually, and some special parameters are required. To get better printing quality, please refer to this wiki: ASA Aero Printing Guide.");
+    const std::string PROFILE_DESCRIPTION_35 = _L("This filament is too soft and not compatible with the AMS. Printing it is of many requirements, and to get better printing quality, please refer to this wiki: TPU printing guide.");
+    const std::string PROFILE_DESCRIPTION_36 = _L("This filament has high enough hardness (about 67D)  and is compatible with the AMS. Printing it is of many requirements, and to get better printing quality, please refer to this wiki: TPU printing guide.");
+    const std::string PROFILE_DESCRIPTION_37 = _L("If you are to print a kind of soft TPU, please don't slice with this profile, and it is only for TPU that has high enough hardness (not less than 55D) and is compatible with the AMS. To get better printing quality, please refer to this wiki: TPU printing guide.");
+    const std::string PROFILE_DESCRIPTION_38 = _L("This is a water-soluble support filament, and usually it is only for the support structure and not for the model body. Printing this filament is of many requirements, and to get better printing quality, please refer to this wiki: PVA Printing Guide.");
+    const std::string PROFILE_DESCRIPTION_39 = _L("This is a non-water-soluble support filament, and usually it is only for the support structure and not for the model body. To get better printing quality, please refer to this wiki: Printing Tips for Support Filament and Support Function.");
+    const std::string PROFILE_DESCRIPTION_40 = _L("The generic presets are conservatively tuned for compatibility with a wider range of filaments. For higher printing quality and speeds, please use Bambu filaments with Bambu presets.");
+    const std::string PROFILE_DESCRIPTION_41 = _L("High quality profile for 0.2mm nozzle, prioritizing print quality.");
+    const std::string PROFILE_DESCRIPTION_42 = _L("High quality profile for 0.16mm layer height, prioritizing print quality and strength.");
+    const std::string PROFILE_DESCRIPTION_43 = _L("Standard profile for 0.16mm layer height, prioritizing speed.");
+    const std::string PROFILE_DESCRIPTION_44 = _L("High quality profile for 0.2mm layer height, prioritizing strength and print quality.");
+    const std::string PROFILE_DESCRIPTION_45 = _L("Standard profile for 0.4mm nozzle, prioritizing speed.");
+    const std::string PROFILE_DESCRIPTION_46 = _L("High quality profile for 0.6mm nozzle, prioritizing print quality and strength.");
+    const std::string PROFILE_DESCRIPTION_47 = _L("Strength profile for 0.6mm nozzle, prioritizing strength.");
+    const std::string PROFILE_DESCRIPTION_48 = _L("Standard profile for 0.6mm nozzle, prioritizing speed.");
+    const std::string PROFILE_DESCRIPTION_49 = _L("High quality profile for 0.8mm nozzle, prioritizing print quality.");
+    const std::string PROFILE_DESCRIPTION_50 = _L("Strength profile for 0.8mm nozzle, prioritizing strength.");
+    const std::string PROFILE_DESCRIPTION_51 = _L("Standard profile for 0.8mm nozzle, prioritizing speed.");
+}

tests/libslic3r/CMakeLists.txt

@@ -30,6 +30,7 @@ add_executable(${_TEST_NAME}_tests
     test_filament_mixer.cpp
     test_fill_plane_path.cpp
     test_geometry.cpp
+    test_kdtree.cpp
     test_multimaterial_segmentation.cpp
     test_placeholder_parser.cpp
     test_polygon.cpp

tests/libslic3r/test_clipper_utils.cpp

@@ -7,6 +7,7 @@
 #include "libslic3r/libslic3r.h"
 #include <numeric>
 #include <iostream>
+#include <utility>
 #include <boost/filesystem.hpp>
 #include <vector>
 
@@ -299,3 +300,90 @@ TEST_CASE("Top level expolygons of an even-odd union", "[ClipperUtils]") {
     REQUIRE(area_sum == Catch::Approx(area(top_level) + area(nested)));
     REQUIRE(top_level_expolygons(reference).size() == 1);
 }
+
+// Rings flattened to x,y,x,y... and sorted, with each ring rotated to start at its lowest point: two
+// encodings of the same geometry compare equal however the pieces came back or wherever a ring started.
+static std::vector<std::vector<coord_t>> canonical_rings(const ExPolygons &expolygons)
+{
+    std::vector<std::vector<coord_t>> rings;
+    const auto add = [&rings](const Polygon &poly) {
+        if (poly.points.empty())
+            return;
+        Points pts = poly.points;
+        std::rotate(pts.begin(),
+                    std::min_element(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
+                        return std::make_pair(a.x(), a.y()) < std::make_pair(b.x(), b.y());
+                    }),
+                    pts.end());
+        std::vector<coord_t> flat;
+        flat.reserve(pts.size() * 2);
+        for (const Point &p : pts) {
+            flat.emplace_back(p.x());
+            flat.emplace_back(p.y());
+        }
+        rings.emplace_back(std::move(flat));
+    };
+    for (const ExPolygon &expoly : expolygons) {
+        add(expoly.contour);
+        for (const Polygon &hole : expoly.holes)
+            add(hole);
+    }
+    std::sort(rings.begin(), rings.end());
+    return rings;
+}
+
+// The same rings, every coordinate within `tolerance`.
+static bool same_rings(const ExPolygons &a, const ExPolygons &b, coord_t tolerance)
+{
+    const std::vector<std::vector<coord_t>> ra = canonical_rings(a), rb = canonical_rings(b);
+    return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(), [tolerance](const std::vector<coord_t> &x, const std::vector<coord_t> &y) {
+        return std::equal(x.begin(), x.end(), y.begin(), y.end(), [tolerance](coord_t u, coord_t v) { return std::abs(u - v) <= tolerance; });
+    });
+}
+
+TEST_CASE("Tiled diff and intersection return the same polygons as the plain calls", "[ClipperUtils]") {
+    // A grid of disjoint framed squares, enough of them to be split into several tiles.
+    const int  n    = 40;
+    const coord_t cell = scaled<coord_t>(2.), side = scaled<coord_t>(1.5), frame = scaled<coord_t>(0.3);
+    ExPolygons subject;
+    for (int y = 0; y < n; ++ y)
+        for (int x = 0; x < n; ++ x) {
+            const Point o(x * cell, y * cell);
+            ExPolygon square(Polygon({ o, o + Point(side, 0), o + Point(side, side), o + Point(0, side) }));
+            Polygon hole({ o + Point(frame, frame), o + Point(frame, side - frame), o + Point(side - frame, side - frame), o + Point(side - frame, frame) });
+            square.holes.emplace_back(std::move(hole));
+            subject.emplace_back(std::move(square));
+        }
+    // Clip polygons crossing many squares, one of them large with holes of its own.
+    Polygons clip;
+    const coord_t span = n * cell;
+    for (int i = 0; i < 8; ++ i) {
+        const coord_t y0 = coord_t(i) * span / 8, y1 = y0 + scaled<coord_t>(0.9);
+        clip.emplace_back(Polygon({ Point(- cell, y0), Point(span, y0 + cell * 3), Point(span, y1 + cell * 3), Point(- cell, y1) }));
+    }
+    ExPolygon big(Polygon({ Point(span / 4, span / 4), Point(3 * span / 4, span / 4), Point(3 * span / 4, 3 * span / 4), Point(span / 4, 3 * span / 4) }));
+    for (int i = 0; i < 4; ++ i) {
+        const Point o(span / 4 + scaled<coord_t>(3.1) + i * scaled<coord_t>(9.7), span / 4 + scaled<coord_t>(5.3));
+        big.holes.emplace_back(Polygon({ o, o + Point(0, scaled<coord_t>(20.)), o + Point(scaled<coord_t>(5.), scaled<coord_t>(20.)), o + Point(scaled<coord_t>(5.), 0) }));
+    }
+    polygons_append(clip, to_polygons(big));
+
+    const ApplySafetyOffset safety = GENERATE(ApplySafetyOffset::No, ApplySafetyOffset::Yes);
+
+    // The point of the fixture: below 128 pieces the helpers fall back to a single tile and the tiled
+    // path under test is never taken.
+    REQUIRE(ClipperUtils::tile_expolygons(subject, 32).size() > 1);
+
+    // With the safety offset a tile unites fewer clip polygons, so Clipper2 can round a crossing 1 unit differently.
+    const coord_t tolerance = safety == ApplySafetyOffset::Yes ? 1 : 0;
+
+    const ExPolygons diff_plain = diff_ex(subject, clip, safety);
+    const ExPolygons diff_tiled = diff_ex_by_piece(subject, clip, safety);
+    REQUIRE(area(diff_plain) > 0.);
+    CHECK(same_rings(diff_tiled, diff_plain, tolerance));
+
+    const ExPolygons intersection_plain = intersection_ex(subject, clip, safety);
+    const ExPolygons intersection_tiled = intersection_ex_by_piece(subject, clip, safety);
+    REQUIRE(area(intersection_plain) > 0.);
+    CHECK(same_rings(intersection_tiled, intersection_plain, tolerance));
+}

tests/libslic3r/test_kdtree.cpp

@@ -0,0 +1,67 @@
+#include <catch2/catch_all.hpp>
+
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include "libslic3r/KDTreeIndirect.hpp"
+#include "libslic3r/Point.hpp"
+
+using namespace Slic3r;
+
+TEST_CASE("Visiting the nearby points gives what collecting them gives", "[KDTree]") {
+    std::mt19937                          rng(19937);
+    std::uniform_real_distribution<float> coord(-50.f, 50.f);
+    // Points in a box, so that a radius search returns anything from none of them to all of them.
+    std::vector<Vec3f> points(2000);
+    for (Vec3f &p : points)
+        p = Vec3f(coord(rng), coord(rng), coord(rng));
+
+    auto coordinate = [&points](size_t idx, size_t dimension) { return points[idx](int(dimension)); };
+    KDTreeIndirect<3, float, decltype(coordinate)> tree(coordinate);
+    std::vector<size_t> indices(points.size());
+    std::iota(indices.begin(), indices.end(), 0);
+    tree.build(indices);
+
+    const float radius = GENERATE(0.5f, 5.f, 25.f, 200.f);
+    for (int i = 0; i < 20; ++ i) {
+        const Vec3f center(coord(rng), coord(rng), coord(rng));
+
+        const std::vector<size_t> collected = find_nearby_points(tree, center, radius);
+        std::vector<size_t>       visited;
+        visit_nearby_points(tree, center, radius, [&visited](size_t idx) { visited.emplace_back(idx); });
+
+        // Same points, and in the same order: a caller that keeps the first of several equally good ones
+        // must get the same answer either way.
+        REQUIRE(visited == collected);
+    }
+}
+
+TEST_CASE("A radius search returns every point within the radius and no other", "[KDTree]") {
+    std::mt19937                          rng(2024);
+    std::uniform_real_distribution<float> coord(-20.f, 20.f);
+    std::vector<Vec3f> points(500);
+    for (Vec3f &p : points)
+        p = Vec3f(coord(rng), coord(rng), coord(rng));
+
+    auto coordinate = [&points](size_t idx, size_t dimension) { return points[idx](int(dimension)); };
+    KDTreeIndirect<3, float, decltype(coordinate)> tree(coordinate);
+    std::vector<size_t> indices(points.size());
+    std::iota(indices.begin(), indices.end(), 0);
+    tree.build(indices);
+
+    const Vec3f center(1.f, -2.f, 3.f);
+    const float radius = 7.f;
+
+    std::vector<size_t> expected;
+    for (size_t i = 0; i < points.size(); ++ i)
+        if ((points[i] - center).squaredNorm() < radius * radius)
+            expected.emplace_back(i);
+
+    std::vector<size_t> visited;
+    visit_nearby_points(tree, center, radius, [&visited](size_t idx) { visited.emplace_back(idx); });
+    std::sort(visited.begin(), visited.end());
+
+    REQUIRE(! expected.empty());
+    REQUIRE(visited == expected);
+}