1
0

Prioritizer.cs 11 KB

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