Unity3D 八叉树划分空间和可视化

也许更好的阅读体验

成果展示

代码

OctreeNode

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OctreeNode
{
    //空间内包含的物体
    public List<GameObject> areaObjects;
    //空间中心
    public Vector3 center;
    //空间大小
    public float size;
    //子节点个数 
    private int kidCount = 8;
    //子节点
    public OctreeNode[] kids;
    //构造函数
    public OctreeNode (Vector3 center, float size)
    {
        this.center = center;
        this.size = size;
        kids = new OctreeNode[kidCount];
        areaObjects = new List<GameObject>();
    }
    #region 八个子节点中心对应的偏移方向
    public static Vector3[] centerOffset = new Vector3[8] {
        new Vector3 (-1, 1, -1),
        new Vector3 (1, 1, -1),
        new Vector3 (-1, 1, 1),
        new Vector3 (1, 1, 1),
        new Vector3 (-1, -1, -1),
        new Vector3 (1, -1, -1),
        new Vector3 (-1, -1, 1),
        new Vector3 (1, -1, 1)
    };
    #endregion

    #region 空间和内部物体管理
    //空间内物体树
    public int objectCount => areaObjects.Count;
    //把该空间画出来
    public void DrawGizmos ()
    {
        Gizmos.DrawWireCube(center, Vector3.one * size);
    }
    //判断是否包含某个点
    public bool Contains (Vector3 position)
    {
        float halfSize = size / 2.0f;
        return Mathf.Abs(position.x - center.x) <= halfSize &&
            Mathf.Abs(position.y - center.y) <= halfSize &&
            Mathf.Abs(position.z - center.z) <= halfSize;
    }
    //清理空间内物体
    public void Clear ()
    {
        areaObjects.Clear();
    }
    //添加物体
    public void AddGameObject (GameObject obj)
    {
        areaObjects.Add(obj);
    }
    #endregion

}

Orctree

using System.Collections;
using System.Collections.Generic;
using System.ComponentModel.Design.Serialization;
using Unity.VisualScripting;
using UnityEngine;

//可视化模式
public enum OctreeDebugMode
{
    AllDepth,
    TargetDepth
}
public class Octree : MonoBehaviour
{

    #region 物体生成和构建八叉树
    //生成物体数
    [Range(0, 500)]
    public int genCount = 500;
    //物体生成范围
    [Range(1, 300)]
    public float range = 100;
    //生成的物体
    public List<GameObject> sceneObjects;
    //Octree最大层数
    [Range(1, 8)]
    public int maxDepth = 3;
    //Octree的根节点
    public OctreeNode root;


    // Start is called before the first frame update
    void Start()
    {
        GenObjects();
        OctreePartition();
    }

    //随机生成一些cube
    private void GenObjects()
    {
        float genRange = range * 0.5f;
        sceneObjects = new List<GameObject>();

        for (int i = 0; i < genCount; ++i)
        {
            GameObject obj = GameObject.CreatePrimitive(PrimitiveType.Cube);
            obj.transform.position = new Vector3(Random.Range(-genRange, genRange),
                Random.Range(-genRange, genRange),
                Random.Range(-genRange, genRange));
            obj.hideFlags = HideFlags.HideInHierarchy;
            sceneObjects.Add(obj);
        }
    }
    //进行八叉树划分
    private void OctreePartition ()
    {
        //设定根节点
        Vector3 origin = Vector3.one;
        root = new OctreeNode(Vector3.zero, range);
        root.areaObjects = sceneObjects;
        //往下生成八叉树 根节点层数为1
        GenerateOcetree(root, range, 2);
    }
    //递归往下生成八叉树
    private void GenerateOcetree (OctreeNode root, float range, int depth)
    {
        //depth是当前生成的层数
        if (depth > maxDepth) return;
        //下一层的大小
        float halfRange = range / 2.0f;
        //根节点偏移量
        float rootOffset = halfRange / 2.0f;
        for (int i = 0; i < 8; ++i)
        {
            Vector3 origin = root.center + OctreeNode.centerOffset[i] * rootOffset;
            root.kids[i] = new OctreeNode(origin, halfRange);
        }
        PartitionSceneObjects(root);
        for (int i = 0; i < 8; ++i)
        {
            if (root.kids[i].objectCount >= 2) GenerateOcetree(root.kids[i], halfRange, depth + 1);
        }
    }
    //把空间内物体划分给子节点
    private void PartitionSceneObjects(OctreeNode root)
    {
        foreach (GameObject obj in root.areaObjects)
        {
            foreach (OctreeNode kid in root.kids)
            {
                if (kid.Contains(obj.transform.position))
                {
                    kid.AddGameObject(obj);
                }
            }
        }
    }
    #endregion

    #region 可视化
    //是否显示八叉树
    public bool showOctree = true;
    //可视化类型
    public OctreeDebugMode octreeDebugMode;
    //可视化层数
    [Range(0, 8)]
    public int displayDepth = 3;
    //不同深度的可视化颜色
    public Color[] displayColor;
    private void OnDrawGizmos()
    {
        if (root == null) return;
        if (showOctree && displayDepth <= maxDepth)
        {
            //显示所有深度的空间范围
            if (octreeDebugMode == OctreeDebugMode.AllDepth)
            {
                DrawNode(root, 1);
            }
            //显示指定深度的空间范围(第displayDepth层)
            else if (octreeDebugMode == OctreeDebugMode.TargetDepth)
            {
                if (displayDepth > 0 && displayColor.Length >= displayDepth) 
                {
                    Color color = displayColor[displayDepth - 1];
                    color.a = 0.5f;
                    Gizmos.color = color;
                    DrawTargetDepth(root, displayDepth);
                }
            }
        }
    }
    //绘制所有节点 当前深度为depth
    private void DrawNode(OctreeNode root, int depth)
    {
        if (root == null || depth > maxDepth) return;
        Color color = displayColor[depth - 1];
        color.a = 0.5f;
        Gizmos.color = color;
        root.DrawGizmos();
        foreach (OctreeNode kid in root.kids)
        {
            DrawNode(kid, depth + 1);
        }
    }
    //绘制指定层
    private void DrawTargetDepth (OctreeNode root, int targetDepth)
    {
        --targetDepth;
        if (root == null || targetDepth < 0) return;
        Debug.Log(targetDepth);
        if (targetDepth == 0)
        {
            root.DrawGizmos();
            return;
        }
        foreach (OctreeNode kid in root.kids)
        {
            DrawTargetDepth(kid, targetDepth);
        }
    }
    #endregion
}