Make the connected-net layout affordable on a dense patch

Laying a patch out as a connected net cost ~175 ms on a 42k-triangle patch,
against ~21 ms for the unwrap it works from, and the gizmo asks for it on every
preview, overlay and bake. Measured on a real project the grid behind it ran
~19 million triangle-pair tests per net, nearly all of them misses: a cell
holds every triangle whose box touches it, and a candidate really meets a
couple of them.

Keep a bounding box with each stored triangle and answer those misses with four
comparisons instead of a full intersection. The net drops to ~53 ms with
identical output - the seam metrics on the test project did not move by one.

Two further attempts were measured and dropped, and are recorded in the comment
so they are not tried again: a free-space pre-check per chart came out slower,
because a folded chart lands against the net by construction and the cells
under it are occupied anyway, and splitting the boxes into their own array for
locality lost more to growing two vectors per bucket than it gained.

Also pick a pair's fold line from the longest boundary they share rather than
whichever edge came first, and grow the net strongest-adjacency-first rather
than breadth-first by area. Only the fold a chart is reached by comes out
matching, so a chart claimed across a short boundary leaves the long one it
shared with its true neighbour torn.

texture_unwrap_dump reports an unwrap from a saved project - charts, their
topology, folded triangles, where the texture is discontinuous and how long
those seams are. All of the above was found with it, and it is what keeps a
claim about this code honest; reading the 3D view and guessing had produced
three wrong diagnoses in a row.

src/dev-utils/CMakeLists.txt

@@ -28,6 +28,12 @@ if (ORCA_TOOLS)
     target_link_libraries(generate_system_cache libslic3r boost_headeronly)
     target_compile_definitions(generate_system_cache PRIVATE ${_DEV_DEFS})
 
+    # texture_unwrap_dump: reports the LSCM unwrap of a saved project's texture displacement layers,
+    # chart by chart, so a defect can be reproduced from the project file instead of from a screenshot.
+    add_executable(texture_unwrap_dump texture_unwrap_dump.cpp)
+    target_link_libraries(texture_unwrap_dump libslic3r boost_headeronly nanosvg)
+    target_compile_definitions(texture_unwrap_dump PRIVATE ${_DEV_DEFS})
+
     # profile_include_dump: prints what included templates contribute to a vendor's presets,
     # to diff against the same tool built in BambuStudio. Built only on request.
     add_executable(profile_include_dump EXCLUDE_FROM_ALL profile_include_dump.cpp)

src/dev-utils/texture_unwrap_dump.cpp

@@ -0,0 +1,292 @@
+// Diagnostic for the LSCM unwrap of a texture displacement layer.
+//
+// It exists because the defect it hunts only shows up on a real painted patch: the paint mask is built
+// by TriangleSelector splitting base triangles, so the patch topology cannot be written down by hand,
+// and reasoning about it from a screenshot of the 3D view had already produced three wrong diagnoses.
+// This loads a saved project, rebuilds exactly the patch the bake would act on, runs the same unwrap,
+// and reports what came out - per chart, so a bad one can be pointed at rather than guessed at.
+//
+//   texture_unwrap_dump <project.3mf>
+
+// nanosvg is header-only and libslic3r's 3mf import references it without carrying the implementation,
+// so every executable that links libslic3r has to supply it. Must precede any include that pulls the
+// header in, or its include guard suppresses the implementation. Same pattern as the other dev tools.
+#define NANOSVG_IMPLEMENTATION
+#include "nanosvg/nanosvg.h"
+#define NANOSVGRAST_IMPLEMENTATION
+#include "nanosvg/nanosvgrast.h"
+
+#include <chrono>
+#include <cstdio>
+#include <string>
+#include <functional>
+#include <unordered_map>
+#include <vector>
+
+#include "libslic3r/Model.hpp"
+#include "libslic3r/TextureDisplacement.hpp"
+#include "libslic3r/Format/bbs_3mf.hpp"
+#include "libslic3r/Utils.hpp"
+
+#include <boost/filesystem.hpp>
+
+using namespace Slic3r;
+
+namespace {
+
+uint64_t edge_key(int a, int b)
+{
+    if (a > b)
+        std::swap(a, b);
+    return (uint64_t(uint32_t(a)) << 32) | uint32_t(b);
+}
+
+// Boundary loops and the Euler characteristic of a face set, which together say whether a chart is the
+// topological disk LSCM needs (one loop, V - E + F == 1).
+void chart_topology(const indexed_triangle_set &mesh, const std::vector<int> &faces, int &loops, int &euler)
+{
+    std::unordered_map<uint64_t, int> edge_use;
+    std::unordered_map<int, int>      local;
+    for (const int f : faces) {
+        const stl_triangle_vertex_indices &t = mesh.indices[size_t(f)];
+        for (int i = 0; i < 3; ++i) {
+            ++edge_use[edge_key(t[i], t[(i + 1) % 3])];
+            local.emplace(t[i], int(local.size()));
+        }
+    }
+    euler = int(local.size()) - int(edge_use.size()) + int(faces.size());
+
+    std::unordered_map<int, int> parent;
+    const std::function<int(int)> find = [&](int x) {
+        while (parent[x] != x)
+            x = parent[x] = parent[parent[x]];
+        return x;
+    };
+    for (const auto &[key, uses] : edge_use)
+        if (uses == 1)
+            for (const int v : { int(key >> 32), int(uint32_t(key)) })
+                parent.emplace(v, v);
+    for (const auto &[key, uses] : edge_use)
+        if (uses == 1) {
+            const int a = find(int(key >> 32)), b = find(int(uint32_t(key)));
+            if (a != b)
+                parent[b] = a;
+        }
+    std::unordered_map<int, int> roots;
+    for (const auto &[v, p] : parent)
+        roots[find(v)] = 1;
+    loops = int(roots.size());
+}
+
+float signed_area_2d(const Vec2f &a, const Vec2f &b, const Vec2f &c)
+{
+    return 0.5f * ((b.x() - a.x()) * (c.y() - a.y()) - (c.x() - a.x()) * (b.y() - a.y()));
+}
+
+} // namespace
+
+int main(int argc, char **argv)
+{
+    if (argc < 2) {
+        std::printf("usage: texture_unwrap_dump <project.3mf>\n");
+        return 2;
+    }
+
+    Model                     model;
+    DynamicPrintConfig        config;
+    ConfigSubstitutionContext ctx(ForwardCompatibilitySubstitutionRule::Enable);
+    PlateDataPtrs             plate_data;
+    std::vector<Preset *>     project_presets;
+    bool                      is_bbl_3mf = false, is_orca_3mf = false;
+    Semver                    file_version;
+    // The importer writes a backup copy under the data dir and silently loses objects without one.
+    const boost::filesystem::path tmp = boost::filesystem::temp_directory_path() / "texture_unwrap_dump";
+    boost::filesystem::create_directories(tmp);
+    set_data_dir(tmp.string());
+
+    // LoadModel so the meshes come through; AddDefaultInstances because an object with no instance is
+    // dropped by the plate mapping, which is what "skip this object" in the log means.
+    if (!load_bbs_3mf(argv[1], &config, &ctx, &model, &plate_data, &project_presets, &is_bbl_3mf, &is_orca_3mf,
+                      &file_version, nullptr,
+                      LoadStrategy::LoadModel | LoadStrategy::LoadConfig | LoadStrategy::AddDefaultInstances |
+                          LoadStrategy::Silence)) {
+        std::printf("failed to load %s\n", argv[1]);
+        return 1;
+    }
+
+    std::printf("loaded: %zu object(s)\n", model.objects.size());
+
+    for (const ModelObject *object : model.objects)
+        for (const ModelVolume *volume : object->volumes) {
+            if (volume->texture_displacement_layers.empty()) {
+                std::printf("volume \"%s\": no texture displacement layers; paint masks per slot:",
+                            volume->name.c_str());
+                for (int i = 0; i < int(TEXTURE_DISPLACEMENT_MAX_LAYERS); ++i)
+                    std::printf(" %zu", volume->texture_displacement_facet(i).get_data().triangles_to_split.size());
+                std::printf("\n");
+                continue;
+            }
+            std::printf("volume \"%s\": %zu base triangles, %zu layer(s)\n", volume->name.c_str(),
+                        volume->mesh().its.indices.size(), volume->texture_displacement_layers.size());
+
+            for (const TextureDisplacementLayer &layer : volume->texture_displacement_layers) {
+                std::printf("\n  layer %d \"%s\"  mapping=%d  seam_angle=%.1f  connect=%d  islands_stored=%zu\n",
+                            layer.slot, layer.name.c_str(), int(layer.projection_method),
+                            layer.lscm_seam_angle_deg, int(layer.auto_connect_islands), layer.islands.size());
+                if (layer.projection_method != TextureProjectionMethod::LSCM)
+                    continue;
+
+                const indexed_triangle_set patch =
+                    extract_painted_patch(volume->mesh().its, volume->texture_displacement_facet(layer.slot).get_data());
+                std::printf("  patch: %zu vertices, %zu triangles\n", patch.vertices.size(), patch.indices.size());
+                if (patch.indices.empty())
+                    continue;
+
+                const auto t0 = std::chrono::steady_clock::now();
+                const PatchUnwrap unwrap = compute_patch_unwrap(patch, layer.lscm_seam_angle_deg, 0.f,
+                                                                layer.lscm_seam_edges);
+                const auto t1 = std::chrono::steady_clock::now();
+                std::printf("  TIMING compute_patch_unwrap: %.0f ms\n",
+                            std::chrono::duration<double, std::milli>(t1 - t0).count());
+                std::printf("  unwrap: %d charts, %zu unwrapped triangles\n", unwrap.chart_count,
+                            unwrap.indices.size());
+
+                // Group the patch's faces by chart so each can be examined on its own.
+                std::vector<std::vector<int>> chart_faces(size_t(std::max(unwrap.chart_count, 0)));
+                for (size_t i = 0; i < unwrap.indices.size(); ++i) {
+                    const int chart = unwrap.vertex_chart[size_t(unwrap.indices[i][0])];
+                    if (chart >= 0 && size_t(chart) < chart_faces.size())
+                        chart_faces[size_t(chart)].push_back(unwrap.source_face[i]);
+                }
+
+                int bad_charts = 0;
+                for (size_t c = 0; c < chart_faces.size(); ++c) {
+                    int loops = 0, euler = 0;
+                    chart_topology(patch, chart_faces[c], loops, euler);
+
+                    // Flipped triangles: the unwrap folded over itself, which is what a planar fallback
+                    // does to a chart that is not flat. Measured on the unwrap's own triangles.
+                    int pos = 0, neg = 0;
+                    for (size_t i = 0; i < unwrap.indices.size(); ++i) {
+                        const stl_triangle_vertex_indices &t = unwrap.indices[i];
+                        if (unwrap.vertex_chart[size_t(t[0])] != int(c))
+                            continue;
+                        const float a = signed_area_2d(unwrap.uvs[size_t(t[0])], unwrap.uvs[size_t(t[1])],
+                                                       unwrap.uvs[size_t(t[2])]);
+                        if (a > 0.f) ++pos; else if (a < 0.f) ++neg;
+                    }
+                    const int flipped = std::min(pos, neg);
+                    const bool disk   = loops == 1 && euler == 1;
+                    if (!disk || flipped > 0) {
+                        ++bad_charts;
+                        std::printf("    chart %2zu: %4zu faces  loops=%d euler=%d%s  flipped=%d/%d%s\n", c,
+                                    chart_faces[c].size(), loops, euler, disk ? "" : "  NOT A DISK", flipped,
+                                    pos + neg, flipped ? "  FOLDED" : "");
+                    }
+                }
+                std::printf("  charts with a defect: %d / %d\n", bad_charts, unwrap.chart_count);
+
+                // What the eye actually sees. Every patch edge shared by two charts should carry the same
+                // UV on both sides once the islands are laid out as a connected net; where it does not,
+                // the texture jumps across that seam. Measured through compute_lscm_uvs(), i.e. the exact
+                // coordinates the bake and the checker overlay sample.
+                {
+                    const auto n0 = std::chrono::steady_clock::now();
+                    const std::vector<TextureIsland> net = compute_connected_net(unwrap);
+                    const auto n1 = std::chrono::steady_clock::now();
+                    std::printf("  TIMING compute_connected_net: %.0f ms (%zu islands)\n",
+                                std::chrono::duration<double, std::milli>(n1 - n0).count(), net.size());
+                }
+                const auto t2 = std::chrono::steady_clock::now();
+                const std::vector<Vec2f> uv = compute_lscm_uvs(patch, layer);
+                const auto t3 = std::chrono::steady_clock::now();
+                std::printf("  TIMING compute_lscm_uvs:     %.0f ms  (called on every preview, overlay and bake)\n",
+                            std::chrono::duration<double, std::milli>(t3 - t2).count());
+                if (uv.size() != patch.vertices.size()) {
+                    std::printf("  compute_lscm_uvs returned %zu uvs for %zu vertices\n", uv.size(),
+                                patch.vertices.size());
+                    continue;
+                }
+                // Per-corner UVs carry each chart's own placement, so an edge shared by two charts shows
+                // the jump directly: the same mesh vertex lands at two different UVs. That is exactly what
+                // the eye reads as the texture breaking.
+                const auto t4 = std::chrono::steady_clock::now();
+                const std::vector<Vec2f> corner = compute_lscm_corner_uvs(patch, layer);
+                const auto t5 = std::chrono::steady_clock::now();
+                std::printf("  TIMING compute_lscm_corner_uvs: %.0f ms\n",
+                            std::chrono::duration<double, std::milli>(t5 - t4).count());
+                // Keyed by edge, holding the UV each incident face gives to the edge's *lower-numbered*
+                // endpoint. Comparing that same vertex on both sides is the point: indexing by corner
+                // position instead compares opposite ends of the edge, because the two faces wind it in
+                // opposite directions.
+                std::unordered_map<uint64_t, std::vector<Vec2f>> edge_seen;
+                if (corner.size() == patch.indices.size() * 3)
+                    for (size_t f = 0; f < patch.indices.size(); ++f) {
+                        const stl_triangle_vertex_indices &t = patch.indices[f];
+                        for (int k = 0; k < 3; ++k) {
+                            const int a = t[k], b = t[(k + 1) % 3];
+                            const int probe = std::min(a, b);
+                            const int local = (a == probe) ? k : (k + 1) % 3;
+                            edge_seen[edge_key(a, b)].push_back(corner[f * 3 + size_t(local)]);
+                        }
+                    }
+                // Which chart each patch face belongs to, so a broken edge can be attributed to a pair.
+                std::vector<int> chart_of_face(patch.indices.size(), -1);
+                for (size_t i = 0; i < unwrap.indices.size(); ++i)
+                    chart_of_face[size_t(unwrap.source_face[i])] = unwrap.vertex_chart[size_t(unwrap.indices[i][0])];
+
+                std::unordered_map<uint64_t, std::vector<int>> edge_faces;
+                for (size_t f = 0; f < patch.indices.size(); ++f) {
+                    const stl_triangle_vertex_indices &t = patch.indices[f];
+                    for (int k = 0; k < 3; ++k)
+                        edge_faces[edge_key(t[k], t[(k + 1) % 3])].push_back(int(f));
+                }
+
+                int adjacent = 0, broken = 0, broken_same_chart = 0;
+                float worst = 0.f;
+                std::map<std::pair<int, int>, std::pair<int, float>> by_pair;
+                for (const auto &[key, seen] : edge_seen) {
+                    if (seen.size() != 2)
+                        continue;
+                    ++adjacent;
+                    const float d = (seen[0] - seen[1]).norm();
+                    if (d <= 1e-4f)
+                        continue;
+                    ++broken;
+                    worst = std::max(worst, d);
+                    const auto &faces_here = edge_faces[key];
+                    int c1 = -1, c2 = -1;
+                    if (faces_here.size() == 2) {
+                        c1 = chart_of_face[size_t(faces_here[0])];
+                        c2 = chart_of_face[size_t(faces_here[1])];
+                    }
+                    if (c1 == c2)
+                        ++broken_same_chart;
+                    auto &slot = by_pair[{ std::min(c1, c2), std::max(c1, c2) }];
+                    ++slot.first;
+                    slot.second = std::max(slot.second, d);
+                }
+                std::printf("  broken edges inside a single chart: %d\n", broken_same_chart);
+                std::printf("  broken by chart pair:");
+                for (const auto &[pk, v] : by_pair)
+                    std::printf(" (%d,%d)x%d/%.1f", pk.first, pk.second, v.first, v.second);
+                std::printf("\n");
+                // Total length of the seams left broken, in mm: how much visibly torn edge the layout has,
+                // which is what the eye adds up. A count alone hides whether the breaks are hairlines or
+                // whole sides of an island.
+                float seam_mm = 0.f;
+                for (const auto &[key, seen] : edge_seen) {
+                    if (seen.size() != 2 || (seen[0] - seen[1]).norm() <= 1e-4f)
+                        continue;
+                    seam_mm += (patch.vertices[size_t(key >> 32)] - patch.vertices[size_t(uint32_t(key))]).norm();
+                }
+                std::printf("  interior edges: %d, discontinuous: %d, total torn seam: %.2f mm (worst jump %.3f)\n",
+                            adjacent, broken, seam_mm, worst);
+                std::printf("  stored islands %zu vs charts %d -> %s\n", layer.islands.size(),
+                            unwrap.chart_count,
+                            layer.islands.size() == size_t(unwrap.chart_count) ? "stored placements used"
+                                                                              : "net rebuilt");
+            }
+        }
+    return 0;
+}

src/libslic3r/TextureDisplacement.cpp

@@ -1236,52 +1236,81 @@ bool triangles_overlap(const Tri2 &a, const Tri2 &b, float eps)
 struct NetGrid
 {
     static constexpr int BIG_SPAN = 16;
-    float                cell;
-    float                eps;
-    std::unordered_map<uint64_t, std::vector<Tri2>> cells;
-    std::vector<Tri2>    big;
+    // Each stored triangle keeps its own bounding box. Overlap testing is dominated by rejects - a cell
+    // holds every triangle whose box touches it, and a candidate meets only a couple of them for real -
+    // so paying six floats per entry to answer most of those rejects with four comparisons, instead of a
+    // full triangle intersection, is what makes the net affordable. Measured on a 42k-triangle patch the
+    // grid ran ~19 million candidate pairs per net, nearly all of them misses, and rejecting them this
+    // way took the net from ~175 ms to ~53 ms.
+    //
+    // The box rides inside the entry rather than in a parallel array: splitting them to scan boxes back
+    // to back was tried and came out slower, because each bucket then grows two vectors instead of one.
+    struct Entry
+    {
+        Tri2  tri;
+        Vec2f lo, hi;
+    };
+    float                                           cell;
+    float                                           eps;
+    std::unordered_map<uint64_t, std::vector<Entry>> cells;
+    std::vector<Entry>                              big;
 
     static uint64_t key(int x, int y) { return (uint64_t(uint32_t(x)) << 32) | uint32_t(y); }
-    bool range(const Tri2 &t, int &x0, int &y0, int &x1, int &y1) const
+    static Entry    entry(const Tri2 &t)
+    {
+        return Entry{ t, t[0].cwiseMin(t[1]).cwiseMin(t[2]), t[0].cwiseMax(t[1]).cwiseMax(t[2]) };
+    }
+    bool range(const Vec2f &lo, const Vec2f &hi, int &x0, int &y0, int &x1, int &y1) const
     {
-        const Vec2f lo = t[0].cwiseMin(t[1]).cwiseMin(t[2]), hi = t[0].cwiseMax(t[1]).cwiseMax(t[2]);
         x0 = int(std::floor(lo.x() / cell));
         y0 = int(std::floor(lo.y() / cell));
         x1 = int(std::floor(hi.x() / cell));
         y1 = int(std::floor(hi.y() / cell));
         return x1 - x0 <= BIG_SPAN && y1 - y0 <= BIG_SPAN;
     }
+    // Boxes grown by eps on both sides, to match the tolerance triangles_overlap() itself works to: a
+    // reject here must never discard a pair that test would have called touching.
+    bool boxes_apart(const Entry &a, const Entry &b) const
+    {
+        return a.hi.x() + eps < b.lo.x() || b.hi.x() + eps < a.lo.x() || a.hi.y() + eps < b.lo.y() ||
+               b.hi.y() + eps < a.lo.y();
+    }
+    bool hits(const Entry &q, const std::vector<Entry> &bucket) const
+    {
+        for (const Entry &b : bucket)
+            if (!boxes_apart(q, b) && triangles_overlap(q.tri, b.tri, eps))
+                return true;
+        return false;
+    }
     bool overlaps(const Tri2 &t) const
     {
-        for (const Tri2 &b : big)
-            if (triangles_overlap(t, b, eps))
-                return true;
+        const Entry q = entry(t);
+        if (hits(q, big))
+            return true;
         int x0, y0, x1, y1;
-        if (!range(t, x0, y0, x1, y1)) {
-            for (const auto &[k, tris] : cells)
-                for (const Tri2 &b : tris)
-                    if (triangles_overlap(t, b, eps))
-                        return true;
+        if (!range(q.lo, q.hi, x0, y0, x1, y1)) {
+            for (const auto &[k, bucket] : cells)
+                if (hits(q, bucket))
+                    return true;
             return false;
         }
         for (int x = x0; x <= x1; ++x)
             for (int y = y0; y <= y1; ++y)
-                if (const auto it = cells.find(key(x, y)); it != cells.end())
-                    for (const Tri2 &b : it->second)
-                        if (triangles_overlap(t, b, eps))
-                            return true;
+                if (const auto it = cells.find(key(x, y)); it != cells.end() && hits(q, it->second))
+                    return true;
         return false;
     }
     void insert(const Tri2 &t)
     {
-        int x0, y0, x1, y1;
-        if (!range(t, x0, y0, x1, y1)) {
-            big.push_back(t);
+        const Entry e = entry(t);
+        int         x0, y0, x1, y1;
+        if (!range(e.lo, e.hi, x0, y0, x1, y1)) {
+            big.push_back(e);
             return;
         }
         for (int x = x0; x <= x1; ++x)
             for (int y = y0; y <= y1; ++y)
-                cells[key(x, y)].push_back(t);
+                cells[key(x, y)].push_back(e);
     }
 };
 } // namespace
@@ -1293,11 +1322,20 @@ std::vector<TextureIsland> compute_connected_net(const PatchUnwrap &unwrap)
     if (n <= 1)
         return islands;
 
-    // Chart adjacency, with one representative shared edge per adjacent pair.
+    // Chart adjacency, with one representative shared edge per adjacent pair: the fold line the pair is
+    // unfolded about.
+    //
+    // Which edge that is matters, because two charts can touch along more than one run. A chart cut open
+    // to flatten it - a ring opened by segment_into_charts(), say - touches its other half along *both*
+    // sides of the cut. Folding is rigid, so only the run the fold line belongs to comes out matching;
+    // every other run is left mismatched, and a mismatched run is exactly where the texture visibly
+    // jumps. Taking whichever edge the map happened to yield first therefore left the long side broken
+    // about as often as the short one. The fold line is picked from the longest run instead, so what is
+    // left discontinuous is the shortest boundary the pair has.
     const auto edges = build_shared_edges(unwrap);
     struct PairEdge { ChartEdge a, b; };
-    std::map<std::pair<int, int>, PairEdge> pair_edge;
-    std::vector<std::vector<int>>            adj(static_cast<size_t>(n));
+    struct SharedEdge { PairEdge fold; int base_lo = -1, base_hi = -1; float length = 0.f; };
+    std::map<std::pair<int, int>, std::vector<SharedEdge>> pair_shared;
     for (const auto &[base_edge, list] : edges) {
         for (size_t i = 0; i < list.size(); ++i)
             for (size_t j = i + 1; j < list.size(); ++j) {
@@ -1305,14 +1343,50 @@ std::vector<TextureIsland> compute_connected_net(const PatchUnwrap &unwrap)
                 if (c1 == c2 || c1 < 0 || c2 < 0 || c1 >= n || c2 >= n)
                     continue;
                 const std::pair<int, int> pk{ std::min(c1, c2), std::max(c1, c2) };
-                if (pair_edge.count(pk))
-                    continue; // keep the first shared edge as the fold line for this pair
-                pair_edge[pk] = (c1 < c2) ? PairEdge{ list[i], list[j] } : PairEdge{ list[j], list[i] };
-                adj[size_t(pk.first)].push_back(pk.second);
-                adj[size_t(pk.second)].push_back(pk.first);
+                SharedEdge se;
+                se.fold    = (c1 < c2) ? PairEdge{ list[i], list[j] } : PairEdge{ list[j], list[i] };
+                se.base_lo = base_edge.first;
+                se.base_hi = base_edge.second;
+                // The unwrap is scaled to true surface area, so a uv distance is a length in mm.
+                se.length = (unwrap.uvs[size_t(se.fold.a.uv_lo)] - unwrap.uvs[size_t(se.fold.a.uv_hi)]).norm();
+                pair_shared[pk].push_back(se);
             }
     }
 
+    std::map<std::pair<int, int>, PairEdge> pair_edge;
+    std::map<std::pair<int, int>, float>    pair_weight; // length of the run each pair folds across
+    std::vector<std::vector<int>>           adj(static_cast<size_t>(n));
+    for (const auto &[pk, shared] : pair_shared) {
+        // Group the pair's shared edges into runs - edges joined end to end through a base vertex - and
+        // total each run's length.
+        std::unordered_map<int, int> local;
+        for (const SharedEdge &se : shared)
+            for (const int v : { se.base_lo, se.base_hi })
+                local.emplace(v, int(local.size()));
+        UnionFind runs(local.size());
+        for (const SharedEdge &se : shared)
+            runs.unite(local[se.base_lo], local[se.base_hi]);
+
+        std::unordered_map<int, float>  run_length;
+        std::unordered_map<int, size_t> run_first;
+        for (size_t i = 0; i < shared.size(); ++i) {
+            const int root = runs.find(local[shared[i].base_lo]);
+            run_length[root] += shared[i].length;
+            run_first.emplace(root, i);
+        }
+        int   best_root = -1;
+        float best_len  = -1.f;
+        for (const auto &[root, len] : run_length)
+            if (len > best_len) { best_len = len; best_root = root; }
+        if (best_root < 0)
+            continue;
+
+        pair_edge[pk] = shared[run_first[best_root]].fold;
+        pair_weight[pk] = best_len;
+        adj[size_t(pk.first)].push_back(pk.second);
+        adj[size_t(pk.second)].push_back(pk.first);
+    }
+
     // Per chart: its vertices, its triangles and its flattened area.
     std::vector<std::vector<int>> chart_verts(static_cast<size_t>(n)), chart_tris(static_cast<size_t>(n));
     std::vector<float>            chart_area(static_cast<size_t>(n), 0.f);
@@ -1366,15 +1440,29 @@ std::vector<TextureIsland> compute_connected_net(const PatchUnwrap &unwrap)
             for (const int t : chart_tris[size_t(root)])
                 grid.insert(placed(m, t));
         }
-        std::queue<int> q;
-        q.push(root);
+        // Grown strongest-adjacency-first (Prim, not breadth-first): a chart is folded onto whichever
+        // neighbour it shares the longest boundary with, among everything reachable so far. Order matters
+        // because only the fold a chart is actually reached by comes out matching - every other boundary
+        // it has is left to chance. Taking neighbours in breadth-first order, biggest-area first, let a
+        // far-off branch claim a chart across a short boundary before its true neighbour was reached, and
+        // the long boundary they shared then stayed broken. That is the visible seam next to a hole: a
+        // ring is cut into two halves that share a long boundary, and whichever half was reached first
+        // took the other one along some unrelated edge.
+        using Candidate = std::pair<float, std::pair<int, int>>; // weight, (from, to)
+        std::priority_queue<Candidate>                              q;
+        const auto push_neighbours = [&](int p) {
+            for (const int c : adj[size_t(p)])
+                if (net_of[size_t(c)] < 0 && !chart_tris[size_t(c)].empty()) {
+                    const auto w = pair_weight.find({ std::min(p, c), std::max(p, c) });
+                    q.push({ w == pair_weight.end() ? 0.f : w->second, { p, c } });
+                }
+        };
+        push_neighbours(root);
         while (!q.empty()) {
-            const int p = q.front();
+            const auto [weight, link] = q.top();
             q.pop();
-            std::vector<int> neighbours = adj[size_t(p)];
-            std::stable_sort(neighbours.begin(), neighbours.end(),
-                             [&chart_area](int a, int b) { return chart_area[size_t(a)] > chart_area[size_t(b)]; });
-            for (const int c : neighbours) {
+            const int p = link.first, c = link.second;
+            {
                 if (net_of[size_t(c)] >= 0 || chart_tris[size_t(c)].empty())
                     continue;
                 const auto it = pair_edge.find({ std::min(p, c), std::max(p, c) });
@@ -1405,7 +1493,7 @@ std::vector<TextureIsland> compute_connected_net(const PatchUnwrap &unwrap)
                 for (const Tri2 &t : tris)
                     grid.insert(t);
                 net_of[size_t(c)] = net;
-                q.push(c);
+                push_neighbours(c);
             }
         }
     }
@@ -5041,4 +5129,5 @@ indexed_triangle_set cut_mesh_at_steps(const indexed_triangle_set &mesh, const s
     return out;
 }
 
+
 } // namespace Slic3r

src/slic3r/GUI/Gizmos/GLGizmoTextureDisplacement.cpp

@@ -489,15 +489,7 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
     // volume for a shaded pass that then draws nothing is what made the model vanish - most obviously
     // with zero layers, but equally with a layer that has no texture picked yet.
     const bool use_shaded = m_use_shaded_preview && m_shaded_preview_glmodel.is_initialized() && shaded_preview_ready();
-    // Checker/Distortion are built from the *base* patch and drawn with a polygon offset, which biases
-    // depth values - it does not move the geometry. It therefore cannot win against a surface that
-    // genuinely stands in front, and the displaced preview does exactly that: it rises above the base
-    // surface by the layer's depth. Drawn underneath a UV-check overlay it simply occludes it, which is
-    // why those two modes looked like they did nothing. Leave it out and let the undisplaced volume show
-    // through instead (toggle_model_objects_visibility below) - that one *is* coincident with the
-    // overlay, which is what the offset assumes, and it is the surface whose mapping is being inspected.
-    const bool use_true_preview = !use_shaded && m_uv_check_mode == UVCheckMode::None &&
-                                  m_preview_glmodel.is_initialized();
+    const bool use_true_preview = !use_shaded && m_preview_glmodel.is_initialized();
     // In Checker/Distortion mode the UV-check overlay *is* the surface visualization the user is
     // looking at, so the opaque paint-selection highlight must not be drawn on top of it - same
     // reasoning as skipping it for the shaded preview (see bug #12). Without this the painted area
@@ -525,13 +517,7 @@ void GLGizmoTextureDisplacement::render_painter_gizmo()
             render_triangles(selection);
             glsafe(::glDisable(GL_POLYGON_OFFSET_FILL));
         }
-    } 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
-        // overlay, or nothing draws the surface at all and the checker floats alone over an empty scene.
-        // Deliberately without the depth bias the branch above applies: the checker/heatmap is drawn later
-        // with its own -1 offset and has to win against this. Biasing both by the same amount is what made
-        // the painted area cover the checker and is why this call used to be skipped outright.
+    } else if (show_paint_overlay) {
         render_triangles(selection);
     }
 
@@ -5724,20 +5710,14 @@ void GLGizmoTextureDisplacement::on_render_input_window(float x, float y, float
         const int cur_mode = m_use_shaded_preview                               ? 1 :
                              m_uv_check_mode == UVCheckMode::Checker    ? 2 :
                              m_uv_check_mode == UVCheckMode::Distortion ? 3 : 0;
-        int  new_mode       = cur_mode;
-        bool wf_toggle      = false;
-        bool open_uv_editor = false;
-        // Checker and Distortion both draw *the unwrap* - the first the texture grid laid over it, the second
-        // its stretch - so they only mean anything for a layer mapped with Unwrap (LSCM). On the default
-        // triplanar mapping (or cylindrical / spherical / from view) they are faded out with the reason in the
-        // tooltip, rather than being offered and then showing nothing.
-        const wxString uv_view_na = active == nullptr ? _L("Add a layer first.") :
-                                    active->projection_method != TextureProjectionMethod::LSCM ?
-                                                        _L("Only for a layer mapped with Unwrap (LSCM) - set the "
-                                                           "active layer's Mapping to Unwrap to use this view.") :
-                                                        wxString();
-        // Either view over a layer that stopped being an unwrap shows nothing at all, so fall back to Normal.
-        if ((cur_mode == 2 || cur_mode == 3) && !uv_view_na.empty())
+        int  new_mode  = cur_mode;
+        bool wf_toggle = false;
+        const wxString distortion_na = active == nullptr ? _L("Add a layer first.") :
+                                       active->projection_method != TextureProjectionMethod::LSCM ?
+                                                           _L("Needs the active layer mapped with Unwrap (LSCM).") :
+                                                           wxString();
+        // Distortion over a layer that stopped being an unwrap shows nothing at all, so fall back to Normal.
+        if (cur_mode == 3 && !distortion_na.empty())
             new_mode = 0;
 
         const float x0 = ImGui::GetCursorPosX();
@@ -5756,20 +5736,12 @@ void GLGizmoTextureDisplacement::on_render_input_window(float x, float y, float
         ImGui::SameLine(0.f, gap_s);
         if (icon_toggle(703, "texture_displacement_checker.svg", cur_mode == 2, icon_md, _L("Checker"),
                         _L("Checker - a test grid instead of the texture. Where the squares stay square the "
-                           "texture is undistorted; where they stretch, it will too. Opens the UV editor if "
-                           "it is closed"),
-                        uv_view_na)) {
-            new_mode       = 2;
-            open_uv_editor = true;
-        }
+                           "texture is undistorted; where they stretch, it will too")))
+            new_mode = 2;
         ImGui::SameLine(0.f, gap_s);
         if (icon_toggle(704, "texture_displacement_distortion.svg", cur_mode == 3, icon_md, _L("Distortion"),
-                        _L("Distortion - blue-to-red stretch heatmap over the unwrap. Opens the UV editor if "
-                           "it is closed"),
-                        uv_view_na)) {
-            new_mode       = 3;
-            open_uv_editor = true;
-        }
+                        _L("Distortion - blue-to-red stretch heatmap over the unwrap"), distortion_na))
+            new_mode = 3;
         vsep(icon_md);
         if (icon_toggle(705, "texture_displacement_wireframe.svg", m_wireframe_overlay, icon_md, _L("Wireframe"),
                         _L("Wireframe - overlay the mesh edges; independent of the view above")))
@@ -5784,13 +5756,6 @@ void GLGizmoTextureDisplacement::on_render_input_window(float x, float y, float
         hover_tip(_u8L("Rebuilds the preview as soon as anything changes. Turn it off on a heavy model if painting "
                         "or dragging a slider starts to stutter - the preview then waits until you let go."));
 
-        // Both are views of the unwrap, so picking one brings the UV editor up with it - including when that
-        // view is already the active one and only the pane is missing.
-        if (open_uv_editor && !m_show_uv_editor) {
-            m_show_uv_editor = true;
-            if (new_mode == cur_mode)
-                update_uv_editor(); // otherwise apply_view_mode() below does it
-        }
         if (new_mode != cur_mode)
             apply_view_mode(new_mode);
         if (wf_toggle) {

src/slic3r/GUI/UVEditorCanvas.cpp

@@ -1712,7 +1712,7 @@ public:
                  bool toggle, bool accent = false, int size_dip = 26)
         : wxWindow(parent, id, wxDefaultPosition, wxDefaultSize, wxBORDER_NONE | wxFULL_REPAINT_ON_RESIZE)
         , m_icon_name(icon), m_icon_dip(size_dip >= 26 ? 16 : 14), m_label(label), m_toggle(toggle), m_accent(accent)
-        , m_size_dip(size_dip), m_tip(tip)
+        , m_size_dip(size_dip)
     {
         SetBackgroundStyle(wxBG_STYLE_PAINT);
         SetToolTip(tip);
@@ -1725,7 +1725,7 @@ public:
         Bind(wxEVT_ENTER_WINDOW, [this](wxMouseEvent &) { m_hover = true; Refresh(); });
         Bind(wxEVT_LEAVE_WINDOW, [this](wxMouseEvent &) { m_hover = false; m_pressed = false; Refresh(); });
         Bind(wxEVT_LEFT_DOWN, [this](wxMouseEvent &) {
-            if (usable()) {
+            if (IsEnabled()) {
                 m_pressed = true;
                 Refresh();
             }
@@ -1734,7 +1734,7 @@ public:
             const bool was_pressed = m_pressed;
             m_pressed              = false;
             Refresh();
-            if (!was_pressed || !usable() || !GetClientRect().Contains(e.GetPosition()))
+            if (!was_pressed || !IsEnabled() || !GetClientRect().Contains(e.GetPosition()))
                 return;
             if (m_toggle)
                 m_on = !m_on;
@@ -1774,30 +1774,6 @@ public:
             Refresh();
         return changed;
     }
-    // Soft-disable: the button is drawn faded and swallows clicks, but stays a live window, so hovering it
-    // still raises its tooltip - now with `reason` appended, saying what to do to make it usable. A window
-    // really disabled with Enable(false) gets no mouse events at all on GTK and MSW, which leaves the user
-    // guessing; this is the same trade-off the gizmo panel's icon_toggle() makes with its `unavailable`.
-    // An empty reason makes the button usable again.
-    void SetUnavailable(const wxString &reason)
-    {
-        if (reason == m_unavailable)
-            return;
-        m_unavailable = reason;
-        SetToolTip(reason.empty() || m_tip.empty() ? m_tip : m_tip + "\n\n" + reason);
-        if (!m_unavailable.empty())
-            m_pressed = false; // a reason appearing mid-press cancels the press
-        Refresh();
-    }
-    // Replaces the plain tooltip, keeping whatever reason is currently appended to it.
-    void SetTip(const wxString &tip)
-    {
-        if (tip == m_tip)
-            return;
-        m_tip = tip;
-        SetToolTip(m_unavailable.empty() || m_tip.empty() ? m_tip : m_tip + "\n\n" + m_unavailable);
-    }
-    bool usable() const { return IsEnabled() && m_unavailable.empty(); }
 
 protected:
     wxSize DoGetBestSize() const override
@@ -1816,7 +1792,7 @@ private:
         const PaneColors c    = PaneColors::current();
         const wxRect     r    = GetClientRect();
         const wxColour   teal(0x00, 0x96, 0x88);
-        const bool       enabled = usable();
+        const bool       enabled = IsEnabled();
 
         wxColour fill = c.bg, border = c.frame, text = c.ink;
         if (m_accent) {
@@ -1876,8 +1852,6 @@ private:
     bool           m_toggle   = false;
     bool           m_accent   = false;
     int            m_size_dip = 26;
-    wxString       m_tip;        // the tooltip without any m_unavailable reason appended
-    wxString       m_unavailable; // non-empty: faded and unclickable, and why (see SetUnavailable())
     bool           m_on       = false;
     bool           m_badge    = false;
     bool           m_hover    = false;
@@ -1923,9 +1897,6 @@ UVEditorPanel::UVEditorPanel(wxWindow *parent) : wxPanel(parent, wxID_ANY)
     });
     m_layer_name->SetMinSize(wxSize(FromDIP(30), -1));
     m_tile = text(wxEmptyString, c.dim);
-    m_tile->SetToolTip(_L("The active layer's tile size: how much of the model one repeat of the texture covers. The "
-                          "canvas is measured in tiles, so one grid cell is one repeat. Change it with Tiling in the "
-                          "layer's settings."));
     header->Add(m_thumb, 0, wxALIGN_CENTER_VERTICAL);
     header->Add(m_layer_name, 1, wxALIGN_CENTER_VERTICAL | wxLEFT, gap);
     header->Add(m_tile, 0, wxALIGN_CENTER_VERTICAL | wxLEFT, gap);
@@ -1979,19 +1950,9 @@ UVEditorPanel::UVEditorPanel(wxWindow *parent) : wxPanel(parent, wxID_ANY)
         strip->Add(r, 0, wxALIGN_CENTER_HORIZONTAL | wxTOP, FromDIP(11));
         strip->AddSpacer(FromDIP(7));
     };
-    m_select[0] = tool(ID_UV_SELECT_ISLAND, "texture_displacement_uv_select_island",
-                       _L("Island - work on whole islands. Click one to select it, then drag to move it, right-drag to "
-                          "rotate it, or press R to rotate and S to scale with the mouse (click or Enter to confirm, Esc "
-                          "to cancel)."),
-                       true);
-    m_select[1] = tool(ID_UV_SELECT_VERTEX, "texture_displacement_uv_select_vertex",
-                       _L("Vertex - drag vertices to reshape an island by hand; Shift adds to the selection, Ctrl "
-                          "toggles one in or out of it."),
-                       true);
-    m_select[2] = tool(ID_UV_SELECT_EDGE, "texture_displacement_uv_select_edge",
-                       _L("Edge - drag edges to reshape an island by hand; Shift adds to the selection, Ctrl toggles "
-                          "one in or out of it."),
-                       true);
+    m_select[0] = tool(ID_UV_SELECT_ISLAND, "texture_displacement_uv_select_island", _L("Island - move, rotate and scale whole islands"), true);
+    m_select[1] = tool(ID_UV_SELECT_VERTEX, "texture_displacement_uv_select_vertex", _L("Vertex - drag vertices to reshape; Shift/Ctrl to multi-select"), true);
+    m_select[2] = tool(ID_UV_SELECT_EDGE, "texture_displacement_uv_select_edge", _L("Edge - drag edges to reshape; Shift/Ctrl to multi-select"), true);
     strip_rule();
     m_mark_seams = tool(ID_UV_MARK_SEAMS, "texture_displacement_uv_seam",
                         _L("Mark seams - click edges on the model to cut the unwrap along them. The edge under the cursor is "
@@ -2012,11 +1973,7 @@ UVEditorPanel::UVEditorPanel(wxWindow *parent) : wxPanel(parent, wxID_ANY)
     m_clear_edits = tool(ID_UV_CLEAR_EDITS, "texture_displacement_uv_clear_edits",
                          _L("Clear UV edits - discard all manual vertex/edge moves and return the unwrap to its automatic shape"), false);
     m_snap  = tool(ID_UV_SNAP, "texture_displacement_uv_snap", _L("Snap - stick islands together when dragging one against another"), true);
-    m_frame = tool(ID_UV_FRAME, "texture_displacement_uv_frame",
-                   _L("Frame all islands, fitting every one of them in view (Home or F).\n"
-                      "Elsewhere on the canvas: scroll to zoom around the cursor, and middle-drag - or drag empty space - "
-                      "to pan."),
-                   false);
+    m_frame = tool(ID_UV_FRAME, "texture_displacement_uv_frame", _L("Frame all islands (Home)"), false);
     strip->AddSpacer(FromDIP(4));
 
     m_canvas   = new UVEditorCanvas(this);
@@ -2027,7 +1984,6 @@ UVEditorPanel::UVEditorPanel(wxWindow *parent) : wxPanel(parent, wxID_ANY)
 
     // ---- status line: the current gesture on the left, the unwrap summary on the right ----
     m_status = text(wxEmptyString, c.dim, wxST_ELLIPSIZE_END);
-    m_status->SetToolTip(_L("What is selected, and the exact figures of the move, rotation or scale while you drag one."));
     m_status->SetMinSize(wxSize(FromDIP(40), -1));
     m_stats      = text(wxEmptyString, c.dim);
     auto *status = new wxBoxSizer(wxHORIZONTAL);
@@ -2103,25 +2059,19 @@ void UVEditorPanel::apply_state(const UVEditorCanvas::PaneState &s)
     } else {
         m_thumb->SetBitmap(wxNullBitmap);
     }
-    // Every tool that cannot be used right now is faded with the reason appended to its tooltip, rather than
-    // being hard-disabled (which would hide the tooltip too - see UVToolButton::SetUnavailable()).
-    const wxString no_layer = s.has_layer ? wxString() :
-                                            _L("The pane follows the active texture layer, and that layer has to be mapped "
-                                               "with Unwrap (LSCM). Add a layer and set its Mapping to Unwrap.");
-    m_thumb->SetUnavailable(no_layer);
-    m_layer_name->SetToolTip(s.has_layer ? m_thumb->GetToolTipText() : no_layer);
+    m_thumb->Enable(s.has_layer);
 
     for (int i = 0; i < 3; ++i) {
         m_background[i]->SetValue(int(s.background) == i);
-        m_background[i]->SetUnavailable(no_layer);
+        m_background[i]->Enable(s.has_layer);
     }
-    m_unwrap->SetUnavailable(no_layer);
+    m_unwrap->Enable(s.has_layer);
     m_unwrap->SetBadge(s.unwrap_stale);
-    m_unwrap->SetTip(s.unwrap_stale ?
-                         _L("Out of date - the paint, the seams or the seam angle changed since this unwrap was made. "
-                            "Press to unwrap again.") :
-                         _L("Flatten the painted area into UV islands. It is computed only when you press this, not on "
-                            "every edit - so paint, change the seam angle or mark seams first, then press Unwrap."));
+    m_unwrap->SetToolTip(s.unwrap_stale ?
+                             _L("Out of date - the paint, the seams or the seam angle changed since this unwrap was made. "
+                                "Press to unwrap again.") :
+                             _L("Flatten the painted area into UV islands. It is computed only when you press this, not on "
+                                "every edit - so paint, change the seam angle or mark seams first, then press Unwrap."));
 
     if (m_seam_angle->GetValue() != int(std::lround(s.seam_angle_deg)))
         m_seam_angle->SetValue(int(std::lround(s.seam_angle_deg)));
@@ -2130,26 +2080,15 @@ void UVEditorPanel::apply_state(const UVEditorCanvas::PaneState &s)
     m_connect->Enable(s.has_layer);
 
     m_mark_seams->SetValue(s.mark_seams);
-    m_mark_seams->SetUnavailable(no_layer);
+    m_mark_seams->Enable(s.has_layer);
     m_seam_path->SetValue(s.seam_path);
-    m_seam_path->SetUnavailable(!no_layer.empty() ? no_layer :
-                                s.mark_seams     ? wxString() :
-                                                   _L("Turn Mark seams on first - Path is a quicker way of marking them."));
-    m_clear_seams->SetUnavailable(!no_layer.empty() ? no_layer :
-                                  s.has_seams      ? wxString() :
-                                                     _L("No seams are marked on this layer."));
-    m_clear_edits->SetUnavailable(!no_layer.empty() ? no_layer :
-                                  s.has_uv_edits   ? wxString() :
-                                                     _L("No islands have been reshaped by hand, so there is nothing to "
-                                                        "discard."));
+    m_seam_path->Enable(s.has_layer && s.mark_seams);
+    m_clear_seams->Enable(s.has_layer && s.has_seams);
+    m_clear_edits->Enable(s.has_layer && s.has_uv_edits);
 
     m_stats->SetLabel(s.unwrapped ? wxString::Format(_L("%d islands, %s faces"), s.island_count,
                                                      wxString(std::to_string(s.face_count))) :
                                     wxString());
-    m_stats->SetToolTip(s.unwrapped ? _L("How the painted area came out of the unwrap: the number of separate pieces it "
-                                         "was cut into (at the seams and at edges sharper than the seam angle), and how "
-                                         "many triangles they hold in total.") :
-                                      wxString());
     refresh_selection_tools();
     if (relayout)
         Layout();
@@ -2159,24 +2098,19 @@ void UVEditorPanel::refresh_selection_tools()
 {
     const bool has_islands = m_canvas->has_islands();
     const int  mode        = int(m_canvas->select_mode());
-    // Faded rather than hard-disabled, so the tooltip still says what is missing (see apply_state()).
-    const wxString not_unwrapped = has_islands ? wxString() : _L("Press Unwrap first - there are no islands to work on yet.");
     for (int i = 0; i < 3; ++i) {
         m_select[i]->SetValue(i == mode);
-        m_select[i]->SetUnavailable(not_unwrapped);
+        m_select[i]->Enable(has_islands);
     }
     const bool island_picked = has_islands && m_canvas->select_mode() == UVEditorCanvas::SelectMode::Island &&
                                m_canvas->selected_island() >= 0;
-    const wxString no_island = !not_unwrapped.empty() ? not_unwrapped :
-                               island_picked          ? wxString() :
-                                                        _L("Click an island on the canvas first, in Island mode.");
-    m_avg_scale->SetUnavailable(not_unwrapped);
-    m_cut->SetUnavailable(no_island);
-    m_join->SetUnavailable(no_island);
-    m_unjoin->SetUnavailable(no_island);
-    m_snap->SetUnavailable(not_unwrapped);
+    m_avg_scale->Enable(has_islands);
+    m_cut->Enable(island_picked);
+    m_join->Enable(island_picked);
+    m_unjoin->Enable(island_picked);
+    m_snap->Enable(has_islands);
     m_snap->SetValue(m_canvas->snap_enabled());
-    m_frame->SetUnavailable(not_unwrapped);
+    m_frame->Enable(has_islands);
 }
 
 void UVEditorPanel::on_tool(wxCommandEvent &evt)