八叉树(Octree)

定义

八叉树(Octree)是四叉树在三维空间的推广:每个内部节点把所辖的立方体区域沿三个轴对半切分,得到八个子立方体,递归细分直至满足终止条件。

原理

八叉树对三维空间做自适应分辨率的层级划分:数据稠密处细分得深,空旷处保持粗粒度,从而在精度与内存之间取得平衡。叶子节点可存储点、体素占据状态或距离场等信息。

应用

点云处理库 PCL 用八叉树做压缩、近邻搜索与空间变化检测;机器人领域的 OctoMap 用概率八叉树表示三维占据栅格地图;图形学中八叉树用于视锥剔除、碰撞检测、光线投射加速以及稀疏体素八叉树(SVO)渲染;三维重建与 Minecraft 类体素引擎也大量使用。

优缺点

优点是内存随场景稀疏程度自适应、层级结构天然支持多分辨率查询;缺点是指针开销较大、频繁动态更新代价高,GPU 上的实现也比规则网格复杂。