【Python】Open3DでOctreeを実装
Octreeの概要
Octree (八分木) は、3D空間内のオブジェクトを効率的に検索するためのアルゴリズムです。
Octreeは3D空間を8分割することで、点集合を効率的に検索することができます。各ノードは、空間を8つに分割する立方体に対応します。
Octree は K-D Tree よりもより多くのメモリを使用する可能性がありますが、領域検索など、空間分割によって検索することができるタスクに適しています。
アルゴリズム
このアルゴリズムは、空間内に規則的なグリッドを構築し、オブジェクトをこのグリッドに含まれるボックスに分類することで、検索操作を高速化するというアイデアをもとにしています。
グリッドは、再帰的に分割されていき、最終的には各グリッドに対して 1 つのオブジェクトしか含まれないようになります。
Octree アルゴリズムの手順としてはKDtreeと似ていますが、以下の通りです。
１．3次元空間を表す根ノードを作成します。このノードは、全ての3次元データを含む最大の矩形領域を表します。
２．各ノードにおいて、空間中に存在するデータが最大の矩形領域を超えないように、空間を 8 分割します。これらの分割領域は子ノードとして表されます。
３．子ノードにおいても同様の手順を繰り返します。繰り返しが終了するタイミングは、各子ノードに存在するデータが十分に少ないか、または空間を分割することができない場合になります。
４．空間を分割した子ノードに対して、各ノードが表す領域に属するデータを格納します。
Octree アルゴリズムを使用することで、大量の3次元データを効率的に管理することができます。また、このアルゴリズムを使用することで、3次元データの検索や空間操作などが高速に実行できます。
Pythonコード
Open3Dを用いてOctreeを実装します。入力した点群をOctreeのデータ構造に変換し可視化します。
全体のコードは以下の通りです。
# 点群の生成
# メッシュファイルの読み込み⇒点のサンプリング
print('input')
N = 2000
armadillo = o3d.data.ArmadilloMesh()
mesh = o3d.io.read_triangle_mesh(armadillo.path)
pcd = mesh.sample_points_poisson_disk(N)
# Octreeの構築
pcd.scale(1 / np.max(pcd.get_max_bound() - pcd.get_min_bound()),
center=pcd.get_center())
print('octree division')
octree = o3d.geometry.Octree(max_depth=4)
octree.convert_from_point_cloud(pcd, size_expand=0.01)
# 可視化
pcd.colors = o3d.utility.Vector3dVector(np.random.uniform(0, 1, size=(N, 3)))
o3d.visualization.draw_geometries([pcd])
o3d.visualization.draw_geometries([octree])
参考：http://www.open3d.org/docs/release/tutorial/geometry/octree.html