八叉树

八叉树简介

八叉树（Octree）是一种在三维空间中进行数据组织和存储的树型数据结构。它的工作原理是将一个大的三维空间递归地分割成八个相等的小空间，每个小空间又可以继续分割成八个更小的空间，以此类推，直到达到某个预定的深度或者满足特定的终止条件（例如，空间内元素数量少于一个阈值）。每个分割后的空间都可以视为一个节点，整个结构形成了一个树形层次。

在Unity游戏引擎中，八叉树主要用于场景管理，特别是对于大型环境和密集物体的高效处理。其主要作用包括：

1. 碰撞检测：在复杂的环境中，八叉树可以快速定位可能发生的碰撞区域，减少不必要的碰撞检测计算，提高效率。
2. 视图裁剪：在渲染过程中，八叉树可以帮助确定哪些物体位于相机视野之内，从而避免渲染视野外的物体，节省GPU资源。
3. 物体查找：八叉树可以快速定位和检索空间中的物体，尤其是在大规模场景中，这种能力尤为重要。
4. 动态负载平衡：在多人在线游戏中，八叉树可以辅助服务器管理玩家的位置，将玩家合理分配到不同的服务器分区，以达到负载平衡。
5. 粒子系统管理：对于具有大量粒子的系统，八叉树可以优化粒子的更新和渲染，减少计算量。
6. 路径寻找：在AI路径规划中，八叉树可以作为障碍物的快速查询结构，加速寻路算法的执行。
7. LOD（Level of Detail）管理：八叉树可以辅助管理不同细节级别的模型，确保远处的模型使用较低细节，近处的模型使用较高细节，从而节省资源

八叉树的实现示例:

using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Serialization;

[System.Serializable]
public class OctreeObject
{
    public GameObject GameObject;
    public Bounds Bounds;

    public OctreeObject(GameObject go)
    {
        GameObject = go;
        Bounds = go.GetComponent<Collider>().bounds;
    }
}
[System.Serializable]
public class OctreeNode
{
    public Bounds NodeBounds;
    public List<OctreeObject> ContainedObjects;
    private float minSize;
    private Bounds[] childBounds;
    public OctreeNode[] Children=null;
    public OctreeNode(Bounds nodeBounds, float minNodeSize)
    {
        ContainedObjects = new List<OctreeObject>();
        this.NodeBounds = nodeBounds;
        this.minSize = minNodeSize;
        
        float quarter= this.NodeBounds.size.y / 4;
        float childLength = this.NodeBounds.size.y / 2;
        Vector3 childSize = new Vector3(childLength, childLength, childLength);
        childBounds = new Bounds[8];
        childBounds[0] = new Bounds(new Vector3(nodeBounds.center.x - quarter, nodeBounds.center.y + quarter, nodeBounds.center.z - quarter), childSize);
        childBounds[1] = new Bounds(new Vector3(nodeBounds.center.x + quarter, nodeBounds.center.y + quarter, nodeBounds.center.z - quarter), childSize);
        childBounds[2] = new Bounds(new Vector3(nodeBounds.center.x - quarter, nodeBounds.center.y + quarter, nodeBounds.center.z + quarter), childSize);
        childBounds[3] = new Bounds(new Vector3(nodeBounds.center.x + quarter, nodeBounds.center.y + quarter, nodeBounds.center.z + quarter), childSize);
        childBounds[4] = new Bounds(new Vector3(nodeBounds.center.x - quarter, nodeBounds.center.y - quarter, nodeBounds.center.z - quarter), childSize);
        childBounds[5] = new Bounds(new Vector3(nodeBounds.center.x + quarter, nodeBounds.center.y - quarter, nodeBounds.center.z - quarter), childSize);
        childBounds[6] = new Bounds(new Vector3(nodeBounds.center.x - quarter, nodeBounds.center.y - quarter, nodeBounds.center.z + quarter), childSize);
        childBounds[7] = new Bounds(new Vector3(nodeBounds.center.x + quarter, nodeBounds.center.y - quarter, nodeBounds.center.z + quarter), childSize);
    }

    

    public void AddObject(GameObject go)
    {
        DivideAndAdd(go);
    }

    private void DivideAndAdd(GameObject go)
    {
        OctreeObject octObj = new OctreeObject(go);
        
        if (NodeBounds.size.y <= minSize)
        {
            ContainedObjects.Add(octObj);
            return;
        }
        
        Children ??= new OctreeNode[8];
        
        var dividing=false;
        for (var i = 0; i < 8; i++)
        {
            Children[i]??= new OctreeNode(childBounds[i], minSize);
            if(childBounds[i].Intersects(octObj.Bounds))
            {
                dividing = true;
                Children[i].DivideAndAdd(go);
            }
        }

        if (dividing == false)
        {
            ContainedObjects.Add(octObj);
            Children = null;
        }
    }
    
    public void Draw()
    {
        Gizmos.color = Color.green;
        Gizmos.DrawWireCube(NodeBounds.center, NodeBounds.size);
        
        Gizmos.color = Color.red;
        foreach (var obj in ContainedObjects)
        {
            Gizmos.DrawWireCube(obj.Bounds.center, obj.Bounds.size);
        }


        if (Children != null)
        {
            foreach (var child in Children)
            {
                if (child != null)
                    child.Draw();
            }
        }
        else if (ContainedObjects.Count != 0)
        {
            Gizmos.color = new Color(0,0,1,0.25f);
            Gizmos.DrawCube(NodeBounds.center, NodeBounds.size);
        }
    }
}

示例——寻找包围盒中最近的点

假设我们已经通过八叉树对很多点进行了分割，现在想找出一个点里这些点集最近的点，太远则视为不相交。

public Vector3? FindNearestPoint(Vector3 p)
{
    if (!Bounds.Contains(p))
        return null; // 如果点P不在八叉树有点的空间,返回null

    if (points.Count > 0)
    {
        // 如果当前节点有点,找到离p最近的唯一一个点
        Vector3 nearestPoint = points[0];
        float nearestDistance = Vector3.Distance(nearestPoint, p);

        for (int i = 1; i < points.Count; i++)
        {
            float distance = Vector3.Distance(points[i], p);
            if (distance < nearestDistance)
            {
                nearestPoint = points[i];
                nearestDistance = distance;
            }
            else if (distance == nearestDistance)
            {
                // 如果有多个点与p的距离相同,返回null
                return null;
            }
        }

        return nearestPoint;
    }
    else if (children != null)
    {
        // 如果当前节点没有点,递归查找子节点
        Vector3? nearestPoint = null;
        float nearestDistance = float.MaxValue;

        for (int i = 0; i < children.Length; i++)
        {
            if (children[i] != null)
            {
                Vector3? childNearestPoint = children[i].FindNearestPoint(p);
                if (childNearestPoint.HasValue)
                {
                    float distance = Vector3.Distance(childNearestPoint.Value, p);
                    if (distance < nearestDistance)
                    {
                        nearestPoint = childNearestPoint;
                        nearestDistance = distance;
                    }
                    else if (distance == nearestDistance)
                    {
                        // 如果有多个点与p的距离相同,返回null
                        return null;
                    }
                }
            }
        }

        return nearestPoint;
    }
    else
    {
        // 如果当前节点既没有点,也没有子节点,返回null
        return null;
    }
}

参考

BVH从Octree开始：https://zhuanlan.zhihu.com/p/696725602

Unity中实现八叉树和BVH：https://www.bilibili.com/video/BV1Ei421e7xi

八叉树等功能库插件：https://prf.hn/click/camref:1011l5dHP/destination:https://assetstore.unity.com/packages/tools/integration/coding-essentials-76797

Unity资源商城：https://prf.hn/click/camref:1011l5dHP

免费AI工具：https://fas.st/t/Ep3jbPVm

获得永久免费的无限 GPT 查询次数！点击链接并下载Monica插件，即可参加限时活动。

https://monica.im/invitation?c=OWBJ2ZBE