Journal

A Divide-and-Conquer Approach for Global Orientation of Non-Watertight Scene-Level Point Clouds Using 0-1 Integer Optimization

Zhuodong Li, Fei Hou, Wencheng Wang, Xuequan Lu, Ying He

Chinese Academy of Sciences; University of Western Australia; Nanyang Technological University

SIGGRAPH 2025Geometry & ModelingPoint CloudNormal OrientationSurface ReconstructionInteger Programming3D Scene
PaperCode

一句话总结

提出 DACPO：用”分而治之”把大规模、非封闭的场景级点云切成小块，先各自定向，再用基于可见性的一致性度量构图，最后以 0-1 整数优化在全局层面统一各块朝向，从而在开放表面场景上实现稳健的法向定向。

研究背景

  • 领域现状：点云法向定向是图形学与三维视觉的基础问题。经典传播类方法（如最小生成树、Dipole 电偶极场）高效但贪心；近年的优化类方法多依赖广义缠绕数（GWN）等隐式函数，把法向作为优化变量做全局求解，对噪声、离群点、薄结构较鲁棒。
  • 核心痛点：现有方法几乎都面向封闭、物体级模型，依赖”内部/外部”的清晰区分。大规模、非封闭（开放表面）的场景级点云缺乏内外之分，GWN 类方法直接失效；传播类方法在稀疏、噪声、弱连接区域容易整片翻错。此前面向大场景的图方法（SNO）虽支持非封闭模型，但对噪声与稀疏敏感。
  • 本文 idea：不去一次性定向整个无界场景，而是切块、逐块定向、再全局对齐。逐块问题几何更简单，易于稳健求解；块间关系建成无向图，用”可见连通区域”的视角对齐度量作为边权，把全局对齐转化为一个块翻转状态的 0-1 整数优化问题。

方法

整体框架：DACPO 分两大阶段。第一阶段”逐块定向”——把输入场景切成空间连通、点数相近的块，每块先用随机化贪心初始化法向，再用改造过的迭代泊松重建（iPSR）精修。第二阶段”全局定向”——把各块作为图节点、相邻块连边，边权由”可见连通区域”的视角对齐度量给出，最后解一个 0-1 整数优化决定每块是否整体翻转。

flowchart LR
  A[输入场景点云] --> B[块分割<br/>kNN图+BFS连通子集]
  B --> C[逐块定向]
  C --> C1[随机化贪心初始化<br/>dipole-like向量场]
  C1 --> C2[Neumann边界iPSR精修]
  C2 --> D[构建块间无向图]
  D --> E[可见连通区域VCR<br/>计算视角对齐一致性边权]
  E --> F[0-1整数优化<br/>决定各块翻转状态]
  F --> G[翻转合并 → 全局一致法向]
  G --> H[屏蔽泊松重建出表面]

关键设计：

  1. 块分割。先用类 kd-tree 划分得到点数相近的子集，但子集内点未必空间连通；于是构建 \(k=10\) 的 kNN 图，从每个子集选种子点做广度优先搜索，得到空间连通的”块”。因为假设输入是单连通分量，故每块都连通。典型场景切成约 200 块，从而把块数控制在几百量级，保证后续组合优化可解。

  2. 逐块朝向初始化。基于”相邻两点法向关系”的观察建模：对两邻近点 \(p, p'\)（法向 \(n, n'\)），沿方向 \(r = p'-p\) 判断——若 \(r \parallel n\) 则 \(n'\) 应反向，若 \(r \perp n\) 则 \(n'\) 应同向。据此定义一个 dipole 式向量场 \(F_{p,n}(p') = -\frac{(c\,\hat r \hat r^\top - I)\,n}{\lVert r\rVert^3}\)，其中 \(c>1\) 可调：\(c\) 越大越擅长定向极薄结构，越小越抗噪（噪声模型取 \(c=2\)，其余取 \(c=4\)）。作者指出 Xie 等与 Dipole 分别是 \(c=2\)、\(c=3\) 的特例。用点积 \(e=F_{p,n}(p')\cdot n'\) 衡量影响，在 kNN 生成的 BFS 顺序上贪心逐点选择翻转与否；重复 \(M=5\) 次并投票，投票前用小规模穷举对齐各次结果。

  3. iPSR 的开放表面改造。原 iPSR 用 Dirichlet 边界的屏蔽泊松重建（sPSR）迭代精修法向，但 Dirichlet 会把空间分成”内/外”，对开放表面会生成大量”封口面”（space-closing faces），污染法向更新。本文改用 Neumann 边界：它把空间分成”左/右”而非”内/外”，不产生封口面，只在边界附近有少量易识别的”延伸面”。策略是前期迭代保留延伸面、仅在最后阶段裁剪，使开放块能快速收敛（示例中 Neumann 6 次迭代收敛，Dirichlet 20 次仍不收敛）。

  4. 可见连通区域（VCR）与全局优化。VCR 定义为：从某视点/视向看，几何连通且投影到视平面也连通的区域——其关键性质是在一个 VCR 内只能看到表面的正面或反面之一。若两相邻块朝向一致，则跨越两块边界的 VCR 必然”视角对齐”。做法是把相邻块透视投影到 \(400\times400\) 带 z-buffer 的视平面，剔除不可见面后生成 VCR，按子区域中两块像素数 \(C_1, C_2\) 与边界像素数 \(C_B\) 计算视角对齐强度 \(I = C_B\,C_1\,C_2\)；再用正十二面体面心作为多视点聚合成块对一致性度量 \(\alpha_{ij}\)。归一化得到边权 \(\omega_{ij}\)，最终把”最大化所有相邻块一致性”写成 0-1 整数优化 \(\arg\max_{o}\sum_{(i,j)\in E}\big[(o_i-o_j)^2\,\omega_{ij}(0,1)+(1-(o_i-o_j)^2)\,\omega_{ij}(0,0)\big]\)，用 Gurobi 求解，\(o_i\in\{0,1\}\) 表示各块是否翻转。

实验结果

在 ScanNet v2 与 SceneNN 两个室内场景数据集上，以”错误定向法向占比（%）”为指标（越低越好），DACPO 在原始、加噪、稀疏各设定下均优于经典与前沿基线。下表取各方法在若干代表性设定上的错误率（数字取自论文，单位 %）：

方法 ScanNet 原始↓ ScanNet Noise2↓ SceneNN 原始↓ SceneNN 10K↓
SNO [2017] 7.333 42.242 3.536 25.728
NGL [2023] 11.846 12.329 11.683 30.972
Hoppe [1992] 10.039 20.680 6.101 26.556
Dipole [2021] 18.121 21.556 15.295 30.594
König [2009] 10.553 30.139 5.615 27.830
WNNC [2024] 15.384 29.089 10.930 27.439
DACPO（本文） 5.270 9.800 2.430 15.603

其中 Noise2 为标准差 0.008 的高斯噪声、10K 为 SceneNN 下采样的极稀疏版本，是最具挑战的设定；DACPO 在这些设定上的优势尤为明显（如 ScanNet Noise2 从次优的 12.329% 降到 9.800%，SceneNN 10K 从 25.728% 降到 15.603%）。

补充实验：重建质量上，用屏蔽泊松重建后计算 Chamfer 距离，DACPO 在 ScanNet 原始/Noise1/Noise2 三档均取得最低值（0.011669 / 0.011957 / 0.012882），但各方法差距较小，说明少量翻错主要表现为重建表面出现缝隙而非整体形变。消融方面：直接对整场景跑 Neumann-iPSR（不分块），错误率从 5.270% 飙到约 29%，证明分而治之必要；单独去掉 iPSR 或去掉初始化都会明显变差（如 Noise2 下 w/o iPSR 30.00%、w/o 初始化 12.40%、两者都用 9.80%），二者缺一不可。运行时得益于分块策略，对约 500K 点的大模型也能良好扩展，且大部分时间花在逐块定向上。

亮点与局限

  • 亮点：
    • 把”整场景一次性定向”的难题转成”逐块定向 + 全局 0-1 组合优化”，绕开了 GWN 类方法对封闭/内外之分的依赖，专门面向非封闭、场景级点云这一被忽视的场景。
    • “可见连通区域 + 视角对齐”提供了一个无需内外定义、纯几何可见性驱动的块间一致性判据，配合正十二面体多视点聚合，鲁棒性好。
    • 用统一的 dipole 式向量场把 Xie、Dipole 等既有方法纳为特例，并以随机化贪心+投票提升初始化稳健性；把块数控制在几百量级使组合优化可解。
    • 在噪声、稀疏、弱连接等硬场景上相较基线优势显著，代码开源。
  • 局限：
    • 依赖”输入为单连通分量”的假设；实际扫描常有遮挡导致的多断连分量，作者只取最大连通分量评测，断连区域的一致性定义会变得含糊。
    • VCR 生成需大量透视投影与光栅化（多视点、每对相邻块），加之 iPSR 迭代，整体计算偏重，主要耗时在逐块定向。
    • \(c\) 需按是否含噪手动切换（噪声取 2、其余取 4），并非完全自适应；评测以网格顶点为输入、网格为真值，与真实原始扫描仍有差距。

延伸思考

  • 全局对齐用的是 0-1 整数优化 + Gurobi 商业求解器，块数受限于可解规模；若场景更大、块数上万，是否可用近似组合优化、图割或学习式方法替代，值得探索。
  • 与 GWN/缠绕数类方法（WNNC、GCNO、iPSR）是互补关系：本文在开放场景更强，而封闭物体上后者仍有优势；一个能自动判别封闭/开放并切换策略的统一框架会很有价值。
  • VCR 的多视点可见性度量本质上把”定向一致性”转成了”渲染视角下只看到一面”的判据，这与可微渲染、遮挡推理相通，或可引入可微光栅化让整条管线端到端可训。
  • “单连通分量”假设是主要软肋，如何把断连区域、弱连接显式建模进图（如引入不确定边或先验约束），可能是提升真实扫描鲁棒性的下一步。