aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorMic Bowman2011-04-04 13:19:45 -0700
committerMic Bowman2011-04-10 16:57:02 -0700
commit0bd06d8ba85595a1707d2093a08a901b950ca120 (patch)
tree3a7fd9d51d65293896a8f489e14782ea58a200e7
parentImplements adaptive queue management and fair queueing for (diff)
downloadopensim-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
-rw-r--r--OpenSim/Region/Framework/Scenes/Prioritizer.cs292
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}