diff options
Diffstat (limited to 'OpenSim/Region/Framework/Scenes/Types')
-rw-r--r-- | OpenSim/Region/Framework/Scenes/Types/BasicQuadTreeNode.cs | 269 | ||||
-rw-r--r-- | OpenSim/Region/Framework/Scenes/Types/UpdateQueue.cs | 134 |
2 files changed, 403 insertions, 0 deletions
diff --git a/OpenSim/Region/Framework/Scenes/Types/BasicQuadTreeNode.cs b/OpenSim/Region/Framework/Scenes/Types/BasicQuadTreeNode.cs new file mode 100644 index 0000000..9fbbb15 --- /dev/null +++ b/OpenSim/Region/Framework/Scenes/Types/BasicQuadTreeNode.cs | |||
@@ -0,0 +1,269 @@ | |||
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 OpenSim 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 | |||
28 | using System; | ||
29 | using System.Collections.Generic; | ||
30 | using OpenSim.Region.Framework.Scenes; | ||
31 | |||
32 | namespace 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 | // Console.WriteLine("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 | } | ||
diff --git a/OpenSim/Region/Framework/Scenes/Types/UpdateQueue.cs b/OpenSim/Region/Framework/Scenes/Types/UpdateQueue.cs new file mode 100644 index 0000000..452ada9 --- /dev/null +++ b/OpenSim/Region/Framework/Scenes/Types/UpdateQueue.cs | |||
@@ -0,0 +1,134 @@ | |||
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 OpenSim 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 | |||
28 | using System; | ||
29 | using System.Collections.Generic; | ||
30 | using System.Runtime.Serialization; | ||
31 | using System.Security.Permissions; | ||
32 | using OpenMetaverse; | ||
33 | using OpenSim.Region.Framework.Scenes; | ||
34 | |||
35 | namespace OpenSim.Region.Framework.Scenes.Types | ||
36 | { | ||
37 | [Serializable] | ||
38 | public class UpdateQueue : ISerializable | ||
39 | { | ||
40 | private Queue<SceneObjectPart> m_queue; | ||
41 | |||
42 | private List<UUID> m_ids; | ||
43 | |||
44 | private object m_syncObject = new object(); | ||
45 | |||
46 | public int Count | ||
47 | { | ||
48 | get { return m_queue.Count; } | ||
49 | } | ||
50 | |||
51 | public UpdateQueue() | ||
52 | { | ||
53 | m_queue = new Queue<SceneObjectPart>(); | ||
54 | m_ids = new List<UUID>(); | ||
55 | } | ||
56 | |||
57 | public void Clear() | ||
58 | { | ||
59 | lock (m_syncObject) | ||
60 | { | ||
61 | m_ids.Clear(); | ||
62 | m_queue.Clear(); | ||
63 | } | ||
64 | } | ||
65 | |||
66 | public void Enqueue(SceneObjectPart part) | ||
67 | { | ||
68 | lock (m_syncObject) | ||
69 | { | ||
70 | if (!m_ids.Contains(part.UUID)) | ||
71 | { | ||
72 | m_ids.Add(part.UUID); | ||
73 | m_queue.Enqueue(part); | ||
74 | } | ||
75 | } | ||
76 | } | ||
77 | |||
78 | public SceneObjectPart Dequeue() | ||
79 | { | ||
80 | SceneObjectPart part = null; | ||
81 | lock (m_syncObject) | ||
82 | { | ||
83 | if (m_queue.Count > 0) | ||
84 | { | ||
85 | part = m_queue.Dequeue(); | ||
86 | m_ids.Remove(part.UUID); | ||
87 | } | ||
88 | } | ||
89 | |||
90 | return part; | ||
91 | } | ||
92 | |||
93 | protected UpdateQueue(SerializationInfo info, StreamingContext context) | ||
94 | { | ||
95 | //System.Console.WriteLine("UpdateQueue Deserialize BGN"); | ||
96 | |||
97 | if (info == null) | ||
98 | { | ||
99 | throw new ArgumentNullException("info"); | ||
100 | } | ||
101 | |||
102 | m_queue = (Queue<SceneObjectPart>)info.GetValue("m_queue", typeof(Queue<SceneObjectPart>)); | ||
103 | List<Guid> ids_work = (List<Guid>)info.GetValue("m_ids", typeof(List<Guid>)); | ||
104 | |||
105 | foreach (Guid guid in ids_work) | ||
106 | { | ||
107 | m_ids.Add(new UUID(guid)); | ||
108 | } | ||
109 | |||
110 | //System.Console.WriteLine("UpdateQueue Deserialize END"); | ||
111 | } | ||
112 | |||
113 | [SecurityPermission(SecurityAction.LinkDemand, | ||
114 | Flags = SecurityPermissionFlag.SerializationFormatter)] | ||
115 | public virtual void GetObjectData( | ||
116 | SerializationInfo info, StreamingContext context) | ||
117 | { | ||
118 | if (info == null) | ||
119 | { | ||
120 | throw new ArgumentNullException("info"); | ||
121 | } | ||
122 | |||
123 | List<Guid> ids_work = new List<Guid>(); | ||
124 | |||
125 | foreach (UUID uuid in m_ids) | ||
126 | { | ||
127 | ids_work.Add(uuid.Guid); | ||
128 | } | ||
129 | |||
130 | info.AddValue("m_queue", m_queue); | ||
131 | info.AddValue("m_ids", ids_work); | ||
132 | } | ||
133 | } | ||
134 | } | ||