基于ET的四叉树场景管理组件

前言

​ 四叉树/八叉树的场景管理广泛应用于RPG类型游戏，其优点在于缩小了判断检测所需的范围，只需要通过简单的矩形的碰撞检测找到对应相交的四叉树/八叉树节点，再对节点内的Entity进行相交判断即可，而无需遍历场景内所有的物体进行碰撞检测。极大的优化了类似于MMORPG这种多人游戏的技能释放判定检测。

​ 感谢Yogi大佬提供的思路，自身在已有思路下进行了动态增加/移除四叉树中管理物体的接口拓展。

实现思路：

• 确定划分颗粒度（代表一个节点内的物体数量,一旦超过这个数量就要进行下一层的划分），最小划分范围（代表一个节点x的最小范围，小于这个范围则不再划分）
• 将场景中需要管理的GameObject与其Render中的Bounds通过ObjectBase类进行整合，同时因为一个Bounds可能会与四叉树的多个节点，即存储在多个QuadTreeNode种，可以用ActiveCount记录下当前判定范围下（如摄像机视椎体）与其所在QuadTreeNode碰撞的个数
• 将ObjectBase统一加入到AllItems的字典中，每个Objectbase对应一个ItemIndex，方便进行移除
• 通过split()进行划分
  • 对于根结点
    • 获取当前cubes下所有Item的MinX，MaxX，MinY，MaxY，构建出总的Bounds
    • 将根结点划分为左上、左下、右上、右下四个区域，设定新的Bounds
    • 遍历cubes中所有item，将item.bounds与某区域（即QuadTreeNode）Bounds交叉的Item加入到对应区域itemData中，若ItemData中的count>划分颗粒度，则进行下一层递归划分
  • 对于子节点
    • 将根结点划分为左上、左下、右上、右下四个区域，设定新的Bounds
    • 遍历cubes中所有item，将item.bounds与某区域（即QuadTreeNode）Bounds交叉的Item加入到对应区域itemData中，若ItemData中的count>划分颗粒度，则进行下一层递归划分

附上部分关键代码：

节点划分：

   /// <summary>
      /// 四叉树节点划分
      /// </summary>
      public static void Split(this SceneTreeModule self)
      {
          self.Split(self.AllItems.Values.ToList(),null);
      }
/// <summary>
      /// 划分递归函数
      /// </summary>
      /// <param name="cubes"></param>
      /// <param name="parent"></param>
      private static void Split(this SceneTreeModule self,List<ObjectBase> cubes, QuadTreeNode parent)
      {
          //1.求中心点位置
          //2.求四个子结点位置
          //3.求各个节点的bounds大小
          QuadTreeNode Root, LT, RT, LB, RB;
          
          // 二分之一
          float halfX, halfZ, halfY;
          // 四分之一
          float quarterX, quarterZ, quarterY;

          Vector3 center;
          
          //初始生成的情况下
          if (parent == null)
          {
              float minX = float.MaxValue,
                  minZ = float.MaxValue,
                  minY = float.MaxValue,
                  maxX = float.MinValue,
                  maxZ = float.MinValue,
                  maxY = float.MinValue;
              
              //根据当前的Tree内的Cube确定初始的Root包围盒
              foreach (var cube in cubes)
              {
                  var cubeBound = cube.bounds;
                  Vector3 boundsMin, boundsMax;
                  boundsMin = cube.bounds.min;
                  boundsMax = cube.bounds.max;

                  minX = Mathf.Min(boundsMin.x, minX);
                  minY = Mathf.Min(boundsMin.y, minY);
                  minZ = Mathf.Min(boundsMin.z, minZ);

                  maxX = Mathf.Max(boundsMax.x, maxX);
                  maxY = Mathf.Max(boundsMax.y, maxY);
                  maxZ = Mathf.Max(boundsMax.z, maxZ);
              }

              halfX = (maxX - minX) / 2;
              halfY = (maxY - minY) / 2;
              halfZ = (maxZ - minZ) / 2;
              quarterX = halfX / 2;
              quarterY = halfY / 2;
              quarterZ = halfZ / 2;
              center = new Vector3(minX + halfX, minY + halfY, minZ + halfZ);

              self.Root = Root = self.AddChild<QuadTreeNode>();
              //生成包围盒
              Root.Bounds = new Bounds(center, new Vector3(halfX, halfY, halfZ) * 2);
          }
          //递归生成的情况下
          else
          {
              var halfParentSize = parent.Bounds.size / 2;

              halfX = halfParentSize.x;
              halfY = halfParentSize.y ;
              halfZ = halfParentSize.z;
              //因为是四叉树Y是不变的
              quarterX = halfX / 2;
              quarterZ = halfZ / 2;

              Root = parent;
              center = parent.Bounds.center;
          }

          var ltPos = center + new Vector3(-quarterX, 0, +quarterZ);
          var rtPos = center + new Vector3(+quarterX, 0, +quarterZ);
          var lbPos = center + new Vector3(-quarterX, 0, -quarterZ);
          var rbPos = center + new Vector3(+quarterX, 0, -quarterZ);
          
          LT = Root.AddChild<QuadTreeNode>();
          LT.Bounds = new Bounds(ltPos, new Vector3(halfX, halfY*2,halfZ));

          RT = Root.AddChild<QuadTreeNode>();
          RT.Bounds = new Bounds(rtPos, new Vector3(halfX, halfY*2, halfZ));

          LB = Root.AddChild<QuadTreeNode>();
          LB.Bounds = new Bounds(lbPos, new Vector3(halfX, halfY*2, halfZ));

          RB = Root.AddChild<QuadTreeNode>();
          RB.Bounds = new Bounds(rbPos, new Vector3(halfX, halfY*2, halfZ));
          
          Root.AddChildNode(LT);
          Root.AddChildNode(RT);
          Root.AddChildNode(LB);
          Root.AddChildNode(RB);

          foreach (var cube in cubes)
          {
              var cubeBound = cube.bounds;
              QuadTreeNode node = null;
              //MARKER：判断相交后添加到对应的四叉树节点中
              foreach (var child in Root.child)
              {
                  if (child.Bounds.Intersects(cubeBound))
                  {
                      child.AddItem(cube);
                  }
              }
          }
          
          // 递归所有子节点（如果子节点中包含多个Child）
          for (var i = 0; i < Root.child.Count; i++)
          {
              var x = Root.child[i];
              //MARKER:移除没有剔除物体的节点
              if (x.ItemData.Count == 0)
              {
                  Root.child.RemoveAt(i);
                  i--;
              }
              
              //判断是否需要进一步划分
              if (x.ItemData.Count > self.MaxCellCount && x.Bounds.size.x > self.MinCellRange)
              {
                  var needSplitData = new List<ObjectBase>();
                  needSplitData.AddRange(x.ItemData);
                  x.ClearObj(); 
                  self.Split(needSplitData,x);
              }
          }
      }

动态增加/删除管理物体对象：

/// <summary>
    /// 后续加入新的Item并更新四叉树（需要先init同时满足物品在init时Root的bounds中）
    /// </summary>
    /// <param name="self"></param>
    /// <param name="go"></param>
    /// <param name="bounds"></param>
    public static void AddItemAndUpdateTree(this SceneTreeModule self, GameObject go, Bounds bounds)
    {
     if (!self.IsInitOver)
     {
         Debug.LogWarning("You must init Tree first");
         return;
     }
     
     var item = new ObjectItem(go, bounds);
     self.AllItems.Add(self.GetItemIndex(),item);
     
     //找到对应的相交的QuadTreeNode集合
     List<QuadTreeNode> nodes = new List<QuadTreeNode>();
     FindTreeNodesByBounds(self.Root,bounds,nodes);

     foreach (var node in nodes)
     {
         node.AddItem(item);
         //判断是否需要再分
         if (node.ItemData.Count > self.MaxCellCount && node.Bounds.size.x > self.MinCellRange)
         {
             var needSplitData = new List<ObjectBase>();
             needSplitData.AddRange(node.ItemData);
             node.ClearObj();
             self.Split(needSplitData,node);
         }
     }
    }
    
    /// <summary>
    /// 在四叉树场景树管理组件中移除Item
    /// </summary>
    /// <param name="self"></param>
    /// <param name="itemIndex"></param>
    public static void RemoveItemAndUpdateTree(this SceneTreeModule self, int itemIndex)
    {
        if (self.AllItems.ContainsKey(itemIndex))
        {
            ObjectBase item = self.AllItems[itemIndex];
            self.AllItems.Remove(itemIndex);
            RemoveItemInTree(self.Root,item);
        }
    }
    
    /// <summary>
    /// DFS在场景树中移除Item
    /// </summary>
    /// <param name="self"></param>
    /// <param name="objectBase"></param>
    private static void RemoveItemInTree(QuadTreeNode node, ObjectBase item)
    {
        if(node==null) return;
        if (node.ItemData.Contains(item))
        {
            node.ItemData.Remove(item);
        }

        for (int i = 0; i < node.child.Count; i++)
        {
            var child = node.child[i];
            RemoveItemInTree(child,item);
            if (child.ItemData.Count == 0)
            {
                node.child.RemoveAt(i);
                i--;
            }
        }
    }

    /// <summary>
    /// 找到对应最小的QuadTreeNode集合
    /// </summary>
    /// <param name="self"></param>
    private static void FindTreeNodesByBounds(QuadTreeNode root, Bounds bound,List<QuadTreeNode> nodes)
    {
     foreach (var child in root.child)
     {
         if (child.Bounds.Intersects(bound))
         {
             //不可再分
             if (root.child == null || root.child.Count == 0)
             {
                 nodes.Add(child);
             }
             else
             {
                 FindTreeNodesByBounds(child,bound,nodes);
             }
         }
     }
    }

判断点在视椎体(多平面)内/外：

△主要在于Vector4对平面plane的定义和表示，用平面法线的x、y、z作为前三个变量，用-Vector3.Dot(normal,point) 表示最后一个向量，理解起来的话是用原点向平面内某点建立射线，并使其与单位法线向量点乘计算出偏移量（投影），配合法线确定平面位置。

同时也是一般式的一种体现：

最终判定点在平面内外其实也是判定原点到该点的射线对于单位法线的偏移量与平面内点的偏移量进行对比，若大于则表示在平面外。

/// <summary>
   /// 平面内一点和法线确定平面
   /// 取自公式(p-p‘)*N=0 （即平面内任意线段垂直于法线）
   /// </summary>
   /// <param name="normal"></param>
   /// <param name="point"></param>
   /// <returns></returns>
   public static Vector4 GetPlane(Vector3 normal, Vector3 point)
   {
       return new Vector4(normal.x, normal.y, normal.z, -Vector3.Dot(normal, point));
   }

   /// <summary>
   /// 三点确定一个平面
   /// MARKER:Unity为左手坐标系，所以叉乘方向遵循左手定则
   /// </summary>
   /// <param name="a"></param>
   /// <param name="b"></param>
   /// <param name="c"></param>
   /// <returns></returns>
   public static Vector4 GetPlane(Vector3 a, Vector3 b, Vector3 c)
   {
       Vector3 normal = Vector3.Normalize(Vector3.Cross(b - a, c - a));//单位法线向量
       return GetPlane(normal, a);
   }
   
   /// <summary>
   /// 获取相机裁剪远平面的所有顶点
   /// </summary>
   /// <param name="camera"></param>
   /// <returns></returns>
   public static Vector3[] GetCameraFarClipPlanePoint(Camera camera)
   {
       Vector3[] points = new Vector3[4];
       Transform transform = camera.transform;
       float distance = camera.farClipPlane;//远裁剪平面的距离
       float halfFovRad = Mathf.Deg2Rad * camera.fieldOfView * 0.5f;
       float halfUpLen = distance * Mathf.Tan(halfFovRad); //MARKER：这里事先选择的Fov Axis是Vertical,所以计算出来的是视锥体的半高度
       float halfRightLen = halfUpLen * camera.aspect;
       Vector3 farCenterPoint = transform.position + distance * transform.forward;
       Vector3 halfUp = halfUpLen * transform.up;
       Vector3 halfRight = halfRightLen * transform.right;
       points[0] = farCenterPoint - halfRight + halfUp;//Left-Top
       points[1] = farCenterPoint + halfRight + halfUp;//Right-Top
       points[2] = farCenterPoint - halfRight - halfUp;//Left-Bottom
       points[3] = farCenterPoint + halfRight - halfUp;//Right-Bottom
       return points;
   }

   /// <summary>
   /// 获取视锥体的六个平面
   /// </summary>
   /// <param name="camera"></param>
   /// <returns></returns>
   public static Vector4[] GetFrustumPlane(Camera camera)
   {
       //模拟的是透视投影
       Vector4[] planes = new Vector4[6];
       Transform transform = camera.transform;
       Vector3 cameraPosition = transform.position;
       Vector3[] points = GetCameraFarClipPlanePoint(camera);
       
       //顺时针(右手定则)
       planes[0] = GetPlane(cameraPosition, points[0], points[1]);
       planes[1] = GetPlane(cameraPosition, points[1], points[3]);
       planes[2] = GetPlane(cameraPosition, points[3], points[2]);
       planes[3] = GetPlane(cameraPosition, points[2], points[0]);
       planes[4] = GetPlane(-transform.forward, transform.position + transform.forward * camera.nearClipPlane);//通过法线和法线外一点求近平面
       planes[5] = GetPlane(transform.forward, transform.position + transform.forward * camera.farClipPlane);//通过法线和法线外一点求远平面
       return planes;
   }

   /// <summary>
   /// 判断点是否在平面外
   /// </summary>
   /// <param name="plane"></param>
   /// <param name="pointPosition"></param>
   /// <returns></returns>
   public static bool isOutSideThePlane(Vector4 plane, Vector3 pointPosition)
   {
       if (Vector3.Dot(plane, pointPosition) + plane.w > 0)//对于处在这个平面上所有点来说，其点乘法线的值都为0，只要现在判断点与平面内一点的连线与法线夹角小于90°则表示其在平面外
       {
           return true;
       }

       return false;
   }