+ misc

1 files changed, 100 insertions, 44 deletions

diff --git a/marching/Assets/Scripts/Physics/Quadtree.cs b/marching/Assets/Scripts/Physics/Quadtree.cs
index af7a005..4185f1f 100644
--- a/marching/Assets/Scripts/Physics/Quadtree.cs
+++ b/marching/Assets/Scripts/Physics/Quadtree.cs
@@ -1,3 +1,5 @@
+using JetBrains.Annotations;
+using System;
 using System.Collections;
 using System.Collections.Generic;
 using System.Drawing;
@@ -16,8 +18,8 @@ namespace mh
 
     public class Quadtree
     {
-        public const int kMaxObjectsPerBlock = 4;
-        public const int kMaxLevel = 20;
+        public const int kMaxObjectsPerBlock = 5;
+        public const int kMaxLevel = 6;
 
         private int m_Level;
         private Vector4 m_Bounds; // x,y,z,w => posx,posy,width,height 
@@ -119,69 +121,86 @@ namespace mh
             m_SubTrees[3] = QueryQuadtree(m_Level + 1, new Vector4(x + subWidth / 2, y - subHeight / 2, subWidth, subHeight));
         }
 
-        // x, y, z, w
         /// <summary>
-        /// -1表示没法完全放在一个subTree: subtree交界或者整个越界
+        /// 0表示没法完全放在一个subTree: subtree交界或者整个越界
         /// </summary>
         /// <param name="bound"></param>
         /// <returns></returns>
-        public int GetSubtreeIndex(Vector4 bound)
+        public int GetSubtreeIndices(Vector4 bound)
         {
+            int indices = 0;
             float halfw = bound.z / 2;
             float halfh = bound.w / 2;
-            float lowerx = bound.x - halfw; 
-            float higherx = bound.x + halfw;    
+            float lowerx = bound.x - halfw;
+            float higherx = bound.x + halfw;
             float lowery = bound.y - halfh;
             float highery = bound.y + halfh;
-            bool bFitInLeft = lowerx >= left && higherx <= x;
-            bool bFitInRight = lowerx >= x && higherx <= right;
-            bool bFitInTop = lowery >= y && highery <= top;
-            bool bFitInBottom = lowery >= bottom && highery <= y;
-            if (bFitInRight && bFitInTop) return 0;
-            if (bFitInLeft && bFitInTop) return 1;
-            if (bFitInLeft && bFitInBottom) return 2;
-            if (bFitInRight && bFitInBottom) return 3;
-            return -1;
+            bool startIsNorth = highery > y;
+            bool startIsWest = lowerx < x;
+            bool endIsEast = higherx > x;
+            bool endIsSouth = lowery < y;
+            //top-right quad
+            if (startIsNorth && endIsEast)
+            {
+                indices |= 1;
+            }
+
+            //top-left quad
+            if (startIsWest && startIsNorth)
+            {
+                indices |= 1 << 1;
+            }
+
+            //bottom-left quad
+            if (startIsWest && endIsSouth)
+            {
+                indices |= 1 << 2;
+            }
+
+            //bottom-right quad
+            if (endIsEast && endIsSouth)
+            {
+                indices |= 1 << 3;
+            }
+
+            return indices;
         }
 
         public void Insert(IQuadTreeObject obj)
         {
-            int index = GetSubtreeIndex(obj.bound);
-            if(index != -1)
+            if (m_SubTrees[0] != null)
             {
-                if (m_SubTrees[0] == null) Split();
-                m_SubTrees[index].Insert(obj);
+                int indices = GetSubtreeIndices(obj.bound);
+                for(int i = 0; i < 4; i++)
+                {
+                    if((indices & (1 << i)) != 0)
+                    {
+                        m_SubTrees[i].Insert(obj);
+                    }
+                }
                 return;
             }
 
-            //if (m_SubTrees[0] != null)
-            //{
-            //    if (index != -1)
-            //    {
-            //        m_SubTrees[index].Insert(obj);
-            //        return;
-            //    }
-            //}
-
             m_Objects.Add(obj);
 
-            if(m_Objects.Count > kMaxObjectsPerBlock && m_Level < kMaxLevel) // 本层满了之后重新排布层内对象
+            if (m_Objects.Count > kMaxObjectsPerBlock && m_Level < kMaxLevel) // 本层满了之后重新排布层内对象
             {
                 if (m_SubTrees[0] == null) Split();
 
-                for(int i = m_Objects.Count - 1; i >= 0; i--) 
+                for (int i = m_Objects.Count - 1; i >= 0; i--)
                 {
-                    index = GetSubtreeIndex(m_Objects[i].bound);
-                    if(index != -1) 
+                    int indices = GetSubtreeIndices(m_Objects[i].bound);
+                    for (int j = 0; j < 4; j++)
                     {
-                        IQuadTreeObject o = m_Objects[i];
-                        m_Objects.RemoveAt(i);
-                        m_SubTrees[index].Insert(o);
+                        if ((indices & (1 << j)) != 0)
+                        {
+                            m_SubTrees[j].Insert(m_Objects[i]);
+                        }
                     }
                 }
-            }
 
-          // Debug.Log(m_Objects.Count);
+                m_Objects.Clear();
+            }
         }
 
         /// <summary>
@@ -192,15 +211,52 @@ namespace mh
         /// <returns></returns>
         public bool Retrieve(ref List<IQuadTreeObject> returnObjs, IQuadTreeObject obj)
         {
-            int index = GetSubtreeIndex(obj.bound);
-            returnObjs.AddRange(m_Objects);
-            if (index != -1 && m_SubTrees[0] != null)
+            for(int i = 0; i < m_Objects.Count; ++i)
             {
-                m_SubTrees[index].Retrieve(ref returnObjs, obj);
+                if (!returnObjs.Contains(m_Objects[i]) && obj != m_Objects[i])
+                {
+                    returnObjs.Add(m_Objects[i]);
+                }
             }
-            if(returnObjs.Contains(obj))
+            if (m_SubTrees[0] != null)
             {
-                returnObjs.Remove(obj);
+                int indices = GetSubtreeIndices(obj.bound);
+                for (int i = 0; i < 4; i++)
+                {
+                    if ((indices & (1 << i)) != 0)
+                    {
+                        m_SubTrees[i].Retrieve(ref returnObjs, obj);
+                    }
+                }
+            }
+            return returnObjs.Count > 0;
+        }
+
+        /// <summary>
+        /// 获得可能和obj碰撞的对象（不包括自己）
+        /// </summary>
+        /// <param name="returnObjs"></param>
+        /// <param name="obj"></param>
+        /// <returns></returns>
+        public bool Retrieve(ref List<IQuadTreeObject> returnObjs, Vector4 bound)
+        {
+            for (int i = 0; i < m_Objects.Count; ++i) // 根节点count==0
+            {
+                if (!returnObjs.Contains(m_Objects[i]))
+                {
+                    returnObjs.Add(m_Objects[i]);
+                }
+            }
+            if (m_SubTrees[0] != null)
+            {
+                int indices = GetSubtreeIndices(bound);
+                for (int i = 0; i < 4; i++)
+                {
+                    if ((indices & (1 << i)) != 0)
+                    {
+                        m_SubTrees[i].Retrieve(ref returnObjs, bound);
+                    }
+                }
             }
             return returnObjs.Count > 0;
         }