Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search 提出了一种基于碰撞感知凹度度量和树搜索的近似凸分解方法（CoACD），旨在解决三维网格分解中细节丢失与组件冗余的难题。传统近似凸分解方法在保留物体功能细节（如烤面包机插槽、茶壶出水口）和碰撞条件方面存在不足，导致下游物理仿真和机器人交互失效。通过三方面创新实现了更精细、高效的分解：

1. 碰撞感知的凹度度量：双维度分析与高效计算

传统凹度指标（如体积差或边界距离）无法全面衡量分解质量，导致中空结构被填充或细长孔洞被忽略。本文提出双维度凹度度量，从边界与内部同时评估形状差异：

1.1 边界凹度（H₀）与内部凹度（Hᵢ）

  • 边界Hausdorff距离（H₀）：
    采样输入网格和其凸包的边界点集（图5），计算双向最大最小距离：
    $$H_b = \max\left( \sup_{p \in \partial S} d(p, \partial \text{CH}(S)), \sup_{q \in \partial \text{CH}(S)} d(q, \partial S) \right)$$ 其中，($\partial S$)为网格表面，($\partial \text{CH}(S)$)为凸包表面。通过点-面距离优化采样效率，确保表面细节（如凹槽深度）被精确捕捉。

  • 内部Hausdorff距离（$H_i$）：
    采样网格与凸包的内部点集，计算最大距离：
    $$ H_i = \sup_{q \in \text{Int}(\text{CH}(S))} d(q, \text{Int}(S)) $$ 该指标防止凸包侵入原网格未占据区域（如茶壶内部），避免碰撞条件破坏。

1.2 体积替代指标（$R_v$）与理论保障

  • $R_v$的推导：
    将凸包与原网格的体积差等效为球体半径：
    $$ R_v = \sqrt[3]{\frac{3(\text{Vol}(\text{CH}(S)) - \text{Vol}(S))}{4\pi}} $$ 该指标近似Hᵢ，避免高成本的内部点采样。通过定理1证明其与Hᵢ的理论关系：
    $$ \sqrt{2} \max(H_b, R_v) \geq \max(H_b, H_i) $$ 实际中，通过系数(k=0.3)调整Rᵥ，得到最终凹度：
    $$ \text{Concavity}(S) = \max(H_b, k \cdot R_v) $$

1.3 碰撞感知的意义

  • 功能保留：Hᵢ确保中空结构（如抽屉把手孔洞）不被填充，H₀防止浅凹槽被忽略（图2-4）。
  • 用户可控性：凹度阈值($\epsilon$)直观对应“形状增厚程度”，便于调整细节与组件数的平衡。

2. 基于平面切割的网格分解：高效与精确并重

传统体素化方法（如V-HACD）因离散化误差无法处理薄壁结构，而面片分组导致凸包交叉。本文提出直接网格切割法：

2.1 切割平面生成与优化

  • 候选平面采样：沿轴对齐（或PCA主方向）生成(m)个等间距切割平面（图8），覆盖形状主要延伸方向。
  • 平面精细化：对搜索到的离散平面进行局部三元搜索，微调位置以最小化子组件凹度。

2.2 轻量化切割实现

切割过程分四步：

  1. 非相交面分类：将未与切割平面相交的三角面按位置分至左右子组件。
  2. 相交面分割：切割平面与三角面交线生成新边，将面片分为两部分。
  3. 约束Delaunay三角剖分：沿交线生成新表面，填补切割后的开放边界。
  4. 冗余面剔除：移除剖分中产生的非流形三角形，确保组件为闭合流形网格。
    该实现比CGAL快100倍，且支持大规模网格处理。

2.3 优势与挑战

  • 保留细节：直接操作网格避免体素化误差，适合薄壁、孔洞等复杂结构。
  • 凸包无交叉：平面切割生成平整边界，子组件凸包互不重叠（图6）。
  • 终止条件：若组件已凸（凹度=0），立即停止分解，避免冗余计算。

3. 蒙特卡洛树搜索（MCTS）：全局优化分解路径

传统贪心策略仅考虑单步最优，易陷入局部最优。本文引入MCTS模拟多步切割，平衡探索与利用：

3.1 树结构与搜索策略

  • 节点表示：每个节点存储当前组件集合，根节点为初始未分解网格。
  • 动作扩展：选择凹度最大的组件，生成所有候选切割平面对应的子节点（最多(3m)个）。
  • UCB选择：节点价值(Q(n))结合历史收益与探索奖励：
    $$ Q(n) + c \sqrt{\frac{2 \ln N(\text{parent}(n))}{N(n)}} $$ 其中$(c = \text{Concavity}(S)/d)$动态调整，鼓励早期探索。

3.2 节点评估与默认策略

  • 中间质量评分：对路径上的每一步分解计算凹度最大值（公式9），避免仅关注最终结果。
  • 贪心模拟（Default Policy）：对未完全分解的节点，继续使用单步贪心切割（沿主方向均分），生成(d+1)个组件后计算综合评分。

3.3 后处理与合并优化

  • 组件合并：遍历相邻组件，若合并后凹度仍低于阈值，则合并以减少冗余（图13a）。
  • 性能对比：相比单步贪心，MCTS减少30%组件数（表2），且避免局部最优（图9-10）。

4. 实验验证：量化对比与应用场景

4.1 数据集与基线对比

  • 数据集：
    • V-HACD数据集（61形状）：测试通用分解能力。
    • PartNet-Mobility（2346形状）：验证复杂功能结构（如铰链、把手）的保留效果。
  • 基线方法：HACD（面片分组）、V-HACD（体素化）、Animation（商业算法）。
  • 评价指标：组件数、平均凹度、运行时间、物理仿真成功率。

4.2 关键结果

  • 量化优势（表1-5）：
    • 在PartNet-Mobility上，CoACD组件数比V-HACD减少55%（7.3 vs. 44.6），凹度降低63%（0.204 vs. 0.414）。
    • 在相同组件数下，CoACD凹度比Animation低29%（0.049 vs. 0.069）。
  • 物理仿真提升：机器人开抽屉任务成功率从49%（V-HACD）提升至80%（图16），因碰撞形状更贴合真实把手结构。

4.3 参数影响分析

  • 凹度阈值$(\epsilon)$：$(\epsilon=0.05)$可平衡细节与效率（图14），阈值越小组件数指数增长。
  • 树搜索参数：
    • 候选平面数(m=20)时效果最优（图13b）。
    • 搜索深度(d=4)，迭代次数(t=500)实现质量与速度平衡（图13c-d）。

5. 总结与展望

本文通过碰撞感知凹度度量、直接网格切割与多步树搜索，解决了传统凸分解方法在细节保留与碰撞条件维护上的缺陷。核心贡献包括：

  1. 双维度凹度指标，兼顾表面与内部结构。
  2. 高效平面切割实现，避免体素化误差。
  3. MCTS全局优化，减少冗余组件。

应用价值：为机器人抓取、物理仿真提供高保真碰撞形状，支持复杂交互任务。
未来方向：引入GPU并行加速切割与搜索过程；结合深度学习预测初始切割平面；设计自适应方向选择策略。