source: GTP/trunk/App/Demos/Geom/OgreStuff/include/OgreRenderQueueSortingGrouping.h @ 1812

/*
-----------------------------------------------------------------------------
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.
-----------------------------------------------------------------------------
*/
#ifndef __RenderQueueSortingGrouping_H__
#define __RenderQueueSortingGrouping_H__

// Precompiler options
#include "OgrePrerequisites.h"
#include "OgreIteratorWrappers.h"
#include "OgreMaterial.h"
#include "OgreTechnique.h"
#include "OgrePass.h"
#include "OgreRadixSort.h"

namespace Ogre {

        /** Struct associating a single Pass with a single Renderable. 
                This is used to for objects sorted by depth and thus not
                grouped by pass.
        */
        struct RenderablePass
        {
                /// Pointer to the Renderable details
                Renderable* renderable;
                /// Pointer to the Pass
                Pass* pass;

                RenderablePass(Renderable* rend, Pass* p) :renderable(rend), pass(p) {}
        };


        /** Visitor interface for items in a QueuedRenderableCollection.
        @remarks
                Those wishing to iterate over the items in a 
                QueuedRenderableCollection should implement this visitor pattern,
                since internal organisation of the collection depends on the 
                sorting method in use.
        */
        class _OgreExport QueuedRenderableVisitor
        {
        public:
                QueuedRenderableVisitor() {}
                virtual ~QueuedRenderableVisitor() {}
                
                /** Called when visiting a RenderablePass, ie items in a
                        sorted collection where items are not grouped by pass.
                @remarks
                        If this is called, neither of the other 2 visit methods
                        will be called.
                */
                virtual void visit(const RenderablePass* rp) = 0;

                /* When visiting a collection grouped by pass, this is
                        called when the grouping pass changes.
                @remarks
                        If this method is called, the RenderablePass visit 
                        method will not be called for this collection. The 
                        Renderable visit method will be called for each item
                        underneath the pass grouping level.
                @returns True to continue, false to skip the Renderables underneath
                */
                virtual bool visit(const Pass* p) = 0;
                /** Visit method called once per Renderable on a grouped 
                        collection.
                @remarks
                        If this method is called, the RenderablePass visit 
                        method will not be called for this collection. 
                */
                virtual void visit(const Renderable* r) = 0;
                
                
        };

        /** Lowest level collection of renderables.
        @remarks
                To iterate over items in this collection, you must call
                the accept method and supply a QueuedRenderableVisitor.
                The order of the iteration, and whether that iteration is
                over a RenderablePass list or a 2-level grouped list which 
                causes a visit call at the Pass level, and a call for each
                Renderable underneath.
        */
        class _OgreExport QueuedRenderableCollection
        {
        public:
                /** Organisation modes required for this collection.
                @remarks
                        This affects the internal placement of the items added to this collection;
                        if only one type of sorting / grouping is to be required, then renderables
                        can be stored only once, whilst if multiple types are going to be needed
                        then internally there will be multiple organisations. Changing the organisation
                        needs to be done when the collection is empty.
                */              
                enum OrganisationMode
                {
                        /// Group by pass
                        OM_PASS_GROUP = 1,
                        /// Sort descending camera distance
                        OM_SORT_DESCENDING = 2,
                        /** Sort ascending camera distance 
                                Note value overlaps with descending since both use same sort
                        */
                        OM_SORT_ASCENDING = 6
                };

        protected:
        /// Comparator to order pass groups
        struct PassGroupLess
        {
            bool _OgreExport operator()(const Pass* a, const Pass* b) const
            {
                // Sort by passHash, which is pass, then texture unit changes
                uint32 hasha = a->getHash();
                uint32 hashb = b->getHash();
                if (hasha == hashb)
                {
                    // Must differentTransparentQueueItemLessiate by pointer incase 2 passes end up with the same hash
                    return a < b;
                }
                else
                {
                    return hasha < hashb;
                }
            }
        };
        /// Comparator to order objects by descending camera distance
                struct DepthSortDescendingLess
        {
            const Camera* camera;

            DepthSortDescendingLess(const Camera* cam)
                : camera(cam)
            {
            }

            bool _OgreExport operator()(const RenderablePass& a, const RenderablePass& b) const
            {
                if (a.renderable == b.renderable)
                {
                    // Same renderable, sort by pass hash
                    return a.pass->getHash() < b.pass->getHash();
                }
                else
                {
                    // Different renderables, sort by depth
                    Real adepth = a.renderable->getSquaredViewDepth(camera);
                    Real bdepth = b.renderable->getSquaredViewDepth(camera);
                                    if (adepth == bdepth)
                                    {
                        // Must return deterministic result, doesn't matter what
                        return a.pass < b.pass;
                                    }
                                    else
                                    {
                                        // Sort DESCENDING by depth (ie far objects first)
                                            return (adepth > bdepth);
                                    }
                }

            }
        };

        /** Vector of RenderablePass objects, this is built on the assumption that
         vectors only ever increase in size, so even if we do clear() the memory stays
         allocated, ie fast */
        typedef std::vector<RenderablePass> RenderablePassList;
        typedef std::vector<Renderable*> RenderableList;
        /** Map of pass to renderable lists, this is a grouping by pass. */
        typedef std::map<Pass*, RenderableList*, PassGroupLess> PassGroupRenderableMap;

                /// Functor for accessing sort value 1 for radix sort (Pass)
                struct RadixSortFunctorPass
                {
                        uint32 operator()(const RenderablePass& p) const
            {
                return p.pass->getHash();
            }
                };

        /// Radix sorter for accessing sort value 1 (Pass)
                static RadixSort<RenderablePassList, RenderablePass, uint32> msRadixSorter1;

                /// Functor for descending sort value 2 for radix sort (distance)
                struct RadixSortFunctorDistance
                {
                        const Camera* camera;

            RadixSortFunctorDistance(const Camera* cam)
                : camera(cam)
            {
            }

                        float operator()(const RenderablePass& p) const
            {
                // Sort DESCENDING by depth (ie far objects first), use negative distance
                // here because radix sorter always dealing with accessing sort
                return static_cast<float>(- p.renderable->getSquaredViewDepth(camera));
            }
                };

        /// Radix sorter for sort value 2 (distance)
                static RadixSort<RenderablePassList, RenderablePass, float> msRadixSorter2;

                /// Bitmask of the organisation modes requested
                uint8 mOrganisationMode;

                /// Grouped 
                PassGroupRenderableMap mGrouped;
                /// Sorted descending (can iterate backwards to get ascending)
                RenderablePassList mSortedDescending;

                /// Internal visitor implementation
                void acceptVisitorGrouped(QueuedRenderableVisitor* visitor) const;
                /// Internal visitor implementation
                void acceptVisitorDescending(QueuedRenderableVisitor* visitor) const;
                /// Internal visitor implementation
                void acceptVisitorAscending(QueuedRenderableVisitor* visitor) const;

        public:
                QueuedRenderableCollection();
                ~QueuedRenderableCollection();

                /// Empty the collection
                void clear(void);

                /** Remove the group entry (if any) for a given Pass.
                @remarks
                        To be used when a pass is destroyed, such that any
                        grouping level for it becomes useless.
                */      
                void removePassGroup(Pass* p);
                
                /** Reset the organisation modes required for this collection. 
                @remarks
                        You can only do this when the collection is empty.
                @see OrganisationMode
                */
                void resetOrganisationModes(void) 
                { 
                        mOrganisationMode = 0; 
                }
                
                /** Add a required sorting / grouping mode to this collection when next used.
                @remarks
                        You can only do this when the collection is empty.
                @see OrganisationMode
                */
                void addOrganisationMode(OrganisationMode om) 
                { 
                        mOrganisationMode |= om; 
                }

        /// Add a renderable to the collection using a given pass
        void addRenderable(Pass* pass, Renderable* rend);
                
                /** Perform any sorting that is required on this collection.
                @param cam The camera
                */
                void sort(const Camera* cam);

                /** Accept a visitor over the collection contents.
                @param visitor Visitor class which should be called back
                @param om The organisation mode which you want to iterate over.
                        Note that this must have been included in an addOrganisationMode
                        call before any renderables were added.
                */
                void acceptVisitor(QueuedRenderableVisitor* visitor, OrganisationMode om) const;
                
        };

        /** Collection of renderables by priority.
    @remarks
        This class simply groups renderables for rendering. All the 
        renderables contained in this class are destined for the same
        RenderQueueGroup (coarse groupings like those between the main
        scene and overlays) and have the same priority (fine groupings
        for detailed overlap control).
    @par
        This class can order solid renderables by a number of criteria; 
                it can optimise them into groups based on pass to reduce render 
                state changes, or can sort them by ascending or descending view 
                depth. Transparent objects are always ordered by descending depth.
        @par
                To iterate over items in the collections held by this object 
                you should retrieve the collection in use (e.g. solids, solids with
                no shadows, transparents) and use the accept() method, providing 
                a class implementing QueuedRenderableVisitor.
        
    */
    class _OgreExport RenderPriorityGroup
    {
        protected:

                /// Parent queue group
        RenderQueueGroup* mParent;
        bool mSplitPassesByLightingType;
        bool mSplitNoShadowPasses;
                bool mShadowCastersNotReceivers;
        /// Solid pass list, used when no shadows, modulative shadows, or ambient passes for additive
                QueuedRenderableCollection mSolidsBasic;
        /// Solid per-light pass list, used with additive shadows
        QueuedRenderableCollection mSolidsDiffuseSpecular;
        /// Solid decal (texture) pass list, used with additive shadows
        QueuedRenderableCollection mSolidsDecal;
        /// Solid pass list, used when shadows are enabled but shadow receive is turned off for these passes
        QueuedRenderableCollection mSolidsNoShadowReceive;
                /// Transparent list
                QueuedRenderableCollection mTransparents;

        /// remove a pass entry from all collections
        void removePassEntry(Pass* p);

        /// Internal method for adding a solid renderable
        void addSolidRenderable(Technique* pTech, Renderable* rend, bool toNoShadowMap);
        /// Internal method for adding a solid renderable
        void addSolidRenderableSplitByLightType(Technique* pTech, Renderable* rend);
        /// Internal method for adding a transparent renderable
        void addTransparentRenderable(Technique* pTech, Renderable* rend);

    public:
        RenderPriorityGroup(RenderQueueGroup* parent, 
            bool splitPassesByLightingType,
            bool splitNoShadowPasses, 
                        bool shadowCastersNotReceivers); 
           
        ~RenderPriorityGroup() { }

        /** Get the collection of basic solids currently queued, this includes
                        all solids when there are no shadows, or all solids which have shadow
                        receiving enabled when using modulative shadows, or all ambient passes
                        of solids which have shadow receive enabled for additive shadows. */
        const QueuedRenderableCollection& getSolidsBasic(void) const
        { return mSolidsBasic; }
        /** Get the collection of solids currently queued per light (only applicable in 
                        additive shadow modes). */
        const QueuedRenderableCollection& getSolidsDiffuseSpecular(void) const
        { return mSolidsDiffuseSpecular; }
        /** Get the collection of solids currently queued for decal passes (only 
                        applicable in additive shadow modes). */
        const QueuedRenderableCollection& getSolidsDecal(void) const
        { return mSolidsDecal; }
        /** Get the collection of solids for which shadow receipt is disabled (only
                        applicable when shadows are enabled). */
        const QueuedRenderableCollection& getSolidsNoShadowReceive(void) const
        { return mSolidsNoShadowReceive; }
        /** Get the collection of transparent objects currently queued */
        const QueuedRenderableCollection& getTransparents(void) const
        { return mTransparents; }


                /** Reset the organisation modes required for the solids in this group. 
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void resetOrganisationModes(void);
                
                /** Add a required sorting / grouping mode for the solids in this group.
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void addOrganisationMode(QueuedRenderableCollection::OrganisationMode om); 

                /** Set the sorting / grouping mode for the solids in this group to the default.
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void defaultOrganisationMode(void); 

                /** Add a renderable to this group. */
        void addRenderable(Renderable* pRend, Technique* pTech);

                /** Sorts the objects which have been added to the queue; transparent objects by their 
            depth in relation to the passed in Camera. */
                void sort(const Camera* cam);

        /** Clears this group of renderables. 
        */
        void clear(void);

        /** Sets whether or not the queue will split passes by their lighting type,
        ie ambient, per-light and decal. 
        */
        void setSplitPassesByLightingType(bool split)
        {
            mSplitPassesByLightingType = split;
        }

        /** Sets whether or not passes which have shadow receive disabled should
            be separated. 
        */
        void setSplitNoShadowPasses(bool split)
        {
            mSplitNoShadowPasses = split;
        }

                /** Sets whether or not objects which cast shadows should be treated as
                        never receiving shadows. 
                */
                void setShadowCastersCannotBeReceivers(bool ind)
                {
                        mShadowCastersNotReceivers = ind;
                }



    };


    /** A grouping level underneath RenderQueue which groups renderables
    to be issued at coarsely the same time to the renderer.
    @remarks
        Each instance of this class itself hold RenderPriorityGroup instances, 
        which are the groupings of renderables by priority for fine control
        of ordering (not required for most instances).
    */
    class _OgreExport RenderQueueGroup
    {
    public:
        typedef std::map<ushort, RenderPriorityGroup*, std::less<ushort> > PriorityMap;
        typedef MapIterator<PriorityMap> PriorityMapIterator;
    protected:
        RenderQueue* mParent;
        bool mSplitPassesByLightingType;
        bool mSplitNoShadowPasses;
                bool mShadowCastersNotReceivers;
        /// Map of RenderPriorityGroup objects
        PriorityMap mPriorityGroups;
                /// Whether shadows are enabled for this queue
                bool mShadowsEnabled;


    public:
                RenderQueueGroup(RenderQueue* parent,
            bool splitPassesByLightingType,
            bool splitNoShadowPasses,
            bool shadowCastersNotReceivers) 
            : mParent(parent)
            , mSplitPassesByLightingType(splitPassesByLightingType)
            , mSplitNoShadowPasses(splitNoShadowPasses)
            , mShadowCastersNotReceivers(shadowCastersNotReceivers)
            , mShadowsEnabled(true)
        {
        }

        ~RenderQueueGroup() {
            // destroy contents now
            PriorityMap::iterator i;
            for (i = mPriorityGroups.begin(); i != mPriorityGroups.end(); ++i)
            {
                delete i->second;
            }
        }

        /** Get an iterator for browsing through child contents. */
        PriorityMapIterator getIterator(void)
        {
            return PriorityMapIterator(mPriorityGroups.begin(), mPriorityGroups.end());
        }

        /** Add a renderable to this group, with the given priority. */
        void addRenderable(Renderable* pRend, Technique* pTech, ushort priority)
        {
            // Check if priority group is there
            PriorityMap::iterator i = mPriorityGroups.find(priority);
            RenderPriorityGroup* pPriorityGrp;
            if (i == mPriorityGroups.end())
            {
                // Missing, create
                pPriorityGrp = new RenderPriorityGroup(this, 
                    mSplitPassesByLightingType,
                    mSplitNoShadowPasses, 
                                        mShadowCastersNotReceivers);
                mPriorityGroups.insert(PriorityMap::value_type(priority, pPriorityGrp));
            }
            else
            {
                pPriorityGrp = i->second;
            }

            // Add
            pPriorityGrp->addRenderable(pRend, pTech);

        }

        /** Clears this group of renderables. 
        @param destroy
            If false, doesn't delete any priority groups, just empties them. Saves on 
            memory deallocations since the chances are rougly the same kinds of 
            renderables are going to be sent to the queue again next time. If
                        true, completely destroys.
        */
        void clear(bool destroy = false)
        {
            PriorityMap::iterator i, iend;
            iend = mPriorityGroups.end();
            for (i = mPriorityGroups.begin(); i != iend; ++i)
            {
                                if (destroy)
                                        delete i->second;
                                else
                                        i->second->clear();
            }

                        if (destroy)
                                mPriorityGroups.clear();

        }

                /** Indicate whether a given queue group will be doing any
                shadow setup.
                @remarks
                This method allows you to inform the queue about a queue group, and to 
                indicate whether this group will require shadow processing of any sort.
                In order to preserve rendering order, OGRE has to treat queue groups
                as very separate elements of the scene, and this can result in it
                having to duplicate shadow setup for each group. Therefore, if you
                know that a group which you are using will never need shadows, you
                should preregister the group using this method in order to improve
                the performance.
                */
                void setShadowsEnabled(bool enabled) { mShadowsEnabled = enabled; }

                /** Are shadows enabled for this queue? */
                bool getShadowsEnabled(void) const { return mShadowsEnabled; }

        /** Sets whether or not the queue will split passes by their lighting type,
        ie ambient, per-light and decal. 
        */
        void setSplitPassesByLightingType(bool split)
        {
            mSplitPassesByLightingType = split;
            PriorityMap::iterator i, iend;
            iend = mPriorityGroups.end();
            for (i = mPriorityGroups.begin(); i != iend; ++i)
            {
                i->second->setSplitPassesByLightingType(split);
            }
        }
        /** Sets whether or not the queue will split passes which have shadow receive
        turned off (in their parent material), which is needed when certain shadow
        techniques are used.
        */
        void setSplitNoShadowPasses(bool split)
        {
            mSplitNoShadowPasses = split;
            PriorityMap::iterator i, iend;
            iend = mPriorityGroups.end();
            for (i = mPriorityGroups.begin(); i != iend; ++i)
            {
                i->second->setSplitNoShadowPasses(split);
            }
        }
                /** Sets whether or not objects which cast shadows should be treated as
                never receiving shadows. 
                */
                void setShadowCastersCannotBeReceivers(bool ind)
                {
                        mShadowCastersNotReceivers = ind;
                        PriorityMap::iterator i, iend;
                        iend = mPriorityGroups.end();
                        for (i = mPriorityGroups.begin(); i != iend; ++i)
                        {
                                i->second->setShadowCastersCannotBeReceivers(ind);
                        }
                }
                /** Reset the organisation modes required for the solids in this group. 
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void resetOrganisationModes(void)
                {
                        PriorityMap::iterator i, iend;
                        iend = mPriorityGroups.end();
                        for (i = mPriorityGroups.begin(); i != iend; ++i)
                        {
                                i->second->resetOrganisationModes();
                        }
                }
                
                /** Add a required sorting / grouping mode for the solids in this group.
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void addOrganisationMode(QueuedRenderableCollection::OrganisationMode om)
                {
                        PriorityMap::iterator i, iend;
                        iend = mPriorityGroups.end();
                        for (i = mPriorityGroups.begin(); i != iend; ++i)
                        {
                                i->second->addOrganisationMode(om);
                        }
                }

                /** Setthe  sorting / grouping mode for the solids in this group to the default.
                @remarks
                        You can only do this when the group is empty, ie after clearing the 
                        queue.
                @see QueuedRenderableCollection::OrganisationMode
                */
                void defaultOrganisationMode(void)
                {
                        PriorityMap::iterator i, iend;
                        iend = mPriorityGroups.end();
                        for (i = mPriorityGroups.begin(); i != iend; ++i)
                        {
                                i->second->defaultOrganisationMode();
                        }
                }

    };



}

#endif