八叉树

八叉树

八叉树是一种空间划分树, 每个结点对应空间中的一片区域, 结点的子节点按八等分继续细分
如果不做限制就会一直细分, 所以需要限制最大划分层级和最大对象数, 如果结点代表的区域包含的对象数大于最大对象数且当前层级小于最大层级,那么就对当前结点进行划分.
适合需要进行相邻区间和查询的情况, 比如需要找到一个点附近的一些点, 维护这些点之间的状态, 就可以用八叉树

---

C#实现

public class Octree
{
    //八叉树根节点
    public OctreeNode rootNode;

    public Octree(GameObject[] worldObjects, float minNodeSize)
    {
        Bounds bounds = new Bounds();

        //创建一个包围所有物体的包围盒
        foreach (GameObject go in worldObjects)
        {
            //用物体所有collider扩大bounds(center会变化), 注意new出来的包围盒默认会包含坐标原点
            bounds.Encapsulate(go.GetComponent<Collider>().bounds);
        }

        //获取包围所有物体的包围盒的最大XYZ值
        float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z });

        Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize) * 0.5f;
        //通过设置最小最大位置, 改变包围盒center和extents
        bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector);


        //根据现有的值创建根节点
        rootNode = new OctreeNode(bounds, minNodeSize);

        AddObjects(worldObjects);
    }

    //将worldObjects插入八叉树
    public void AddObjects(GameObject[] worldObjects)
    {
        foreach (GameObject go in worldObjects)
        {
            rootNode.AddObject(go);
        }
    }
}

public class OctreeNode
{
    Bounds nodeBounds;
    float minSize;
    Bounds[] childBounds; //子树包围盒
    OctreeNode[] children = null; //子树对象

    public OctreeNode(Bounds bounds, float minNodeSize)
    {
        //bounds:包含所有物体的AABB, minNodeSize:八叉树最小划分单位(相对于包围盒边长)
        nodeBounds = bounds;
        minSize = minNodeSize;

        //取整体长度的1/4, 计算子树的 center
        float quarter = nodeBounds.size.x / 4.0f;
        //整体长度的1/2, 作为一颗子树边长
        float childLength = nodeBounds.size.x / 2;

        //初始包围盒和子包围盒
        Vector3 childSize = new Vector3(childLength, childLength, childLength);
        childBounds = new Bounds[8];
        childBounds[0] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, -quarter), childSize);
        childBounds[1] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, -quarter), childSize);
        childBounds[2] = new Bounds(nodeBounds.center + new Vector3(-quarter, quarter, quarter), childSize);
        childBounds[3] = new Bounds(nodeBounds.center + new Vector3(quarter, quarter, quarter), childSize);
        childBounds[4] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, -quarter), childSize);
        childBounds[5] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, -quarter), childSize);
        childBounds[6] = new Bounds(nodeBounds.center + new Vector3(-quarter, -quarter, quarter), childSize);
        childBounds[7] = new Bounds(nodeBounds.center + new Vector3(quarter, -quarter, quarter), childSize);
    }

    // 判断所在的区域里有没有GameObject并将其放入该区域的树结点中
    public void AddObject(GameObject gam)
    {
        DivideAndAdd(gam);
    }

    // 使用递归完成八叉树的创建
    public void DivideAndAdd(GameObject gam)
    {
        //如果包围盒已经小于等于最小尺寸就停止，直接返回树
        if (nodeBounds.size.x <= minSize)
        {
            return;
        }

        if (children == null)
        {
            children = new OctreeNode[8];
        }

        bool divided = false;
        for (int i = 0; i < 8; i++)
        {
            if (children[i] == null)
            {
                //根据childBounds创建子树的八个包围盒
                children[i] = new OctreeNode(childBounds[i], minSize);
            }
            //通过碰撞体包围盒是否相交来判断物体在哪个区域内
            if (childBounds[i].Intersects(gam.GetComponent<Collider>().bounds))
            {
                divided = true;
                children[i].DivideAndAdd(gam);
            }
        }

        if (divided == false)
        {
            children = null;
        }
    }
}