宿迁seo,优化网站排名解析推广,12360官方网站下载,手机百度屏蔽我网站关键词八叉树原理
八叉树#xff08;Octree#xff09;是一种用于在三维空间中进行空间分割的数据结构。它将三维空间递归地划分为八个子空间#xff0c;每个子空间对应于一个八叉树节点。这种分割方式可以有效地组织和管理场景中的对象#xff0c;提高检索效率#xff0c;特别…八叉树原理
八叉树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.GetComponentCollider().bounds)){dividing true;children[i].DivideAndAdd(go);}}// 如果没有进行分割将子节点数组设为nullif (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.GetComponentCollider().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 八叉树空间分割的简单实现part2Dividing 3D Space into an Octree_哔哩哔哩_bilibili
Unity 八叉树空间分割的简单实现part3Dividing 3D Space into an Octree_哔哩哔哩_bilibili
