八叉树，分裂空间的魔法师

八叉树（Octree）是一种空间划分数据结构，广泛应用于三维计算机图形学、物理仿真和游戏开发中。通过递归划分三维空间，八叉树能够有效管理和优化场景中的物体，加速碰撞检测、光线追踪和视锥剔除等操作。

诞生

当我们要做物理碰撞检测的时候，例如一枚子弹射了出去，我们或许会选择遍历所有的物体，通过运算判断是否相交，是否发生碰撞，但这不理想，尤其是面对成千上万物体的时候，计算量极其恐怖。
同样的，在面对光线计算，遮挡关系计算中也有这个问题。
事实上，如果让我们也这样做，即从头看到尾，依次遍历，寻找碰撞，也未必迅速。但是我们能很快发现发生碰撞的物品，为什么？

因为我们会进行一个潜在的分区，只看可能会碰撞的位置

这就是我们的思路，尝试进行分区，然后遍历分区内的物体； 八叉树就这样诞生了

原理

先看个图片: 这个图片是李恒老师的图片，很直观的展示了八叉树根本的原理。
即通过预划分，将其分类，当需要检测东西的时候，只需要对其空间内的进行遍历

从Octree到BVH，对空间划分的理解

最近在看games104，也算是学了游戏引擎的毛毛皮。 其最大的意义，我认为是让游戏引擎变聪明了，可以借助技巧减少运算了。

• 例如生化危机8：村庄中，也可以说绝大数生化危机中，都对房间进行划分，进入某个房间后，激活僵尸AI，做相关处理。
• 再例如僵尸毁灭工程，我的世界，就对引入区块的概念，重点渲染，处理区块内的内容。

总之，核心并不难理解，其底层就是划分，然后分开处理。

使用

有了最最最浅显的理解，可以写一下最基本的数据结构了

public class OctreeNode  
{  
    // 空间大小与其内的物体  
    public List<GameObject> areaObjects;  
    public Vector3 center;  
    public float size;  
          
	private const int kidCount = 8;  
    private OctreeNode[] kids;  
    
    public OctreeNode(Vector3 center, float size)  
    {        
	    kids = new OctreeNode[kidCount];  
        this.center = center;  
        this.size = size;  
        areaObjects = new List<GameObject>();  
    }    
    //四个上面的节点
    public OctreeNode top0  
    {  
        get { return kids[0];}  
        set { kids[0] = value; }  
    }  
	// 省略
	//四个下面的节点
    public OctreeNode bottom0  
    {  
        get{ return kids[4];}  
        set { kids[4] = value; }  
    }  
    // 省略
    
    public int objectCount => areaObjects.Count;  
  
    public void DrawGizmos()  
    {        
	    Gizmos.DrawWireCube(center, Vector3.one * size);  
    }  
    
    public bool Contains(Vector3 position)  
    {        
	    var halfSize = size * 0.5f;  
        return Mathf.Abs(position.x - center.x) <= halfSize &&  
               Mathf.Abs(position.y - center.y) <= halfSize &&  
               Mathf.Abs(position.z - center.z) <= halfSize;  
    }          

    public void AddGameobject(GameObject go)  
    {        
	    areaObjects.Add(go);  
    }          
}

很容易理解，即定义了一个OctreeNode，其拥有一个位置与大小，其包含八个OctreeNode；

接下来是八叉树控制代码

public class OctreeNodeCon : MonoBehaviour  
{  
    public OctreeNode root;  
    private List<GameObject> sceneObjects;  
    [Range(0, 500)] public int genCount = 100;  
    [Range(1, 8)] public int buildDepth;  
    [Range(1, 300)] public float range = 100;  
          
  
    [Range(0, 8)] public int displayDepth = 3;  
    public bool showOctree = true;  
    public OctreeDebugMode octreeDebugMode;  
    public Color[] displayColor;  
    // 检测信息  
    public bool showQueryResult = true;  
    public GameObject checkTarget;  
    private List<GameObject> queryObjects;  
    private OctreeNode queryNode;  
    
    private void Start()  
    {        
	    GenSceneObjects();  
        OctreePartion();  
    }  
    
    private void Update()  
    {        
	    if (checkTarget != null)  
        {            
	        var position = checkTarget.transform.position;  
            if (root.Contains(position))  
            {                
	            var node = QueryOctTree(position, root);  
                if (node != null)  
                {                    
	                queryObjects = node.areaObjects;  
                    queryNode = node;  
                }            
            }            
            else  
            {  
                queryObjects = null;  
                queryNode = null;  
            }        
        }    
    }   
     
    // 查询八叉树  
    private OctreeNode QueryOctTree(Vector3 position, OctreeNode checkNode)  
    {        
	    if(checkNode == null)  
            return null;  
        if (checkNode.top0?.Contains(position) ?? false) return QueryOctTree(position, checkNode.top0);  
        if (checkNode.top1?.Contains(position) ?? false) return QueryOctTree(position, checkNode.top1);  
        if (checkNode.top2?.Contains(position) ?? false) return QueryOctTree(position, checkNode.top2);  
        if (checkNode.top3?.Contains(position) ?? false) return QueryOctTree(position, checkNode.top3);  
  
        if (checkNode.bottom0?.Contains(position) ?? false) return QueryOctTree(position, checkNode.bottom0);  
        if (checkNode.bottom1?.Contains(position) ?? false) return QueryOctTree(position, checkNode.bottom1);  
        if (checkNode.bottom2?.Contains(position) ?? false) return QueryOctTree(position, checkNode.bottom2);  
        if (checkNode.bottom3?.Contains(position) ?? false) return QueryOctTree(position, checkNode.bottom3);  
  
        return checkNode;  
    }    
    // 生成场景物体  
    private void GenSceneObjects()  
    {        
	    var genRang = range * 0.5f;  
        sceneObjects = new List<GameObject>();  
		for (int i = 0; i < genCount; i++)  
        {            
	        var obj = GameObject.CreatePrimitive(PrimitiveType.Cube);  
            obj.transform.position = new Vector3(Random.Range(-genRang, genRang), Random.Range(-genRang, genRang),  Random.Range(-genRang, genRang));  
            obj.hideFlags = HideFlags.HideInHierarchy;  
            sceneObjects.Add(obj);  
        }    
    }  
    // 生成八叉树  
    private void OctreePartion()  
    {        
	    var initialOrgin = Vector3.zero;  
        root = new OctreeNode(initialOrgin, range);  
        root.areaObjects = sceneObjects;  
        GenerateOctree(root, range, buildDepth);  
    }  
    // 递归生成八叉树  
    private void GenerateOctree(OctreeNode root, float range, float depth)  
    {        
	    if (depth <= 0)  
        {            
	        return;  
        }  
        var halfRange = range / 2.0f;  
        var rootCenter = root.center;  
        var rootOffset = halfRange / 2.0f;  
  
        var origin = rootCenter + new Vector3(-1, 1, -1) * rootOffset;  
        root.top0 = new OctreeNode(origin, halfRange);  
        
        origin = rootCenter + new Vector3(1, 1, -1) * rootOffset;  
        root.top1 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(1, 1, 1) * rootOffset;  
        root.top2 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(-1, 1, 1) * rootOffset;  
        root.top3 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(-1, -1, -1) * rootOffset;  
        root.bottom0 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(1, -1, -1) * rootOffset;  
        root.bottom1 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(1, -1, 1) * rootOffset;  
        root.bottom2 = new OctreeNode(origin, halfRange);  
  
        origin = rootCenter + new Vector3(-1, -1, 1) * rootOffset;  
        root.bottom3 = new OctreeNode(origin, halfRange);  
        PartitionSceneObjects(root);  
  
        if (root.top0.objectCount >= 2)  
        {            
	        GenerateOctree(root.top0,halfRange,depth-1);  
        }  
        if (root.top1.objectCount >= 2)  
        {            
	        GenerateOctree(root.top1, halfRange, depth - 1);  
        }  
        if (root.top2.objectCount >= 2)  
        {            
	        GenerateOctree(root.top2, halfRange, depth - 1);  
        }  
        if (root.top3.objectCount >= 2)  
        {            
	        GenerateOctree(root.top3, halfRange, depth - 1);  
        }  
        if (root.bottom0.objectCount >= 2)  
        {            
	        GenerateOctree(root.bottom0, halfRange, depth - 1);  
        }  
        if (root.bottom1.objectCount >= 2)  
        {            
	        GenerateOctree(root.bottom1, halfRange, depth - 1);  
        }  
        if (root.bottom2.objectCount >= 2)  
        {            
	        GenerateOctree(root.bottom2, halfRange, depth - 1);  
        }  
        if (root.bottom3.objectCount >= 2)  
        {            
	        GenerateOctree(root.bottom3, halfRange, depth - 1);  
        }            
    }  
  
    // 将场景物体分配到八叉树节点  
    private void PartitionSceneObjects(OctreeNode root)  
    {        var objects = root.areaObjects;  
        foreach (var obj in objects)  
        {            
        if (root.top0.Contains(obj.transform.position))  
            {                
	            root.top0.AddGameobject(obj);  
            }            
        else if (root.top1.Contains(obj.transform.position))  
            {                
	            root.top1.AddGameobject(obj);  
            }            
        else if (root.top2.Contains(obj.transform.position))  
            {                
	            root.top2.AddGameobject(obj);  
            }            
	    else if (root.top3.Contains(obj.transform.position))  
            {                
	            root.top3.AddGameobject(obj);  
            }            
            else if (root.bottom0.Contains(obj.transform.position))  
            {                
	            root.bottom0.AddGameobject(obj);  
            }            
            else if (root.bottom1.Contains(obj.transform.position))  
            {                
	            root.bottom1.AddGameobject(obj);  
            }            
            else if (root.bottom2.Contains(obj.transform.position))  
            {                
	            root.bottom2.AddGameobject(obj);  
            }            
            else if (root.bottom3.Contains(obj.transform.position))  
            {                
	            root.bottom3.AddGameobject(obj);  
            }        
        }    
    }  
    // 绘制八叉树  
    public void OnDrawGizmos()  
    {        
	    if (root == null)  
            return;  
  
        if (showOctree && displayDepth <= buildDepth)  
        {            
	        if (octreeDebugMode == OctreeDebugMode.AllDepth)  
            {                
	            Gizmos.color = new Color(1, 1, 1, 0.2f);  
                DrawNode(root, displayDepth);  
            }            
            else if (octreeDebugMode == OctreeDebugMode.TargetDepth)  
            {                
	            if (displayColor.Length > displayDepth)  
                {                    
	                var color = displayColor[displayDepth];  
                    color.a = 0.2f;  
                    Gizmos.color = color;  
                    DrawTargetDepth(root,displayDepth);  
                }            
            }        
        }        
        if (showQueryResult)  
        {            
	        Gizmos.color = Color.green;  
            queryNode?.DrawGizmos();  
			if (queryObjects != null)  
            {                
	            Gizmos.color = Color.red;  
				foreach (var obj in queryObjects)  
                {                    
	                Gizmos.DrawWireSphere(obj.transform.position, 0.2f);  
                    Gizmos.DrawLine(checkTarget.transform.position, obj.transform.position);  
                }            
            }        
	    }    
	}  
    // 绘制目标深度的八叉树  
    private void DrawTargetDepth(OctreeNode node, int depth)  
    {        
	    if (node == null) return;  
        if (depth <= 0)  
        {            
	        node.DrawGizmos();  
            return;  
        }  
        var nextDepth = depth - 1;  
        
        var kid = node.top0;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.top1;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.top2;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.top3;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.bottom0;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.bottom1;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.bottom2;  
        DrawTargetDepth(kid, nextDepth);  
  
        kid = node.bottom3;  
        DrawTargetDepth(kid, nextDepth);  
    }    // 绘制所有深度的八叉树  
    private void DrawNode(OctreeNode node, int depth)  
    {        
	    if (node == null)  
            return;  
        if (depth > 0 && depth < displayColor.Length)  
        {            
	        var color = displayColor[depth];  
            color.a = 0.5f;  
            Gizmos.color = color;  
            node.DrawGizmos();  
        }  
        var kid = node.top0;  
        DrawNode(kid, depth - 1);  
  
        kid = node.top1;  
        DrawNode(kid, depth - 1);  
  
        kid = node.top2;  
        DrawNode(kid, depth - 1);  
  
        kid = node.top3;  
        DrawNode(kid, depth - 1);  
  
        kid = node.bottom0;  
        DrawNode(kid, depth - 1);  
  
        kid = node.bottom1;  
        DrawNode(kid, depth - 1);  
  
        kid = node.bottom2;  
        DrawNode(kid, depth - 1);  
  
        kid = node.bottom3;  
        DrawNode(kid, depth - 1);  
    }    
}  
  
public enum OctreeDebugMode  
{  
    AllDepth,  
    TargetDepth  
}

评价

Octree本质上是维护一个区域划分当需要处理的时候只对特定区域处理。 这和算法中的二叉树有异曲同工之处。优点很明显

• 高效的初始化空间划分。
• 区域内添加物品迅速
• 多数情况下范围查询和碰撞检测效率高。

但同样的，它只是一个普通的二叉树，问题也几乎一致：

• 在物体分布不均匀的情况下，某些区域可能会被过度细分，导致树的深度增加，查询效率降低，最坏情况下，等效于没有划分。
• 对动态物体的支持较差，频繁更新会出现性能问题