三维点云处理（九）：Octree 八叉树自适应空间细分
在上一章中，KD-Tree 通过交替坐标轴划分实现了 的邻域搜索。然而，KD-Tree 的划分方式并不感知空间中点的密度分布。
Octree（八叉树） 采用了不同的策略：将空间递归地八等分（8 个子卦限），仅在有数据存在的子空间中继续细分。这种“有数据才细分”的策略使得 Octree 天然适合三维点云的层次化表达、压缩存储和体素化处理。
八叉树立体划分几何直觉
一、Octree 的结构原理
1.1 八分递归
Octree 的每个节点代表一个立方体空间区域（Axis-Aligned Bounding Box, AABB）。一个有子节点的内部节点拥有恰好 个子节点，分别对应该立方体被三个正交平面切分后的八个子立方体。
8 个子节点 = {000, 001, 010, 011, 100, 101, 110, 111} 每个二进制位对应 xyz 坐标是否在父节点中心的上方(1)或下方(0)
1.2 节点数据结构
python
from dataclasses import dataclass, field
import numpy as np
from typing import List, Optional
@dataclass
class OctreeNode:
"""八叉树节点"""
# 空间范围：该节点表示的立方体
center: np.ndarray # 立方体中心 (3,)
half_size: float # 立方体半边长
# 节点数据
points: List[np.ndarray] = field(default_factory=list) # 该节点包含的点
point_indices: List[int] = field(default_factory=list) # 点在原始数组中的索引
# 子节点 (恰好 8 个或 0 个)
children: List[Optional['OctreeNode']] = field(default_factory=lambda: [None] * 8)
# 节点类型
is_leaf: bool = True
depth: int = 0
@property
def size(self):
"""节点立方体边长"""
return 2 * self.half_size
def get_child_index(center, half_size, point):
"""
确定点落入哪个子节点。
八分索引编码:
第 0 位 (位掩码 1): x > center[0] ? 1 : 0
第 1 位 (位掩码 2): y > center[1] ? 1 : 0
第 2 位 (位掩码 4): z > center[2] ? 1 : 0
返回 0~7 的整数索引。
"""
child_idx = 0
if point[0] > center[0]:
child_idx |= 1 # 设置第 0 位
if point[1] > center[1]:
child_idx |= 2 # 设置第 1 位
if point[2] > center[2]:
child_idx |= 4 # 设置第 2 位
return child_idx
def get_child_center(parent_center, parent_half_size, child_index):
"""计算指定子节点的中心坐标"""
child_half = parent_half_size / 2
offset = np.array([
child_half if (child_index & 1) else -child_half,
child_half if (child_index & 2) else -child_half,
child_half if (child_index & 4) else -child_half,
])
return parent_center + offset二、Octree 的构建
2.1 构建算法
2.2 构建实现
python
def build_octree(points, max_points_per_leaf=32, max_depth=10):
"""
递归构建 Octree。
:param points: N x 3 的 NumPy 点云数组
:param max_points_per_leaf: 叶子节点最大点数
:param max_depth: 最大递归深度
:return: OctreeNode (根节点)
"""
if points.shape[0] == 0:
return None
# 1. 计算完整包围盒
min_bound = np.min(points, axis=0)
max_bound = np.max(points, axis=0)
center = (min_bound + max_bound) / 2.0
half_size = np.max(max_bound - min_bound) / 2.0 * 1.01 # 稍微放大避免边界问题
# 2. 创建根节点
root = OctreeNode(
center=center,
half_size=half_size,
depth=0
)
# 3. 初始化根节点的点列表
indices = list(range(points.shape[0]))
root.points = [p for p in points]
root.point_indices = indices
# 4. 递归构建
_build_recursive(root, points, max_points_per_leaf, max_depth)
return root
def _build_recursive(node, all_points, max_per_leaf, max_depth):
"""递归构建子树"""
if node.depth >= max_depth:
return
if len(node.points) <= max_per_leaf:
return
# 八等分
node.is_leaf = False
child_points = [[] for _ in range(8)]
child_indices = [[] for _ in range(8)]
for i, pt in enumerate(node.points):
child_idx = get_child_index(node.center, node.half_size, pt)
child_points[child_idx].append(pt)
child_indices[child_idx].append(node.point_indices[i])
# 递归构建每个非空子节点
for idx in range(8):
if len(child_points[idx]) == 0:
continue
child_center = get_child_center(node.center, node.half_size, idx)
child = OctreeNode(
center=child_center,
half_size=node.half_size / 2,
points=child_points[idx],
point_indices=child_indices[idx],
depth=node.depth + 1
)
node.children[idx] = child
_build_recursive(child, all_points, max_per_leaf, max_depth)三、Octree 的搜索算法
3.1 K 近邻搜索
python
def octree_knn_search(root, query_point, k=1):
"""
基于 Octree 的 K 近邻搜索。
策略：
1. 从根开始，定位 query_point 所在的叶子节点
2. 以该叶子中的点初始化 K 近邻集合
3. 向外扩张搜索：检查相邻节点（通过计算节点包围盒到查询点的最小距离）
"""
import heapq
best_heap = [] # (-distance, point_index, point)
def _point_to_node_min_dist(query, node):
"""
计算查询点到节点包围盒的理论最小距离。
如果查询点在包围盒内部，则距离为 0。
"""
d2 = 0.0
for dim in range(3):
lower = node.center[dim] - node.half_size
upper = node.center[dim] + node.half_size
if query[dim] < lower:
d2 += (lower - query[dim]) ** 2
elif query[dim] > upper:
d2 += (query[dim] - upper) ** 2
# else: 查询点在这个维度上位于包围盒内部，距离贡献为 0
return np.sqrt(d2)
def _search(node):
if node is None:
return
# 剪枝：如果节点包围盒到查询点的最小距离大于当前第 K 近的距离，跳过
worst_dist = -best_heap[0][0] if len(best_heap) >= k else np.inf
node_min_dist = _point_to_node_min_dist(query_point, node)
if node_min_dist >= worst_dist:
return
if node.is_leaf:
# 检查叶子节点中的所有点
for pt, pt_idx in zip(node.points, node.point_indices):
dist = np.linalg.norm(pt - query_point)
heapq.heappush(best_heap, (-dist, pt_idx, pt))
if len(best_heap) > k:
heapq.heappop(best_heap)
else:
# 按子节点到查询点的距离排序，优先搜索最近的子节点
child_distances = []
for child_idx, child in enumerate(node.children):
if child is not None:
min_d = _point_to_node_min_dist(query_point, child)
child_distances.append((min_d, child))
child_distances.sort(key=lambda x: x[0])
for _, child in child_distances:
# 再次检查剪枝条件
cur_worst = -best_heap[0][0] if len(best_heap) >= k else np.inf
if _point_to_node_min_dist(query_point, child) < cur_worst:
_search(child)
_search(root)
# 提取排序结果
result = sorted(best_heap, key=lambda x: -x[0])
distances = np.array([-r[0] for r in result])
indices = np.array([r[1] for r in result])
return distances, indices3.2 半径搜索
python
def octree_radius_search(root, query_point, radius):
"""
基于 Octree 的半径搜索。
返回所有距离 ≤ radius 的点。
"""
results = []
def _point_to_node_max_dist(query, node):
"""计算查询点到节点包围盒的理论最大距离"""
corners = []
for dx in [-1, 1]:
for dy in [-1, 1]:
for dz in [-1, 1]:
corner = node.center + node.half_size * np.array([dx, dy, dz])
corners.append(np.linalg.norm(corner - query))
return max(corners)
def _search(node):
if node is None:
return
# 全包含快速通道：如果包围盒完全在球内，直接添加所有点
max_d = _point_to_node_max_dist(query_point, node)
if max_d <= radius and node.is_leaf:
for pt, pt_idx in zip(node.points, node.point_indices):
results.append((pt_idx, np.linalg.norm(pt - query_point), pt))
return
# 剪枝
min_d = 0.0
for dim in range(3):
lower = node.center[dim] - node.half_size
upper = node.center[dim] + node.half_size
if query_point[dim] < lower:
min_d += (lower - query_point[dim]) ** 2
elif query_point[dim] > upper:
min_d += (query_point[dim] - upper) ** 2
if np.sqrt(min_d) > radius:
return
if node.is_leaf:
for pt, pt_idx in zip(node.points, node.point_indices):
dist = np.linalg.norm(pt - query_point)
if dist <= radius:
results.append((pt_idx, dist, pt))
else:
for child in node.children:
_search(child)
_search(root)
results.sort(key=lambda x: x[1])
return ([r[0] for r in results],
[r[1] for r in results],
[r[2] for r in results])四、Open3D 中的 Octree
python
import open3d as o3d
import numpy as np
def open3d_octree_demo():
"""演示 Open3D 内置 Octree 功能"""
# 创建点云
pcd = o3d.geometry.PointCloud()
pcd.points = o3d.utility.Vector3dVector(np.random.randn(5000, 3) * 2)
# 构建 Octree（最大深度 8）
octree = o3d.geometry.Octree(max_depth=8)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
print(f"Octree 根节点: origin={octree.origin}, size={octree.size}")
# 遍历叶子节点
def count_leaves(node, node_info):
if isinstance(node, o3d.geometry.OctreeLeafNode):
if len(node.indices) > 0:
print(f" 叶子节点 [{node_info.origin}], "
f"size={node_info.size}, "
f"点数={len(node.indices)}")
print("\n叶子节点列表:")
octree.traverse(count_leaves)
# 定位某个点所在的叶子节点
query_point = pcd.points[0]
leaf, node_info = octree.locate_leaf_node(query_point)
print(f"\n查询点 {query_point} 所在的叶子节点: origin={node_info.origin}")
return octree五、Octree 的核心应用
5.1 真实的 Octree 体素化下采样 (Voxel Downsampling)
在很多通用教程中，体素下采样是通过计算 hash(x,y,z) 来实现的（如第六章所述）。但在使用 Octree 时，由于Octree 的每一个叶子节点 (Leaf Node) 本身就是一个固定大小的体素，下采样过程变得极其自然优雅：
算法步骤：
- 指定最大深度 构建 Octree（这决定了最终的体素分辨率）。
- 遍历所有深度的叶子节点。
- 对于每个非空叶子节点，计算其内部包含的所有点的质心（或直接取叶子节点的中心点
node.origin），作为下采样后的代表点。
python
def octree_voxel_downsample(pcd, max_depth=6):
"""
利用真正的 Octree 叶子节点进行下采样。
"""
octree = o3d.geometry.Octree(max_depth=max_depth)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
down_points = []
def extract_leaf_centers(node, node_info):
if isinstance(node, o3d.geometry.OctreeLeafNode):
# 将该体素叶子内的点聚合成一个代表点 (此处简单取叶子中心)
# 更精确的做法是记录原始点索引并计算质心
down_points.append(node_info.origin)
octree.traverse(extract_leaf_centers)
down_pcd = o3d.geometry.PointCloud()
down_pcd.points = o3d.utility.Vector3dVector(np.array(down_points))
return down_pcd5.2 多分辨率分析（LOD）
Octree 天然支持多级细节层次（Level of Detail, LOD）：
python
def extract_lod(octree, max_depth):
"""从 Octree 中提取指定深度的 LOD 点集"""
points = []
def _collect(node, node_info):
if isinstance(node, o3d.geometry.OctreeInternalNode):
if node_info.depth >= max_depth:
points.append(node_info.origin)
# 如果未到目标深度，traverse 会继续深入子节点
# 重建 Octree 的 LOD 提取
# （注：此处为示意，Open3D 的 Octree.traverse 会自动处理深度）
return np.array(points)5.3 点云压缩与序列化
Octree 的结构可以用二进制流高效编码：每个内部节点用 8 bits 表示哪些子节点非空，叶子节点存储点数据。这使得 Octree 成为点云压缩标准（如 MPEG G-PCC）的核心数据结构。
text
二进制编码示意 (每个节点一个字节):
根节点: 11100000 → 子节点 0,1,2 非空
节点 0: 10100000 → 子节点 0,2 非空
节点 1: 00000000 → 叶子节点（全0表示无子节点）
...
这种编码方式在存储和网络传输中极其高效。5.4 快速碰撞检测与相交测试 (Collision Detection)
在机器人路径规划、无人机避障以及三维游戏引擎中，经常需要检测一个物体（例如无人机的包围盒）是否与环境点云发生碰撞，或者光线是否击中物体（光线投射 Ray Casting）。Octree 是解决此类问题的核心：
- AABB 快速重叠测试：当检测无人机的边界盒 是否撞墙时，不需要遍历点云。只需从 Octree 根节点开始，测试 是否与当前子节点的包围盒相交。如果不相交，直接剪枝跳过整个子树；如果相交且深入到了包含实际点云的叶子节点，则确认发生碰撞。这能将千万级点云的碰撞检测压缩到微秒级。
- 光线投射 (Ray Casting)：用于模拟 LiDAR 传感器或相机视线遮挡。从光源发射射线，通过参数方程快速求交 Octree 各层包围盒。一旦在极近的叶子节点发现交点，射线即被遮挡，无需再向后计算。
六、Octree vs KD-Tree 详细对比
| 特性 | Octree | KD-Tree |
|---|---|---|
| 划分策略 | 空间八等分（固定） | 数据中位数（自适应） |
| 平衡性 | 空间平衡，数据可能不平衡 | 数据平衡（树高 ） |
| 空洞处理 | 空区域被合并跳过 | 不处理空洞 |
| 最近邻搜索 | （需处理跨体素） | （剪枝更优） |
| 半径搜索 | 可直接跳过大片空白区域 | 依赖剪枝策略 |
| 体素操作 | 天然适配 | 不适合 |
| 增删点 | 需局部重构 | 树的旋转/重构更复杂 |
| 压缩存储 | 优秀（二进制编码） | 一般 |
七、项目工程实战与算法选型映射
Octree（八叉树）在实际工程中主要用于规则体素数据管理、体数据视切与大体量点云网格层次过滤。
7.1 八叉树选型优势
- 规则体数据天然匹配：对于 CBCT（锥束 CT）等三维体素网格（
vtkImageData），Octree 的 8 分割能完美自适应 DICOM 体素空间。 - Empty Voxel Skipping（空体素剪枝跳过）：在渲染或 Marching Cubes 等值面抽取时，直接剪枝跳过不含空气/骨骼的空白正方体盒，极大降低迭代开销。
7.2 关联项目实际应用与文档索引
1. JMScan-face (CBCT 三维人脸扫描系统)
- CBCT DICOM 体数据四宫格 MPR 视切：利用 Octree 空间分割对
vtkImageData进行层次管理与三维切面联动。详见 [01-VTK渲染管线与四宫格MPR视切.md](file:///c:/Users/tolcf/Nutstore/1/blog/JMScan-face_ProjectDetails/04-CT三维渲染与四宫格视切/01-VTK渲染管线与四宫格MPR视切.md)。 - CloudCompare CCLib SCALE_ICP 配准：在百万级面扫点云配准中，基于 Octree 进行大空间体素盒网格预筛选，提高最近邻查找效率。详见 [03-DICOM选点与ICP精配库集成.md](file:///c:/Users/tolcf/Nutstore/1/blog/JMScan-face_ProjectDetails/03-点云配准与ROI优化/03-DICOM选点与ICP精配库集成.md)。
- LOD 多分辨率渲染：基于 Octree 控制遍历深度，按需提取不同分辨率点云/网格 LOD 结构，提升高频渲染帧率。详见 [02-三维Manipulator操纵杆与LOD优化.md](file:///c:/Users/tolcf/Nutstore/1/blog/JMScan-face_ProjectDetails/04-CT三维渲染与四宫格视切/02-三维Manipulator操纵杆与LOD优化.md)。
2. JMColor 智能贴图系统
- 高密度网格泊松等值面重建：在 MVS 稠密重建
meshing阶段，利用八叉树自适应空间采样建立隐式函数指示场。详见 [04-稠密重建与构网.md](file:///c:/Users/tolcf/Nutstore/1/blog/JMColor_ProjectDetails/02-照片建模流程/04-稠密重建与构网.md)。
总结
Octree 是三维点云处理中"空间驱动"的索引结构，其核心优势在于：
- 自适应密度：只有含数据的区域才会被继续细分，避免了 KD-Tree 在稀疏区域的浪费。
- 体素操作天然适配：体素下采样、体素融合、碰撞检测等。
- 多分辨率表达：通过控制遍历深度，可获取不同精度的 LOD。
- 高效压缩：8-bit 子节点掩码 + 叶子数据 = 极简的二进制序列化。
对于大规模非均匀分布的点云（如室外 LiDAR 扫描数据），Octree 往往是比 KD-Tree 更优的选择。
下一章将进入聚类算法模块，从聚类算法简介开始，学习如何在点云中自动发现物体和区域。