八叉树原理
八叉树(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
原文地址:https://blog.csdn.net/weixin_43042683/article/details/135833325
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_62185.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!