2.4 体素网格与八叉树

2.4 体素网格与八叉树：给三维空间建索引

本节摘要：体素网格把空间切成规则立方体，是三维数据的"像素化"；八叉树是它的自适应版本，密集处细分、空旷处粗放。本节讲 VoxelGrid 的构造与查询、体素化过程中的信息取舍，八叉树的递归结构与插入/查询逻辑，并对比 KD 树、均匀体素、八叉树三种空间索引的适用场景，帮你在大场景近邻、占据判断、碰撞粗检等任务里选对工具。

本节导读

阅读完本节，你应当能够：

1. 从点云和网格两种来源构造体素网格与八叉树，说明各自保留和丢失了什么；
2. 计算体素化的量化误差，并按任务精度要求反推体素边长；
3. 解释八叉树"需要时才细分"的结构优势与查询复杂度特征；
4. 在 KD 树、均匀体素、八叉树之间按任务特性做出选择。

一、问题与直觉：空间查询为什么需要"铺地砖"

先看一个高频任务：机器人导航里每秒要回答上千次"这个位置是不是被挡住了"。如果拿原始点云回答，每次都要在百万点里找近邻——KD 树也要对数级时间。但换个思路：把空间切成 5 厘米的格子，每个格子记"有没有点"，查询退化为一次除法加一次查表，O(1)。

这就是体素化的本质：用精度换查询速度。代价也明摆着：5 厘米的格子抹掉了所有小于 5 厘米的细节，斜面变成台阶。所以体素化从来不是"要不要"的问题，而是"取多粗"的问题。

八叉树解决的是均匀体素的另一半痛点：一间 10×10×3 米的房间按 5 厘米切要 240 万个格子，其中九成五是空的（空气不挡路）。八叉树把空间递归二分——每个节点分八块，空块整个剪掉、密集块继续细分——存储与实际表面成正比，与场景总大小无关。

三种空间组织方式的对照图，配合正文的存储账一起读更有味道：同样的分辨率下，均匀体素的内存随体积三次方增长，八叉树只随表面积增长，KD 树随点数增长。这三条增长曲线决定了各自的势力范围——房间级的扫描谁都能扛，街区级的大场景必须剪枝，亿级点云的精确近邻只能 KD 树。做选型时不妨先估算三个数（场景体积、表面面积、点数），再对照曲线挑出内存最省的那个结构，这比「听说八叉树高级」式的选型靠谱得多。索引结构没有高下，只有与数据规模合不合身。

二、核心操作与代码

2.4.1 构造与查询

从点云构造体素网格，一行；从网格构造，一行；查某个体素的邻居，还是接近一行：

import open3d as o3d

pcd = o3d.io.read_point_cloud(o3d.data.PLYPointCloud().path)
grid = o3d.geometry.VoxelGrid.create_from_point_cloud(pcd, voxel_size=0.05)
print(grid)                          # 体素数量
print(grid.get_voxel_centers()[:3])  # 每个体素的中心坐标

octree = o3d.geometry.Octree(max_depth=6)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
octree.traverse(lambda node, depth: None)   # 遍历钩子，可统计每层节点
​

体素化时每个格子记的是落入该格子的点的平均位置与平均颜色（不是格子中心），这个细节让"体素中心转回点云"的路径保留了原始观测的加权信息。八叉树的 max_depth 与体素边长是同一个旋钮的两面：深度 d 时最小格子边长约为包围盒边长除以 2 的 d 次方。

2.4.2 八叉树的查询与射线

八叉树真正值钱的是三类查询，全部是"从根往下走，走不动就停"：

占据查询从根出发，每层判断目标点落在八个孩子中的哪一个，走到叶子看有没有数据——深度即复杂度，与点数无关。近邻查询先粗定位到叶子格子，再在格子内做小规模精算，避开了 KD 树在大场景下的长边遍历。射线相交（raycast bounding volume）是体渲染与激光雷达仿真的基础：只有与射线相交的子树才递归下去，空间大片剪枝。

2.4.3 体素化的量化误差

体素化的几何误差上界是体素对角线的一半（边长乘根号三除以二）。反着用更有价值：任务要求多准，体素就该多细。移动机器人避障要求 5 厘米精度，体素取 3 厘米即可；工件检测要 0.5 毫米精度，体素得压到 0.3 毫米，这时均匀体素的存储量会爆炸，必须换八叉树或干脆只用点云。

⚠️ 常见坑：把体素网格当点云用（取体素中心当点）做 ICP，分辨率粗时配准结果系统性偏差——量化误差不是随机噪声，平均不掉，它是有方向的。粗体素可以用来做粗配准初值，精细配准必须回到原始点云。

三、三种空间索引怎么选

选型三句话：要精确 K 近邻用 KD 树（Open3D 的配准内部就是它）；要判断"这块空间有没有东西"用体素；场景大而稀疏、还要动态插点用八叉树。真实系统经常三者混用：八叉树做全局剪枝，叶子内挂体素或小 KD 树，各司其职。

💡 关键直觉：空间索引的本质都是"用空间换时间"——预先花内存把空间组织好，查询时才能整片整片地跳过不可能区域。KD 树跳的是"距离不够近的半空间"，八叉树跳的是"空的孩子"，体素干脆把时间换成了除法。

四、动手上手：体素与八叉树各跑一遍

一段代码感受两种结构的构造与体感差异：

import open3d as o3d

pcd = o3d.io.read_point_cloud(o3d.data.PLYPointCloud().path)

# 体素网格：从点云构造
grid = o3d.geometry.VoxelGrid.create_from_point_cloud(pcd, voxel_size=0.05)
print("体素数:", len(grid.voxels))

# 体素上色与取中心（与官方示例一致的思路）
centers = grid.get_voxel_centers()
center_pcd = o3d.geometry.PointCloud()
center_pcd.points = o3d.utility.Vector3dVector(centers)
center_pcd.paint_uniform_color([0, 0, 1])        # 蓝色体素中心
o3d.visualization.draw_geometries([grid, center_pcd])

# 八叉树：从点云转换，最大深度 8
octree = o3d.geometry.Octree(max_depth=8)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
print("根节点尺寸:", octree.size)
​

把体素网格与体素中心点云同时画出来，能直观看到"格子+中心"的对应关系；换 voxel_size 为 0.02 与 0.1 各跑一次，体素数量会以立方速度增长或收缩——体素内存随边长三次方反比变化，这个体感对后面选参数至关重要。

八叉树侧值得做的实验是改 max_depth：深度 4 时只有粗粒度的大格子，深度 10 时细分到接近点级。观察每层节点数量（可用 traverse 钩子统计），会发现绝大多数节点集中在表面附近的几层，空旷区域早早剪枝——这就是"存储正比表面"的现场证据。

常见疑问

问：体素网格和 TSDF 体积（2.3 节）是什么关系？
答：VoxelGrid 是"占据+颜色"的离散表示；TSDF 是每个体素存"有符号距离+权重"的更丰富表示。前者回答"这里有没有东西"，后者回答"离最近表面多远"。底层数据结构思想同源，用途不同。

问：八叉树的 max_depth 怎么定？
答：由你要的最小格子尺寸反推：最小格 ≈ 包围盒边长 ÷ 2 的 depth 次方。想要 1 厘米格、场景 10 米，depth 至少 10。

问：体素化会改变点数统计口径吗？
答：会。体素化后"点数"变成"体素数"，两者不可直接比较——汇报数据规模时先说清口径，避免和同事鸡同鸭讲。

问：点云动态变化时，八叉树要重建吗？
答：八叉树支持增量插入，新点沿根往下找叶子挂上即可；删除点则麻烦些。频繁大改的场景，考虑定期重建或换体素哈希。

提到体素哈希，值得多说两句它与传统 VoxelGrid 的关系，这是近年大场景处理的关键进化。传统体素的"均匀网格"假设决定了它必须为空格子付内存（第五节算过这笔账）；体素哈希的做法是只分配"被观测到的块"——把空间按固定大小的块（block）划分，块内仍是均匀体素，但块的分配由哈希表管理，没观测过的块根本不存在于内存里。2.3 节 ScalableTSDFVolume 的"Scalable"正来源于此，Tensor 侧的 VoxelBlockGrid 把同一思想搬上了 GPU。三者关系一句话总结：均匀体素是数据结构教科书里的起点，八叉树与体素哈希是工程界对"空旷世界"的两份优化答卷——前者用层级剪枝、后者用按需分配，解决的问题相同。做项目选型时，场景小于一个房间用哪个都行，一到建筑、街区尺度，这个选择就开始影响内存账了。

五、深入一层：从均匀网格到八叉树的存储账

空间索引的选型，算一笔存储账就彻底清楚。设一个 10×10×3 米的房间，问：三种结构各要多少内存？

均匀体素：按 5 厘米切，格子数 = 200×200×60 = 240 万个。每个格子哪怕只存一个字节的占据标志，也要 2.4 MB；现实里还要存颜色或指针，轻松上 20 MB。其中大约 95% 的格子是空的——空气区域白白占了内存。切到 1 厘米时格子数暴涨 125 倍，300 MB 起步，内存预算直接爆表。

八叉树：同样 1 厘米分辨率，但只沿表面细分。房间表面约占空间的极小一部分，实际叶子节点数与"表面积 × 细分密度"成正比，而不是与"体积"成正比。经验上，同分辨率下八叉树的节点数比均匀网格少一到两个数量级。代价是每个节点要存八个孩子指针（或压缩的子树索引），单节点更重，但总量优势碾压。

KD 树：存储与点数线性相关，一百万点约几十 MB（含内部节点）。它与分辨率无关，与点数共生死——点云多大它就多大。

这笔账解释了一个工程现实：为什么大场景占据地图（机器人、AR）清一色用八叉树或体素哈希——它们的内存随"世界上有多少表面"增长，而不是随"世界有多大"增长。2.3 节的 ScalableTSDFVolume 内部用的体素哈希也是同一思想：把均匀三维数组换成"只分配被观测到的格子"的哈希表，内存问题釜底抽薪。

💡 记忆口诀：均匀网格为常数查询付出体积的代价，八叉树为稀疏世界省下体积的钱，KD 树为精确近邻付出点数的钱。谁的钱包（内存预算）多大，决定你能付哪种代价。

温故知新

• 体素化是精度换速度：查询退化为除法加查表，代价是半个体素级的量化误差，误差有方向、平均不掉。
• 八叉树是自适应体素：密集细分、空旷剪枝，存储正比表面而非场景体积。
• 三查询三式：占据、近邻、射线相交，全是根到叶的递归，复杂度看深度不看点数。
• 选型口诀：精确近邻 KD 树，占据判断体素，大而动态用八叉树；复杂系统三者混编。
• 体素边长由任务精度反推，同时决定均匀体素的内存量，爆内存就是换八叉树的信号。

第二章到此收官。下一章把镜头从数据转向"看"与"学"——高级可视化、Open3D-ML 与行业应用案例。