Octree

又称: sparse voxel octree
类别: Sensing › 3D maps & reconstruction
标签: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds

一种树形数据结构，它把 3D 空间递归地划分为八个立方体，只在有数据的地方分配精细单元，以获得紧凑的地图和快速的空间查询。

定义

八叉树（Octree）是这样一种树：每个节点代表空间中的一个立方体，最多可以有八个子节点，每个子节点对应把该立方体沿三个轴各二等分后得到的一个卦限。根节点覆盖整个体积；每向下一层，单元尺寸减半。只有在存在有意义的内容（例如测得的表面点）的地方，分支才会被细分，因此大片空的或未观测的区域仍保持为单个粗糙节点。八叉树由 Donald Meagher 于 1980 年代初为实体建模而提出，如今已成为图形学、点云处理和机器人建图中的标准方法。

它的主要吸引力在于内存。在大型建筑上以精细分辨率建立的稠密体素网格需要为每个单元分配存储，而八叉树的存储量大致随观测到的表面积增长。它还提供多分辨率访问：规划器可以查询粗糙单元进行快速检查，再向下深入获取细节。在 Hornung 及其同事开发的广泛使用的库 OctoMap 中，每个叶节点以对数几率（log-odds）形式保存一个概率占据值，并根据距离测量进行更新，因此地图能区分占据、空闲和未知空间。状态相同的子节点会被剪枝合并回其父节点，以节省内存。

八叉树以一定的速度换取这种紧凑性：到达一个叶节点需要沿树向下遍历，这比索引一个扁平数组要慢。体素哈希和 VDB 结构等替代方案在某些工作负载下访问更快。八叉树也被用于加速点云上的最近邻搜索和碰撞检测；在近期的神经建图系统中，它们用于组织存储学习特征的稀疏体素，并随着新的深度帧到来而增量生长。

为何重要

机器人需要以有用的分辨率覆盖大片区域、又不耗尽内存的 3D 地图。八叉树让这一点成为现实，它们也是操作和空中导航中常用的占据建图和碰撞检测工具的基础。

主要应用

用 OctoMap 进行概率 3D 占据建图
机械臂和无人机的碰撞检测
点云上的最近邻搜索和半径搜索
用于神经隐式建图和稠密建图的稀疏体素结构
点云压缩和细节层次渲染

实际应用

一个为在仓库中飞行的无人机构建 3D 地图的团队，把深度相机或激光雷达的点云连同其里程计给出的位姿，以几厘米的分辨率输入 OctoMap。每条光线把它经过的单元标记为更可能空闲，把它末端的单元标记为更可能被占据。规划器沿候选路径查询八叉树中的占据情况，并把未知空间当作障碍物。在机械臂上，MoveIt 可以从深度传感器获取同类的八叉树，使手臂的规划场景保持最新。工程师调节分辨率、传感器量程以及命中和未命中概率，以在细节、内存以及移动物体被清除的速度之间取得平衡。

常见误解

八叉树与体素网格是一回事 — 体素网格存储每一个单元，而八叉树只在需要的地方细分，并合并均匀的区域
八叉树总是比扁平网格更快 — 它们节省内存，但每次查找都要遍历树，因此对某些查询而言，稠密网格或哈希网格可能更快
八叉树中的空白空间意味着空闲空间 — 在占据八叉树中，未观测的空间是未知的，规划器通常应把它与空闲空间区别对待

谁需要了解

建图和 SLAM 工程师
运动规划和碰撞检测开发者
在 3D 环境中工作的无人机自主工程师
神经建图和稠密建图系统的开发者

视频

Using Octrees and A* for Efficient Pathfinding: git-amend

维基百科

八叉树

Open Source Robotics