octree
An octree is a tree data structure in which each internal node
has exactly eight children.
Octrees are most often used to partition a three-dimensional space
by recursively subdividing it into eight octants.
Octrees are the three-dimensional analog of quadtrees.
The name is formed from oct + tree,
but note that it is normally written “octree” with only one “t”.
Octrees are often used in 3D graphics and 3D game engines.
#
Left: Recursive subdivision of a cube into octants.
Right: The corresponding octree.
八叉树 想象一下一个正方形的方块的三个面各切一刀 不就变成八块了嘛
实际的数据结构呢 就是一个树根不断地往下扩 每次分成八个枝 直到叶子为止.
叶子节点代表了分辨率最高的情况.
例如分辨率设成 0.01 m 那么每个叶子就是一个 1 cm 见方的小方块了呢
每个小方块都有一个数描述它是否被占据.
在最简单的情况下 可以用 0 1 两个数表示(太简单了所以没什么用).
通常还是用 0 ~ 1 之间的浮点数表示它被占据的概率.
0.5 表示未确定, 越大则表示被占据的可能性越高, 反之亦然.
由于它是八叉树, 那么一个节点的八个孩子都有一定的概率被占据或不被占据啦
用树结构的好处时: 当某个节点的子结点都 占据 或 不占据 或 未确定 时, 就可以把它给剪掉
换句话说 如果没必要进一步描述更精细的结构(孩子节点)时,
只要一个粗方块(父节点)的信息就够了.
这可以省去很多的存储空间. 因为我们不用存一个 全八叉树.
在八叉树中 我们用概率来表达一个叶子是否被占据.
为什么不直接用 0 1 表达呢?
因为在对环境的观测过程中 由于噪声的存在 某个方块有时可能被观测到是 占据 的
过了一会儿 在另一些方块中又是 不占据 的.
有时 占据 的时候多 有时 不占据 的时候多.
这一方面可能是由于环境本身有动态特征(例如桌子被挪走了),
另一方面(多数时候)可能是由于噪声.
根据八叉树的推导, 假设 t = 1, … ,T 时刻, 观测的数据为 z1, … , zT
那么第 n 个叶子节点记录的信息为:
(每新来一个就直接加到原来的上面)
八叉树中的父亲节点占据概率 可以根据孩子节点的数值进行计算.
比较简单的是取平均值或最大值. 如果把八叉树按照占据概率进行渲染,
不确定的方块渲染成透明的, 确定占据的渲染成不透明的, 就能看到我们平时见到的那种东西