Octree

An octree is a tree data structure where each internal node has eight children. Octrees are commonly used for spatial partitioning of 3D point clouds. Non-empty leaf nodes of an octree contain one or more points that fall within the same spatial subdivision. Octrees are a useful description of 3D space and can be used to quickly find nearby points. Open3D has the geometry type Octree that can be used to create, search, and traverse octrees with a user-specified maximum tree depth, max_depth.

From point cloud

An octree can be constructed from a point cloud using the method convert_from_point_cloud. Each point is inserted into the tree by following the path from the root node to the appropriate leaf node at depth max_depth. As the tree depth increases, internal (and eventually leaf) nodes represents a smaller partition of 3D space.

If the point cloud has color, the the corresponding leaf node takes the color of the last inserted point. The size_expand parameter increases the size of the root octree node so it is slightly bigger than the original point cloud bounds to accommodate all points.

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
[Open3D WARNING] GLFW Error: Failed to detect any supported platform
[Open3D INFO] [Visualizer] No display detected, falling back to EGL offscreen rendering.
[Open3D INFO] EGLOffscreenContext: created 1920x1080 offscreen GPU context (EGL 1.5, vendor: Mesa Project).

octree division
[Open3D WARNING] GLFW Error: Failed to detect any supported platform
[Open3D INFO] [Visualizer] No display detected, falling back to EGL offscreen rendering.
[Open3D INFO] EGLOffscreenContext: created 1920x1080 offscreen GPU context (EGL 1.5, vendor: Mesa Project).

From voxel grid

An octree can also be constructed from an Open3D VoxelGrid geometry using the method create_from_voxel_grid. Each voxel of the input VoxelGrid is treated as a point in 3D space with coordinates corresponding to the origin of the voxel. Each leaf node takes the color of its corresponding voxel.

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
[Open3D WARNING] GLFW Error: Failed to detect any supported platform
[Open3D INFO] [Visualizer] No display detected, falling back to EGL offscreen rendering.
[Open3D INFO] EGLOffscreenContext: created 1920x1080 offscreen GPU context (EGL 1.5, vendor: Mesa Project).

octree division
[Open3D WARNING] GLFW Error: Failed to detect any supported platform
[Open3D INFO] [Visualizer] No display detected, falling back to EGL offscreen rendering.
[Open3D INFO] EGLOffscreenContext: created 1920x1080 offscreen GPU context (EGL 1.5, vendor: Mesa Project).

Additionally, an Octree can be converted to a VoxelGrid with to_voxel_grid.

Traversal

An octree can be traversed which can be useful for searching or processing subsections of 3D geometry. By providing the traverse method with a callback, each time a node (internal or leaf) is visited, additional processing can be performed.

In the following example, an early stopping criterion is used to only process internal/leaf nodes with more than a certain number of points. This early stopping ability can be used to efficiently process spatial regions meeting certain conditions.

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.76526999 31.2406216   1.95735462])
    0: Internal node at depth 1 has 4 children and 74 points ([-2.76526999 31.2406216   1.95735462])
    1: Internal node at depth 1 has 2 children and 49 points ([-2.26026999 31.2406216   1.95735462])
    2: Internal node at depth 1 has 8 children and 409 points ([-2.76526999 31.7456216   1.95735462])
        0: Internal node at depth 2 has 2 children and 5 points ([-2.76526999 31.7456216   1.95735462])
        1: Internal node at depth 2 has 1 children and 7 points ([-2.51276999 31.7456216   1.95735462])
        2: Internal node at depth 2 has 4 children and 43 points ([-2.76526999 31.9981216   1.95735462])
        3: Internal node at depth 2 has 1 children and 3 points ([-2.51276999 31.9981216   1.95735462])
        4: Internal node at depth 2 has 4 children and 63 points ([-2.76526999 31.7456216   2.20985462])
        5: Internal node at depth 2 has 5 children and 93 points ([-2.51276999 31.7456216   2.20985462])
        6: Internal node at depth 2 has 4 children and 70 points ([-2.76526999 31.9981216   2.20985462])
        7: Internal node at depth 2 has 6 children and 125 points ([-2.51276999 31.9981216   2.20985462])
    3: Internal node at depth 1 has 7 children and 369 points ([-2.26026999 31.7456216   1.95735462])
        0: Internal node at depth 2 has 1 children and 7 points ([-2.26026999 31.7456216   1.95735462])
        2: Internal node at depth 2 has 1 children and 6 points ([-2.26026999 31.9981216   1.95735462])
        3: Internal node at depth 2 has 3 children and 11 points ([-2.00776999 31.9981216   1.95735462])
        4: Internal node at depth 2 has 4 children and 87 points ([-2.26026999 31.7456216   2.20985462])
        5: Internal node at depth 2 has 4 children and 46 points ([-2.00776999 31.7456216   2.20985462])
        6: Internal node at depth 2 has 6 children and 108 points ([-2.26026999 31.9981216   2.20985462])
        7: Internal node at depth 2 has 6 children and 104 points ([-2.00776999 31.9981216   2.20985462])
    4: Internal node at depth 1 has 5 children and 342 points ([-2.76526999 31.2406216   2.46235462])
        0: Internal node at depth 2 has 3 children and 59 points ([-2.76526999 31.2406216   2.46235462])
        1: Internal node at depth 2 has 4 children and 98 points ([-2.51276999 31.2406216   2.46235462])
        2: Internal node at depth 2 has 2 children and 19 points ([-2.76526999 31.4931216   2.46235462])
        3: Internal node at depth 2 has 8 children and 147 points ([-2.51276999 31.4931216   2.46235462])
        7: Internal node at depth 2 has 1 children and 19 points ([-2.51276999 31.4931216   2.71485462])
    5: Internal node at depth 1 has 4 children and 313 points ([-2.26026999 31.2406216   2.46235462])
        0: Internal node at depth 2 has 8 children and 164 points ([-2.26026999 31.2406216   2.46235462])
        1: Internal node at depth 2 has 1 children and 2 points ([-2.00776999 31.2406216   2.46235462])
        2: Internal node at depth 2 has 8 children and 144 points ([-2.26026999 31.4931216   2.46235462])
        6: Internal node at depth 2 has 1 children and 3 points ([-2.26026999 31.4931216   2.71485462])
    6: Internal node at depth 1 has 4 children and 226 points ([-2.76526999 31.7456216   2.46235462])
    7: Internal node at depth 1 has 4 children and 218 points ([-2.26026999 31.7456216   2.46235462])

Find leaf node containing point

Using the above traversal mechanism, an octree can be quickly searched for the leaf node that contains a given point. This functionality is provided via the locate_leaf_node method.

octree.locate_leaf_node(pcd.points[0])

(OctreePointColorLeafNode with color [0.380424, 0.258173, 0.838248] containing 5 points.,
 OctreeNodeInfo with origin [-2.13402, 31.4931, 2.39923], size 0.063125, depth 4, child_index 4)