八叉樹

八叉樹（Octree）的定義是：若不為空樹的話，樹中任一節點的子節點恰好只會有八個，或零個，也就是子節點不會有0與8以外的數目。那么，這要用來做什麼？想像一個立方體，我們最少可以切成多少個相同等分的小立方體？答案就是8個。再想像我們有一個房間，房間裡某個角落藏著一枚金幣，我們想很快的把金幣找出來，聰明的你會怎么做？我們可以把房間當成一個立方體，先切成八個小立方體，然後排除掉沒有放任何東西的小立方體，再把有可能藏金幣的小立方體繼續切八等份….如此下去，平均在Log8(房間內的所有物品數)的時間內就可找到金幣。因此，八叉樹就是用在3D空間中的場景管理，可以很快地知道物體在3D場景中的位置，或偵測與其它物體是否有碰撞以及是否在可視範圍內。

簡介

八叉樹是一種用於描述三維空間的樹狀數據結構。八叉樹的每個節點表示一個正方體的體積元素，每個節點有八個子節點，將八個子節點所表示的體積元素加在一起就等於父節點的體積。

實現原理

(1). 設定最大遞歸深度

(2). 找出場景的最大尺寸，並以此尺寸建立第一個立方體

(3). 依序將單位元元素丟入能被包含且沒有子節點的立方體

(4). 若沒有達到最大遞歸深度，就進行細分八等份，再將該立方體所裝的單位元元素全部分擔給八個子立方體

(5). 若發現子立方體所分配到的單位元元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎么切數目還是一樣，會造成無窮切割的情形。

(6). 重複3，直到達到最大遞歸深度。

存貯結構

本例中八叉樹的存貯結構用一個有（若干+八）個欄位的記錄來表示樹中的每個結點。其中若干欄位用來描述該結點的特性(本例中的特性為：節點的值和節點坐標)，其餘的八個欄位用來作為存放指向其八個子結點的指針。此外，還有線性存儲和1托8式存儲。

叉樹對比

a) BSP樹將場景分割為1個面，而八叉樹分割為3個面。

b) BSP樹每個節點最多有2個子結點，而八叉樹最多有8個子結點

因此BSP樹可以用在任意維度的場景中，而八叉樹則常用於三維空間場。