[692] | 1 | /*
|
---|
| 2 | -----------------------------------------------------------------------------
|
---|
| 3 | This source file is part of OGRE
|
---|
| 4 | (Object-oriented Graphics Rendering Engine)
|
---|
| 5 | For the latest info, see http://www.ogre3d.org/
|
---|
| 6 |
|
---|
| 7 | Copyright (c) 2000-2005 The OGRE Team
|
---|
| 8 | Also see acknowledgements in Readme.html
|
---|
| 9 |
|
---|
| 10 | This program is free software; you can redistribute it and/or modify it under
|
---|
| 11 | the terms of the GNU Lesser General Public License as published by the Free Software
|
---|
| 12 | Foundation; either version 2 of the License, or (at your option) any later
|
---|
| 13 | version.
|
---|
| 14 |
|
---|
| 15 | This program is distributed in the hope that it will be useful, but WITHOUT
|
---|
| 16 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
---|
| 17 | FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
|
---|
| 18 |
|
---|
| 19 | You should have received a copy of the GNU Lesser General Public License along with
|
---|
| 20 | this program; if not, write to the Free Software Foundation, Inc., 59 Temple
|
---|
| 21 | Place - Suite 330, Boston, MA 02111-1307, USA, or go to
|
---|
| 22 | http://www.gnu.org/copyleft/lesser.txt.
|
---|
| 23 | -----------------------------------------------------------------------------
|
---|
| 24 | */
|
---|
| 25 | #include "OgreStableHeaders.h"
|
---|
| 26 | #include "OgreRenderQueueSortingGrouping.h"
|
---|
| 27 | #include "OgreException.h"
|
---|
| 28 |
|
---|
| 29 | namespace 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 |
|
---|