八叉樹

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