八叉树（Octree）

八叉树（octree）是一种树形数据结构，其中每个内部节点都有 8 个子节点。八叉树常用于三维点云的空间划分（spatial partitioning）。八叉树中非空的叶子节点包含落在同一空间细分区域内的一个或多个点。八叉树是对三维空间的一种有效描述，可用于快速查找邻近点。Open3D 提供了 Octree 这一几何类型，可用于创建、搜索和遍历八叉树，并支持用户指定的最大树深 max_depth。

从点云构建

可以使用 convert_from_point_cloud 方法由点云构建八叉树。每个点都沿着从根节点到 max_depth 深度处对应叶子节点的路径插入树中。随着树深增加，内部节点（以及最终的叶子节点）所代表的三维空间细分区域会越来越小。

如果点云带有颜色，则对应叶子节点会取最后插入点的颜色。size_expand 参数会增大根节点的尺寸，使其略大于原始点云的边界范围，从而容纳所有点。

print('input')
N = 2000

armadillo = o3d.data.ArmadilloMesh()
mesh = o3d.io.read_triangle_mesh(armadillo.path)
pcd = mesh.sample_points_poisson_disk(N)
# fit to unit cube
pcd.scale(1 / np.max(pcd.get_max_bound() - pcd.get_min_bound()),
          center=pcd.get_center())
pcd.colors = o3d.utility.Vector3dVector(np.random.uniform(0, 1, size=(N, 3)))
o3d.visualization.draw_geometries([pcd])

print('octree division')
octree = o3d.geometry.Octree(max_depth=4)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
o3d.visualization.draw_geometries([octree])

输出：

input
octree division

从体素网格构建

还可以使用 create_from_voxel_grid 方法，由 Open3D 的 VoxelGrid 几何体构建八叉树。输入 VoxelGrid 的每个体素都被当作三维空间中的一个点，其坐标对应于该体素的原点。每个叶子节点取其对应体素的颜色。

print('voxelization')
voxel_grid = o3d.geometry.VoxelGrid.create_from_point_cloud(pcd,
                                                            voxel_size=0.05)
o3d.visualization.draw_geometries([voxel_grid])

print('octree division')
octree = o3d.geometry.Octree(max_depth=4)
octree.create_from_voxel_grid(voxel_grid)
o3d.visualization.draw_geometries([octree])

输出：

voxelization
octree division

此外，可以使用 to_voxel_grid 将 Octree 转换为 VoxelGrid。

遍历

可以对八叉树进行遍历（traversal），这在搜索或处理三维几何体的子区域时非常有用。通过向 traverse 方法传入一个回调函数，每当访问一个节点（内部节点或叶子节点）时，就可以执行额外的处理。

下面的示例使用了一个提前终止（early stopping）判据，只处理包含点数超过一定数量的内部/叶子节点。这种提前终止能力可用于高效地处理满足特定条件的空间区域。

def f_traverse(node, node_info):
    early_stop = False

    if isinstance(node, o3d.geometry.OctreeInternalNode):
        if isinstance(node, o3d.geometry.OctreeInternalPointNode):
            n = 0
            for child in node.children:
                if child is not None:
                    n += 1
            print(
                "{}{}: Internal node at depth {} has {} children and {} points ({})"
                .format('    ' * node_info.depth,
                        node_info.child_index, node_info.depth, n,
                        len(node.indices), node_info.origin))

            # we only want to process nodes / spatial regions with enough points
            early_stop = len(node.indices) < 250
    elif isinstance(node, o3d.geometry.OctreeLeafNode):
        if isinstance(node, o3d.geometry.OctreePointColorLeafNode):
            print("{}{}: Leaf node at depth {} has {} points with origin {}".
                  format('    ' * node_info.depth, node_info.child_index,
                         node_info.depth, len(node.indices), node_info.origin))
    else:
        raise NotImplementedError('Node type not recognized!')

    # early stopping: if True, traversal of children of the current node will be skipped
    return early_stop

octree = o3d.geometry.Octree(max_depth=4)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
octree.traverse(f_traverse)

输出（缩进反映节点深度）：

0: Internal node at depth 0 has 8 children and 2000 points ([-2.37681206 31.11572638  1.96359967])
    0: Internal node at depth 1 has 4 children and 62 points ([-2.37681206 31.11572638  1.96359967])
    1: Internal node at depth 1 has 2 children and 46 points ([-1.87181206 31.11572638  1.96359967])
    2: Internal node at depth 1 has 8 children and 399 points ([-2.37681206 31.62072638  1.96359967])
        0: Internal node at depth 2 has 2 children and 6 points ([-2.37681206 31.62072638  1.96359967])
        1: Internal node at depth 2 has 1 children and 6 points ([-2.12431206 31.62072638  1.96359967])
        2: Internal node at depth 2 has 4 children and 42 points ([-2.37681206 31.87322638  1.96359967])
        3: Internal node at depth 2 has 1 children and 5 points ([-2.12431206 31.87322638  1.96359967])
        4: Internal node at depth 2 has 4 children and 59 points ([-2.37681206 31.62072638  2.21609967])
        5: Internal node at depth 2 has 5 children and 88 points ([-2.12431206 31.62072638  2.21609967])
        6: Internal node at depth 2 has 4 children and 74 points ([-2.37681206 31.87322638  2.21609967])
        7: Internal node at depth 2 has 6 children and 119 points ([-2.12431206 31.87322638  2.21609967])
    3: Internal node at depth 1 has 7 children and 372 points ([-1.87181206 31.62072638  1.96359967])
        0: Internal node at depth 2 has 1 children and 4 points ([-1.87181206 31.62072638  1.96359967])
        2: Internal node at depth 2 has 1 children and 5 points ([-1.87181206 31.87322638  1.96359967])
        3: Internal node at depth 2 has 4 children and 9 points ([-1.61931206 31.87322638  1.96359967])
        4: Internal node at depth 2 has 5 children and 83 points ([-1.87181206 31.62072638  2.21609967])
        5: Internal node at depth 2 has 3 children and 41 points ([-1.61931206 31.62072638  2.21609967])
        6: Internal node at depth 2 has 6 children and 114 points ([-1.87181206 31.87322638  2.21609967])
        7: Internal node at depth 2 has 6 children and 116 points ([-1.61931206 31.87322638  2.21609967])
    4: Internal node at depth 1 has 5 children and 340 points ([-2.37681206 31.11572638  2.46859967])
        0: Internal node at depth 2 has 3 children and 59 points ([-2.37681206 31.11572638  2.46859967])
        1: Internal node at depth 2 has 4 children and 97 points ([-2.12431206 31.11572638  2.46859967])
        2: Internal node at depth 2 has 2 children and 22 points ([-2.37681206 31.36822638  2.46859967])
        3: Internal node at depth 2 has 8 children and 142 points ([-2.12431206 31.36822638  2.46859967])
        7: Internal node at depth 2 has 1 children and 20 points ([-2.12431206 31.36822638  2.72109967])
    5: Internal node at depth 1 has 4 children and 319 points ([-1.87181206 31.11572638  2.46859967])
        0: Internal node at depth 2 has 8 children and 171 points ([-1.87181206 31.11572638  2.46859967])
        1: Internal node at depth 2 has 1 children and 1 points ([-1.61931206 31.11572638  2.46859967])
        2: Internal node at depth 2 has 8 children and 145 points ([-1.87181206 31.36822638  2.46859967])
        6: Internal node at depth 2 has 1 children and 2 points ([-1.87181206 31.36822638  2.72109967])
    6: Internal node at depth 1 has 6 children and 236 points ([-2.37681206 31.62072638  2.46859967])
    7: Internal node at depth 1 has 4 children and 226 points ([-1.87181206 31.62072638  2.46859967])

查找包含某点的叶子节点

借助上述遍历机制，可以快速在八叉树中搜索包含给定点的叶子节点。该功能由 locate_leaf_node 方法提供。

octree.locate_leaf_node(pcd.points[0])

输出：

(OctreePointColorLeafNode with color [0.550455, 0.986321, 0.874585] containing 5 points.,
 OctreeNodeInfo with origin [-1.80869, 31.1789, 2.59485], size 0.063125, depth 4, child_index 3)