Unity——八叉树的原理与实现

八叉树原理

八叉树（Octree）是一种用于在三维空间中进行空间分割的数据结构。它将三维空间递归地划分为八个子空间，每个子空间对应于一个八叉树节点。这种分割方式可以有效地组织和管理场景中的对象，提高检索效率，特别是在进行空间查询时。

以下是八叉树的基本原理：

空间划分：

初始状态：整个三维空间被表示为一个根节点，该节点包含所有的对象。递归划分：根节点被递归地划分为八个子节点，每个子节点对应于父节点的一个八分之一空间。这个过程会一直持续下去，直到达到预定义的停止条件，例如节点包含的对象数量小于某个阈值或达到最小节点大小。

节点结构：

每个节点包含一个包围盒（Bounding Box）用于表示该节点所包含的空间范围。节点可能包含零个或多个对象，这些对象是该节点所表示空间范围内的物体。如果节点包含的对象数量达到某个限制，或者达到最小节点大小，不再继续划分，成为叶子节点。

添加对象：

当需要向八叉树中添加对象时，从根节点开始递归地查找合适的叶子节点。将对象添加到叶子节点中。如果该节点包含的对象数量超过限制，可以考虑划分该节点。

查询操作：

对于空间查询，从根节点开始，检查查询范围与每个节点的包围盒是否相交。如果相交，进一步检查该节点的子节点。递归地沿着相交的子节点继续查询，直到达到叶子节点。叶子节点包含在查询范围内的对象。

优点：

空间局部性：八叉树有效地利用了物体在三维空间中的局部性，提高了检索效率。动态场景：适用于动态场景，因为对象的添加和删除只影响八叉树的局部结构。

应用领域：

游戏开发：用于场景管理、碰撞检测等。计算机图形学：在光照、阴影等方面的优化中有广泛应用。计算机辅助设计（CAD）：用于加速物体查询。 代码实现

1.创建项目

2.创建三个C#文件，命名为OctreeNode.cs、Octree.cs和CreateOctree.cs。

OctreeNode.cs具体代码

这个类实现了八叉树节点的功能，包括分割、添加游戏对象和绘制节点的包围盒等操作。

using System.Collections; using System.Collections.Generic; using UnityEngine; public class OctreeNode { Bounds nodeBounds; // 节点的包围盒 float minSize; // 最小节点大小 Bounds[] childBounds; // 子节点的包围盒数组 OctreeNode[] children = null; // 子节点数组 // 构造函数，接受一个包围盒和最小节点大小作为参数 public OctreeNode(Bounds b, float minNodeSize) { nodeBounds = b; minSize = minNodeSize; float quarter = nodeBounds.size.y / 4.0f; float childLength = nodeBounds.size.y / 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); } // 将游戏对象添加到节点 public void AddObject(GameObject go) { DivideAndAdd(go); } // 分割并添加游戏对象 public void DivideAndAdd(GameObject go) { if (nodeBounds.size.y <= minSize) { return; // 如果节点大小小于等于最小节点大小，停止分割 } if (children == null) { children = new OctreeNode[8]; } bool dividing = false; for (int i = 0; i < 8; i++) { if (children[i] == null) { children[i] = new OctreeNode(childBounds[i], minSize); } // 如果游戏对象的包围盒与子节点的包围盒相交，进行分割 if (childBounds[i].Intersects(go.GetComponent<Collider>().bounds)) { dividing = true; children[i].DivideAndAdd(go); } } // 如果没有进行分割，将子节点数组设为null if (dividing == false) { children = null; } } // 绘制节点的包围盒 public void Draw() { Gizmos.color = new Color(0, 1, 0); Gizmos.DrawWireCube(nodeBounds.center, nodeBounds.size); // 如果子节点不为空，递归绘制子节点 if (children != null) { for (int i = 0; i < 8; i++) { if (children[i] != null) { children[i].Draw(); // 递归调用 } } } } }

Octree.cs具体代码

这个类实现主要包括构造函数和将游戏对象添加到八叉树中的方法。八叉树的根节点存储在 rootNode 中，用于表示整个八叉树的结构。

using System.Collections; using System.Collections.Generic; using UnityEngine; public class Octree { public OctreeNode rootNode; // 八叉树的根节点 // 构造函数，接受世界中的游戏对象数组和最小节点大小作为参数 public Octree(GameObject[] worldObjects, float minNodeSize) { Bounds bounds = new Bounds(); // 用于计算包围盒的 Bounds 对象 // 遍历所有游戏对象，计算包围盒以包含它们 foreach (GameObject go in worldObjects) { bounds.Encapsulate(go.GetComponent<Collider>().bounds); } // 计算包围盒的最大边长 float maxSize = Mathf.Max(new float[] { bounds.size.x, bounds.size.y, bounds.size.z }); Vector3 sizeVector = new Vector3(maxSize, maxSize, maxSize) * 0.5f; // 将包围盒的最小和最大点调整为形成一个正方体 bounds.SetMinMax(bounds.center - sizeVector, bounds.center + sizeVector); // 创建八叉树的根节点，传入包围盒和最小节点大小 rootNode = new OctreeNode(bounds, minNodeSize); // 将世界中的游戏对象添加到八叉树中 AddObjects(worldObjects); } // 将游戏对象添加到八叉树中 public void AddObjects(GameObject[] worldObjects) { foreach (GameObject go in worldObjects) { rootNode.AddObject(go); } } }

CreateOctree.cs具体代码

这个类主要用于在启动时创建八叉树对象，并在运行时通过 OnDrawGizmos 方法绘制八叉树的根节点的包围盒。在 Start 方法中，创建了一个 Octree 对象（otree），并通过传入的世界游戏对象数组和最小节点大小进行初始化。在 OnDrawGizmos 方法中，如果应用程序正在运行，则调用八叉树的根节点的 Draw 方法来绘制八叉树的结构。

using System.Collections; using System.Collections.Generic; using UnityEngine; public class CreateOctree : MonoBehaviour { public GameObject[] worldObjects; // 存储世界中的游戏对象数组 public int nodeMinsize = 5; // 八叉树的最小节点大小 Octree otree; // 八叉树对象 // 在启动时调用，用于初始化 void Start() { otree = new Octree(worldObjects, nodeMinsize); // 创建八叉树对象并初始化 } // 在每一帧更新时调用 void OnDrawGizmos() { if (Application.isPlaying) { otree.rootNode.Draw(); // 在运行时绘制八叉树的根节点的包围盒 } } }

3.创建一个空物体（Create empty），命名为Octree，添加CreateOctree组件。

4.创建对象，调整位置和缩放比例等。（本实验创建了4个立方体，可根据情况，自由创建其他对象，注：对象一定要有碰撞器 Collier，不如会报错：NullReferenceException: Object reference not set to an instance of an object）

5.把对象添加到 world Objects中。

6.运行项目，效果如下：

参考链接

最浅显易懂的 Unity 八叉树场景管理(保姆级)-CSDN博客

Unity 八叉树空间分割的简单实现，part1， Dividing 3D Space into an Octree_哔哩哔哩_bilibili

Unity 八叉树空间分割的简单实现，part2，Dividing 3D Space into an Octree_哔哩哔哩_bilibili

Unity 八叉树空间分割的简单实现，part3，Dividing 3D Space into an Octree_哔哩哔哩_bilibili