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