diff options
author | Mic Bowman | 2011-04-04 13:19:45 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-10 16:57:02 -0700 |
commit | 0bd06d8ba85595a1707d2093a08a901b950ca120 (patch) | |
tree | 3a7fd9d51d65293896a8f489e14782ea58a200e7 /OpenSim/Region/Framework/Scenes/Prioritizer.cs | |
parent | Implements adaptive queue management and fair queueing for (diff) | |
download | opensim-SC_OLD-0bd06d8ba85595a1707d2093a08a901b950ca120.zip opensim-SC_OLD-0bd06d8ba85595a1707d2093a08a901b950ca120.tar.gz opensim-SC_OLD-0bd06d8ba85595a1707d2093a08a901b950ca120.tar.bz2 opensim-SC_OLD-0bd06d8ba85595a1707d2093a08a901b950ca120.tar.xz |
Fixed the prioritizer functions for the new priority queues
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/Framework/Scenes/Prioritizer.cs | 292 |
1 files changed, 82 insertions, 210 deletions
diff --git a/OpenSim/Region/Framework/Scenes/Prioritizer.cs b/OpenSim/Region/Framework/Scenes/Prioritizer.cs index 2764b05..a14bb70 100644 --- a/OpenSim/Region/Framework/Scenes/Prioritizer.cs +++ b/OpenSim/Region/Framework/Scenes/Prioritizer.cs | |||
@@ -60,15 +60,6 @@ namespace OpenSim.Region.Framework.Scenes | |||
60 | { | 60 | { |
61 | private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType); | 61 | private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType); |
62 | 62 | ||
63 | /// <summary> | ||
64 | /// This is added to the priority of all child prims, to make sure that the root prim update is sent to the | ||
65 | /// viewer before child prim updates. | ||
66 | /// The adjustment is added to child prims and subtracted from root prims, so the gap ends up | ||
67 | /// being double. We do it both ways so that there is a still a priority delta even if the priority is already | ||
68 | /// double.MinValue or double.MaxValue. | ||
69 | /// </summary> | ||
70 | private double m_childPrimAdjustmentFactor = 0.05; | ||
71 | |||
72 | private Scene m_scene; | 63 | private Scene m_scene; |
73 | 64 | ||
74 | public Prioritizer(Scene scene) | 65 | public Prioritizer(Scene scene) |
@@ -76,9 +67,19 @@ namespace OpenSim.Region.Framework.Scenes | |||
76 | m_scene = scene; | 67 | m_scene = scene; |
77 | } | 68 | } |
78 | 69 | ||
79 | //<mic> | 70 | /// <summary> |
71 | /// Returns the priority queue into which the update should be placed. Updates within a | ||
72 | /// queue will be processed in arrival order. There are currently 12 priority queues | ||
73 | /// implemented in PriorityQueue class in LLClientView. Queue 0 is generally retained | ||
74 | /// for avatar updates. The fair queuing discipline for processing the priority queues | ||
75 | /// assumes that the number of entities in each priority queues increases exponentially. | ||
76 | /// So for example... if queue 1 contains all updates within 10m of the avatar or camera | ||
77 | /// then queue 2 at 20m is about 3X bigger in space & about 3X bigger in total number | ||
78 | /// of updates. | ||
79 | /// </summary> | ||
80 | public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity) | 80 | public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity) |
81 | { | 81 | { |
82 | // If entity is null we have a serious problem | ||
82 | if (entity == null) | 83 | if (entity == null) |
83 | { | 84 | { |
84 | m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity"); | 85 | m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity"); |
@@ -89,71 +90,12 @@ namespace OpenSim.Region.Framework.Scenes | |||
89 | if (client.AgentId == entity.UUID) | 90 | if (client.AgentId == entity.UUID) |
90 | return 0; | 91 | return 0; |
91 | 92 | ||
92 | // Get this agent's position | 93 | uint priority; |
93 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); | ||
94 | if (presence == null) | ||
95 | { | ||
96 | m_log.WarnFormat("[PRIORITIZER] attempt to prioritize agent no longer in the scene"); | ||
97 | throw new InvalidOperationException("Prioritization agent not defined"); | ||
98 | } | ||
99 | |||
100 | // Use group position for child prims | ||
101 | Vector3 entityPos = entity.AbsolutePosition; | ||
102 | if (entity is SceneObjectPart) | ||
103 | { | ||
104 | SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup; | ||
105 | if (group != null) | ||
106 | entityPos = group.AbsolutePosition; | ||
107 | } | ||
108 | |||
109 | // Use the camera position for local agents and avatar position for remote agents | ||
110 | Vector3 presencePos = (presence.IsChildAgent) ? | ||
111 | presence.AbsolutePosition : | ||
112 | presence.CameraPosition; | ||
113 | |||
114 | // Compute the distance... | ||
115 | double distance = Vector3.Distance(presencePos, entityPos); | ||
116 | |||
117 | // And convert the distance to a priority queue, this computation gives queues | ||
118 | // at 10, 20, 40, 80, 160, 320, 640, and 1280m | ||
119 | uint pqueue = 1; | ||
120 | for (int i = 0; i < 8; i++) | ||
121 | { | ||
122 | if (distance < 10 * Math.Pow(2.0,i)) | ||
123 | break; | ||
124 | pqueue++; | ||
125 | } | ||
126 | |||
127 | // If this is a root agent, then determine front & back | ||
128 | // Bump up the priority queue for any objects behind the avatar | ||
129 | if (! presence.IsChildAgent) | ||
130 | { | ||
131 | // Root agent, decrease priority for objects behind us | ||
132 | Vector3 camPosition = presence.CameraPosition; | ||
133 | Vector3 camAtAxis = presence.CameraAtAxis; | ||
134 | |||
135 | // Plane equation | ||
136 | float d = -Vector3.Dot(camPosition, camAtAxis); | ||
137 | float p = Vector3.Dot(camAtAxis, entityPos) + d; | ||
138 | if (p < 0.0f) | ||
139 | pqueue++; | ||
140 | } | ||
141 | |||
142 | return pqueue; | ||
143 | } | ||
144 | //</mic> | ||
145 | |||
146 | public double bGetUpdatePriority(IClientAPI client, ISceneEntity entity) | ||
147 | { | ||
148 | double priority = 0; | ||
149 | |||
150 | if (entity == null) | ||
151 | return 100000; | ||
152 | 94 | ||
153 | switch (m_scene.UpdatePrioritizationScheme) | 95 | switch (m_scene.UpdatePrioritizationScheme) |
154 | { | 96 | { |
155 | case UpdatePrioritizationSchemes.Time: | 97 | case UpdatePrioritizationSchemes.Time: |
156 | priority = GetPriorityByTime(); | 98 | priority = GetPriorityByTime(client, entity); |
157 | break; | 99 | break; |
158 | case UpdatePrioritizationSchemes.Distance: | 100 | case UpdatePrioritizationSchemes.Distance: |
159 | priority = GetPriorityByDistance(client, entity); | 101 | priority = GetPriorityByDistance(client, entity); |
@@ -171,180 +113,110 @@ namespace OpenSim.Region.Framework.Scenes | |||
171 | throw new InvalidOperationException("UpdatePrioritizationScheme not defined."); | 113 | throw new InvalidOperationException("UpdatePrioritizationScheme not defined."); |
172 | } | 114 | } |
173 | 115 | ||
174 | // Adjust priority so that root prims are sent to the viewer first. This is especially important for | ||
175 | // attachments acting as huds, since current viewers fail to display hud child prims if their updates | ||
176 | // arrive before the root one. | ||
177 | if (entity is SceneObjectPart) | ||
178 | { | ||
179 | SceneObjectPart sop = ((SceneObjectPart)entity); | ||
180 | |||
181 | if (sop.IsRoot) | ||
182 | { | ||
183 | if (priority >= double.MinValue + m_childPrimAdjustmentFactor) | ||
184 | priority -= m_childPrimAdjustmentFactor; | ||
185 | } | ||
186 | else | ||
187 | { | ||
188 | if (priority <= double.MaxValue - m_childPrimAdjustmentFactor) | ||
189 | priority += m_childPrimAdjustmentFactor; | ||
190 | } | ||
191 | } | ||
192 | |||
193 | return priority; | 116 | return priority; |
194 | } | 117 | } |
195 | 118 | ||
196 | private double GetPriorityByTime() | 119 | |
120 | private uint GetPriorityByTime(IClientAPI client, ISceneEntity entity) | ||
197 | { | 121 | { |
198 | return DateTime.UtcNow.ToOADate(); | 122 | return 1; |
199 | } | 123 | } |
200 | 124 | ||
201 | private double GetPriorityByDistance(IClientAPI client, ISceneEntity entity) | 125 | private uint GetPriorityByDistance(IClientAPI client, ISceneEntity entity) |
202 | { | 126 | { |
203 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); | 127 | return ComputeDistancePriority(client,entity,false); |
204 | if (presence != null) | 128 | } |
205 | { | 129 | |
206 | // If this is an update for our own avatar give it the highest priority | 130 | private uint GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity) |
207 | if (presence == entity) | 131 | { |
208 | return 0.0; | 132 | return ComputeDistancePriority(client,entity,true); |
209 | |||
210 | // Use the camera position for local agents and avatar position for remote agents | ||
211 | Vector3 presencePos = (presence.IsChildAgent) ? | ||
212 | presence.AbsolutePosition : | ||
213 | presence.CameraPosition; | ||
214 | |||
215 | // Use group position for child prims | ||
216 | Vector3 entityPos; | ||
217 | if (entity is SceneObjectPart) | ||
218 | { | ||
219 | // Can't use Scene.GetGroupByPrim() here, since the entity may have been delete from the scene | ||
220 | // before its scheduled update was triggered | ||
221 | //entityPos = m_scene.GetGroupByPrim(entity.LocalId).AbsolutePosition; | ||
222 | entityPos = ((SceneObjectPart)entity).ParentGroup.AbsolutePosition; | ||
223 | } | ||
224 | else | ||
225 | { | ||
226 | entityPos = entity.AbsolutePosition; | ||
227 | } | ||
228 | |||
229 | return Vector3.DistanceSquared(presencePos, entityPos); | ||
230 | } | ||
231 | |||
232 | return double.NaN; | ||
233 | } | 133 | } |
234 | 134 | ||
235 | private double GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity) | 135 | private uint GetPriorityByBestAvatarResponsiveness(IClientAPI client, ISceneEntity entity) |
236 | { | 136 | { |
137 | uint pqueue = ComputeDistancePriority(client,entity,true); | ||
138 | |||
237 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); | 139 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); |
238 | if (presence != null) | 140 | if (presence != null) |
239 | { | 141 | { |
240 | // If this is an update for our own avatar give it the highest priority | ||
241 | if (presence == entity) | ||
242 | return 0.0; | ||
243 | |||
244 | // Use group position for child prims | ||
245 | Vector3 entityPos = entity.AbsolutePosition; | ||
246 | if (entity is SceneObjectPart) | ||
247 | { | ||
248 | // Can't use Scene.GetGroupByPrim() here, since the entity may have been delete from the scene | ||
249 | // before its scheduled update was triggered | ||
250 | //entityPos = m_scene.GetGroupByPrim(entity.LocalId).AbsolutePosition; | ||
251 | entityPos = ((SceneObjectPart)entity).ParentGroup.AbsolutePosition; | ||
252 | } | ||
253 | else | ||
254 | { | ||
255 | entityPos = entity.AbsolutePosition; | ||
256 | } | ||
257 | |||
258 | if (!presence.IsChildAgent) | 142 | if (!presence.IsChildAgent) |
259 | { | 143 | { |
260 | // Root agent. Use distance from camera and a priority decrease for objects behind us | 144 | if (entity is SceneObjectPart) |
261 | Vector3 camPosition = presence.CameraPosition; | 145 | { |
262 | Vector3 camAtAxis = presence.CameraAtAxis; | 146 | // Non physical prims are lower priority than physical prims |
263 | 147 | PhysicsActor physActor = ((SceneObjectPart)entity).ParentGroup.RootPart.PhysActor; | |
264 | // Distance | 148 | if (physActor == null || !physActor.IsPhysical) |
265 | double priority = Vector3.DistanceSquared(camPosition, entityPos); | 149 | pqueue++; |
266 | |||
267 | // Plane equation | ||
268 | float d = -Vector3.Dot(camPosition, camAtAxis); | ||
269 | float p = Vector3.Dot(camAtAxis, entityPos) + d; | ||
270 | if (p < 0.0f) priority *= 2.0; | ||
271 | |||
272 | return priority; | ||
273 | } | ||
274 | else | ||
275 | { | ||
276 | // Child agent. Use the normal distance method | ||
277 | Vector3 presencePos = presence.AbsolutePosition; | ||
278 | 150 | ||
279 | return Vector3.DistanceSquared(presencePos, entityPos); | 151 | // Attachments are high priority, |
152 | // MIC: shouldn't these already be in the highest priority queue already | ||
153 | // since their root position is same as the avatars? | ||
154 | if (((SceneObjectPart)entity).ParentGroup.RootPart.IsAttachment) | ||
155 | pqueue = 1; | ||
156 | } | ||
280 | } | 157 | } |
281 | } | 158 | } |
282 | 159 | ||
283 | return double.NaN; | 160 | return pqueue; |
284 | } | 161 | } |
285 | 162 | ||
286 | private double GetPriorityByBestAvatarResponsiveness(IClientAPI client, ISceneEntity entity) | 163 | private uint ComputeDistancePriority(IClientAPI client, ISceneEntity entity, bool useFrontBack) |
287 | { | 164 | { |
288 | // If this is an update for our own avatar give it the highest priority | 165 | // Get this agent's position |
289 | if (client.AgentId == entity.UUID) | 166 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); |
290 | return 0.0; | 167 | if (presence == null) |
291 | if (entity == null) | 168 | { |
292 | return double.NaN; | 169 | m_log.WarnFormat("[PRIORITIZER] attempt to prioritize agent no longer in the scene"); |
293 | 170 | throw new InvalidOperationException("Prioritization agent not defined"); | |
294 | // Use group position for child prims | 171 | } |
172 | |||
173 | // Use group position for child prims, since we are putting child prims in | ||
174 | // the same queue with the root of the group, the root prim (which goes into | ||
175 | // the queue first) should always be sent first, no need to adjust child prim | ||
176 | // priorities | ||
295 | Vector3 entityPos = entity.AbsolutePosition; | 177 | Vector3 entityPos = entity.AbsolutePosition; |
296 | if (entity is SceneObjectPart) | 178 | if (entity is SceneObjectPart) |
297 | { | 179 | { |
298 | SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup; | 180 | SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup; |
299 | if (group != null) | 181 | if (group != null) |
300 | entityPos = group.AbsolutePosition; | 182 | entityPos = group.AbsolutePosition; |
301 | else | ||
302 | entityPos = entity.AbsolutePosition; | ||
303 | } | 183 | } |
304 | else | ||
305 | entityPos = entity.AbsolutePosition; | ||
306 | |||
307 | ScenePresence presence = m_scene.GetScenePresence(client.AgentId); | ||
308 | if (presence != null) | ||
309 | { | ||
310 | if (!presence.IsChildAgent) | ||
311 | { | ||
312 | if (entity is ScenePresence) | ||
313 | return 1.0; | ||
314 | 184 | ||
315 | // Root agent. Use distance from camera and a priority decrease for objects behind us | 185 | // Use the camera position for local agents and avatar position for remote agents |
316 | Vector3 camPosition = presence.CameraPosition; | 186 | Vector3 presencePos = (presence.IsChildAgent) ? |
317 | Vector3 camAtAxis = presence.CameraAtAxis; | 187 | presence.AbsolutePosition : |
318 | 188 | presence.CameraPosition; | |
319 | // Distance | ||
320 | double priority = Vector3.DistanceSquared(camPosition, entityPos); | ||
321 | |||
322 | // Plane equation | ||
323 | float d = -Vector3.Dot(camPosition, camAtAxis); | ||
324 | float p = Vector3.Dot(camAtAxis, entityPos) + d; | ||
325 | if (p < 0.0f) priority *= 2.0; | ||
326 | 189 | ||
327 | if (entity is SceneObjectPart) | 190 | // Compute the distance... |
328 | { | 191 | double distance = Vector3.Distance(presencePos, entityPos); |
329 | PhysicsActor physActor = ((SceneObjectPart)entity).ParentGroup.RootPart.PhysActor; | ||
330 | if (physActor == null || !physActor.IsPhysical) | ||
331 | priority += 100; | ||
332 | 192 | ||
333 | if (((SceneObjectPart)entity).ParentGroup.RootPart.IsAttachment) | 193 | // And convert the distance to a priority queue, this computation gives queues |
334 | priority = 1.0; | 194 | // at 10, 20, 40, 80, 160, 320, 640, and 1280m |
335 | } | 195 | uint pqueue = 1; |
336 | return priority; | 196 | for (int i = 0; i < 8; i++) |
337 | } | 197 | { |
338 | else | 198 | if (distance < 10 * Math.Pow(2.0,i)) |
339 | { | 199 | break; |
340 | // Child agent. Use the normal distance method | 200 | pqueue++; |
341 | Vector3 presencePos = presence.AbsolutePosition; | 201 | } |
202 | |||
203 | // If this is a root agent, then determine front & back | ||
204 | // Bump up the priority queue (drop the priority) for any objects behind the avatar | ||
205 | if (useFrontBack && ! presence.IsChildAgent) | ||
206 | { | ||
207 | // Root agent, decrease priority for objects behind us | ||
208 | Vector3 camPosition = presence.CameraPosition; | ||
209 | Vector3 camAtAxis = presence.CameraAtAxis; | ||
342 | 210 | ||
343 | return Vector3.DistanceSquared(presencePos, entityPos); | 211 | // Plane equation |
344 | } | 212 | float d = -Vector3.Dot(camPosition, camAtAxis); |
213 | float p = Vector3.Dot(camAtAxis, entityPos) + d; | ||
214 | if (p < 0.0f) | ||
215 | pqueue++; | ||
345 | } | 216 | } |
346 | 217 | ||
347 | return double.NaN; | 218 | return pqueue; |
348 | } | 219 | } |
220 | |||
349 | } | 221 | } |
350 | } | 222 | } |