Journal

Split-and-Fit: Learning B-Reps via Structure-Aware Voronoi Partitioning

Yilin Liu, Jiale Chen, Shanshan Pan, Daniel Cohen-Or, Hao Zhang, Hui Huang

Simon Fraser University; Shenzhen University; Tel Aviv University

SIGGRAPH 2024Geometry & ModelingB-RepCAD ReconstructionVoronoi DiagramNeural NetworkPoint CloudPrimitive FittingShape Inference
PaperCode

一句话总结

把 B-Rep（边界表示）CAD 模型的重建拆成”先分割空间、再逐格拟合”两步：用神经网络预测目标形状的 Voronoi 图（split），再在每个 Voronoi 单元里拟合一个几何图元（fit）。这种自顶向下、结构感知的思路，比传统自底向上的聚类/拟合方法更稳、更准，且泛化能力更强。

研究背景

B-Rep 是 CAD 建模事实上的标准表示：它用参数化的曲面、曲线、顶点以及它们之间的拓扑关系，紧凑而结构化地描述一个 3D 实体的边界。从点云、距离场这类非结构化输入重建 B-Rep 一直是需求旺盛的问题，但也很难。

已有方法几乎都是自底向上（bottom-up）的：

  • 形状拟合类：用 RANSAC、区域生长、变分形状近似等直接从点云里检测平面、圆柱、球、锥、环面等图元，再推断它们之间的拓扑。几何与拓扑分开处理，容易陷入局部极小。
  • 点分割类（segment-and-fit）：用神经网络先做实例分割（SPFN、ParSeNet、HPNet、SEDNet 等），再对每个点簇拟合图元。但”给点分配标签”这个离散组合决策与”连续参数拟合”混在一起，学习过程不稳定。
  • 直接 CAD 学习类：BSPNet、CAPRINet、D2CSG 等学习 CSG 树/二叉空间划分，或用 ComplexGen 把重建当作目标检测任务。这类方法的通病是：优化目标只是重建误差，而能达到零重建误差的 CSG 树有无穷多棵，存在固有歧义，导致结果常包含大量冗余、不自然的图元。

作者指出问题的根源在于”自底向上 + 局部特征 + 混合的组合-连续优化”。他们想换一个视角：能不能找到一个唯一确定的中间表示，既揭示图元的数量，又揭示图元之间的连接关系，从而绕开歧义？答案就是基于图元的 Voronoi 图。

核心方法

整体分两大步，overview 如下：

flowchart LR
    A[输入: 点云/网格/距离场] --> B[转为体素化 UDF 场]
    B --> C[NVD-Net 预测 Voronoi 边界<br/>二分类]
    C --> D[区域生长构造 Voronoi 单元<br/>及其连接关系]
    D --> E[每个单元内拟合一个图元<br/>单元边界自然裁剪图元]
    E --> F[从连接关系推断拓扑<br/>补交线]
    F --> G[输出 B-Rep: 顶点+曲线+曲面]

关键洞察：定义在图元上的 Voronoi 图

不同于以往定义在点集上的 Voronoi 图，本文的 Voronoi 图定义在图元（顶点、曲线、曲面）之上。给定一组真值（GT）图元，其 Voronoi 图 \(G_v(N_v, E_v)\) 把整个体积空间划分成若干相邻的 Voronoi 单元 \(N_v\)，\(E_v\) 是记录单元间邻接关系的邻接矩阵。

Voronoi 图的两个性质是整个方法的地基：

  1. 对偶性：图元与其 Voronoi 图互为对偶结构，所以不必显式存储图元的类型和参数，只需存这个对偶的 Voronoi 图，学习时可以自由适配各种图元类型。
  2. 唯一性：给定一组图元，Voronoi 图是唯一且固定的。这就把 CSG 树”一个形状对应无穷多种表示”的歧义彻底消除了——训练目标唯一，学习问题变得良定义。

更关键的是，Voronoi 单元边界天然地起到了裁剪（trim）图元的作用，图元被自动裁剪到正确的范围，不需要像 ComplexGen 那样另设一套复杂的裁剪流程。

Split：NVD-Net 预测 Voronoi 图

作者把输入统一转成体素化的无符号距离场（UDF）（点云可经 Neural Dual Contouring 转成 UDF）。UDF 是定义在整个空间上的连续函数，天然适合空间划分问题。

  • 在分辨率 \(r=256\) 的体素网格上，每个体素带 4 通道特征 \((d, g_x, g_y, g_z)\)：\(d\) 是 UDF 值，\((g_x,g_y,g_z)\) 是 UDF 场的一阶梯度向量。
  • 用一个 UNet 结构的网络 \(F(V)\) 做二分类：预测每个体素是否落在 Voronoi 边界上，即 \(b: X \to \{0, 1\}\)。
  • 为了泛化，网络只吃局部特征：把整个体素网格切成大量重叠的局部 patch（步长 \(s=16\)、大小 \(k=32\)），逐个送入网络。重叠保证 patch 边界处预测一致。
  • 训练用 focal loss 应对正负样本极不平衡（边界体素远少于非边界体素）：

\[L_{focal} = -\alpha (1 - b^*)^{\gamma} \log(1 - b) - (1 - \alpha) b^* \log(b)\]

为什么是二分类就够了？ 作者给出了一个漂亮的几何解释：Voronoi 边界本质上等价于 UDF 场的不连续性。对最近图元是平面的点，其梯度向量彼此平行，两平面交界处出现一阶导不连续；对二次曲面，则要看沿梯度正交方向的二阶、三阶导——三阶导 \(L_2\) 范数高的地方，正好落在两个二次图元的交界，即 Voronoi 边界。于是”找 Voronoi 边界”就约化成”找 UDF 二阶导不连续处”这个纯局部的判定问题。真实 UDF 有噪声让不连续难以直接判定，所以用网络来近似这一过程，鲁棒性更好。

Fit：从 Voronoi 图提取图元与拓扑

  1. 区域生长构造单元：从种子体素出发，不断吞并 flag 为 0（非边界）的邻居体素，把体素聚成一个个 Voronoi 单元 \(N_v\)；单元间的邻接关系 \(E_v\) 直接从体素邻域推出。
  2. 逐单元拟合图元：按定义每个单元恰好含一个图元。用最小二乘法在每个单元内拟合，遍历所有可能的图元类型（平面、球、圆柱、锥、环面等），取拟合误差最小的那个。关键是拟合只在单元内单独进行，不需要像 ComplexGen 或搜索类方法那样纠结”把每个点分给哪个图元”，因此歧义小、更鲁棒。
  3. 推断拓扑：单元连接关系已知，故图元间拓扑关系 \(\partial\) 可直接推断——对每个图元找其相邻单元，判断两图元内点距离是否小于阈值。最后仿照 SEDNet 补算相邻曲面的交线，得到完整 B-Rep。输出模型可被主流 CAD 软件编辑、网格化、可视化。

实验结果

在提供 GT B-Rep 的 ABC 数据集上训练（约 20000 个模型）、测试（约 1000 个模型），对比 RANSAC、ComplexGen、HPNet+Point2CAD、SEDNet+Point2CAD。所有方法输入 GT 网格采样的 10k 点；值得注意的是本文方法不需要法向输入，其他方法都用了法向。

几何误差（Table 1，越低越好）： 本文在 Chamfer Distance、Light Field Distance、各类图元误差、有效图元数上全面领先。

方法 顶点 CD 曲线 CD 曲面 CD LFD
ComplexGen 0.0901 0.0601 0.0402 4280
HPNet+Point2CAD 0.0782 0.0222 0.0157 2104
SEDNet+Point2CAD 0.0832 0.0268 0.0192 2262
Ours 0.0327 0.0144 0.0093 908

拓扑误差（Table 2，F1，越高越好）： 曲面-曲线连接 FE = 0.778、曲线-顶点连接 EV = 0.753，均为最优。

检测得分（Table 3）： 顶点/曲线/曲面的 F1、Precision、Recall 全面领先，例如曲面 F1 达 0.821，Precision 0.902。

泛化能力： 作者按”测试形状与训练集的相似度”排序画出重建误差曲线。ComplexGen 随相似度下降误差显著上升（它在 voxel 与图元特征间做全量信息交换，学习歧义大）；本文方法因为只依赖局部几何线索、且把任务简化为二分类，误差几乎不随相似度变化，泛化性最好。

压力测试与用户研究： 加入 1% 对角线长度的噪声后（Table 5），本文在几何误差和检测得分上仍领先；在结构光扫描的真实数据上也能给出合理重建。186 人参与的用户研究中，本文重建结果的视觉保真度排名第一。

贡献与局限

主要贡献：

  • 提出 Split-and-Fit 新范式：通过对体积空间做空间划分来重建 B-Rep，自顶向下、结构感知，从根本上消除 CSG 类方法的表示歧义。
  • 提出 NVD-Net（neural Voronoi diagram network）：把 Voronoi 图预测转化为基于局部特征的体素二分类，泛化能力强、对噪声鲁棒。
  • 给出一套从 Voronoi 图高效提取 B-Rep 曲面、曲线、顶点及其连接关系的方案，图元被单元边界自然裁剪，无需独立复杂的裁剪步骤。

局限：

  • 体素化的量化误差：Voronoi 图用体素表示，分辨率受限。薄图元可能整个单元被边界占满而丢失（如某薄平面未被恢复，导致相邻平面出现锯齿边界）；预测边界上的小孔洞可能误连相邻单元，造成拟合退化。这是作者认为最主要的限制。
  • 噪声数据：真实噪声分布非均匀、来源多样，难以建模，含噪重建仍具挑战。
  • B-Spline 拟合不稳定：解析拟合 B-Spline 仍不稳，实验主要用初等图元（但训练 Voronoi 预测时仍包含 B-Spline，因为 Voronoi 图的构造与图元类型无关）。
  • 网格化不稳定：图元在拓扑上相连但几何上未必精确相接，环路查找与裁剪过程仍不可靠——这是该领域的公开难题。
  • 依赖分片 G2 连续假设：训练数据来自分片 G2 连续、仅在图元交界处不连续的 CAD 模型，遇到偏离该假设的输入（如部分扫描、G2 连续过渡的曲面）时预测可能变差。

延伸思考

这篇工作最值得琢磨的，是它把一个充满歧义的组合优化问题，通过引入”唯一且固定”的 Voronoi 图这一中间表示，转化成了一个良定义、可局部判定的二分类问题。歧义的消除不是靠更强的网络或更多数据，而是靠换一个数学上唯一的学习目标——这种”选对表示胜过硬train”的思路很有借鉴意义。作者在结论里也点明了下一步方向：用隐式函数等连续表示替代体素化 Voronoi 图，以消除量化误差，尤其是拯救那些在体素分辨率下被抹掉的微小结构。