智能分区 — 算法参考与论文

配套设计文档：docs/07-智能分区设计.md（方案 / REFUTE 结论 / 实现状态）。 本文档沉淀算法原理、论文出处、复杂度、端到端 pipeline，以及迭代 39 的性能根因复盘——把"为什么这么做"固化成可检索的项目资产。 范围：三种已落地算法（dihedral / ShapeDiameter / intrinsic CurvatureKMeans）；MultiView 3→2→3 仅列设计要点（backlog，未实现）。

0. 总览

SegmentationAlgorithm 枚举 + run_segmentation 统一入口见 segment/mod.rs；前端经 invoke("auto_segment_v2", { algorithm }) 触发。

1. 算法与论文

1.1 Dihedral（二面角区域生长）

• 原理：对每对共享边的相邻面计算二面角；二面角 < angle_threshold（默认 30°，约 cos 0.93）视为"共面/平滑"，归入同一区域；以邻接图做区域生长（region growing），再用小区域合并（normal_consistency_merge / merge_small_regions_fast）消除碎片。label 0 合法。
• 出处：二面角驱动的区域生长是网格分割的工业标准做法，OrcaSlicer / Bambu Studio 的"按角度分割"即此思路；连通性合并框架与 CGAL Surface_mesh_segmentation 的 Variational Shape Approximation（VSA）同构。
• 复杂度：邻接 BFS + 小区域合并，约 O(F·A)，F=面数，A=平均邻接度（≈6）。在真实网格上毫秒级。

1.2 Shape Diameter Function（SDF，形状直径函数）

• 原理：对每个面，沿其（定向一致的）内法线发射若干条射线，取射线与模型对侧表面的交点距离的中位数/均值，作为该面的"厚度"描述子；薄特征（肢体）SDF 小，厚特征（装甲板）SDF 大。再做 log 归一化 + K-means 聚类。
• 论文：
  • Gal, R., Shamir, A., Cohen-Or, D. (2006). Salient Geometric Features for Partial Shape Matching and Retrieval. (SDF 的提出)
  • Shapira, L., Shamir, A., Cohen-Or, D. (2008). Consistent Mesh Partitioning and Skeletonisation using the Shape Diameter Function. The Visual Computer, 24(4):249–259. (SDF 用于网格分割/骨架化)
• 本仓库实现（segment/sdf.rs）：每面经 kdtree nearest_n(K=512) 取候选面，沿 12 条锥形射线做 ray_triangle 求交 → 约 6144 次射线-三角形求交/面，O(n·K·rays)。这是默认 curvatureKMeans + useSdf:true 路径的主瓶颈（迭代 39 卡死的根因）。
• 关键修正（REFUTE blocker #1）：早期实现把 kdtree 查询半径设为整 bbox 对角线且放在射线循环内 → O(12·n²)；改为 nearest_n(K) 有界候选降到 O(n·K·rays)。另修 consistent_normals 副作用：改为 oriented_normals(mesh)->Vec 不写回 mesh.normals，避免多算法串联污染。

1.3 Intrinsic Curvature K-Means（内在曲率 K 均值）

• 原理：逐面特征向量 = [mean |dihedral curvature|, log-normalized |SDF|]（剔除依赖全局朝向的 PCA 法线投影，避免主轴符号/简并导致"按朝向聚类"）。确定性最远点播种（无 rand 依赖，保测试确定性）+ Lloyd K-means（默认 k=6，20 轮）+ 连通分量拆分（BFS over face_adjacency 把每个簇拆成空间连通片）+ 特征距离合并小碎片到大邻居，最终每个 label 是连通"部件"。
• 论文：
  • Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Trans. Information Theory. (K-means / Lloyd)
  • Meyer, M., Desbrun, M., Schröder, P., Barr, A. H. (2003). Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. VisMath. (离散 Laplace-Beltrami 曲率)
  • Cohen-Steiner, D., Alliez, P., Desbrun, M. (2004). Variational Shape Approximation. SIGGRAPH. (VSA — 连通性/凹度合并的理论基础，CGAL Surface_mesh_segmentation 同源)
• 复杂度：特征提取 O(F)（含 SDF）、K-means O(F·k·iters)、连通 BFS O(F)。SDF 主导时整体退化到 1.2 的量级。

1.4 MultiView 3→2→3（backlog，未实现）

• 设计要点（详见 docs/07 §11）：多视角正交投影 → 仅最近深度面占栅格 → 每个视角 2D 连通区域 → 构建带权 match graph（≥T 视角同区才连边）→ 可切割算法（normalized cut / 自研 Louvain），非 union-find（单调不可切）。
• 启发来源：渲染→2D mask→回投→图社区检测范式（如 Segment Anything, Kirillov et al. 2023；SAMesh 类多视角回投分割）。本轮因 petgraph 0.6 无社区检测 + union-find 方向反（视角越多越合并）而推迟。

2. 复杂度对照

K=512（SDF_CANDIDATE_K）、rays=12 为工程取值；ragk 与 k 由用户配置。真实网格（数十万面）下 SDF/Curvature 路径可达数秒～数十秒——必须在 worker 线程跑（见 §4）。

3. 端到端 pipeline

前端 IntelligentSegmentPanel
  └─ invoke("auto_segment_v2", { algorithm })   // 面板 setLoading(true)
        │
后端 auto_segment_v2 (async fn → Tauri tokio worker 线程)
  ├─ mesh.take() 出 Mutex（释放锁，主线程不冻结）
  ├─ run_segmentation(&mut mesh, algo)
  │     ├─ Dihedral | ShapeDiameter | CurvatureKMeans
  │     └─ 每阶段 emit("segment-progress", {progress, stage})
  ├─ mesh.history.clear()
  ├─ mesh 写回 Mutex
  └─ SegmentResult { segments, segment_labels, face_colors: Vec::new() }
        │  (前端 setLoading(false))
前端 updateSegmentLabels(labels, segments)   // 不再传 faceColors

• 进度链路：segment-progress 事件 → Toolbar.tsx 浮层 + Viewport.tsx 由 isLoading 门控。缺口（已修）：面板 run() 原先未 setLoading(true)，浮层不显示。
• label-only 历史：auto 分区不改 face_colors（仅改 labels），故 face_colors 返回空，省多兆 IPC + 前端全量重绘（与 MergeResult/SplitResult 同例）。

4. 性能根因复盘（迭代 39，2026-08-09）

症状：点击"智能分区"后窗口"未响应"、无法操作。

根因（三层叠加）：

1. 同步命令跑主线程：Tauri v2 的 sync #[tauri::command] 在 webview/主线程执行；默认 curvatureKMeans + useSdf:true 走 SDF（O(n·6144)），重计算冻结 UI 消息泵 → 窗口假死。（Tauri v2 的 async fn 命令由内置多线程 tokio runtime 调度到 worker 线程，不阻塞主线程。）
2. Mutex 持锁冻结：即使改 async，若 lock() 后持 MutexGuard 跑重计算，主线程的同步命令在 lock() 处被阻塞 → 仍卡。必须把 mesh take() 出锁、算完再写回。
3. 多兆 face_colors 回传：auto 分区从不改色，却回传 4n 字节全量颜色 JSON（数 MB），挤占 IPC 与前端全量重绘。

修复（R1–R4）：

• R1 commands/segment.rs：auto_segment_v2 改 async fn + State<AppState>；mesh take() 出 Mutex 计算、释放锁、算完锁回（worker 线程跑重计算）。
• R2 同上：face_colors 返回 Vec::new()（auto 分区可证不改色）。
• R3 sdf.rs / curvature.rs：compute_sdf 加 on_progress/base/span，每 n/50 面发一次进度（SDF 段占 curvature 管线 0.0..0.3）。
• R4 IntelligentSegmentPanel.tsx：run() 开头 setLoading(true)，finally 里 setLoading(false)。

验证：cargo test --lib 103 passed / 0 failed / 1 ignored；tsc --noEmit exit 0；vite build 634 模块 exit 0。

显式 backlog（用户点 3：确认交互后再迭代）：

• rayon 并行化 sdf.rs per-face 循环（墙钟时间不变，仅降 CPU 占用）。
• load_model 同病异步化（大模型加载也走主线程）。
• 默认值：useSdf:true + lastSegmentKind 污染导入自动分区路径（用户可能不想要 SDF 的慢）。
• SDF 平滑法线复用（oriented_normals 两遍）。
• Plane 拆分视口"画切痕"交互（坐标系混用会静默切错）。
• 调色板 label % 15 撞色（拆分两片约 1/15 同色）。

5. 参考文献（Bibliography）

• Gal, R., Shamir, A., Cohen-Or, D. (2006). Salient Geometric Features for Partial Shape Matching and Retrieval. Computer Graphics Forum / Eurographics.
• Shapira, L., Shamir, A., Cohen-Or, D. (2008). Consistent Mesh Partitioning and Skeletonisation using the Shape Diameter Function. The Visual Computer, 24(4):249–259.
• Cohen-Steiner, D., Alliez, P., Desbrun, M. (2004). Variational Shape Approximation. ACM SIGGRAPH 2004.
• Meyer, M., Desbrun, M., Schröder, P., Barr, A. H. (2003). Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. VisMath / IEEE Visualization.
• Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137.
• Kirillov, A., et al. (2023). Segment Anything. ICCV 2023 (Meta AI). （MultiView 3→2→3 范式启发）
• CGAL. Surface Mesh Segmentation (package Surface_mesh_segmentation), based on Shapira et al. 2008 + Cohen-Steiner et al. 2004.
• OrcaSlicer / Bambu Studio. Mesh segmentation by dihedral angle (工业实现参考).