1 files changed, 167 insertions, 0 deletions
diff --git a/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
new file mode 100644
index 0000000..c7b0524
--- /dev/null
+++ b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
@@ -0,0 +1,167 @@
+using System;
+using System.Collections.Generic;
+using System.Text;
+using OpenSim.Region.Environment.Scenes;
+namespace OpenSim.Region.Environment.Types
+{
+    public class BasicQuadTreeNode
+    {
+        private List<SceneObjectGroup> m_objects = new List<SceneObjectGroup>();
+        private BasicQuadTreeNode[] m_childNodes = null;
+        private BasicQuadTreeNode m_parent = null;
+        private short m_leftX;
+        private short m_leftY;
+        private short m_width;
+        private short m_height;
+        public BasicQuadTreeNode(BasicQuadTreeNode parent, short leftX, short leftY, short width, short height)
+        {
+            m_parent = parent;
+            m_leftX = leftX;
+            m_leftY = leftY;
+            m_width = width;
+            m_height = height;
+        }
+        public void AddObject(SceneObjectGroup obj)
+        {
+            if (m_childNodes == null)
+            {
+                if (!m_objects.Contains(obj))
+                {
+                    m_objects.Add(obj);
+                }
+            }
+            else
+            {
+                if (obj.AbsolutePosition.X < (m_leftX + (m_width / 2)))
+                {
+                    if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
+                    {
+                        m_childNodes[0].AddObject(obj);
+                    }
+                    else
+                    {
+                        m_childNodes[2].AddObject(obj);
+                    }
+                }
+                else
+                {
+                    if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
+                    {
+                        m_childNodes[1].AddObject(obj);
+                    }
+                    else
+                    {
+                        m_childNodes[3].AddObject(obj);
+                    }
+                }
+            }
+        }
+        public void Subdivide()
+        {
+            if (m_childNodes == null)
+            {
+                m_childNodes = new BasicQuadTreeNode[4];
+                m_childNodes[0] = new BasicQuadTreeNode(this, m_leftX, m_leftY,(short) (m_width / 2), (short)( m_height / 2));
+                m_childNodes[1] = new BasicQuadTreeNode(this,(short)( m_leftX + (m_width / 2)), m_leftY,(short)( m_width / 2),(short) (m_height / 2));
+                m_childNodes[2] = new BasicQuadTreeNode(this, m_leftX, (short)( m_leftY + (m_height / 2)), (short)(m_width / 2),(short)( m_height / 2));
+                m_childNodes[3] = new BasicQuadTreeNode(this, (short)( m_leftX + (m_width / 2)),(short)( m_height + (m_height / 2)),(short)( m_width / 2), (short)(m_height / 2));
+            }
+            else
+            {
+                for (int i = 0; i < m_childNodes.Length; i++)
+                {
+                    m_childNodes[i].Subdivide();
+                }
+            }
+        }
+        public List<SceneObjectGroup> GetObjectsFrom(int x, int y)
+        {
+            if (m_childNodes == null)
+            {
+                return m_objects;
+            }
+            else
+            {
+                if (x < (m_leftX + (m_width / 2)))
+                {
+                    if (y < (m_leftY + (m_height / 2)))
+                    {
+                        return m_childNodes[0].GetObjectsFrom(x, y);
+                    }
+                    else
+                    {
+                        return m_childNodes[2].GetObjectsFrom(x, y);
+                    }
+                }
+                else
+                {
+                    if (y < (m_leftY + (m_height / 2)))
+                    {
+                        return m_childNodes[1].GetObjectsFrom(x, y);
+                    }
+                    else
+                    {
+                        return m_childNodes[3].GetObjectsFrom(x, y);
+                    }
+                }
+            }
+        }
+        public void Update()
+        {
+            if (m_childNodes != null)
+            {
+                for (int i = 0; i < 4; i++)
+                {
+                    m_childNodes[i].Update();
+                }
+            }
+            else
+            {
+                List<SceneObjectGroup> outBounds = new List<SceneObjectGroup>();
+                foreach (SceneObjectGroup group in m_objects)
+                {
+                    if (((group.AbsolutePosition.X > m_leftX) && (group.AbsolutePosition.X < (m_leftX + m_width))) && ((group.AbsolutePosition.Y > m_leftY) && (group.AbsolutePosition.Y < (m_leftY + m_height))))
+                    {
+                        //still in bounds
+                    }
+                    else
+                    {
+                        outBounds.Add(group);
+                    }
+                }
+                foreach (SceneObjectGroup removee in outBounds)
+                {
+                    m_objects.Remove(removee);
+                    if (m_parent != null)
+                    {
+                        m_parent.PassUp(removee);
+                    }
+                }
+                outBounds.Clear();
+            }
+        }
+        public void PassUp(SceneObjectGroup group)
+        {
+            if (((group.AbsolutePosition.X > m_leftX) && (group.AbsolutePosition.X < (m_leftX + m_width))) && ((group.AbsolutePosition.Y > m_leftY) && (group.AbsolutePosition.Y < (m_leftY + m_height))))
+            {
+                this.AddObject(group);
+            }
+            else
+            {
+                if (m_parent != null)
+                {
+                    m_parent.PassUp(group);
+                }
+            }
+        }
+    }
+}

diff --git a/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs new file mode 100644 index 0000000..c7b0524 --- /dev/null +++ b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
@@ -0,0 +1,167 @@
	1	using System;
	2	using System.Collections.Generic;
	3	using System.Text;
	4	using OpenSim.Region.Environment.Scenes;
	5
	6	namespace OpenSim.Region.Environment.Types
	7	{
	8	public class BasicQuadTreeNode
	9	{
	10	private List<SceneObjectGroup> m_objects = new List<SceneObjectGroup>();
	11	private BasicQuadTreeNode[] m_childNodes = null;
	12	private BasicQuadTreeNode m_parent = null;
	13
	14	private short m_leftX;
	15	private short m_leftY;
	16	private short m_width;
	17	private short m_height;
	18
	19	public BasicQuadTreeNode(BasicQuadTreeNode parent, short leftX, short leftY, short width, short height)
	20	{
	21	m_parent = parent;
	22	m_leftX = leftX;
	23	m_leftY = leftY;
	24	m_width = width;
	25	m_height = height;
	26	}
	27
	28	public void AddObject(SceneObjectGroup obj)
	29	{
	30	if (m_childNodes == null)
	31	{
	32	if (!m_objects.Contains(obj))
	33	{
	34	m_objects.Add(obj);
	35	}
	36	}
	37	else
	38	{
	39	if (obj.AbsolutePosition.X < (m_leftX + (m_width / 2)))
	40	{
	41	if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
	42	{
	43	m_childNodes[0].AddObject(obj);
	44	}
	45	else
	46	{
	47	m_childNodes[2].AddObject(obj);
	48	}
	49	}
	50	else
	51	{
	52	if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
	53	{
	54	m_childNodes[1].AddObject(obj);
	55	}
	56	else
	57	{
	58	m_childNodes[3].AddObject(obj);
	59	}
	60	}
	61	}
	62	}
	63
	64	public void Subdivide()
	65	{
	66	if (m_childNodes == null)
	67	{
	68	m_childNodes = new BasicQuadTreeNode[4];
	69	m_childNodes[0] = new BasicQuadTreeNode(this, m_leftX, m_leftY,(short) (m_width / 2), (short)( m_height / 2));
	70	m_childNodes[1] = new BasicQuadTreeNode(this,(short)( m_leftX + (m_width / 2)), m_leftY,(short)( m_width / 2),(short) (m_height / 2));
	71	m_childNodes[2] = new BasicQuadTreeNode(this, m_leftX, (short)( m_leftY + (m_height / 2)), (short)(m_width / 2),(short)( m_height / 2));
	72	m_childNodes[3] = new BasicQuadTreeNode(this, (short)( m_leftX + (m_width / 2)),(short)( m_height + (m_height / 2)),(short)( m_width / 2), (short)(m_height / 2));
	73	}
	74	else
	75	{
	76	for (int i = 0; i < m_childNodes.Length; i++)
	77	{
	78	m_childNodes[i].Subdivide();
	79	}
	80	}
	81	}
	82
	83	public List<SceneObjectGroup> GetObjectsFrom(int x, int y)
	84	{
	85	if (m_childNodes == null)
	86	{
	87	return m_objects;
	88	}
	89	else
	90	{
	91	if (x < (m_leftX + (m_width / 2)))
	92	{
	93	if (y < (m_leftY + (m_height / 2)))
	94	{
	95	return m_childNodes[0].GetObjectsFrom(x, y);
	96	}
	97	else
	98	{
	99	return m_childNodes[2].GetObjectsFrom(x, y);
	100	}
	101	}
	102	else
	103	{
	104	if (y < (m_leftY + (m_height / 2)))
	105	{
	106	return m_childNodes[1].GetObjectsFrom(x, y);
	107	}
	108	else
	109	{
	110	return m_childNodes[3].GetObjectsFrom(x, y);
	111	}
	112	}
	113	}
	114	}
	115
	116	public void Update()
	117	{
	118	if (m_childNodes != null)
	119	{
	120	for (int i = 0; i < 4; i++)
	121	{
	122	m_childNodes[i].Update();
	123	}
	124	}
	125	else
	126	{
	127	List<SceneObjectGroup> outBounds = new List<SceneObjectGroup>();
	128	foreach (SceneObjectGroup group in m_objects)
	129	{
	130	if (((group.AbsolutePosition.X > m_leftX) && (group.AbsolutePosition.X < (m_leftX + m_width))) && ((group.AbsolutePosition.Y > m_leftY) && (group.AbsolutePosition.Y < (m_leftY + m_height))))
	131	{
	132	//still in bounds
	133	}
	134	else
	135	{
	136	outBounds.Add(group);
	137	}
	138	}
	139
	140	foreach (SceneObjectGroup removee in outBounds)
	141	{
	142	m_objects.Remove(removee);
	143	if (m_parent != null)
	144	{
	145	m_parent.PassUp(removee);
	146	}
	147	}
	148	outBounds.Clear();
	149	}
	150	}
	151
	152	public void PassUp(SceneObjectGroup group)
	153	{
	154	if (((group.AbsolutePosition.X > m_leftX) && (group.AbsolutePosition.X < (m_leftX + m_width))) && ((group.AbsolutePosition.Y > m_leftY) && (group.AbsolutePosition.Y < (m_leftY + m_height))))
	155	{
	156	this.AddObject(group);
	157	}
	158	else
	159	{
	160	if (m_parent != null)
	161	{
	162	m_parent.PassUp(group);
	163	}
	164	}
	165	}
	166	}
	167	}