Octree

又稱: sparse voxel octree
類別: Sensing › 3D maps & reconstruction
標籤: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds

一種樹狀資料結構，把 3D 空間遞迴地切分成八個立方體，只在有資料的地方配置精細單元，以得到精簡的地圖與快速的空間查詢。

定義

八元樹（Octree）是這樣的樹：每個節點代表空間中的一個立方體，最多可以有八個子節點，每個子節點對應把立方體沿三個軸各對半切開後得到的一個卦限。根節點涵蓋整個體積；每往下一層，單元尺寸就減半。只有在有值得關注的內容（例如量測到的表面點）之處，分支才會被細分，因此大片空的或未觀測的區域會維持為單一的粗略節點。八元樹由 Donald Meagher 在 1980 年代初期為實體建模而提出，如今已是電腦圖學、點雲處理與機器人建圖的標準方法。

它的主要吸引力在於記憶體。在大型建築物上以精細解析度建立的稠密體素網格，必須為每個單元配置儲存空間，而八元樹的儲存量大致隨觀測到的表面積成長。它也提供多解析度存取：規劃器可以先查詢粗略單元做快速檢查，再往下深入取得細節。在 Hornung 與同事開發、廣受使用的函式庫 OctoMap 中，每個葉節點以對數勝算（log-odds）形式保存一個機率佔據值，並依距離量測更新，因此地圖能區分佔據、空閒與未知的空間。狀態相同的子節點會被修剪、合併回父節點，以節省記憶體。

八元樹以部分速度換取這種精簡性：要到達葉節點必須沿著樹往下走，這比索引扁平陣列慢。體素雜湊與 VDB 結構等替代方案，在某些工作負載下存取更快。八元樹也用於加速點雲上的最近鄰搜尋與碰撞檢查；在近期的神經建圖系統中，它們用來組織儲存學習特徵的稀疏體素，並隨著新的深度影格到來而逐步擴展。

為何重要

機器人需要能以實用解析度涵蓋大範圍、又不會耗盡記憶體的 3D 地圖。八元樹讓這件事變得可行，它們也是操作與空中導航中常用之佔據建圖與碰撞檢查工具的基礎。

主要應用

以 OctoMap 進行機率式 3D 佔據建圖
機器手臂與無人機的碰撞檢查
點雲上的最近鄰與半徑搜尋
用於神經隱式與稠密建圖的稀疏體素結構
點雲壓縮與細節層次渲染

實際應用

一個為在倉庫中飛行的無人機建立 3D 地圖的團隊，把深度攝影機或光達的點雲，連同里程計提供的姿態，以幾公分的解析度輸入 OctoMap。每條光線把它穿過的單元標記為較可能空閒，把它末端的單元標記為較可能被佔據。規劃器沿著候選路徑查詢八元樹中的佔據情形，並把未知空間當作障礙物。在機器手臂上，MoveIt 可以從深度感測器取得同類的八元樹，讓手臂的規劃場景保持最新。工程師調整解析度、感測器量程，以及命中與未命中機率，在細節、記憶體與移動物體被清除的速度之間取得平衡。

常見誤解

八元樹與體素網格是同一回事 — 體素網格儲存每個單元，而八元樹只在需要之處細分，並合併均勻的區域
八元樹一定比扁平網格快 — 它們節省記憶體，但每次查找都要走過樹，因此對某些查詢而言，稠密網格或雜湊網格可能更快
八元樹中的空白空間代表空閒空間 — 在佔據八元樹中，未觀測的空間是未知的，規劃器通常應該把它與空閒空間區別對待

誰需要了解

建圖與 SLAM 工程師
運動規劃與碰撞檢查開發者
在 3D 環境中工作的無人機自主工程師
神經與稠密建圖系統的開發者

影片

Using Octrees and A* for Efficient Pathfinding: git-amend

維基百科

八叉树

Open Source Robotics