unity 四叉樹管理場景

  • 2019 年 10 月 3 日
  • 筆記

聲明:參考https://blog.csdn.net/mobilebbki399/article/details/79491544和《遊戲編程模式》

當場景元素過多時,需要實時的顯示及隱藏物體使得性能提示,但是物體那麼多,怎麼知道哪些物體需要顯示,哪些物體不需要顯示的。當然,遍歷物體判斷該物體是否可以顯示是最容易想到的方法,但是每次更新要遍歷所有物體的代價很高,有沒有其他可以替代的方法呢,當然有,四叉樹就是其中一個方法。

假設場景是一維的,所有物體從左到右排成一條線,那麼用二分法就可以快速找出距離自己一定範圍內的物體。

同樣四叉樹的原理像二分一樣,只是二分法處理的是一維世界, 四叉樹處理的是二維世界,再往上三維世界用八叉樹處理,這裡用四叉樹管理,八叉樹暫時不討論,原理類似。

這裡先展示效果:

四叉樹結構:

根節點是整個場景區域,然後分成四塊:左上右上左下右下,分別作為根節點的兒子,然後每個兒子又分成四塊重複之前步驟,這就是一棵四叉樹。

每個節點保存四個兒子節點的引用,並且有存放在自己節點的物體列表,為什麼物體不全部存放在葉子節點呢?因為有可能某個物體比較大,剛好在兩個塊的邊界上。

這時候有兩種做法:

1、這個物體同時插入兩個節點的物體列表中

2、這個物體放在兩個幾點的父親節點的物體列表中

第一種方法管理起來比較麻煩,所以在此採用第二種方法。

首先定義場景物體的數據類:

 1 [System.Serializable]   2 public class ObjData   3 {   4     [SerializeField]   5     public string sUid;//獨一無二的id,通過guid創建   6     [SerializeField]   7     public string resPath;//prefab路徑   8     [SerializeField]   9     public Vector3 pos;//位置  10     [SerializeField]  11     public Quaternion rotation;//旋轉  12     public ObjData(string resPath, Vector3 pos, Quaternion rotation)  13     {  14         this.sUid = System.Guid.NewGuid().ToString();  15         this.resPath = resPath;  16         this.pos = pos;  17         this.rotation = rotation;  18     }  19 }

View Code

定義節點的介面:

 1 public interface INode   2 {   3     Bounds bound { get; set; }   4     /// <summary>   5     /// 初始化插入一個場景物體   6     /// </summary>   7     /// <param name="obj"></param>   8     void InsertObj(ObjData obj);   9     /// <summary>  10     /// 當觸發者(主角)移動時顯示/隱藏物體  11     /// </summary>  12     /// <param name="camera"></param>  13     void TriggerMove(Camera camera);  14     void DrawBound();  15 }

View Code

定義節點:

 1 public class Node : INode   2 {   3     public Bounds bound { get; set; }   4   5     private int depth;   6     private Tree belongTree;   7     private Node[] childList;   8     private List<ObjData> objList;   9  10     public Node(Bounds bound, int depth, Tree belongTree)  11     {  12         this.belongTree = belongTree;  13         this.bound = bound;  14         this.depth = depth;  15         objList = new List<ObjData>();  16     }  17  18     public void InsertObj(ObjData obj)  19     {}  20  21     public void TriggerMove(Camera camera)  22     {}  23  24     private void CerateChild()  25     {}  26 }

View Code

一棵完整的樹:

 1 public class Tree : INode   2 {   3     public Bounds bound { get; set; }   4     private Node root;   5     public int maxDepth { get; }   6     public int maxChildCount { get; }   7   8     public Tree(Bounds bound)   9     {  10         this.bound = bound;  11         this.maxDepth = 5;  12         this.maxChildCount = 4;  13         root = new Node(bound, 0, this);  14     }  15  16     public void InsertObj(ObjData obj)  17     {  18         root.InsertObj(obj);  19     }  20  21     public void TriggerMove(Camera camera)  22     {  23         root.TriggerMove(camera);  24     }  25  26     public void DrawBound()  27     {  28         root.DrawBound();  29     }  30 }

View Code

初始化場景物體時,對於每個物體,需要插入四叉樹中:判斷該物體屬於根節點的哪個兒子中,如果有多個兒子都可以包含這個物體,那麼這個物體屬於該節點,否則屬於兒子,進入兒子中重複之前的步驟。

程式碼如下:

 1 public void InsertObj(ObjData obj)   2     {   3         Node node = null;   4         bool bChild = false;   5   6         if(depth < belongTree.maxDepth && childList == null)   7         {   8             //如果還沒到葉子節點,可以擁有兒子且兒子未創建,則創建兒子   9             CerateChild();  10         }  11         if(childList != null)  12         {  13             for (int i = 0; i < childList.Length; ++i)  14             {  15                 Node item = childList[i];  16                 if (item == null)  17                 {  18                     break;  19                 }  20                 if (item.bound.Contains(obj.pos))  21                 {  22                     if (node != null)  23                     {  24                         bChild = false;  25                         break;  26                     }  27                     node = item;  28                     bChild = true;  29                 }  30             }  31         }  32  33         if (bChild)  34         {  35             //只有一個兒子可以包含該物體,則該物體  36             node.InsertObj(obj);  37         }  38         else  39         {  40             objList.Add(obj);  41         }  42     }

View Code

當role走動的時候,需要從四叉樹中找到並創建攝像機可以看到的物體

 1 public void TriggerMove(Camera camera)   2     {   3         //刷新當前節點   4         for(int i = 0; i < objList.Count; ++i)   5         {   6             //進入該節點中意味著該節點在攝像機內,把該節點保存的物體全部創建出來   7             ResourcesManager.Instance.LoadAsync(objList[i]);   8         }   9  10         if(depth == 0)  11         {  12             ResourcesManager.Instance.RefreshStatus();  13         }  14  15         //刷新子節點  16         if (childList != null)  17         {  18             for(int i = 0; i < childList.Length; ++i)  19             {  20                 if (childList[i].bound.CheckBoundIsInCamera(camera))  21                 {  22                     childList[i].TriggerMove(camera);  23                 }  24             }  25         }  26     }

View Code

遊戲運行的一開始,先構造四叉樹,並把場景物體的數據插入四叉樹中由四叉樹管理數據:

 1 [System.Serializable]   2 public class Main : MonoBehaviour   3 {   4     [SerializeField]   5     public List<ObjData> objList = new List<ObjData>();   6     public Bounds mainBound;   7   8     private Tree tree;   9     private bool bInitEnd = false;  10  11     private Role role;  12  13     public void Awake()  14     {  15         tree = new Tree(mainBound);  16         for(int i = 0; i < objList.Count; ++i)  17         {  18             tree.InsertObj(objList[i]);  19         }  20         role = GameObject.Find("Role").GetComponent<Role>();  21         bInitEnd = true;  22     }  23      ...  24 }

View Code

每次玩家移動則創建物體:

 1 [System.Serializable]   2 public class Main : MonoBehaviour   3 {   4     ...   5   6     private void Update()   7     {   8         if (role.bMove)   9         {  10             tree.TriggerMove(role.mCamera);  11         }  12     }  13     ...  14  15 }

View Code

怎麼計算出某個節點的bound是否與攝像機交叉呢?

 

我們知道,渲染管線是局部坐標系=》世界坐標系=》攝像機坐標系=》裁剪坐標系=》ndc-》螢幕坐標系,其中在後三個坐標系中可以很便捷的得到某個點是否處於攝像機可視範圍內。

在此用裁剪坐標系來判斷,省了幾次坐標轉換,判斷某個點在攝像機可視範圍內方法如下:

將該點轉換到裁剪空間,得到裁剪空間中的坐標為vec(x,y,z,w),那麼如果-w<x<w&&-w<y<w&&-w<z<w,那麼該點在攝像機可視範圍內。

對bound來說,它有8個點,當它的8個點同時處於攝像機裁剪塊上方/下方/前方/後方/左方/右方,那麼該bound不與攝像機可視範圍交叉

程式碼如下:

 1 public static bool CheckBoundIsInCamera(this Bounds bound, Camera camera)   2     {   3         System.Func<Vector4, int> ComputeOutCode = (projectionPos) =>   4         {   5             int _code = 0;   6             if (projectionPos.x < -projectionPos.w) _code |= 1;   7             if (projectionPos.x > projectionPos.w) _code |= 2;   8             if (projectionPos.y < -projectionPos.w) _code |= 4;   9             if (projectionPos.y > projectionPos.w) _code |= 8;  10             if (projectionPos.z < -projectionPos.w) _code |= 16;  11             if (projectionPos.z > projectionPos.w) _code |= 32;  12             return _code;  13         };  14  15         Vector4 worldPos = Vector4.one;  16         int code = 63;  17         for (int i = -1; i <= 1; i += 2)  18         {  19             for (int j = -1; j <= 1; j += 2)  20             {  21                 for (int k = -1; k <= 1; k += 2)  22                 {  23                     worldPos.x = bound.center.x + i * bound.extents.x;  24                     worldPos.y = bound.center.y + j * bound.extents.y;  25                     worldPos.z = bound.center.z + k * bound.extents.z;  26  27                     code &= ComputeOutCode(camera.projectionMatrix * camera.worldToCameraMatrix * worldPos);  28                 }  29             }  30         }  31         return code == 0 ? true : false;  32     }

View Code

以上是物體的創建,物體的消失放在resourcesmanager中。

建立兩個字典分別保存當前顯示的物體,和當前隱藏的物體

1 public class ResourcesManager : MonoBehaviour  2 {  3     public static ResourcesManager Instance;  4  5     ...  6     private Dictionary<string, SceneObj> activeObjDic;//<suid,SceneObj>  7     private Dictionary<string, SceneObj> inActiveObjDic;//<suid,SceneObj>  8     ...  9 }

View Code

開啟一段協程,每過一段時間就刪除在隱藏字典中的物體:

 1 private IEnumerator IEDel()   2     {   3         while (true)   4         {   5             bool bDel = false;   6             foreach(var pair in InActiveObjDic)   7             {   8                 ...   9                 Destroy(pair.Value.obj);  10             }  11             InActiveObjDic.Clear();  12             if (bDel)  13             {  14                 Resources.UnloadUnusedAssets();  15             }  16             yield return new WaitForSeconds(delTime);  17         }  18     }

View Code

每次triggerMove創建物體後刷新資源狀態,將此次未進入節點(status = old)的物體從顯示字典中移到隱藏字典中,並將此次進入節點(status = new)的物體標記為old為下次創建做準備

 1 public void RefreshStatus()   2     {   3         DelKeysList.Clear();   4         foreach (var pair in ActiveObjDic)   5         {   6             SceneObj sceneObj = pair.Value;   7             if(sceneObj.status == SceneObjStatus.Old)   8             {   9                 DelKeysList.Add(pair.Key);  10             }  11             else if(sceneObj.status == SceneObjStatus.New)  12             {  13                 sceneObj.status = SceneObjStatus.Old;  14             }  15         }  16         for(int i = 0; i < DelKeysList.Count; ++i)  17         {  18             MoveToInActive(ActiveObjDic[DelKeysList[i]].data);  19         }  20     }

View Code

 

至此,比較簡單的四叉樹就完畢了。

更複雜的四叉樹還需要實現物體在節點之間移動,比如物體是動態的可能從某個節點塊移動到另個節點塊;物體不消失而用LOD等,在此就不討論了

 

項目地址:https://github.com/MCxYY/unity-Multi-tree-manage-scenario