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.cs516
1 files changed, 258 insertions, 258 deletions
diff --git a/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
index 20bb51d..942ec4d 100644
--- a/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
+++ b/OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs
@@ -1,258 +1,258 @@
1/* 1/*
2* Copyright (c) Contributors, http://opensimulator.org/ 2* Copyright (c) Contributors, http://opensimulator.org/
3* See CONTRIBUTORS.TXT for a full list of copyright holders. 3* See CONTRIBUTORS.TXT for a full list of copyright holders.
4* 4*
5* Redistribution and use in source and binary forms, with or without 5* Redistribution and use in source and binary forms, with or without
6* modification, are permitted provided that the following conditions are met: 6* modification, are permitted provided that the following conditions are met:
7* * Redistributions of source code must retain the above copyright 7* * Redistributions of source code must retain the above copyright
8* notice, this list of conditions and the following disclaimer. 8* notice, this list of conditions and the following disclaimer.
9* * Redistributions in binary form must reproduce the above copyright 9* * Redistributions in binary form must reproduce the above copyright
10* notice, this list of conditions and the following disclaimer in the 10* notice, this list of conditions and the following disclaimer in the
11* documentation and/or other materials provided with the distribution. 11* documentation and/or other materials provided with the distribution.
12* * Neither the name of the OpenSim Project nor the 12* * Neither the name of the OpenSim Project nor the
13* names of its contributors may be used to endorse or promote products 13* names of its contributors may be used to endorse or promote products
14* derived from this software without specific prior written permission. 14* derived from this software without specific prior written permission.
15* 15*
16* THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS AS IS AND ANY 16* THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS AS IS AND ANY
17* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 17* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 18* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19* DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY 19* DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
20* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 20* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 21* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 22* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 24* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26* 26*
27*/ 27*/
28 28
29using System.Collections.Generic; 29using System.Collections.Generic;
30using OpenSim.Region.Environment.Scenes; 30using OpenSim.Region.Environment.Scenes;
31 31
32namespace OpenSim.Region.Environment.Types 32namespace OpenSim.Region.Environment.Types
33{ 33{
34 public class BasicQuadTreeNode 34 public class BasicQuadTreeNode
35 { 35 {
36 private List<SceneObjectGroup> m_objects = new List<SceneObjectGroup>(); 36 private List<SceneObjectGroup> m_objects = new List<SceneObjectGroup>();
37 private BasicQuadTreeNode[] m_childNodes = null; 37 private BasicQuadTreeNode[] m_childNodes = null;
38 private BasicQuadTreeNode m_parent = null; 38 private BasicQuadTreeNode m_parent = null;
39 39
40 private short m_leftX; 40 private short m_leftX;
41 private short m_leftY; 41 private short m_leftY;
42 private short m_width; 42 private short m_width;
43 private short m_height; 43 private short m_height;
44 //private int m_quadNumber; 44 //private int m_quadNumber;
45 private string m_quadID; 45 private string m_quadID;
46 46
47 public BasicQuadTreeNode(BasicQuadTreeNode parent, string quadID, short leftX, short leftY, short width, short height) 47 public BasicQuadTreeNode(BasicQuadTreeNode parent, string quadID, short leftX, short leftY, short width, short height)
48 { 48 {
49 m_parent = parent; 49 m_parent = parent;
50 m_quadID = quadID; 50 m_quadID = quadID;
51 m_leftX = leftX; 51 m_leftX = leftX;
52 m_leftY = leftY; 52 m_leftY = leftY;
53 m_width = width; 53 m_width = width;
54 m_height = height; 54 m_height = height;
55 // Console.WriteLine("creating quadtree node " + m_quadID); 55 // Console.WriteLine("creating quadtree node " + m_quadID);
56 } 56 }
57 57
58 public void AddObject(SceneObjectGroup obj) 58 public void AddObject(SceneObjectGroup obj)
59 { 59 {
60 if (m_childNodes == null) 60 if (m_childNodes == null)
61 { 61 {
62 if (!m_objects.Contains(obj)) 62 if (!m_objects.Contains(obj))
63 { 63 {
64 m_objects.Add(obj); 64 m_objects.Add(obj);
65 } 65 }
66 } 66 }
67 else 67 else
68 { 68 {
69 if (obj.AbsolutePosition.X < (m_leftX + (m_width / 2))) 69 if (obj.AbsolutePosition.X < (m_leftX + (m_width / 2)))
70 { 70 {
71 if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2))) 71 if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
72 { 72 {
73 m_childNodes[0].AddObject(obj); 73 m_childNodes[0].AddObject(obj);
74 } 74 }
75 else 75 else
76 { 76 {
77 m_childNodes[2].AddObject(obj); 77 m_childNodes[2].AddObject(obj);
78 } 78 }
79 } 79 }
80 else 80 else
81 { 81 {
82 if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2))) 82 if (obj.AbsolutePosition.Y < (m_leftY + (m_height / 2)))
83 { 83 {
84 m_childNodes[1].AddObject(obj); 84 m_childNodes[1].AddObject(obj);
85 } 85 }
86 else 86 else
87 { 87 {
88 m_childNodes[3].AddObject(obj); 88 m_childNodes[3].AddObject(obj);
89 } 89 }
90 } 90 }
91 } 91 }
92 } 92 }
93 93
94 public void Subdivide() 94 public void Subdivide()
95 { 95 {
96 if (m_childNodes == null) 96 if (m_childNodes == null)
97 { 97 {
98 m_childNodes = new BasicQuadTreeNode[4]; 98 m_childNodes = new BasicQuadTreeNode[4];
99 m_childNodes[0] = new BasicQuadTreeNode(this, m_quadID + "1/", m_leftX, m_leftY, (short)(m_width / 2), (short)(m_height / 2)); 99 m_childNodes[0] = new BasicQuadTreeNode(this, m_quadID + "1/", m_leftX, m_leftY, (short)(m_width / 2), (short)(m_height / 2));
100 m_childNodes[1] = new BasicQuadTreeNode(this, m_quadID + "2/", (short)(m_leftX + (m_width / 2)), m_leftY, (short)(m_width / 2), (short)(m_height / 2)); 100 m_childNodes[1] = new BasicQuadTreeNode(this, m_quadID + "2/", (short)(m_leftX + (m_width / 2)), m_leftY, (short)(m_width / 2), (short)(m_height / 2));
101 m_childNodes[2] = new BasicQuadTreeNode(this, m_quadID + "3/", m_leftX, (short)(m_leftY + (m_height / 2)), (short)(m_width / 2), (short)(m_height / 2)); 101 m_childNodes[2] = new BasicQuadTreeNode(this, m_quadID + "3/", m_leftX, (short)(m_leftY + (m_height / 2)), (short)(m_width / 2), (short)(m_height / 2));
102 m_childNodes[3] = new BasicQuadTreeNode(this, m_quadID + "4/", (short)(m_leftX + (m_width / 2)), (short)(m_height + (m_height / 2)), (short)(m_width / 2), (short)(m_height / 2)); 102 m_childNodes[3] = new BasicQuadTreeNode(this, m_quadID + "4/", (short)(m_leftX + (m_width / 2)), (short)(m_height + (m_height / 2)), (short)(m_width / 2), (short)(m_height / 2));
103 } 103 }
104 else 104 else
105 { 105 {
106 for (int i = 0; i < m_childNodes.Length; i++) 106 for (int i = 0; i < m_childNodes.Length; i++)
107 { 107 {
108 m_childNodes[i].Subdivide(); 108 m_childNodes[i].Subdivide();
109 } 109 }
110 } 110 }
111 } 111 }
112 112
113 public List<SceneObjectGroup> GetObjectsFrom(float x, float y) 113 public List<SceneObjectGroup> GetObjectsFrom(float x, float y)
114 { 114 {
115 if (m_childNodes == null) 115 if (m_childNodes == null)
116 { 116 {
117 return new List<SceneObjectGroup>(m_objects); 117 return new List<SceneObjectGroup>(m_objects);
118 } 118 }
119 else 119 else
120 { 120 {
121 if (x < m_leftX + (m_width / 2)) 121 if (x < m_leftX + (m_width / 2))
122 { 122 {
123 if (y < m_leftY + (m_height / 2)) 123 if (y < m_leftY + (m_height / 2))
124 { 124 {
125 return m_childNodes[0].GetObjectsFrom(x, y); 125 return m_childNodes[0].GetObjectsFrom(x, y);
126 } 126 }
127 else 127 else
128 { 128 {
129 return m_childNodes[2].GetObjectsFrom(x, y); 129 return m_childNodes[2].GetObjectsFrom(x, y);
130 } 130 }
131 } 131 }
132 else 132 else
133 { 133 {
134 if (y < m_leftY + (m_height / 2)) 134 if (y < m_leftY + (m_height / 2))
135 { 135 {
136 return m_childNodes[1].GetObjectsFrom(x, y); 136 return m_childNodes[1].GetObjectsFrom(x, y);
137 } 137 }
138 else 138 else
139 { 139 {
140 return m_childNodes[3].GetObjectsFrom(x, y); 140 return m_childNodes[3].GetObjectsFrom(x, y);
141 } 141 }
142 } 142 }
143 } 143 }
144 } 144 }
145 145
146 public List<SceneObjectGroup> GetObjectsFrom(string nodeName) 146 public List<SceneObjectGroup> GetObjectsFrom(string nodeName)
147 { 147 {
148 if (nodeName == m_quadID) 148 if (nodeName == m_quadID)
149 { 149 {
150 return new List<SceneObjectGroup>(m_objects); 150 return new List<SceneObjectGroup>(m_objects);
151 } 151 }
152 else if (m_childNodes != null) 152 else if (m_childNodes != null)
153 { 153 {
154 for (int i = 0; i < 4; i++) 154 for (int i = 0; i < 4; i++)
155 { 155 {
156 List<SceneObjectGroup> retVal; 156 List<SceneObjectGroup> retVal;
157 retVal = m_childNodes[i].GetObjectsFrom(nodeName); 157 retVal = m_childNodes[i].GetObjectsFrom(nodeName);
158 if (retVal != null) 158 if (retVal != null)
159 { 159 {
160 return retVal; 160 return retVal;
161 } 161 }
162 } 162 }
163 } 163 }
164 return null; 164 return null;
165 } 165 }
166 166
167 public string GetNodeID(float x, float y) 167 public string GetNodeID(float x, float y)
168 { 168 {
169 if (m_childNodes == null) 169 if (m_childNodes == null)
170 { 170 {
171 return m_quadID; 171 return m_quadID;
172 } 172 }
173 else 173 else
174 { 174 {
175 if (x < m_leftX + (m_width / 2)) 175 if (x < m_leftX + (m_width / 2))
176 { 176 {
177 if (y < m_leftY + (m_height / 2)) 177 if (y < m_leftY + (m_height / 2))
178 { 178 {
179 return m_childNodes[0].GetNodeID(x, y); 179 return m_childNodes[0].GetNodeID(x, y);
180 } 180 }
181 else 181 else
182 { 182 {
183 return m_childNodes[2].GetNodeID(x, y); 183 return m_childNodes[2].GetNodeID(x, y);
184 } 184 }
185 } 185 }
186 else 186 else
187 { 187 {
188 if (y < m_leftY + (m_height / 2)) 188 if (y < m_leftY + (m_height / 2))
189 { 189 {
190 return m_childNodes[1].GetNodeID(x, y); 190 return m_childNodes[1].GetNodeID(x, y);
191 } 191 }
192 else 192 else
193 { 193 {
194 return m_childNodes[3].GetNodeID(x, y); 194 return m_childNodes[3].GetNodeID(x, y);
195 } 195 }
196 } 196 }
197 } 197 }
198 } 198 }
199 199
200 public void Update() 200 public void Update()
201 { 201 {
202 if (m_childNodes != null) 202 if (m_childNodes != null)
203 { 203 {
204 for (int i = 0; i < 4; i++) 204 for (int i = 0; i < 4; i++)
205 { 205 {
206 m_childNodes[i].Update(); 206 m_childNodes[i].Update();
207 } 207 }
208 } 208 }
209 else 209 else
210 { 210 {
211 List<SceneObjectGroup> outBounds = new List<SceneObjectGroup>(); 211 List<SceneObjectGroup> outBounds = new List<SceneObjectGroup>();
212 foreach (SceneObjectGroup group in m_objects) 212 foreach (SceneObjectGroup group in m_objects)
213 { 213 {
214 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)))) 214 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))))
215 { 215 {
216 //still in bounds 216 //still in bounds
217 } 217 }
218 else 218 else
219 { 219 {
220 outBounds.Add(group); 220 outBounds.Add(group);
221 } 221 }
222 } 222 }
223 223
224 foreach (SceneObjectGroup removee in outBounds) 224 foreach (SceneObjectGroup removee in outBounds)
225 { 225 {
226 m_objects.Remove(removee); 226 m_objects.Remove(removee);
227 if (m_parent != null) 227 if (m_parent != null)
228 { 228 {
229 m_parent.PassUp(removee); 229 m_parent.PassUp(removee);
230 } 230 }
231 } 231 }
232 outBounds.Clear(); 232 outBounds.Clear();
233 } 233 }
234 } 234 }
235 235
236 public void PassUp(SceneObjectGroup group) 236 public void PassUp(SceneObjectGroup group)
237 { 237 {
238 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)))) 238 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))))
239 { 239 {
240 AddObject(group); 240 AddObject(group);
241 } 241 }
242 else 242 else
243 { 243 {
244 if (m_parent != null) 244 if (m_parent != null)
245 { 245 {
246 m_parent.PassUp(group); 246 m_parent.PassUp(group);
247 } 247 }
248 } 248 }
249 } 249 }
250 250
251 public string[] GetNeighbours(string nodeName) 251 public string[] GetNeighbours(string nodeName)
252 { 252 {
253 string[] retVal = new string[1]; 253 string[] retVal = new string[1];
254 retVal[0] = ""; 254 retVal[0] = "";
255 return retVal; 255 return retVal;
256 } 256 }
257 } 257 }
258} 258}
generated by cgit v1.1 at 2024-07-05 02:14:38 +0000