💻 computer science

IBPA: Real-time Free-form Manifold Mesh Reconstruction via Incremental Ball Pivoting with Integrated Hole Detection

本文提出了 IBPA，这是一种实时增量表面重建方法，它通过改进球体旋转算法（Ball Pivoting Algorithm），能够从流式水下点云数据中生成自由形式流形网格并检测空洞，从而克服了传统数字地形模型在高度场方面的局限性，以改善决策制定。

原作者： Mauhing Yip, Mohit Singh, Kostas Alexis, Christian Schellewald, Annette Stahl

发布于 2026-07-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Mauhing Yip, Mohit Singh, Kostas Alexis, Christian Schellewald, Annette Stahl

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名深海探险家，正驾驶着一台机器人潜水器（ROV 或 AUV）进行海底测绘。你正在向回传送一股 3D 点云流，以构建海底的图像。但问题在于，海洋中充满了复杂的形状。沉船有着向外延伸的机翼、洞穴和悬挑结构。

传统的测绘工具就像是试图在平坦的坐标纸上绘制一个 3D 雕塑。它们在地图上的每个位置只能显示一个高度。如果你尝试用这些旧工具去绘制一架沉没飞机的机翼底部，地图会显示“此处无物”，因为纸张无法表现悬挂在地面“上方”的东西。这就像试图用一张平面地图来描述过山车环形轨道一样；那个环形结构就消失了。

这篇论文的作者 Mauhing Yip 及其同事说：“让我们尝试一种不同的方法。”他们采用了经典的老方法——球体滚转算法（Ball Pivoting Algorithm, BPA），并赋予了它一项超能力：使其能够在机器人移动时进行实时处理。他们将这种新方法称为 IBPA（增量球体滚转算法）。

魔力球与不断增长的网格

想象一下，机器人在海底投下一个巨大的、隐形的沙滩球。球从一个 3D 点滚动到下一个点。每当球完美地触碰到三个点时，它就会“旋转”并创建一个连接这三个点的平面三角形。它不断地滚动和旋转，像缝补拼布被一样将这些三角形缝合在一起，慢慢构建出海底的 3D 网格。

但问题在于，在旧版游戏中，你必须等到收集到所有的点之后才能开始构建。作者意识到，对于正在探索深海的机器人来说，等待太慢了。他们需要随着点的到来，同步构建这张“拼布”。

“禁区”与“漏洞侦探”

当你一边接收织物，一边构建拼布时，情况可能会变得混乱。

“幽灵”三角形： 有时，一个不该出现的点会突然到达（也许是机器人的导航出了差错）。如果机器人盲目地添加一个三角形，它可能会刺穿现有的网格，造成“自相交”（就像一个三角形在刺穿它自己）。作者的方法就像一个严格的编辑：如果一个新点落在现有三角形球体的“空隙”内，那么这个三角形会被立即删除。点依然存在，但错误的三角形消失了。
“意面”结节： 有时，网格可能会在 3D 空间中扭曲成一个毫无意义的结（比如莫比乌斯环，它只有一个面）。作者的方法会检查每一个新生成的三角形，确保它的朝向正确，从而保证整个表面是“可定向的”（即有明确的内外之分）。
“漏洞猎手”： 这是最酷的部分。在机器人进行测绘时，该方法会不断寻找网格中的“漏洞”。但它很聪明。它不仅仅是说“我们还没去过那里”，它会寻找那些本该被填补却仍有缺口的区域。如果机器人刚刚经过某个地方，但网格仍有缺口，系统就会用红色标出。这就像一个侦探在说：“我们刚才就在这里，但我们漏掉了一块拼图！”

他们排除了什么

作者非常明确地说明了他们的法方法不是什么。

他们明确拒绝将标准的 2D 地图（如数字地形模型）用于复杂的海底场景。他们认为这类地图无法处理悬挑或垂直墙壁，因此无法胜任。
他们也拒绝依赖随机猜测来寻找缺失点的方法。与其让机器人盲目地转圈寻找缺口，他们的法方法会先检测出缺口，然后告诉操作员具体应该回到哪里。
他们不会为了让地图看起来漂亮而发明虚假数据。如果某个地方缺失，他们就让它保持为空洞。他们不会去猜测下面是什么。

证明：真实的机器人，真实的数据

团队不仅在计算机上进行了模拟，还用真实的机器人进行了测试。

他们使用了一台配备多波束声呐的名为 Eelume 的水下机器人。
他们在三个真实世界的数据集上进行了测试：Heinkel（一架沉没的飞机）、Nyhavna 和 Figaro。
在 Heikel 测试中，机器人收集数据花费了 886 秒（约 15 分钟），而作者的方法仅用了 22 秒 就重建了整个 3D 网格。
他们发现该方法可以识别地图中的“漏洞”。例如，在 Heinkel 数据集中，他们识别出了飞机机翼下的两个大洞。他们设定了一个规则：如果洞口的边缘长度超过 3.16 米，就会被标记为红色。
他们还在实验室的大型水箱和 特隆德海姆港（Trondheim Harbour） 进行过实时测试。在水箱中，他们故意留出了一个 3 米 的缺口。系统立即发现了它，将其标红，操作员随后可以引导机器人去填补那个特定的缺口。

核心结论

作者认为，这种方法是一种稳健的方式，可以在移动过程中构建海底 3D 地图，能够处理杂乱的数据和奇特的形状而不至于出错。他们证明了该方法可以通过忽略异常值（坏点）或删除导致错误的三角形来处理“离群值”，并且能准确告诉人类操作员哪里需要重新观察。

他们并没有解决世界上所有的海底测绘问题，但他们打造了一个能够实时工作、保持地图真实性（无虚假数据）并能指出哪里不完整的工具。最棒的是，他们免费分享了代码，所以任何人都可以尝试使用。

技术摘要：IBPA —— 通过增量球形滚转算法实现实时自由形式流形网格重建

1. 问题陈述

遥控无人潜水器（ROV）和自主水下航行器（AUV）经常获取几何形貌测深数据，但后期调查分析往往显示覆盖范围不完整。由于水下部署的运营成本极高，迫切需要通过实时表面覆盖可视化来支持数据采集过程中的决策制定。

传统的增量表面重建方法（如数字地形模型 DTM 或数字表面模型 DSM）在表达能力上存在根本局限。它们将表面表示为高度场（ $z = f(x, y)$ ），每个 $(x, y)$ 坐标仅允许一个高度值。因此，它们无法捕捉水下环境中常见的悬挑结构、垂直结构或复杂的拓扑结构（例如飞机机翼下方或岩石构造）。此外，现有的缺失数据检测方法通常依赖于 2D 投影或随机姿态生成策略，这些方法无法区分“未探索区域”与“因遮挡或传感器故障导致本应采集数据但实际缺失的区域”。

2. 方法论：增量球形滚转算法 (IBPA)

作者提出了 IBPA，这是对经典球形滚转算法（BPA）的一种改进，旨在实现实时、增量且自由形式的表面重建。该方法处理带有法向量的流式点云数据，以构建可定向的流形网格，且不对点云的重叠或空间分布做任何假设。

核心算法改进

将非增量式 BPA 转化为 IBPA 的过程涉及解决三个主要挑战：

动态空间数据结构：
原始 BPA 依赖静态八叉树。IBPA 实现了一个可扩展八叉树，能够动态增长以适应流中到达的新点。当新点位于当前边界之外时，八叉树会沿必要轴向扩展，重新定义原点并为位置编码添加位（bits）以保持各轴之间的一致性。
强制执行空球配置（Empty Ball Configuration）：
在增量处理过程中，新点可能会违反“空球”条件（即三角形的外接球内不包含其他点）。IBPA 通过检查输入的顶点是否违反现有三角形关联球的情况来检测此类违规。如果发生违规，被违反的三角形将被移除，但其顶点会被保留以备未来使用。这确保了表面的有效性，同时不会删除数据点。
流形与可定向性保证：
标准的 BPA 虽然能生成边流形（edge-manifold）网格，但不能保证顶点流形（vertex-manifold）或可定向性。IBPA 通过在每批次重建后执行特定的后处理步骤来强制执行这些属性：
- 顶点流形性： 算法检测并移除非流形顶点。
  - 1-盘非流形顶点（1-disk non-manifold vertices）： 指围绕顶点存在闭合表面环路但包含边界边的配置（产生歧义的内部边界）。冗余的非连通面片会被识别并移除。
  - 0-盘非流形顶点（0-disk non-manifold vertices）： 指不存在闭合环路的配置，可能导致无法填充的孔洞。算法迭代地识别具有高度数（表示多个边界边汇聚于一点）的边界顶点，并移除相关的面片以解决拓扑问题。
- 可定向性： 为了防止出现非定向表面（例如莫比乌斯带），算法强制执行方向一致性。只有当新三角形的方向与所有相邻三角形保持一致时，才会被接受。

其他特性

法向量估计： 对于缺乏法向量的点云，系统通过从顶点指向机器人姿态中心的向量来估计法向量。
计算效率： 为了控制负载，系统限制了每个八叉树叶节点中的“孤立顶点”（未连接到任何面片的顶点）的数量。如果超过限制，则保留随机子集。
孔洞检测： 该方法将边界分类为主要边界（如海岸线）和次要边界（孔洞）。它将最长的边界环识别为主表面，并将较小的环视为孔洞。至关重要的是，只有当孔洞的边界长度超过用户定义的阈值时，才将其标记为“缺失信息”，从而将孔洞与小间隙或噪声区分开来。

3. 主要贡献

论文概述了以下具体贡献：

增量式 BPA： 一种能够从流式数据中生成满足顶点和边流形属性的可定向流形网格的方法。
自由形式拓扑支持： 能够重建悬挑、垂直墙壁和多值 $z$ 表面的能力，克服了 DSM/DTM 方法的局限性。
鲁棒性： 该方法可以处理变化的的空间分辨率、离群点和多样化的环境（室内/室外），且无需伪造点或表面。
实时孔洞检测： 具备在线检测网格孔洞的能力，并在任务完成前向操作员提供关于覆盖范围不足区域的可操作反馈。
无重叠假设： 该算法在无需预先假设输入点云的位置或重叠的情况下运行。
开源： 提供了一个带有完整 ROS 集成的参考实现。

4. 实验结果

作者通过线下和线上实验对 IBPA 进行了评估。

线下实验

使用配备多波束测深仪（MBES）的 Eelume AUV 在特隆赫姆峡湾收集了三个数据集：

Heinkel 数据集（沉没飞机）： 任务时长 886 秒；重建耗时 22 秒。该方法成功重建了复杂的几何结构，包括机翼下方的悬挑部分，并检测到了两个显著的孔洞。
Nyhavna 数据集： 任务时长 324 秒；重建耗时 13 秒。检测到一个超过阈值的孔洞。
Figaro 数据集： 任务时长 547 秒；重建耗时 7 秒。检测到了三个大的孔洞。该方法正确识别了点云中的平移偏移为离群点，并由于球半径限制拒绝了该不连通区域。
离群点抗性： 在 Heinkel 数据集中，该方法有效地忽略了由错误地理配准导致的七个异常扫描读数。

线上实验

进行了两项实时实验：

室内（NTNU 海洋控制实验室）： 机器人绘制了一个水箱壁。实验中有意制造了一个 3 米的间隙。系统检测到了该孔洞（边界 > 3 米）并引导操作员进行填充，随后新数据被自动集成。
室外（特隆赫姆港口）： 机器人在自然港口环境中进行测绘。系统成功重建了表面，且缺失信息极少（所有孔洞边界 < 3 米），并有效地移除了靠近水面的离群点。

5. 重要性与主张

论文声称 IBPA 解决了水下机器人领域的一个关键空白，即传统基于 2D 的重建方法无法表示复杂的 3D 几何结构。通过实现可定向流形网格的实时增量重建，该方法允许操作员动态评估覆盖完整性。

其重要性在于能够：

区分缺失数据与未探索区域： 通过仅在数据“应当”被采集到的地方（基于边界长度阈值）识别孔洞，系统避免了将未探索区域误标为错误。
支持复杂几何结构： 与 DTM 不同，IBPA 能准确建模悬挑和垂直结构，这对于详细的海底测绘至关重要。
增强下游处理： 高保真几何数据可以提高摄影测量、神经辐射场（NeRF）和高斯泼溅（Gaussian Splatting）等后期处理技术的质量。
促进自主决策： 实时检测覆盖缺口为下一最佳视角（NBV）规划提供了可操作的反馈，允许机器人通过重新访问特定区域来闭合孔洞，从而在任务终止前完成采集。

作者总结道，IBPA 适用于实际水下机器人场景中的批量和流式重建流水线，为体积重建或非流形重建方法提供了一个鲁棒的替代方案。未来的工作重点在于提高边界边扫描的效率，以及开发无需完整网格扫描即可验证单边连通分量的方法。