Source/System/RenderingBackend/OSGStateSorter.cpp

   1 /*---------------------------------------------------------------------------*\
   2  *                                OpenSG                                     *
   3  *                                                                           *
   4  *                                                                           *
   5  *             Copyright (C) 2000-2002 by the OpenSG Forum                   *
   6  *                                                                           *
   7  *                            www.opensg.org                                 *
   8  *                                                                           *
   9  *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
  10  *                                                                           *
  11 \*---------------------------------------------------------------------------*/
  12 /*---------------------------------------------------------------------------*\
  13  *                                License                                    *
  14  *                                                                           *
  15  * This library is free software; you can redistribute it and/or modify it   *
  16  * under the terms of the GNU Library General Public License as published    *
  17  * by the Free Software Foundation, version 2.                               *
  18  *                                                                           *
  19  * This library is distributed in the hope that it will be useful, but       *
  20  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  22  * Library General Public License for more details.                          *
  23  *                                                                           *
  24  * You should have received a copy of the GNU Library General Public         *
  25  * License along with this library; if not, write to the Free Software       *
  26  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  27  *                                                                           *
  28 \*---------------------------------------------------------------------------*/
  29 /*---------------------------------------------------------------------------*\
  30  *                                Changes                                    *
  31  *                                                                           *
  32  *                                                                           *
  33  *                                                                           *
  34  *                                                                           *
  35  *                                                                           *
  36  *                                                                           *
  37 \*---------------------------------------------------------------------------*/
  38
  39 #include <cstdlib>
  40 #include <cstdio>
  41
  42 #include "OSGConfig.h"
  43
  44
  45 #include "OSGRenderTreeNodePool.h"
  46 #include "OSGStateSorter.h"
  47 #include "OSGBaseFunctions.h"
  48 #include "OSGStateOverride.h"
  49
  50 //#define OSG_DUMP_SORTING
  51
  52 OSG_USING_NAMESPACE
  53
  54 /*! \class OSG::StateSorter
  55     \ingroup GrpSystemRenderingBackend
  56  */
  57
  58 /*-------------------------------------------------------------------------*/
  59 /*                            Constructors                                 */
  60
  61
  62 StateSorter::StateSorter(void) :
  63     _pNodePool      (NULL    ),
  64     _uiNodePoolIdx  (0       ),
  65     _pRoot          (NULL    ),
  66     _oSorter        (        ),
  67     _eSortMode      (StateKey),
  68     _mFallbackSorter(        )
  69 {
  70 }
  71
  72 StateSorter::~StateSorter(void)
  73 {
  74 }
  75
  76
  77 void StateSorter::add(RenderTreeNode *pNode,
  78                       State          *pState,
  79                       StateOverride  *pStateOverride,
  80                       UInt32          uiKeyGen      )
  81 {
  82     if(_pRoot == NULL)
  83     {
  84         _pRoot                  =
  85             _pNodePool->create<RenderTreeNode>(_uiNodePoolIdx);
  86         RenderTreeNode *pL1Root =
  87             _pNodePool->create<RenderTreeNode>(_uiNodePoolIdx);
  88
  89         _oSorter.setupLevel1Root(pL1Root);
  90
  91         _pRoot->addChild(pL1Root);
  92     }
  93
  94     if(_eSortMode == StateKey)
  95     {
  96         UInt32 uiSortKey = pState->getSortKey(uiKeyGen);
  97
  98         if(pStateOverride != NULL)
  99         {
 100             pStateOverride->updateSortKey(uiSortKey, uiKeyGen);
 101         }
 102
 103         // Default Mat Id sorting
 104         if(uiSortKey > State::DefaultKeyMask)
 105         {
 106             MapSorterIt msIt = _mFallbackSorter.lower_bound(uiSortKey);
 107
 108             RenderTreeNode *pMatElem = NULL;
 109
 110             if(msIt == _mFallbackSorter.end() || msIt->first != uiSortKey)
 111             {
 112                 pMatElem = _pNodePool->create<RenderTreeNode>(_uiNodePoolIdx);
 113
 114                 pMatElem->setState        (pState        );
 115                 pMatElem->setStateOverride(pStateOverride);
 116
 117                 _mFallbackSorter.insert(msIt, std::make_pair(uiSortKey,
 118                                                              pMatElem ));
 119
 120                 _pRoot->addChild(pMatElem);
 121             }
 122             else
 123             {
 124                 pMatElem = msIt->second;
 125             }
 126
 127
 128             pMatElem->addChild(pNode);
 129         }
 130         else
 131         {
 132 #ifdef OSG_DUMP_SORTING
 133             fprintf(stderr, "Sort by chunk\n");
 134 #endif
 135
 136             UInt32 uiKey1 =  uiSortKey & State::Key1Mask;
 137             UInt32 uiKey2 = (uiSortKey & State::Key2Mask) >> 10;
 138             UInt32 uiKey3 = (uiSortKey & State::Key3Mask) >> 20;
 139
 140 #ifdef OSG_DUMP_SORTING
 141             fprintf(stderr, "Got Keys %d %d %d\n", uiKey1, uiKey2, uiKey3);
 142 #endif
 143
 144             RenderTreeNode *pMatElem = _oSorter.find(uiKey1,
 145                                                      uiKey2,
 146                                                      uiKey3);
 147
 148 #ifdef OSG_DUMP_SORTING
 149             fprintf(stderr, "got %p\n", pMatElem);
 150 #endif
 151
 152             if(pMatElem == NULL)
 153             {
 154                 pMatElem = _pNodePool->create<RenderTreeNode>(_uiNodePoolIdx);
 155
 156 //                pMatElem->setState        (pState        );
 157 //                pMatElem->setStateOverride(pStateOverride);
 158
 159                 _oSorter.insert( uiKey1,
 160                                  uiKey2,
 161                                  uiKey3,
 162                                  pMatElem,
 163                                 _pNodePool);
 164
 165 #ifdef OSG_DUMP_SORTING
 166                 fprintf(stderr, "Insert %p\n", pMatElem);
 167 #endif
 168             }
 169
 170             pMatElem->addChild(pNode);
 171
 172             pNode->setState        (pState        );
 173             pNode->setStateOverride(pStateOverride);
 174         }
 175     }
 176     else if(_eSortMode == ScalarKey)
 177     {
 178         if(_pRoot->getFirstChild() == NULL)
 179         {
 180             _pRoot->addChild(pNode);
 181         }
 182         else
 183         {
 184             RenderTreeNode *pCurrent = _pRoot->getFirstChild();
 185
 186             RenderTreeNode *pLast    = NULL;
 187             bool            bFound   = false;
 188
 189             do
 190             {
 191                 if(pNode->getScalar() > pCurrent->getScalar())
 192                 {
 193                     pLast    = pCurrent;
 194                     pCurrent = pCurrent->getBrother();
 195                 }
 196                 else
 197                 {
 198                     bFound = true;
 199                 }
 200
 201             } while(bFound   == false &&
 202                     pCurrent != NULL    );
 203
 204             if(bFound == true)
 205             {
 206                 if(pLast == NULL)
 207                 {
 208                     _pRoot->insertFirstChild(pNode);
 209                 }
 210                 else
 211                 {
 212                     _pRoot->insertChildAfter(pLast, pNode);
 213                 }
 214             }
 215             else
 216             {
 217                 _pRoot->addChild(pNode);
 218             }
 219         }
 220     }
 221     else
 222     {
 223         FFATAL(("StateSorter::add: unknown sort mode: %d!\n", _eSortMode));
 224     }
 225 }
 226