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

Revision 921, 17.1 KB checked in by mattausch, 19 years ago (diff)

added updates for visibility
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#ifdef GTP_VISIBILITY_MODIFIED_OGRE     
229        //-----------------------------------------------------------------------
230    void RenderPriorityGroup::clear(const int leavePassesInQueue, bool destroy = false)
231    {
232                //-- standard method if no passes are left in queue
233                if (!leavePassesInQueue)
234                {
235                        clear();
236
237                        // additionally destroy the collections
238                        if (destroy)
239                        {
240                                mSolidsBasic.clear(destroy);
241                                mSolidsDecal.clear(destroy);
242                                mSolidsDiffuseSpecular.clear(destroy);
243                                mSolidsNoShadowReceive.clear(destroy);
244                                mTransparents.clear(destroy);
245                        }
246
247                        return;
248                }
249
250        // We do not clear the unchanged solid pass maps, only the contents of each list
251        // This is because we assume passes are reused a lot and it saves resorting
252                if (!(leavePassesInQueue & SOLID_PASSES))
253                        mSolidsBasic.clear(destroy);
254                if (!(leavePassesInQueue & SOLID_PASSES_DECAL))
255                mSolidsDecal.clear(destroy);
256        if (!(leavePassesInQueue & SOLID_PASSES_DIFFUSE_SPECULAR))
257                    mSolidsDiffuseSpecular.clear(destroy);
258                if (!(leavePassesInQueue & SOLID_PASSES_NOSHADOW))
259                        mSolidsNoShadowReceive.clear(destroy);
260        if (!(leavePassesInQueue & TRANSPARENT_PASSES))
261                        mTransparents.clear(destroy);
262    }
263#endif // GTP_VISIBILITY_MODIFIED_OGRE 
264
265        //-----------------------------------------------------------------------
266        void RenderPriorityGroup::sort(const Camera* cam)
267        {
268                mSolidsBasic.sort(cam);
269                mSolidsDecal.sort(cam);
270                mSolidsDiffuseSpecular.sort(cam);
271                mSolidsNoShadowReceive.sort(cam);
272                mTransparents.sort(cam);
273        }
274    //-----------------------------------------------------------------------
275        QueuedRenderableCollection::QueuedRenderableCollection(void)
276                :mOrganisationMode(0)
277        {
278        }
279    //-----------------------------------------------------------------------
280        QueuedRenderableCollection::~QueuedRenderableCollection(void)
281        {
282        // destroy all the pass map entries (rather than clearing)
283        PassGroupRenderableMap::iterator i, iend;
284        iend = mGrouped.end();
285        for (i = mGrouped.begin(); i != iend; ++i)
286        {
287            // Free the list associated with this pass
288            delete i->second;
289        }
290               
291        }
292    //-----------------------------------------------------------------------
293        void QueuedRenderableCollection::clear(void)
294        {
295        PassGroupRenderableMap::iterator i, iend;
296        iend = mGrouped.end();
297        for (i = mGrouped.begin(); i != iend; ++i)
298        {
299            // Clear the list associated with this pass, but leave the pass entry
300            i->second->clear();
301        }
302
303                // Clear sorted list
304                mSortedDescending.clear();
305        }
306        //-----------------------------------------------------------------------
307#ifdef GTP_VISIBILITY_MODIFIED_OGRE
308        void QueuedRenderableCollection::clear(bool destroy)
309        {
310                if (!destroy)
311                {
312                        clear();
313                        return;
314                }
315
316        PassGroupRenderableMap::iterator i, iend;
317        iend = mGrouped.end();
318        for (i = mGrouped.begin(); i != iend; ++i)
319        {
320            // Clear the list associated with this pass, but leave the pass entry
321            delete i->second;
322        }
323
324
325                mGrouped.clear();
326
327                // Clear sorted list
328                mSortedDescending.clear();
329        }
330#endif // GTP_VISIBILITY_MODIFIED_OGRE
331    //-----------------------------------------------------------------------
332        void QueuedRenderableCollection::removePassGroup(Pass* p)
333        {
334        PassGroupRenderableMap::iterator i;
335
336        i = mGrouped.find(p);
337        if (i != mGrouped.end())
338        {
339            // free memory
340            delete i->second;
341            // erase from map
342            mGrouped.erase(i);
343        }
344        }
345    //-----------------------------------------------------------------------
346        void QueuedRenderableCollection::sort(const Camera* cam)
347    {
348                // ascending and descending sort both set bit 1
349                if (mOrganisationMode & OM_SORT_DESCENDING)
350                {
351                       
352                        // We can either use a stable_sort and the 'less' implementation,
353                        // or a 2-pass radix sort (once by pass, then by distance, since
354                        // radix sorting is inherently stable this will work)
355                        // We use stable_sort if the number of items is 512 or less, since
356                        // the complexity of the radix sort is approximately O(10N), since
357                        // each sort is O(5N) (1 pass histograms, 4 passes sort)
358                        // Since stable_sort has a worst-case performance of O(N(logN)^2)
359                        // the performance tipping point is from about 1500 items, but in
360                        // stable_sorts best-case scenario O(NlogN) it would be much higher.
361                        // Take a stab at 2000 items.
362                       
363                        if (mSortedDescending.size() > 2000)
364                        {
365                                // sort by pass
366                                msRadixSorter1.sort(mSortedDescending, RadixSortFunctorPass());
367                                // sort by depth
368                                msRadixSorter2.sort(mSortedDescending, RadixSortFunctorDistance(cam));
369                        }
370                        else
371                        {
372                                std::stable_sort(
373                                        mSortedDescending.begin(), mSortedDescending.end(),
374                                        DepthSortDescendingLess(cam));
375                        }
376                }
377
378                // Nothing needs to be done for pass groups, they auto-organise
379
380    }
381    //-----------------------------------------------------------------------
382    void QueuedRenderableCollection::addRenderable(Pass* pass, Renderable* rend)
383        {
384                // ascending and descending sort both set bit 1
385                if (mOrganisationMode & OM_SORT_DESCENDING)
386                {
387                        mSortedDescending.push_back(RenderablePass(rend, pass));
388                }
389
390                if (mOrganisationMode & OM_PASS_GROUP)
391                {
392            PassGroupRenderableMap::iterator i = mGrouped.find(pass);
393            if (i == mGrouped.end())
394            {
395                std::pair<PassGroupRenderableMap::iterator, bool> retPair;
396                // Create new pass entry, build a new list
397                // Note that this pass and list are never destroyed until the
398                                // engine shuts down, or a pass is destroyed or has it's hash
399                                // recalculated, although the lists will be cleared
400                retPair = mGrouped.insert(
401                    PassGroupRenderableMap::value_type(
402                                                pass, new RenderableList() ));
403                assert(retPair.second &&
404                                        "Error inserting new pass entry into PassGroupRenderableMap");
405                i = retPair.first;
406            }
407            // Insert renderable
408            i->second->push_back(rend);
409                       
410                }
411               
412        }
413    //-----------------------------------------------------------------------
414        void QueuedRenderableCollection::acceptVisitor(
415                QueuedRenderableVisitor* visitor, OrganisationMode om) const
416        {
417                if ((om & mOrganisationMode) == 0)
418                {
419                        OGRE_EXCEPT(Exception::ERR_INVALIDPARAMS,
420                                "Organisation mode requested in acceptVistor was not notified "
421                                "to this class ahead of time, therefore may not be supported.",
422                                "QueuedRenderableCollection::acceptVisitor");
423                }
424
425                switch(om)
426                {
427                case OM_PASS_GROUP:
428                        acceptVisitorGrouped(visitor);
429                        break;
430                case OM_SORT_DESCENDING:
431                        acceptVisitorDescending(visitor);
432                        break;
433                case OM_SORT_ASCENDING:
434                        acceptVisitorAscending(visitor);
435                        break;
436                }
437               
438        }
439    //-----------------------------------------------------------------------
440        void QueuedRenderableCollection::acceptVisitorGrouped(
441                QueuedRenderableVisitor* visitor) const
442        {
443                PassGroupRenderableMap::const_iterator ipass, ipassend;
444                ipassend = mGrouped.end();
445                for (ipass = mGrouped.begin(); ipass != ipassend; ++ipass)
446                {
447                        // Fast bypass if this group is now empty
448                        if (ipass->second->empty()) continue;
449
450                        // Visit Pass - allow skip
451                        if (!visitor->visit(ipass->first))
452                                continue;
453
454                        RenderableList* rendList = ipass->second;
455                        RenderableList::const_iterator irend, irendend;
456                        irendend = rendList->end();
457                        for (irend = rendList->begin(); irend != irendend; ++irend)
458                        {
459                                // Visit Renderable
460                                visitor->visit(*irend);
461                        }
462                }
463
464        }
465    //-----------------------------------------------------------------------
466        void QueuedRenderableCollection::acceptVisitorDescending(
467                QueuedRenderableVisitor* visitor) const
468        {
469                // List is already in descending order, so iterate forward
470                RenderablePassList::const_iterator i, iend;
471
472                iend = mSortedDescending.end();
473                for (i = mSortedDescending.begin(); i != iend; ++i)
474                {
475                        visitor->visit(&(*i));
476                }
477        }
478    //-----------------------------------------------------------------------
479        void QueuedRenderableCollection::acceptVisitorAscending(
480                QueuedRenderableVisitor* visitor) const
481        {
482                // List is in descending order, so iterate in reverse
483                RenderablePassList::const_reverse_iterator i, iend;
484
485                iend = mSortedDescending.rend();
486                for (i = mSortedDescending.rbegin(); i != iend; ++i)
487                {
488                        visitor->visit(&(*i));
489                }
490
491        }
492
493
494}
495
Note: See TracBrowser for help on using the repository browser.