知了博客

集天地之精华，吸日月之灵气

« [转]Apktool（1）——Apktool的安装你丫才美工：“设计师们说，他们每天都上这些网站！” »

2018-7-24 16:53:47

【Unity】四叉树/八叉树管理和动态加载场景物件

 一、引言：

场景的组织与管理是3d游戏开发中重要的一环，unity3d引擎中，只提供了最基本的场景组织，当我们加载场景时，会将场景中的物件及其依赖的资源全部加载出来，这对于较为庞大的场景显然是不合理的。可以考虑在进入场景时预先将可见范围内的物体加载，之后的其它物件也全部在当进入可见区域时加载，但如何才能快速索引到进入某区域的物体？因此，我们需要考虑一种层次化的场景管理机制，可以快速的索引出指定空间区域内的物体，以实现这种效果。
 
二、几何剖分技术：
几何剖分技术是一种能将场景中的几何物体通过层次性机制组织，使用时可以快速剔除层次树的整个分支，从而加快索引几何体的过程。四叉树（quad tree）和八叉树（octree）是一种常用的空间剖分方法，它将已知的空间分成四/八个子空间作为节点，每个节点又划分成四/八个子空间，依此递归，直到达到指定深度。
 
四叉树：
 
 
八叉树：
 
 
三、原理：
四叉树/八叉树的数据结构不算复杂，其节点主要包含如下成员：数据成员Data，节点的包围盒信息Bounds，用于确定节点的空间信息（对于2D情况的四叉树，也可以是Rect），子节点引用。其中树的根节点拥有最大的Bounds，其子节点的Bounds将其分割成四/八个子Bounds。这样每次我们需要查找某点附近的数据时，可以根据节点的Bounds快速的剔除掉大量不需要查找的物体。
 
注意，由于插入的数据成员本身也包含空间位置和大小信息，可能出现数据刚好处于节点的边界上，如下：
如图中右上角的星星图案，其刚好位于两个节点的边界上，此时的处理方法有：
1.两个节点同时包含该数据
2.由父节点包含该数据（这样意味着不仅仅只有叶子节点可以存储数据）
 
第一种方式尽管相对精确，但如果存在特别大的物体可能覆盖多个节点，那就需要同时被这些节点引用，不容易管理。
本文的实现采用了第二种方式，一些很小的物体也可能出现没有插入到叶子节点而导致范围过大，特别的，如果该物体恰巧位于四叉树区域的正中心，则其只能被四叉树的根节点所包含。
 
另外还可以通过实现松散四叉树的方式，不在本文讨论范围内，可以查阅相关的文档或博客。
 
 
四、实现：
1.检索进入指定区域的物体
抽象出了一个检测器接口：
 
  1.  
    /// <summary>
  2.  
    /// 检测器接口，用于检测和场景物件的触发
  3.  
    /// </summary>
  4.  
    public interface IDetector
  5.  
    {
  6.  
    /// <summary>
  7.  
    /// 是否检测成功
  8.  
    /// </summary>
  9.  
    /// <param name="bounds">包围盒</param>
  10.  
    /// <returns></returns>
  11.  
    bool IsDetected(Bounds bounds);
  12.  
     
  13.  
    /// <summary>
  14.  
    /// 触发器位置
  15.  
    /// </summary>
  16.  
    Vector3 Position { get; }
  17.  
    }
 
 
对于场景树中存储的节点和节点下的物体数据，其全部包含了一个Bounds数据，用于确定该节点或该场景物体的包围盒区域，这样每次进行检索时，实际上就是调用具体Detector的IsDetected接口，并传入Bounds，以判断该节点或该场景物体是否可以被检索。
 
我目前实现了两种形式的Detector，一种通过简单的设置Detector周围指定范围的六面体区域作为可见区域，另一种则是基于相机视锥体的判断，两种效果如下：
基于简单的六面体区域：
 
  1.  
    /// <summary>
  2.  
    /// 该触发器根据六面体包围盒区域触发
  3.  
    /// </summary>
  4.  
    public class SceneTransformDetector : SceneDetectorBase
  5.  
    {
  6.  
    public Vector3 detectorSize;
  7.  
     
  8.  
    private Bounds m_Bounds;
  9.  
     
  10.  
    public override bool IsDetected(Bounds bounds)
  11.  
    {
  12.  
    m_Bounds.center = Position;
  13.  
    m_Bounds.size = detectorSize;
  14.  
    return bounds.Intersects(m_Bounds);
  15.  
    }
  16.  
    }

 
基于相机视锥体：
  1.  
    /// <summary>
  2.  
    /// 该触发器根据相机裁剪区域触发
  3.  
    /// </summary>
  4.  
    public class SceneCameraDetector : SceneDetectorBase
  5.  
    {
  6.  
    private Camera m_Camera;
  7.  
     
  8.  
    void Start()
  9.  
    {
  10.  
    m_Camera = gameObject.GetComponent<Camera>();
  11.  
    }
  12.  
     
  13.  
    public override bool IsDetected(Bounds bounds)
  14.  
    {
  15.  
    if (m_Camera == null)
  16.  
    return false;
  17.  
    return bounds.IsBoundsInCamera(m_Camera);
  18.  
    }
  19.  
    }
 
2.删除区域外的物体
对于场景物体，为每个物体初始化一个权重数据，每次物体被检索，权重进行累加，超出区域的物体则被推入一个优先级队列，该优先级队列根据权重排序，权重越大，表示在场景中滞留的时间越久，说明该物体出现的几率比较频繁，则删除的时机越靠后。一旦物体销毁，权重归零。
 
 
 
 
未完善的地方
由于待加载的物体是预先计算其包围盒并插入四叉树/八叉树中，如果涉及到物体的变换，考虑到需要更新物体的包围盒，这将影响原始物体在树中的信息，例如更新后的包围盒超出了物体所在节点的包围盒，导致不得不重新计算物体在树中的位置，因此该demo中暂时不涉及被加载物体会动态变换的情况，即目前仅适用于静态物体的加载。（当然如果物体的变换不会导致包围盒更新，例如播放一些原地不动的动画，则是可以支持的）
 
 
Demo下载地址请浏览我的博客原文：点击打开链接
Tags: unity  
发布:webgou | 分类:编程开发 | 评论:0 | 引用:0 | 浏览:

发表评论:

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

日历

最新评论及回复

最近发表

Powered By Z-Blog 1.8 Arwen Build 90619 Code detection by Codefense  theme by BokeZhuti

Copyright know blog. Some Rights Reserved.站长(msn):webmaster#webgou.info(#换成@) 粤ICP备09183716号