Reference: https://www.cs.sfu.ca/~haoz/teaching/cmpt464/index.html SFU CMPT 464 Computer Graphics Course Notes by Hao Zhang 学习笔记可能有理解错的地方，不保真!!!

Shape Segmentation

Edge

Edges on 2D images

Edges on 3D surfaces

Edge detection in point clouds
- Edge-Aware Resampling (EAR) → not just detection since edge points may not have been sampled → upsampling

Edge: Model-driven vs Data-driven

Model-driven segmentation

Minima rule

cut boundary at negative minima of curvature → “内凹连接”部位
over concavity (a local criterion) → 局部准则
- 计算曲率: 对每个表面点计算主曲率 \(k_1, k_2\)（通常取负的 \(⁡k_{\min}\)）
- 检测局部极小值: 找出曲率为负且为局部极小的点 → 凹陷点
- 形成凹谷线（valley lines）:将这些凹陷点沿最小曲率方向连接成连续线
- 执行分割: 以凹谷线为边界，将表面分成不同部分

Symmetry

A non-local criterion: a segment is self-symmetric → 几何准则

计算对称性度量（symmetry measure）

检测它是否与自身镜像对称
- 对称性不能通过单个点或局部曲率判断
- 需要全局信息或整个 patch 的几何结构来评估对称度 → “non-local”的体现
可以沿主对称轴或者通过最近邻点匹配计算

Part-type segmentation

Skeleton-based

沿骨架进行平面扫描（plane sweep），通过分析切面轮廓变化，将形状分割成自然部件

计算曲线骨架（Curve Skeleton）
- 生成形状的中心线（medial axis-like 结构），捕捉形状主干与分支。
- 骨架提供了形状的“主轴”信息。
Plane sweep
- 沿骨架方向生成一系列垂直切平面（planar sweep）。
- 每个切面截取形状，得到一个轮廓剖面（2D profile）。
跟踪剖面函数的关键点（critical points）→ 定义 part
- 剖面函数可以是截面面积、边界长度或其他几何量。
- 识别局部极值或变化点（critical points），表示可能的部件边界

Surface-based

Boundary-based→先提取物体表面或体积中的“边界”或“特征线”→沿这些边界将形状分割 →Mesh Scissoring
- 从稠密网格上提取特征边（feature edges）
- 对提取出的边缘进行筛选
- 将分散的边缘连接成闭合轮廓
- Post processing
Region growing / Clustering
- Region growing: watershed
  - 为每个顶点分配权重例如曲率、法向变化或其他几何属性
  - Threshold weights 识别局部最小值或平坦谷底（minima / minima plateau）
  - 将 unlinked vertex v 连接到邻域中权重最小的顶点
  - 所有可以流向同一个局部最小值或谷底的顶点 → 属于同一 segment
  - Con: prone to over-segmentation
  - Con: boundaries may not be smooth
- Clustering:
  - k-means clustering (Lloyd or Lloyd-Max algorithm)
    - \(\text{minimize } J = \sum_{j=1}^{K} \sum_{x \in S_j} ( x - \mu_j )^2\) where \(\mu_j = \frac{1}{/S_j/} \sum_{x \in S_j} x\) is the mean of cluster \(S_j\). K-means 算法的本质就是迭代寻找簇分配 \(S_j\) 和簇中心 \(\mu_j\)

    - k-means for mesh segmentation: (从2D的点变成3D的面)
        - **距离计算**：两两面距离 $$O(n^2 \log n)$$，结合地形距离 + 法向角度，凹角加权防止跨簇 → 凹陷/边缘区域 不容易被同一簇包含
        - Cons: 局部最小值、难选 k、特征缺失区域连锁、锯齿边界
        - 改进
            - Fuzzy k-means
                - 对网格做 fuzzy k-means，标记那些属于多个簇可能性的面。
                    - 每个面有一个隶属度向量，表示属于各簇的可能性
                - 在模糊区域上应用 显式图割（graph min-cut）优化边界
            - Spectral k-means: Spectral embedding