path: root/OpenSim/Region/Framework/Scenes/Prioritizer.cs

/*
 * Copyright (c) Contributors, http://opensimulator.org/
 * See CONTRIBUTORS.TXT for a full list of copyright holders.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the OpenSimulator Project nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Collections.Generic;
using log4net;
using Nini.Config;
using OpenSim.Framework;
using OpenMetaverse;
using OpenSim.Region.PhysicsModules.SharedBase;

/*
 * Steps to add a new prioritization policy:
 * 
 *  - Add a new value to the UpdatePrioritizationSchemes enum.
 *  - Specify this new value in the [InterestManagement] section of your
 *    OpenSim.ini. The name in the config file must match the enum value name
 *    (although it is not case sensitive).
 *  - Write a new GetPriorityBy*() method in this class.
 *  - Add a new entry to the switch statement in GetUpdatePriority() that calls
 *    your method.
 */

namespace OpenSim.Region.Framework.Scenes
{
    public enum UpdatePrioritizationSchemes
    {
        Time = 0,
        Distance = 1,
        SimpleAngularDistance = 2,
        FrontBack = 3,
        BestAvatarResponsiveness = 4,
    }

    public class Prioritizer
    {
        private static readonly ILog m_log = LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);
        
        private Scene m_scene;

        public Prioritizer(Scene scene)
        {
            m_scene = scene;
        }

        /// <summary>
        /// Returns the priority queue into which the update should be placed. Updates within a
        /// queue will be processed in arrival order. There are currently 12 priority queues
        /// implemented in PriorityQueue class in LLClientView. Queue 0 is generally retained
        /// for avatar updates. The fair queuing discipline for processing the priority queues
        /// assumes that the number of entities in each priority queues increases exponentially.
        /// So for example... if queue 1 contains all updates within 10m of the avatar or camera
        /// then queue 2 at 20m is about 3X bigger in space & about 3X bigger in total number
        /// of updates.
        /// </summary>
        public uint GetUpdatePriority(IClientAPI client, ISceneEntity entity)
        {
            // If entity is null we have a serious problem
            if (entity == null)
            {
                m_log.WarnFormat("[PRIORITIZER] attempt to prioritize null entity");
                throw new InvalidOperationException("Prioritization entity not defined");
            }

            // If this is an update for our own avatar give it the highest priority
            if (client.AgentId == entity.UUID)
                return 0;

            uint priority;
            
            switch (m_scene.UpdatePrioritizationScheme)
            {
/*
                case UpdatePrioritizationSchemes.Time:
                    priority = GetPriorityByTime(client, entity);
                    break;
                case UpdatePrioritizationSchemes.Distance:
                    priority = GetPriorityByDistance(client, entity);
                    break;
                case UpdatePrioritizationSchemes.SimpleAngularDistance:
                    priority = GetPriorityByDistance(client, entity); // TODO: Reimplement SimpleAngularDistance
                    break;
                case UpdatePrioritizationSchemes.FrontBack:
                    priority = GetPriorityByFrontBack(client, entity);
                    break;
*/
                case UpdatePrioritizationSchemes.SimpleAngularDistance:
                    priority = GetPriorityByAngularDistance(client, entity); // TODO: Reimplement SimpleAngularDistance
                    break;
                case UpdatePrioritizationSchemes.BestAvatarResponsiveness:
                default:
                    priority = GetPriorityByBestAvatarResponsiveness(client, entity);
                    break;
            }
            
            return priority;
        }

        private uint GetPriorityByTime(IClientAPI client, ISceneEntity entity)
        {
            // And anything attached to this avatar gets top priority as well
            if (entity is SceneObjectPart)
            {
                SceneObjectPart sop = (SceneObjectPart)entity;
                if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
                    return 1;
            }

            return PriorityQueue.NumberOfImmediateQueues; // first queue past the immediate queues
        }

        private uint GetPriorityByDistance(IClientAPI client, ISceneEntity entity)
        {
            // And anything attached to this avatar gets top priority as well
            if (entity is SceneObjectPart)
            {
                SceneObjectPart sop = (SceneObjectPart)entity;
                if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
                    return 1;
            }

            return ComputeDistancePriority(client,entity,false);
        }
        
        private uint GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity)
        {
            // And anything attached to this avatar gets top priority as well
            if (entity is SceneObjectPart)
            {
                SceneObjectPart sop = (SceneObjectPart)entity;
                if (sop.ParentGroup.IsAttachment && client.AgentId == sop.ParentGroup.AttachedAvatar)
                    return 1;
            }

            return ComputeDistancePriority(client,entity,true);
        }

        private uint GetPriorityByBestAvatarResponsiveness(IClientAPI client, ISceneEntity entity)
        {
            uint pqueue = 2; // keep compiler happy

            ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
            if (presence != null)
            {
                // All avatars other than our own go into pqueue 1
                if (entity is ScenePresence)
                    return 1;

                if (entity is SceneObjectPart)
                {
                    // Attachments are high priority, 
                    if (((SceneObjectPart)entity).ParentGroup.IsAttachment)
                        return 2;

                    pqueue = ComputeDistancePriority(client, entity, false);

                    // Non physical prims are lower priority than physical prims
                    PhysicsActor physActor = ((SceneObjectPart)entity).ParentGroup.RootPart.PhysActor;
                    if (physActor == null || !physActor.IsPhysical)
                        pqueue++;
                }
            }
            else
                pqueue = ComputeDistancePriority(client, entity, false);

            return pqueue;
        }

        private uint ComputeDistancePriority(IClientAPI client, ISceneEntity entity, bool useFrontBack)
        {
            // Get this agent's position
            ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
            if (presence == null)
            {
                // this shouldn't happen, it basically means that we are prioritizing 
                // updates to send to a client that doesn't have a presence in the scene
                // seems like there's race condition here...

                // m_log.WarnFormat("[PRIORITIZER] attempt to use agent {0} not in the scene",client.AgentId);
                // throw new InvalidOperationException("Prioritization agent not defined");
                return PriorityQueue.NumberOfQueues - 1;
            }
                
            // Use group position for child prims, since we are putting child prims in
            // the same queue with the root of the group, the root prim (which goes into
            // the queue first) should always be sent first, no need to adjust child prim
            // priorities
            Vector3 entityPos = entity.AbsolutePosition;
            if (entity is SceneObjectPart)
            {
                SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup;
                entityPos = group.AbsolutePosition;
            }

            // Use the camera position for local agents and avatar position for remote agents
            // Why would I want that? They could be camming but I still see them at the
            // avatar position, so why should I update them as if they were at their
            // camera positions? Makes no sense!
            // TODO: Fix this mess
            //Vector3 presencePos = (presence.IsChildAgent) ?
            //    presence.AbsolutePosition :
            //    presence.CameraPosition;

            Vector3 presencePos = presence.AbsolutePosition;

            // Compute the distance... 
            double distance = Vector3.Distance(presencePos, entityPos);

            // And convert the distance to a priority queue, this computation gives queues
            // at 10, 20, 40, 80, 160, 320, 640, and 1280m
            uint pqueue = PriorityQueue.NumberOfImmediateQueues + 1; // reserve attachments queue
            uint queues = PriorityQueue.NumberOfQueues - PriorityQueue.NumberOfImmediateQueues;
/*            
            for (int i = 0; i < queues - 1; i++)
            {
                if (distance < 30 * Math.Pow(2.0,i))
                    break;
                pqueue++;
            }
*/
            if (distance > 10f)
            {
                float tmp = (float)Math.Log((double)distance) * 1.442695f - 3.321928f;
                // for a map identical to original:
                // now 
                // 1st constant is 1/(log(2)) (natural log) so we get log2(distance)
                // 2st constant makes it be log2(distance/10)
                pqueue += (uint)tmp;
                if (pqueue > queues - 1)
                    pqueue = queues - 1;
            }

            // If this is a root agent, then determine front & back
            // Bump up the priority queue (drop the priority) for any objects behind the avatar
            if (useFrontBack && ! presence.IsChildAgent)
            {
                // Root agent, decrease priority for objects behind us
                Vector3 camPosition = presence.CameraPosition;
                Vector3 camAtAxis = presence.CameraAtAxis;

                // Plane equation
                float d = -Vector3.Dot(camPosition, camAtAxis);
                float p = Vector3.Dot(camAtAxis, entityPos) + d;
                if (p < 0.0f) 
                    pqueue++;
            }

            return pqueue;
        }

        private uint GetPriorityByAngularDistance(IClientAPI client, ISceneEntity entity)
        {
            uint pqueue = 2; // keep compiler happy

            ScenePresence presence = m_scene.GetScenePresence(client.AgentId);
            if (presence == null)
                return PriorityQueue.NumberOfQueues - 1;

            // All avatars other than our own go into pqueue 1
            if (entity is ScenePresence)
                return 1;

            if (entity is SceneObjectPart)
            {
                // Attachments are high priority, 
                if (((SceneObjectPart)entity).ParentGroup.IsAttachment)
                    return 2;

                pqueue = ComputeAngleDistancePriority(presence, entity);

                // Non physical prims are lower priority than physical prims
                PhysicsActor physActor = ((SceneObjectPart)entity).ParentGroup.RootPart.PhysActor;
                if (physActor == null || !physActor.IsPhysical)
                    pqueue++;
            }

            return pqueue;
        }

        private uint ComputeAngleDistancePriority(ScenePresence presence, ISceneEntity entity)
        {
            double distance;
                
            Vector3 presencePos = presence.AbsolutePosition;

            SceneObjectGroup group = (entity as SceneObjectPart).ParentGroup;
            float bradius = group.GetBoundsRadius();
            Vector3 grppos = group.AbsolutePosition + group.getBoundsCenter();
            distance = Vector3.Distance(presencePos, grppos);
            distance -= bradius;
            distance *= group.getAreaFactor();

            // And convert the distance to a priority queue, this computation gives queues
            // at 10, 20, 40, 80, 160, 320, 640, and 1280m
            uint pqueue = PriorityQueue.NumberOfImmediateQueues + 1; // reserve attachments queue
            uint queues = PriorityQueue.NumberOfQueues - PriorityQueue.NumberOfImmediateQueues;

            if (distance > 10f)
            {
                float tmp = (float)Math.Log(distance) * 1.442695f - 3.321928f;
                // for a map identical to original:
                // now 
                // 1st constant is 1/(log(2)) (natural log) so we get log2(distance)
                // 2st constant makes it be log2(distance/10)
                
                pqueue += (uint)tmp;
                if (pqueue > queues - 1)
                    pqueue = queues - 1;
            }

            return pqueue;
        }
    }
}