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