八叉树，分裂空间的魔法师【Unity】
八叉树，分裂空间的魔法师
前往我的博客阅读，享受免费无广告的体验
诞生
当我们要做物理碰撞检测的时候，例如一枚子弹射了出去，我们或许会选择遍历所有的物体，通过运算判断是否相交，是否发生碰撞，但这不理想，尤其是面对成千上万物体的时候，计算量极其恐怖。
同样的，在面对光线计算，遮挡关系计算中也有这个问题。
事实上，如果让我们也这样做，即从头看到尾，依次遍历，寻找碰撞，也未必迅速。但是我们能很快发现发生碰撞的物品，为什么？
因为我们会进行一个潜在的分区，只看可能会碰撞的位置
这就是我们的思路，尝试进行分区，然后遍历分区内的物体；
八叉树就这样诞生了
原理
先看个图片:
这个图片是李恒老师的图片，很直观的展示了八叉树根本的原理。
即通过预划分，将其分类，当需要检测东西的时候，只需要对其空间内的进行遍历
从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