八叉樹

八叉樹（英語：Octree）是一種樹形數據結構，每個內部節點都正好有八個子節點。八叉樹常用於分割三維空間，將其遞歸細分為八個卦限。八叉樹是四叉樹在三維空間中的對應，在三維圖形、三維遊戲引擎等領域有很多應用。

八叉樹
類型	樹
發明時間	1980年
發明者	唐納德·米格爾
用大O符號表示的時間複雜度 演算法 平均 最差 用大O符號表示的空間複雜度

左：遞歸子切分一個立方體為多個卦限。右：對應的八叉樹

表示空間

八叉樹的每個節點都可以代表一個空間，對應的八個子節點則將這個空間細分為八個卦限。點域（point region，簡稱PR）八叉樹的節點中都儲存着一個三維點，即該節點對應區域的「中心」，也是八個子節點對應區域中的一個角落。矩陣（matrix based，簡稱MX）八叉樹中，節點只記錄區域範圍，對應的中心點坐標需要從區域範圍推算。因此，PR八叉樹的根節點可以表示無限大的空間；而MX八叉樹的根節點只能表示有限空間，這樣才可以得到隱含的中心點。

歷史

八叉樹在3D電腦圖形領域的應用可以追溯到1980年倫斯勒理工學院唐納德·馬爾（Donald Meagher）的報告《八叉樹編碼：使用電腦表示、操作、顯示任意三維對象的新技術》（Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer）^[1]。

主要用途

• 3D電腦圖形學中的細節層次渲染^[2]
• 最鄰近搜尋
• 三維空間中的高效碰撞檢測
• 稀疏體素八叉樹（英語：Sparse voxel octree）
• 狀態估計^[3]

另見

• 線性八叉樹（英語：Linear octree）
• 體素
• 四叉樹
• OGRE，有基於八叉樹的場景管理器
• Irrlicht引擎（英語：Irrlicht Engine），支援八叉樹場景節點