source: OGRE/trunk/ogrenew/OgreMain/src/OgreRenderQueueSortingGrouping.cpp @ 692

Revision 692, 15.2 KB checked in by mattausch, 19 years ago (diff)

adding ogre 1.2 and dependencies

Line 
1/*
2-----------------------------------------------------------------------------
3This source file is part of OGRE
4(Object-oriented Graphics Rendering Engine)
5For the latest info, see http://www.ogre3d.org/
6
7Copyright (c) 2000-2005 The OGRE Team
8Also see acknowledgements in Readme.html
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25#include "OgreStableHeaders.h"
26#include "OgreRenderQueueSortingGrouping.h"
27#include "OgreException.h"
28
29namespace Ogre {
30    // Init statics
31    RadixSort<QueuedRenderableCollection::RenderablePassList,
32        RenderablePass, uint32> QueuedRenderableCollection::msRadixSorter1;
33    RadixSort<QueuedRenderableCollection::RenderablePassList,
34        RenderablePass, float> QueuedRenderableCollection::msRadixSorter2;
35
36
37        //-----------------------------------------------------------------------
38        RenderPriorityGroup::RenderPriorityGroup(RenderQueueGroup* parent,
39            bool splitPassesByLightingType,
40            bool splitNoShadowPasses,
41                        bool shadowCastersNotReceivers)
42                : mParent(parent)
43        , mSplitPassesByLightingType(splitPassesByLightingType)
44        , mSplitNoShadowPasses(splitNoShadowPasses)
45        , mShadowCastersNotReceivers(shadowCastersNotReceivers)
46        {
47                // Initialise collection sorting options
48                // this can become dynamic according to invocation later
49                defaultOrganisationMode();
50
51                // Transparents will always be sorted this way
52                mTransparents.addOrganisationMode(QueuedRenderableCollection::OM_SORT_DESCENDING);
53
54               
55        }
56        //-----------------------------------------------------------------------
57        void RenderPriorityGroup::resetOrganisationModes(void)
58        {
59                mSolidsBasic.resetOrganisationModes();
60                mSolidsDiffuseSpecular.resetOrganisationModes();
61                mSolidsDecal.resetOrganisationModes();
62                mSolidsNoShadowReceive.resetOrganisationModes();
63        }
64        //-----------------------------------------------------------------------
65        void RenderPriorityGroup::addOrganisationMode(QueuedRenderableCollection::OrganisationMode om)
66        {
67                mSolidsBasic.addOrganisationMode(om);
68                mSolidsDiffuseSpecular.addOrganisationMode(om);
69                mSolidsDecal.addOrganisationMode(om);
70                mSolidsNoShadowReceive.addOrganisationMode(om);
71        }
72        //-----------------------------------------------------------------------
73        void RenderPriorityGroup::defaultOrganisationMode(void)
74        {
75                resetOrganisationModes();
76                addOrganisationMode(QueuedRenderableCollection::OM_PASS_GROUP);
77        }
78        //-----------------------------------------------------------------------
79    void RenderPriorityGroup::addRenderable(Renderable* rend, Technique* pTech)
80    {
81        // Transparent and depth/colour settings mean depth sorting is required?
82        // Note: colour write disabled with depth check/write enabled means
83        //       setup depth buffer for other passes use.
84        if (pTech->isTransparent() &&
85            (!pTech->isDepthWriteEnabled() ||
86             !pTech->isDepthCheckEnabled() ||
87             pTech->hasColourWriteDisabled()))
88        {
89            addTransparentRenderable(pTech, rend);
90        }
91        else
92        {
93            if (mSplitNoShadowPasses &&
94                mParent->getShadowsEnabled() &&
95                                (!pTech->getParent()->getReceiveShadows() ||
96                                rend->getCastsShadows() && mShadowCastersNotReceivers))
97            {
98                // Add solid renderable and add passes to no-shadow group
99                addSolidRenderable(pTech, rend, true);
100            }
101            else
102            {
103                if (mSplitPassesByLightingType && mParent->getShadowsEnabled())
104                {
105                    addSolidRenderableSplitByLightType(pTech, rend);
106                }
107                else
108                {
109                    addSolidRenderable(pTech, rend, false);
110                }
111            }
112        }
113
114    }
115    //-----------------------------------------------------------------------
116    void RenderPriorityGroup::addSolidRenderable(Technique* pTech,
117        Renderable* rend, bool addToNoShadow)
118    {
119        Technique::PassIterator pi = pTech->getPassIterator();
120
121                QueuedRenderableCollection* collection;
122        if (addToNoShadow)
123        {
124            collection = &mSolidsNoShadowReceive;
125        }
126        else
127        {
128            collection = &mSolidsBasic;
129        }
130
131
132        while (pi.hasMoreElements())
133        {
134            // Insert into solid list
135            Pass* p = pi.getNext();
136                        collection->addRenderable(p, rend);
137        }
138    }
139    //-----------------------------------------------------------------------
140    void RenderPriorityGroup::addSolidRenderableSplitByLightType(Technique* pTech,
141        Renderable* rend)
142    {
143        // Divide the passes into the 3 categories
144        Technique::IlluminationPassIterator pi =
145            pTech->getIlluminationPassIterator();
146
147        while (pi.hasMoreElements())
148        {
149            // Insert into solid list
150            IlluminationPass* p = pi.getNext();
151            QueuedRenderableCollection* collection;
152            switch(p->stage)
153            {
154            case IS_AMBIENT:
155                collection = &mSolidsBasic;
156                break;
157            case IS_PER_LIGHT:
158                collection = &mSolidsDiffuseSpecular;
159                break;
160            case IS_DECAL:
161                collection = &mSolidsDecal;
162                break;
163            };
164
165                        collection->addRenderable(p->pass, rend);
166        }
167    }
168    //-----------------------------------------------------------------------
169    void RenderPriorityGroup::addTransparentRenderable(Technique* pTech, Renderable* rend)
170    {
171        Technique::PassIterator pi = pTech->getPassIterator();
172
173        while (pi.hasMoreElements())
174        {
175            // Insert into transparent list
176            mTransparents.addRenderable(pi.getNext(), rend);
177        }
178    }
179    //-----------------------------------------------------------------------
180        void RenderPriorityGroup::removePassEntry(Pass* p)
181        {
182                mSolidsBasic.removePassGroup(p);
183                mSolidsDiffuseSpecular.removePassGroup(p);
184                mSolidsNoShadowReceive.removePassGroup(p);
185                mSolidsDecal.removePassGroup(p);
186                mTransparents.removePassGroup(p); // shouldn't be any, but for completeness
187        }       
188    //-----------------------------------------------------------------------
189    void RenderPriorityGroup::clear(void)
190    {
191        // Delete queue groups which are using passes which are to be
192        // deleted, we won't need these any more and they clutter up
193        // the list and can cause problems with future clones
194        const Pass::PassSet& graveyardList = Pass::getPassGraveyard();
195        Pass::PassSet::const_iterator gi, giend;
196        giend = graveyardList.end();
197        for (gi = graveyardList.begin(); gi != giend; ++gi)
198        {
199            removePassEntry(*gi);
200        }
201
202        // Now remove any dirty passes, these will have their hashes recalculated
203        // by the parent queue after all groups have been processed
204        // If we don't do this, the std::map will become inconsistent for new insterts
205        const Pass::PassSet& dirtyList = Pass::getDirtyHashList();
206        Pass::PassSet::const_iterator di, diend;
207        diend = dirtyList.end();
208        for (di = dirtyList.begin(); di != diend; ++di)
209        {
210            removePassEntry(*di);
211        }
212        // NB we do NOT clear the graveyard or the dirty list here, because
213        // it needs to be acted on for all groups, the parent queue takes
214        // care of this afterwards
215
216                // Now empty the remaining collections
217                // Note that groups don't get deleted, just emptied hence the difference
218                // between the pass groups which are removed above, and clearing done
219                // here
220                mSolidsBasic.clear();
221        mSolidsDecal.clear();
222        mSolidsDiffuseSpecular.clear();
223        mSolidsNoShadowReceive.clear();
224        mTransparents.clear();
225
226    }
227        //-----------------------------------------------------------------------
228        void RenderPriorityGroup::sort(const Camera* cam)
229        {
230                mSolidsBasic.sort(cam);
231                mSolidsDecal.sort(cam);
232                mSolidsDiffuseSpecular.sort(cam);
233                mSolidsNoShadowReceive.sort(cam);
234                mTransparents.sort(cam);
235        }
236    //-----------------------------------------------------------------------
237        QueuedRenderableCollection::QueuedRenderableCollection(void)
238                :mOrganisationMode(0)
239        {
240        }
241    //-----------------------------------------------------------------------
242        QueuedRenderableCollection::~QueuedRenderableCollection(void)
243        {
244        // destroy all the pass map entries (rather than clearing)
245        PassGroupRenderableMap::iterator i, iend;
246        iend = mGrouped.end();
247        for (i = mGrouped.begin(); i != iend; ++i)
248        {
249            // Free the list associated with this pass
250            delete i->second;
251        }
252               
253        }
254    //-----------------------------------------------------------------------
255        void QueuedRenderableCollection::clear(void)
256        {
257        PassGroupRenderableMap::iterator i, iend;
258        iend = mGrouped.end();
259        for (i = mGrouped.begin(); i != iend; ++i)
260        {
261            // Clear the list associated with this pass, but leave the pass entry
262            i->second->clear();
263        }
264
265                // Clear sorted list
266                mSortedDescending.clear();
267        }
268    //-----------------------------------------------------------------------
269        void QueuedRenderableCollection::removePassGroup(Pass* p)
270        {
271        PassGroupRenderableMap::iterator i;
272
273        i = mGrouped.find(p);
274        if (i != mGrouped.end())
275        {
276            // free memory
277            delete i->second;
278            // erase from map
279            mGrouped.erase(i);
280        }
281        }
282    //-----------------------------------------------------------------------
283        void QueuedRenderableCollection::sort(const Camera* cam)
284    {
285                // ascending and descending sort both set bit 1
286                if (mOrganisationMode & OM_SORT_DESCENDING)
287                {
288                       
289                        // We can either use a stable_sort and the 'less' implementation,
290                        // or a 2-pass radix sort (once by pass, then by distance, since
291                        // radix sorting is inherently stable this will work)
292                        // We use stable_sort if the number of items is 512 or less, since
293                        // the complexity of the radix sort is approximately O(10N), since
294                        // each sort is O(5N) (1 pass histograms, 4 passes sort)
295                        // Since stable_sort has a worst-case performance of O(N(logN)^2)
296                        // the performance tipping point is from about 1500 items, but in
297                        // stable_sorts best-case scenario O(NlogN) it would be much higher.
298                        // Take a stab at 2000 items.
299                       
300                        if (mSortedDescending.size() > 2000)
301                        {
302                                // sort by pass
303                                msRadixSorter1.sort(mSortedDescending, RadixSortFunctorPass());
304                                // sort by depth
305                                msRadixSorter2.sort(mSortedDescending, RadixSortFunctorDistance(cam));
306                        }
307                        else
308                        {
309                                std::stable_sort(
310                                        mSortedDescending.begin(), mSortedDescending.end(),
311                                        DepthSortDescendingLess(cam));
312                        }
313                }
314
315                // Nothing needs to be done for pass groups, they auto-organise
316
317    }
318    //-----------------------------------------------------------------------
319    void QueuedRenderableCollection::addRenderable(Pass* pass, Renderable* rend)
320        {
321                // ascending and descending sort both set bit 1
322                if (mOrganisationMode & OM_SORT_DESCENDING)
323                {
324                        mSortedDescending.push_back(RenderablePass(rend, pass));
325                }
326
327                if (mOrganisationMode & OM_PASS_GROUP)
328                {
329            PassGroupRenderableMap::iterator i = mGrouped.find(pass);
330            if (i == mGrouped.end())
331            {
332                std::pair<PassGroupRenderableMap::iterator, bool> retPair;
333                // Create new pass entry, build a new list
334                // Note that this pass and list are never destroyed until the
335                                // engine shuts down, or a pass is destroyed or has it's hash
336                                // recalculated, although the lists will be cleared
337                retPair = mGrouped.insert(
338                    PassGroupRenderableMap::value_type(
339                                                pass, new RenderableList() ));
340                assert(retPair.second &&
341                                        "Error inserting new pass entry into PassGroupRenderableMap");
342                i = retPair.first;
343            }
344            // Insert renderable
345            i->second->push_back(rend);
346                       
347                }
348               
349        }
350    //-----------------------------------------------------------------------
351        void QueuedRenderableCollection::acceptVisitor(
352                QueuedRenderableVisitor* visitor, OrganisationMode om) const
353        {
354                if ((om & mOrganisationMode) == 0)
355                {
356                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
357                                "Organisation mode requested in acceptVistor was not notified "
358                                "to this class ahead of time, therefore may not be supported.",
359                                "QueuedRenderableCollection::acceptVisitor");
360                }
361
362                switch(om)
363                {
364                case OM_PASS_GROUP:
365                        acceptVisitorGrouped(visitor);
366                        break;
367                case OM_SORT_DESCENDING:
368                        acceptVisitorDescending(visitor);
369                        break;
370                case OM_SORT_ASCENDING:
371                        acceptVisitorAscending(visitor);
372                        break;
373                }
374               
375        }
376    //-----------------------------------------------------------------------
377        void QueuedRenderableCollection::acceptVisitorGrouped(
378                QueuedRenderableVisitor* visitor) const
379        {
380                PassGroupRenderableMap::const_iterator ipass, ipassend;
381                ipassend = mGrouped.end();
382                for (ipass = mGrouped.begin(); ipass != ipassend; ++ipass)
383                {
384                        // Fast bypass if this group is now empty
385                        if (ipass->second->empty()) continue;
386
387                        // Visit Pass - allow skip
388                        if (!visitor->visit(ipass->first))
389                                continue;
390
391                        RenderableList* rendList = ipass->second;
392                        RenderableList::const_iterator irend, irendend;
393                        irendend = rendList->end();
394                        for (irend = rendList->begin(); irend != irendend; ++irend)
395                        {
396                                // Visit Renderable
397                                visitor->visit(*irend);
398                        }
399                }
400
401        }
402    //-----------------------------------------------------------------------
403        void QueuedRenderableCollection::acceptVisitorDescending(
404                QueuedRenderableVisitor* visitor) const
405        {
406                // List is already in descending order, so iterate forward
407                RenderablePassList::const_iterator i, iend;
408
409                iend = mSortedDescending.end();
410                for (i = mSortedDescending.begin(); i != iend; ++i)
411                {
412                        visitor->visit(&(*i));
413                }
414        }
415    //-----------------------------------------------------------------------
416        void QueuedRenderableCollection::acceptVisitorAscending(
417                QueuedRenderableVisitor* visitor) const
418        {
419                // List is in descending order, so iterate in reverse
420                RenderablePassList::const_reverse_iterator i, iend;
421
422                iend = mSortedDescending.rend();
423                for (i = mSortedDescending.rbegin(); i != iend; ++i)
424                {
425                        visitor->visit(&(*i));
426                }
427
428        }
429
430
431}
432
Note: See TracBrowser for help on using the repository browser.