OCtree
octree 是一个树数据结构，其中每个内部节点有八个子节点。八叉树通常用于 3D 点云的空间分区。八叉树的非空叶节点包含一个或多个位于同一空间细分内的点。Octrees是对3D空间的有用描述，可用于快速查找附近的点。Open3D 具有Octree类型，可用于创建、搜索和遍历具有用户指定的最大树深度的八进制,max_depth.
From point cloud 从点云
可以使用convert_from_point_cloud方法从点云构造八叉树。每个
可以使用convert_from_point_cloud方法从点云构造八叉树。每个点都是通过沿着从根节点到深度max_depth的相应叶节点的路径插入到树中的。随着树深度的增加，内部（最终是叶）节点表示 3D 空间的较小分区。
如果点云具有颜色，则相应的叶节点将采用最后插入点的颜色。参数size_expand增加根八叉节点的大小，使其略大于原始点云边界以容纳所有点。
import open3d as o3d import numpy as np print('input') N = 2000 armadillo_path = r'../data/ArmadilloMesh.ply' 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])
From voxel grid 从体素网格
八叉树也可以使用create_from_voxel_grid方法从Open3D几何体VoxelGrid构建。输入VoxelGrid的每个体素都被视为3D空间中的一个点，其坐标对应于原始体素。每个叶节点都采用其相应体素的颜色。
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])
另外, Octree 可以通过to_voxel_grid转化为VoxelGrid。
Traversal 遍历
可以遍历八叉树，这对于搜索或处理3D几何体的子部分非常有用。通过为traverse方法提供回调，每次访问节点（内部或叶）时，都可以执行其他处理。
在下面的示例中，早期停止条件用于仅处理点数超过一定数量的内部/叶节点。这种早期停止能力可用于有效地处理满足特定条件的空间区域。
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)
Find leaf node containing point 查找包含点的叶节点
使用上述遍历机制，可以快速搜索八叉树以查找包含给定点的叶节点。此功能通过locate_leaf_node方法提供。
octree.locate_leaf_node(pcd.points[0])
