diff options
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/Environment/Types/BasicQuadTreeNode.cs | 167 | ||||
-rw-r--r-- | OpenSim/Region/Environment/Types/UpdateQueue.cs | 21 |
2 files changed, 188 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 @@ | |||
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 | } | ||
diff --git a/OpenSim/Region/Environment/Types/UpdateQueue.cs b/OpenSim/Region/Environment/Types/UpdateQueue.cs new file mode 100644 index 0000000..d7eb6ee --- /dev/null +++ b/OpenSim/Region/Environment/Types/UpdateQueue.cs | |||
@@ -0,0 +1,21 @@ | |||
1 | using System; | ||
2 | using System.Collections.Generic; | ||
3 | using System.Text; | ||
4 | using OpenSim.Region.Environment.Scenes; | ||
5 | using libsecondlife; | ||
6 | |||
7 | namespace OpenSim.Region.Environment.Types | ||
8 | { | ||
9 | public class UpdateQueue | ||
10 | { | ||
11 | private Queue<SceneObjectPart> m_queue; | ||
12 | |||
13 | private List<LLUUID> m_ids; | ||
14 | |||
15 | public UpdateQueue() | ||
16 | { | ||
17 | m_queue = new Queue<SceneObjectPart>(); | ||
18 | m_ids = new List<LLUUID>(); | ||
19 | } | ||
20 | } | ||
21 | } | ||