Prioritizer.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271
  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.PhysicsModules.SharedBase;
  34. namespace OpenSim.Region.Framework.Scenes
  35. {
  36. public enum UpdatePrioritizationSchemes
  37. {
  38. SimpleAngularDistance = 0,
  39. BestAvatarResponsiveness = 1,
  40. }
  41. public class Prioritizer
  42. {
  43. private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);
  44. private Scene m_scene;
  45. public Prioritizer(Scene scene)
  46. {
  47. m_scene = scene;
  48. }
  49. /// <summary>
  50. /// Returns the priority queue into which the update should be placed.
  51. /// </summary>
  52. public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity)
  53. {
  54. // If entity is null we have a serious problem
  55. if (entity == null)
  56. {
  57. m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity");
  58. throw new InvalidOperationException("Prioritization entity not defined");
  59. }
  60. // If this is an update for our own avatar give it the highest priority
  61. if (client.AgentId == entity.UUID)
  62. return 0;
  63. uint priority;
  64. switch (m_scene.UpdatePrioritizationScheme)
  65. {
  66. case UpdatePrioritizationSchemes.SimpleAngularDistance:
  67. priority = GetPriorityByAngularDistance(client, entity);
  68. break;
  69. case UpdatePrioritizationSchemes.BestAvatarResponsiveness:
  70. default:
  71. priority = GetPriorityByBestAvatarResponsiveness(client, entity);
  72. break;
  73. }
  74. return priority;
  75. }
  76. private uint GetPriorityByBestAvatarResponsiveness(IClientAPI client, ISceneEntity entity)
  77. {
  78. uint pqueue = 2; // keep compiler happy
  79. ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
  80. if (presence != null)
  81. {
  82. // All avatars other than our own go into pqueue 1
  83. if (entity is ScenePresence)
  84. return 1;
  85. if (entity is SceneObjectPart)
  86. {
  87. SceneObjectGroup sog = ((SceneObjectPart)entity).ParentGroup;
  88. // Attachments are high priority,
  89. if (sog.IsAttachment)
  90. return 2;
  91. if(presence.ParentPart != null)
  92. {
  93. if(presence.ParentPart.ParentGroup == sog)
  94. return 2;
  95. }
  96. pqueue = ComputeDistancePriority(client, entity, false);
  97. // Non physical prims are lower priority than physical prims
  98. PhysicsActor physActor = sog.RootPart.PhysActor;
  99. if (physActor == null || !physActor.IsPhysical)
  100. pqueue++;
  101. }
  102. }
  103. else
  104. pqueue = ComputeDistancePriority(client, entity, false);
  105. return pqueue;
  106. }
  107. private uint ComputeDistancePriority(IClientAPI client, ISceneEntity entity, bool useFrontBack)
  108. {
  109. // Get this agent's position
  110. ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
  111. if (presence == null)
  112. {
  113. // this shouldn't happen, it basically means that we are prioritizing
  114. // updates to send to a client that doesn't have a presence in the scene
  115. // seems like there's race condition here...
  116. // m_log.WarnFormat("[PRIORITIZER] attempt to use agent {0} not in the scene",client.AgentId);
  117. // throw new InvalidOperationException("Prioritization agent not defined");
  118. return PriorityQueue.NumberOfQueues - 1;
  119. }
  120. // Use group position for child prims, since we are putting child prims in
  121. // the same queue with the root of the group, the root prim (which goes into
  122. // the queue first) should always be sent first, no need to adjust child prim
  123. // priorities
  124. Vector3 entityPos = entity.AbsolutePosition;
  125. if (entity is SceneObjectPart)
  126. {
  127. SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup;
  128. entityPos = group.AbsolutePosition;
  129. }
  130. // Use the camera position for local agents and avatar position for remote agents
  131. // Why would I want that? They could be camming but I still see them at the
  132. // avatar position, so why should I update them as if they were at their
  133. // camera positions? Makes no sense!
  134. // TODO: Fix this mess
  135. //Vector3 presencePos = (presence.IsChildAgent) ?
  136. // presence.AbsolutePosition :
  137. // presence.CameraPosition;
  138. Vector3 presencePos = presence.AbsolutePosition;
  139. // Compute the distance...
  140. double distance = Vector3.Distance(presencePos, entityPos);
  141. // And convert the distance to a priority queue, this computation gives queues
  142. // at 10, 20, 40, 80, 160, 320, 640, and 1280m
  143. uint pqueue = PriorityQueue.NumberOfImmediateQueues + 1; // reserve attachments queue
  144. if (distance > 10f)
  145. {
  146. float tmp = (float)Math.Log((double)distance) * 1.442695f - 3.321928f;
  147. // for a map identical to original:
  148. // now
  149. // 1st constant is 1/(log(2)) (natural log) so we get log2(distance)
  150. // 2st constant makes it be log2(distance/10)
  151. pqueue += (uint)tmp;
  152. }
  153. // If this is a root agent, then determine front & back
  154. // Bump up the priority queue (drop the priority) for any objects behind the avatar
  155. if (useFrontBack && ! presence.IsChildAgent)
  156. {
  157. // Root agent, decrease priority for objects behind us
  158. Vector3 camPosition = presence.CameraPosition;
  159. Vector3 camAtAxis = presence.CameraAtAxis;
  160. // Plane equation
  161. float d = -Vector3.Dot(camPosition, camAtAxis);
  162. float p = Vector3.Dot(camAtAxis, entityPos) + d;
  163. if (p < 0.0f)
  164. pqueue++;
  165. }
  166. return pqueue;
  167. }
  168. private uint GetPriorityByAngularDistance(IClientAPI client, ISceneEntity entity)
  169. {
  170. ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
  171. if (presence == null)
  172. return PriorityQueue.NumberOfQueues - 1;
  173. uint pqueue = ComputeAngleDistancePriority(presence, entity);
  174. return pqueue;
  175. }
  176. private uint ComputeAngleDistancePriority(ScenePresence presence, ISceneEntity entity)
  177. {
  178. uint pqueue = PriorityQueue.NumberOfImmediateQueues;
  179. float distance;
  180. Vector3 presencePos = presence.AbsolutePosition;
  181. if(entity is ScenePresence)
  182. {
  183. ScenePresence sp = entity as ScenePresence;
  184. distance = Vector3.DistanceSquared(presencePos, sp.AbsolutePosition);
  185. if (distance > 400f)
  186. {
  187. float tmp = (float)Math.Log(distance) * 0.7213475f - 4.321928f;
  188. pqueue += (uint)tmp;
  189. }
  190. return pqueue;
  191. }
  192. SceneObjectPart sop = entity as SceneObjectPart;
  193. SceneObjectGroup group = sop.ParentGroup;
  194. if(presence.ParentPart != null)
  195. {
  196. if(presence.ParentPart.ParentGroup == group)
  197. return pqueue;
  198. }
  199. if (group.IsAttachment)
  200. {
  201. if(group.RootPart.LocalId == presence.LocalId)
  202. return pqueue;
  203. distance = Vector3.DistanceSquared(presencePos, group.AbsolutePosition);
  204. if (distance > 400f)
  205. {
  206. float tmp = (float)Math.Log(distance) * 0.7213475f - 4.321928f;
  207. pqueue += (uint)tmp;
  208. }
  209. return pqueue;
  210. }
  211. float bradius = group.GetBoundsRadius();
  212. Vector3 grppos = group.getCenterOffset();
  213. distance = Vector3.Distance(presencePos, grppos);
  214. distance -= bradius;
  215. distance *= group.getAreaFactor();
  216. if(group.IsAttachment)
  217. distance *= 0.5f;
  218. else if(group.UsesPhysics)
  219. distance *= 0.6f;
  220. else if(group.GetSittingAvatarsCount() > 0)
  221. distance *= 0.5f;
  222. if (distance > 10f)
  223. {
  224. float tmp = (float)Math.Log(distance) * 1.442695f - 3.321928f;
  225. // for a map identical to original:
  226. // now
  227. // 1st constant is 1/(log(2)) (natural log) so we get log2(distance)
  228. // 2st constant makes it be log2(distance/10)
  229. pqueue += (uint)tmp;
  230. }
  231. return pqueue;
  232. }
  233. }
  234. }