Merge branch 'main' into feature/texture-color-number

The green highlight and tint no longer cover a colour preview, and return while a stroke is
painted. The Fast view also keeps the other parts of a multi-part object.

docs/HLSD/polygon-clipping.md

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

resources/shaders/110/texture_displacement_shaded.fs

@@ -29,13 +29,11 @@ uniform vec3      palette_lab[64];
 uniform vec3      palette_rgb[64];
 uniform int       palette_count;
 uniform bool      pure_only;      // match against single filaments only (flat-colour image)
-// How each entry prints. Every entry names a single filament: a mix is given its own mixed filament
-// slot, whose components the slicer alternates per print layer, so the fragment just looks that slot's
-// colour up.
+// The entry's two filaments, equal for a single filament - only so a mix can be told apart. An entry's
+// palette_rgb is already the colour it prints in (for a mix, its mixed filament slot's).
 uniform int       palette_a[64];
 uniform int       palette_b[64];
-uniform vec3      filament_rgb[16];
-uniform int       filament_count;
+uniform float     prefer_pure_de; // PREFER_PURE_DE: how much better than a single filament a mix must be
 uniform sampler2D color_tex;     // the layer's colour image, sampled at the same uv as the height
 uniform bool      has_color_tex;
 uniform bool volume_mirrored;
@@ -210,31 +208,16 @@ int nearest_palette_entry(vec3 rgb)
             best = i;
         }
     }
-    // The same bias make_palette_quantizer() applies (PREFER_PURE_DE = 10): a mix is an interleave, so
-    // it is only worth taking when it beats the nearest single filament by a visible step. Without it
-    // this picked a mix for almost every fragment - with four filaments the palette is 4 pure entries
-    // against 30 mixes - while the bake picked a single filament for most of them, so the preview
-    // interleaved the whole wall where the bake interleaves only patches. Compared on the distances
-    // rather than their squares, so the threshold means the same thing as it does on the CPU (up to
-    // CIE76 against CIEDE2000, the approximation already noted above).
-    if (best_pure >= 0 && palette_a[best] != palette_b[best] && sqrt(bd_pure) - sqrt(bd) < 10.0)
+    // The same bias make_palette_quantizer() applies: a mix is an interleave, so it is only worth taking
+    // when it beats the nearest single filament by a visible step - otherwise the preview shows mixes
+    // where the bake prints a single filament. Compared on the distances rather than their squares, so
+    // the margin means the same thing as it does on the CPU (up to CIE76 against CIEDE2000, the
+    // approximation already noted above).
+    if (best_pure >= 0 && palette_a[best] != palette_b[best] && sqrt(bd_pure) - sqrt(bd) < prefer_pure_de)
         best = best_pure;
     return best;
 }
 
-// One 2x2 Bayer cell, {0, 2; 3, 1}, for x and y in {0, 1}.
-
-// The colour the printer lays down at world point `pos` for palette entry `index`. Every entry names a
-// single filament: a mix is given its own mixed filament slot, whose components the slicer alternates
-// per print layer, so there is nothing left to interleave here.
-vec3 printed_color(int index)
-{
-    int a = palette_a[index];
-    if (a < 0 || a >= filament_count)
-        return palette_rgb[index]; // no filament to resolve to: the entry's own colour
-    return filament_rgb[a];
-}
-
 void main()
 {
     if (any(lessThan(clipping_planes_dots, ZERO)))
@@ -354,16 +337,11 @@ void main()
     NdotL = max(dot(eye_normal, LIGHT_FRONT_DIR), 0.0);
     intensity.x += NdotL * LIGHT_FRONT_DIFFUSE;
 
-    // Diffuse albedo: the image's colour at this fragment, snapped to the nearest printable colour -
-    // and, where that is a mix, the filament the interleave puts here, so the pattern that prints shows.
+    // Diffuse albedo: the image's colour at this fragment, snapped to the nearest printable colour.
     // Only the albedo - the specular term (intensity.y) stays white - so a coloured fragment reads as
     // the same material under the same light, and the relief this preview exists to show is unaffected.
     vec3 albedo = uniform_color.rgb;
     if (palette_count > 0 && has_color_tex && have_uv && weight > 0.0)
-        // tex_pos, not world_pos: the bake resolves the interleave in the bake frame (world
-        // orientation and scale about the volume's origin, see texture_displacement_bake_frame()), so
-        // measuring z from the bed instead shifted the band phase by the volume origin's height - a
-        // different filament in the same place than the bake produces.
-        albedo = printed_color(nearest_palette_entry(texture2D(color_tex, color_uv).rgb));
+        albedo = palette_rgb[nearest_palette_entry(texture2D(color_tex, color_uv).rgb)];
     gl_FragColor = vec4(vec3(intensity.y) + albedo * intensity.x, uniform_color.a);
 }

resources/shaders/140/texture_displacement_shaded.fs

@@ -88,13 +88,11 @@ uniform vec3      palette_lab[64];
 uniform vec3      palette_rgb[64];
 uniform int       palette_count;
 uniform bool      pure_only;      // match against single filaments only (flat-colour image)
-// How each entry prints. Every entry names a single filament: a mix is given its own mixed filament
-// slot, whose components the slicer alternates per print layer, so the fragment just looks that slot's
-// colour up.
+// The entry's two filaments, equal for a single filament - only so a mix can be told apart. An entry's
+// palette_rgb is already the colour it prints in (for a mix, its mixed filament slot's).
 uniform int       palette_a[64];
 uniform int       palette_b[64];
-uniform vec3      filament_rgb[16];
-uniform int       filament_count;
+uniform float     prefer_pure_de; // PREFER_PURE_DE: how much better than a single filament a mix must be
 uniform sampler2D color_tex;     // the layer's colour image, sampled at the same uv as the height
 uniform bool      has_color_tex;
 uniform bool volume_mirrored;
@@ -276,31 +274,16 @@ int nearest_palette_entry(vec3 rgb)
             best = i;
         }
     }
-    // The same bias make_palette_quantizer() applies (PREFER_PURE_DE = 10): a mix is an interleave, so
-    // it is only worth taking when it beats the nearest single filament by a visible step. Without it
-    // this picked a mix for almost every fragment - with four filaments the palette is 4 pure entries
-    // against 30 mixes - while the bake picked a single filament for most of them, so the preview
-    // interleaved the whole wall where the bake interleaves only patches. Compared on the distances
-    // rather than their squares, so the threshold means the same thing as it does on the CPU (up to
-    // CIE76 against CIEDE2000, the approximation already noted above).
-    if (best_pure >= 0 && palette_a[best] != palette_b[best] && sqrt(bd_pure) - sqrt(bd) < 10.0)
+    // The same bias make_palette_quantizer() applies: a mix is an interleave, so it is only worth taking
+    // when it beats the nearest single filament by a visible step - otherwise the preview shows mixes
+    // where the bake prints a single filament. Compared on the distances rather than their squares, so
+    // the margin means the same thing as it does on the CPU (up to CIE76 against CIEDE2000, the
+    // approximation already noted above).
+    if (best_pure >= 0 && palette_a[best] != palette_b[best] && sqrt(bd_pure) - sqrt(bd) < prefer_pure_de)
         best = best_pure;
     return best;
 }
 
-// One 2x2 Bayer cell, {0, 2; 3, 1}, for x and y in {0, 1}.
-
-// The colour the printer lays down at world point `pos` for palette entry `index`. Every entry names a
-// single filament: a mix is given its own mixed filament slot, whose components the slicer alternates
-// per print layer, so there is nothing left to interleave here.
-vec3 printed_color(int index)
-{
-    int a = palette_a[index];
-    if (a < 0 || a >= filament_count)
-        return palette_rgb[index]; // no filament to resolve to: the entry's own colour
-    return filament_rgb[a];
-}
-
 void main()
 {
     if (any(lessThan(clipping_planes_dots, ZERO)))
@@ -442,16 +425,11 @@ void main()
     NdotL = max(dot(eye_normal, LIGHT_FRONT_DIR), 0.0);
     intensity.x += NdotL * LIGHT_FRONT_DIFFUSE;
 
-    // Diffuse albedo: the image's colour at this fragment, snapped to the nearest printable colour -
-    // and, where that is a mix, the filament the interleave puts here, so the pattern that prints shows.
+    // Diffuse albedo: the image's colour at this fragment, snapped to the nearest printable colour.
     // Only the albedo - the specular term (intensity.y) stays white - so a coloured fragment reads as
     // the same material under the same light, and the relief this preview exists to show is unaffected.
     vec3 albedo = uniform_color.rgb;
     if (palette_count > 0 && has_color_tex && have_uv && weight > 0.0)
-        // tex_pos, not world_pos: the bake resolves the interleave in the bake frame (world
-        // orientation and scale about the volume's origin, see texture_displacement_bake_frame()), so
-        // measuring z from the bed instead shifted the band phase by the volume origin's height - a
-        // different filament in the same place than the bake produces.
-        albedo = printed_color(nearest_palette_entry(texture(color_tex, color_uv).rgb));
+        albedo = palette_rgb[nearest_palette_entry(texture(color_tex, color_uv).rgb)];
     out_color = vec4(vec3(intensity.y) + albedo * intensity.x, uniform_color.a);
 }

src/libslic3r/ClipperUtils.cpp

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

src/libslic3r/ClipperUtils.hpp

@@ -5,7 +5,6 @@
 #include "Polyline.hpp"
 #include "Line.hpp"
 #include "libslic3r.h"
-#include "BoundingBox.hpp"
 #include "ExPolygon.hpp"
 #include "Polygon.hpp"
 #include "Surface.hpp"
@@ -333,15 +332,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 Clipper on a
-    // layer of many pieces tile by tile. Returns the non-empty tiles, each with the indices of its ExPolygons and their box.
-    struct ExPolygonsTile
-    {
-        BoundingBox         bbox;
-        std::vector<size_t> members;
-    };
-    [[nodiscard]] std::vector<ExPolygonsTile> tile_expolygons(const ExPolygons &expolygons, size_t per_tile);
-
     }
 
 // offset Polygons
@@ -537,11 +527,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: Clipper slows down with the number of edges crossing a scan line.
-Slic3r::ExPolygons diff_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
-Slic3r::ExPolygons intersection_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::Polygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polyline &subject, const Slic3r::ExPolygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::ExPolygon &clip);

src/libslic3r/FilamentMixer.cpp

@@ -18,6 +18,7 @@
 #include <utility>
 
 #include "ColorDecomposeRecipe.hpp"
+#include "Config.hpp"
 #include "FilamentMixerModel.hpp"
 #include "LocalesUtils.hpp"
 
@@ -427,6 +428,59 @@ std::vector<double> parse_mixed_ratios(const std::string &str, size_t n_componen
     return ratios;
 }
 
+std::string format_mixed_components(const std::vector<unsigned int> &components)
+{
+    std::string out;
+    for (size_t i = 0; i < components.size(); ++i) {
+        if (i > 0)
+            out += ",";
+        out += std::to_string(components[i]);
+    }
+    return out;
+}
+
+std::string format_mixed_ratios(const std::vector<int> &weights)
+{
+    int sum = std::accumulate(weights.begin(), weights.end(), 0);
+    if (sum <= 0)
+        sum = 100;
+    CNumericLocalesSetter c_locale_setter;
+    std::string           out;
+    for (size_t i = 0; i < weights.size(); ++i) {
+        if (i > 0)
+            out += ",";
+        char buf[32];
+        std::snprintf(buf, sizeof(buf), "%.4f", float(weights[i]) / float(sum));
+        out += buf;
+    }
+    return out;
+}
+
+int find_fixed_mixed_filament(const ConfigBase                &project_config,
+                              const std::vector<unsigned int> &components,
+                              const std::vector<int>          &weights)
+{
+    const auto *is_mixed = project_config.option<ConfigOptionBools>("filament_is_mixed");
+    const auto *comps    = project_config.option<ConfigOptionStrings>("filament_mixed_components");
+    const auto *ratios   = project_config.option<ConfigOptionStrings>("filament_mixed_sublayer_ratios");
+    if (is_mixed == nullptr || comps == nullptr || ratios == nullptr)
+        return -1;
+    // Created lazily with the first mixed slot, so an older project may not have it at all.
+    const auto *gradient = project_config.option<ConfigOptionBools>("filament_mixed_gradient");
+
+    const std::string comp_str  = format_mixed_components(components);
+    const std::string ratio_str = format_mixed_ratios(weights);
+    for (size_t i = 0; i < is_mixed->values.size(); ++i) {
+        if (!is_mixed->values[i] || i >= comps->values.size() || i >= ratios->values.size())
+            continue;
+        if (gradient != nullptr && i < gradient->values.size() && gradient->values[i])
+            continue;
+        if (comps->values[i] == comp_str && ratios->values[i] == ratio_str)
+            return int(i);
+    }
+    return -1;
+}
+
 bool has_any_mixed_filament(const std::vector<unsigned char> &is_mixed)
 {
     for (unsigned char v : is_mixed)

src/libslic3r/FilamentMixer.hpp

@@ -11,6 +11,8 @@
 
 namespace Slic3r {
 
+class ConfigBase;
+
 // Photoshop-style gradient curve control point in [0,1] x [0,1].
 // (x, y) is the anchor position; (m_in, m_out) are optional cubic Hermite tangent
 // overrides. NaN means "use the PCHIP-computed default", which is the case for plain
@@ -94,6 +96,22 @@ std::vector<unsigned int> parse_mixed_components(const std::string &str);
 // Normalizes so the sum equals 1.0.
 std::vector<double> parse_mixed_ratios(const std::string &str, size_t n_components);
 
+// The text a mixed slot stores in filament_mixed_components, e.g. {1, 3} → "1,3".
+std::string format_mixed_components(const std::vector<unsigned int> &components);
+
+// The text a mixed slot stores in filament_mixed_sublayer_ratios: the weights normalised to sum to 1,
+// four decimals, e.g. {1, 2} → "0.3333,0.6667". A non-positive sum is read as 100.
+std::string format_mixed_ratios(const std::vector<int> &weights);
+
+// The 0-based index of the mixed slot in `project_config` that blends `components` (1-based physical
+// filaments) in `weights` at a fixed ratio, or -1 when there is none. Matched on the stored text, as
+// format_mixed_components() and format_mixed_ratios() write it. A gradient slot never matches: its
+// ratio drifts from layer to layer, so it is not the blend asked for even where its stored ratios
+// are the same.
+int find_fixed_mixed_filament(const ConfigBase                &project_config,
+                              const std::vector<unsigned int> &components,
+                              const std::vector<int>          &weights);
+
 // Returns true if any element in is_mixed is true.
 // ConfigOptionBools stores values as std::vector<unsigned char>.
 bool has_any_mixed_filament(const std::vector<unsigned char> &is_mixed);

src/libslic3r/Fill/Fill.cpp

@@ -22,8 +22,6 @@
 #include "../PrintConfig.hpp"
 #include "../Surface.hpp"
 
-#include <tbb/parallel_for.h>
-
 #include "AABBTreeLines.hpp"
 #include "libslic3r/Config.hpp"
 #include "libslic3r/ExPolygon.hpp"
@@ -666,28 +664,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.
-        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];
+        for (const ExPolygon &expolygon : fill.expolygons) {
             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);
-                return;
+                narrow_infill.emplace_back(expolygon);
+                continue;
             }
 
             ExPolygons inner_ex = union_ex(inner_area);
             ExPolygons expolys{expolygon};
-            split_parts[idx].second = diff_ex(expolys, inner_ex);         // narrow infill area
-            split_parts[idx].first  = intersection_ex(expolys, inner_ex); // normal infill area
-        });
-        for (auto &[normal_ex, narrow_ex] : split_parts) {
-            append(normal_infill, std::move(normal_ex));
-            append(narrow_infill, std::move(narrow_ex));
+            ExPolygons narrow_ex = diff_ex(expolys, inner_ex);
+            ExPolygons normal_ex = intersection_ex(expolys, inner_ex);
+
+            append(normal_infill, normal_ex); // normal infill area
+            append(narrow_infill, narrow_ex); // narrow infill area
         }
 
         return;
@@ -709,10 +703,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.
-    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];
+	for (const ExPolygon &expolygon : fill.expolygons) {
         Polygons filled_area = to_polygons(expolygon);
         polygons_rotate(filled_area, aligning_angle);
         BoundingBox bb = get_extents(filled_area);
@@ -843,10 +834,8 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
             }
         }
 
-        split_reconstructed[expolygon_idx] = std::move(reconstructed_area);
-    });
-    for (Polygons &reconstructed_area : split_reconstructed)
-        polygons_append(normal_fill_areas, std::move(reconstructed_area));
+        polygons_append(normal_fill_areas, reconstructed_area);
+    }
 
     polygons_rotate(normal_fill_areas, -aligning_angle);
 
@@ -1461,15 +1450,7 @@ void Layer::make_fills(const FillAdaptive::RegionOctrees* fill_octrees, FillLigh
             f->set_bounding_box(body >= 0 ? this->object()->separated_body_bboxes()[body] : bbox);
             f->adapt_fill_octree = octrees ? octrees->get(body) : nullptr;
 
-            // Only the part of the layer-wide no-overlap area under this expolygon matters, so clip it to the
-            // expolygon's box first (padded past the safety offset, which grows the clip side). The result is
-            // identical; the cost is not: a layer split into many small fills, e.g. by colour painting,
-            // otherwise intersects every one of them with the whole layer.
-            BoundingBox no_overlap_bbox = get_extents(expoly);
-            no_overlap_bbox.offset(SCALED_EPSILON);
-            f->no_overlap_expolygons = intersection_ex(
-                ClipperUtils::clip_clipper_polygons_with_subject_bbox(surface_fill.no_overlap_expolygons, no_overlap_bbox),
-                ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
+            f->no_overlap_expolygons = intersection_ex(surface_fill.no_overlap_expolygons, 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

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

src/libslic3r/GCode/SeamPlacer.cpp

@@ -29,7 +29,6 @@
 #include <memory>
 #include <random>
 #include <algorithm>
-#include <limits>
 #include <queue>
 #include <string>
 #include <unordered_map>
@@ -1211,21 +1210,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
-  // the radius, so they are looked at as the search finds them rather than collected into a vector first.
-  constexpr size_t none = std::numeric_limits<size_t>::max();
-  size_t best_nearby_point_index = none;
-  size_t nearest_point_index = none;
-  visit_nearby_points(*layers[layer_idx].points_tree, projected_position, max_distance,
-                      [&layers, &comparator, &projected_position, layer_idx, &best_nearby_point_index, &nearest_point_index]
-                      (size_t nearby_point_index) {
-    if (best_nearby_point_index == none) {
-      // The first point found starts both, as the first of the collected ones did.
-      best_nearby_point_index = nearest_point_index = nearby_point_index;
-    }
+  std::vector<size_t> nearby_points_indices = find_nearby_points(*layers[layer_idx].points_tree, projected_position,
+                                                                 max_distance);
+
+  if (nearby_points_indices.empty()) {
+    return {};
+  }
+
+  size_t best_nearby_point_index = nearby_points_indices[0];
+  size_t nearest_point_index = nearby_points_indices[0];
+
+  // Now find best nearby point, nearest point, and corresponding indices
+  for (const size_t &nearby_point_index : nearby_points_indices) {
     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>())
@@ -1237,10 +1236,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

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

@@ -99,11 +99,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

@@ -22,7 +22,6 @@
 #include "Surface.hpp"
 #include "libslic3r.h"
 
-#include <numeric>
 #include <cmath>
 #include <cstddef>
 #include <list>
@@ -1363,15 +1362,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.
-    // 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.
+    // When the upper surface of an object is occluded, it should no longer be considered the upper surface
     {
-        const size_t occluded_pairs = num_facets_states * layers.size();
-        tbb::parallel_for(tbb::blocked_range<size_t>(0, occluded_pairs), [&](const tbb::blocked_range<size_t> &range) {
-            for (size_t pair_idx = range.begin(); pair_idx < range.end(); ++pair_idx) {
-                const size_t extruder_idx = pair_idx / layers.size();
-                const size_t layer_idx    = pair_idx % layers.size();
+        for (size_t extruder_idx = 0; extruder_idx < num_facets_states; ++extruder_idx) {
+            for (size_t layer_idx = 0; layer_idx < layers.size(); ++layer_idx) {
                 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]);
                 }
@@ -1379,7 +1373,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);
@@ -1437,58 +1431,11 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
         return out;
     };
 
-    // Projects a painted top or bottom face `ex` of layer `layer_idx` onto the shell layers below or above it (in
-    // `shell_layers`, nearest first), one more perimeter in on each, stopping at the first layer where nothing is left.
-    // Only the slices within the deepest offset of `ex` (three times that with the miter joins) decide the result, so the
-    // work is done per tile of `ex`'s ExPolygons on the slices cut to the tile's box grown by that much: the same result, but
-    // each Clipper call stays the size of a tile rather than of a layer cut through a fine relief, and the tiles run in
-    // parallel.
-    const auto project_to_shells = [&input_expolygons](const ExPolygons &ex, size_t layer_idx, const std::vector<size_t> &shell_layers,
-                                                       const LayerColorStat &stat, ShellProjections &dst) {
-        std::vector<float> offsets(shell_layers.size());
-        float              offset = 0.f;
-        for (size_t i = 0; i < shell_layers.size(); ++i) {
-            //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
-            offset -= (stat.extrusion_spacing + stat.extrusion_width);
-            offsets[i] = offset;
-        }
-        if (offsets.empty())
-            return;
-        const coord_t reach = coord_t(std::ceil(DefaultMiterLimit * std::abs(offsets.back()))) + 10 * SCALED_EPSILON;
-        const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(ex, 16);
-        // [shell layer][tile]
-        std::vector<std::vector<ExPolygons>> shells(shell_layers.size(), std::vector<ExPolygons>(tiles.size()));
-        tbb::parallel_for(size_t(0), tiles.size(), [&](size_t tile_idx) {
-            const ClipperUtils::ExPolygonsTile &tile = tiles[tile_idx];
-            const BoundingBox                   bbox = tile.bbox.inflated(reach);
-            ExPolygons                          tile_ex;
-            tile_ex.reserve(tile.members.size());
-            for (size_t i : tile.members)
-                tile_ex.emplace_back(ex[i]);
-            Polygons layer_slices_trimmed = ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[layer_idx], bbox);
-            for (size_t i = 0; i < shell_layers.size() && ! layer_slices_trimmed.empty(); ++i) {
-                const ExPolygons trimmed = intersection_ex(layer_slices_trimmed, ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[shell_layers[i]], bbox));
-                shells[i][tile_idx]  = opening_ex(intersection_ex(tile_ex, offset_ex(trimmed, offsets[i])), stat.small_region_threshold);
-                layer_slices_trimmed = to_polygons(trimmed);
-            }
-        });
-        for (size_t i = 0; i < shell_layers.size(); ++i) {
-            ExPolygons shell;
-            for (ExPolygons &tile_shell : shells[i])
-                append(shell, std::move(tile_shell));
-            if (shell.empty())
-                break;
-            dst.emplace_back(shell_layers[i], std::move(shell));
-        }
-    };
-
     tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&num_layers, &num_facets_states, &layer_color_stat, &top_raw, &triangles_by_color_top,
-                                                                  &throw_on_cancel_callback, &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) {
         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
-            // 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) {
+            for (size_t color_idx = 0; color_idx < num_facets_states; ++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())
@@ -1497,10 +1444,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], top_ex);
-                            std::vector<size_t> shell_layers;
-                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx)
-                                shell_layers.emplace_back(size_t(last_idx));
-                            project_to_shells(top_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_top[color_idx][layer_idx]);
+                            float offset = 0.f;
+                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
+                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx) {
+                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+                                //offset -= stat.extrusion_width ;
+                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
+                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
+                                ExPolygons last = opening_ex(intersection_ex(top_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
+                                if (last.empty())
+                                    break;
+                                shell_triangles_by_color_top[color_idx][layer_idx].emplace_back(size_t(last_idx), std::move(last));
+                            }
                         }
                     }
                 if (std::vector<Polygons> &bottom = bottom_raw[color_idx]; ! bottom.empty() && ! bottom[layer_idx].empty())
@@ -1509,13 +1464,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], bottom_ex);
-                            std::vector<size_t> shell_layers;
-                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx)
-                                shell_layers.emplace_back(last_idx);
-                            project_to_shells(bottom_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_bottom[color_idx][layer_idx]);
+                            float offset = 0.f;
+                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
+                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx) {
+                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+                                //offset -= stat.extrusion_width;
+                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
+                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
+                                ExPolygons last = opening_ex(intersection_ex(bottom_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
+                                if (last.empty())
+                                    break;
+                                shell_triangles_by_color_bottom[color_idx][layer_idx].emplace_back(last_idx, std::move(last));
+                            }
                         }
                     }
-            });
+            }
         }
     });
 
@@ -1536,23 +1499,20 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                                                                   &shell_top_by_layer, &shell_bottom_by_layer](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
             throw_on_cancel_callback();
-            // The per-colour unions below are independent of each other, so they run in parallel (a painted top or
-            // bottom face puts all of its colours on one layer); whatever combines the colours stays in colour order.
-            const auto merge_colour_union = [&](size_t color_idx) {
+            ExPolygons painted_exploys;
+            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];
                 append(self, std::move(triangles_by_color_bottom[color_idx][layer_idx]));
                 append(self, std::move(triangles_by_color_top[color_idx][layer_idx]));
                 self = union_ex(self);
-            };
-            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), merge_colour_union);
 
-            ExPolygons painted_exploys;
-            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx)
-                append(painted_exploys, triangles_by_color_merged[color_idx][layer_idx]);
+                append(painted_exploys, self);
+            }
+
             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_top_by_layer[color_idx][layer_idx]), painted_exploys);
@@ -1561,7 +1521,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) {
@@ -1928,69 +1888,7 @@ static void remove_multiple_edges_in_vertices(MMU_Graph &graph, const std::vecto
     }
 }
 
-
-// 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,
+static std::vector<std::vector<ExPolygons>> merge_segmented_layers(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)
@@ -2001,91 +1899,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
-    // apart than the dimple removal below reaches, so this gives the same result as merging the layer at once. On a layer
-    // cut through a fine relief every region shares thousands of hole contours with every other, and Clipper, splitting
-    // and re-linking one huge polygon over and over, took anything up to half an hour for a layer; per island each operation
-    // stays the size of the island, and the islands run in parallel.
-    tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&](const tbb::blocked_range<size_t> &range) {
+    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) {
         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();
-            // 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.
+            // Zero is skipped because it is the default color of the volume
             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()) {
-                    for (size_t bucket = 0; bucket < num_buckets; ++bucket)
-                        append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
-                    continue;
+                throw_on_cancel_callback();
+                if (!segmented_regions[layer_idx][extruder_id].empty()) {
+                    ExPolygons segmented_regions_trimmed = segmented_regions[layer_idx][extruder_id];
+                    if (!top_and_bottom_layers.empty()) {
+                        for (const std::vector<ExPolygons> &top_and_bottom_by_extruder : top_and_bottom_layers) {
+                            if (!top_and_bottom_by_extruder[layer_idx].empty() && !segmented_regions_trimmed.empty()) {
+                                segmented_regions_trimmed = diff_ex(segmented_regions_trimmed, top_and_bottom_by_extruder[layer_idx]);
+                            }
+                        }
+                    }
+
+                    segmented_regions_merged[layer_idx][extruder_id - 1] = std::move(segmented_regions_trimmed);
+                }
+
+                if (!top_and_bottom_layers.empty() && !top_and_bottom_layers[extruder_id][layer_idx].empty()) {
+                    bool was_top_and_bottom_empty = segmented_regions_merged[layer_idx][extruder_id - 1].empty();
+                    append(segmented_regions_merged[layer_idx][extruder_id - 1], top_and_bottom_layers[extruder_id][layer_idx]);
+
+                    // Remove dimples (#7235) appearing after merging side segmentation of the model with tops and bottoms painted layers.
+                    if (!was_top_and_bottom_empty)
+                        segmented_regions_merged[layer_idx][extruder_id - 1] = offset2_ex(union_ex(segmented_regions_merged[layer_idx][extruder_id - 1]), float(SCALED_EPSILON), -float(SCALED_EPSILON));
                 }
-                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
@@ -2373,56 +2213,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
-                // that island's contours than to any other island's - the way out crosses its own boundary first - so its
-                // Voronoi cells, and with them its colour regions, depend on nothing else. A layer cut through a fine relief
-                // has thousands of islands, and one Voronoi diagram over all of them degenerated into overlapping regions
-                // that every boolean afterwards had to untangle. Per island the diagrams stay small and the islands run in
-                // parallel; an island in a single colour needs no diagram at all.
-                const ExPolygons                      &islands = input_expolygons[layer_idx];
-                std::vector<std::pair<size_t, size_t>> island_contours(islands.size()); // [first, last) into color_poly
-                {
-                    // The same order EdgeGrid::Grid::create() lists the contours in, and so colorize_contours().
-                    size_t idx = 0;
-                    for (size_t island_idx = 0; island_idx < islands.size(); ++island_idx) {
-                        const size_t first = idx;
-                        if (!islands[island_idx].contour.empty())
-                            ++idx;
-                        for (const Polygon &hole : islands[island_idx].holes)
-                            if (!hole.empty())
-                                ++idx;
-                        island_contours[island_idx] = {first, idx};
-                    }
-                    assert(idx == color_poly.size());
+                if (has_layer_only_one_color(color_poly)) {
+                    // If the whole layer is painted using the same color, it is not needed to construct a Voronoi diagram for the segmentation of this layer.
+                    segmented_regions[layer_idx][size_t(color_poly.front().front().color)] = input_expolygons[layer_idx];
+                } else {
+                    MMU_Graph graph = build_graph(layer_idx, color_poly);
+                    remove_multiple_edges_in_vertices(graph, color_poly);
+                    graph.remove_nodes_with_one_arc();
+                    segmented_regions[layer_idx] = extract_colored_segments(graph, num_facets_states);
+                    //segmented_regions[layer_idx] = extract_colored_segments(color_poly, num_extruders, layer_idx);
                 }
-                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]);
@@ -2445,7 +2245,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

@@ -23,15 +23,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, which
-    // also means a moved-from Polygon or Polyline is now really empty where it used to silently keep its
-    // points: a use-after-move anywhere in the tree that happened to work before now sees nothing.
-    explicit MultiPoint(Points &&_points) noexcept : points(std::move(_points)) {}
     MultiPoint& operator=(const MultiPoint &other) { points = other.points; return *this; }
-    MultiPoint& operator=(MultiPoint &&other) 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

@@ -32,8 +32,6 @@
 #include <tuple>
 #include <unordered_set>
 #include <thread>
-#include <tbb/blocked_range.h>
-#include <tbb/parallel_for.h>
 #include <vector>
 #include "libslic3r.h"
 #include <utility>
@@ -2554,490 +2552,467 @@ 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
-    // of islands (e.g. by colour painting) otherwise ran on one thread - and the outputs are then committed in the
-    // original island order, which is what the extra overhang perimeters (applied to the last island's loops and to
-    // all fill surfaces so far) depend on.
-    struct ArachneSurfaceResult
-    {
-        ExtrusionEntityCollection loops;
-        bool                      has_loops = false;
-        ExPolygons                infill;
-        ExPolygons                no_overlap;
-    };
-    std::vector<ArachneSurfaceResult> results(all_surfaces.size());
-    tbb::parallel_for(tbb::blocked_range<size_t>(0, all_surfaces.size()), [&](const tbb::blocked_range<size_t> &range) {
-      for (size_t surface_idx = range.begin(); surface_idx < range.end(); ++surface_idx) {
-        const Surface        &surface = all_surfaces[surface_idx];
-        ArachneSurfaceResult &result  = results[surface_idx];
-            coord_t bead_width_0 = ext_perimeter_spacing;
-            // detect how many perimeters must be generated for this island
-            int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
-            int sparse_infill_density = this->config->sparse_infill_density.value;
-            if (this->config->alternate_extra_wall && this->layer_id % 2 == 1 && !m_spiral_vase && sparse_infill_density > 0) // add alternating extra wall
-                loop_number++;
+    for (const Surface& surface : all_surfaces) {
+        coord_t bead_width_0 = ext_perimeter_spacing;
+        // detect how many perimeters must be generated for this island
+        int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
+        int sparse_infill_density = this->config->sparse_infill_density.value;
+        if (this->config->alternate_extra_wall && this->layer_id % 2 == 1 && !m_spiral_vase && sparse_infill_density > 0) // add alternating extra wall
+            loop_number++;
 
-            // Set the bottommost layer to be one wall
-            const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
-            if (is_bottom_layer && only_one_wall_first_layer)
-                loop_number = 0;
+        // Set the bottommost layer to be one wall
+        const bool is_bottom_layer = (this->layer_id == object_config->raft_layers) ? true : false;
+        if (is_bottom_layer && only_one_wall_first_layer)
+            loop_number = 0;
 
-            // Orca: set the topmost layer to be one wall according to the config
-            const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
-            if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
-                loop_number = 0;
+        // Orca: set the topmost layer to be one wall according to the config
+        const bool is_topmost_layer = (this->upper_slices == nullptr) ? true : false;
+        if (is_topmost_layer && loop_number > 0 && only_one_wall_top)
+            loop_number = 0;
         
-            auto apply_precise_outer_wall = config->precise_outer_wall && config->wall_sequence == WallSequence::InnerOuter;
-            // Orca: properly adjust offset for the outer wall if precise_outer_wall is enabled.
-            ExPolygons last = offset_ex(surface.expolygon.simplify_p(surface_simplify_resolution),
-                           apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
-                                                     : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
+        auto apply_precise_outer_wall = config->precise_outer_wall && config->wall_sequence == WallSequence::InnerOuter;
+        // Orca: properly adjust offset for the outer wall if precise_outer_wall is enabled.
+        ExPolygons last = offset_ex(surface.expolygon.simplify_p(surface_simplify_resolution),
+                       apply_precise_outer_wall? -float(ext_perimeter_width - ext_perimeter_spacing )
+                                                 : -float(ext_perimeter_width / 2. - ext_perimeter_spacing / 2.));
         
-            Arachne::WallToolPathsParams input_params = Arachne::make_paths_params(this->layer_id, *object_config, *print_config);
-            // Set params is_top_or_bottom_layer for adjusting short-wall removal sensitivity.
-            input_params.is_top_or_bottom_layer = (is_bottom_layer || is_topmost_layer) ? true : false;
+        Arachne::WallToolPathsParams input_params = Arachne::make_paths_params(this->layer_id, *object_config, *print_config);
+        // Set params is_top_or_bottom_layer for adjusting short-wall removal sensitivity.
+        input_params.is_top_or_bottom_layer = (is_bottom_layer || is_topmost_layer) ? true : false;
 
-            coord_t wall_0_inset = 0;
-            if (apply_precise_outer_wall)
-               wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
+        coord_t wall_0_inset = 0;
+        if (apply_precise_outer_wall)
+           wall_0_inset = -coord_t(ext_perimeter_width / 2 - ext_perimeter_spacing / 2);
 
-            //PS: One wall top surface for Arachne
-            ExPolygons top_expolygons;
-            // Calculate how many inner loops remain when TopSurfaces is selected.
-            const int inner_loop_number = (only_one_wall_top && upper_slices != nullptr) ? loop_number - 1 : -1;
+        //PS: One wall top surface for Arachne
+        ExPolygons top_expolygons;
+        // Calculate how many inner loops remain when TopSurfaces is selected.
+        const int inner_loop_number = (only_one_wall_top && upper_slices != nullptr) ? loop_number - 1 : -1;
 
-            // Set one perimeter when TopSurfaces is selected.
-            if (only_one_wall_top && loop_number > 0)
-                loop_number = 0;
+        // Set one perimeter when TopSurfaces is selected.
+        if (only_one_wall_top && loop_number > 0)
+            loop_number = 0;
 
-            Arachne::WallToolPathsParams input_params_tmp = input_params;
+        Arachne::WallToolPathsParams input_params_tmp = input_params;
         
-            Polygons   last_p = to_polygons(last);
-            Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
-                                                   wall_0_inset, layer_height, input_params_tmp);
-            std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
-            ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
+        Polygons   last_p = to_polygons(last);
+        Arachne::WallToolPaths wallToolPaths(last_p, bead_width_0, perimeter_spacing, coord_t(loop_number + 1),
+                                               wall_0_inset, layer_height, input_params_tmp);
+        std::vector<Arachne::VariableWidthLines>   perimeters = wallToolPaths.getToolPaths();
+        ExPolygons  infill_contour = union_ex(wallToolPaths.getInnerContour());
 
-            // Check if there are some remaining perimeters to generate (the number of perimeters
-            // is greater than one together with enabled the single perimeter on top surface feature).
-            if (inner_loop_number >= 0) {
-                assert(upper_slices != nullptr);
+        // Check if there are some remaining perimeters to generate (the number of perimeters
+        // is greater than one together with enabled the single perimeter on top surface feature).
+        if (inner_loop_number >= 0) {
+            assert(upper_slices != nullptr);
 
-                coord_t perimeter_width = this->perimeter_flow.scaled_width();
+            coord_t perimeter_width = this->perimeter_flow.scaled_width();
 
-                // 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);
+            // 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);
 
-                // Get top ExPolygons from the given contour. uncovered reports whether the upper layer leaves any of the
-                // contour uncovered, before bridges and too thin areas are filtered out.
-                auto get_top_expolygons = [&](const ExPolygons &contour, bool &uncovered) {
-                    // Contour bounding box.
-                    BoundingBox contour_bbox = get_extents(contour);
-                    contour_bbox.offset(SCALED_EPSILON);
+            // Get top ExPolygons from the given contour. uncovered reports whether the upper layer leaves any of the
+            // contour uncovered, before bridges and too thin areas are filtered out.
+            auto get_top_expolygons = [&](const ExPolygons &contour, bool &uncovered) {
+                // Contour bounding box.
+                BoundingBox contour_bbox = get_extents(contour);
+                contour_bbox.offset(SCALED_EPSILON);
 
-                    Polygons upper_slices_clipped;
-                    if (object_config->interface_shells) {
-                        auto upper_slicer_same_region = to_expolygons(this->upper_slices_same_region->surfaces);
-                        upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(upper_slicer_same_region, contour_bbox);
-                    } else
-                        upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*upper_slices, contour_bbox);
+                Polygons upper_slices_clipped;
+                if (object_config->interface_shells) {
+                    auto upper_slicer_same_region = to_expolygons(this->upper_slices_same_region->surfaces);
+                    upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(upper_slicer_same_region, contour_bbox);
+                } else
+                    upper_slices_clipped = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*upper_slices, contour_bbox);
 
-                    ExPolygons top = diff_ex(contour, upper_slices_clipped);
-                    uncovered      = !top.empty();
-                    if (top.empty())
-                        return top;
+                ExPolygons top = diff_ex(contour, upper_slices_clipped);
+                uncovered      = !top.empty();
+                if (top.empty())
+                    return top;
 
-                    if (lower_slices != nullptr) {
-                        const float      bridge_offset          = float(std::max<coord_t>(ext_perimeter_spacing, perimeter_width));
-                        const Polygons   lower_slices_clipped   = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*lower_slices, contour_bbox);
-                        const ExPolygons current_slices_bridges = offset_ex(diff_ex(top, lower_slices_clipped), bridge_offset);
+                if (lower_slices != nullptr) {
+                    const float      bridge_offset          = float(std::max<coord_t>(ext_perimeter_spacing, perimeter_width));
+                    const Polygons   lower_slices_clipped   = ClipperUtils::clip_clipper_polygons_with_subject_bbox(*lower_slices, contour_bbox);
+                    const ExPolygons current_slices_bridges = offset_ex(diff_ex(top, lower_slices_clipped), bridge_offset);
 
-                        // Remove bridges from top surface polygons.
-                        top = diff_ex(top, current_slices_bridges);
-                    }
-
-                    // 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 = offset2_ex(top, -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).
-                    return intersection_ex(top, contour);
-                };
-
-                // Walls with the full count, as generated when the single perimeter feature is disabled. Generated on first use.
-                std::vector<Arachne::VariableWidthLines> full_perimeters;
-                Polygons                                 full_inner_contour;
-                bool                                     full_perimeters_generated = false;
-                auto generate_full_perimeters = [&]() {
-                    if (full_perimeters_generated)
-                        return;
-                    Arachne::WallToolPaths full_tool_paths(last_p, bead_width_0, perimeter_spacing, coord_t(inner_loop_number + 2), wall_0_inset, layer_height, input_params_tmp);
-                    full_perimeters           = full_tool_paths.getToolPaths();
-                    full_inner_contour        = full_tool_paths.getInnerContour();
-                    full_perimeters_generated = true;
-                };
-
-                // ORCA: the single wall pass allows Arachne 2 beads across a wall, so it fills a wall narrower than 3 outer wall
-                // widths by widening both, where the full pass adds a middle bead. Over the top surface that is the intent;
-                // anywhere else it leaves no room for the inner walls. When the single wall pass's outer walls run away from
-                // the full pass's outside the top surface, take the full pass's outer walls and the area inside them instead.
-                // Walls closer than outer_wall_tolerance count as the same wall: a widened bead's centerline moves by half
-                // the width added, and only beads widened by more than twice the tolerance are looked for.
-                const coord_t outer_wall_tolerance = bead_width_0 / 10;
-                if (widest_bead(perimeters) > bead_width_0 + 2 * outer_wall_tolerance) {
-                    // The single wall pass's inner contour where it widens no bead: inside nominal width outer walls.
-                    const ExPolygons nominal_infill_contour = offset_ex(last, -float(bead_width_0 + wall_0_inset));
-                    bool             nominal_uncovered      = false;
-                    // Grown by an outer wall width to take in the outer walls bordering the top surface.
-                    const ExPolygons top_zone = offset_ex(get_top_expolygons(nominal_infill_contour, nominal_uncovered), float(bead_width_0));
-                    if (nominal_uncovered) {
-                        generate_full_perimeters();
-                        if (! full_perimeters.empty() && ! full_perimeters.front().empty() &&
-                            length_off_reference(perimeters, full_perimeters.front(), top_zone, outer_wall_tolerance) > double(perimeter_width)) {
-                            perimeters     = { full_perimeters.front() };
-                            infill_contour = diff_ex(nominal_infill_contour, walls_footprint(full_perimeters.front()), ApplySafetyOffset::Yes);
-                        }
-                    }
+                    // Remove bridges from top surface polygons.
+                    top = diff_ex(top, current_slices_bridges);
                 }
 
-                bool uncovered = false;
-                top_expolygons = get_top_expolygons(infill_contour, uncovered);
+                // 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 = offset2_ex(top, -top_surface_min_width, top_surface_min_width + float(perimeter_width * 0.85));
 
-                if (uncovered) {
-                    // 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();
+                // Get final top ExPolygons (bridges were excluded above, so they stay walled).
+                return intersection_ex(top, contour);
+            };
 
-                    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);
-                    }
+            // Walls with the full count, as generated when the single perimeter feature is disabled. Generated on first use.
+            std::vector<Arachne::VariableWidthLines> full_perimeters;
+            Polygons                                 full_inner_contour;
+            bool                                     full_perimeters_generated = false;
+            auto generate_full_perimeters = [&]() {
+                if (full_perimeters_generated)
+                    return;
+                Arachne::WallToolPaths full_tool_paths(last_p, bead_width_0, perimeter_spacing, coord_t(inner_loop_number + 2), wall_0_inset, layer_height, input_params_tmp);
+                full_perimeters           = full_tool_paths.getToolPaths();
+                full_inner_contour        = full_tool_paths.getInnerContour();
+                full_perimeters_generated = true;
+            };
 
-                    // 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 use the walls generated like when the single perimeter
-                    // feature is disabled.
+            // ORCA: the single wall pass allows Arachne 2 beads across a wall, so it fills a wall narrower than 3 outer wall
+            // widths by widening both, where the full pass adds a middle bead. Over the top surface that is the intent;
+            // anywhere else it leaves no room for the inner walls. When the single wall pass's outer walls run away from
+            // the full pass's outside the top surface, take the full pass's outer walls and the area inside them instead.
+            // Walls closer than outer_wall_tolerance count as the same wall: a widened bead's centerline moves by half
+            // the width added, and only beads widened by more than twice the tolerance are looked for.
+            const coord_t outer_wall_tolerance = bead_width_0 / 10;
+            if (widest_bead(perimeters) > bead_width_0 + 2 * outer_wall_tolerance) {
+                // The single wall pass's inner contour where it widens no bead: inside nominal width outer walls.
+                const ExPolygons nominal_infill_contour = offset_ex(last, -float(bead_width_0 + wall_0_inset));
+                bool             nominal_uncovered      = false;
+                // Grown by an outer wall width to take in the outer walls bordering the top surface.
+                const ExPolygons top_zone = offset_ex(get_top_expolygons(nominal_infill_contour, nominal_uncovered), float(bead_width_0));
+                if (nominal_uncovered) {
                     generate_full_perimeters();
-                    perimeters     = std::move(full_perimeters);
-                    infill_contour = union_ex(full_inner_contour);
+                    if (! full_perimeters.empty() && ! full_perimeters.front().empty() &&
+                        length_off_reference(perimeters, full_perimeters.front(), top_zone, outer_wall_tolerance) > double(perimeter_width)) {
+                        perimeters     = { full_perimeters.front() };
+                        infill_contour = diff_ex(nominal_infill_contour, walls_footprint(full_perimeters.front()), ApplySafetyOffset::Yes);
+                    }
                 }
             }
-            //PS
 
-            loop_number = int(perimeters.size()) - 1;
+            bool uncovered = false;
+            top_expolygons = get_top_expolygons(infill_contour, uncovered);
 
-            #ifdef ARACHNE_DEBUG
-            {
-                static int iRun = 0;
-                export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
+            if (uncovered) {
+                // 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 use the walls generated like when the single perimeter
+                // feature is disabled.
+                generate_full_perimeters();
+                perimeters     = std::move(full_perimeters);
+                infill_contour = union_ex(full_inner_contour);
             }
-    #endif
+        }
+        //PS
 
-            // All closed ExtrusionLine should have the same the first and the last point.
-            // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
-            // equal the first and the last point.
-            assert([&perimeters = std::as_const(perimeters)]() -> bool {
-                for (const Arachne::VariableWidthLines& perimeter : perimeters)
-                    for (const Arachne::ExtrusionLine& el : perimeter)
-                        if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
-                            return false;
-                return true;
-            }());
+        loop_number = int(perimeters.size()) - 1;
 
-            int start_perimeter = int(perimeters.size()) - 1;
-            int end_perimeter = -1;
-            int direction = -1;
+        #ifdef ARACHNE_DEBUG
+        {
+            static int iRun = 0;
+            export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
+        }
+#endif
 
-    		bool is_outer_wall_first =
-                	this->config->wall_sequence == WallSequence::OuterInner ||
-                	this->config->wall_sequence == WallSequence::InnerOuterInner;
+        // All closed ExtrusionLine should have the same the first and the last point.
+        // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
+        // equal the first and the last point.
+        assert([&perimeters = std::as_const(perimeters)]() -> bool {
+            for (const Arachne::VariableWidthLines& perimeter : perimeters)
+                for (const Arachne::ExtrusionLine& el : perimeter)
+                    if (el.is_closed && el.junctions.front().p != el.junctions.back().p)
+                        return false;
+            return true;
+        }());
+
+        int start_perimeter = int(perimeters.size()) - 1;
+        int end_perimeter = -1;
+        int direction = -1;
+
+		bool is_outer_wall_first =
+            	this->config->wall_sequence == WallSequence::OuterInner ||
+            	this->config->wall_sequence == WallSequence::InnerOuterInner;
         
-            if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
-            	is_outer_wall_first =
-                	this->config->wall_sequence == WallSequence::OuterInner;
-            }
-            if (is_outer_wall_first) {
-                start_perimeter = 0;
-                end_perimeter = int(perimeters.size());
-                direction = 1;
+        if (layer_id == 0){ // disable inner outer inner algorithm after the first layer
+        	is_outer_wall_first =
+            	this->config->wall_sequence == WallSequence::OuterInner;
+        }
+        if (is_outer_wall_first) {
+            start_perimeter = 0;
+            end_perimeter = int(perimeters.size());
+            direction = 1;
+        }
+
+        std::vector<Arachne::ExtrusionLine*> all_extrusions;
+        for (int perimeter_idx = start_perimeter; perimeter_idx != end_perimeter; perimeter_idx += direction) {
+            if (perimeters[perimeter_idx].empty())
+                continue;
+            for (Arachne::ExtrusionLine& wall : perimeters[perimeter_idx])
+                all_extrusions.emplace_back(&wall);
+        }
+
+        // Find topological order with constraints from extrusions_constrains.
+        std::vector<size_t>              blocked(all_extrusions.size(), 0); // Value indicating how many extrusions it is blocking (preceding extrusions) an extrusion.
+        std::vector<std::vector<size_t>> blocking(all_extrusions.size());   // Each extrusion contains a vector of extrusions that are blocked by this extrusion.
+        std::unordered_map<const Arachne::ExtrusionLine*, size_t> map_extrusion_to_idx;
+        for (size_t idx = 0; idx < all_extrusions.size(); idx++)
+            map_extrusion_to_idx.emplace(all_extrusions[idx], idx);
+
+        auto extrusions_constrains = Arachne::WallToolPaths::getRegionOrder(all_extrusions, is_outer_wall_first);
+        for (auto [before, after] : extrusions_constrains) {
+            auto after_it = map_extrusion_to_idx.find(after);
+            ++blocked[after_it->second];
+            blocking[map_extrusion_to_idx.find(before)->second].emplace_back(after_it->second);
+        }
+
+        std::vector<bool> processed(all_extrusions.size(), false);          // Indicate that the extrusion was already processed.
+        Point             current_position = all_extrusions.empty() ? Point::Zero() : all_extrusions.front()->junctions.front().p; // Some starting position.
+        std::vector<PerimeterGeneratorArachneExtrusion> ordered_extrusions;         // To store our result in. At the end we'll std::swap.
+        ordered_extrusions.reserve(all_extrusions.size());
+
+        while (ordered_extrusions.size() < all_extrusions.size()) {
+            size_t best_candidate = 0;
+            double best_distance_sqr = std::numeric_limits<double>::max();
+            bool   is_best_closed = false;
+
+            std::vector<size_t> available_candidates;
+            for (size_t candidate = 0; candidate < all_extrusions.size(); ++candidate) {
+                if (processed[candidate] || blocked[candidate])
+                    continue; // Not a valid candidate.
+                available_candidates.push_back(candidate);
             }
 
-            std::vector<Arachne::ExtrusionLine*> all_extrusions;
-            for (int perimeter_idx = start_perimeter; perimeter_idx != end_perimeter; perimeter_idx += direction) {
-                if (perimeters[perimeter_idx].empty())
+            std::sort(available_candidates.begin(), available_candidates.end(), [&all_extrusions](const size_t a_idx, const size_t b_idx) -> bool {
+                return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
+                });
+
+            for (const size_t candidate_path_idx : available_candidates) {
+                auto& path = all_extrusions[candidate_path_idx];
+
+                if (path->junctions.empty()) { // No vertices in the path. Can't find the start position then or really plan it in. Put that at the end.
+                    if (best_distance_sqr == std::numeric_limits<double>::max()) {
+                        best_candidate = candidate_path_idx;
+                        is_best_closed = path->is_closed;
+                    }
                     continue;
-                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 {
-                    return all_extrusions[a_idx]->is_closed < all_extrusions[b_idx]->is_closed;
-                    });
-
-                for (const size_t candidate_path_idx : available_candidates) {
-                    auto& path = all_extrusions[candidate_path_idx];
-
-                    if (path->junctions.empty()) { // No vertices in the path. Can't find the start position then or really plan it in. Put that at the end.
-                        if (best_distance_sqr == std::numeric_limits<double>::max()) {
-                            best_candidate = candidate_path_idx;
-                            is_best_closed = path->is_closed;
-                        }
-                        continue;
-                    }
-
-                    const Point candidate_position = path->junctions.front().p;
-                    double      distance_sqr = (current_position - candidate_position).cast<double>().norm();
-                    if (distance_sqr < best_distance_sqr) { // Closer than the best candidate so far.
-                        if (path->is_closed || (!path->is_closed && best_distance_sqr != std::numeric_limits<double>::max()) || (!path->is_closed && !is_best_closed)) {
-                            best_candidate = candidate_path_idx;
-                            best_distance_sqr = distance_sqr;
-                            is_best_closed = path->is_closed;
-                        }
+                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
-            if (this->config->wall_sequence == WallSequence::InnerOuterInner && layer_id > 0) { // only enable inner outer inner algorithm after first layer
-                if (ordered_extrusions.size() > 2) { // 3 walls minimum needed to do inner outer inner ordering
-                    int position = 0; // index to run the re-ordering for multiple external perimeters in a single island.
-                    int arr_i, arr_j = 0;    // indexes to run through the walls in the for loops
-                    int outer, first_internal, second_internal, max_internal, current_perimeter; // allocate index values
-                
-                    // To address any remaining scenarios where the outer perimeter contour is not first on the list as arachne sometimes reorders the perimeters when clustering
-                    // for OI mode that is used the basis for IOI
-                    bringContoursToFront(ordered_extrusions);
-                    std::vector<PerimeterGeneratorArachneExtrusion> reordered_extrusions;
-                
-                    // Debug statement to print spacing values:
-                    //printf("External threshold - Ext perimeter: %d Ext spacing: %d Int perimeter: %d Int spacing: %d\n", this->ext_perimeter_flow.scaled_width(),this->ext_perimeter_flow.scaled_spacing(),this->perimeter_flow.scaled_width(), this->perimeter_flow.scaled_spacing());
+            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]--;
 
-                    // Get searching thresholds. For an external perimeter we take the external perimeter spacing/2 plus the internal perimeter spacing/2 and expand by the factor
-                    // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
-                    coord_t threshold_external = (apply_precise_outer_wall)
-                        // Precise outer wall: use the full external spacing
-                        ? ( this->ext_perimeter_flow.scaled_spacing()
-                            + this->perimeter_flow.scaled_spacing()/2.0 )
-                        // Normal: half ext spacing plus half int spacing
-                        : ( this->ext_perimeter_flow.scaled_spacing()/2.0
-                            + this->perimeter_flow.scaled_spacing()/2.0 );
+            if (!best_path->junctions.empty()) { //If all paths were empty, the best path is still empty. We don't upate the current position then.
+                if (best_path->is_closed)
+                    current_position = best_path->junctions[0].p; //We end where we started.
+                else
+                    current_position = best_path->junctions.back().p; //Pick the other end from where we started.
+            }
+        }
+
+       // printf("New Layer: Layer ID %d\n",layer_id); //debug - new layer
+        if (this->config->wall_sequence == WallSequence::InnerOuterInner && layer_id > 0) { // only enable inner outer inner algorithm after first layer
+            if (ordered_extrusions.size() > 2) { // 3 walls minimum needed to do inner outer inner ordering
+                int position = 0; // index to run the re-ordering for multiple external perimeters in a single island.
+                int arr_i, arr_j = 0;    // indexes to run through the walls in the for loops
+                int outer, first_internal, second_internal, max_internal, current_perimeter; // allocate index values
                 
-                    // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
-                    coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
+                // 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;
                 
-                    // Re-order extrusions based on distance
-                    // Alorithm will aggresively optimise for the appearance of the outermost perimeter
-                    ordered_extrusions = reorderPerimetersByProximity(ordered_extrusions,threshold_external,threshold_internal );
-                    reordered_extrusions = ordered_extrusions; // copy them into the reordered extrusions vector to allow for IOI operations to be performed below without altering the base ordered extrusions list.
+                // Debug statement to print spacing values:
+                //printf("External threshold - Ext perimeter: %d Ext spacing: %d Int perimeter: %d Int spacing: %d\n", this->ext_perimeter_flow.scaled_width(),this->ext_perimeter_flow.scaled_spacing(),this->perimeter_flow.scaled_width(), this->perimeter_flow.scaled_spacing());
+
+                // Get searching thresholds. For an external perimeter we take the external perimeter spacing/2 plus the internal perimeter spacing/2 and expand by the factor
+                // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
+                coord_t threshold_external = (apply_precise_outer_wall)
+                    // Precise outer wall ⇒ use “full external spacing”
+                    ? ( this->ext_perimeter_flow.scaled_spacing()
+                        + this->perimeter_flow.scaled_spacing()/2.0 )
+                    // Normal ⇒ half ext spacing + half int spacing
+                    : ( this->ext_perimeter_flow.scaled_spacing()/2.0
+                        + this->perimeter_flow.scaled_spacing()/2.0 );
                 
-                    // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
-                    // scan to find the external perimeter, first internal, second internal and last perimeter in the island.
-                    // We then advance the position index to move to the second island and continue until there are no more
-                    // perimeters left.
-                    while (position < reordered_extrusions.size()) {
-                        outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
-                        max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
-                        // run through the walls to get the index values that need re-ordering until the first one for each
-                        // is found. Start at "position" index to enable the for loop to iterate for multiple external
-                        // perimeters in a single island
-                        // printf("Reorder Loop. Position %d, extrusion list size: %d, Outer index %d, inner index %d, second inner index %d\n", position, reordered_extrusions.size(),outer,first_internal,second_internal);
-                        for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
-                            // printf("Perimeter: extrusion inset index %d, ordered extrusions array position %d\n",reordered_extrusions[arr_i].extrusion->inset_idx, arr_i);
-                            switch (reordered_extrusions[arr_i].extrusion->inset_idx) {
-                                case 0: // external perimeter
-                                    if (outer == -1)
-                                        outer = arr_i;
-                                    break;
-                                case 1: // first internal wall
-                                    if (first_internal==-1 && arr_i>outer && outer!=-1){
-                                        first_internal = arr_i;
-                                    }
-                                    break;
-                                case 2: // second internal wall
-                                    if (second_internal == -1 && arr_i > first_internal && outer!=-1){
-                                        second_internal = arr_i;
-                                    }
-                                    break;
-                            }
-                            if(outer >-1 && first_internal>-1 && reordered_extrusions[arr_i].extrusion->inset_idx == 0){  // found a new external perimeter after we've found at least a first internal perimeter to re-order.
-                                                                                                                          // This means we entered a new island.
-                                arr_i=arr_i-1; //step back one perimeter
-                                max_internal = arr_i; // new maximum internal perimeter is now this as we have found a new external perimeter, hence a new island.
-                                break; // exit the for loop
-                            }
-                        }
-                    
-                        // printf("Layer ID %d, Outer index %d, inner index %d, second inner index %d, maximum internal perimeter %d \n",layer_id,outer,first_internal,second_internal, max_internal);
-                        if (outer > -1 && first_internal > -1 && second_internal > -1) { // found all three perimeters to re-order? If not the perimeters will be processed outside in.
-                            std::vector<PerimeterGeneratorArachneExtrusion> inner_outer_extrusions; // temporary array to hold extrusions for reordering
-                            inner_outer_extrusions.resize(max_internal - position + 1); // reserve array containing the number of perimeters before a new island. Variables are array indexes hence need to add +1 to convert to position allocations
-                            // printf("Allocated array size %d, max_internal index %d, start position index %d \n",max_internal-position+1,max_internal,position);
-                        
-                            for (arr_j = max_internal; arr_j >=position; --arr_j){ // go inside out towards the external perimeter (perimeters in reverse order) and store all internal perimeters until the first one identified with inset index 2
-                                if(arr_j >= second_internal){
-                                    //printf("Inside out loop: Mapped perimeter index %d to array position %d\n", arr_j, max_internal-arr_j);
-                                    inner_outer_extrusions[max_internal-arr_j] = reordered_extrusions[arr_j];
-                                    current_perimeter++; 
+                // For the intenal perimeter threshold, the distance is the internal perimeter spacing expanded by the factor to cover rounding errors.
+                coord_t threshold_internal = this->perimeter_flow.scaled_spacing();
+                
+                // Re-order extrusions based on distance
+                // Alorithm will aggresively optimise for the appearance of the outermost perimeter
+                ordered_extrusions = reorderPerimetersByProximity(ordered_extrusions,threshold_external,threshold_internal );
+                reordered_extrusions = ordered_extrusions; // copy them into the reordered extrusions vector to allow for IOI operations to be performed below without altering the base ordered extrusions list.
+                
+                // Now start the sandwich mode wall re-ordering using the reordered_extrusions as the basis
+                // scan to find the external perimeter, first internal, second internal and last perimeter in the island.
+                // We then advance the position index to move to the second island and continue until there are no more
+                // perimeters left.
+                while (position < reordered_extrusions.size()) {
+                    outer = first_internal = second_internal = current_perimeter = -1; // initialise all index values to -1
+                    max_internal = reordered_extrusions.size()-1; // initialise the maximum internal perimeter to the last perimeter on the extrusion list
+                    // run through the walls to get the index values that need re-ordering until the first one for each
+                    // is found. Start at "position" index to enable the for loop to iterate for multiple external
+                    // perimeters in a single island
+                    // printf("Reorder Loop. Position %d, extrusion list size: %d, Outer index %d, inner index %d, second inner index %d\n", position, reordered_extrusions.size(),outer,first_internal,second_internal);
+                    for (arr_i = position; arr_i < reordered_extrusions.size(); ++arr_i) {
+                        // printf("Perimeter: extrusion inset index %d, ordered extrusions array position %d\n",reordered_extrusions[arr_i].extrusion->inset_idx, arr_i);
+                        switch (reordered_extrusions[arr_i].extrusion->inset_idx) {
+                            case 0: // external perimeter
+                                if (outer == -1)
+                                    outer = arr_i;
+                                break;
+                            case 1: // first internal wall
+                                if (first_internal==-1 && arr_i>outer && outer!=-1){
+                                    first_internal = arr_i;
                                 }
-                            }
-                        
-                            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];
+                                break;
+                            case 2: // second internal wall
+                                if (second_internal == -1 && arr_i > first_internal && outer!=-1){
+                                    second_internal = arr_i;
+                                }
+                                break;
+                        }
+                        if(outer >-1 && first_internal>-1 && reordered_extrusions[arr_i].extrusion->inset_idx == 0){  // found a new external perimeter after we've found at least a first internal perimeter to re-order.
+                                                                                                                      // This means we entered a new island.
+                            arr_i=arr_i-1; //step back one perimeter
+                            max_internal = arr_i; // new maximum internal perimeter is now this as we have found a new external perimeter, hence a new island.
+                            break; // exit the for loop
                         }
-                        // 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_hole    = false;
-            if (!config->overhang_reverse) {
-                // Skip steep overhang detection no reverse is specified
-                steep_overhang_contour = true;
-                steep_overhang_hole    = true;
-            }
-            if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
-                if (config->overhang_reverse) {
-                    reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
-                                        this->config->overhang_reverse_internal_only);
-                }
-                defer_unsupported_loops(*this, extrusion_coll);
-                result.loops     = std::move(extrusion_coll);
-                result.has_loops = true;
+        bool steep_overhang_contour = false;
+        bool steep_overhang_hole    = false;
+        if (!config->overhang_reverse) {
+            // Skip steep overhang detection no reverse is specified
+            steep_overhang_contour = true;
+            steep_overhang_hole    = true;
+        }
+        if (ExtrusionEntityCollection extrusion_coll = traverse_extrusions(*this, ordered_extrusions, steep_overhang_contour, steep_overhang_hole); !extrusion_coll.empty()) {
+            if (config->overhang_reverse) {
+                reorient_perimeters(extrusion_coll, steep_overhang_contour, steep_overhang_hole,
+                                    this->config->overhang_reverse_internal_only);
             }
+            defer_unsupported_loops(*this, extrusion_coll);
+            this->loops->append(extrusion_coll);
+        }
 
-            const coord_t spacing = (perimeters.size() == 1) ? ext_perimeter_spacing2 : perimeter_spacing;
+        const coord_t spacing = (perimeters.size() == 1) ? ext_perimeter_spacing2 : perimeter_spacing;
 
-            if (offset_ex(infill_contour, -float(spacing / 2.)).empty())
-                infill_contour.clear(); // Infill region is too small, so let's filter it out.
+        if (offset_ex(infill_contour, -float(spacing / 2.)).empty())
+            infill_contour.clear(); // Infill region is too small, so let's filter it out.
 
-            // create one more offset to be used as boundary for fill
-            // we offset by half the perimeter spacing (to get to the actual infill boundary)
-            // and then we offset back and forth by half the infill spacing to only consider the
-            // non-collapsing regions
-            coord_t inset =
-                (loop_number < 0) ? 0 :
-                (loop_number == 0) ?
-                // one loop
-                ext_perimeter_spacing :
-                // two or more loops?
-                perimeter_spacing;
-            coord_t top_inset = inset;
+        // create one more offset to be used as boundary for fill
+        // we offset by half the perimeter spacing (to get to the actual infill boundary)
+        // and then we offset back and forth by half the infill spacing to only consider the
+        // non-collapsing regions
+        coord_t inset =
+            (loop_number < 0) ? 0 :
+            (loop_number == 0) ?
+            // one loop
+            ext_perimeter_spacing :
+            // two or more loops?
+            perimeter_spacing;
+        coord_t top_inset = inset;
         
-            top_inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
-            if(is_topmost_layer || is_bottom_layer)
-                inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
-            else
-                inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+        top_inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+        if(is_topmost_layer || is_bottom_layer)
+            inset = coord_t(scale_(this->config->top_bottom_infill_wall_overlap.get_abs_value(unscale<double>(inset))));
+        else
+            inset = coord_t(scale_(this->config->infill_wall_overlap.get_abs_value(unscale<double>(inset))));
         
-            // simplify infill contours according to resolution
-            Polygons pp;
-            for (ExPolygon& ex : infill_contour)
-                ex.simplify_p(m_scaled_resolution, &pp);
-            ExPolygons not_filled_exp = union_ex(pp);
-            // collapse too narrow infill areas
-            const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
+        // simplify infill contours according to resolution
+        Polygons pp;
+        for (ExPolygon& ex : infill_contour)
+            ex.simplify_p(m_scaled_resolution, &pp);
+        ExPolygons not_filled_exp = union_ex(pp);
+        // collapse too narrow infill areas
+        const auto    min_perimeter_infill_spacing = coord_t(solid_infill_spacing * (1. - INSET_OVERLAP_TOLERANCE));
 
-            ExPolygons infill_exp = offset2_ex(
+        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.));
-            // append infill areas to fill_surfaces
-            if (!top_expolygons.empty()) {
-                infill_exp = union_ex(infill_exp, offset_ex(top_expolygons, double(top_inset)));
-            }
-            result.infill = std::move(infill_exp);
-
-            // BBS: get the no-overlap infill expolygons
-            {
-                ExPolygons polyWithoutOverlap;
-                polyWithoutOverlap = offset2_ex(
-                    not_filled_exp,
-                    float(-min_perimeter_infill_spacing / 2.),
-                    float(+min_perimeter_infill_spacing / 2.));
-                if (!top_expolygons.empty())
-                    polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
-                result.no_overlap = std::move(polyWithoutOverlap);
-            }
-      }
-    });
-    for (ArachneSurfaceResult &result : results) {
-        if (result.has_loops)
-            // Moved, not copied: append(const ExtrusionEntity &) clones the whole wall tree of the island.
-            this->loops->append(std::move(result.loops));
-        this->fill_surfaces->append(result.infill, stInternal);
-        apply_extra_perimeters(result.infill);
-        append(*this->fill_no_overlap, std::move(result.no_overlap));
+                float(+min_perimeter_infill_spacing / 2.));
+            if (!top_expolygons.empty())
+                polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
+            this->fill_no_overlap->insert(this->fill_no_overlap->end(), polyWithoutOverlap.begin(), polyWithoutOverlap.end());
+        }
     }
 }
 

src/libslic3r/Polygon.hpp

@@ -34,7 +34,7 @@ public:
     explicit Polygon(const Points &points) : MultiPoint(points) {}
 	Polygon(std::initializer_list<Point> points) : MultiPoint(points) {}
     Polygon(const Polygon &other) : MultiPoint(other.points) {}
-    Polygon(Polygon &&other) 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());
@@ -43,7 +43,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

@@ -26,7 +26,7 @@ class Polyline : public MultiPoint {
 public:
     Polyline() {};
     Polyline(const Polyline& other) : MultiPoint(other.points), fitting_result(other.fitting_result) {}
-    Polyline(Polyline &&other) 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();
     }
@@ -47,7 +47,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

@@ -47,7 +47,6 @@
 #include <cstdlib>
 #include <cstdint>
 #include <float.h>
-#include <array>
 #include <functional>
 #include <ios>
 #include <iomanip>
@@ -74,7 +73,6 @@
 #include <Eigen/Core>
 
 #include <tbb/parallel_for.h>
-#include <tbb/parallel_invoke.h>
 #include <tbb/spin_mutex.h>
 #include <tbb/concurrent_unordered_set.h>
 
@@ -1944,9 +1942,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
-    // 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) {
+    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ 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)
@@ -2004,7 +2000,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
@@ -2030,7 +2026,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
@@ -2061,44 +2057,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, &crack_bbox, small_crack_threshold](const Surface& s) {
+                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, small_crack_threshold](const Surface& s) {
                                                 const auto& se = s.expolygon;
-                                                return get_extents(se).inflated(SCALED_EPSILON).contains(crack_bbox)
-                                                    && diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
+                                                return 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, grown_crack), b.surface_type);
-                                            else
-                                                bot_tmp.emplace_back(std::move(b));
+                                            surfaces_append(bot_tmp, diff_ex(b.expolygon, offset_ex(crack, -small_crack_threshold)), b.surface_type);
                                         }
                                         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);
                         }
                     }
 
@@ -2189,7 +2175,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));
@@ -2366,31 +2352,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(
@@ -2407,7 +2391,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;
@@ -2474,10 +2458,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";
-    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
-    // others, so the regions run next to each other instead of one after another, each still over all layers.
-    tbb::parallel_for(size_t(0), this->num_printing_regions(), [this, &surfaces_covered](size_t region_id) {
+	for (size_t region_id = 0; region_id < this->num_printing_regions(); ++region_id) {
+        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - start";
         tbb::parallel_for(
             tbb::blocked_range<size_t>(0, m_layers.size()),
             [this, &surfaces_covered, region_id](const tbb::blocked_range<size_t>& range) {
@@ -2492,9 +2474,9 @@ void PrintObject::process_external_surfaces()
                 }
             }
         );
-    });
-    m_print->throw_if_canceled();
-    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - end";
+        m_print->throw_if_canceled();
+        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - end";
+    }
 }
 
 void PrintObject::discover_vertical_shells()
@@ -2533,10 +2515,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
-        // few such layers next to each other must not end up in one task.
+        //FIXME Improve the heuristics for a grain size.
+        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();
@@ -2544,198 +2526,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) {
-                        return float(layer.m_regions[region_id]->flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
-                    };
+                    // Simulate single set of perimeters over all merged regions.
+                    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.
-                    tbb::parallel_invoke(
-                        [&]() {
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
-                                append(cache.top_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_type(stTop), top_bottom_expansion(region_id)));
-//                              append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
-                            // Save some computing time by reducing the number of polygons.
-                            cache.top_surfaces = union_(cache.top_surfaces);
-                        },
-                        [&]() {
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
-                                append(cache.bottom_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_types(surfaces_bottom), top_bottom_expansion(region_id)));
-//                              append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
-                            cache.bottom_surfaces = union_(cache.bottom_surfaces);
-                        },
-                        [&]() {
-                            // Simulate single set of perimeters over all merged regions.
-                            float perimeter_offset      = 0.f;
-                            float perimeter_min_spacing = FLT_MAX;
-                            for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
-                                const LayerRegion &layerm = *layer.m_regions[region_id];
-                                // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
-                                // First find the maxium number of perimeters per region slice.
-                                unsigned int perimeters = 0;
-                                for (const Surface &s : layerm.slices.surfaces)
-                                    perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
-                                perimeters += layerm.region().config().wall_loops.value;
-                                // Then calculate the infill offset.
-                                if (perimeters > 0) {
-                                    Flow extflow = layerm.flow(frExternalPerimeter);
-                                    Flow flow    = layerm.flow(frPerimeter);
-                                    perimeter_offset = std::max(perimeter_offset,
-                                        0.5f * float(extflow.scaled_width() + extflow.scaled_spacing()) + (float(perimeters) - 1.f) * flow.scaled_spacing());
-                                    perimeter_min_spacing = std::min(perimeter_min_spacing, float(std::min(extflow.scaled_spacing(), flow.scaled_spacing())));
-                                }
-                                polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
-                            }
-                            // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
-                            if (perimeter_offset > 0.) {
-                                // The layer.lslices are forced to merge by expanding them first.
-                                polygons_append(cache.holes, offset2(layer.lslices, 0.3f * perimeter_min_spacing, - perimeter_offset - 0.3f * perimeter_min_spacing));
+                    for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
+                        LayerRegion &layerm               = *layer.m_regions[region_id];
+                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
+                        // Top surfaces.
+                        append(cache.top_surfaces, offset(layerm.slices.filter_by_type(stTop), top_bottom_expansion));
+//                        append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
+                        // Bottom surfaces.
+                        append(cache.bottom_surfaces, offset(layerm.slices.filter_by_types(surfaces_bottom), top_bottom_expansion));
+//                        append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                        // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
+                        // First find the maxium number of perimeters per region slice.
+                        unsigned int perimeters = 0;
+                        for (Surface &s : layerm.slices.surfaces)
+                            perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
+                        perimeters += layerm.region().config().wall_loops.value;
+                        // Then calculate the infill offset.
+                        if (perimeters > 0) {
+                            Flow extflow = layerm.flow(frExternalPerimeter);
+                            Flow flow    = layerm.flow(frPerimeter);
+                            perimeter_offset = std::max(perimeter_offset,
+                                0.5f * float(extflow.scaled_width() + extflow.scaled_spacing()) + (float(perimeters) - 1.f) * flow.scaled_spacing());
+                            perimeter_min_spacing = std::min(perimeter_min_spacing, float(std::min(extflow.scaled_spacing(), flow.scaled_spacing())));
+                        }
+                        polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
+                    }
+                    // Save some computing time by reducing the number of polygons.
+                    cache.top_surfaces    = union_(cache.top_surfaces);
+                    cache.bottom_surfaces = union_(cache.bottom_surfaces);
+                    // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
+                    if (perimeter_offset > 0.) {
+                        // The layer.lslices are forced to merge by expanding them first.
+                        polygons_append(cache.holes, offset2(layer.lslices, 0.3f * perimeter_min_spacing, - perimeter_offset - 0.3f * perimeter_min_spacing));
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
-                                {
-                                    Slic3r::SVG svg(debug_out_path("discover_vertical_shells-extra-holes-%d.svg", debug_idx), get_extents(layer.lslices));
-                                    svg.draw(layer.lslices, "blue");
-                                    svg.draw(union_ex(cache.holes), "red");
-                                    svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
-                                    svg.Close();
-                                }
+                        {
+                            Slic3r::SVG svg(debug_out_path("discover_vertical_shells-extra-holes-%d.svg", debug_idx), get_extents(layer.lslices));
+                            svg.draw(layer.lslices, "blue");
+                            svg.draw(union_ex(cache.holes), "red");
+                            svg.draw_outline(union_ex(cache.holes), "black", "blue", scale_(0.05));
+                            svg.Close();
+                        }
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                            }
-                            cache.holes = union_(cache.holes);
-                        });
+                    }
+                    cache.holes = union_(cache.holes);
                 }
             });
         m_print->throw_if_canceled();
         BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells in parallel - end : cache top / bottom";
     }
 
-    // With one top/bottom cache for all regions, the shell and hole accumulation in the loop below depends on nothing
-    // region-specific but the shell settings and the external perimeter spacing, so a region sharing them with an earlier
-    // one reuses its result instead of repeating it: that accumulation is a union over several layers of top/bottom
-    // surfaces, and a multi-material print has a region per filament.
-    using AccumulationKey = std::array<double, 5>;
-    struct ShellAccumulation
-    {
-        AccumulationKey key;
-        Polygons        shell;
-        Polygons        holes;
-    };
-    const auto accumulation_key = [](const PrintRegionConfig &region_config, const LayerRegion *layerm) {
-        return AccumulationKey{ double(region_config.top_shell_layers.value), region_config.top_shell_thickness.value,
-                                double(region_config.bottom_shell_layers.value), region_config.bottom_shell_thickness.value,
-                                double(layerm->flow(frExternalPerimeter).scaled_spacing()) };
-    };
-    const auto accumulate_shell = [this, &cache_top_botom_regions](size_t idx_layer, const PrintRegionConfig &region_config,
-                                                                   const LayerRegion *layerm, Polygons &shell, Polygons &holes) {
-        const Layer *layer = m_layers[idx_layer];
-    			        polygons_append(holes, cache_top_botom_regions[idx_layer].holes);
-                        auto combine_holes = [&holes](const Polygons &holes2) {
-                            if (holes.empty() || holes2.empty())
-                                holes.clear();
-                            else
-                                holes = intersection(holes, holes2);
-                        };
-                        auto combine_shells = [&shell](const Polygons &shells2) {
-                            if (shell.empty())
-                                shell = std::move(shells2);
-                            else if (! shells2.empty()) {
-                                polygons_append(shell, shells2);
-                                // Running the union_ using the Clipper library piece by piece is cheaper
-                                // than running the union_ all at once.
-                                shell = union_(shell);
-                            }
-                        };
-                        static constexpr const bool one_more_layer_below_top_bottom_surfaces = false;
-    			        if (int n_top_layers = region_config.top_shell_layers.value; n_top_layers > 0) {
-                            // Gather top regions projected to this layer.
-                            coordf_t print_z = layer->print_z;
-                            int i = int(idx_layer) + 1;
-                            int itop = int(idx_layer) + n_top_layers;
-                            bool at_least_one_top_projected = false;
-    	                    for (; i < int(cache_top_botom_regions.size()) &&
-    	                         (i < itop || m_layers[i]->print_z - print_z < region_config.top_shell_thickness - EPSILON);
-    	                        ++ i) {
-                                at_least_one_top_projected = true;
-    	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
-                                combine_holes(cache.holes);
-                                combine_shells(cache.top_surfaces);
-    	                    }
-                            if (!at_least_one_top_projected && i < int(cache_top_botom_regions.size())) {
-                                // Lets consider this a special case - with only 1 top solid and minimal shell thickness settings, the
-                                // boundaries of solid layers are not anchored over/under perimeters, so lets fix it by adding at least one
-                                // perimeter width of area
-                                Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].top_surfaces,
-                                                                           layerm->flow(frExternalPerimeter).scaled_spacing()),
-                                                                    to_polygons(m_layers[i]->lslices));
-                                combine_shells(anchor_area);
-                            }
-
-                            if (one_more_layer_below_top_bottom_surfaces)
-                                if (i < int(cache_top_botom_regions.size()) &&
-                                    (i <= itop || m_layers[i]->bottom_z() - print_z < region_config.top_shell_thickness - EPSILON))
-                                    combine_holes(cache_top_botom_regions[i].holes);
-    	                }
-    	                if (int n_bottom_layers = region_config.bottom_shell_layers.value; n_bottom_layers > 0) {
-                            // Gather bottom regions projected to this layer.
-                            coordf_t bottom_z = layer->bottom_z();
-                            int i = int(idx_layer) - 1;
-                            int ibottom = int(idx_layer) - n_bottom_layers;
-                            bool at_least_one_bottom_projected = false;
-    	                    for (; i >= 0 &&
-    	                         (i > ibottom || bottom_z - m_layers[i]->bottom_z() < region_config.bottom_shell_thickness - EPSILON);
-    	                        -- i) {
-                                    at_least_one_bottom_projected = true;
-    	                        const DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[i];
-    							combine_holes(cache.holes);
-                                combine_shells(cache.bottom_surfaces);
-    	                    }
-
-                            if (!at_least_one_bottom_projected && i >= 0) {
-                                Polygons anchor_area = intersection(expand(cache_top_botom_regions[idx_layer].bottom_surfaces,
-                                                                           layerm->flow(frExternalPerimeter).scaled_spacing()),
-                                                                    to_polygons(m_layers[i]->lslices));
-                                combine_shells(anchor_area);
-                            }
-
-                            if (one_more_layer_below_top_bottom_surfaces)
-                                if (i >= 0 &&
-                                    (i > ibottom || bottom_z - m_layers[i]->print_z < region_config.bottom_shell_thickness - EPSILON))
-                                    combine_holes(cache_top_botom_regions[i].holes);
-    	                }
-    };
-    std::vector<std::vector<ShellAccumulation>> shell_accumulations(top_bottom_surfaces_all_regions ? num_layers : 0);
-    if (! shell_accumulations.empty()) {
-        // Every (layer, key) pair is accumulated once, before the regions, so that nothing in the loop below is shared
-        // between them and they can run next to each other.
-        std::vector<std::array<size_t, 3>> todo; // layer, its slot, a region holding the key
-        for (size_t idx_layer = 0; idx_layer < num_layers; ++ idx_layer) {
-            std::vector<ShellAccumulation> &accumulations = shell_accumulations[idx_layer];
-            for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
-                if (this->printing_region(region_id).config().ensure_vertical_shell_thickness.value != evstAll)
-                    continue;
-                const LayerRegion    *layerm = m_layers[idx_layer]->m_regions[region_id];
-                const AccumulationKey key    = accumulation_key(layerm->region().config(), layerm);
-                if (std::none_of(accumulations.begin(), accumulations.end(), [&key](const ShellAccumulation &a) { return a.key == key; })) {
-                    todo.push_back({ idx_layer, accumulations.size(), region_id });
-                    accumulations.push_back({ key, {}, {} });
-                }
-            }
-        }
-        tbb::parallel_for(size_t(0), todo.size(), [this, &todo, &shell_accumulations, &accumulate_shell](size_t i) {
-            m_print->throw_if_canceled();
-            const LayerRegion *layerm = m_layers[todo[i][0]]->m_regions[todo[i][2]];
-            ShellAccumulation &out    = shell_accumulations[todo[i][0]][todo[i][1]];
-            accumulate_shell(todo[i][0], layerm->region().config(), layerm, out.shell, out.holes);
-        });
-        m_print->throw_if_canceled();
-    }
-
-    const auto process_region = [&](size_t region_id) {
+    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ 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));
@@ -2775,7 +2626,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) {
@@ -2825,19 +2676,80 @@ void PrintObject::discover_vertical_shells()
                         }
                     }
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    const AccumulationKey key = accumulation_key(region_config, layerm);
-                    const ShellAccumulation *reused = shell_accumulations.empty() ? nullptr :
-                        [&]() -> const ShellAccumulation * {
-                            for (const ShellAccumulation &a : shell_accumulations[idx_layer])
-                                if (a.key == key)
-                                    return &a;
-                            return nullptr;
-                        }();
-                    if (reused != nullptr) {
-                        shell = reused->shell;
-                        holes = reused->holes;
-                    } else
-                        accumulate_shell(idx_layer, region_config, layerm, shell, holes);
+			        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);
+	                }
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
         				Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-%d.svg", debug_idx), get_extents(shell));
@@ -2931,8 +2843,11 @@ void PrintObject::discover_vertical_shells()
                         Polygons object_volume;
                         Polygons internal_volume;
                         {
-                            if (idx_layer > 0 && idx_layer + 1 < m_layers.size())
-                                object_volume = to_polygons(intersection_ex_by_piece(m_layers[idx_layer - 1]->lslices, to_polygons(m_layers[idx_layer + 1]->lslices)));
+                            Polygons shrinked_bottom_slice = idx_layer > 0 ? to_polygons(m_layers[idx_layer - 1]->lslices) : Polygons{};
+                            Polygons shrinked_upper_slice  = (idx_layer + 1) < m_layers.size() ?
+                                                                 to_polygons(m_layers[idx_layer + 1]->lslices) :
+                                                                 Polygons{};
+                            object_volume = intersection(shrinked_bottom_slice, shrinked_upper_slice);
                             internal_volume = closing(polygonsInternal, SCALED_EPSILON);
                         }
 
@@ -2943,34 +2858,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) ||
-                                                                                      (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
-                                                                                       diff(to_polygons(p),
-                                                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
-                                                                                                object_volume, get_extents(p).inflated(SCALED_EPSILON)))
-                                                                                           .empty());
-                                                                   if (!small)
-                                                                       return false;
-                                                                   const Polygons    expanded = expand(to_polygons(p), min_perimeter_infill_spacing);
-                                                                   const BoundingBox bbox     = get_extents(expanded);
-                                                                   Polygons          nearby;
-                                                                   for (size_t i = 0; i < internal_volume.size(); ++i)
-                                                                       if (internal_bboxes[i].overlap(bbox))
-                                                                           nearby.emplace_back(internal_volume[i]);
-                                                                   return diff(nearby, expanded).size() >= nearby.size();
+                                                                   return (p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
+                                                                           (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
+                                                                            diff(to_polygons(p), object_volume).empty())) &&
+                                                                          diff(internal_volume,
+                                                                               expand(to_polygons(p), min_perimeter_infill_spacing))
+                                                                                  .size() >= internal_volume.size();
                                                                }),
                                                 regularized_shell.end());
                     }
@@ -2992,9 +2888,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_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternal)), regularized_shell_polygons);
-                    Slic3r::ExPolygons new_internal_void = diff_ex_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternalVoid)), regularized_shell_polygons);
+                    Slic3r::ExPolygons new_internal = diff_ex(layerm->fill_surfaces.filter_by_type(stInternal), regularized_shell);
+                    Slic3r::ExPolygons new_internal_void = diff_ex(layerm->fill_surfaces.filter_by_type(stInternalVoid), regularized_shell);
 
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
@@ -3021,15 +2916,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
-    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);
+    } // for each region
 } // void PrintObject::discover_vertical_shells()
 
 // #define DEBUG_BRIDGE_OVER_INFILL
@@ -3549,16 +3436,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)};
 
@@ -3803,58 +3680,26 @@ 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 cutting a bridge out of it only changes the
-                // polygons near that bridge. The rest are passed through untouched instead of being fed to Clipper
-                // with the whole layer again for every candidate.
-                // Not `near`/`far`: the Windows headers still define those as macros, and they expand to
-                // nothing, which turns the declaration below into an empty one.
-                const auto split_near = [](const Polygons &polys, const BoundingBox &bbox, Polygons &rest) {
-                    Polygons nearby;
-                    for (const Polygon &p : polys)
-                        (get_extents(p).overlap(bbox) ? nearby : rest).emplace_back(p);
-                    return nearby;
-                };
                 for (const CandidateSurface &candidate : surfaces_by_layer[lidx]) {
                     const auto &region_config = candidate.region->region().config();
                     const bool turning_pattern = region_config.sparse_infill_pattern == ipHilbertCurve ||
                                                  region_config.sparse_infill_pattern == ipOctagramSpiral;
                     const Flow &flow              = candidate.region->bridging_flow(frSolidInfill, true);
-                    const Polygons expanded_polys = expand(candidate.new_polys, flow.scaled_spacing());
-                    // deep_infill_area and internal_unsupported_area cover the whole layer; only their part under
-                    // this candidate can change the results, so they are clipped to its box first.
-                    ExPolygons bridge_components;
-                    if (!expanded_polys.empty())
-                        bridge_components = intersection_ex(expanded_polys,
-                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
-                                                                deep_infill_area, get_extents(expanded_polys).inflated(SCALED_EPSILON)));
+                    ExPolygons bridge_components = intersection_ex(expand(candidate.new_polys, flow.scaled_spacing()), deep_infill_area);
                     // Orca: Filter whole bridge areas so their holes remain holes.
                     bridge_components.erase(std::remove_if(bridge_components.begin(), bridge_components.end(),
                                                            [&internal_unsupported_area](const ExPolygon &component) {
-                                                               return intersection_ex(component, ClipperUtils::clip_clipper_polygons_with_subject_bbox(
-                                                                                                     internal_unsupported_area,
-                                                                                                     get_extents(component).inflated(SCALED_EPSILON)))
-                                                                   .empty();
+                                                               return intersection_ex(component, internal_unsupported_area).empty();
                                                            }),
                                             bridge_components.end());
                     Polygons area_to_be_bridge = to_polygons(std::move(bridge_components));
 
+                    Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
+
                     if (area_to_be_bridge.empty())
                         continue;
 
-                    // Not split like the cut of expansion_area below: the whole limiting area is grown by 30% of the spacing,
-                    // which merges neighbouring polygons, and any of its boundary can anchor the bridge.
-                    Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
-
-                    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.3f * flow.scaled_spacing())))
-                                          .first;
-                    Polylines boundary_plines = boundary_it->second;
+                    Polylines boundary_plines = to_polylines(expand(total_fill_area, 1.3f * flow.scaled_spacing()));
                     {
                         Polylines limiting_plines = to_polylines(expand(limiting_area, 0.3f * flow.scaled_spacing()));
                         boundary_plines.insert(boundary_plines.end(), limiting_plines.begin(), limiting_plines.end());
@@ -3930,12 +3775,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());
-                        const BoundingBox tmp_expanded_bbox = get_extents(tmp_expanded_area);
+                        Polygons tmp_expanded_area = expand(bridging_area, 3.0f * flow.scaled_spacing());
                         for (const CandidateSurface &s : expanded_surfaces) {
-                            // Surfaces whose boxes miss each other cannot intersect, which is most pairs on a busy layer.
-                            if (get_extents(s.new_polys).overlap(tmp_expanded_bbox) &&
-                                !intersection(s.new_polys, tmp_expanded_area).empty()) {
+                            if (!intersection(s.new_polys, tmp_expanded_area).empty()) {
                                 bridging_angle = s.bridge_angle;
                                 reconstruct    = true;
                                 break;
@@ -3959,20 +3801,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
-                    // bridge's box (and expansion_area split as above); the result is the same.
-                    if (!bridging_area.empty()) {
-                        const BoundingBox bridging_bbox = get_extents(bridging_area).inflated(SCALED_EPSILON);
-                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(limiting_area, bridging_bbox));
-                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_fill_area, bridging_bbox));
-                        bridging_area = diff(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_top_area, bridging_bbox));
-                    }
-                    if (!bridging_area.empty()) {
-                        Polygons       kept;
-                        const Polygons cut = split_near(expansion_area, get_extents(bridging_area).inflated(SCALED_EPSILON), kept);
-                        append(kept, diff(cut, bridging_area));
-                        expansion_area = std::move(kept);
-                    }
+                    bridging_area          = intersection(bridging_area, limiting_area);
+                    bridging_area          = intersection(bridging_area, total_fill_area);
+                    bridging_area          = diff(bridging_area, total_top_area);
+                    expansion_area         = diff(expansion_area, bridging_area);
 
 #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

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

@@ -996,46 +996,16 @@ void TreeSupport::detect_overhangs(bool check_support_necessity/* = false*/)
                 if (is_auto(stype) && config_detect_sharp_tails)
                 {
                     // BBS detect sharp tail
-                    // On a belt, "below" has to include the belt itself and the
-                    // shear-advanced lower layer, or every belt-contact island reads as
-                    // a sharp tail -- which is what the empty-predecessor skip above was
-                    // really masking. effective_lower is exactly that notion of below.
-                    const ExPolygons &tail_lower = belt_ovh_active ? effective_lower : lower_polys;
-                    // Each island is tested only against the lower islands whose box meets its own; overlaps() tries
-                    // every pair, which is quadratic in the island counts of the two layers.
-                    std::vector<BoundingBox> lower_bboxes;
-                    lower_bboxes.reserve(tail_lower.size());
-                    for (const ExPolygon &lower : tail_lower)
-                        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);
-                        const BoundingBox bbox     = get_extents(expanded);
-                        ExPolygons        lower_nearby;
-                        for (size_t i = 0; i < tail_lower.size(); ++i)
-                            if (lower_bboxes[i].overlap(bbox))
-                                lower_nearby.emplace_back(tail_lower[i]);
-                        // As overlaps(expanded, lower_nearby), with each lower island cut to the island's box first:
-                        // below a fine relief the lower layer is a few islands with thousands of holes, and the whole
-                        // of that boundary would otherwise be intersected once per island above.
-                        const auto overlaps_nearby = [&]() {
-                            for (const ExPolygon &a : expanded) {
-                                if (a.empty())
-                                    continue;
-                                const BoundingBox a_bbox = get_extents(a);
-                                for (const ExPolygon &b : lower_nearby) {
-                                    if (b.empty() || !get_extents(b).overlap(a_bbox))
-                                        continue;
-                                    const Polygons b_near = ClipperUtils::clip_clipper_polygons_with_subject_bbox(b, a_bbox.inflated(SCALED_EPSILON));
-                                    if (!intersection_pl(to_polylines(b_near), a).empty() || b.contains(a.contour.points.front()))
-                                        return true;
-                                }
-                            }
-                            return false;
-                        };
-                        if (!overlaps_nearby()) {
+                        // this is a sharp tail region if it's floating and non-ignorable.
+                        // On a belt, "below" has to include the belt itself and the
+                        // shear-advanced lower layer, or every belt-contact island reads as
+                        // a sharp tail -- which is what the empty-predecessor skip above was
+                        // really masking. effective_lower is exactly that notion of below.
+                        const ExPolygons &tail_lower = belt_ovh_active ? effective_lower : lower_polys;
+                        if (!overlaps(offset_ex(expoly, 0.1 * extrusion_width_scaled), tail_lower)) {
                             is_sharp_tail = !offset_ex(expoly, -0.1 * extrusion_width_scaled).empty();
                         }
 

src/libslic3r/Surface.hpp

@@ -68,7 +68,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)
@@ -94,7 +94,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/TextureDisplacement.cpp

@@ -247,6 +247,20 @@ void smooth_height_pixels(std::vector<uint8_t> &pixels, int width, int height, f
 }
 } // namespace
 
+bool height_texture_has_color(const TextureDisplacementLayer &layer)
+{
+    if (layer.empty())
+        return false;
+    {
+        std::lock_guard<std::mutex> lock(g_decoded_texture_cache.mutex);
+        const auto it = g_decoded_texture_cache.entries.find(layer.image_data.get());
+        if (it != g_decoded_texture_cache.entries.end() && it->second.first.lock() == layer.image_data)
+            return it->second.second.has_color();
+    }
+    // Not decoded yet. Decoding caches the raw image, so this happens once per image.
+    return decode_height_texture(layer).has_color();
+}
+
 DecodedHeightTexture decode_height_texture(const TextureDisplacementLayer &layer)
 {
     DecodedHeightTexture result;

src/libslic3r/TextureDisplacement.hpp

@@ -1,6 +1,7 @@
 #ifndef slic3r_TextureDisplacement_hpp_
 #define slic3r_TextureDisplacement_hpp_
 
+#include <cmath>
 #include <cstddef>
 #include <Eigen/Core>
 #include <cstdint>
@@ -387,6 +388,10 @@ struct TextureDisplacementOptions
     // image (TextureDetail::flat_colors): a texture of flat colours prints in single filaments, a
     // photograph or gradient in mixes. Off forces single filaments everywhere.
     bool         color_mix_enabled = true;
+    // The most mixes the palette may offer. Every mix a bake paints with becomes a mixed filament slot,
+    // so this is also the most slots one bake can add. The mixes themselves are picked from the
+    // texture's colours, those that improve the match the most coming first.
+    int          color_mix_count   = 8;
     // Majority-filter passes over the assigned colours. See TextureColorRequest::despeckle_passes -
     // this is the control for it, and 2 is enough to clear the salt-and-pepper an image with detail
     // finer than the mesh leaves behind, without eating features that are genuinely a facet wide.
@@ -396,7 +401,7 @@ struct TextureDisplacementOptions
     {
         ar(displace_border, smooth_enabled, smooth_strength, smooth_iterations, smooth_skip_border,
            pipeline_v2, v2_refine_mm, v2_regularize, v2_max_triangles_k,
-           v2_relocate, color_mix_enabled, color_despeckle);
+           v2_relocate, color_mix_enabled, color_despeckle, color_mix_count);
     }
 };
 
@@ -480,6 +485,10 @@ struct DecodedHeightTexture
 // DecodedHeightTexture if image_data is empty or is not a PNG at all.
 DecodedHeightTexture decode_height_texture(const TextureDisplacementLayer &layer);
 
+// decode_height_texture(layer).has_color(), answered from the decode cache rather than from a copy of the
+// texture - cheap enough to ask every frame. Smoothing does not change it, so the raw decode is what is read.
+bool height_texture_has_color(const TextureDisplacementLayer &layer);
+
 // Maps a linear RGB colour in [0, 1] to an index into the caller's palette, or -1 for "no colour".
 //
 // Deliberately a callback rather than a function here: matching a colour to a filament is a
@@ -494,12 +503,14 @@ using ColorQuantizeFn = std::function<int(const Vec3f &)>;
 // interleaving, which the slicer does per print layer. Plain data, so it can be captured into a job.
 struct PrintableColor
 {
-    Vec3f rgb   = Vec3f::Zero(); // what it looks like; for a mix, the perceptual average of the two
+    Vec3f rgb   = Vec3f::Zero(); // what it looks like; for a mix, the colour its mixed filament slot shows
     int   a     = 0;             // filament index
     int   b     = 0;             // the second filament; == a for a pure entry
     int   num   = 1;             // a's share of the interleave, out of `den`
     int   den   = 1;
     bool  is_mix() const { return a != b; }
+    // a's share in percent, the form a mixed filament slot is created from.
+    int   a_percent() const { return int(std::lround(100.0 * double(num) / double(den))); }
 };
 
 // Everything needed to colour a mesh, captured on the main thread and handed to a job. An empty
@@ -762,9 +773,10 @@ struct TextureColorRequest
     float           min_color_region_mm2 = 0.5f;
     // Filled per *base mesh* triangle (the bake is topology-preserving, so this indexes the returned
     // mesh too): the quantize callback's index plus one, or 0 for "this triangle takes no colour from
-    // the texture". The +1 is not arbitrary - it lines up with EnforcerBlockerType, where 0 is NONE
-    // ("use the volume's own filament") and 1..16 are Extruder1..16, so the caller can hand these
-    // straight to a TriangleSelector without a second mapping table.
+    // the texture". The +1 lines up with EnforcerBlockerType, where 0 is NONE ("use the volume's own
+    // filament"): where every palette entry is a filament, these go straight to a TriangleSelector. A
+    // palette with mixes maps each index to the mix's filament slot first (see
+    // GLGizmoTextureDisplacement::palette_filaments()).
     std::vector<uint8_t> *out_triangle = nullptr;
 };
 

src/libslic3r/libslic3r.h

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

src/slic3r/GUI/Gizmos/GLGizmoPainterBase.cpp

@@ -113,7 +113,7 @@ Vec3f GLGizmoPainterBase::get_tilt_up_direction() const
     return build_plate_tilt_up_direction().cast<float>();
 }
 
-void GLGizmoPainterBase::render_triangles(const Selection& selection) const
+void GLGizmoPainterBase::render_triangles(const Selection& selection, const ModelVolume* skip) const
 {
     auto* shader = wxGetApp().get_shader("mm_gouraud");
     if (!shader)
@@ -135,6 +135,8 @@ void GLGizmoPainterBase::render_triangles(const Selection& selection) const
             continue;
 
         ++mesh_id;
+        if (mv == skip)
+            continue;
 
         Transform3d trafo_matrix;
         if (m_parent.get_canvas_type() == GLCanvas3D::CanvasAssembleView) {

src/slic3r/GUI/Gizmos/GLGizmoPainterBase.hpp

@@ -48,6 +48,9 @@ public:
     virtual ~TriangleSelectorGUI() = default;
 
     virtual void render(ImGuiWrapper* imgui, const Transform3d& matrix);
+    // The seed-fill contour alone, as render() last built it - for a gizmo that draws over the selector
+    // and has to put the contour back on top.
+    void         render_paint_contour(const Transform3d& matrix);
     //void         render(const Transform3d& matrix) { this->render(nullptr, matrix); }
     void         set_wireframe_needed(bool need_wireframe) { m_need_wireframe = need_wireframe; }
     bool         get_wireframe_needed() { return m_need_wireframe; }
@@ -90,7 +93,6 @@ protected:
     GLModel                      m_paint_contour;
 
     void update_paint_contour();
-    void render_paint_contour(const Transform3d& matrix);
 
     bool                                m_need_wireframe {false};
 };
@@ -231,7 +233,8 @@ public:
     bool on_mouse(const wxMouseEvent &mouse_event) override;
 
 protected:
-    virtual void render_triangles(const Selection& selection) const;
+    // Draws every model part's selector, except `skip`'s when given.
+    virtual void render_triangles(const Selection& selection, const ModelVolume* skip = nullptr) const;
     void render_cursor();
     void render_cursor_circle();
     void render_cursor_sphere(const Transform3d& trafo) const;
@@ -328,6 +331,9 @@ protected:
 
     TriangleSelector::ClippingPlane get_clipping_plane_in_volume_coordinates(const Transform3d &trafo) const;
 
+    // True while a paint or erase stroke is under way.
+    bool is_painting() const { return m_button_down != Button::None; }
+
 private:
     std::vector<std::vector<ProjectedMousePosition>> get_projected_mouse_positions(const Vec2d &mouse_position, double resolution, const std::vector<Transform3d> &trafo_matrices) const;
 

src/slic3r/GUI/Gizmos/GLGizmoTextureDisplacement.cpp

@@ -8,6 +8,7 @@
 #include "ColorSpaceConvert.hpp"
 #include "libslic3r/AABBTreeIndirect.hpp"
 #include "libslic3r/Color.hpp"
+#include "libslic3r/FilamentMixer.hpp"
 #include "libslic3r/PresetBundle.hpp"
 #include "libslic3r/MeshBoolean.hpp"
 #include "libslic3r/Model.hpp"
@@ -69,6 +70,7 @@
 #include <array>
 #include <cmath>
 #include <limits>
+#include <numeric>
 #include <queue>
 #include <set>
 #include <vector>
@@ -257,11 +259,54 @@ TriangleSelector::TriangleSplittingData remap_texture_paint_spatial(
 // entry to fill.
 constexpr int PALETTE_LUT_EDGE = 24;
 
-// Ceiling on the printable palette, which bounds that fill cost (and the shader's uniform array).
+// The shaded preview shader's palette arrays. The palette itself stays within the paint mask's
+// EnforcerBlockerType::ExtruderMax states, since every entry has to become a filament.
 constexpr int PALETTE_MAX_ENTRIES = 64;
-// Ceiling on the filaments the palette's entries can refer to (the shaded preview shader's filament_rgb[]);
-// mmu segmentation stops at Extruder16 anyway.
-constexpr int PALETTE_MAX_FILAMENTS = 16;
+
+// A mix is an interleave that only reads as its colour from a distance; up close it is stripes. So it
+// is spent only where it beats the nearest single filament by this much (CIEDE2000). Two is about
+// where a side-by-side difference stops being arguable; a margin of ten already turns most of a
+// greyscale ramp - the shape a height texture actually traces - back into single filaments. The
+// quantizer, the mix ranking and the shaded preview shader all apply it, so they agree on where a mix
+// is used.
+constexpr float PREFER_PURE_DE = 2.f;
+
+// mix_targets(): the most pixels read per layer, and the histogram bins kept over all layers. Together
+// they bound rank_mixes() to candidates x MIX_TARGET_BINS colour differences, the same order as filling
+// the quantizer's lookup cube.
+constexpr size_t MIX_TARGET_SAMPLES = size_t(1) << 20;
+constexpr size_t MIX_TARGET_BINS    = 256;
+// rank_mixes() stops once the best remaining mix would improve the match by less than this, in
+// CIEDE2000 averaged over every pixel of the colouring layers (see mix_targets()): a mix that only
+// touches a few stray pixels is not worth a filament slot.
+constexpr float MIN_MIX_GAIN = 0.05f;
+
+// The project's mixed filament slots, one string each, as the palette cache compares them: anything
+// that changes which of them a mix can reuse changes this.
+std::vector<std::string> mixed_slot_signature(const DynamicPrintConfig &project_config)
+{
+    std::vector<std::string> out;
+    const auto *is_mixed = project_config.option<ConfigOptionBools>("filament_is_mixed");
+    const auto *comps    = project_config.option<ConfigOptionStrings>("filament_mixed_components");
+    const auto *ratios   = project_config.option<ConfigOptionStrings>("filament_mixed_sublayer_ratios");
+    const auto *gradient = project_config.option<ConfigOptionBools>("filament_mixed_gradient");
+    if (is_mixed == nullptr || comps == nullptr || ratios == nullptr)
+        return out;
+    for (size_t i = 0; i < is_mixed->values.size(); ++i)
+        if (is_mixed->values[i])
+            out.push_back(std::to_string(i) + ':' + (i < comps->values.size() ? comps->values[i] : std::string()) + '|' +
+                          (i < ratios->values.size() ? ratios->values[i] : std::string()) + '|' +
+                          (gradient != nullptr && i < gradient->values.size() && gradient->values[i] ? "g" : ""));
+    return out;
+}
+
+// Whether two palettes would draw and print the same.
+bool same_palette(const std::vector<PrintableColor> &l, const std::vector<PrintableColor> &r)
+{
+    return std::equal(l.begin(), l.end(), r.begin(), r.end(), [](const PrintableColor &x, const PrintableColor &y) {
+        return x.a == y.a && x.b == y.b && x.num == y.num && x.den == y.den && x.rgb == y.rgb;
+    });
+}
 
 // sRGB (0..1) <-> CIELAB, D65. Exactly what the preview shader's srgb_to_lab() computes, so the CPU
 // quantizer, the mixed-palette entries and the per-fragment preview all match in the same space.
@@ -458,6 +503,11 @@ std::string GLGizmoTextureDisplacement::on_get_name() const
     return _u8L("Texture displacement");
 }
 
+bool GLGizmoTextureDisplacement::on_is_activable() const
+{
+    return m_parent.get_canvas_type() != GLCanvas3D::CanvasAssembleView && GLGizmoPainterBase::on_is_activable();
+}
+
 void GLGizmoTextureDisplacement::on_shutdown()
 {
     m_parent.toggle_model_objects_visibility(true);
@@ -465,10 +515,25 @@ void GLGizmoTextureDisplacement::on_shutdown()
     m_shaded_preview_glmodel.reset();
     m_paint_overlay_glmodel.reset();
     m_paint_overlay_dirty = false;
+    m_painted_colors = PaintedColors{};
+    m_painted_colors_key.clear();
+    m_painted_colors_glmodel.reset();
+    m_painted_colors_drawn_key.clear();
+    m_painted_colors_runs.clear();
+    m_seed_fill_last_mesh_id = -1; // a hover from this session must not count in the next
     // Any preview still in flight is superseded: raising the shared counter makes it abort at its next
     // progress poll, and its completion handler then finds nothing to do.
     m_preview_generation->fetch_add(1);
     m_preview_job_pending = false;
+    // The palette caches hold the last volume's images; a closed gizmo should not keep them alive.
+    m_palette_cache.clear();
+    m_palette_quantizer      = nullptr;
+    m_palette_pure_quantizer = nullptr;
+    m_palette_filaments.clear();
+    m_palette_images.clear();
+    m_mix_ranking.reset();
+    m_palette_slots.clear();
+    m_palette_changed = false;
     m_uvcheck_glmodel.reset();
     m_wireframe_overlay_glmodel.reset();
     m_wireframe_overlay_vcount = 0;
@@ -538,11 +603,15 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
     // The shaded preview is different: it never actually moves geometry (it only shades), so
     // its depth is identical to the overlay's *everywhere*, not just in the unpainted area - the
     // depth-biased opaque overlay would win the depth test across the whole surface and hide the relief
-    // shading entirely. So render_triangles() is skipped for it. What is *not* skipped is
+    // shading entirely. So render_triangles() leaves the textured volume out there. What is *not* skipped is
     // render_paint_overlay(): leaving the shading as the only paint feedback meant a stroke that
     // erased paint, or added it with no texture picked, changed nothing on screen until the whole
     // preview rebuilt at stroke end - and in the true-displacement view the opaque overlay is hidden
     // by the raised surface for the same reason. The translucent tint covers both cases.
+    //
+    // A colour preview is the exception to both: the opaque overlay buries its colours under a flat plane
+    // wherever the relief does not rise, and the tint washes them green. Both are what the user steers by
+    // while painting, though, so they give way only between strokes.
     // Coalesced shaded-preview rebuild from an in-progress UV island drag (see on_island_edited): done here, at
     // most once per drawn frame, rather than synchronously in the UV canvas's mouse-move handler.
     if (m_use_shaded_preview && m_shaded_preview_dirty) {
@@ -579,24 +648,39 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
     // Hide the real volume only when something is actually going to be drawn in its place; otherwise
     // put it back. Getting this wrong leaves an invisible model, so it is decided once, here, rather
     // than per branch below.
+    ModelVolume *mv = texture_volume();
     m_parent.toggle_model_objects_visibility(true);
-    if (use_shaded || use_true_preview) {
-        if (ModelVolume *mv = texture_volume())
-            m_parent.toggle_model_objects_visibility(false, m_c->selection_info()->model_object(),
-                                                      m_c->selection_info()->get_active_instance(), mv);
-    }
+    if ((use_shaded || use_true_preview) && mv != nullptr)
+        m_parent.toggle_model_objects_visibility(false, m_c->selection_info()->model_object(),
+                                                  m_c->selection_info()->get_active_instance(), mv);
 
+    // Which colour preview is on screen decides what the highlight gives way to: the Normal mesh colours
+    // from every layer, the shaded one from the active layer only. Only a stroke brings it back - a fill
+    // tool's hover does not, so the colours stay on screen until the click. The debug view shows a captured
+    // stage, not a colour preview, so it keeps its highlight.
+    const TextureDisplacementLayer *al         = active_layer();
+    const bool                      color_view = !is_painting() && m_debug_stage < 0;
+    const bool stack_colors  = color_view && mv != nullptr && any_layer_colors(*mv);
+    const bool active_colors = color_view && al != nullptr && layer_shows_color(*al);
+
+    // Whether the textured volume's selector - and with it a fill tool's contour - is drawn this frame.
+    bool textured_selector_drawn = true;
     if (use_shaded) {
         render_shaded_preview_mesh();
+        // The shaded mesh is the textured volume alone, so the other model parts are still the selectors' to draw.
+        render_triangles(selection, mv);
+        textured_selector_drawn = false;
     } else if (use_true_preview) {
         render_preview_mesh();
 
         if (show_paint_overlay) {
             glsafe(::glEnable(GL_POLYGON_OFFSET_FILL));
             glsafe(::glPolygonOffset(-1.0f, -1.0f));
-            render_triangles(selection);
+            // Over a colour preview only the other model parts: render_preview_mesh() draws the textured one.
+            render_triangles(selection, stack_colors ? mv : nullptr);
             glsafe(::glDisable(GL_POLYGON_OFFSET_FILL));
         }
+        textured_selector_drawn = show_paint_overlay && !stack_colors;
     } else {
         // render_triangles() *is* the model in a painter gizmo (it draws every model-part volume with the
         // selector's colours), not an overlay on top of one - so it still has to run under a UV-check
@@ -607,6 +691,10 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
         render_triangles(selection);
     }
 
+    // The model's colour paint, over whichever surface was drawn, left out where that surface's preview shows
+    // paint of its own: every layer's for the Normal mesh, the active layer's otherwise.
+    const bool painted_colors_drawn = show_paint_overlay && m_debug_stage < 0 && render_painted_colors(use_true_preview);
+
     // Every other layer's paint, in muted grey, so all layers stay visible while one of them is edited. Drawn
     // before the active layer's tint so that one reads on top where the two overlap.
     if (show_paint_overlay)
@@ -615,15 +703,36 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
     // The translucent paint tint. Needed in the shaded view because the opaque highlight above is
     // skipped there, and in the true-displacement view because the displaced surface rises *above*
     // the undisplaced overlay geometry and hides it exactly where the relief is strongest - in both
-    // cases leaving an erase stroke with no visible effect until the next full preview rebuild.
-    if (show_paint_overlay && (use_shaded || use_true_preview))
+    // cases leaving an erase stroke with no visible effect until the next full preview rebuild. With no
+    // preview, the highlight is the selectors' own, except during a stroke over the colour paint: the paint
+    // there is not flushed yet, so the colours are still drawn over the stroke's highlight.
+    const bool preview_drawn = use_shaded || use_true_preview;
+    if (show_paint_overlay && (preview_drawn ? !active_colors : painted_colors_drawn && is_painting()))
         render_paint_overlay(m_paint_overlay_glmodel);
 
+    // A fill tool's contour is drawn with the selectors, under the colour paint drawn since - which covers it
+    // on a steep face, where the paint's slope-scaled offset outruns the contour's fixed one. Put it back on top,
+    // at the depth its first draw stored, hence LEQUAL. Only where the selector was drawn this frame: drawing it
+    // is what rebuilds the contour. The tool test matters because the base keeps the last hovered mesh when the
+    // tool changes.
+    const bool fill_tool = m_tool_type == ToolType::SMART_FILL || m_tool_type == ToolType::BUCKET_FILL ||
+                           (m_tool_type == ToolType::BRUSH && m_cursor_type == TriangleSelector::CursorType::POINTER);
+    const int  textured_mesh_id = texture_volume_raycaster_index();
+    if (painted_colors_drawn && textured_selector_drawn && fill_tool && textured_mesh_id >= 0 &&
+        textured_mesh_id == m_seed_fill_last_mesh_id && size_t(textured_mesh_id) < m_triangle_selectors.size()) {
+        const ModelObject *mo = m_c->selection_info()->model_object();
+        GLint depth_func = GL_LESS;
+        glsafe(::glGetIntegerv(GL_DEPTH_FUNC, &depth_func));
+        glsafe(::glDepthFunc(GL_LEQUAL));
+        m_triangle_selectors[size_t(textured_mesh_id)]->render_paint_contour(
+            mo->instances[selection.get_instance_idx()]->get_transformation().get_matrix() * mv->get_matrix());
+        glsafe(::glDepthFunc(GLenum(depth_func)));
+    }
+
     // The UV editor's island selection, shown on the model. Polled here rather than pushed: the pane
     // changes its selection in its own mouse handling, and a compare of a few ints per frame is free.
     {
-        const TextureDisplacementLayer *al = active_layer();
-        const UVEditorCanvas           *uv_canvas = wxGetApp().plater()->get_uv_editor_canvas();
+        const UVEditorCanvas *uv_canvas = wxGetApp().plater()->get_uv_editor_canvas();
         if (m_show_uv_editor && al != nullptr && al->projection_method == TextureProjectionMethod::LSCM &&
             uv_canvas != nullptr && !m_uv_editor_unwrap.empty()) {
             if (uv_canvas->selected_islands() != m_island_overlay_selection)
@@ -1495,10 +1604,9 @@ void GLGizmoTextureDisplacement::render_shaded_preview_mesh()
     shader->set_uniform("patch_center", m_shaded_patch_center);
     shader->set_uniform("patch_axis", m_shaded_patch_axis);
 
-    // The filament palette the mesh's per-triangle indices refer to. Count 0 means "no layer is
-    // colouring", and the shader keeps the model's own colour for every fragment.
-    // The printable palette, in RGB for display and in Lab for the match. Uploaded rather than
-    // matched on the CPU because the quantization is per fragment here.
+    // The printable palette, in RGB for display and in Lab for the match. Uploaded rather than matched
+    // on the CPU because the quantization is per fragment here. Count 0 means "no layer is colouring",
+    // and the shader keeps the model's own colour for every fragment.
     const GLTexture *color_tex = get_layer_color_texture(*layer);
     const int        palette_count =
         (color_tex != nullptr) ? int(std::min(m_shaded_preview_palette.size(), size_t(PALETTE_MAX_ENTRIES))) : 0;
@@ -1506,24 +1614,17 @@ void GLGizmoTextureDisplacement::render_shaded_preview_mesh()
     shader->set_uniform("has_color_tex", color_tex != nullptr);
     // A flat-colour image is matched against single filaments only, as the bake does.
     shader->set_uniform("pure_only", color_tex != nullptr && analyze_texture_detail(*layer).flat_colors);
+    shader->set_uniform("prefer_pure_de", PREFER_PURE_DE);
     for (int i = 0; i < palette_count; ++i) {
         const PaletteEntry &e   = m_shaded_preview_palette[size_t(i)];
         const std::string   idx = "[" + std::to_string(i) + "]";
+        // An entry's colour is what it prints as: its filament's, or for a mix its mixed filament slot's.
         shader->set_uniform(("palette_rgb" + idx).c_str(), e.rgb);
         shader->set_uniform(("palette_lab" + idx).c_str(), srgb_to_lab(e.rgb));
-        // How the entry prints: its filament, or for a mix the two it interleaves and in what ratio.
+        // Only so the shader can tell a mix (a != b) from a single filament.
         shader->set_uniform(("palette_a" + idx).c_str(), e.a);
         shader->set_uniform(("palette_b" + idx).c_str(), e.b);
     }
-    // The filaments those indices refer to, and the interleave the shader resolves a mix with - the
-    // the mix's smooth average colour. m_palette_filaments is what m_shaded_preview_palette was built from.
-    const int filament_count =
-        (palette_count > 0) ? int(std::min(m_palette_filaments.size(), size_t(PALETTE_MAX_FILAMENTS))) : 0;
-    shader->set_uniform("filament_count", filament_count);
-    for (int i = 0; i < filament_count; ++i) {
-        const ColorRGBA &c = m_palette_filaments[size_t(i)];
-        shader->set_uniform(("filament_rgb[" + std::to_string(i) + "]").c_str(), Vec3f(c.r(), c.g(), c.b()));
-    }
     if (color_tex != nullptr) {
         shader->set_uniform("color_tex", 1);
         glsafe(::glActiveTexture(GL_TEXTURE1));
@@ -1617,6 +1718,151 @@ void GLGizmoTextureDisplacement::rebuild_other_paint_overlay()
     m_other_paint_glmodel.set_color(ColorRGBA(0.55f, 0.58f, 0.60f, 0.35f));
 }
 
+std::vector<size_t> GLGizmoTextureDisplacement::PaintedColors::outside(const std::vector<bool> &excluded) const
+{
+    std::vector<size_t> out;
+    out.reserve(source.size());
+    for (size_t i = 0; i < source.size(); ++i)
+        if (size_t(source[i]) >= excluded.size() || !excluded[size_t(source[i])])
+            out.push_back(i);
+    return out;
+}
+
+GLGizmoTextureDisplacement::PaintedColors GLGizmoTextureDisplacement::painted_colors(const TriangleMesh &mesh,
+                                                                                     const TriangleSelector::TriangleSplittingData &paint)
+{
+    PaintedColors out;
+    TriangleSelector selector(mesh);
+    selector.deserialize(paint, false);
+    for (const EnforcerBlockerType state : TriangleSelector::extract_used_facet_states(paint)) {
+        if (state == EnforcerBlockerType::NONE)
+            continue;
+        std::vector<int>           source;
+        const indexed_triangle_set part = selector.get_facets_strict(state, &source);
+        // Every state comes back over the same vertex array, only the triangles differ.
+        if (out.facets.vertices.empty())
+            out.facets.vertices = part.vertices;
+        out.facets.indices.insert(out.facets.indices.end(), part.indices.begin(), part.indices.end());
+        out.source.insert(out.source.end(), source.begin(), source.end());
+        out.state.resize(out.facets.indices.size(), int(state));
+    }
+    return out;
+}
+
+void GLGizmoTextureDisplacement::rebuild_painted_colors(bool whole_stack)
+{
+    const ModelVolume *mv    = texture_volume();
+    const bool         shown = mv != nullptr && any_layer_colors(*mv) && !mv->mmu_segmentation_facets.empty();
+
+    // The sub-triangles, keyed on what they were read from: the volume, its mesh and the paint.
+    std::string key;
+    if (shown)
+        key = std::to_string(mv->id().id) + ":" + std::to_string(reinterpret_cast<uintptr_t>(mv->mesh_ptr().get())) + ":" +
+              std::to_string(mv->mmu_segmentation_facets.timestamp());
+    if (key != m_painted_colors_key) {
+        m_painted_colors_key = std::move(key);
+        m_painted_colors     = shown ? painted_colors(mv->mesh(), mv->mmu_segmentation_facets.get_data()) : PaintedColors{};
+        m_painted_colors_drawn_key.clear();
+        m_painted_colors_glmodel.reset();
+        m_painted_colors_runs.clear();
+    }
+    if (m_painted_colors.state.empty())
+        return;
+
+    // The part drawn, keyed on whose paint is left out and on that paint.
+    std::string drawn_key = m_painted_colors_key + (whole_stack ? std::string(":all") : ":" + std::to_string(m_active_layer_slot));
+    for (const TextureDisplacementLayer &l : mv->texture_displacement_layers)
+        if (l.slot >= 0 && l.slot < int(TEXTURE_DISPLACEMENT_MAX_LAYERS))
+            drawn_key += "|" + std::to_string(l.slot) + "@" + std::to_string(mv->texture_displacement_facet(l.slot).timestamp());
+    if (drawn_key == m_painted_colors_drawn_key)
+        return;
+    m_painted_colors_drawn_key = std::move(drawn_key);
+    m_painted_colors_glmodel.reset();
+    m_painted_colors_runs.clear();
+
+    // Whole model triangles, as the facets record what they touch: a triangle the paint only partly covers
+    // is left to the preview.
+    std::vector<bool> excluded(mv->mesh().its.indices.size(), false);
+    for (const TextureDisplacementLayer &l : mv->texture_displacement_layers) {
+        if (l.slot < 0 || l.slot >= int(TEXTURE_DISPLACEMENT_MAX_LAYERS) || (!whole_stack && l.slot != m_active_layer_slot))
+            continue;
+        for (const TriangleSelector::TriangleBitStreamMapping &m : mv->texture_displacement_facet(l.slot).get_data().triangles_to_split)
+            if (m.triangle_idx >= 0 && size_t(m.triangle_idx) < excluded.size())
+                excluded[size_t(m.triangle_idx)] = true;
+    }
+
+    // One model, its triangles in filament order (painted_colors() groups them), drawn a range per filament.
+    const std::vector<size_t> kept = m_painted_colors.outside(excluded);
+    GLModel::Geometry         init_data;
+    init_data.format = { GLModel::Geometry::EPrimitiveType::Triangles, GLModel::Geometry::EVertexLayout::P3 };
+    init_data.reserve_vertices(kept.size() * 3);
+    init_data.reserve_indices(kept.size() * 3);
+    unsigned n = 0;
+    for (const size_t t : kept) {
+        const int state = m_painted_colors.state[t];
+        if (m_painted_colors_runs.empty() || m_painted_colors_runs.back().first != state)
+            m_painted_colors_runs.push_back({ state, { size_t(n), size_t(n) } });
+        for (int i = 0; i < 3; ++i)
+            init_data.add_vertex(m_painted_colors.facets.vertices[size_t(m_painted_colors.facets.indices[t][i])]);
+        init_data.add_triangle(n, n + 1, n + 2);
+        n += 3;
+        m_painted_colors_runs.back().second.second = size_t(n);
+    }
+    if (!init_data.is_empty())
+        m_painted_colors_glmodel.init_from(std::move(init_data));
+}
+
+bool GLGizmoTextureDisplacement::render_painted_colors(bool whole_stack)
+{
+    rebuild_painted_colors(whole_stack);
+    const ModelObject *mo     = m_c->selection_info()->model_object();
+    const ModelVolume *mv     = texture_volume();
+    GLShaderProgram   *shader = wxGetApp().get_shader("mm_gouraud");
+    if (mo == nullptr || mv == nullptr || shader == nullptr || !m_painted_colors_glmodel.is_initialized())
+        return false;
+
+    const Selection             &selection    = m_parent.get_selection();
+    const Transform3d            trafo_matrix = mo->instances[selection.get_instance_idx()]->get_transformation().get_matrix() * mv->get_matrix();
+    const Camera                &camera       = wxGetApp().plater()->get_camera();
+    const Transform3d           &view_matrix  = camera.get_view_matrix();
+    const Matrix3d               normal_matrix = trafo_matrix.matrix().block(0, 0, 3, 3).inverse().transpose();
+    const std::vector<ColorRGBA> colors        = wxGetApp().plater()->get_extruders_colors();
+
+    shader->start_using();
+    // Set up as render_triangles() sets it up, so the colours are lit, clipped and slope-marked exactly as the
+    // neutral surface they cover.
+    const ClippingPlaneDataWrapper clp_data = get_clipping_plane_data();
+    shader->set_uniform("clipping_plane", clp_data.clp_dataf);
+    shader->set_uniform("z_range", clp_data.z_range);
+    shader->set_uniform("view_model_matrix", view_matrix * trafo_matrix);
+    shader->set_uniform("projection_matrix", camera.get_projection_matrix());
+    shader->set_uniform("view_normal_matrix", Matrix3d(view_matrix.matrix().block(0, 0, 3, 3) * normal_matrix));
+    shader->set_uniform("volume_world_matrix", trafo_matrix);
+    shader->set_uniform("volume_mirrored", trafo_matrix.matrix().determinant() < 0.);
+    shader->set_uniform("slope.actived", m_parent.is_using_slope());
+    shader->set_uniform("slope.volume_world_normal_matrix", Matrix3f(normal_matrix.cast<float>()));
+    shader->set_uniform("slope.normal_z", float(-std::cos(Geometry::deg2rad(m_highlight_by_angle_threshold_deg))));
+    shader->set_uniform("slope.up_direction", get_tilt_up_direction());
+    shader->set_uniform("show_wireframe", false);
+    // A full depth unit in front of the selectors' highlight at -1 in the Normal view, the least OpenGL
+    // guarantees to tell apart. Depth writes off, as for the tint: the wireframe and seam overlays drawn later
+    // test against the real surface, and the tint drawn after this shows on top of it.
+    glsafe(::glEnable(GL_POLYGON_OFFSET_FILL));
+    glsafe(::glPolygonOffset(-2.f, -2.f));
+    glsafe(::glDepthMask(GL_FALSE));
+    bool drawn = false;
+    for (const auto &[state, range] : m_painted_colors_runs)
+        if (state >= 1 && size_t(state) <= colors.size()) {
+            m_painted_colors_glmodel.set_color(adjust_color_for_rendering(colors[size_t(state - 1)]));
+            m_painted_colors_glmodel.render(range, shader);
+            drawn = true;
+        }
+    glsafe(::glDepthMask(GL_TRUE));
+    glsafe(::glDisable(GL_POLYGON_OFFSET_FILL));
+    shader->stop_using();
+    return drawn;
+}
+
 void GLGizmoTextureDisplacement::rebuild_paint_overlay()
 {
     m_paint_overlay_glmodel.reset();
@@ -1671,11 +1917,12 @@ void GLGizmoTextureDisplacement::render_paint_overlay(GLModel &overlay)
     shader->set_uniform("view_model_matrix", camera.get_view_matrix() * trafo_matrix);
     shader->set_uniform("projection_matrix", camera.get_projection_matrix());
     // Translucent, and pulled toward the camera so it wins the depth test against the coincident
-    // shaded surface. Depth writes are off: this is a tint, and letting it own the depth buffer would
-    // make the wireframe and seam overlays drawn after it fight with geometry that is not really
-    // there. Blending is already enabled by render_painter_gizmo().
+    // shaded surface - and against the selectors' highlight at -1 in the Normal view, by the full depth
+    // unit OpenGL guarantees to tell apart. Depth writes are off: this is a tint, and letting it own the
+    // depth buffer would make the wireframe and seam overlays drawn after it fight with geometry that is
+    // not really there. Blending is already enabled by render_painter_gizmo().
     glsafe(::glEnable(GL_POLYGON_OFFSET_FILL));
-    glsafe(::glPolygonOffset(-1.5f, -1.5f));
+    glsafe(::glPolygonOffset(-2.f, -2.f));
     glsafe(::glDepthMask(GL_FALSE));
     overlay.render();
     glsafe(::glDepthMask(GL_TRUE));
@@ -1991,6 +2238,9 @@ void GLGizmoTextureDisplacement::rebuild_preview()
     // finishes after the job queued below - and, since the counter is shared with the worker, that
     // job also notices mid-run and aborts rather than computing a result nobody will use.
     m_preview_generation->fetch_add(1);
+    // Everything rebuilt from here on reads the current palette. Cleared before any of the early returns
+    // below, which would otherwise leave it set and re-run this every frame.
+    m_palette_changed = false;
     update_uv_editor();
     rebuild_shaded_preview_mesh();
     rebuild_paint_overlay();
@@ -2061,25 +2311,21 @@ void GLGizmoTextureDisplacement::queue_preview_job()
     input.volume_to_world = texture_displacement_volume_to_world(*mv);
     for (int i = 0; i < int(TEXTURE_DISPLACEMENT_MAX_LAYERS); ++i)
         input.facets_data[size_t(i)] = mv->texture_displacement_facet(i).get_data();
-    // Captured here rather than read in the handler: get_extruders_colors() is main-thread state and
-    // the preview has to be grouped against the same palette it was computed with, not whatever is
-    // loaded by the time it lands.
+    // Captured here rather than read in the handler: the palette is main-thread state, and the preview
+    // has to be grouped against the same palette it was computed with, not whatever it is by the time
+    // the result lands.
     input.color = color_settings_for(*mv);
-    // The filament list the result's indices refer to, captured with the job rather than read back
-    // when it lands - loading a filament meanwhile must not recolour a preview computed against a
-    // different list.
-    // Every extruder, not the palette's physical-only list: the bake writes the filament it resolved
-    // to, and a mix resolves to a *mixed filament slot*, which is an extruder past the physical ones.
-    // Grouping against the shorter list dropped every triangle carrying such a slot out of the mesh
-    // entirely - the relief vanished and left only the few triangles that happened to print in a plain
-    // filament. The palette still has to be built from physical filaments alone (see filament_palette()),
-    // which is why these two are not the same list.
-    const std::vector<ColorRGBA> filaments = wxGetApp().plater()->get_extruders_colors();
+    // The result names a palette entry per triangle (index + 1), so these are the colours to draw it in:
+    // a single filament's own, or for a mix the colour its slot will show once a bake creates it.
+    std::vector<ColorRGBA> entry_colors;
+    entry_colors.reserve(input.color.palette.size());
+    for (const PrintableColor &e : input.color.palette)
+        entry_colors.emplace_back(e.rgb.x(), e.rgb.y(), e.rgb.z(), 1.f);
 
     m_preview_job_running = true;
     auto &worker = wxGetApp().plater()->get_ui_job_worker();
     queue_job(worker, std::make_unique<TextureDisplacementPreviewJob>(std::move(input), generation, m_preview_generation,
-        [this, filaments](TextureDisplacementPreviewResult result, uint64_t result_generation) {
+        [this, entry_colors](TextureDisplacementPreviewResult result, uint64_t result_generation) {
             indexed_triangle_set its = std::move(result.mesh);
             m_preview_job_running = false;
             if (result_generation != m_preview_generation->load()) {
@@ -2093,14 +2339,11 @@ void GLGizmoTextureDisplacement::queue_preview_job()
             } else {
                 m_preview_glmodel.reset();
                 m_preview_color_runs.clear();
-                if (result.triangle_color.size() == its.indices.size() && !filaments.empty()) {
-                    // Group by *filament*, not by palette entry: what the bake wrote is the resolved
-                    // filament, interleaving already applied, so this shows the real banding rather
-                    // than the flat average the eye will turn it into.
+                if (result.triangle_color.size() == its.indices.size() && !entry_colors.empty()) {
                     indexed_triangle_set sorted;
                     sorted.vertices = its.vertices;
                     sorted.indices.reserve(its.indices.size());
-                    for (int want = 0; want <= int(filaments.size()); ++want) {
+                    for (int want = 0; want <= int(entry_colors.size()); ++want) {
                         const size_t first = sorted.indices.size();
                         for (size_t i = 0; i < its.indices.size(); ++i)
                             if (int(result.triangle_color[i]) == want)
@@ -2109,7 +2352,7 @@ void GLGizmoTextureDisplacement::queue_preview_job()
                             continue;
                         m_preview_color_runs.push_back(
                             { { first * 3, sorted.indices.size() * 3 },
-                              want == 0 ? GLVolume::NEUTRAL_COLOR : filaments[size_t(want - 1)] });
+                              want == 0 ? GLVolume::NEUTRAL_COLOR : entry_colors[size_t(want - 1)] });
                     }
                     m_preview_glmodel.init_from(sorted);
                 } else {
@@ -3366,6 +3609,9 @@ void GLGizmoTextureDisplacement::update_from_model_object(bool first_update)
 
     const ModelObject *mo = m_c->selection_info()->model_object();
     m_triangle_selectors.clear();
+    // The base keeps the last mesh a fill tool hovered, and render_painter_gizmo() reads it as a hover that is
+    // still on: a new set of selectors has none.
+    m_seed_fill_last_mesh_id = -1;
 
     std::vector<ColorRGBA> ebt_colors;
     ebt_colors.push_back(GLVolume::NEUTRAL_COLOR);
@@ -4263,38 +4509,14 @@ TextureDisplacementFacetsData GLGizmoTextureDisplacement::facets_data_of(const M
     return out;
 }
 
-bool GLGizmoTextureDisplacement::any_layer_colors(const ModelVolume &mv)
+bool GLGizmoTextureDisplacement::layer_shows_color(const TextureDisplacementLayer &layer)
 {
-    for (const TextureDisplacementLayer &layer : mv.texture_displacement_layers)
-        if (layer.color_enabled && !layer.empty() && decode_height_texture(layer).has_color())
-            return true;
-    return false;
+    return layer.color_enabled && !layer.empty() && height_texture_has_color(layer);
 }
 
-void GLGizmoTextureDisplacement::bind_mixes_to_filament_slots(std::vector<PaletteEntry> &palette)
+bool GLGizmoTextureDisplacement::any_layer_colors(const ModelVolume &mv)
 {
-    Sidebar *sidebar = &wxGetApp().plater()->sidebar();
-    if (sidebar == nullptr)
-        return;
-    for (PaletteEntry &e : palette) {
-        if (!e.is_mix())
-            continue;
-        // Components are 1-based in the config; the ratios are percentages summing to 100, which is the
-        // form create_mixed_filament_from_result() normalises from.
-        const int a_pct = int(std::lround(100.0 * double(e.num) / double(e.den)));
-        const int slot  = sidebar->ensure_mixed_filament({ unsigned(e.a + 1), unsigned(e.b + 1) },
-                                                         { a_pct, 100 - a_pct });
-        if (slot >= 0) {
-            e.a = e.b = slot;
-            e.num = e.den = 1;
-        } else {
-            // No room for another slot. Collapse to the component that dominates the blend, which is what
-            // the old per-triangle path did on a surface it could not band anyway.
-            const int dominant = (e.num * 2 >= e.den) ? e.a : e.b;
-            e.a = e.b = dominant;
-            e.num = e.den = 1;
-        }
-    }
+    return std::any_of(mv.texture_displacement_layers.begin(), mv.texture_displacement_layers.end(), layer_shows_color);
 }
 
 TextureColorSettings GLGizmoTextureDisplacement::color_settings_for(const ModelVolume &mv)
@@ -4303,47 +4525,90 @@ TextureColorSettings GLGizmoTextureDisplacement::color_settings_for(const ModelV
     if (!any_layer_colors(mv))
         return out; // nothing is colouring: every colour path stays switched off
     out.palette          = cached_palette();
-    out.palette_pure     = make_palette(m_palette_filaments, /* mixing */ false, PALETTE_MAX_ENTRIES);
-    // Done here rather than in cached_palette(): this runs when a preview or a bake is queued, off a
-    // user action, while that one is also touched from the render path - and creating filament slots
-    // there would mutate the project mid-frame.
-    bind_mixes_to_filament_slots(out.palette);
+    out.palette_pure     = make_palette(m_palette_filaments, {});
     out.despeckle_passes = mv.texture_displacement_options.color_despeckle;
     return out;
 }
 
 const std::vector<GLGizmoTextureDisplacement::PaletteEntry> &GLGizmoTextureDisplacement::cached_palette()
 {
-    // Rebuilt only when the loaded filaments or the mixing setting actually change. The shaded preview
-    // rebuilds on every paint stroke and the subdivide preview on every slider frame, and filling the
-    // quantizer's lookup cube for a 64-entry palette is tens of milliseconds - paying that per stroke
-    // is the difference between painting that keeps up and painting that stutters.
-    const ModelVolume *mv     = texture_volume();
-    const bool         mixing = mv != nullptr && mv->texture_displacement_options.color_mix_enabled;
+    // Rebuilt only when something it depends on actually changes. The shaded preview rebuilds on every
+    // paint stroke and the panel asks every frame, while ranking the mixes and filling the quantizer's
+    // lookup cube each take tens of milliseconds - paying that per stroke is the difference between
+    // painting that keeps up and painting that stutters.
+    //
+    // Two levels. The ranking depends only on the filaments and the images, so dragging the count, or a
+    // bake creating slots, re-picks from it without ranking again; the palette and its quantizers depend
+    // on that pick as well.
+    const ModelVolume     *mv        = texture_volume();
+    const bool             mixing    = mv != nullptr && mv->texture_displacement_options.color_mix_enabled;
+    const int              mix_count = mv != nullptr ? std::max(0, mv->texture_displacement_options.color_mix_count) : 0;
     std::vector<ColorRGBA> filaments = filament_palette();
-    // Every mix costs a filament slot once they are bound to one, and the mask can name only so many
-    // states, so the palette has to leave room beside the physical filaments it already counts.
-    const int cap = int(EnforcerBlockerType::ExtruderMax);
-    if (m_palette_cache.empty() || filaments != m_palette_filaments || mixing != m_palette_mixing ||
-        cap != m_palette_cap) {
+    // The images themselves rather than their addresses, so a freed and reallocated image can never
+    // pass for the old one. Whether one has colour, and whether its colours are flat, follows from it.
+    std::vector<std::shared_ptr<std::vector<unsigned char>>> images;
+    if (mv != nullptr)
+        for (const TextureDisplacementLayer &layer : mv->texture_displacement_layers)
+            if (layer.color_enabled && !layer.empty())
+                images.push_back(layer.image_data);
+
+    const bool ranking_stale = filaments != m_palette_filaments || images != m_palette_images;
+    if (ranking_stale) {
         m_palette_filaments = std::move(filaments);
-        m_palette_mixing    = mixing;
-        m_palette_cap       = cap;
-        m_palette_cache     = make_palette(m_palette_filaments, mixing, cap);
-        m_palette_quantizer = make_palette_quantizer(m_palette_cache);
+        m_palette_images    = std::move(images);
+        m_mix_ranking.reset();
+    }
+    if (mixing && !m_mix_ranking)
+        m_mix_ranking = rank_mixes(m_palette_filaments, mix_targets(mv->texture_displacement_layers),
+                                   int(EnforcerBlockerType::ExtruderMax) - int(m_palette_filaments.size()));
+
+    // Which mixes the project can still print: those it has a fixed slot for, plus as many new ones as
+    // there are free slots.
+    const PresetBundle            &bundle     = *wxGetApp().preset_bundle;
+    const int                      free_slots = std::max(0, int(EnforcerBlockerType::ExtruderMax) - int(bundle.filament_presets.size()));
+    const std::vector<std::string> slots      = mixed_slot_signature(bundle.project_config);
+    if (ranking_stale || m_palette_cache.empty() || mixing != m_palette_mixing || mix_count != m_palette_mix_count ||
+        free_slots != m_palette_free_slots || slots != m_palette_slots) {
+        m_palette_mixing     = mixing;
+        m_palette_mix_count  = mix_count;
+        m_palette_free_slots = free_slots;
+        m_palette_slots      = slots;
+        std::vector<PaletteEntry> mixes;
+        if (mixing && m_mix_ranking)
+            mixes = pick_mixes(*m_mix_ranking, mix_count, free_slots, [&bundle](const PaletteEntry &e) {
+                return find_fixed_mixed_filament(bundle.project_config, {unsigned(e.a + 1), unsigned(e.b + 1)},
+                                                 {e.a_percent(), 100 - e.a_percent()}) >= 0;
+            });
+        std::vector<PaletteEntry> palette = make_palette(m_palette_filaments, mixes);
+        // The previews keep what they were drawn with, so a palette that really changed under them -
+        // a filament or a mixed slot edited in the sidebar - has to send them round again.
+        m_palette_changed        = m_palette_changed || (!m_palette_cache.empty() && !same_palette(palette, m_palette_cache));
+        m_palette_cache          = std::move(palette);
+        m_palette_quantizer      = nullptr;
+        m_palette_pure_quantizer = nullptr;
     }
     return m_palette_cache;
 }
 
+std::pair<ColorQuantizeFn, ColorQuantizeFn> GLGizmoTextureDisplacement::palette_quantizers()
+{
+    cached_palette();
+    if (!m_palette_quantizer) {
+        m_palette_quantizer      = make_palette_quantizer(m_palette_cache);
+        const bool has_mixes     = m_palette_cache.size() > m_palette_filaments.size();
+        m_palette_pure_quantizer = has_mixes ? make_palette_quantizer(make_palette(m_palette_filaments, {})) : m_palette_quantizer;
+    }
+    return { m_palette_quantizer, m_palette_pure_quantizer };
+}
+
 std::vector<ColorRGBA> GLGizmoTextureDisplacement::filament_palette()
 {
     std::vector<ColorRGBA> all = wxGetApp().plater()->get_extruders_colors();
 
-    // Physical filaments only. The mixes this palette produces each become a mixed filament slot of
-    // their own (see bind_mixes_to_filament_slots()), and those slots are extruders too - so taking the
-    // list as it comes meant the next rebuild mixed *them* again, and handed components naming a
-    // virtual slot to a blend that can only name physical ones. That is what left entries reading
-    // "filament 1 plus nothing" and raised "Mixed filament has invalid or mismatched components".
+    // Physical filaments only. A mix bakes into a mixed filament slot of its own, and those slots are
+    // extruders too - mixing them again would hand a blend components naming a virtual slot, where it
+    // can only name physical ones ("Mixed filament has invalid or mismatched components"). Mixed slots
+    // are kept after the physical ones, so filament i here is extruder i.
     const auto *is_mixed = wxGetApp().preset_bundle->project_config.option<ConfigOptionBools>("filament_is_mixed");
     std::vector<ColorRGBA> palette;
     palette.reserve(all.size());
@@ -4357,44 +4622,211 @@ std::vector<ColorRGBA> GLGizmoTextureDisplacement::filament_palette()
     return palette;
 }
 
-
-std::vector<GLGizmoTextureDisplacement::PaletteEntry> GLGizmoTextureDisplacement::make_palette(
-    const std::vector<ColorRGBA> &filaments, bool mixing, int max_entries)
+std::vector<GLGizmoTextureDisplacement::MixTarget> GLGizmoTextureDisplacement::mix_targets(
+    const std::vector<TextureDisplacementLayer> &layers)
 {
-    std::vector<PaletteEntry> out;
-    const int                 n = int(filaments.size());
-    for (int i = 0; i < n; ++i)
-        out.push_back({ Vec3f(filaments[size_t(i)].r(), filaments[size_t(i)].g(), filaments[size_t(i)].b()),
-                        i, i, 1, 1 });
-    if (!mixing || n < 2)
-        return out;
+    // Each layer's bins, weighted by their share of that layer's pixels.
+    std::vector<std::vector<MixTarget>> per_layer;
+    for (const TextureDisplacementLayer &layer : layers) {
+        if (!layer.color_enabled || layer.empty() || analyze_texture_detail(layer).flat_colors)
+            continue;
+        TextureDisplacementLayer raw = layer;
+        raw.smoothing                = 0.f;
+        const DecodedHeightTexture tex = decode_height_texture(raw);
+        if (!tex.has_color())
+            continue;
 
-    // How many intermediate steps each pair gets, chosen so the whole palette stays under
-    // PALETTE_MAX_ENTRIES. Fewer filaments means more room for mixes, which is also what you want:
-    // with two filaments the mixes are the only way to get anywhere, and with sixteen there is little
-    // point mixing at all. `den` is also the band/dither repeat, so a small one is a short pattern.
-    const int pairs = n * (n - 1) / 2;
-    int       steps = 0;
-    for (int s = 5; s >= 1; --s)
-        if (n + pairs * s <= max_entries) {
-            steps = s;
-            break;
+        // 16 levels per channel, each bin keeping the mean of the colours that fell in it: a coarse grid
+        // to gather on, without snapping every colour to a bin corner.
+        struct Bin
+        {
+            double   r = 0., g = 0., b = 0.;
+            uint32_t n = 0;
+        };
+        std::vector<Bin> bins(size_t(16 * 16 * 16));
+        // Past the budget, one pixel from each run of `stride`, at an offset jittered by a fixed-seed
+        // generator. A fixed step would sample a lattice that a striped texture can line up with, so
+        // that only one of its colours is ever seen; jittered, stripes of any period or orientation are
+        // sampled in proportion, and the same image still always gives the same targets. The offset
+        // comes from the generator's high bits: a power-of-two LCG's low bits repeat every 2, 4, 8...
+        // steps, and the stride is a power of two for exactly the images large enough to need this.
+        const size_t npx     = size_t(tex.width) * size_t(tex.height);
+        const size_t stride  = std::max<size_t>(1, npx / MIX_TARGET_SAMPLES);
+        uint64_t     state   = 0x9E3779B97F4A7C15ull;
+        size_t       sampled = 0;
+        for (size_t start = 0; start < npx; start += stride) {
+            state          = state * 6364136223846793005ull + 1442695040888963407ull;
+            const size_t i = start + size_t((uint64_t(uint32_t(state >> 32)) * uint64_t(stride)) >> 32);
+            if (i >= npx)
+                break;
+            const uint8_t *px  = &tex.rgb[i * 3];
+            Bin           &bin = bins[size_t(px[0] >> 4) * 256 + size_t(px[1] >> 4) * 16 + size_t(px[2] >> 4)];
+            bin.r += px[0];
+            bin.g += px[1];
+            bin.b += px[2];
+            ++bin.n;
+            ++sampled;
         }
-    if (steps == 0)
-        return out;
-    const int den = steps + 1;
+        std::vector<MixTarget> targets;
+        for (const Bin &bin : bins)
+            if (bin.n > 0) {
+                const double inv = 1. / (255. * double(bin.n));
+                targets.push_back({ srgb_to_lab(Vec3f(float(bin.r * inv), float(bin.g * inv), float(bin.b * inv))),
+                                    float(double(bin.n) / double(sampled)) });
+            }
+        per_layer.push_back(std::move(targets));
+    }
 
+    // The layers weigh the same and together 1, settled before the pruning below: what rank_mixes() sums
+    // over the kept bins is then a mean over every pixel of the colouring layers, with the pixels of a
+    // dropped bin counted as no better off.
+    std::vector<MixTarget> out;
+    for (std::vector<MixTarget> &targets : per_layer)
+        for (MixTarget &t : targets) {
+            t.weight /= float(per_layer.size());
+            out.push_back(t);
+        }
+    if (out.size() > MIX_TARGET_BINS) {
+        std::partial_sort(out.begin(), out.begin() + MIX_TARGET_BINS, out.end(),
+                          [](const MixTarget &l, const MixTarget &r) { return l.weight > r.weight; });
+        out.resize(MIX_TARGET_BINS);
+    }
+    return out;
+}
+
+std::vector<GLGizmoTextureDisplacement::PaletteEntry> GLGizmoTextureDisplacement::rank_mixes(
+    const std::vector<ColorRGBA> &filaments, const std::vector<MixTarget> &targets, int limit)
+{
+    const int n = int(filaments.size());
+    if (n < 2 || targets.empty() || limit <= 0)
+        return {};
+
+    // Every pair at every short-cycle ratio, coloured as its slot will be.
+    std::vector<std::string> hex(filaments.size());
     for (int i = 0; i < n; ++i)
-        for (int j = i + 1; j < n; ++j) {
-            const Vec3f lab_i = srgb_to_lab(Vec3f(filaments[size_t(i)].r(), filaments[size_t(i)].g(), filaments[size_t(i)].b()));
-            const Vec3f lab_j = srgb_to_lab(Vec3f(filaments[size_t(j)].r(), filaments[size_t(j)].g(), filaments[size_t(j)].b()));
-            for (int k = 1; k <= steps; ++k) {
-                // k/den of filament i, the rest of j - averaged in Lab, which is what the eye does
-                // when the two are interleaved too finely to resolve.
-                const float t = float(k) / float(den);
-                out.push_back({ lab_to_srgb(lab_i * t + lab_j * (1.f - t)), i, j, k, den });
+        hex[size_t(i)] = encode_color(filaments[size_t(i)]);
+    std::vector<PaletteEntry> candidates;
+    for (int i = 0; i < n; ++i)
+        for (int j = i + 1; j < n; ++j)
+            for (int den = 2; den <= 6; ++den)
+                for (int num = 1; num < den; ++num) {
+                    if (std::gcd(num, den) != 1)
+                        continue; // 2/4 is 1/2, already there
+                    PaletteEntry e{ Vec3f::Zero(), i, j, num, den };
+                    ColorRGB     blended;
+                    if (!decode_color(blend_color_multi({ hex[size_t(i)], hex[size_t(j)] },
+                                                        { e.a_percent(), 100 - e.a_percent() }),
+                                      blended))
+                        continue;
+                    e.rgb = Vec3f(blended.r(), blended.g(), blended.b());
+                    candidates.push_back(e);
+                }
+
+    // How far each target is from the nearest single filament, and from every candidate.
+    const size_t       nt = targets.size(), nc = candidates.size();
+    std::vector<Vec3f> filament_lab(size_t(n), Vec3f::Zero());
+    for (int i = 0; i < n; ++i)
+        filament_lab[size_t(i)] = srgb_to_lab(Vec3f(filaments[size_t(i)].r(), filaments[size_t(i)].g(), filaments[size_t(i)].b()));
+    const auto de = [](const Vec3f &l, const Vec3f &r) { return DeltaE00(l.x(), l.y(), l.z(), r.x(), r.y(), r.z()); };
+    std::vector<float> pure_d(nt, std::numeric_limits<float>::max());
+    for (size_t t = 0; t < nt; ++t)
+        for (const Vec3f &lab : filament_lab)
+            pure_d[t] = std::min(pure_d[t], de(targets[t].lab, lab));
+    std::vector<float> dist(nc * nt);
+    tbb::parallel_for(tbb::blocked_range<size_t>(0, nc), [&](const tbb::blocked_range<size_t> &range) {
+        for (size_t c = range.begin(); c < range.end(); ++c) {
+            const Vec3f lab = srgb_to_lab(candidates[c].rgb);
+            for (size_t t = 0; t < nt; ++t)
+                dist[c * nt + t] = de(targets[t].lab, lab);
+        }
+    });
+
+    // Greedy: each round takes the candidate that lowers the weighted error the most. A candidate only
+    // counts where it beats the single filament by PREFER_PURE_DE, since everywhere else the quantizer
+    // picks the filament anyway.
+    std::vector<float>        current = pure_d;
+    std::vector<char>         taken(nc, 0);
+    std::vector<PaletteEntry> out;
+    const auto                counts = [&](size_t c, size_t t) {
+        const float d = dist[c * nt + t];
+        return d < current[t] && d <= pure_d[t] - PREFER_PURE_DE;
+    };
+    while (int(out.size()) < limit) {
+        size_t best      = nc;
+        double best_gain = 0.;
+        for (size_t c = 0; c < nc; ++c) {
+            if (taken[c])
+                continue;
+            double gain = 0.;
+            for (size_t t = 0; t < nt; ++t)
+                if (counts(c, t))
+                    gain += double(targets[t].weight) * double(current[t] - dist[c * nt + t]);
+            if (gain > best_gain) {
+                best_gain = gain;
+                best      = c;
             }
         }
+        if (best == nc || best_gain < double(MIN_MIX_GAIN))
+            break;
+        taken[best] = 1;
+        out.push_back(candidates[best]);
+        for (size_t t = 0; t < nt; ++t)
+            if (counts(best, t))
+                current[t] = dist[best * nt + t];
+    }
+    return out;
+}
+
+std::vector<GLGizmoTextureDisplacement::PaletteEntry> GLGizmoTextureDisplacement::pick_mixes(
+    const std::vector<PaletteEntry> &ranking, int count, int free_slots, const std::function<bool(const PaletteEntry &)> &reusable)
+{
+    std::vector<PaletteEntry> out;
+    for (const PaletteEntry &e : ranking) {
+        if (int(out.size()) >= count)
+            break;
+        // Out of free slots, a later mix that already has one still fits.
+        if (reusable && reusable(e)) {
+            out.push_back(e);
+        } else if (free_slots > 0) {
+            out.push_back(e);
+            --free_slots;
+        }
+    }
+    return out;
+}
+
+std::vector<GLGizmoTextureDisplacement::PaletteEntry> GLGizmoTextureDisplacement::make_palette(
+    const std::vector<ColorRGBA> &filaments, const std::vector<PaletteEntry> &mixes)
+{
+    std::vector<PaletteEntry> out;
+    out.reserve(filaments.size() + mixes.size());
+    for (int i = 0; i < int(filaments.size()); ++i)
+        out.push_back({ Vec3f(filaments[size_t(i)].r(), filaments[size_t(i)].g(), filaments[size_t(i)].b()), i, i, 1, 1 });
+    out.insert(out.end(), mixes.begin(), mixes.end());
+    return out;
+}
+
+std::vector<int> GLGizmoTextureDisplacement::palette_filaments(const std::vector<PaletteEntry>                &palette,
+                                                               const std::vector<uint8_t>                     &triangle_color,
+                                                               const std::function<int(const PaletteEntry &)> &slot_for_mix)
+{
+    std::vector<char> used(palette.size(), 0);
+    for (const uint8_t v : triangle_color)
+        if (v > 0 && size_t(v) <= palette.size())
+            used[size_t(v) - 1] = 1;
+
+    std::vector<int> out(palette.size(), -1);
+    for (size_t i = 0; i < palette.size(); ++i) {
+        const PaletteEntry &e = palette[i];
+        if (!e.is_mix()) {
+            out[i] = e.a;
+        } else if (used[i]) {
+            const int slot = slot_for_mix ? slot_for_mix(e) : -1;
+            // No room for another slot: the component that dominates the blend is the nearest the print
+            // can come.
+            out[i] = slot >= 0 ? slot : (e.num * 2 >= e.den ? e.a : e.b);
+        }
+    }
     return out;
 }
 
@@ -4434,15 +4866,7 @@ ColorQuantizeFn GLGizmoTextureDisplacement::make_palette_quantizer(const std::ve
                             best_pure   = int(i);
                         }
                     }
-                    // A mix is an interleave that only reads as its colour from a distance; up close it is
-                    // stripes. So it is spent only where it buys a better match than the nearest single
-                    // filament - but "better" was set at ten Delta E, which is not a visible step, it is a
-                    // different colour. Measured over the whole cube that threshold turned 94% of the
-                    // lookups that wanted a mix back into a pure filament, leaving 38%; along a greyscale
-                    // ramp, the shape a height texture actually traces, it cut 80% to 66%. Two Delta E is
-                    // about where a side-by-side difference stops being arguable, which is the right place
-                    // to start paying for stripes.
-                    constexpr float PREFER_PURE_DE = 2.f;
+                    // A mix only where it clearly beats the nearest single filament, see PREFER_PURE_DE.
                     if (best_pure >= 0 && palette[size_t(best)].is_mix() && best_pure_d - best_d < PREFER_PURE_DE)
                         best = best_pure;
                     (*lut)[(size_t(r) * E + size_t(g)) * E + size_t(b)] = uint8_t(best);
@@ -4461,7 +4885,7 @@ ColorQuantizeFn GLGizmoTextureDisplacement::make_palette_quantizer(const std::ve
 TextureDisplacementPrepareResult GLGizmoTextureDisplacement::prepare_mesh(
     const indexed_triangle_set &base, const TextureDisplacementFacetsData &masks,
     const std::vector<TextureDisplacementLayer> &layers, const TextureDisplacementPrepareParams &params,
-    const std::vector<PrintableColor> &palette, const DisplacementProgressFn &progress,
+    const TextureColorSettings &color_settings, const DisplacementProgressFn &progress,
     BakeStageRecorder *debug)
 {
     TextureDisplacementPrepareResult out;
@@ -4539,10 +4963,13 @@ TextureDisplacementPrepareResult GLGizmoTextureDisplacement::prepare_mesh(
             // Colour boundaries need triangles of their own - the chord test cannot see them, since
             // the height field is perfectly smooth across a change of filament.
             ColorFieldSampler color;
-            if (params.subdiv_color_edge_mm > 0.f && !palette.empty())
-                color = make_combined_color_sampler(mesh.its, layers, current, make_palette_quantizer(palette));
-            // Note the sampler is built on the *quantizer* alone - the refinement follows perceived
-            // colour, never the interleaving that realises a mix - the slicer does that per layer.
+            // A flat-colour layer is matched against single filaments only, as the bake does, so its
+            // boundaries are refined where the bake will actually change filament.
+            if (params.subdiv_color_edge_mm > 0.f && !color_settings.empty())
+                color = make_combined_color_sampler(mesh.its, layers, current, make_palette_quantizer(color_settings.palette),
+                                                    make_palette_quantizer(color_settings.palette_pure));
+            // The refinement follows perceived colour: a mix is one colour here, however the slicer
+            // interleaves its filaments layer by layer.
             // "Min edge" is a feature-mode control (it is the floor the curvature test refines down
             // to); in plain adaptive mode the target edge length is the only criterion, so the floor
             // must not be allowed to silently override a target the user set below it.
@@ -4830,9 +5257,9 @@ void GLGizmoTextureDisplacement::rebuild_subdivide_preview()
         // Same colour criterion Apply will use, so the previewed wireframe is the mesh that commits.
         ColorFieldSampler color;
         if (m_subdivide_color_mm > 0.f && any_layer_colors(*mv)) {
-            cached_palette(); // refreshes m_palette_quantizer if the filaments changed
-            color = make_combined_color_sampler(mv->mesh().its, mv->texture_displacement_layers, facets,
-                                                m_palette_quantizer);
+            const auto [quantize, quantize_pure] = palette_quantizers();
+            color = make_combined_color_sampler(mv->mesh().its, mv->texture_displacement_layers, facets, quantize,
+                                                quantize_pure);
         }
         its = subdivide_mesh_adaptive(mv->mesh().its, region, m_subdivide_target_mm,
                                       int(mv->mesh().its.indices.size()) + m_subdivide_budget_k * 1000,
@@ -5344,6 +5771,12 @@ void GLGizmoTextureDisplacement::on_render_input_window(float x, float y, float
         return;
     ModelVolume *mv = texture_volume();
 
+    // The palette also follows project state nobody tells this gizmo about - the filaments and mixed
+    // slots in the sidebar - so it is checked once a frame, and a change re-runs the previews.
+    cached_palette();
+    if (m_palette_changed)
+        m_preview_params_dirty = true;
+
     float  scale = m_parent.get_scale();
     #ifdef WIN32
         int dpi = get_dpi_for_window(wxGetApp().GetTopWindow());
@@ -6127,6 +6560,15 @@ void GLGizmoTextureDisplacement::on_render_input_window(float x, float y, float
                                        "of filaments can cover a photo or a gradient. An image of flat colors "
                                        "prints the same either way. Off uses one filament per area."));
                         if (opts.color_mix_enabled) {
+                            cached_palette(); // brings m_palette_filaments up to date
+                            // Every mix can become a filament slot, and there are only so many beside the
+                            // physical filaments.
+                            const int max_mixes = std::max(1, int(EnforcerBlockerType::ExtruderMax) - int(m_palette_filaments.size()));
+                            if (int_row("##color_mix_count", _L("Mixed colors"), &opts.color_mix_count, 1, max_mixes, "%d", card_pad))
+                                m_preview_params_dirty = true;
+                            hover_tip(_u8L("The most mixed filaments a bake may add. They are picked from the "
+                                           "texture's colors, and only the ones the bake actually uses are created."));
+                            // After the slider, so a change shows in the same frame.
                             ImGui::TextDisabled("%s", Slic3r::format(_u8L("%1% printable colors from %2% filaments"),
                                                                      int(cached_palette().size()), int(m_palette_filaments.size())).c_str());
                         }

src/slic3r/GUI/Gizmos/GLGizmoTextureDisplacement.hpp

@@ -16,11 +16,15 @@
 #include "libslic3r/Color.hpp"
 #include <cstddef>
 #include "libslic3r/TriangleSelector.hpp"
+#include "libslic3r/TriangleMesh.hpp"
+#include "admesh/stl.h"
 #include <cstdint>
+#include <functional>
 #include "libslic3r/Point.hpp"
 #include <imgui.h>
 #include <map>
 #include <memory>
+#include <optional>
 #include "slic3r/GUI/Gizmos/GLGizmoBase.hpp"
 #include <string>
 #include <vector>
@@ -58,7 +62,7 @@ public:
                                                          const TextureDisplacementFacetsData         &masks,
                                                          const std::vector<TextureDisplacementLayer> &layers,
                                                          const TextureDisplacementPrepareParams      &params,
-                                                         const std::vector<PrintableColor>           &palette,
+                                                         const TextureColorSettings                  &color_settings,
                                                          const DisplacementProgressFn                &progress,
                                                          // Optional step capture: receives the mesh
                                                          // after the remesh and after the refinement,
@@ -70,22 +74,43 @@ public:
 
     using PaletteEntry = PrintableColor;
 
-    // The printable palette: the loaded filaments (clamped to the sixteen mmu_segmentation_facets can
-    // address), plus - when `mixing` - every pair of them at evenly spaced ratios.
+    // One colour mixes are meant to reach: a bin of the textures' colour histogram, in CIELAB, and how
+    // much of the image it covers.
+    struct MixTarget
+    {
+        Vec3f lab    = Vec3f::Zero();
+        float weight = 0.f;
+    };
+
+    // The colours worth mixing for: those of the colouring layers in `layers` whose image is not made of
+    // flat colours (TextureDetail::flat_colors - those print in single filaments only, so no mix could
+    // serve them). The layers weigh the same and, before only the heaviest bins are kept (which is what
+    // bounds rank_mixes()), together 1. Read from the image as imported, as analyze_texture_detail()
+    // does, so the Smoothing slider does not move the palette around.
+    static std::vector<MixTarget> mix_targets(const std::vector<TextureDisplacementLayer> &layers);
+
+    // Mixes of pairs of `filaments`, best first and at most `limit` of them. Each is the one that most
+    // improves the match to `targets` given those ranked before it, counted only where it beats the
+    // nearest single filament by the quantizer's prefer-pure margin - which is where the quantizer will
+    // actually pick it. Stops early once another mix would make no noticeable difference, so a texture
+    // the filaments already cover gets few mixes or none.
     //
-    // Mixes are averaged in **CIELAB**, not RGB and not subtractively: two filaments interleaved too
-    // finely to resolve are averaged by the eye, which is what a perceptual space models. Yellow and
-    // blue banded together read as a desaturated grey-green, and that is what the preview must promise
-    // - blending them subtractively would show a green the printer cannot produce this way.
-    //
-    // How many ratios depends on how many filaments there are, so the palette stays bounded: the
-    // quantizer's lookup cube costs one DeltaE00 per cell per entry to fill, and with sixteen
-    // filaments there are already plenty of colours without mixing any of them.
-    // `max_entries` bounds the whole palette. It is normally the quantizer's own limit, but when the
-    // mixes become filament slots it has to be the paint mask's instead: a mask can name only
-    // EnforcerBlockerType::ExtruderMax states, and every mix now occupies one of them.
-    static std::vector<PaletteEntry> make_palette(const std::vector<ColorRGBA> &filaments, bool mixing,
-                                                  int max_entries);
+    // Ratios are the short-cycle ones (k/d for d up to 6): the slicer interleaves a mix layer by layer,
+    // and a long cycle prints as visible bands rather than as a colour. A mix's `rgb` is the colour its
+    // mixed filament slot will show (blend_color_multi(), as the sidebar computes it), so the match, the
+    // preview and the slot all agree on what the mix looks like.
+    static std::vector<PaletteEntry> rank_mixes(const std::vector<ColorRGBA> &filaments,
+                                                const std::vector<MixTarget> &targets, int limit);
+
+    // The first `count` mixes of `ranking` the project can give a filament slot to. A mix `reusable`
+    // reports as already having a fixed slot costs nothing; any other uses up one of `free_slots`, and
+    // is skipped once they run out - so the palette never offers a colour a bake could not print.
+    static std::vector<PaletteEntry> pick_mixes(const std::vector<PaletteEntry> &ranking, int count, int free_slots,
+                                                const std::function<bool(const PaletteEntry &)> &reusable);
+
+    // The printable palette: the loaded filaments, entry i being filament i, followed by `mixes`.
+    static std::vector<PaletteEntry> make_palette(const std::vector<ColorRGBA> &filaments,
+                                                  const std::vector<PaletteEntry> &mixes);
 
     // Maps an image colour to the closest entry of `palette`, perceptually (CIEDE2000 over CIELAB - a
     // plain RGB distance picks visibly wrong filaments, most obviously between a saturated colour and
@@ -97,40 +122,49 @@ public:
     // to a worker thread and outlives the palette it was built from.
     static ColorQuantizeFn make_palette_quantizer(const std::vector<PaletteEntry> &palette);
 
-    // Turns a palette index plus a position into the filament to print there, interleaving the two
-    // filaments of a mixed entry per `mode`. `layer_height` sizes the Z bands; `cell_mm` the dither
+    // The filament (0-based) each entry of `palette` prints in, by palette index: a single filament is
+    // itself, a mix is the slot `slot_for_mix` returns for it. Only the mixes `triangle_color` actually
+    // uses (palette index + 1 per triangle, 0 for none) are asked for, since asking is what creates a
+    // slot. A mix that gets no slot (-1) prints in its dominant component; one nothing uses maps to -1.
+    //
+    // This is what the bake writes into the paint: a palette index is a filament only for the single
+    // filaments, while a mix's slot can sit anywhere among the project's mixed slots.
+    static std::vector<int> palette_filaments(const std::vector<PaletteEntry> &palette,
+                                              const std::vector<uint8_t> &triangle_color,
+                                              const std::function<int(const PaletteEntry &)> &slot_for_mix);
 
-    // Everything the jobs need to colour with, for the current volume: palette, mix mode, layer
-    // height, despeckle. Empty when no layer is actually colouring.
+    // Everything the jobs need to colour with, for the current volume: the palette, its single-filament
+    // part, and the despeckle passes. Empty when no layer is actually colouring. Read-only: no filament
+    // slot is created here, only when a bake commits (see palette_filaments()).
     TextureColorSettings color_settings_for(const ModelVolume &mv);
 
-    // The printable palette for the current filaments and mixing setting, rebuilt only when either
-    // actually changes - see the definition for why that caching is not optional.
+    // The printable palette for the current volume and project, rebuilt only when what it depends on
+    // changes - see the definition for why that caching is not optional.
     const std::vector<PaletteEntry> &cached_palette();
-    // Turns every mix in `palette` into a mixed filament slot and rewrites the entry to name that slot
-    // as a plain filament, so nothing downstream has to know a mix is involved: is_mix() goes false and
-    // the resolver simply returns it. The per-layer interleaving then happens in the slicer, where it is
-    // not limited by how fine the mesh is. Entries whose slot could not be created (the paint-state cap)
-    // fall back to the nearer of the two components.
-    void bind_mixes_to_filament_slots(std::vector<PaletteEntry> &palette);
-    std::vector<PaletteEntry>  m_palette_cache;
-    std::vector<ColorRGBA>     m_palette_filaments;
-    int                        m_palette_cap = 0; // the max_entries m_palette_cache was built with
-    bool                       m_palette_mixing = false;
-    ColorQuantizeFn            m_palette_quantizer;
+    // The quantizers for the cached palette and for its single filaments alone (flat-colour images),
+    // filled on first use. Only the subdivide preview matches colours on this thread - the jobs build
+    // their own from the palette they capture - so a palette rebuild, such as every step of a count
+    // drag, costs no lookup cube unless that preview asks for one.
+    std::pair<ColorQuantizeFn, ColorQuantizeFn> palette_quantizers();
+    std::vector<PaletteEntry> m_palette_cache;
+    ColorQuantizeFn           m_palette_quantizer;
+    ColorQuantizeFn           m_palette_pure_quantizer;
+    // Set when a rebuild changed the palette the previews were drawn with; cleared by rebuild_preview().
+    bool                      m_palette_changed = false;
+    // What the cache was built from.
+    std::vector<ColorRGBA>                                   m_palette_filaments;
+    std::vector<std::shared_ptr<std::vector<unsigned char>>> m_palette_images; // the colouring layers' images
+    std::optional<std::vector<PaletteEntry>>                 m_mix_ranking;    // rank_mixes(), computed on demand
+    bool                                                     m_palette_mixing     = false;
+    int                                                      m_palette_mix_count  = 0;
+    int                                                      m_palette_free_slots = 0;
+    std::vector<std::string>                                 m_palette_slots;  // the project's mixed slots
 
-    // The loaded filaments, clamped to the sixteen mmu_segmentation_facets can address.
+    // The loaded physical filaments, clamped to the states mmu_segmentation_facets can address.
     static std::vector<ColorRGBA> filament_palette();
-    // The Z band height, in mm. One print layer is the ideal, but the interleave is realised per
-    // *facet*: a band thinner than the mesh can resolve does not dither, it beats against the triangle
-    // grid and comes out as broad horizontal stripes - and since MMU segmentation reads facet colour,
-    // it does so in the print too, not only on screen. The refinement edge is chosen from the model's
-    // diagonal and knows nothing about the layer height, so the band is rounded up to a whole number of
-    // layers at least two facet rows tall: still exact on the printer, and representable by the mesh
-    // that has to carry it. Used by both the bake settings and the preview shader, so the two agree.
 
-    // The Normal preview's triangles, grouped by the filament they will print in. Colour is per facet
-    // and there are at most sixteen filaments, so the mesh is uploaded once with its index buffer
+    // The Normal preview's triangles, grouped by the palette entry they will print in. Colour is per facet
+    // and the palette is small, so the mesh is uploaded once with its index buffer
     // sorted by colour and drawn as one GLModel::render(range) per group - which needs no per-vertex
     // colour attribute, and so no change to GLModel's vertex layouts.
     //
@@ -143,11 +177,28 @@ public:
         ColorRGBA                 color;
     };
     std::vector<PreviewColorRun> m_preview_color_runs;
-    // True if any of the volume's layers would actually colour something: colour turned on, and a
-    // texture that has colour to give. What decides whether a palette is captured into a job at all,
-    // and so whether the colour criterion and the mmu write ever run.
+    // True if the layer would actually colour something: colour turned on, and a texture that has colour
+    // to give.
+    static bool layer_shows_color(const TextureDisplacementLayer &layer);
+    // True if any of the volume's layers would. What decides whether a palette is captured into a job at
+    // all, and so whether the colour criterion and the mmu write ever run.
     static bool any_layer_colors(const ModelVolume &mv);
 
+    // The model's own colour paint (mmu_segmentation_facets) as the gizmo draws it over its surface: the
+    // sub-triangles painted in a filament, grouped by that filament. NONE - the volume's own filament - is
+    // left out, so those triangles keep the gizmo's neutral, as they do in the preview.
+    struct PaintedColors
+    {
+        indexed_triangle_set facets; // over the paint's whole vertex array
+        std::vector<int>     source; // per triangle of `facets`: the model triangle it lies in
+        std::vector<int>     state;  // per triangle of `facets`: its filament state, 1-based
+
+        // The triangles of `facets` outside the model triangles `excluded` marks, in order. A model
+        // triangle past the end of `excluded` is not excluded.
+        std::vector<size_t> outside(const std::vector<bool> &excluded) const;
+    };
+    static PaintedColors painted_colors(const TriangleMesh &mesh, const TriangleSelector::TriangleSplittingData &paint);
+
     void render_painter_gizmo() override;
 
     // Intercepts mouse input while "Adjust Texture" mode is on (dragging the on-canvas offset/
@@ -157,6 +208,9 @@ public:
 protected:
     void        on_render_input_window(float x, float y, float bottom_limit) override;
     std::string on_get_name() const override;
+    // Never in the assemble view: its toolbar does not offer this gizmo, and every preview here is drawn
+    // with the main canvas's instance transform. The base alone would let the keyboard shortcut open it there.
+    bool        on_is_activable() const override;
 
     wxString handle_snapshot_action_name(bool shift_down, Button button_down) const override;
 
@@ -676,12 +730,13 @@ private:
     GLModel m_shaded_preview_glmodel;
 
     // Translucent tint over the active layer's painted triangles, drawn on top of whichever preview
-    // is showing. The base painter's own opaque paint highlight (render_triangles()) cannot be used
-    // in either preview mode - it is coincident with the surface and simply covers it - so the only
-    // paint feedback the gizmo had was the relief itself, which meant erasing showed nothing at all
-    // until the stroke ended and the whole preview rebuilt. This is that feedback: cheap (the painted
-    // patch only), translucent (the preview stays visible through it) and rebuilt live during a
-    // stroke.
+    // is showing - except, between strokes, the active layer's own colour preview, which it would wash
+    // green (see render_painter_gizmo()). The base painter's own opaque paint highlight
+    // (render_triangles()) cannot be used in either preview mode - it is coincident with the surface
+    // and simply covers it - so the only paint feedback the gizmo had was the relief itself, which
+    // meant erasing showed nothing at all until the stroke ended and the whole preview rebuilt. This
+    // is that feedback: cheap (the painted patch only), translucent (the preview stays visible through
+    // it) and rebuilt live during a stroke.
     GLModel m_paint_overlay_glmodel;
     // The islands selected in the UV editor, tinted on the model so the pane's selection can be seen
     // in place. Rebuilt whenever the pane's selection differs from the one it was built for.
@@ -699,6 +754,23 @@ private:
     GLModel     m_other_paint_glmodel;
     std::string m_other_paint_key;
     void        rebuild_other_paint_overlay();
+    // The model's colour paint, drawn over the surface so the colours a bake wrote stay visible - the
+    // canvas draws no volume while a paint gizmo is open, and the selectors hold only displacement paint.
+    // Left out wherever the preview on screen shows paint of its own (`whole_stack`: every layer's, as the
+    // Normal preview does; otherwise the active layer's), since an opaque overlay there would hide that
+    // preview. Only while a layer colours: it is the colour workflow's result, and every other paint gizmo
+    // shows the model neutral.
+    //
+    // Two levels: the paint's sub-triangles, which take a selector over the whole mesh and change only with
+    // the paint itself, and the part drawn, which follows every flushed stroke.
+    PaintedColors m_painted_colors;
+    std::string   m_painted_colors_key;
+    GLModel       m_painted_colors_glmodel;
+    std::string   m_painted_colors_drawn_key;
+    std::vector<std::pair<int, std::pair<size_t, size_t>>> m_painted_colors_runs; // filament state, index range
+    void          rebuild_painted_colors(bool whole_stack);
+    // False when there was nothing to draw.
+    bool          render_painted_colors(bool whole_stack);
     // Whether render_shaded_preview_mesh() would actually draw something. Checked before the real volume
     // is hidden: with no layer, no texture or no shader the shaded path draws nothing, and hiding the
     // volume for it left the model invisible.
@@ -712,11 +784,9 @@ private:
     int   m_shaded_projection_mode = 0;
     Vec3f m_shaded_patch_center    = Vec3f::Zero();
     Vec3f m_shaded_patch_axis      = Vec3f::UnitZ();
-    // The palette the fast preview's per-triangle filament indices were built against, captured when
-    // the mesh was. Empty when the active layer is not colouring, which is what tells the shader to
-    // fall back to the model's own colour. Held rather than re-read at draw time so the indices baked
-    // into the mesh can never be resolved against a different set of filaments than they were computed
-    // from - loading a filament mid-session would otherwise recolour a stale preview at random.
+    // The palette the fast preview matches each fragment against, captured with its mesh. Empty when the
+    // active layer is not colouring, which is what tells the shader to fall back to the model's own
+    // colour. Every entry carries the colour it prints in, so drawing it needs nothing else.
     std::vector<PaletteEntry> m_shaded_preview_palette;
 
     // GPU island drag: while an island is dragged in the UV editor, the displacement mesh is baked once (with

src/slic3r/GUI/Jobs/TextureDisplacementBakeJob.cpp

@@ -4,6 +4,7 @@
 #include <functional>
 #include <utility>
 #include <string>
+#include <vector>
 #include "libslic3r/TextureDisplacement.hpp"
 #include <exception>
 #include <cstddef>
@@ -114,6 +115,17 @@ void TextureDisplacementBakeJob::finalize(bool canceled, std::exception_ptr &ept
         if (volume == nullptr)
             return;
 
+        // The filament each palette entry prints in. This is where a mix becomes a mixed filament slot,
+        // and only a mix the bake actually painted with: the preview never creates one, so the project
+        // gains only the slots this result needs. Done before anything below names them - adding a slot
+        // runs ModelVolume::update_extruder_count(), which clamps paint above the old filament count.
+        Sidebar &sidebar = plater->sidebar();
+        const std::vector<int> filament_of = GLGizmoTextureDisplacement::palette_filaments(
+            m_input.color.palette, m_triangle_color, [&sidebar](const PrintableColor &mix) {
+                return sidebar.ensure_mixed_filament({ unsigned(mix.a + 1), unsigned(mix.b + 1) },
+                                                     { mix.a_percent(), 100 - mix.a_percent() });
+            });
+
         volume->set_mesh(std::move(m_result));
         volume->set_new_unique_id();
         volume->calculate_convex_hull();
@@ -129,9 +141,11 @@ void TextureDisplacementBakeJob::finalize(bool canceled, std::exception_ptr &ept
             const TriangleSelector::TriangleSplittingData &existing = volume->mmu_segmentation_facets.get_data();
             if (!existing.bitstream.empty())
                 selector.deserialize(existing, false);
-            for (size_t i = 0; i < m_triangle_color.size(); ++i)
-                if (m_triangle_color[i] > 0)
-                    selector.set_facet(int(i), EnforcerBlockerType(m_triangle_color[i]));
+            for (size_t i = 0; i < m_triangle_color.size(); ++i) {
+                const size_t entry = size_t(m_triangle_color[i]);
+                if (entry > 0 && entry <= filament_of.size() && filament_of[entry - 1] >= 0)
+                    selector.set_facet(int(i), EnforcerBlockerType(filament_of[entry - 1] + 1));
+            }
             volume->mmu_segmentation_facets.set(selector);
         }
 

src/slic3r/GUI/Jobs/TextureDisplacementBakeJob.hpp

@@ -56,8 +56,9 @@ private:
     TriangleMesh                 m_result;
     // What the bake spent, for the message it leaves behind when the budget capped the detail.
     TextureBakeStats m_stats;
-    // Per triangle of m_result: the filament to print it in, as an EnforcerBlockerType value
-    // (0 = leave alone). Empty unless a layer asked for colour. See TextureColorRequest.
+    // Per triangle of m_result: the palette entry to print it in, as its index + 1 (0 = leave alone).
+    // Empty unless a layer asked for colour. See TextureColorRequest; finalize() turns these into
+    // filaments.
     std::vector<uint8_t>         m_triangle_color;
     std::function<void()>        m_on_finished;
 };

src/slic3r/GUI/Jobs/TextureDisplacementDebugJob.cpp

@@ -59,7 +59,7 @@ void TextureDisplacementDebugJob::process(Ctl &ctl)
     if (m_input.run_prepare && !m_input.options.pipeline_v2) {
         const TextureDisplacementPrepareResult prepared =
             GLGizmoTextureDisplacement::prepare_mesh(mesh, masks, m_input.layers, m_input.prepare_params,
-                                                     m_input.color.palette,
+                                                     m_input.color,
                                                      // Preparation is roughly half the run; the bake
                                                      // takes the progress bar from there.
                                                      [&report](int pct) { return report(1 + pct / 2); },

src/slic3r/GUI/Jobs/TextureDisplacementPrepareJob.cpp

@@ -46,7 +46,7 @@ void TextureDisplacementPrepareJob::process(Ctl &ctl)
     // idle loop.
     int last_reported = 1;
     m_result = GLGizmoTextureDisplacement::prepare_mesh(m_input.base_mesh, m_input.masks, m_input.layers,
-                                                        m_input.params, m_input.color.palette,
+                                                        m_input.params, m_input.color,
                                                         [&ctl, &status, &last_reported](int percent) {
                                                             if (ctl.was_canceled())
                                                                 return false;

src/slic3r/GUI/Jobs/TextureDisplacementPreviewJob.hpp

@@ -26,13 +26,13 @@ struct TextureDisplacementPreviewInput
     // Mesh coordinates -> world millimetres, so the preview is displaced in the same space the bake
     // is and the two cannot disagree. See build_texture_displacement().
     Transform3d                           volume_to_world = Transform3d::Identity();
-    // Empty unless a layer is colouring, in which case the preview reports the filament per triangle
-    // alongside the mesh, so the Normal view shows what the bake will produce - interleaving included.
+    // Empty unless a layer is colouring, in which case the preview reports the palette entry per
+    // triangle alongside the mesh, so the Normal view shows the colours the bake will produce.
     TextureColorSettings                  color;
 };
 
-// A preview result: the displaced mesh, and - when the input carried a palette - one filament index
-// per triangle (an EnforcerBlockerType value; 0 means "no colour from the texture").
+// A preview result: the displaced mesh, and - when the input carried a palette - one palette entry per
+// triangle (its index + 1; 0 means "no colour from the texture").
 struct TextureDisplacementPreviewResult
 {
     indexed_triangle_set  mesh;

src/slic3r/GUI/Plater.cpp

@@ -5048,35 +5048,15 @@ static bool create_mixed_filament_from_result(
         is_mixed_opt->values[new_idx] = true;
     }
 
-    std::string comp_str;
-    for (size_t i = 0; i < result.components.size(); ++i) {
-        if (i > 0) comp_str += ",";
-        comp_str += std::to_string(result.components[i]);
-    }
     {
         auto* comp_opt = project_config.option<ConfigOptionStrings>("filament_mixed_components");
         while (comp_opt->values.size() <= new_idx) comp_opt->values.push_back(std::string{});
-        comp_opt->values[new_idx] = comp_str;
-    }
-
-    int ratio_sum = 0;
-    for (int r : result.ratios) ratio_sum += r;
-    if (ratio_sum <= 0) ratio_sum = 100;
-
-    std::string ratio_str;
-    {
-        CNumericLocalesSetter c_locale_setter;
-        for (size_t i = 0; i < result.ratios.size(); ++i) {
-            if (i > 0) ratio_str += ",";
-            char buf[32];
-            std::snprintf(buf, sizeof(buf), "%.4f", (float)result.ratios[i] / ratio_sum);
-            ratio_str += buf;
-        }
+        comp_opt->values[new_idx] = format_mixed_components(result.components);
     }
     {
         auto* ratios_opt = project_config.option<ConfigOptionStrings>("filament_mixed_sublayer_ratios");
         while (ratios_opt->values.size() <= new_idx) ratios_opt->values.push_back(std::string{});
-        ratios_opt->values[new_idx] = ratio_str;
+        ratios_opt->values[new_idx] = format_mixed_ratios(result.ratios);
     }
 
     if (!project_config.option("filament_mixed_gradient"))
@@ -5136,36 +5116,12 @@ int Sidebar::ensure_mixed_filament(const std::vector<unsigned int> &components,
         return -1;
     if (p->combos_filament.size() < 2)
         return -1;
-
-    // Normalise the way create_mixed_filament_from_result() stores them, so the comparison below sees
-    // the same text the config holds rather than two spellings of one blend.
-    int ratio_sum = 0;
-    for (const int r : ratios)
-        ratio_sum += r;
-    if (ratio_sum <= 0)
+    if (std::accumulate(ratios.begin(), ratios.end(), 0) <= 0)
         return -1;
 
-    std::string comp_str, ratio_str;
-    {
-        CNumericLocalesSetter c_locale_setter;
-        for (size_t i = 0; i < components.size(); ++i) {
-            if (i > 0) { comp_str += ","; ratio_str += ","; }
-            comp_str += std::to_string(components[i]);
-            char buf[32];
-            std::snprintf(buf, sizeof(buf), "%.4f", float(ratios[i]) / float(ratio_sum));
-            ratio_str += buf;
-        }
-    }
-
-    const auto &project_config = wxGetApp().preset_bundle->project_config;
-    const auto *is_mixed_opt   = project_config.option<ConfigOptionBools>("filament_is_mixed");
-    const auto *comp_opt       = project_config.option<ConfigOptionStrings>("filament_mixed_components");
-    const auto *ratios_opt     = project_config.option<ConfigOptionStrings>("filament_mixed_sublayer_ratios");
-    if (is_mixed_opt != nullptr && comp_opt != nullptr && ratios_opt != nullptr)
-        for (size_t i = 0; i < is_mixed_opt->values.size(); ++i)
-            if (is_mixed_opt->values[i] && i < comp_opt->values.size() && i < ratios_opt->values.size() &&
-                comp_opt->values[i] == comp_str && ratios_opt->values[i] == ratio_str)
-                return int(i);
+    if (const int existing = find_fixed_mixed_filament(wxGetApp().preset_bundle->project_config, components, ratios);
+        existing >= 0)
+        return existing;
 
     if (wxGetApp().preset_bundle->filament_presets.size() >= size_t(EnforcerBlockerType::ExtruderMax))
         return -1;

src/slic3r/GUI/Plater.hpp

@@ -292,11 +292,12 @@ public:
     // Mixed-color filament sidebar section
     void add_mixed_filament();
     // The filament slot that blends `components` (1-based physical filament indices) in `ratios`
-    // (percentages), creating it when no existing mixed slot already describes that blend. Returns the
-    // 0-based filament index, or -1 when the paint-state cap leaves no room for another one.
+    // (percentages) at a fixed ratio, creating it when no existing fixed mixed slot already describes
+    // that blend (see find_fixed_mixed_filament()). Returns the 0-based filament index, or -1 when the
+    // paint-state cap leaves no room for another one.
     //
     // Exists so a feature that needs a blend can ask for one without going through the modal dialog:
-    // the texture displacement gizmo turns each mix in its palette into a slot, which is what moves the
+    // a texture displacement bake turns each mix it painted with into a slot, which is what moves the
     // interleaving from its own paint mask to the slicer, where it happens per layer.
     int ensure_mixed_filament(const std::vector<unsigned int> &components, const std::vector<int> &ratios);
     void edit_mixed_filament(size_t idx);

tests/libslic3r/CMakeLists.txt

@@ -36,7 +36,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_png_read_write.cpp

tests/libslic3r/test_clipper_utils.cpp

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

tests/libslic3r/test_filament_mixer.cpp

@@ -255,3 +255,39 @@ TEST_CASE("blend_color_multi weights components", "[FilamentMixer]")
             REQUIRE(std::abs(comp(mixed, i) - comp("#123456", i)) <= 8);
     }
 }
+
+TEST_CASE("format_mixed_ratios normalises weights to four decimals", "[FilamentMixer]")
+{
+    REQUIRE(format_mixed_components({1, 3}) == "1,3");
+    REQUIRE(format_mixed_ratios({50, 50}) == "0.5000,0.5000");
+    REQUIRE(format_mixed_ratios({1, 2}) == "0.3333,0.6667");
+    REQUIRE(format_mixed_ratios({1, 1}) == format_mixed_ratios({50, 50}));
+}
+
+TEST_CASE("find_fixed_mixed_filament reuses only a fixed slot of the same blend", "[FilamentMixer]")
+{
+    // Physical slots 0 and 1; slot 2 blends them 50:50 as a gradient, slot 3 at a fixed 50:50.
+    DynamicPrintConfig cfg;
+    cfg.set_key_value("filament_is_mixed", new ConfigOptionBools({false, false, true, true}));
+    cfg.set_key_value("filament_mixed_components", new ConfigOptionStrings({"", "", "1,2", "1,2"}));
+    cfg.set_key_value("filament_mixed_sublayer_ratios",
+                      new ConfigOptionStrings({"", "", format_mixed_ratios({50, 50}), format_mixed_ratios({50, 50})}));
+    cfg.set_key_value("filament_mixed_gradient", new ConfigOptionBools({false, false, true, false}));
+
+    SECTION("The fixed slot is found, whatever scale the weights are given at") {
+        REQUIRE(find_fixed_mixed_filament(cfg, {1, 2}, {50, 50}) == 3);
+        REQUIRE(find_fixed_mixed_filament(cfg, {1, 2}, {1, 1}) == 3);
+    }
+    SECTION("A gradient slot with the same components and ratios is not a match") {
+        cfg.option<ConfigOptionBools>("filament_is_mixed")->values[3] = false;
+        REQUIRE(find_fixed_mixed_filament(cfg, {1, 2}, {50, 50}) == -1);
+    }
+    SECTION("A project without the gradient key still matches its fixed slots") {
+        cfg.erase("filament_mixed_gradient");
+        REQUIRE(find_fixed_mixed_filament(cfg, {1, 2}, {50, 50}) == 2);
+    }
+    SECTION("Another ratio or another component order is a different blend") {
+        REQUIRE(find_fixed_mixed_filament(cfg, {1, 2}, {1, 2}) == -1);
+        REQUIRE(find_fixed_mixed_filament(cfg, {2, 1}, {50, 50}) == -1);
+    }
+}

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_texture_displacement.cpp

@@ -68,6 +68,28 @@ static std::shared_ptr<std::vector<unsigned char>> make_flat_gray_png(uint8_t va
     return std::make_shared<std::vector<unsigned char>>(std::move(bytes));
 }
 
+// The same round trip for a flat colour image, which decode_height_texture() reads through its colour path.
+static std::shared_ptr<std::vector<unsigned char>> make_flat_rgb_png(uint8_t r, uint8_t g, uint8_t b, size_t w = 4, size_t h = 4)
+{
+    std::vector<uint8_t> rgb;
+    for (size_t i = 0; i < w * h; ++i)
+        rgb.insert(rgb.end(), { r, g, b });
+    const boost::filesystem::path tmp_path = boost::filesystem::temp_directory_path()
+        / boost::filesystem::unique_path("texdisp_test_%%%%%%%%.png");
+    REQUIRE(Slic3r::png::write_rgb_to_file(tmp_path.string(), w, h, rgb));
+
+    std::vector<unsigned char> bytes;
+    {
+        std::ifstream ifs(tmp_path.string(), std::ios::binary);
+        bytes.assign(std::istreambuf_iterator<char>(ifs), std::istreambuf_iterator<char>());
+    }
+    boost::system::error_code ec;
+    boost::filesystem::remove(tmp_path, ec);
+
+    REQUIRE_FALSE(bytes.empty());
+    return std::make_shared<std::vector<unsigned char>>(std::move(bytes));
+}
+
 // A hard-edged black/white checkerboard, the worst case for a height map: every texel boundary is a
 // step, which is precisely the relief the post-process smoothing exists to round off.
 static std::shared_ptr<std::vector<unsigned char>> make_checkerboard_png(size_t w = 16, size_t h = 16)
@@ -2135,3 +2157,20 @@ TEST_CASE("A second bake beside a first comes out as fine as a single bake", "[T
     CHECK(second <= single * 5 / 4);
 }
 
+TEST_CASE("whether a layer's texture has colour agrees with its decode", "[TextureDisplacement]")
+{
+    TextureDisplacementLayer gray;
+    gray.image_data = make_flat_gray_png(128);
+    CHECK_FALSE(height_texture_has_color(gray));
+
+    TextureDisplacementLayer color;
+    color.image_data = make_flat_rgb_png(200, 40, 10);
+    // Before the image is decoded and after, and whatever the smoothing.
+    CHECK(height_texture_has_color(color));
+    CHECK(decode_height_texture(color).has_color());
+    CHECK(height_texture_has_color(color));
+    color.smoothing = 0.5f;
+    CHECK(height_texture_has_color(color));
+
+    CHECK_FALSE(height_texture_has_color(TextureDisplacementLayer{}));
+}

tests/slic3rutils/CMakeLists.txt

@@ -36,6 +36,7 @@ add_executable(${_TEST_NAME}_tests
     test_plugin_audit.cpp
     test_plugin_json_depth.cpp
     test_shortcuts.cpp
+    test_texture_color_palette.cpp
     test_file_url.cpp
     test_user_manager.cpp
     ../fff_print/test_helpers.cpp

tests/slic3rutils/test_texture_color_palette.cpp

@@ -0,0 +1,294 @@
+// The texture displacement gizmo's palette helpers live in libslic3r_gui; this is the suite that links it.
+// Same Windows include prologue as test_filament_bitmap_utils.cpp (wx pulls in <windows.h>; keep
+// WIN32_LEAN_AND_MEAN / NOMINMAX ahead of the Catch2 headers).
+#ifdef WIN32
+    #ifndef WIN32_LEAN_AND_MEAN
+        #define WIN32_LEAN_AND_MEAN
+    #endif
+    #ifndef NOMINMAX
+        #define NOMINMAX
+    #endif
+    #include <Windows.h>
+#endif
+
+#include <cstddef>
+#include <cstdint>
+#include <fstream>
+#include <ios>
+#include <iterator>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <catch2/catch_all.hpp>
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/matchers/catch_matchers.hpp>
+#include <catch2/matchers/catch_matchers_floating_point.hpp>
+
+#include "libslic3r/Color.hpp"
+#include "libslic3r/FilamentMixer.hpp"
+#include "libslic3r/PNGReadWrite.hpp"
+#include "libslic3r/Point.hpp"
+#include "libslic3r/TextureDisplacement.hpp"
+#include "libslic3r/TriangleMesh.hpp"
+#include "libslic3r/TriangleSelector.hpp"
+#include "slic3r/GUI/Gizmos/GLGizmoTextureDisplacement.hpp"
+#include "slic3r/Utils/ColorSpaceConvert.hpp"
+#include "test_utils.hpp"
+
+using namespace Slic3r;
+using Catch::Matchers::WithinAbs;
+using Gizmo     = Slic3r::GUI::GLGizmoTextureDisplacement;
+using Entry     = Gizmo::PaletteEntry;
+using MixTarget = Gizmo::MixTarget;
+
+namespace {
+
+const ColorRGBA BLACK{ 0.f, 0.f, 0.f, 1.f };
+const ColorRGBA WHITE{ 1.f, 1.f, 1.f, 1.f };
+const ColorRGBA RED{ 1.f, 0.f, 0.f, 1.f };
+const ColorRGBA BLUE{ 0.f, 0.f, 1.f, 1.f };
+const ColorRGBA YELLOW{ 1.f, 1.f, 0.f, 1.f };
+
+MixTarget target(const Vec3f &rgb, float weight)
+{
+    MixTarget t;
+    RGB2Lab(rgb.x(), rgb.y(), rgb.z(), &t.lab.x(), &t.lab.y(), &t.lab.z());
+    t.weight = weight;
+    return t;
+}
+
+// The colour a mixed slot of these two filaments shows, as the sidebar computes it.
+Vec3f slot_color(const ColorRGBA &a, const ColorRGBA &b, int a_percent)
+{
+    ColorRGB c;
+    REQUIRE(decode_color(blend_color_multi({ encode_color(a), encode_color(b) }, { a_percent, 100 - a_percent }), c));
+    return Vec3f(c.r(), c.g(), c.b());
+}
+
+// A colour image layer, through Slic3r's own PNG writer so decode_height_texture() reads it the way it
+// reads an imported texture.
+TextureDisplacementLayer color_layer(int w, int h, const std::vector<uint8_t> &rgb)
+{
+    ScopedTemporaryFile png(".png");
+    REQUIRE(png::write_rgb_to_file(png.string(), size_t(w), size_t(h), rgb));
+    std::ifstream              in(png.string(), std::ios::binary);
+    std::vector<unsigned char> bytes{ std::istreambuf_iterator<char>(in), std::istreambuf_iterator<char>() };
+    REQUIRE_FALSE(bytes.empty());
+
+    TextureDisplacementLayer layer;
+    layer.image_data    = std::make_shared<std::vector<unsigned char>>(std::move(bytes));
+    layer.color_enabled = true;
+    return layer;
+}
+
+// A red/green ramp over a fixed blue: colours spread over many bins, so the image is not flat-colour.
+TextureDisplacementLayer gradient_layer()
+{
+    const int            n = 64;
+    std::vector<uint8_t> rgb;
+    for (int y = 0; y < n; ++y)
+        for (int x = 0; x < n; ++x) {
+            rgb.push_back(uint8_t(x * 4));
+            rgb.push_back(uint8_t(y * 4));
+            rgb.push_back(128);
+        }
+    return color_layer(n, n, rgb);
+}
+
+// A 2048x1100 image, over mix_targets()' sampling budget, that is pure red wherever `red(x, y)` holds and
+// elsewhere a gradient spread over far more than eight coarse bins, so the image is not flat-colour.
+template<class RedFn> TextureDisplacementLayer striped_layer(RedFn red)
+{
+    const int            w = 2048, h = 1100;
+    std::vector<uint8_t> rgb;
+    rgb.reserve(size_t(w) * size_t(h) * 3);
+    for (int y = 0; y < h; ++y)
+        for (int x = 0; x < w; ++x) {
+            const bool is_red = red(x, y);
+            rgb.push_back(is_red ? 255 : uint8_t(x * 255 / w));
+            rgb.push_back(is_red ? 0 : uint8_t(y * 255 / h));
+            rgb.push_back(is_red ? 0 : 128);
+        }
+    return color_layer(w, h, rgb);
+}
+
+// How much of the targets' weight is pure red.
+float red_weight(const std::vector<MixTarget> &targets)
+{
+    Vec3f red;
+    RGB2Lab(1.f, 0.f, 0.f, &red.x(), &red.y(), &red.z());
+    float weight = 0.f;
+    for (const MixTarget &t : targets)
+        if ((t.lab - red).norm() < 3.f)
+            weight += t.weight;
+    return weight;
+}
+
+} // namespace
+
+TEST_CASE("mix targets cover each colouring photo layer once and skip the rest", "[TextureColorPalette][TextureDisplacement]")
+{
+    TextureDisplacementLayer photo = gradient_layer();
+
+    const std::vector<MixTarget> targets = Gizmo::mix_targets({ photo });
+    REQUIRE_FALSE(targets.empty());
+    float total = 0.f;
+    for (const MixTarget &t : targets)
+        total += t.weight;
+    REQUIRE_THAT(total, WithinAbs(1., 1e-4));
+
+    SECTION("A layer that does not colour gives no targets") {
+        photo.color_enabled = false;
+        REQUIRE(Gizmo::mix_targets({ photo }).empty());
+    }
+    SECTION("A flat-colour image prints in single filaments, so it gives no targets") {
+        const TextureDisplacementLayer flat = color_layer(8, 8, std::vector<uint8_t>(8 * 8 * 3, 200));
+        REQUIRE(Gizmo::mix_targets({ flat }).empty());
+    }
+}
+
+TEST_CASE("mix targets of a large image weigh each colour by its share, whatever its stripes", "[TextureColorPalette][TextureDisplacement]")
+{
+    // Sampled rather than read in full, these must not line up with the samples: a fixed sampling step
+    // sees only one phase of a stripe pattern, and a generator whose offsets repeat sees only some.
+    SECTION("Red on every other column") {
+        CHECK_THAT(red_weight(Gizmo::mix_targets({ striped_layer([](int x, int) { return x % 2 == 0; }) })),
+                   WithinAbs(1. / 2., 0.03));
+    }
+    SECTION("Red on every fourth column") {
+        CHECK_THAT(red_weight(Gizmo::mix_targets({ striped_layer([](int x, int) { return x % 4 == 0; }) })),
+                   WithinAbs(1. / 4., 0.03));
+    }
+    SECTION("Red on diagonals") {
+        CHECK_THAT(red_weight(Gizmo::mix_targets({ striped_layer([](int x, int y) { return (x - y) % 3 == 0; }) })),
+                   WithinAbs(1. / 3., 0.03));
+    }
+}
+
+TEST_CASE("the mix ranked first is the one the image needs most", "[TextureColorPalette][TextureDisplacement]")
+{
+    // The whole image is exactly the colour of a 1:1 black/white slot.
+    const std::vector<MixTarget> targets = { target(slot_color(BLACK, WHITE, 50), 1.f) };
+    const std::vector<Entry>     ranked  = Gizmo::rank_mixes({ BLACK, WHITE }, targets, 1);
+    REQUIRE(ranked.size() == 1);
+    CHECK(ranked.front().a == 0);
+    CHECK(ranked.front().b == 1);
+    CHECK(ranked.front().num * 2 == ranked.front().den);
+}
+
+TEST_CASE("an image the filaments already match ranks no mixes", "[TextureColorPalette][TextureDisplacement]")
+{
+    const std::vector<MixTarget> targets = { target(Vec3f(1.f, 0.f, 0.f), 0.5f), target(Vec3f(0.f, 0.f, 1.f), 0.5f) };
+    REQUIRE(Gizmo::rank_mixes({ RED, BLUE }, targets, 8).empty());
+}
+
+TEST_CASE("ranked mixes stay within the limit and show their slot's colour", "[TextureColorPalette][TextureDisplacement]")
+{
+    const std::vector<ColorRGBA> filaments = { RED, BLUE, YELLOW };
+    const std::vector<MixTarget> targets   = Gizmo::mix_targets({ gradient_layer() });
+
+    for (const int limit : { 1, 3 }) {
+        const std::vector<Entry> ranked = Gizmo::rank_mixes(filaments, targets, limit);
+        CHECK(int(ranked.size()) <= limit);
+        CHECK_FALSE(ranked.empty());
+    }
+
+    const std::vector<Entry> ranked = Gizmo::rank_mixes(filaments, targets, 6);
+    for (const Entry &e : ranked) {
+        REQUIRE(e.is_mix());
+        const Vec3f expected = slot_color(filaments[size_t(e.a)], filaments[size_t(e.b)], e.a_percent());
+        CHECK_THAT(e.rgb.x(), WithinAbs(expected.x(), 1e-6));
+        CHECK_THAT(e.rgb.y(), WithinAbs(expected.y(), 1e-6));
+        CHECK_THAT(e.rgb.z(), WithinAbs(expected.z(), 1e-6));
+    }
+}
+
+TEST_CASE("picked mixes never need more slots than the project has free", "[TextureColorPalette][TextureDisplacement]")
+{
+    const std::vector<Entry> ranking = { { Vec3f::Zero(), 0, 1, 1, 2 }, { Vec3f::Zero(), 0, 1, 1, 3 }, { Vec3f::Zero(), 0, 1, 2, 3 } };
+    const auto               reusable_second = [](const Entry &e) { return e.num == 1 && e.den == 3; };
+
+    SECTION("The count caps the pick") {
+        REQUIRE(Gizmo::pick_mixes(ranking, 2, 10, nullptr).size() == 2);
+    }
+    SECTION("With no free slot only a mix that already has one is kept") {
+        const std::vector<Entry> picked = Gizmo::pick_mixes(ranking, 3, 0, reusable_second);
+        REQUIRE(picked.size() == 1);
+        CHECK(picked.front().den == 3);
+        CHECK(picked.front().num == 1);
+    }
+    SECTION("A reusable mix costs no free slot") {
+        const std::vector<Entry> picked = Gizmo::pick_mixes(ranking, 3, 1, reusable_second);
+        REQUIRE(picked.size() == 2);
+        CHECK(picked[0].den == 2);
+        CHECK(picked[1].den == 3);
+    }
+}
+
+TEST_CASE("a baked mix paints the slot it was given, wherever that slot sits", "[TextureColorPalette][TextureDisplacement]")
+{
+    // Two filaments, then two mixes of them. Palette index 2 is a mix, but its slot need not be
+    // filament 2: a project that already holds other mixed slots puts it further along.
+    const std::vector<Entry> palette = Gizmo::make_palette({ BLACK, WHITE }, { { Vec3f::Zero(), 0, 1, 1, 2 }, { Vec3f::Zero(), 0, 1, 1, 3 } });
+    REQUIRE(palette.size() == 4);
+    // Filament 0, the 1:1 mix twice, nothing: the 1:2 mix is never used.
+    const std::vector<uint8_t> triangle_color = { 1, 3, 3, 0 };
+
+    std::vector<Entry> asked;
+    const auto         slot_seven = [&asked](const Entry &e) {
+        asked.push_back(e);
+        return 7;
+    };
+    const std::vector<int> filament = Gizmo::palette_filaments(palette, triangle_color, slot_seven);
+    REQUIRE(filament.size() == 4);
+    CHECK(filament[0] == 0);
+    CHECK(filament[1] == 1);
+    CHECK(filament[2] == 7);
+    CHECK(filament[3] == -1);
+    // Asking creates a slot, so an unused mix is never asked for.
+    REQUIRE(asked.size() == 1);
+    CHECK(asked.front().den == 2);
+
+    SECTION("A mix that gets no slot prints in its dominant component") {
+        const std::vector<int> fallback = Gizmo::palette_filaments(palette, { 3, 4 }, [](const Entry &) { return -1; });
+        CHECK(fallback[2] == 0); // 1:1 - the first component
+        CHECK(fallback[3] == 1); // 1 part black in 3 - white dominates
+    }
+}
+
+TEST_CASE("the model's colour paint is drawn by filament, and only where no layer paint covers it", "[TextureColorPalette][TextureDisplacement]")
+{
+    // A strip of four triangles: filament 2 on the first and last, filament 5 on the second, and the third
+    // left to the volume's own filament.
+    indexed_triangle_set strip;
+    strip.vertices = { Vec3f(0, 0, 0), Vec3f(1, 0, 0), Vec3f(0, 1, 0), Vec3f(1, 1, 0), Vec3f(0, 2, 0), Vec3f(1, 2, 0) };
+    strip.indices  = { stl_triangle_vertex_indices(0, 1, 2), stl_triangle_vertex_indices(1, 3, 2), stl_triangle_vertex_indices(2, 3, 4),
+                       stl_triangle_vertex_indices(3, 5, 4) };
+    const TriangleMesh mesh(strip);
+    TriangleSelector   paint(mesh);
+    paint.set_facet(0, EnforcerBlockerType(2));
+    paint.set_facet(1, EnforcerBlockerType(5));
+    paint.set_facet(3, EnforcerBlockerType(2));
+
+    const Gizmo::PaintedColors colors = Gizmo::painted_colors(mesh, paint.serialize());
+    // Grouped by filament; the triangle in the volume's own filament is never drawn.
+    REQUIRE(colors.facets.indices.size() == 3);
+    REQUIRE(colors.source.size() == 3);
+    REQUIRE(colors.state.size() == 3);
+    CHECK(colors.state == std::vector<int>{ 2, 2, 5 });
+    CHECK(colors.source == std::vector<int>{ 0, 3, 1 });
+
+    SECTION("A model triangle a layer's paint covers is left to the preview") {
+        std::vector<bool> excluded(mesh.its.indices.size(), false);
+        excluded[3] = true;
+        const std::vector<size_t> kept = colors.outside(excluded);
+        REQUIRE(kept.size() == 2);
+        CHECK(colors.source[kept[0]] == 0);
+        CHECK(colors.source[kept[1]] == 1);
+    }
+    SECTION("A mask shorter than the model leaves the rest drawn") {
+        CHECK(colors.outside({ true }).size() == 2);
+    }
+}