3、点云空间分割：八叉树（Octree）原理、KD-Tree原理、体素网格（Voxel Grid）下采样
点云数据有多「密」？我举个例子你就明白了。一个64线激光雷达，每秒能产生上百万个点。这么多点直接传输，带宽根本扛不住。所以我们要做空间分割——说白了，就是把点云拆成小块，只保留关键信息。
这一章，我带你看看三种最常用的空间分割方法。它们各有各的脾气，用对了地方，效果立竿见影。
3.1 八叉树（Octree）原理
八叉树这个名字，听起来挺唬人。其实它的思想很简单：把三维空间像切西瓜一样，一刀一刀切成八块。
具体怎么切？先找一个立方体包围盒，把整个点云包住。然后把这个立方体均匀切成八个小立方体。每个小立方体里有点，就继续切；没点，就扔掉。一直切到每个小立方体里只剩一个点，或者达到你设定的最小尺寸。
我刚开始做点云压缩时，就踩过一个坑。当时我设的八叉树深度太浅，结果压缩率上不去。后来调深了，又发现重建精度下降。嗯，这里要注意：深度和精度是一对矛盾体。
- 最大深度：决定了分割的精细程度。深度越大，空间划分越细，但存储开销也越大。
- 最小点数：每个叶子节点最少包含的点数。设成1就是最精细，设成10就是粗粒度压缩。
- 包围盒尺寸：必须能完整包住所有点云，否则会丢失数据。
八叉树最大的好处是什么？是空间局部性。相邻的点大概率落在同一个或相邻的节点里。这对后续的编码压缩非常有利。我在做自动驾驶点云传输时，就利用这个特性，把压缩率做到了15:1以上。
3.2 KD-Tree原理
KD-Tree和八叉树不一样。八叉树是「一刀切八块」，KD-Tree是「一刀切两半」。它每次只沿着一个维度切，切完左边一堆，右边一堆。
你可能会问：那沿着哪个维度切？答案是：选点云分布最分散的那个维度。说白了，就是方差最大的那个轴。这样切出来的左右子树，点云分布更均匀，搜索效率更高。
我记得有一次做点云配准，用KD-Tree做最近邻搜索。一开始没注意切分策略，结果搜索速度慢得像蜗牛。后来改成中值切分，速度直接提升了3倍。你想想看，这就是选对切分维度的威力。
KD-Tree的构建过程，其实就是一个递归的二分过程：
// 伪代码：KD-Tree构建
function buildKDTree(points, depth):
if points.length == 0: return null
// 选择切分维度：轮流使用x,y,z
axis = depth % 3
// 按axis维度排序，取中值
sort(points, by=axis)
median = points[points.length/2]
// 递归构建左右子树
node = new Node(median)
node.left = buildKDTree(left_points, depth+1)
node.right = buildKDTree(right_points, depth+1)
return node3.3 体素网格（Voxel Grid）下采样
体素网格下采样，是我个人最常用的方法。为什么？因为它简单、高效、可控。
它的原理特别直白：把空间划分成一个个小立方体（体素），每个体素里只保留一个点。这个点可以是体素内所有点的重心，也可以是离体素中心最近的那个点。
我做过一个对比实验：用体素网格下采样把100万点的点云压缩到10万点，重建后的形状几乎看不出差别。但传输带宽节省了90%。这就是体素网格的魅力——用最小的代价，换取最大的压缩收益。
| 特性 | 体素网格 | 八叉树 | KD-Tree |
|---|---|---|---|
| 构建速度 | 最快 | 中等 | 较慢 |
| 压缩率 | 可控（体素大小决定） | 高（深度决定） | 中等 |
| 搜索效率 | 低 | 高 | 最高 |
| 适用场景 | 下采样、预处理 | 压缩、传输 | 最近邻搜索、配准 |
体素网格下采样有一个关键参数：体素大小。设得太小，压缩效果不明显；设得太大，点云细节丢失严重。我一般建议从点云平均点间距的2-3倍开始试。比如你的点云平均点间距是5cm，那体素大小就设10-15cm。
3.4 三种方法的对比与选择
说了这么多，到底该用哪个？我给你一个简单的判断标准：
- 做压缩传输：首选八叉树。它的层次化结构天然适合渐进式传输。
- 做预处理下采样：首选体素网格。速度快，效果好，参数少。
- 做点云搜索/配准：首选KD-Tree。搜索效率最高，尤其适合静态点云。
当然，实际项目中往往是组合使用。比如我做过的一个系统：先用体素网格做粗粒度下采样，再用八叉树做精细压缩，最后用KD-Tree做接收端的点云重建。三种方法各司其职，效果非常好。
最后说一句：没有最好的方法，只有最合适的方法。多试、多调、多对比，你就能找到最适合你场景的方案。
公众号:蓝海资料掘金营，微信deep3321