Reject Paths with an Embedded NUL When Confining Extraction

is_path_within_root compared each component with "..", so a name such
as "..\0" passed the check. The filesystem calls stop at the NUL and
act on a shorter path than the one that was checked: a symlink target
read from a plugin archive as raw bytes was created as "..", pointing
out of the plugin directory.

A path containing a NUL is now rejected before anything touches the
filesystem, which covers every caller, including entry names taken from
the Unicode Path extra field.

src/libslic3r/ClipperUtils.cpp

@@ -1,11 +1,7 @@
-#include <algorithm>
-#include <cmath>
 #include <limits>
 #include <numeric>
 #include <unordered_map>
 
-#include <tbb/parallel_for.h>
-
 #include "ClipperUtils.hpp"
 #include "Geometry.hpp"
 #include "ShortestPath.hpp"
@@ -817,69 +813,6 @@ Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r
     { return _clipper_ex(ClipperLib::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(ClipperLib::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(ClipperLib::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 ClipperLib call with the clip cut to the tile's box.
-    const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(subject, 32);
-    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(ClipperLib::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(ClipperLib::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, ClipperLib::PolyFillType fill_type)
     { return _clipper_ex(ClipperLib::ctUnion, ClipperUtils::PolygonsProvider(subject), ClipperUtils::EmptyPathsProvider(), ApplySafetyOffset::No, fill_type); }

src/libslic3r/ClipperUtils.hpp

@@ -2,7 +2,6 @@
 #define slic3r_ClipperUtils_hpp_
 
 #include "libslic3r.h"
-#include "BoundingBox.hpp"
 #include "clipper.hpp"
 #include "ExPolygon.hpp"
 #include "Polygon.hpp"
@@ -322,15 +321,6 @@ 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 ClipperLib 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);
-
     }
 
 // Perform union of input polygons using the non-zero rule, convert to ExPolygons.
@@ -528,11 +518,6 @@ 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: ClipperLib 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

@@ -9,8 +9,6 @@
 #include "../PrintConfig.hpp"
 #include "../Surface.hpp"
 
-#include <tbb/parallel_for.h>
-
 #include "AABBTreeLines.hpp"
 #include "ExtrusionEntity.hpp"
 #include "Fill.hpp"
@@ -632,28 +630,24 @@ 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);
 
-        // Each expolygon is split on its own, so they run in parallel and are collected in their original order.
+        for (const ExPolygon &expolygon : fill.expolygons) {
-        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()) {
-                split_parts[idx].second.emplace_back(expolygon);
+                narrow_infill.emplace_back(expolygon);
-                return;
+                continue;
             }
 
             ExPolygons inner_ex = union_ex(inner_area);
             ExPolygons expolys{expolygon};
-            split_parts[idx].second = diff_ex(expolys, inner_ex);         // narrow infill area
+            ExPolygons narrow_ex = diff_ex(expolys, inner_ex);
-            split_parts[idx].first  = intersection_ex(expolys, inner_ex); // normal infill area
+            ExPolygons normal_ex = intersection_ex(expolys, inner_ex);
-        });
+
-        for (auto &[normal_ex, narrow_ex] : split_parts) {
+            append(normal_infill, normal_ex); // normal infill area
-            append(normal_infill, std::move(normal_ex));
+            append(narrow_infill, narrow_ex); // narrow infill area
-            append(narrow_infill, std::move(narrow_ex));
         }
 
         return;
@@ -675,10 +669,7 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
     }
     const double aligning_angle = -base_angle + PI;
 
-    // Each expolygon is reconstructed on its own, so they run in parallel and are collected in their original order.
+	for (const ExPolygon &expolygon : fill.expolygons) {
-    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);
@@ -809,10 +800,8 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
             }
         }
 
-        split_reconstructed[expolygon_idx] = std::move(reconstructed_area);
+        polygons_append(normal_fill_areas, reconstructed_area);
-    });
+    }
-    for (Polygons &reconstructed_area : split_reconstructed)
-        polygons_append(normal_fill_areas, std::move(reconstructed_area));
 
     polygons_rotate(normal_fill_areas, -aligning_angle);
 
@@ -1420,15 +1409,7 @@ 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));
 
-            // Only the part of the layer-wide no-overlap area under this expolygon matters, so clip it to the
+            f->no_overlap_expolygons = intersection_ex(surface_fill.no_overlap_expolygons, ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
-            // 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

@@ -10,7 +10,6 @@
 #include <limits>
 #include <numeric>
 #include <unordered_map>
-#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -135,79 +134,15 @@ 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; with thousands of islands on a layer the all-pairs
-    // scan, repeated after every reversal, never finished. Rebuilding the grid costs more than it saves on small inputs.
-    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);
     bool improved = false;
-    // Reversing between two segments that only touch or overlap along a line need not remove the intersection, and on
-    // islands laid out on a regular grid (a tiled texture, an array of parts) the loop cycled through the same orderings
-    // until the pn * pn cap - effectively forever. Stop as soon as an ordering repeats: until then this is the same loop.
-    std::unordered_set<uint64_t> seen_paths;
-    const auto path_hash = [&path]() {
-        uint64_t h = 1469598103934665603ull; // FNV-1a
-        for (size_t idx : path)
-            h = (h ^ uint64_t(idx)) * 1099511628211ull;
-        return h;
-    };
-    seen_paths.insert(path_hash());
     while (max_iters-- > 0) {
-        auto [ci, cj] = pn >= grid_min_size ? find_crossing_grid() : find_crossing();
+        auto [ci, cj] = find_crossing();
         if (ci == std::numeric_limits<size_t>::max()) break;
         improved = true;
         std::reverse(path.begin() + ci + 1, path.begin() + cj + 1);
-        if (!seen_paths.insert(path_hash()).second)
-            break;
     }
     return improved;
 }

src/libslic3r/GCode/SeamPlacer.cpp

@@ -8,7 +8,6 @@
 #include <boost/log/trivial.hpp>
 #include <random>
 #include <algorithm>
-#include <limits>
 #include <queue>
 #include <unordered_map>
 
@@ -1179,21 +1178,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;
-  // Find the best nearby point and the nearest one. A layer of a fine relief has tens of thousands of candidates within
+  std::vector<size_t> nearby_points_indices = find_nearby_points(*layers[layer_idx].points_tree, projected_position,
-  // the radius, so they are looked at as the search finds them rather than collected into a vector first.
+                                                                 max_distance);
-  constexpr size_t none = std::numeric_limits<size_t>::max();
+
-  size_t best_nearby_point_index = none;
+  if (nearby_points_indices.empty()) {
-  size_t nearest_point_index = none;
+    return {};
-  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) {
+  size_t best_nearby_point_index = nearby_points_indices[0];
-    if (best_nearby_point_index == none) {
+  size_t nearest_point_index = nearby_points_indices[0];
-      // The first point found starts both, as the first of the collected ones did.
+
-      best_nearby_point_index = nearest_point_index = nearby_point_index;
+  // Now find best nearby point, nearest point, and corresponding indices
-    }
+  for (const size_t &nearby_point_index : nearby_points_indices) {
     const SeamCandidate &point = layers[layer_idx].points[nearby_point_index];
     if (point.perimeter.finalized) {
-      return; // skip over finalized perimeters, try to find some that is not finalized
+      continue; // 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>())
@@ -1205,10 +1204,6 @@ 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

@@ -313,36 +313,6 @@ 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

@@ -72,11 +72,10 @@ 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_by_piece(to_expolygons(this_surfaces), fill_boundaries), SurfaceType(surface_type));
+            this->fill_surfaces.append(intersection_ex(this_surfaces, this->fill_expolygons), SurfaceType(surface_type));
     }
 }
 

src/libslic3r/MultiMaterialSegmentation.cpp

@@ -8,7 +8,6 @@
 #include "MutablePolygon.hpp"
 #include "format.hpp"
 
-#include <numeric>
 #include <utility>
 #include <unordered_set>
 
@@ -1312,15 +1311,10 @@ 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.
     {
-        const size_t occluded_pairs = num_facets_states * layers.size();
+        for (size_t extruder_idx = 0; extruder_idx < num_facets_states; ++extruder_idx) {
-        tbb::parallel_for(tbb::blocked_range<size_t>(0, occluded_pairs), [&](const tbb::blocked_range<size_t> &range) {
+            for (size_t layer_idx = 0; layer_idx < layers.size(); ++layer_idx) {
-            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]);
                 }
@@ -1328,7 +1322,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);
@@ -1384,62 +1378,13 @@ 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 ClipperLib 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, std::vector<ExPolygons> &dst, size_t dst_offset) {
-        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) {
-            bool empty = true;
-            for (ExPolygons &shell : shells[i])
-                if (! shell.empty()) {
-                    append(dst[shell_layers[i] + dst_offset], std::move(shell));
-                    empty = false;
-                }
-            if (empty)
-                break;
-        }
-    };
-
     tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers, granularity), [&granularity, &num_layers, &num_facets_states, &layer_color_stat, &top_raw, &triangles_by_color_top,
-                                                                               &throw_on_cancel_callback, &bottom_raw, &triangles_by_color_bottom, &project_to_shells,
+                                                                               &throw_on_cancel_callback, &input_expolygons, &bottom_raw, &triangles_by_color_bottom,
                                                                                &shell_triangles_by_color_top, &shell_triangles_by_color_bottom](const tbb::blocked_range<size_t> &range) {
         size_t group_idx   = range.begin() / granularity;
         size_t layer_idx_offset = (group_idx & 1) * num_layers;
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
-            // Each colour writes only its own vectors, so the colours run in parallel: a painted top or bottom face
+            for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx) {
-            // 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())
@@ -1448,10 +1393,18 @@ 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 + layer_idx_offset], top_ex);
-                            std::vector<size_t> shell_layers;
+                            float offset = 0.f;
-                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx)
+                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
-                                shell_layers.emplace_back(size_t(last_idx));
+                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx) {
-                            project_to_shells(top_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_top[color_idx], layer_idx_offset);
+                                //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;
+                                append(shell_triangles_by_color_top[color_idx][last_idx + layer_idx_offset], std::move(last));
+                            }
                         }
                     }
                 if (std::vector<Polygons> &bottom = bottom_raw[color_idx]; ! bottom.empty() && ! bottom[layer_idx].empty())
@@ -1460,13 +1413,21 @@ 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 + layer_idx_offset], bottom_ex);
-                            std::vector<size_t> shell_layers;
+                            float offset = 0.f;
-                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx)
+                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
-                                shell_layers.emplace_back(last_idx);
+                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx) {
-                            project_to_shells(bottom_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_bottom[color_idx], layer_idx_offset);
+                                //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;
+                                append(shell_triangles_by_color_bottom[color_idx][last_idx + layer_idx_offset], std::move(last));
+                            }
                         }
                     }
-            });
+            }
         }
     });
 
@@ -1476,25 +1437,22 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                                                                   &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) {
             throw_on_cancel_callback();
-            // The per-colour unions below are independent of each other, so they run in parallel (a painted top or
+            ExPolygons painted_exploys;
-            // bottom face puts all of its colours on one layer); whatever combines the colours stays in colour order.
+            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
-            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_bottom[color_idx][layer_idx + num_layers]));
                 append(self, std::move(triangles_by_color_top[color_idx][layer_idx]));
                 append(self, std::move(triangles_by_color_top[color_idx][layer_idx + num_layers]));
                 self = union_ex(self);
-            };
-            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), merge_colour_union);
 
-            ExPolygons painted_exploys;
+                append(painted_exploys, self);
-            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
-            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), [&](size_t color_idx) {
+            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
                 auto &self = triangles_by_color_merged[color_idx][layer_idx];
 
                 auto top_area = diff_ex(union_ex(shell_triangles_by_color_top[color_idx][layer_idx],
@@ -1508,7 +1466,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) {
@@ -1875,69 +1833,7 @@ 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)
@@ -1948,91 +1844,33 @@ 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";
-    // Every region of a layer is merged together with the regions of the islands it overlaps, and the islands are further
+    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) {
-    // 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 ClipperLib, 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);
-            throw_on_cancel_callback();
+            // Zero is skipped because it is the default color of the volume
-            // 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) {
-                if (top_and_bottom_layers.empty() || top_and_bottom_layers[extruder_id][layer_idx].empty()) {
+                throw_on_cancel_callback();
-                    for (size_t bucket = 0; bucket < num_buckets; ++bucket)
+                if (!segmented_regions[layer_idx][extruder_id].empty()) {
-                        append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
+                    ExPolygons segmented_regions_trimmed = segmented_regions[layer_idx][extruder_id];
-                    continue;
+                    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));
                 }
-                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
@@ -2319,56 +2157,16 @@ std::vector<std::vector<ExPolygons>> segmentation_by_painting(const PrintObject
 
                 assert(!color_poly.empty());
                 assert(!color_poly.front().empty());
-                // Each island (an ExPolygon with its holes) is segmented on its own. Any point of an island is closer to
+                if (has_layer_only_one_color(color_poly)) {
-                // that island's contours than to any other island's - the way out crosses its own boundary first - so its
+                    // 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.
-                // Voronoi cells, and with them its colour regions, depend on nothing else. A layer cut through a fine relief
+                    segmented_regions[layer_idx][size_t(color_poly.front().front().color)] = input_expolygons[layer_idx];
-                // has thousands of islands, and one Voronoi diagram over all of them degenerated into overlapping regions
+                } else {
-                // that every boolean afterwards had to untangle. Per island the diagrams stay small and the islands run in
+                    MMU_Graph graph = build_graph(layer_idx, color_poly);
-                // parallel; an island in a single colour needs no diagram at all.
+                    remove_multiple_edges_in_vertices(graph, color_poly);
-                const ExPolygons                      &islands = input_expolygons[layer_idx];
+                    graph.remove_nodes_with_one_arc();
-                std::vector<std::pair<size_t, size_t>> island_contours(islands.size()); // [first, last) into color_poly
+                    segmented_regions[layer_idx] = extract_colored_segments(graph, num_facets_states);
-                {
+                    //segmented_regions[layer_idx] = extract_colored_segments(color_poly, num_extruders, layer_idx);
-                    // 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]);
@@ -2391,7 +2189,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(input_expolygons, 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(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

@@ -19,13 +19,11 @@ public:
     
     MultiPoint() {}
     MultiPoint(const MultiPoint &other) : points(other.points) {}
-    MultiPoint(MultiPoint &&other) noexcept : points(std::move(other.points)) {}
+    MultiPoint(MultiPoint &&other) : 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.
-    explicit MultiPoint(Points &&_points) noexcept : points(std::move(_points)) {}
     MultiPoint& operator=(const MultiPoint &other) { points = other.points; return *this; }
-    MultiPoint& operator=(MultiPoint &&other) noexcept { points = std::move(other.points); return *this; }
+    MultiPoint& operator=(MultiPoint &&other) { 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

@@ -17,8 +17,6 @@
 #include <cassert>
 #include <unordered_set>
 #include <thread>
-#include <tbb/blocked_range.h>
-#include <tbb/parallel_for.h>
 #include "libslic3r/AABBTreeLines.hpp"
 #include "Print.hpp"
 static const int overhang_sampling_number = 6;
@@ -2483,443 +2481,421 @@ 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
-    // Each island is independent up to its outputs, so they are generated in parallel - a layer split into thousands
+    for (const Surface& surface : all_surfaces) {
-    // of islands (e.g. by colour painting) otherwise ran on one thread - and the outputs are then committed in the
+        coord_t bead_width_0 = ext_perimeter_spacing;
-    // original island order, which is what the extra overhang perimeters (applied to the last island's loops and to
+        // detect how many perimeters must be generated for this island
-    // all fill surfaces so far) depend on.
+        int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
-    struct ArachneSurfaceResult
+        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
-        ExtrusionEntityCollection loops;
+            loop_number++;
-        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
+        // Set the bottommost layer to be one wall
-            const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
+        const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
-            if (is_bottom_layer && only_one_wall_first_layer)
+        if (is_bottom_layer && only_one_wall_first_layer)
-                loop_number = 0;
+            loop_number = 0;
 
-            // Orca: set the topmost layer to be one wall according to the config
+        // Orca: set the topmost layer to be one wall according to the config
-            const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
+        const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
-            if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
+        if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
-                loop_number = 0;
+            loop_number = 0;
         
-            auto apply_precise_outer_wall = config->precise_outer_wall && config->wall_sequence == WallSequence::InnerOuter;
+        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.
+        // 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),
+        ExPolygons last = offset_ex(surface.expolygon.simplify_p(surface_simplify_resolution),
-                           apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
+                       apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
-                                                     : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
+                                                 : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
         
-            Arachne::WallToolPathsParams input_params = Arachne::make_paths_params(this->layer_id, *object_config, *print_config);
+        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.
+        // 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;
+        input_params.is_top_or_bottom_layer = (is_bottom_layer || is_topmost_layer) ? true : false;
 
-            coord_t wall_0_inset = 0;
+        coord_t wall_0_inset = 0;
-            if (apply_precise_outer_wall)
+        if (apply_precise_outer_wall)
-               wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
+           wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
 
-            //PS: One wall top surface for Arachne
+        //PS: One wall top surface for Arachne
-            ExPolygons top_expolygons;
+        ExPolygons top_expolygons;
-            // Calculate how many inner loops remain when TopSurfaces is selected.
+        // 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;
+        const int inner_loop_number = (only_one_wall_top && upper_slices != nullptr) ? loop_number - 1 : -1;
 
-            // Set one perimeter when TopSurfaces is selected.
+        // Set one perimeter when TopSurfaces is selected.
-            if (only_one_wall_top && loop_number > 0)
+        if (only_one_wall_top && loop_number > 0)
-                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);
+        Polygons   last_p = to_polygons(last);
-            Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
+        Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
-                                                   wall_0_inset, layer_height, input_params_tmp);
+                                               wall_0_inset, layer_height, input_params_tmp);
-            std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
+        std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
-            ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
+        ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
 
-            // Check if there are some remaining perimeters to generate (the number of perimeters
+        // 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).
+        // is greater than one together with enabled the single perimeter on top surface feature).
-            if (inner_loop_number >= 0) {
+        if (inner_loop_number >= 0) {
-                assert(upper_slices != nullptr);
+            assert(upper_slices != nullptr);
 
-                // Infill contour bounding box.
+            // Infill contour bounding box.
-                BoundingBox infill_contour_bbox = get_extents(infill_contour);
+            BoundingBox infill_contour_bbox = get_extents(infill_contour);
-                infill_contour_bbox.offset(SCALED_EPSILON);
+            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.
+            // Get top ExPolygons from current infill contour.
-                Polygons upper_slices_clipped;
+            Polygons upper_slices_clipped;
-                if (object_config->interface_shells) {
+            if (object_config->interface_shells) {
-                    auto upper_slicer_same_region = to_expolygons(this->upper_slices_same_region->surfaces);
+                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);
+                upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(upper_slicer_same_region, infill_contour_bbox);
-                } else
+            } else
-                    upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*upper_slices, infill_contour_bbox);
+                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 (!top_expolygons.empty()) {
-                    if (lower_slices != nullptr) {
+                if (lower_slices != nullptr) {
-                        const float      bridge_offset          = float(std::max<coord_t>(ext_perimeter_spacing, perimeter_width));
+                    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 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);
+                    const ExPolygons current_slices_bridges = offset_ex(diff_ex(top_expolygons, lower_slices_clipped), bridge_offset);
 
-                        // Remove bridges from top surface polygons.
+                    // Remove bridges from top surface polygons.
-                        top_expolygons = diff_ex(top_expolygons, current_slices_bridges);
+                    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
+        #ifdef ARACHNE_DEBUG
-            {
+        {
-                static int iRun = 0;
+            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()));
+            export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
-            }
+        }
-    #endif
+#endif
 
-            // All closed ExtrusionLine should have the same the first and the last point.
+        // 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
+        // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
-            // equal the first and the last point.
+        // equal the first and the last point.
-            assert([&perimeters = std::as_const(perimeters)]() -> bool {
+        assert([&perimeters = std::as_const(perimeters)]() -> bool {
-                for (const Arachne::VariableWidthLines& perimeter : perimeters)
+            for (const Arachne::VariableWidthLines& perimeter : perimeters)
-                    for (const Arachne::ExtrusionLine& el : perimeter)
+                for (const Arachne::ExtrusionLine& el : perimeter)
-                        if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
+                    if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
-                            return false;
+                        return false;
-                return true;
+            return true;
-            }());
+        }());
 
-            int start_perimeter = int(perimeters.size()) - 1;
+        int start_perimeter = int(perimeters.size()) - 1;
-            int end_perimeter = -1;
+        int end_perimeter = -1;
-            int direction = -1;
+        int direction = -1;
 
-    		bool is_outer_wall_first =
+		bool is_outer_wall_first =
-                	this->config->wall_sequence == WallSequence::OuterInner ||
+            	this->config->wall_sequence == WallSequence::OuterInner ||
-                	this->config->wall_sequence == WallSequence::InnerOuterInner;
+            	this->config->wall_sequence == WallSequence::InnerOuterInner;
         
-            if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
+        if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
-            	is_outer_wall_first =
+        	is_outer_wall_first =
-                	this->config->wall_sequence == WallSequence::OuterInner;
+            	this->config->wall_sequence == WallSequence::OuterInner;
-            }
+        }
-            if (is_outer_wall_first) {
+        if (is_outer_wall_first) {
-                start_perimeter = 0;
+            start_perimeter = 0;
-                end_perimeter = int(perimeters.size());
+            end_perimeter = int(perimeters.size());
-                direction = 1;
+            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);
             }
 
-            std::vector<Arachne::ExtrusionLine*> all_extrusions;
+            std::sort(available_candidates.begin(), available_candidates.end(), [&all_extrusions](const size_t a_idx, const size_t b_idx) -> bool {
-            for (int perimeter_idx = start_perimeter; perimeter_idx != end_perimeter; perimeter_idx += direction) {
+                return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
-                if (perimeters[perimeter_idx].empty())
+                });
+
+            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;
-                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);
                 }
 
-                std::sort(available_candidates.begin(), available_candidates.end(), [&all_extrusions](const size_t a_idx, const size_t b_idx) -> bool {
+                const Point candidate_position = path->junctions.front().p;
-                    return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
+                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)) {
-                for (const size_t candidate_path_idx : available_candidates) {
+                        best_candidate = candidate_path_idx;
-                    auto& path = all_extrusions[candidate_path_idx];
+                        best_distance_sqr = distance_sqr;
-
+                        is_best_closed = path->is_closed;
-                    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.
-                }
             }
 
-           // printf("New Layer: Layer ID %d\n",layer_id); //debug - new layer
+            auto& best_path = all_extrusions[best_candidate];
-            if (this->config->wall_sequence == WallSequence::InnerOuterInner && layer_id > 0) { // only enable inner outer inner algorithm after first layer
+            ordered_extrusions.push_back({ best_path, best_path->is_contour() });
-                if (ordered_extrusions.size() > 2) { // 3 walls minimum needed to do inner outer inner ordering
+            processed[best_candidate] = true;
-                    int position = 0; // index to run the re-ordering for multiple external perimeters in a single island.
+            for (size_t unlocked_idx : blocking[best_candidate])
-                    int arr_i, arr_j = 0;    // indexes to run through the walls in the for loops
+                blocked[unlocked_idx]--;
-                    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());
 
-                    // 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
+            if (!best_path->junctions.empty()) { //If all paths were empty, the best path is still empty. We don't upate the current position then.
-                    // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
+                if (best_path->is_closed)
-                    coord_t threshold_external = (apply_precise_outer_wall)
+                    current_position = best_path->junctions[0].p; //We end where we started.
-                        // Precise outer wall ⇒ use “full external spacing”
+                else
-                        ? ( this->ext_perimeter_flow.scaled_spacing()
+                    current_position = best_path->junctions.back().p; //Pick the other end from where we started.
-                            + 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 );
+       // 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
                 
-                    // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
+                // To address any remaining scenarios where the outer perimeter contour is not first on the list as arachne sometimes reorders the perimeters when clustering
-                    coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
+                // for OI mode that is used the basis for IOI
+                bringContoursToFront(ordered_extrusions);
+                std::vector<PerimeterGeneratorArachneExtrusion> reordered_extrusions;
                 
-                    // Re-order extrusions based on distance
+                // Debug statement to print spacing values:
-                    // Alorithm will aggresively optimise for the appearance of the outermost perimeter
+                //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());
-                    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.
+                // 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 );
                 
-                    // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
+                // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
-                    // scan to find the external perimeter, first internal, second internal and last perimeter in the island.
+                coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
-                    // We then advance the position index to move to the second island and continue until there are no more
+                
-                    // perimeters left.
+                // Re-order extrusions based on distance
-                    while (position < reordered_extrusions.size()) {
+                // Alorithm will aggresively optimise for the appearance of the outermost perimeter
-                        outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
+                ordered_extrusions = reorderPerimetersByProximity(ordered_extrusions,threshold_external,threshold_internal );
-                        max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
+                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.
-                        // 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
+                // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
-                        // perimeters in a single island
+                // scan to find the external perimeter, first internal, second internal and last perimeter in the 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);
+                // We then advance the position index to move to the second island and continue until there are no more
-                        for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
+                // perimeters left.
-                            // printf("Perimeter: extrusion inset index %d, ordered extrusions array position %d\n",reordered_extrusions[arr_i].extrusion->inset_idx, arr_i);
+                while (position < reordered_extrusions.size()) {
-                            switch (reordered_extrusions[arr_i].extrusion->inset_idx) {
+                    outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
-                                case 0: // external perimeter
+                    max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
-                                    if (outer == -1)
+                    // run through the walls to get the index values that need re-ordering until the first one for each
-                                        outer = arr_i;
+                    // is found. Start at "position" index to enable the for loop to iterate for multiple external
-                                    break;
+                    // perimeters in a single island
-                                case 1: // first internal wall
+                    // 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);
-                                    if (first_internal==-1 && arr_i>outer && outer!=-1){
+                    for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
-                                        first_internal = 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) {
-                                    break;
+                            case 0: // external perimeter
-                                case 2: // second internal wall
+                                if (outer == -1)
-                                    if (second_internal == -1 && arr_i > first_internal && outer!=-1){
+                                    outer = arr_i;
-                                        second_internal = arr_i;
+                                break;
-                                    }
+                            case 1: // first internal wall
-                                    break;
+                                if (first_internal==-1 && arr_i>outer && outer!=-1){
-                            }
+                                    first_internal = arr_i;
-                            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++; 
                                 }
-                            }
+                                break;
-                        
+                            case 2: // second internal wall
-                            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
+                                if (second_internal == -1 && arr_i > first_internal && outer!=-1){
-                                // printf("Outside in loop: Mapped perimeter index %d to array position %d\n", arr_j, current_perimeter+1);
+                                    second_internal = arr_i;
-                                inner_outer_extrusions[++current_perimeter] = reordered_extrusions[arr_j];
+                                }
-                            }
+                                break;
-                        
+                        }
-                            for(arr_j = position; arr_j <= max_internal; ++arr_j) // replace perimeter array with the new re-ordered array
+                        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.
-                                ordered_extrusions[arr_j] = inner_outer_extrusions[arr_j-position];
+                                                                                                                      // 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
                         }
-                        // go to the next perimeter from the current position to continue scanning for external walls in the same island
-                        position = arr_i + 1;
                     }
+                    
+                    // 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++; 
+                            }
+                        }
+                        
+                        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];
+                    }
+                    // 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_contour = false;
-            bool steep_overhang_hole    = false;
+        bool steep_overhang_hole    = false;
-            if (!config->overhang_reverse) {
+        if (!config->overhang_reverse) {
-                // Skip steep overhang detection no reverse is specified
+            // Skip steep overhang detection no reverse is specified
-                steep_overhang_contour = true;
+            steep_overhang_contour = true;
-                steep_overhang_hole    = true;
+            steep_overhang_hole    = true;
-            }
+        }
-            if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
+        if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
-                if (config->overhang_reverse) {
+            if (config->overhang_reverse) {
-                    reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
+                reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
-                                        this->config->overhang_reverse_internal_only);
+                                    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())
+        if (offset_ex(infill_contour, -float(spacing / 2.)).empty())
-                infill_contour.clear(); // Infill region is too small, so let's filter it out.
+            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
+        // 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)
+        // 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
+        // and then we offset back and forth by half the infill spacing to only consider the
-            // non-collapsing regions
+        // non-collapsing regions
-            coord_t inset =
+        coord_t inset =
-                (loop_number < 0) ? 0 :
+            (loop_number < 0) ? 0 :
-                (loop_number == 0) ?
+            (loop_number == 0) ?
-                // one loop
+            // one loop
-                ext_perimeter_spacing :
+            ext_perimeter_spacing :
-                // two or more loops?
+            // two or more loops?
-                perimeter_spacing;
+            perimeter_spacing;
-            coord_t top_inset = inset;
+        coord_t top_inset = inset;
         
-            top_inset = coord_t(scale_(this->config->top_bottom_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)
+        if(is_topmost_layer || is_bottom_layer)
-                inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+            inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
-            else
+        else
-                inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+            inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
         
-            // simplify infill contours according to resolution
+        // simplify infill contours according to resolution
-            Polygons pp;
+        Polygons pp;
-            for (ExPolygon& ex : infill_contour)
+        for (ExPolygon& ex : infill_contour)
-                ex.simplify_p(m_scaled_resolution, &pp);
+            ex.simplify_p(m_scaled_resolution, &pp);
-            ExPolygons not_filled_exp = union_ex(pp);
+        ExPolygons not_filled_exp = union_ex(pp);
-            // collapse too narrow infill areas
+        // collapse too narrow infill areas
-            const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
+        const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
 
-            ExPolygons infill_exp = offset2_ex(
+        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(
                 not_filled_exp,
                 float(-min_perimeter_infill_spacing / 2.),
-                float(inset + min_perimeter_infill_spacing / 2.));
+                float(+min_perimeter_infill_spacing / 2.));
-            // append infill areas to fill_surfaces
+            if (!top_expolygons.empty())
-            if (!top_expolygons.empty()) {
+                polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
-                infill_exp = union_ex(infill_exp, offset_ex(top_expolygons, double(top_inset)));
+            this->fill_no_overlap->insert(this->fill_no_overlap->end(), polyWithoutOverlap.begin(), polyWithoutOverlap.end());
-            }
+        }
-            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)
-            this->loops->append(result.loops);
-        this->fill_surfaces->append(result.infill, stInternal);
-        apply_extra_perimeters(result.infill);
-        this->fill_no_overlap->insert(this->fill_no_overlap->end(), result.no_overlap.begin(), result.no_overlap.end());
     }
 }
 

src/libslic3r/Polygon.hpp

@@ -27,7 +27,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) noexcept : MultiPoint(std::move(other.points)) {}
+    Polygon(Polygon &&other) : MultiPoint(std::move(other.points)) {}
 	static Polygon new_scale(const std::vector<Vec2d> &points) { 
         Polygon pgn;
         pgn.points.reserve(points.size());
@@ -36,7 +36,7 @@ public:
 		return pgn;
 	}
     Polygon& operator=(const Polygon &other) { points = other.points; return *this; }
-    Polygon& operator=(Polygon &&other) noexcept { points = std::move(other.points); return *this; }
+    Polygon& operator=(Polygon &&other) { 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

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

src/libslic3r/PrintObject.cpp

@@ -30,7 +30,6 @@
 
 #include <cstddef>
 #include <float.h>
-#include <array>
 #include <iterator>
 #include <mutex>
 #include <string>
@@ -43,7 +42,6 @@
 #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>
 
@@ -1666,9 +1664,7 @@ 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();
 
-    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
+    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
-    // 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)
@@ -1726,7 +1722,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_by_piece(layerm_slices_surfaces, to_polygons(upper_layer->lslices), ApplySafetyOffset::Yes);
+                            diff_ex(layerm_slices_surfaces, 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
@@ -1752,7 +1748,7 @@ void PrintObject::detect_surfaces_type()
                         surfaces_append(
                             bottom,
                             opening_ex(
-                                diff_ex_by_piece(layerm_slices_surfaces, to_polygons(lower_layer->lslices), ApplySafetyOffset::Yes),
+                                diff_ex(layerm_slices_surfaces, lower_layer->lslices, ApplySafetyOffset::Yes),
                                 offset),
                             surface_type_bottom_other);
                         // if user requested internal shells, we need to identify surfaces
@@ -1783,44 +1779,34 @@ 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_by_piece(to_expolygons(top), to_polygons(bottom));
+                        const auto cracks = intersection_ex(top, 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
-                                        const BoundingBox crack_bbox = get_extents(crack);
+                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, small_crack_threshold](const Surface& s) {
-                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, &crack_bbox, small_crack_threshold](const Surface& s) {
                                                 const auto& se = s.expolygon;
-                                                return get_extents(se).inflated(SCALED_EPSILON).contains(crack_bbox)
+                                                return diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
-                                                    && 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) {
-                                            if (get_extents(b.expolygon).overlap(grown_bbox))
+                                            surfaces_append(bot_tmp, diff_ex(b.expolygon, offset_ex(crack, -small_crack_threshold)), b.surface_type);
-                                                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);
                                     }
                                 }
                             }
 
-                            ExPolygons top_expolygons = to_expolygons(std::move(top));
+                            Polygons top_polygons = to_polygons(std::move(top));
                             top.clear();
-                            surfaces_append(top, diff_ex_by_piece(top_expolygons, to_polygons(bottom)), stTop);
+                            surfaces_append(top, diff_ex(top_polygons, bottom), stTop);
                         }
                     }
 
@@ -1911,7 +1897,7 @@ void PrintObject::detect_surfaces_type()
                     {
                         Polygons topbottom = to_polygons(top);
                         polygons_append(topbottom, to_polygons(bottom));
-                        surfaces_append(surfaces_out, diff_ex_by_piece(surfaces_prev_expolys, topbottom), stInternal);
+                        surfaces_append(surfaces_out, diff_ex(surfaces_prev_expolys, topbottom), stInternal);
                     }
 
                     surfaces_append(surfaces_out, std::move(top));
@@ -2088,31 +2074,29 @@ 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(
@@ -2129,7 +2113,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;
@@ -2196,10 +2180,8 @@ void PrintObject::process_external_surfaces()
 	    BOOST_LOG_TRIVIAL(debug) << "Collecting surfaces covered with extrusions in parallel - end";
 	}
 
-    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - start";
+	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
+        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - start";
-    // 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) {
@@ -2214,9 +2196,9 @@ void PrintObject::process_external_surfaces()
                 }
             }
         );
-    });
+        m_print->throw_if_canceled();
-    m_print->throw_if_canceled();
+        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - end";
-    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - end";
+    }
 }
 
 void PrintObject::discover_vertical_shells()
@@ -2255,10 +2237,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";
-        // One layer per task: on a layer cut through a fine relief the unions below take far longer than elsewhere, and a
+        //FIXME Improve the heuristics for a grain size.
-        // few such layers next to each other must not end up in one task.
+        size_t grain_size = std::max(num_layers / 16, size_t(1));
         tbb::parallel_for(
-            tbb::blocked_range<size_t>(0, num_layers, 1),
+            tbb::blocked_range<size_t>(0, num_layers, grain_size),
             [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();
@@ -2266,198 +2248,67 @@ 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];
-                    const auto top_bottom_expansion = [&layer](size_t region_id) {
+                    // Simulate single set of perimeters over all merged regions.
-                        return float(layer.m_regions[region_id]->flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
+                    float                             perimeter_offset = 0.f;
-                    };
+                    float                             perimeter_min_spacing = FLT_MAX;
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     static size_t debug_idx = 0;
                     ++ debug_idx;
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    // The top surfaces, the bottom surfaces and the holes are independent of each other.
+                    for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
-                    tbb::parallel_invoke(
+                        LayerRegion &layerm               = *layer.m_regions[region_id];
-                        [&]() {
+                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
+                        // Top surfaces.
-                                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.slices.filter_by_type(stTop), top_bottom_expansion));
-//                              append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
+//                        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.
+                        // Bottom surfaces.
-                            cache.top_surfaces = union_(cache.top_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.
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
+                        // First find the maxium number of perimeters per region slice.
-                                append(cache.bottom_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_types(surfaces_bottom), top_bottom_expansion(region_id)));
+                        unsigned int perimeters = 0;
-//                              append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                        for (Surface &s : layerm.slices.surfaces)
-                            cache.bottom_surfaces = union_(cache.bottom_surfaces);
+                            perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
-                        },
+                        perimeters += layerm.region().config().wall_loops.value;
-                        [&]() {
+                        // Then calculate the infill offset.
-                            // Simulate single set of perimeters over all merged regions.
+                        if (perimeters > 0) {
-                            float perimeter_offset      = 0.f;
+                            Flow extflow = layerm.flow(frExternalPerimeter);
-                            float perimeter_min_spacing = FLT_MAX;
+                            Flow flow    = layerm.flow(frPerimeter);
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
+                            perimeter_offset = std::max(perimeter_offset,
-                                const LayerRegion &layerm = *layer.m_regions[region_id];
+                                0.5f * float(extflow.scaled_width() + extflow.scaled_spacing()) + (float(perimeters) - 1.f) * flow.scaled_spacing());
-                                // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
+                            perimeter_min_spacing = std::min(perimeter_min_spacing, float(std::min(extflow.scaled_spacing(), flow.scaled_spacing())));
-                                // First find the maxium number of perimeters per region slice.
+                        }
-                                unsigned int perimeters = 0;
+                        polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
-                                for (const Surface &s : layerm.slices.surfaces)
+                    }
-                                    perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
+                    // Save some computing time by reducing the number of polygons.
-                                perimeters += layerm.region().config().wall_loops.value;
+                    cache.top_surfaces    = union_(cache.top_surfaces);
-                                // Then calculate the infill offset.
+                    cache.bottom_surfaces = union_(cache.bottom_surfaces);
-                                if (perimeters > 0) {
+                    // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
-                                    Flow extflow = layerm.flow(frExternalPerimeter);
+                    if (perimeter_offset > 0.) {
-                                    Flow flow    = layerm.flow(frPerimeter);
+                        // The layer.lslices are forced to merge by expanding them first.
-                                    perimeter_offset = std::max(perimeter_offset,
+                        polygons_append(cache.holes, offset2(layer.lslices, 0.3f * perimeter_min_spacing, - perimeter_offset - 0.3f * perimeter_min_spacing));
-                                        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));
+                            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(layer.lslices, "blue");
-                                    svg.draw(union_ex(cache.holes), "red");
+                            svg.draw(union_ex(cache.holes), "red");
-                                    svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
+                            svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
-                                    svg.Close();
+                            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";
     }
 
-    // With one top/bottom cache for all regions, the shell and hole accumulation in the loop below depends on nothing
+    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
-    // 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().
-            return;
+            continue;
 
         //FIXME Improve the heuristics for a grain size.
         size_t grain_size = std::max(num_layers / 16, size_t(1));
@@ -2497,7 +2348,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, &shell_accumulations, &accumulation_key, &accumulate_shell]
+            [this, region_id, &cache_top_botom_regions]
             (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) {
@@ -2547,19 +2398,80 @@ void PrintObject::discover_vertical_shells()
                         }
                     }
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    const AccumulationKey key = accumulation_key(region_config, layerm);
+			        polygons_append(holes, cache_top_botom_regions[idx_layer].holes);
-                    const ShellAccumulation *reused = shell_accumulations.empty() ? nullptr :
+                    auto combine_holes = [&holes](const Polygons &holes2) {
-                        [&]() -> const ShellAccumulation * {
+                        if (holes.empty() || holes2.empty())
-                            for (const ShellAccumulation &a : shell_accumulations[idx_layer])
+                            holes.clear();
-                                if (a.key == key)
+                        else
-                                    return &a;
+                            holes = intersection(holes, holes2);
-                            return nullptr;
+                    };
-                        }();
+                    auto combine_shells = [&shell](const Polygons &shells2) {
-                    if (reused != nullptr) {
+                        if (shell.empty())
-                        shell = reused->shell;
+                            shell = std::move(shells2);
-                        holes = reused->holes;
+                        else if (! shells2.empty()) {
-                    } else
+                            polygons_append(shell, shells2);
-                        accumulate_shell(idx_layer, region_config, layerm, shell, holes);
+                            // 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);
+	                }
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
         				Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-%d.svg", debug_idx), get_extents(shell));
@@ -2653,8 +2565,11 @@ void PrintObject::discover_vertical_shells()
                         Polygons object_volume;
                         Polygons internal_volume;
                         {
-                            if (idx_layer > 0 && idx_layer + 1 < m_layers.size())
+                            Polygons shrinked_bottom_slice = idx_layer > 0 ? to_polygons(m_layers[idx_layer - 1]->lslices) : Polygons{};
-                                object_volume = to_polygons(intersection_ex_by_piece(m_layers[idx_layer - 1]->lslices, to_polygons(m_layers[idx_layer + 1]->lslices)));
+                            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);
                             internal_volume = closing(polygonsInternal, SCALED_EPSILON);
                         }
 
@@ -2665,34 +2580,15 @@ 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, &internal_bboxes, &min_perimeter_infill_spacing,
+                                                               [&internal_volume, &min_perimeter_infill_spacing,
                                                                 &object_volume](const ExPolygon &p) {
-                                                                   const bool small = p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
+                                                                   return (p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
-                                                                                      (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
+                                                                           (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
-                                                                                       diff(to_polygons(p),
+                                                                            diff(to_polygons(p), object_volume).empty())) &&
-                                                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                                          diff(internal_volume,
-                                                                                                object_volume, get_extents(p).inflated(SCALED_EPSILON)))
+                                                                               expand(to_polygons(p), min_perimeter_infill_spacing))
-                                                                                           .empty());
+                                                                                  .size() >= internal_volume.size();
-                                                                   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());
                     }
@@ -2714,9 +2610,8 @@ void PrintObject::discover_vertical_shells()
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
 
                     // Trim the internal & internalvoid by the shell.
-                    const Polygons     regularized_shell_polygons = to_polygons(regularized_shell);
+                    Slic3r::ExPolygons new_internal = diff_ex(layerm->fill_surfaces.filter_by_type(stInternal), 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(layerm->fill_surfaces.filter_by_type(stInternalVoid), regularized_shell);
-                    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
                     {
@@ -2743,15 +2638,7 @@ 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
@@ -3272,16 +3159,6 @@ 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)};
 
@@ -3526,63 +3403,28 @@ 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 ClipperLib 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());
-                    // deep_infill_area and internal_unsupported_area cover the whole layer; only their part under
+                    area_to_be_bridge             = intersection(area_to_be_bridge, deep_infill_area);
-                    // 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) {
+                                                           [internal_unsupported_area](const Polygon &p) {
-                                                               return intersection({p}, ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                               return intersection({p}, internal_unsupported_area).empty();
-                                                                                            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;
 
-                    Polygons       limiting_area;
+                    Polylines boundary_plines = to_polylines(expand(total_fill_area, 1.3 * flow.scaled_spacing()));
-                    const Polygons near_expansion = split_near(expansion_area, get_extents(area_to_be_bridge).inflated(SCALED_EPSILON),
-                                                               limiting_area);
-                    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;
                     {
-                        // No offset here: flow.spacing() is in mm, so the expand(limiting_area, 0.3 * flow.spacing())
+                        Polylines limiting_plines = to_polylines(expand(limiting_area, 0.3*flow.spacing()));
-                        // this used to be moved the outline by 0.135 scaled units - nothing beyond rounding - while
-                        // costing a whole-layer ClipperLib pass for every candidate. limiting_area is already a clean
-                        // union, so its own outline is the same boundary.
-                        Polylines limiting_plines = to_polylines(limiting_area);
                         boundary_plines.insert(boundary_plines.end(), limiting_plines.begin(), limiting_plines.end());
                     }
 
@@ -3656,12 +3498,9 @@ 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) {
-                            // Surfaces whose boxes miss each other cannot intersect, which is most pairs on a busy layer.
+                            if (!intersection(s.new_polys, tmp_expanded_area).empty()) {
-                            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;
@@ -3685,20 +3524,10 @@ 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));
                     }
-                    // Each of these meets one bridge with the whole layer, so the layer side is first cut down to the
+                    bridging_area          = intersection(bridging_area, limiting_area);
-                    // bridge's box (and expansion_area split as above); the result is the same.
+                    bridging_area          = intersection(bridging_area, total_fill_area);
-                    if (!bridging_area.empty()) {
+                    bridging_area          = diff(bridging_area, total_top_area);
-                        const BoundingBox bridging_bbox = get_extents(bridging_area).inflated(SCALED_EPSILON);
+                    expansion_area         = diff(expansion_area, bridging_area);
-                        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/Support/SupportMaterial.cpp

@@ -929,9 +929,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

@@ -854,41 +854,11 @@ 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 on a layer cut through a fine relief (thousands of islands above thousands) never ends.
-                    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
-                        const ExPolygons  expanded = offset_ex(expoly, 0.1 * extrusion_width_scaled);
+                        if (!overlaps(offset_ex(expoly, 0.1 * extrusion_width_scaled), lower_polys)) {
-                        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, whose whole boundary
-                        // was otherwise intersected again for every 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

@@ -61,7 +61,7 @@ public:
             thickness(other.thickness), thickness_layers(other.thickness_layers),
             bridge_angle(other.bridge_angle), extra_perimeters(other.extra_perimeters)
         {};
-    Surface(Surface &&rhs) noexcept
+    Surface(Surface &&rhs)
         : 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)
@@ -87,7 +87,7 @@ public:
         return *this;
     }
 
-    Surface& operator=(Surface &&rhs) noexcept
+    Surface& operator=(Surface &&rhs)
     {
         surface_type     = rhs.surface_type;
         expolygon        = std::move(rhs.expolygon);

src/libslic3r/Utils.hpp

@@ -256,10 +256,13 @@ extern bool is_gallery_file(const std::string& path, char const* type);
 extern bool is_shapes_dir(const std::string& dir);
 //BBS: add json support
 extern bool is_json_file(const std::string& path);
-// True if rel_path is relative, has no ".." component and, joined to root, still resolves inside it.
+// True if rel_path is relative, has no ".." component or embedded NUL and, joined to root, still resolves inside it.
 // Both '/' and '\\' are treated as separators on every platform, so an archive rejected on one OS
 // is rejected on all of them.
 extern bool is_path_within_root(const std::string &rel_path, const boost::filesystem::path &root);
+// True if a symlink stored at link_rel_path (relative to root) with this target stays inside root: the target
+// must be relative, and joined to the link's directory it must pass is_path_within_root.
+extern bool is_symlink_target_within_root(const std::string &link_rel_path, const std::string &target, const boost::filesystem::path &root);
 
 // Orca: custom protocal support utils
 inline bool is_orca_open(const std::string& url) { return boost::starts_with(url, "orcaslicer://open"); }

src/libslic3r/libslic3r.h

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

src/libslic3r/miniz_extension.cpp

@@ -4,6 +4,9 @@
 #include "miniz_extension.hpp"
 #include "Utils.hpp"
 
+#include <boost/filesystem.hpp>
+#include <boost/log/trivial.hpp>
+
 #if defined(_MSC_VER) || defined(__MINGW64__)
 #include "boost/nowide/cstdio.hpp"
 #endif
@@ -115,6 +118,66 @@ std::string decode_archive_entry_path(mz_zip_archive *zip, const mz_zip_archive_
     return decode_zip_unicode_path_extra_field(extra.substr(0, extra_size > 0 ? extra_size - 1 : 0), stat.m_filename);
 }
 
+bool extract_archive_confined(const std::string &zip_path_utf8, const std::string &dest_dir)
+{
+    mz_zip_archive archive;
+    mz_zip_zero_struct(&archive);
+
+    if (!open_zip_reader(&archive, zip_path_utf8)) {
+        BOOST_LOG_TRIVIAL(error) << "Unable to open zip reader for " << zip_path_utf8;
+        return false;
+    }
+
+    const mz_uint num_entries = mz_zip_reader_get_num_files(&archive);
+    mz_zip_archive_file_stat stat;
+
+    // Validate every entry first so an archive with a single escaping entry leaves no partial output behind.
+    const boost::filesystem::path root(dest_dir);
+    for (mz_uint i = 0; i < num_entries; ++i) {
+        if (mz_zip_reader_file_stat(&archive, i, &stat) && !is_path_within_root(stat.m_filename, root)) {
+            BOOST_LOG_TRIVIAL(error) << "Unzip: rejecting " << zip_path_utf8 << ", entry " << stat.m_filename << " resolves outside " << dest_dir;
+            close_zip_reader(&archive);
+            return false;
+        }
+    }
+
+    for (mz_uint i = 0; i < num_entries; ++i) {
+        if (!mz_zip_reader_file_stat(&archive, i, &stat)) {
+            BOOST_LOG_TRIVIAL(warning) << "Unzip: read file stat failed";
+            continue;
+        }
+        const std::string dest_file = dest_dir + "/" + stat.m_filename;
+        try {
+            if (stat.m_is_directory) {
+                const boost::filesystem::path dest_path(dest_file);
+                if (!boost::filesystem::exists(dest_path))
+                    boost::filesystem::create_directories(dest_path);
+                continue;
+            }
+            if (stat.m_uncomp_size == 0) {
+                BOOST_LOG_TRIVIAL(warning) << "Unzip: invalid size for file " << stat.m_filename;
+                continue;
+            }
+            // Replace a symlink at the destination rather than writing through it.
+            const boost::filesystem::path dest_path(dest_file);
+            if (boost::filesystem::is_symlink(boost::filesystem::symlink_status(dest_path)))
+                boost::filesystem::remove(dest_path);
+            if (!mz_zip_reader_extract_to_file(&archive, stat.m_file_index, dest_file.c_str(), 0)) {
+                BOOST_LOG_TRIVIAL(error) << "Unzip: extract file " << stat.m_filename << " to dest " << dest_file << " failed";
+                close_zip_reader(&archive);
+                return false;
+            }
+            BOOST_LOG_TRIVIAL(info) << "Unzip: successfully extract file " << stat.m_file_index << " to " << dest_file;
+        } catch (const std::exception &e) {
+            close_zip_reader(&archive);
+            BOOST_LOG_TRIVIAL(error) << "Unzip: archive read exception: " << e.what();
+            return false;
+        }
+    }
+    close_zip_reader(&archive);
+    return true;
+}
+
 MZ_Archive::MZ_Archive()
 {
     mz_zip_zero_struct(&arch);

src/libslic3r/miniz_extension.hpp

@@ -11,6 +11,8 @@ bool open_zip_writer(mz_zip_archive *zip, const std::string &fname_utf8);
 bool close_zip_reader(mz_zip_archive *zip);
 bool close_zip_writer(mz_zip_archive *zip);
 std::string decode_archive_entry_path(mz_zip_archive *zip, const mz_zip_archive_file_stat &stat);
+// Extracts every entry of the archive under dest_dir. Nothing is written if any entry would resolve outside dest_dir.
+bool extract_archive_confined(const std::string &zip_path_utf8, const std::string &dest_dir);
 
 class MZ_Archive {
 public:

src/libslic3r/utils.cpp

@@ -1093,6 +1093,9 @@ bool is_path_within_root(const std::string &rel_path, const boost::filesystem::p
     auto is_separator = [](char c) { return c == '/' || c == '\\'; };
     if (rel_path.empty() || is_separator(rel_path.front()) || (rel_path.size() > 1 && rel_path[1] == ':'))
         return false;
+    // The filesystem calls stop at a NUL, so they would act on a shorter path than the one checked here.
+    if (rel_path.find('\0') != std::string::npos)
+        return false;
     for (size_t start = 0; start <= rel_path.size();) {
         size_t end = start;
         while (end < rel_path.size() && !is_separator(rel_path[end]))
@@ -1103,7 +1106,10 @@ bool is_path_within_root(const std::string &rel_path, const boost::filesystem::p
     }
     // Resolve against the canonical root so a symlink inside it cannot lead back out.
     try {
-        const std::string root_str = boost::filesystem::weakly_canonical(root).string();
+        std::string root_str = boost::filesystem::weakly_canonical(root).string();
+        // A trailing separator on root would otherwise fail the prefix match below for every path.
+        while (!root_str.empty() && (root_str.back() == '/' || root_str.back() == boost::filesystem::path::preferred_separator))
+            root_str.pop_back();
         const std::string full_str = boost::filesystem::weakly_canonical(root / rel_path).string();
         return full_str.compare(0, root_str.size(), root_str) == 0 &&
                (full_str.size() == root_str.size() || full_str[root_str.size()] == boost::filesystem::path::preferred_separator);
@@ -1112,6 +1118,15 @@ bool is_path_within_root(const std::string &rel_path, const boost::filesystem::p
     }
 }
 
+bool is_symlink_target_within_root(const std::string &link_rel_path, const std::string &target, const boost::filesystem::path &root)
+{
+    if (target.empty() || target.front() == '/' || target.front() == '\\' || (target.size() > 1 && target[1] == ':'))
+        return false;
+    // A relative target without ".." only descends from the link's directory, so no chain of such links can leave root.
+    const size_t sep = link_rel_path.find_last_of("/\\");
+    return is_path_within_root((sep == std::string::npos ? std::string() : link_rel_path.substr(0, sep + 1)) + target, root);
+}
+
 bool is_img_file(const std::string &path)
 {
 	return boost::iends_with(path, ".png") || boost::iends_with(path, ".svg");

src/slic3r/CMakeLists.txt

@@ -1019,14 +1019,9 @@ if (UNIX AND NOT APPLE)
     find_package(GTK${SLIC3R_GTK} REQUIRED)
     pkg_check_modules(LIBSECRET REQUIRED libsecret-1)
     pkg_check_modules(webkit2gtk REQUIRED webkit2gtk-4.1)
-    if (FLATPAK)
+    find_package(X11 REQUIRED)
-        # I don't know why this is needed, but for whatever reason slic3r isn't
-        # linking to X11 and webkit2gtk. force it.
-        find_package(X11 REQUIRED)
-        target_link_libraries(libslic3r_gui ${X11_LIBRARIES} ${webkit2gtk_LIBRARIES})
-    endif()
     target_include_directories(libslic3r_gui SYSTEM PRIVATE ${GTK${SLIC3R_GTK}_INCLUDE_DIRS} ${LIBSECRET_INCLUDE_DIRS} ${webkit2gtk_INCLUDE_DIRS})
-    target_link_libraries(libslic3r_gui ${GTK${SLIC3R_GTK}_LIBRARIES} fontconfig ${LIBSECRET_LIBRARIES})
+    target_link_libraries(libslic3r_gui ${GTK${SLIC3R_GTK}_LIBRARIES} fontconfig ${LIBSECRET_LIBRARIES} ${webkit2gtk_LIBRARIES} ${X11_LIBRARIES})
 
     # Propagate GDK backend detection results as compile definitions so that
     # LinuxDisplayBackend.cpp can include the right GDK headers.

src/slic3r/GUI/GUI.cpp

@@ -14,6 +14,9 @@
 #include <boost/algorithm/string/predicate.hpp>
 #include <boost/any.hpp>
 
+#include <wx/filename.h>
+#include <wx/filesys.h>
+
 #if __APPLE__
 #import <IOKit/pwr_mgt/IOPMLib.h>
 #elif _WIN32
@@ -531,6 +534,11 @@ boost::filesystem::path into_path(const wxString &str)
 	return boost::filesystem::path(str.wx_str());
 }
 
+wxString file_url_from_path(const boost::filesystem::path &path)
+{
+	return wxFileSystem::FileNameToURL(wxFileName(from_path(path)));
+}
+
 void about()
 {
     AboutDialog dlg;

src/slic3r/GUI/GUI.hpp

@@ -76,6 +76,9 @@ std::string	into_u8(const wxString &str);
 wxString	from_path(const boost::filesystem::path &path);
 // boost path from wxString
 boost::filesystem::path	into_path(const wxString &str);
+// file:// URL of a local path, percent-encoded so characters such as '#', '%' and '?' stay part of the path.
+// Append any query or fragment to the result.
+wxString	file_url_from_path(const boost::filesystem::path &path);
 
 // Display an About dialog
 extern void about();

src/slic3r/GUI/GUI_App.cpp

@@ -1512,11 +1512,33 @@ int GUI_App::install_plugin(std::string name, std::string package_name, InstallP
                     size_t n = mz_zip_reader_get_extra(&archive, stat.m_file_index, extra.data(), extra.size());
                     dest_file = decode(extra.substr(0, n), stat.m_filename);
                 }
+                if (!is_path_within_root(dest_file, plugin_folder)) {
+                    BOOST_LOG_TRIVIAL(error) << "[install_plugin] entry " << dest_file << " resolves outside " << plugin_folder.string();
+                    close_zip_reader(&archive);
+                    if (pro_fn) { pro_fn(InstallStatusUnzipFailed, 0, cancel); }
+                    return InstallStatusUnzipFailed;
+                }
                 auto dest_path = plugin_folder / dest_file;
-                boost::filesystem::create_directories(dest_path.parent_path());
                 std::string dest_zip_file = encode_path(dest_path.string().c_str());
+#ifndef WIN32
+                // Validate a symlink's target before anything at the destination is replaced.
+                const bool is_link = S_ISLNK(stat.m_external_attr >> 16);
+                std::string link;
+                if (is_link) {
+                    link.assign(stat.m_uncomp_size, 0);
+                    if (!mz_zip_reader_extract_to_mem(&archive, stat.m_file_index, link.data(), stat.m_uncomp_size, 0) ||
+                        !is_symlink_target_within_root(dest_file, link, plugin_folder)) {
+                        BOOST_LOG_TRIVIAL(error) << "[install_plugin] link " << dest_file << " -> " << link << " is unreadable or resolves outside " << plugin_folder.string();
+                        close_zip_reader(&archive);
+                        if (pro_fn) { pro_fn(InstallStatusUnzipFailed, 0, cancel); }
+                        return InstallStatusUnzipFailed;
+                    }
+                }
+#endif
                 try {
-                    if (fs::exists(dest_path)) {
+                    boost::filesystem::create_directories(dest_path.parent_path());
+                    // symlink_status so that an existing symlink, dangling or not, is replaced rather than written through.
+                    if (fs::exists(fs::symlink_status(dest_path))) {
                         boost::system::error_code ec;
                         fs::remove(dest_path, ec);
                         if (ec) {
@@ -1544,9 +1566,8 @@ int GUI_App::install_plugin(std::string name, std::string package_name, InstallP
                     }
                     mz_bool res = 0;
 #ifndef WIN32
-                    if (S_ISLNK(stat.m_external_attr >> 16)) {
+                    if (is_link) {
-                        std::string link(stat.m_uncomp_size + 1, 0);
+                        res = 1;
-                        res = mz_zip_reader_extract_to_mem(&archive, stat.m_file_index, link.data(), stat.m_uncomp_size, 0);
                         try {
                             boost::filesystem::create_symlink(link, dest_path);
                         } catch (const std::exception &e) {

src/slic3r/GUI/MarkdownTip.cpp

@@ -98,10 +98,7 @@ void MarkdownTip::LoadStyle()
         ph /= "tooltip/styled.html";
         _data_dir = false;
     }
-    auto url = ph.string();
+    _tipView->LoadURL(file_url_from_path(ph));
-    std::replace(url.begin(), url.end(), '\\', '/');
-    url = "file:///" + url;
-    _tipView->LoadURL(from_u8(url));
     _lastTip.clear();
 }
 

src/slic3r/GUI/Plater.cpp

@@ -3672,7 +3672,7 @@ void Sidebar::update_all_preset_comboboxes()
         wxString url = from_u8(PrintHost::get_print_host_webui(&cfg));
         wxString apikey;
         if(url.empty())
-            url = wxString::Format("file://%s/web/orca/missing_connection.html", from_u8(resources_dir()));
+            url = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/orca/missing_connection.html");
         else {
             const auto host_type = cfg.option<ConfigOptionEnum<PrintHostType>>("host_type")->value;
             if (cfg.has("printhost_apikey") && (host_type != htSimplyPrint))

src/slic3r/GUI/PrivacyUpdateDialog.cpp

@@ -57,9 +57,7 @@ PrivacyUpdateDialog::PrivacyUpdateDialog(wxWindow* parent, wxWindowID id, const
 
     fs::path ph(resources_dir());
     ph /= "tooltip/privacyupdate.html";
-    m_host_url = ph.string();
+    m_host_url = into_u8(file_url_from_path(ph));
-    std::replace(m_host_url.begin(), m_host_url.end(), '\\', '/');
-    m_host_url = "file:///" + m_host_url;
     m_vebview_release_note->LoadURL(from_u8(m_host_url));
     m_sizer_right->Add(m_vebview_release_note, 0, wxEXPAND | wxRIGHT | wxLEFT, FromDIP(15));
 

src/slic3r/GUI/Project.cpp

@@ -45,10 +45,10 @@ const std::vector<std::string> license_list = {
 ProjectPanel::ProjectPanel(wxWindow *parent, wxWindowID id, const wxPoint &pos, const wxSize &size, long style) : wxPanel(parent, id, pos, size, style)
 {
     SetBackgroundColour(*wxWHITE);
-    m_project_home_url = wxString::Format("file://%s/web/model/index.html", from_u8(resources_dir()));
+    m_project_home_url = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/model/index.html");
     wxString strlang = wxGetApp().current_language_code_safe();
     if (strlang != "")
-        m_project_home_url = wxString::Format("file://%s/web/model/index.html?lang=%s", from_u8(resources_dir()), strlang);
+        m_project_home_url += "?lang=" + strlang;
 
     wxBoxSizer* main_sizer = new wxBoxSizer(wxVERTICAL);
 

src/slic3r/GUI/ReleaseNote.cpp

@@ -510,7 +510,7 @@ void UpdateVersionDialog::update_version_info(wxString release_note, wxString ve
         out_buf->append(text, size);
     }, (void*) &html_source, MD_DIALECT_GITHUB | MD_FLAG_STRIKETHROUGH | MD_FLAG_WIKILINKS, 0);
     html_source.append("</body></html>");
-    m_vebview_release_note->LoadURL("file://" + (boost::filesystem::path (resources_dir()) / "web/guide/0/index.html").string());
+    m_vebview_release_note->LoadURL(file_url_from_path(boost::filesystem::path(resources_dir()) / "web/guide/0/index.html"));
 
     SetMinSize(GetSize());
     SetMaxSize(GetSize());

src/slic3r/GUI/WebDownPluginDlg.cpp

@@ -38,9 +38,7 @@ DownPluginFrame::DownPluginFrame(GUI_App *pGUI) : wxDialog((wxWindow *) (pGUI->m
 
     // set the frame icon
     wxBoxSizer *topsizer = new wxBoxSizer(wxVERTICAL);
-    wxString TargetUrl    = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/6/index.html").make_preferred().string());
+    wxString TargetUrl    = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/guide/6/index.html");
-
-    TargetUrl = "file://" + TargetUrl;
 
     // Create the webview
     m_browser = WebView::CreateWebView(this, TargetUrl);

src/slic3r/GUI/WebGuideDialog.cpp

@@ -218,37 +218,38 @@ wxString GuideFrame::SetStartPage(GuidePage startpage, bool load)
     m_page = startpage;
     BOOST_LOG_TRIVIAL(info) << __FUNCTION__<< boost::format(" enter, load=%1%, start_page=%2%")%load%int(startpage);
     //wxLogMessage("GUIDE: webpage_1  %s", (boost::filesystem::path(resources_dir()) / "web\\guide\\1\\index.html").make_preferred().string().c_str() );
-    wxString TargetUrl = from_u8( (boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=1").make_preferred().string() );
+    const wxString guide_url = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/guide/0/index.html");
+    wxString TargetUrl = guide_url + "?target=1";
     //wxLogMessage("GUIDE: webpage_2  %s", TargetUrl.mb_str());
 
     if (startpage == BBL_WELCOME){
         SetTitle(_L("Setup Wizard"));
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=1").make_preferred().string());
+        TargetUrl = guide_url + "?target=1";
     } else if (startpage == BBL_REGION) {
         SetTitle(_L("Setup Wizard"));
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=11").make_preferred().string());
+        TargetUrl = guide_url + "?target=11";
     } else if (startpage == BBL_MODELS) {
         SetTitle(_L("Setup Wizard"));
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=21").make_preferred().string());
+        TargetUrl = guide_url + "?target=21";
     } else if (startpage == BBL_FILAMENTS) {
         SetTitle(_L("Setup Wizard"));
 
         int nSize = m_ProfileJson["model"].size();
 
         if (nSize>0)
-            TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=22").make_preferred().string());
+            TargetUrl = guide_url + "?target=22";
         else
-            TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=21").make_preferred().string());
+            TargetUrl = guide_url + "?target=21";
     } else if (startpage == BBL_FILAMENT_ONLY) {
         SetTitle("");
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=23").make_preferred().string());
+        TargetUrl = guide_url + "?target=23";
     } else if (startpage == BBL_MODELS_ONLY) {
         SetTitle("");
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=24").make_preferred().string());
+        TargetUrl = guide_url + "?target=24";
     }
     else {
         SetTitle(_L("Setup Wizard"));
-        TargetUrl = from_u8((boost::filesystem::path(resources_dir()) / "web/guide/0/index.html?target=21").make_preferred().string());
+        TargetUrl = guide_url + "?target=21";
     }
 
     wxString strlang = wxGetApp().current_language_code_safe();
@@ -256,7 +257,6 @@ wxString GuideFrame::SetStartPage(GuidePage startpage, bool load)
     if (strlang != "")
         TargetUrl = wxString::Format("%s&lang=%s", w2s(TargetUrl), strlang);
 
-    TargetUrl = "file://" + TargetUrl;
     if (load)
         load_url(TargetUrl);
 
@@ -1284,7 +1284,7 @@ bool GuideFrame::BuildProfileJson(const PresetBundle& bundle, bool require_all_r
                 entry["vendor"]          = vp.id;
                 entry["nozzle_diameter"] = nozzle_str;
                 entry["materials"]       = materials_str;
-                entry["cover"]           = cover_path.string();
+                entry["cover"]           = into_u8(file_url_from_path(cover_path));
                 entry["nozzle_selected"] = "";
                 entry["sub_path"]        = "";
                 m_ProfileJson["model"].push_back(entry);
@@ -1732,7 +1732,7 @@ int GuideFrame::LoadProfileFamily(std::string strVendor, std::string strFilePath
                     cover_path = (boost::filesystem::absolute(boost::filesystem::path(resources_dir()) / "/web/image/printer/") / cover_file)
                                      .make_preferred();
             }
-            OneModel["cover"]                  = cover_path.string();
+            OneModel["cover"]                  = into_u8(file_url_from_path(cover_path));
 
             OneModel["nozzle_selected"] = "";
 

src/slic3r/GUI/WebUserLoginDialog.cpp

@@ -599,7 +599,7 @@ void ZUserLogin::OnScriptResponseMessage(wxCommandEvent &WXUNUSED(evt))
 
 bool  ZUserLogin::ShowErrorPage()
 {
-    wxString ErrortUrl = from_u8((boost::filesystem::path(resources_dir()) / "web\\login\\error.html").make_preferred().string());
+    wxString ErrortUrl = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/login/error.html");
     load_url(ErrortUrl);
 
     return true;

src/slic3r/GUI/WebViewDialog.cpp

@@ -36,10 +36,10 @@ namespace GUI {
 WebViewPanel::WebViewPanel(wxWindow *parent)
         : wxPanel(parent, wxID_ANY, wxDefaultPosition, wxDefaultSize)
  {
-    wxString url = wxString::Format("file://%s/web/homepage/index.html", from_u8(resources_dir()));
+    wxString url = file_url_from_path(boost::filesystem::path(resources_dir()) / "web/homepage/index.html");
     wxString strlang = wxGetApp().current_language_code_safe();
     if (strlang != "")
-        url = wxString::Format("file://%s/web/homepage/index.html?lang=%s", from_u8(resources_dir()), strlang);
+        url += "?lang=" + strlang;
 
     wxBoxSizer* topsizer = new wxBoxSizer(wxVERTICAL);
     

src/slic3r/GUI/Widgets/MultiNozzleSync.cpp

@@ -1,5 +1,6 @@
 #include "MultiNozzleSync.hpp"
 
+#include "../GUI.hpp"
 #include "../GUI_App.hpp"
 #include "../I18N.hpp"
 #include "../Plater.hpp"
@@ -21,8 +22,6 @@
 #include <set>
 
 #include <wx/choice.h>
-#include <wx/filename.h>
-#include <wx/filesys.h>
 #include <wx/sizer.h>
 #include <wx/stattext.h>
 
@@ -641,8 +640,7 @@ NozzleListTable::NozzleListTable(wxWindow* parent) : wxPanel(parent,wxID_ANY,wxD
     m_web_view->AddScriptMessageHandler("nozzleListTable");
     m_web_view->EnableContextMenu(false);
     fs::path filepath = fs::path(resources_dir()) / "web/flush/NozzleListTable.html";
-    wxFileName fn(wxString::FromUTF8(filepath.string()));
+    wxString url = file_url_from_path(filepath);
-    wxString url = wxFileSystem::FileNameToURL(fn);
     m_web_view->LoadURL(url);
 
     auto sizer = new wxBoxSizer(wxVERTICAL);

src/slic3r/GUI/Widgets/WebHosting.cpp

@@ -48,20 +48,19 @@ constexpr char ORCA_BRIDGE_JS[] = R"JS(
 
 wxString bootstrap_url()
 {
-    return wxString("file://") + from_u8((boost::filesystem::path(resources_dir()) / BOOTSTRAP_PAGE).make_preferred().string());
+    return file_url_from_path(boost::filesystem::path(resources_dir()) / BOOTSTRAP_PAGE);
 }
 
 wxString content_base_url()
 {
-    const std::string dir = (boost::filesystem::path(resources_dir()) / "web").make_preferred().string();
+    return file_url_from_path(boost::filesystem::path(resources_dir()) / "web") + "/";
-    return wxString("file://") + from_u8(dir) + "/";
 }
 
 bool is_content_url(const wxString& url)
 {
-    // The web view reports the URL it parsed, which escapes anything the resources path holds
+    // The web view reports the URL it parsed, which may escape the resources path differently
-    // (a space, a non-ASCII character), while content_base_url() is the raw path.
+    // from content_base_url().
-    return wxURI::Unescape(url.BeforeFirst('#')) == content_base_url();
+    return wxURI::Unescape(url.BeforeFirst('#')) == wxURI::Unescape(content_base_url());
 }
 
 const char* orca_bridge_script() { return ORCA_BRIDGE_JS; }

src/slic3r/GUI/Widgets/WebViewHostDialog.cpp

@@ -192,7 +192,7 @@ bool WebViewHostDialog::create_webview(const std::string& resource_path,
 
 wxString WebViewHostDialog::build_resource_url(const std::string& resource_path) const
 {
-    wxString target_url = from_u8((boost::filesystem::path(resources_dir()) / resource_path).make_preferred().string());
+    wxString target_url = file_url_from_path(boost::filesystem::path(resources_dir()) / resource_path);
 
     if (append_language_to_url()) {
         const wxString lang = wxGetApp().current_language_code_safe();
@@ -202,7 +202,7 @@ wxString WebViewHostDialog::build_resource_url(const std::string& resource_path)
         }
     }
 
-    return wxString("file://") + target_url;
+    return target_url;
 }
 
 void WebViewHostDialog::load_url(const wxString& url)

src/slic3r/GUI/WipeTowerDialog.cpp

@@ -464,7 +464,7 @@ WipingDialog::WipingDialog(wxWindow* parent, const int max_flush_volume) :
     wxString filepath_str = from_path(filepath);
     wxFileName fn(filepath_str);
     if(fn.FileExists()) {
-        wxString url = wxFileSystem::FileNameToURL(fn);
+        wxString url = file_url_from_path(filepath);
         BOOST_LOG_TRIVIAL(debug) << __FUNCTION__<< "File exists and load url " << url.ToStdString();
         m_webview->LoadURL(url);
         BOOST_LOG_TRIVIAL(debug) << __FUNCTION__<< "Successfully loaded url: " << url.ToStdString();

src/slic3r/Utils/ElegooLink.cpp

@@ -340,9 +340,7 @@ namespace Slic3r {
         if (classify_printer_model(config->opt_string("printer_model")) != ElegooPrinterType::CC2)
             return fallback_webui;
 
-        std::string web_path = resources_dir() + "/web/elegoolink/lan_service_web/index.html";
+        std::string web_path = GUI::into_u8(GUI::file_url_from_path(boost::filesystem::path(resources_dir()) / "web/elegoolink/lan_service_web/index.html"));
-        std::replace(web_path.begin(), web_path.end(), '\\', '/');
-        web_path = "file://" + web_path;
         const std::string token   = get_cc2_token(config->opt_string("printhost_apikey"));
         const std::string host_ip = Http::get_host_header_value(host);
 

src/slic3r/Utils/PresetUpdater.cpp

@@ -339,62 +339,8 @@ bool PresetUpdater::priv::get_file(const std::string &url, const fs::path &targe
 //BBS: refine preset update logic
 bool PresetUpdater::priv::extract_file(const fs::path &source_path, const fs::path &dest_path)
 {
-    bool res = true;
+    const std::string parent_path = (!dest_path.empty() ? dest_path : source_path.parent_path()).string();
-    std::string file_path = source_path.string();
+    return extract_archive_confined(source_path.string(), parent_path);
-    std::string parent_path = (!dest_path.empty() ? dest_path : source_path.parent_path()).string();
-    mz_zip_archive archive;
-    mz_zip_zero_struct(&archive);
-
-    if (!open_zip_reader(&archive, file_path))
-    {
-        BOOST_LOG_TRIVIAL(error) << "Unable to open zip reader for "<<file_path;
-        return false;
-    }
-
-    mz_uint num_entries = mz_zip_reader_get_num_files(&archive);
-
-    mz_zip_archive_file_stat stat;
-    // we first loop the entries to read from the archive the .amf file only, in order to extract the version from it
-    for (mz_uint i = 0; i < num_entries; ++i)
-    {
-        if (mz_zip_reader_file_stat(&archive, i, &stat))
-        {
-            std::string dest_file = parent_path+"/"+stat.m_filename;
-            if (stat.m_is_directory) {
-                fs::path dest_path(dest_file);
-                if (!fs::exists(dest_path))
-                    fs::create_directories(dest_path);
-				continue;
-            }
-            else if (stat.m_uncomp_size == 0) {
-                BOOST_LOG_TRIVIAL(warning) << "[Orca Updater]Unzip: invalid size for file "<<stat.m_filename;
-                continue;
-            }
-            try
-            {
-                res = mz_zip_reader_extract_to_file(&archive, stat.m_file_index, dest_file.c_str(), 0);
-                if (!res) {
-                    BOOST_LOG_TRIVIAL(error) << "[Orca Updater]extract file "<<stat.m_filename<<" to dest "<<dest_file<<" failed";
-                    close_zip_reader(&archive);
-                    return res;
-                }
-                BOOST_LOG_TRIVIAL(info) << "[Orca Updater]successfully extract file " << stat.m_file_index << " to "<<dest_file;
-            }
-            catch (const std::exception& e)
-            {
-                // ensure the zip archive is closed and rethrow the exception
-                close_zip_reader(&archive);
-                BOOST_LOG_TRIVIAL(error) << "[Orca Updater]Archive read exception:"<<e.what();
-                return false;
-            }
-        }
-        else {
-            BOOST_LOG_TRIVIAL(warning) << "[Orca Updater]Unzip: read file stat failed";
-        }
-    }
-    close_zip_reader(&archive);
-
-	return true;
 }
 
 // Remove a leftover partial archive for the vendor about to be synchronized.

tests/libslic3r/CMakeLists.txt

@@ -28,7 +28,6 @@ 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
@@ -45,6 +44,7 @@ add_executable(${_TEST_NAME}_tests
     test_lay_on_face.cpp
     test_model.cpp
     test_utils.cpp
+    test_miniz_extension.cpp
     test_timeutils.cpp
     test_voronoi.cpp
     test_wipe_tower_estimate.cpp

tests/libslic3r/test_clipper_utils.cpp

@@ -299,47 +299,3 @@ TEST_CASE("Traversing Clipper PolyTree", "[ClipperUtils]") {
         REQUIRE(count_polys(output) == reference.size());
     }
 }
-
-TEST_CASE("Tiled diff and intersection cover the same area 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 auto xor_area = [](const ExPolygons &a, const ExPolygons &b) { return area(diff_ex(a, b)) + area(diff_ex(b, a)); };
-    const ApplySafetyOffset safety = GENERATE(ApplySafetyOffset::No, ApplySafetyOffset::Yes);
-    const double tolerance = double(scaled<coord_t>(0.001)) * double(span);
-
-    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_THAT(area(diff_tiled), Catch::Matchers::WithinRel(area(diff_plain), 1e-9));
-    CHECK(xor_area(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_THAT(area(intersection_tiled), Catch::Matchers::WithinRel(area(intersection_plain), 1e-9));
-    CHECK(xor_area(intersection_tiled, intersection_plain) < tolerance);
-}

tests/libslic3r/test_kdtree.cpp

@@ -1,67 +0,0 @@
-#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);
-}

tests/libslic3r/test_miniz_extension.cpp

@@ -0,0 +1,194 @@
+#include <catch2/catch_all.hpp>
+
+#include "libslic3r/miniz_extension.hpp"
+
+#include "test_utils.hpp"
+
+#include <boost/filesystem.hpp>
+
+#include <algorithm>
+#include <fstream>
+#include <iterator>
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace Slic3r;
+namespace fs = boost::filesystem;
+
+namespace {
+
+void write_zip(const fs::path &zip_file, const std::vector<std::pair<std::string, std::string>> &entries)
+{
+    mz_zip_archive zip;
+    mz_zip_zero_struct(&zip);
+    REQUIRE(open_zip_writer(&zip, zip_file.string()));
+    for (const auto &[name, content] : entries)
+        REQUIRE(mz_zip_writer_add_mem(&zip, name.c_str(), content.data(), content.size(), MZ_DEFAULT_COMPRESSION));
+    REQUIRE(mz_zip_writer_finalize_archive(&zip));
+    REQUIRE(close_zip_writer(&zip));
+}
+
+// miniz refuses to write a name starting with '/', so write a placeholder of the same length and patch it in place.
+void rename_entry(const fs::path &zip_file, const std::string &from, const std::string &to)
+{
+    REQUIRE(from.size() == to.size());
+    std::string bytes;
+    {
+        std::ifstream in(zip_file.string(), std::ios::binary);
+        bytes.assign(std::istreambuf_iterator<char>(in), std::istreambuf_iterator<char>());
+    }
+    size_t count = 0;
+    for (size_t pos = bytes.find(from); pos != std::string::npos; pos = bytes.find(from, pos + to.size()), ++count)
+        bytes.replace(pos, from.size(), to);
+    // Once in the local header and once in the central directory.
+    REQUIRE(count == 2);
+    std::ofstream out(zip_file.string(), std::ios::binary | std::ios::trunc);
+    out << bytes;
+}
+
+std::vector<std::string> list_dir(const fs::path &dir)
+{
+    std::vector<std::string> names;
+    for (const fs::directory_entry &entry : fs::directory_iterator(dir))
+        names.push_back(entry.path().filename().string());
+    std::sort(names.begin(), names.end());
+    return names;
+}
+
+std::string read_file(const fs::path &file)
+{
+    std::ifstream in(file.string(), std::ios::binary);
+    return std::string(std::istreambuf_iterator<char>(in), std::istreambuf_iterator<char>());
+}
+
+} // namespace
+
+TEST_CASE("Confined extraction writes a well-formed archive under the target directory", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+    write_zip(zip_file, {{"vendor/", ""}, {"vendor/machine/", ""}, {"vendor.json", "{\"a\":1}"}, {"vendor/machine/printer.json", "{\"b\":2}"}});
+
+    REQUIRE(extract_archive_confined(zip_file.string(), target.string()));
+    CHECK(fs::is_directory(target / "vendor"));
+    CHECK(read_file(target / "vendor.json") == "{\"a\":1}");
+    CHECK(read_file(target / "vendor" / "machine" / "printer.json") == "{\"b\":2}");
+}
+
+TEST_CASE("Confined extraction rejects an archive with an entry outside the target directory", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+
+    const std::string escaping_entry = GENERATE(std::string("../escape.txt"), std::string("..\\escape.txt"),
+                                                std::string("sub/../../escape.txt"), std::string("C:/escape.txt"),
+                                                std::string("C:escape.txt"), std::string("\\escape.txt"));
+    // The normal entry comes first so a per-entry check would already have written it.
+    write_zip(zip_file, {{"normal.json", "{}"}, {escaping_entry, "escaped"}});
+
+    CAPTURE(escaping_entry);
+    CHECK_FALSE(extract_archive_confined(zip_file.string(), target.string()));
+    CHECK_FALSE(fs::exists(tmp.path() / "escape.txt"));
+    CHECK(fs::is_empty(target));
+}
+
+TEST_CASE("Confined extraction rejects an archive with an absolute entry name", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+
+    const std::string absolute    = (tmp.path() / "escape.txt").generic_string();
+    const std::string placeholder = "#" + absolute.substr(1);
+    write_zip(zip_file, {{"normal.json", "{}"}, {placeholder, "escaped"}});
+    rename_entry(zip_file, placeholder, absolute);
+
+    CHECK_FALSE(extract_archive_confined(zip_file.string(), target.string()));
+    CHECK_FALSE(fs::exists(tmp.path() / "escape.txt"));
+    CHECK(fs::is_empty(target));
+}
+
+TEST_CASE("Confined extraction rejects a directory entry outside the target directory", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+    write_zip(zip_file, {{"vendor/", ""}, {"../outside/", ""}});
+
+    CHECK_FALSE(extract_archive_confined(zip_file.string(), target.string()));
+    CHECK_FALSE(fs::exists(tmp.path() / "outside"));
+    CHECK(fs::is_empty(target));
+}
+
+TEST_CASE("Confined extraction validates zero-size entries like any other", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+
+    SECTION("an empty file inside the target does not fail the archive") {
+        write_zip(zip_file, {{"empty.json", ""}, {"vendor.json", "{}"}});
+        CHECK(extract_archive_confined(zip_file.string(), target.string()));
+        CHECK(read_file(target / "vendor.json") == "{}");
+    }
+    SECTION("an empty file outside the target rejects the archive") {
+        write_zip(zip_file, {{"vendor.json", "{}"}, {"../escape.txt", ""}});
+        CHECK_FALSE(extract_archive_confined(zip_file.string(), target.string()));
+        CHECK_FALSE(fs::exists(tmp.path() / "escape.txt"));
+        CHECK(fs::is_empty(target));
+    }
+}
+
+TEST_CASE("Confined extraction writes nothing outside the target for Windows-specific name forms", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    fs::create_directories(target);
+
+    // Windows strips trailing dots and spaces and maps device names; whether these extract depends on the
+    // platform, but none of them may land beside the target.
+    const std::string name = GENERATE(std::string("name."), std::string("name "), std::string("..."), std::string(".. "),
+                                      std::string(".. /escape.txt"), std::string(".../escape.txt"), std::string("CON"),
+                                      std::string("sub/NUL.txt"), std::string("C:escape.txt"));
+    write_zip(zip_file, {{name, "payload"}});
+
+    CAPTURE(name);
+    extract_archive_confined(zip_file.string(), target.string());
+    CHECK(list_dir(tmp.path()) == std::vector<std::string>{"bundle.zip", "cache"});
+}
+
+#ifndef _WIN32
+TEST_CASE("Confined extraction replaces a symlink at the destination instead of writing through it", "[MinizExtension]")
+{
+    ScopedTemporaryDir tmp;
+    const fs::path     zip_file = tmp.path() / "bundle.zip";
+    const fs::path     target   = tmp.path() / "cache";
+    const fs::path     outside  = tmp.path() / "outside";
+    fs::create_directories(target);
+    fs::create_directories(outside);
+    write_zip(zip_file, {{"vendor.json", "{\"a\":1}"}});
+
+    SECTION("a dangling symlink") {
+        fs::create_symlink(outside / "vendor.json", target / "vendor.json");
+        CHECK(extract_archive_confined(zip_file.string(), target.string()));
+        CHECK_FALSE(fs::exists(outside / "vendor.json"));
+        CHECK_FALSE(fs::is_symlink(fs::symlink_status(target / "vendor.json")));
+        CHECK(read_file(target / "vendor.json") == "{\"a\":1}");
+    }
+    SECTION("a symlink to an existing file") {
+        { std::ofstream((outside / "vendor.json").string()) << "original"; }
+        fs::create_symlink(outside / "vendor.json", target / "vendor.json");
+        extract_archive_confined(zip_file.string(), target.string());
+        CHECK(read_file(outside / "vendor.json") == "original");
+    }
+}
+#endif

tests/libslic3r/test_utils.cpp

@@ -243,3 +243,82 @@ TEST_CASE("find_unused_filename gives up after 999 versions", "[Utils]") {
     REQUIRE_FALSE(find_unused_filename(dir.path(), "model.3mf", {}, name));
     CHECK(name == "model(999).3mf");
 }
+
+TEST_CASE("is_path_within_root accepts a root given with a trailing separator", "[utils]") {
+    ScopedTemporaryDir tmp;
+    const std::string root = tmp.path().string();
+    const std::string with_separator = GENERATE_COPY(root + "/", root + std::string(1, static_cast<char>(boost::filesystem::path::preferred_separator)));
+
+    CAPTURE(with_separator);
+    CHECK(is_path_within_root("vendor.json", with_separator));
+    CHECK(is_path_within_root("vendor/machine/printer.json", with_separator));
+    CHECK_FALSE(is_path_within_root("../vendor.json", with_separator));
+}
+
+TEST_CASE("is_path_within_root treats Windows-specific name forms the same on every platform", "[utils]") {
+    ScopedTemporaryDir tmp;
+
+    SECTION("names ending in dots or spaces stay inside the root") {
+        const std::string name = GENERATE(std::string("name."), std::string("name "), std::string("dir./file.json"), std::string("dir /file.json"));
+        CAPTURE(name);
+        CHECK(is_path_within_root(name, tmp.path()));
+    }
+    SECTION("drive-relative names are rejected") {
+        const std::string name = GENERATE(std::string("C:x"), std::string("c:x/y.json"), std::string("C:"));
+        CAPTURE(name);
+        CHECK_FALSE(is_path_within_root(name, tmp.path()));
+    }
+}
+
+TEST_CASE("is_path_within_root rejects a name with an embedded NUL", "[utils]") {
+    ScopedTemporaryDir tmp;
+    // The filesystem calls stop at the NUL, so they would act on a different path than the one checked.
+    const std::string name = GENERATE(std::string("..\0", 3), std::string("..\0x/file.json", 14), std::string("sub/..\0x", 8),
+                                      std::string("file.json\0", 10), std::string("\0file.json", 10));
+    CAPTURE(name.size());
+    CHECK_FALSE(is_path_within_root(name, tmp.path()));
+}
+
+TEST_CASE("is_symlink_target_within_root accepts relative targets that stay inside the root", "[utils]") {
+    ScopedTemporaryDir tmp;
+    const auto [link, target] = GENERATE(std::make_pair(std::string("Versions/Current"), std::string("A")),
+                                         std::make_pair(std::string("Foo.framework/Foo"), std::string("Versions/Current/Foo")),
+                                         std::make_pair(std::string("libfoo.so"), std::string("libfoo.so.1")),
+                                         std::make_pair(std::string("a/b/link"), std::string("c/d")));
+    CAPTURE(link, target);
+    CHECK(is_symlink_target_within_root(link, target, tmp.path()));
+}
+
+TEST_CASE("is_symlink_target_within_root rejects absolute targets and targets that climb out", "[utils]") {
+    ScopedTemporaryDir tmp;
+    const std::string outside = (tmp.path().parent_path() / "outside").generic_string();
+    const auto [link, target] = GENERATE_COPY(std::make_pair(std::string("sub/link"), outside),
+                                              std::make_pair(std::string("sub/link"), std::string("/etc/passwd")),
+                                              std::make_pair(std::string("sub/link"), std::string("\\outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("C:/outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("C:outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("")),
+                                              std::make_pair(std::string("link"), std::string("..")),
+                                              std::make_pair(std::string("link"), std::string("../outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("../../outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("x/../../../outside")),
+                                              std::make_pair(std::string("sub/link"), std::string("..\\..\\outside")),
+                                              // symlink() stops at the NUL, so this target would be created as "..".
+                                              std::make_pair(std::string("link"), std::string("..\0", 3)));
+    CAPTURE(link, target);
+    CHECK_FALSE(is_symlink_target_within_root(link, target, tmp.path()));
+}
+
+#ifndef _WIN32
+TEST_CASE("is_symlink_target_within_root rejects a target that passes through a symlink leading out", "[utils]") {
+    ScopedTemporaryDir tmp;
+    const boost::filesystem::path root    = tmp.path() / "root";
+    const boost::filesystem::path outside = tmp.path() / "outside";
+    boost::filesystem::create_directories(root);
+    boost::filesystem::create_directories(outside);
+    boost::filesystem::create_symlink(outside, root / "out");
+
+    CHECK_FALSE(is_symlink_target_within_root("link", "out/lib.so", root));
+    CHECK(is_symlink_target_within_root("link", "in/lib.so", root));
+}
+#endif

tests/slic3rutils/CMakeLists.txt

@@ -27,6 +27,7 @@ add_executable(${_TEST_NAME}_tests
     test_plugin_cloud_metadata.cpp
     test_plugin_audit.cpp
     test_shortcuts.cpp
+    test_file_url.cpp
     ../fff_print/test_helpers.cpp
     )
 

tests/slic3rutils/test_file_url.cpp

@@ -0,0 +1,74 @@
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/generators/catch_generators.hpp>
+
+#include "slic3r/GUI/GUI.hpp"
+
+#include <boost/filesystem/path.hpp>
+
+#include <wx/uri.h>
+
+using namespace Slic3r::GUI;
+
+#ifndef _WIN32
+TEST_CASE("A file URL keeps characters special to URLs in its path", "[FileUrl]")
+{
+    const std::string path = GENERATE(as<std::string>{},
+        "/opt/test#dir/resources/web/homepage/index.html",
+        "/opt/test%20x/resources/web/homepage/index.html",
+        "/opt/Orca Slicer/resources/web/homepage/index.html",
+        "/opt/what?/resources/web/homepage/index.html",
+        "/home/Jos\xC3\xA9/\xE8\xB5\x84\xE6\xBA\x90/resources/web/homepage/index.html");
+
+    const wxString url = file_url_from_path(boost::filesystem::path(path));
+    CAPTURE(path, url.utf8_string());
+
+    // WebView::CreateWebView() and WebView::LoadUrl() re-parse the URL before loading it.
+    const wxURI uri(wxURI(url).BuildURI());
+    CHECK(uri.GetScheme() == "file");
+    CHECK(!uri.HasQuery());
+    CHECK(!uri.HasFragment());
+    CHECK(wxURI::Unescape(uri.GetPath()).utf8_string() == path);
+}
+
+TEST_CASE("A file URL of a plain path is the path behind file://", "[FileUrl]")
+{
+    const std::string path = "/opt/OrcaSlicer/resources/web/homepage/index.html";
+    CHECK(file_url_from_path(boost::filesystem::path(path)) == "file://" + path);
+}
+
+TEST_CASE("A query appended to a file URL stays separate from its path", "[FileUrl]")
+{
+    const std::string path = "/opt/test#dir%20x/resources/web/guide/0/index.html";
+    const wxURI uri(file_url_from_path(boost::filesystem::path(path)) + "?target=21&lang=de");
+    CHECK(wxURI::Unescape(uri.GetPath()).utf8_string() == path);
+    CHECK(uri.GetQuery() == "target=21&lang=de");
+    CHECK(!uri.HasFragment());
+}
+#else
+TEST_CASE("A file URL of a Windows path has a drive letter and forward slashes", "[FileUrl]")
+{
+    const auto [path, url] = GENERATE(table<std::wstring, std::string>({
+        { L"C:\\Program Files\\OrcaSlicer\\resources\\web\\homepage\\index.html",
+          "file:///C:/Program%20Files/OrcaSlicer/resources/web/homepage/index.html" },
+        { L"D:\\#OneDrive\\OrcaSlicer\\resources\\web\\guide\\0\\index.html",
+          "file:///D:/%23OneDrive/OrcaSlicer/resources/web/guide/0/index.html" },
+        { L"D:\\100%\\OrcaSlicer\\resources\\web\\homepage\\index.html",
+          "file:///D:/100%25/OrcaSlicer/resources/web/homepage/index.html" },
+        // Callers join the resources directory with a forward-slash relative path.
+        { L"D:\\#OneDrive\\OrcaSlicer\\resources/web/homepage/index.html",
+          "file:///D:/%23OneDrive/OrcaSlicer/resources/web/homepage/index.html" },
+        { L"\\\\server\\share\\OrcaSlicer\\resources\\web\\homepage\\index.html",
+          "file://server/share/OrcaSlicer/resources/web/homepage/index.html" },
+    }));
+    CHECK(file_url_from_path(boost::filesystem::path(path)).utf8_string() == url);
+}
+
+TEST_CASE("A query appended to a Windows file URL stays separate from its path", "[FileUrl]")
+{
+    const wxURI uri(file_url_from_path(boost::filesystem::path(L"D:\\#OneDrive\\OrcaSlicer\\resources\\web\\guide\\0\\index.html")) +
+                    "?target=21&lang=de");
+    CHECK(wxURI::Unescape(uri.GetPath()) == "/D:/#OneDrive/OrcaSlicer/resources/web/guide/0/index.html");
+    CHECK(uri.GetQuery() == "target=21&lang=de");
+    CHECK(!uri.HasFragment());
+}
+#endif

tests/slic3rutils/test_plugin_host_api.cpp

@@ -16,6 +16,8 @@
 
 #include <string>
 
+#include <wx/uri.h>
+
 namespace py = pybind11;
 
 namespace {
@@ -210,23 +212,33 @@ TEST_CASE("A reloaded plugin page is recognised by its base URL, fragment aside"
 {
     using namespace Slic3r::GUI::web_hosting;
 
-    // A resources path holding a space, which the web view reports escaped.
+    // A resources path holding a space, which the web view may report escaped differently.
     const Slic3r::ScopedResourcesDir resources("web content check");
 
     // The swapped-in page, then after an in-page anchor and a reload.
     CHECK(is_content_url(content_base_url()));
     CHECK(is_content_url(content_base_url() + "#tab2"));
-    wxString escaped = content_base_url();
+    const wxString unescaped = wxURI::Unescape(content_base_url());
-    escaped.Replace(" ", "%20");
+    REQUIRE(unescaped != content_base_url());
-    REQUIRE(escaped != content_base_url());
+    CHECK(is_content_url(unescaped));
-    CHECK(is_content_url(escaped));
+    CHECK(is_content_url(unescaped + "#tab2"));
-    CHECK(is_content_url(escaped + "#tab2"));
     // A page the plugin linked to keeps its own URL and must be left alone.
     CHECK_FALSE(is_content_url(content_base_url() + "guide.html"));
     CHECK_FALSE(is_content_url("https://example.com/"));
     CHECK_FALSE(is_content_url(""));
 }
 
+TEST_CASE("A reloaded plugin page is recognised when the resources path holds a '#'", "[PluginHost]")
+{
+    using namespace Slic3r::GUI::web_hosting;
+
+    const Slic3r::ScopedResourcesDir resources("web#content check");
+
+    CHECK(is_content_url(content_base_url()));
+    CHECK(is_content_url(content_base_url() + "#tab2"));
+    CHECK_FALSE(is_content_url(content_base_url() + "guide.html"));
+}
+
 TEST_CASE("Plugin host API exposes model geometry and structure to Python", "[PluginHost][Python]")
 {
     using Catch::Matchers::WithinAbs;