1
0

Prioritizer.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253
  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. using System;
  28. using System.Collections.Generic;
  29. using log4net;
  30. using Nini.Config;
  31. using OpenSim.Framework;
  32. using OpenMetaverse;
  33. using OpenSim.Region.Physics.Manager;
  34. /*
  35. * Steps to add a new prioritization policy:
  36. *
  37. * - Add a new value to the UpdatePrioritizationSchemes enum.
  38. * - Specify this new value in the [InterestManagement] section of your
  39. * OpenSim.ini. The name in the config file must match the enum value name
  40. * (although it is not case sensitive).
  41. * - Write a new GetPriorityBy*() method in this class.
  42. * - Add a new entry to the switch statement in GetUpdatePriority() that calls
  43. * your method.
  44. */
  45. namespace OpenSim.Region.Framework.Scenes
  46. {
  47. public enum UpdatePrioritizationSchemes
  48. {
  49. Time = 0,
  50. Distance = 1,
  51. SimpleAngularDistance = 2,
  52. FrontBack = 3,
  53. BestAvatarResponsiveness = 4,
  54. }
  55. public class Prioritizer
  56. {
  57. private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);
  58. private Scene m_scene;
  59. public Prioritizer(Scene scene)
  60. {
  61. m_scene = scene;
  62. }
  63. /// <summary>
  64. /// Returns the priority queue into which the update should be placed. Updates within a
  65. /// queue will be processed in arrival order. There are currently 12 priority queues
  66. /// implemented in PriorityQueue class in LLClientView. Queue 0 is generally retained
  67. /// for avatar updates. The fair queuing discipline for processing the priority queues
  68. /// assumes that the number of entities in each priority queues increases exponentially.
  69. /// So for example... if queue 1 contains all updates within 10m of the avatar or camera
  70. /// then queue 2 at 20m is about 3X bigger in space & about 3X bigger in total number
  71. /// of updates.
  72. /// </summary>
  73. public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity)
  74. {
  75. // If entity is null we have a serious problem
  76. if (entity == null)
  77. {
  78. m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity");
  79. throw new InvalidOperationException("Prioritization entity not defined");
  80. }
  81. // If this is an update for our own avatar give it the highest priority
  82. if (client.AgentId == entity.UUID)
  83. return 0;
  84. uint priority;
  85. switch (m_scene.UpdatePrioritizationScheme)
  86. {
  87. case UpdatePrioritizationSchemes.Time:
  88. priority = GetPriorityByTime(client, entity);
  89. break;
  90. case UpdatePrioritizationSchemes.Distance:
  91. priority = GetPriorityByDistance(client, entity);
  92. break;
  93. case UpdatePrioritizationSchemes.SimpleAngularDistance:
  94. priority = GetPriorityByDistance(client, entity); // TODO: Reimplement SimpleAngularDistance
  95. break;
  96. case UpdatePrioritizationSchemes.FrontBack:
  97. priority = GetPriorityByFrontBack(client, entity);
  98. break;
  99. case UpdatePrioritizationSchemes.BestAvatarResponsiveness:
  100. priority = GetPriorityByBestAvatarResponsiveness(client, entity);
  101. break;
  102. default:
  103. throw new InvalidOperationException("UpdatePrioritizationScheme not defined.");
  104. }
  105. return priority;
  106. }
  107. private uint GetPriorityByTime(IClientAPI client, ISceneEntity entity)
  108. {
  109. // And anything attached to this avatar gets top priority as well
  110. if (entity is SceneObjectPart)
  111. {
  112. SceneObjectPart sop = (SceneObjectPart)entity;
  113. if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
  114. return 1;
  115. }
  116. return PriorityQueue.NumberOfImmediateQueues; // first queue past the immediate queues
  117. }
  118. private uint GetPriorityByDistance(IClientAPI client, ISceneEntity entity)
  119. {
  120. // And anything attached to this avatar gets top priority as well
  121. if (entity is SceneObjectPart)
  122. {
  123. SceneObjectPart sop = (SceneObjectPart)entity;
  124. if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
  125. return 1;
  126. }
  127. return ComputeDistancePriority(client,entity,false);
  128. }
  129. private uint GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity)
  130. {
  131. // And anything attached to this avatar gets top priority as well
  132. if (entity is SceneObjectPart)
  133. {
  134. SceneObjectPart sop = (SceneObjectPart)entity;
  135. if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
  136. return 1;
  137. }
  138. return ComputeDistancePriority(client,entity,true);
  139. }
  140. private uint GetPriorityByBestAvatarResponsiveness(IClientAPI client, ISceneEntity entity)
  141. {
  142. uint pqueue = ComputeDistancePriority(client,entity,true);
  143. ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
  144. if (presence != null)
  145. {
  146. if (!presence.IsChildAgent)
  147. {
  148. // All avatars other than our own go into pqueue 1
  149. if (entity is ScenePresence)
  150. return 1;
  151. if (entity is SceneObjectPart)
  152. {
  153. // Attachments are high priority,
  154. if (((SceneObjectPart)entity).ParentGroup.IsAttachment)
  155. return 1;
  156. // Non physical prims are lower priority than physical prims
  157. PhysicsActor physActor = ((SceneObjectPart)entity).ParentGroup.RootPart.PhysActor;
  158. if (physActor == null || !physActor.IsPhysical)
  159. pqueue++;
  160. }
  161. }
  162. }
  163. return pqueue;
  164. }
  165. private uint ComputeDistancePriority(IClientAPI client, ISceneEntity entity, bool useFrontBack)
  166. {
  167. // Get this agent's position
  168. ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
  169. if (presence == null)
  170. {
  171. // this shouldn't happen, it basically means that we are prioritizing
  172. // updates to send to a client that doesn't have a presence in the scene
  173. // seems like there's race condition here...
  174. // m_log.WarnFormat("[PRIORITIZER] attempt to use agent {0} not in the scene",client.AgentId);
  175. // throw new InvalidOperationException("Prioritization agent not defined");
  176. return PriorityQueue.NumberOfQueues - 1;
  177. }
  178. // Use group position for child prims, since we are putting child prims in
  179. // the same queue with the root of the group, the root prim (which goes into
  180. // the queue first) should always be sent first, no need to adjust child prim
  181. // priorities
  182. Vector3 entityPos = entity.AbsolutePosition;
  183. if (entity is SceneObjectPart)
  184. {
  185. SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup;
  186. entityPos = group.AbsolutePosition;
  187. }
  188. // Use the camera position for local agents and avatar position for remote agents
  189. Vector3 presencePos = (presence.IsChildAgent) ?
  190. presence.AbsolutePosition :
  191. presence.CameraPosition;
  192. // Compute the distance...
  193. double distance = Vector3.Distance(presencePos, entityPos);
  194. // And convert the distance to a priority queue, this computation gives queues
  195. // at 10, 20, 40, 80, 160, 320, 640, and 1280m
  196. uint pqueue = PriorityQueue.NumberOfImmediateQueues;
  197. uint queues = PriorityQueue.NumberOfQueues - PriorityQueue.NumberOfImmediateQueues;
  198. for (int i = 0; i < queues - 1; i++)
  199. {
  200. if (distance < 10 * Math.Pow(2.0,i))
  201. break;
  202. pqueue++;
  203. }
  204. // If this is a root agent, then determine front & back
  205. // Bump up the priority queue (drop the priority) for any objects behind the avatar
  206. if (useFrontBack && ! presence.IsChildAgent)
  207. {
  208. // Root agent, decrease priority for objects behind us
  209. Vector3 camPosition = presence.CameraPosition;
  210. Vector3 camAtAxis = presence.CameraAtAxis;
  211. // Plane equation
  212. float d = -Vector3.Dot(camPosition, camAtAxis);
  213. float p = Vector3.Dot(camAtAxis, entityPos) + d;
  214. if (p < 0.0f)
  215. pqueue++;
  216. }
  217. return pqueue;
  218. }
  219. }
  220. }