source: OGRE/trunk/ogre_changes/Ogre1.2/OgreMain/src/OgreRenderQueueSortingGrouping.cpp @ 921

/*
-----------------------------------------------------------------------------
This source file is part of OGRE
(Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2005 The OGRE Team
Also see acknowledgements in Readme.html

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
Place - Suite 330, Boston, MA 02111-1307, USA, or go to
http://www.gnu.org/copyleft/lesser.txt.
-----------------------------------------------------------------------------
*/
#include "OgreStableHeaders.h"
#include "OgreRenderQueueSortingGrouping.h"
#include "OgreException.h"

namespace Ogre {
    // Init statics
    RadixSort<QueuedRenderableCollection::RenderablePassList,
        RenderablePass, uint32> QueuedRenderableCollection::msRadixSorter1;
    RadixSort<QueuedRenderableCollection::RenderablePassList,
        RenderablePass, float> QueuedRenderableCollection::msRadixSorter2;


        //-----------------------------------------------------------------------
        RenderPriorityGroup::RenderPriorityGroup(RenderQueueGroup* parent, 
            bool splitPassesByLightingType,
            bool splitNoShadowPasses, 
                        bool shadowCastersNotReceivers)
                : mParent(parent)
        , mSplitPassesByLightingType(splitPassesByLightingType)
        , mSplitNoShadowPasses(splitNoShadowPasses)
        , mShadowCastersNotReceivers(shadowCastersNotReceivers)
        {
                // Initialise collection sorting options
                // this can become dynamic according to invocation later
                defaultOrganisationMode();

                // Transparents will always be sorted this way
                mTransparents.addOrganisationMode(QueuedRenderableCollection::OM_SORT_DESCENDING);

                
        }
        //-----------------------------------------------------------------------
        void RenderPriorityGroup::resetOrganisationModes(void)
        {
                mSolidsBasic.resetOrganisationModes();
                mSolidsDiffuseSpecular.resetOrganisationModes();
                mSolidsDecal.resetOrganisationModes();
                mSolidsNoShadowReceive.resetOrganisationModes();
        }
        //-----------------------------------------------------------------------
        void RenderPriorityGroup::addOrganisationMode(QueuedRenderableCollection::OrganisationMode om)
        {
                mSolidsBasic.addOrganisationMode(om);
                mSolidsDiffuseSpecular.addOrganisationMode(om);
                mSolidsDecal.addOrganisationMode(om);
                mSolidsNoShadowReceive.addOrganisationMode(om);
        }
        //-----------------------------------------------------------------------
        void RenderPriorityGroup::defaultOrganisationMode(void)
        {
                resetOrganisationModes();
                addOrganisationMode(QueuedRenderableCollection::OM_PASS_GROUP);
        }
        //-----------------------------------------------------------------------
    void RenderPriorityGroup::addRenderable(Renderable* rend, Technique* pTech)
    {
        // Transparent and depth/colour settings mean depth sorting is required?
        // Note: colour write disabled with depth check/write enabled means
        //       setup depth buffer for other passes use.
        if (pTech->isTransparent() && 
            (!pTech->isDepthWriteEnabled() ||
             !pTech->isDepthCheckEnabled() ||
             pTech->hasColourWriteDisabled()))
        {
            addTransparentRenderable(pTech, rend);
        }
        else
        {
            if (mSplitNoShadowPasses &&
                mParent->getShadowsEnabled() &&
                                (!pTech->getParent()->getReceiveShadows() ||
                                rend->getCastsShadows() && mShadowCastersNotReceivers))
            {
                // Add solid renderable and add passes to no-shadow group
                addSolidRenderable(pTech, rend, true);
            }
            else
            {
                if (mSplitPassesByLightingType && mParent->getShadowsEnabled())
                {
                    addSolidRenderableSplitByLightType(pTech, rend);
                }
                else
                {
                    addSolidRenderable(pTech, rend, false);
                }
            }
        }

    }
    //-----------------------------------------------------------------------
    void RenderPriorityGroup::addSolidRenderable(Technique* pTech, 
        Renderable* rend, bool addToNoShadow)
    {
        Technique::PassIterator pi = pTech->getPassIterator();

                QueuedRenderableCollection* collection;
        if (addToNoShadow)
        {
            collection = &mSolidsNoShadowReceive;
        }
        else
        {
            collection = &mSolidsBasic;
        }


        while (pi.hasMoreElements())
        {
            // Insert into solid list
            Pass* p = pi.getNext();
                        collection->addRenderable(p, rend);
        }
    }
    //-----------------------------------------------------------------------
    void RenderPriorityGroup::addSolidRenderableSplitByLightType(Technique* pTech,
        Renderable* rend)
    {
        // Divide the passes into the 3 categories
        Technique::IlluminationPassIterator pi = 
            pTech->getIlluminationPassIterator();

        while (pi.hasMoreElements())
        {
            // Insert into solid list
            IlluminationPass* p = pi.getNext();
            QueuedRenderableCollection* collection;
            switch(p->stage)
            {
            case IS_AMBIENT:
                collection = &mSolidsBasic;
                break;
            case IS_PER_LIGHT:
                collection = &mSolidsDiffuseSpecular;
                break;
            case IS_DECAL:
                collection = &mSolidsDecal;
                break;
            };

                        collection->addRenderable(p->pass, rend);
        }
    }
    //-----------------------------------------------------------------------
    void RenderPriorityGroup::addTransparentRenderable(Technique* pTech, Renderable* rend)
    {
        Technique::PassIterator pi = pTech->getPassIterator();

        while (pi.hasMoreElements())
        {
            // Insert into transparent list
            mTransparents.addRenderable(pi.getNext(), rend);
        }
    }
    //-----------------------------------------------------------------------
        void RenderPriorityGroup::removePassEntry(Pass* p)
        {
                mSolidsBasic.removePassGroup(p);
                mSolidsDiffuseSpecular.removePassGroup(p);
                mSolidsNoShadowReceive.removePassGroup(p);
                mSolidsDecal.removePassGroup(p);
                mTransparents.removePassGroup(p); // shouldn't be any, but for completeness
        }       
    //-----------------------------------------------------------------------
    void RenderPriorityGroup::clear(void)
    {
        // Delete queue groups which are using passes which are to be
        // deleted, we won't need these any more and they clutter up 
        // the list and can cause problems with future clones
        const Pass::PassSet& graveyardList = Pass::getPassGraveyard();
        Pass::PassSet::const_iterator gi, giend;
        giend = graveyardList.end();
        for (gi = graveyardList.begin(); gi != giend; ++gi)
        {
            removePassEntry(*gi);
        }

        // Now remove any dirty passes, these will have their hashes recalculated
        // by the parent queue after all groups have been processed
        // If we don't do this, the std::map will become inconsistent for new insterts
        const Pass::PassSet& dirtyList = Pass::getDirtyHashList();
        Pass::PassSet::const_iterator di, diend;
        diend = dirtyList.end();
        for (di = dirtyList.begin(); di != diend; ++di)
        {
            removePassEntry(*di);
        }
        // NB we do NOT clear the graveyard or the dirty list here, because 
        // it needs to be acted on for all groups, the parent queue takes 
        // care of this afterwards

                // Now empty the remaining collections
                // Note that groups don't get deleted, just emptied hence the difference
                // between the pass groups which are removed above, and clearing done
                // here
                mSolidsBasic.clear();
        mSolidsDecal.clear();
        mSolidsDiffuseSpecular.clear();
        mSolidsNoShadowReceive.clear();
        mTransparents.clear();

    }

#ifdef GTP_VISIBILITY_MODIFIED_OGRE     
        //-----------------------------------------------------------------------
    void RenderPriorityGroup::clear(const int leavePassesInQueue, bool destroy = false)
    {
                //-- standard method if no passes are left in queue
                if (!leavePassesInQueue)
                {
                        clear();

                        // additionally destroy the collections
                        if (destroy)
                        {
                                mSolidsBasic.clear(destroy);
                                mSolidsDecal.clear(destroy);
                                mSolidsDiffuseSpecular.clear(destroy);
                                mSolidsNoShadowReceive.clear(destroy);
                                mTransparents.clear(destroy);
                        }

                        return;
                }

        // We do not clear the unchanged solid pass maps, only the contents of each list
        // This is because we assume passes are reused a lot and it saves resorting
                if (!(leavePassesInQueue & SOLID_PASSES))
                        mSolidsBasic.clear(destroy);
                if (!(leavePassesInQueue & SOLID_PASSES_DECAL))
                mSolidsDecal.clear(destroy);
        if (!(leavePassesInQueue & SOLID_PASSES_DIFFUSE_SPECULAR))
                    mSolidsDiffuseSpecular.clear(destroy);
                if (!(leavePassesInQueue & SOLID_PASSES_NOSHADOW))
                        mSolidsNoShadowReceive.clear(destroy);
        if (!(leavePassesInQueue & TRANSPARENT_PASSES))
                        mTransparents.clear(destroy);
    }
#endif // GTP_VISIBILITY_MODIFIED_OGRE  

        //-----------------------------------------------------------------------
        void RenderPriorityGroup::sort(const Camera* cam)
        {
                mSolidsBasic.sort(cam);
                mSolidsDecal.sort(cam);
                mSolidsDiffuseSpecular.sort(cam);
                mSolidsNoShadowReceive.sort(cam);
                mTransparents.sort(cam);
        }
    //-----------------------------------------------------------------------
        QueuedRenderableCollection::QueuedRenderableCollection(void)
                :mOrganisationMode(0)
        {
        }
    //-----------------------------------------------------------------------
        QueuedRenderableCollection::~QueuedRenderableCollection(void)
        {
        // destroy all the pass map entries (rather than clearing)
        PassGroupRenderableMap::iterator i, iend;
        iend = mGrouped.end();
        for (i = mGrouped.begin(); i != iend; ++i)
        {
            // Free the list associated with this pass
            delete i->second;
        }
                
        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::clear(void)
        {
        PassGroupRenderableMap::iterator i, iend;
        iend = mGrouped.end();
        for (i = mGrouped.begin(); i != iend; ++i)
        {
            // Clear the list associated with this pass, but leave the pass entry
            i->second->clear();
        }

                // Clear sorted list
                mSortedDescending.clear();
        }
        //-----------------------------------------------------------------------
#ifdef GTP_VISIBILITY_MODIFIED_OGRE
        void QueuedRenderableCollection::clear(bool destroy)
        {
                if (!destroy)
                {
                        clear();
                        return;
                }

        PassGroupRenderableMap::iterator i, iend;
        iend = mGrouped.end();
        for (i = mGrouped.begin(); i != iend; ++i)
        {
            // Clear the list associated with this pass, but leave the pass entry
            delete i->second;
        }


                mGrouped.clear();

                // Clear sorted list
                mSortedDescending.clear();
        }
#endif // GTP_VISIBILITY_MODIFIED_OGRE
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::removePassGroup(Pass* p)
        {
        PassGroupRenderableMap::iterator i;

        i = mGrouped.find(p);
        if (i != mGrouped.end())
        {
            // free memory
            delete i->second;
            // erase from map
            mGrouped.erase(i);
        }
        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::sort(const Camera* cam)
    {
                // ascending and descending sort both set bit 1
                if (mOrganisationMode & OM_SORT_DESCENDING)
                {
                        
                        // We can either use a stable_sort and the 'less' implementation,
                        // or a 2-pass radix sort (once by pass, then by distance, since
                        // radix sorting is inherently stable this will work)
                        // We use stable_sort if the number of items is 512 or less, since
                        // the complexity of the radix sort is approximately O(10N), since 
                        // each sort is O(5N) (1 pass histograms, 4 passes sort)
                        // Since stable_sort has a worst-case performance of O(N(logN)^2)
                        // the performance tipping point is from about 1500 items, but in
                        // stable_sorts best-case scenario O(NlogN) it would be much higher.
                        // Take a stab at 2000 items.
                        
                        if (mSortedDescending.size() > 2000)
                        {
                                // sort by pass
                                msRadixSorter1.sort(mSortedDescending, RadixSortFunctorPass());
                                // sort by depth
                                msRadixSorter2.sort(mSortedDescending, RadixSortFunctorDistance(cam));
                        }
                        else
                        {
                                std::stable_sort(
                                        mSortedDescending.begin(), mSortedDescending.end(), 
                                        DepthSortDescendingLess(cam));
                        }
                }

                // Nothing needs to be done for pass groups, they auto-organise

    }
    //-----------------------------------------------------------------------
    void QueuedRenderableCollection::addRenderable(Pass* pass, Renderable* rend)
        {
                // ascending and descending sort both set bit 1
                if (mOrganisationMode & OM_SORT_DESCENDING)
                {
                        mSortedDescending.push_back(RenderablePass(rend, pass));
                }

                if (mOrganisationMode & OM_PASS_GROUP)
                {
            PassGroupRenderableMap::iterator i = mGrouped.find(pass);
            if (i == mGrouped.end())
            {
                std::pair<PassGroupRenderableMap::iterator, bool> retPair;
                // Create new pass entry, build a new list
                // Note that this pass and list are never destroyed until the 
                                // engine shuts down, or a pass is destroyed or has it's hash
                                // recalculated, although the lists will be cleared
                retPair = mGrouped.insert(
                    PassGroupRenderableMap::value_type(
                                                pass, new RenderableList() ));
                assert(retPair.second && 
                                        "Error inserting new pass entry into PassGroupRenderableMap");
                i = retPair.first;
            }
            // Insert renderable
            i->second->push_back(rend);
                        
                }
                
        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::acceptVisitor(
                QueuedRenderableVisitor* visitor, OrganisationMode om) const
        {
                if ((om & mOrganisationMode) == 0)
                {
                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS, 
                                "Organisation mode requested in acceptVistor was not notified "
                                "to this class ahead of time, therefore may not be supported.", 
                                "QueuedRenderableCollection::acceptVisitor");
                }

                switch(om)
                {
                case OM_PASS_GROUP:
                        acceptVisitorGrouped(visitor);
                        break;
                case OM_SORT_DESCENDING:
                        acceptVisitorDescending(visitor);
                        break;
                case OM_SORT_ASCENDING:
                        acceptVisitorAscending(visitor);
                        break;
                }
                
        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::acceptVisitorGrouped(
                QueuedRenderableVisitor* visitor) const
        {
                PassGroupRenderableMap::const_iterator ipass, ipassend;
                ipassend = mGrouped.end();
                for (ipass = mGrouped.begin(); ipass != ipassend; ++ipass)
                {
                        // Fast bypass if this group is now empty
                        if (ipass->second->empty()) continue;

                        // Visit Pass - allow skip
                        if (!visitor->visit(ipass->first))
                                continue;

                        RenderableList* rendList = ipass->second;
                        RenderableList::const_iterator irend, irendend;
                        irendend = rendList->end();
                        for (irend = rendList->begin(); irend != irendend; ++irend)
                        {
                                // Visit Renderable
                                visitor->visit(*irend);
                        }
                } 

        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::acceptVisitorDescending(
                QueuedRenderableVisitor* visitor) const
        {
                // List is already in descending order, so iterate forward
                RenderablePassList::const_iterator i, iend;

                iend = mSortedDescending.end();
                for (i = mSortedDescending.begin(); i != iend; ++i)
                {
                        visitor->visit(&(*i));
                }
        }
    //-----------------------------------------------------------------------
        void QueuedRenderableCollection::acceptVisitorAscending(
                QueuedRenderableVisitor* visitor) const
        {
                // List is in descending order, so iterate in reverse
                RenderablePassList::const_reverse_iterator i, iend;

                iend = mSortedDescending.rend();
                for (i = mSortedDescending.rbegin(); i != iend; ++i)
                {
                        visitor->visit(&(*i));
                }

        }


}