/* ----------------------------------------------------------------------------- This source file is part of OGRE (Object-oriented Graphics Rendering Engine) For the latest info, see http://www.ogre3d.org/ Copyright (c) 2000-2009 Torus Knot Software Ltd Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ----------------------------------------------------------------------------- */ #include "OgreStableHeaders.h" #include "OgreRenderQueueSortingGrouping.h" #include "OgreException.h" namespace Ogre { // Init statics RadixSort QueuedRenderableCollection::msRadixSorter1; RadixSort 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(); mTransparentsUnsorted.resetOrganisationModes(); } //----------------------------------------------------------------------- void RenderPriorityGroup::addOrganisationMode(QueuedRenderableCollection::OrganisationMode om) { mSolidsBasic.addOrganisationMode(om); mSolidsDiffuseSpecular.addOrganisationMode(om); mSolidsDecal.addOrganisationMode(om); mSolidsNoShadowReceive.addOrganisationMode(om); mTransparentsUnsorted.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->isTransparentSortingForced() || (pTech->isTransparent() && (!pTech->isDepthWriteEnabled() || !pTech->isDepthCheckEnabled() || pTech->hasColourWriteDisabled()))) { if (pTech->isTransparentSortingEnabled()) addTransparentRenderable(pTech, rend); else addUnsortedTransparentRenderable(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 = NULL; switch(p->stage) { case IS_AMBIENT: collection = &mSolidsBasic; break; case IS_PER_LIGHT: collection = &mSolidsDiffuseSpecular; break; case IS_DECAL: collection = &mSolidsDecal; break; default: assert(false); // should never happen }; collection->addRenderable(p->pass, rend); } } //----------------------------------------------------------------------- void RenderPriorityGroup::addUnsortedTransparentRenderable(Technique* pTech, Renderable* rend) { Technique::PassIterator pi = pTech->getPassIterator(); while (pi.hasMoreElements()) { // Insert into transparent list mTransparentsUnsorted.addRenderable(pi.getNext(), 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); mTransparentsUnsorted.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 { // Hmm, a bit hacky but least obtrusive for now OGRE_LOCK_MUTEX(Pass::msPassGraveyardMutex) 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 { // Hmm, a bit hacky but least obtrusive for now OGRE_LOCK_MUTEX(Pass::msDirtyHashListMutex) 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(); mTransparentsUnsorted.clear(); mTransparents.clear(); } //----------------------------------------------------------------------- void RenderPriorityGroup::sort(const Camera* cam) { mSolidsBasic.sort(cam); mSolidsDecal.sort(cam); mSolidsDiffuseSpecular.sort(cam); mSolidsNoShadowReceive.sort(cam); mTransparentsUnsorted.sort(cam); mTransparents.sort(cam); } //----------------------------------------------------------------------- void RenderPriorityGroup::merge( const RenderPriorityGroup* rhs ) { mSolidsBasic.merge( rhs->mSolidsBasic ); mSolidsDecal.merge( rhs->mSolidsDecal ); mSolidsDiffuseSpecular.merge( rhs->mSolidsDiffuseSpecular ); mSolidsNoShadowReceive.merge( rhs->mSolidsNoShadowReceive ); mTransparentsUnsorted.merge( rhs->mTransparentsUnsorted ); mTransparents.merge( rhs->mTransparents ); } //----------------------------------------------------------------------- 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 OGRE_DELETE_T(i->second, RenderableList, MEMCATEGORY_SCENE_CONTROL); } } //----------------------------------------------------------------------- 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(); } //----------------------------------------------------------------------- void QueuedRenderableCollection::removePassGroup(Pass* p) { PassGroupRenderableMap::iterator i; i = mGrouped.find(p); if (i != mGrouped.end()) { // free memory OGRE_DELETE_T(i->second, RenderableList, MEMCATEGORY_SCENE_CONTROL); // erase from map mGrouped.erase(i); } } //----------------------------------------------------------------------- void QueuedRenderableCollection::sort(const Camera* cam) { // ascending and descending sort both set bit 1 // We always sort descending, because the only difference is in the // acceptVisitor method, where we iterate in reverse in ascending mode 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 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, OGRE_NEW_T(RenderableList, MEMCATEGORY_SCENE_CONTROL)() )); 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) { // try to fall back if (OM_PASS_GROUP & mOrganisationMode) om = OM_PASS_GROUP; else if (OM_SORT_ASCENDING & mOrganisationMode) om = OM_SORT_ASCENDING; else if (OM_SORT_DESCENDING & mOrganisationMode) om = OM_SORT_DESCENDING; else 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(const_cast(*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(const_cast(&(*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(const_cast(&(*i))); } } //----------------------------------------------------------------------- void QueuedRenderableCollection::merge( const QueuedRenderableCollection& rhs ) { mSortedDescending.insert( mSortedDescending.end(), rhs.mSortedDescending.begin(), rhs.mSortedDescending.end() ); PassGroupRenderableMap::const_iterator srcGroup; for( srcGroup = rhs.mGrouped.begin(); srcGroup != rhs.mGrouped.end(); ++srcGroup ) { PassGroupRenderableMap::iterator dstGroup = mGrouped.find( srcGroup->first ); if (dstGroup == mGrouped.end()) { std::pair 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( srcGroup->first, OGRE_NEW_T(RenderableList, MEMCATEGORY_SCENE_CONTROL)() )); assert(retPair.second && "Error inserting new pass entry into PassGroupRenderableMap"); dstGroup = retPair.first; } // Insert renderable dstGroup->second->insert( dstGroup->second->end(), srcGroup->second->begin(), srcGroup->second->end() ); } } }