source: GTP/trunk/Lib/Vis/OnlineCullingCHC/OGRE/src/OgreKdTreeSceneManager.cpp @ 2130

/*
-----------------------------------------------------------------------------
This source file is part of the GameTools Project
http://www.gametools.org

Author: Martin Szydlowski
-----------------------------------------------------------------------------
*/

#include <OgreCamera.h>
#include <OgreSubEntity.h>
#include <OgreMaterialManager.h>
#include <OgreLogManager.h>
#include <OgreStringConverter.h>

#include "OgreKdTreeSceneManager.h"
#include "OgreKdTreeSceneNode.h"
#include "OgreKdTree.h"

#include <OgreMeshInstance.h>
#include <OgreBoundingBoxConverter.h>
#include <OgreTypeConverter.h>
#include <VisibilityEnvironment.h>
#include "OgreVisibilityOptionsManager.h"

namespace Ogre
{

KdTreeSceneManager::KdTreeSceneManager(const String& name, GtpVisibility::VisibilityManager *vm):
SceneManager(name), 
mVisibilityManager(vm), 
mKdTree(0), 
mMaxDepth(KDTREE_MAX_DEPTH),
mShowBoxes(false),
mHiLiteLevel(0),
mShowAllBoxes(false),
mEnhancedVisiblity(true),
mBuildMethod(KdTree::KDBM_RECURSIVE),
mRenderMethod(KdTree::KDRM_INTERNAL),
mShowVisualization(false),
mRenderNodesForViz(false),
mRenderNodesContentForViz(false),
mVisualizeCulledNodes(false),
mLeavePassesInQueue(0),
mDelayRenderTransparents(true),
mUseDepthPass(false),
mIsDepthPassPhase(false),
mUseItemBuffer(false),
mIsItemBufferPhase(false),
mCurrentEntityId(1),
mEnableDepthWrite(true),
mSkipTransparents(false),
mRenderTransparentsForItemBuffer(true),
mExecuteVertexProgramForAllPasses(false),
mIsHierarchicalCulling(false),
mDeleteQueueAfterRendering(true),
mViewCellsLoaded(false),
mUseViewCells(false),
mUseVisibilityFilter(false),
mViewCellsManager(0),
mElementaryViewCell(0),
mCurrentViewCell(0)
{
        // Replace root node with my node
        OGRE_DELETE(mSceneRoot);
        mSceneRoot = new KdTreeSceneNode(this, "root node");
        mSceneRoot->_notifyRootNode();

        // init heirarchy interface
        mHierarchyInterface = new KdTreeHierarchyInterface(this, mDestRenderSystem);
}

KdTreeSceneManager::~KdTreeSceneManager(void)
{
        delete mHierarchyInterface;
        delete mKdTree;
}

void KdTreeSceneManager::clearScene()
{
        // DEBUG
        //if (mKdTree)
        //      mKdTree->dump();

        // must happen before actual scene is cleared
        OGRE_DELETE(mKdTree);

        SceneManager::clearScene();
}


const String& KdTreeSceneManager::getTypeName(void) const
{
        return KdTreeSceneManagerFactory::FACTORY_TYPE_NAME;
}

void KdTreeSceneManager::setShowBoxes(bool showboxes)
{
        mShowBoxes = showboxes;
}

bool KdTreeSceneManager::getShowBoxes(void) const
{
        return mShowBoxes;
}

bool KdTreeSceneManager::setOption(const String& strKey, const void* pValue)
{
        // change max depth of the kdtree
        // rebuild the tree if already exists
        if (strKey == "KdTreeMaxDepth")
        {
                int maxdepth = *static_cast<const int *>(pValue);

                // no negative depth, plz!
                if (maxdepth < 0)
                {
                        return false;
                }
                else
                {
                        mMaxDepth = maxdepth;
                        if (mHiLiteLevel > mMaxDepth)
                                mHiLiteLevel = mMaxDepth;
                        return true;
                }
                return true;
        }
        else if (strKey == "KT")
        {
                Real kt = *static_cast<const Real *>(pValue);
                if (kt > 0)
                {
                        PlaneEvent::KT = kt;
                        return true;
                }
                else
                {
                        return false;
                }
        }
        else if (strKey == "KI")
        {
                Real ki = *static_cast<const Real *>(pValue);
                if (ki > 0)
                {
                        PlaneEvent::KI = ki;
                        return true;
                }
                else
                {
                        return false;
                }
        }
        else if (strKey == "RebuildKdTree")
        {
                OGRE_DELETE(mKdTree);
                mKdTree = new KdTree(mMaxDepth, mBuildMethod, mHiLiteLevel, mShowAllBoxes, mShowNodes);
                mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
                mKdTree->setEnhancedVis(mEnhancedVisiblity);
                return true;
        }
        else if (strKey == "EnhancedVisibility")
        {
                bool enh = *static_cast<const bool *>(pValue);
                mEnhancedVisiblity = enh;
                if (mKdTree)
                        mKdTree->setEnhancedVis(mEnhancedVisiblity);
                //setEnhancedVis(enh);
                return true;
        }
        else if (strKey == "BuildMethod")
        {
                KdTree::BuildMethod bm = *static_cast<const KdTree::BuildMethod *>(pValue);
                if (bm == KdTree::KDBM_RECURSIVE || bm == KdTree::KDBM_PRIORITYQUEUE)
                {
                        mBuildMethod = bm;
                        return true;
                }
                else
                {
                        return false;
                }
        }
        else if (strKey == "RenderMethod")
        {
                KdTree::RenderMethod rm = *static_cast<const KdTree::RenderMethod *>(pValue);
                if (rm == KdTree::KDRM_INTERNAL)
                {
                        mRenderMethod = rm;
                        return true;
                }
                else if (rm == KdTree::KDRM_GTP_VFC)
                {
                        mRenderMethod = rm;
                        int cmt = GtpVisibility::VisibilityEnvironment::FRUSTUM_CULLING;
                        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                                .setOption("Algorithm", &cmt);
                }
                else if (rm == KdTree::KDRM_GTP_SWC)
                {
                        mRenderMethod = rm;
                        int cmt = GtpVisibility::VisibilityEnvironment::STOP_AND_WAIT_CULLING;
                        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                                .setOption("Algorithm", &cmt);
                }
                else if (rm == KdTree::KDRM_GTP_CHC)
                {
                        mRenderMethod = rm;
                        int cmt = GtpVisibility::VisibilityEnvironment::COHERENT_HIERARCHICAL_CULLING;
                        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                                .setOption("Algorithm", &cmt);
                }
                else
                {
                        return false;
                }
        }
        // little hack in case someone uses "Algorithm" option from VisOptMan directly
        else if (strKey == "Algorithm")
        {
                bool success = VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                        .setOption(strKey, pValue);
                // change setting only if change in VisOptMan was successful
                if (success)
                {
                        int val = *static_cast<const int *>(pValue);
                        if (val == GtpVisibility::VisibilityEnvironment::FRUSTUM_CULLING)
                                mRenderMethod = KdTree::KDRM_GTP_VFC;
                        else if (val == GtpVisibility::VisibilityEnvironment::STOP_AND_WAIT_CULLING)
                                mRenderMethod = KdTree::KDRM_GTP_SWC;
                        else if (val == GtpVisibility::VisibilityEnvironment::COHERENT_HIERARCHICAL_CULLING)
                                mRenderMethod = KdTree::KDRM_GTP_CHC;
                        // default, should never happen
                        else
                                mRenderMethod = KdTree::KDRM_INTERNAL;
                }
                else
                {
                        mRenderMethod = KdTree::KDRM_INTERNAL;
                }
                return success;
        }
        else if (strKey == "ShowKdTree")
        {
                bool sk = *static_cast<const bool *>(pValue);
                mShowBoxes = sk;
                return true;
        }
        else if (strKey == "HiLiteLevel")
        {
                int hl = *static_cast<const int *>(pValue);
                if (hl >= 0 && hl <= mMaxDepth)
                {
                        mHiLiteLevel = hl;
                        if (mKdTree)
                                mKdTree->setHiLiteLevel(mHiLiteLevel);
                        return true;
                }
                else
                {
                        return false;
                }
        }
        else if (strKey == "ShowAllBoxes")
        {
                bool sa = *static_cast<const bool *>(pValue);
                mShowAllBoxes = sa;
                if (mKdTree)
                        mKdTree->setShowAllBoxes(mShowAllBoxes);
                return true;
        }
        else if (strKey == "ShowNodes")
        {
                bool sn = *static_cast<const bool *>(pValue);
                mShowNodes = sn;
                if (mKdTree)
                        mKdTree->setShowNodes(mShowNodes);
                return true;
        }
        // options for CHC
        else if (strKey == "UseDepthPass")
        {
                mUseDepthPass = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "PrepareVisualization")
        {
                mShowVisualization = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "RenderNodesForViz")
        {
                mRenderNodesForViz = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "RenderNodesContentForViz")
        {
                mRenderNodesContentForViz = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "SkyBoxEnabled")
        {
                mSkyBoxEnabled = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "SkyPlaneEnabled")
        {
                mSkyPlaneEnabled = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "SkyDomeEnabled")
        {
                mSkyDomeEnabled = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "VisualizeCulledNodes")
        {
                mVisualizeCulledNodes = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "DelayRenderTransparents")
        {
                mDelayRenderTransparents = (*static_cast<const bool *>(pValue));
                return true;
        }

        else if (strKey == "DepthWrite")
        {
                mEnableDepthWrite = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "UseItemBuffer")
        {
                mUseItemBuffer = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "ExecuteVertexProgramForAllPasses")
        { 
                mExecuteVertexProgramForAllPasses  = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "RenderTransparentsForItemBuffer")
        { 
                mRenderTransparentsForItemBuffer  = (*static_cast<const bool *>(pValue));
                return true;
        }
        else if (strKey == "DeleteRenderQueue")
        {
                mDeleteQueueAfterRendering = (*static_cast<const bool *>(pValue));
                return true;
        }
        // options for viewcells
        else if (strKey == "LoadViewCells")
        { 
                if (!mViewCellsLoaded)
                {
                        String filename(static_cast<const char *>(pValue));
                        mViewCellsLoaded = LoadViewCells(filename);     
                }

                return mViewCellsLoaded;
        }
        else if (strKey == "UseViewCells")
        { 
                if (mViewCellsLoaded)
                {
                        mUseViewCells = *static_cast<const bool *>(pValue);

                        // reset view cell
                        OGRE_DELETE(mCurrentViewCell);

                        if (mUseViewCells)
                                mCurrentViewCell = mViewCellsManager->GenerateViewCell();

                        mElementaryViewCell = NULL;

                        // if using view cells, all objects are set to false initially
                        SetObjectsVisible(!mUseViewCells);

                        return true;
                }
                else
                {
                        return false;
                }

        }
        else if (strKey == "UseVisibilityFilter")
        {
                if (mViewCellsLoaded)
                {
                        mUseVisibilityFilter = *static_cast<const bool *>(pValue);
                        // set null =>recomputation of the pvs
                        mElementaryViewCell = NULL;
                        return true;
                }
                else
                {
                        return false;
                }
        }

        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                .setOption(strKey, pValue) || SceneManager::setOption(strKey, pValue);
}

bool KdTreeSceneManager::getOption(const String& strKey, void* pDestValue)
{
        if (strKey == "KdTreeMaxDepth")
        {
                *static_cast<int *>(pDestValue) = mMaxDepth;
                return true;
        }
        else if (strKey == "KT")
        {
                *static_cast<Real *>(pDestValue) = PlaneEvent::KT;
                return true;
        }
        else if (strKey == "KI")
        {
                *static_cast<Real *>(pDestValue) = PlaneEvent::KI;
                return true;
        }
        else if (strKey == "EnhancedVisibility")
        {
                if (mKdTree)
                        *static_cast<bool *>(pDestValue) = mKdTree->getEnhancedVis();
                else
                        *static_cast<bool *>(pDestValue) = mEnhancedVisiblity;
                return true;
        }
        else if (strKey == "BuildMethod")
        {
                *static_cast<KdTree::BuildMethod *>(pDestValue) = mBuildMethod;
                return true;
        }
        else if (strKey == "RenderMethod")
        {
                *static_cast<KdTree::RenderMethod *>(pDestValue) = mRenderMethod;
                return true;
        }
        else if (strKey == "ShowKdTree")
        {
                *static_cast<bool *>(pDestValue) = mShowBoxes;
                return true;
        }       
        else if (strKey == "HiLiteLevel")
        {
                *static_cast<int *>(pDestValue) = mHiLiteLevel;
                return true;
        }
        else if (strKey == "ShowAllBoxes")
        {
                *static_cast<bool *>(pDestValue) = mShowAllBoxes;
                return true;
        }
        else if (strKey == "ShowNodes")
        {
                *static_cast<bool *>(pDestValue) = mShowNodes;
                return true;
        }
        // vis options
        else if (strKey == "NumFrustumCulledNodes")
        {
                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                {
                        unsigned int numnodes = 0;
                        if (mKdTree)
                                numnodes = mKdTree->getFramesStats().mFrustumCulledNodes;

                        * static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
                        return true;
                }
                // otherwise let fall through to VisibilityOptionsManager
        }
        else if (strKey == "NumQueryCulledNodes")
        {
                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                {
                        * static_cast<unsigned int *>(pDestValue) = 0;
                        return true;
                }
                // otherwise let fall through to VisibilityOptionsManager
        }
        else if (strKey == "NumHierarchyNodes")
        {
                unsigned int numnodes = 0;
                if (mKdTree)
                        numnodes = mKdTree->getTreeStats().mNumNodes;

                * static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
                return true;
        }
        else if (strKey == "NumRenderedNodes")
        {
                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                {
                        unsigned int numnodes = 0;
                        if (mKdTree)
                                numnodes = mKdTree->getFramesStats().mRenderedNodes;

                        * static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
                        return true;
                }
                // otherwise let fall through to VisibilityOptionsManager
        }
        else if (strKey == "NumQueriesIssued")
        {
                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                {
                        * static_cast<unsigned int *>(pDestValue) = 0;
                        return true;
                }
                // otherwise let fall through to VisibilityOptionsManager
        }
        else if (strKey == "NumTraversedNodes")
        {
                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                {
                        unsigned int numnodes = 0;
                        if (mKdTree)
                                numnodes = mKdTree->getFramesStats().mTraversedNodes;

                        * static_cast<unsigned int *>(pDestValue) = (unsigned int)numnodes;
                        return true;
                }
                // otherwise let fall through to VisibilityOptionsManager
        }
        else if (strKey == "VisibilityManager")
        {
                * static_cast<GtpVisibility::VisibilityManager **>(pDestValue) = 
                        (GtpVisibility::VisibilityManager *)mVisibilityManager;
                return true;
        }
        else if (strKey == "HierarchInterface")
        {
                * static_cast<GtpVisibility::HierarchyInterface **>(pDestValue) = 
                        (GtpVisibility::HierarchyInterface *)mHierarchyInterface;
                return true;
        }
        // view cell options

        else if (strKey == "UseViewCells")
        { 
                *static_cast<bool *>(pDestValue) = mUseViewCells;
                return mViewCellsLoaded;
        }
        else if (strKey == "UseVisibilityFilter")
        {
                *static_cast<bool *>(pDestValue) = mUseVisibilityFilter;
                return mViewCellsLoaded;
        }

        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                .getOption(strKey, pDestValue) || SceneManager::getOption(strKey, pDestValue);
}

bool KdTreeSceneManager::getOptionKeys(StringVector &refKeys)
{
        refKeys.push_back("Algorithm");
        refKeys.push_back("BuildMethod");
        refKeys.push_back("DelayRenderTransparents");
        refKeys.push_back("DeleteRenderQueue");
        refKeys.push_back("DepthWrite");
        refKeys.push_back("EnhancedVisibility");
        refKeys.push_back("ExecuteVertexProgramForAllPasses");
        refKeys.push_back("HiLiteLevel");
        refKeys.push_back("HierarchInterface");
        refKeys.push_back("KI");
        refKeys.push_back("KT");
        refKeys.push_back("KdTreeMaxDepth");
        refKeys.push_back("LoadViewCells");
        refKeys.push_back("NumHierarchyNodes");
        refKeys.push_back("PrepareVisualization");
        refKeys.push_back("RebuildKdTree");
        refKeys.push_back("RenderMethod");
        refKeys.push_back("RenderNodesContentForViz");
        refKeys.push_back("RenderNodesForViz");
        refKeys.push_back("RenderTransparentsForItemBuffer");
        refKeys.push_back("ShowAllBoxes");
        refKeys.push_back("ShowKdTree");
        refKeys.push_back("ShowNodes");
        refKeys.push_back("SkyBoxEnabled");
        refKeys.push_back("SkyDomeEnabled");
        refKeys.push_back("SkyPlaneEnabled");
        refKeys.push_back("UseDepthPass");
        refKeys.push_back("UseItemBuffer");
        refKeys.push_back("UseViewCells");
        refKeys.push_back("UseVisibilityFilter");
        refKeys.push_back("VisibilityManager");
        refKeys.push_back("VisualizeCulledNodes");
        return VisibilityOptionsManager(mVisibilityManager, mHierarchyInterface)
                .getOptionKeys(refKeys);
}

bool KdTreeSceneManager::getOptionValues(const String & key, StringVector &refValueList)
{
        return SceneManager::getOptionValues(key, refValueList);
}

void KdTreeSceneManager::setVisibilityManager(GtpVisibility::VisibilityManager *visManager)
{
        mVisibilityManager = visManager;
}

GtpVisibility::VisibilityManager * KdTreeSceneManager::getVisibilityManager()
{
        return mVisibilityManager;
}

GtpVisibility::VisibilityManager * KdTreeSceneManager::GetVisibilityManager()
{
        return mVisibilityManager;
}

KdTreeHierarchyInterface * KdTreeSceneManager::GetHierarchyInterface()
{
        return mHierarchyInterface;
}

Camera* KdTreeSceneManager::createCamera(const String& name)
{
        // Check name not used
        if (mCameras.find(name) != mCameras.end())
        {
                OGRE_EXCEPT(
                        Exception::ERR_DUPLICATE_ITEM,
                        "A camera with the name " + name + " already exists",
                        "SceneManager::createCamera" );
        }

        Camera *c = new KdTreeCamera(name, this);
        mCameras.insert(CameraList::value_type(name, c));

        return c;
}

SceneNode* KdTreeSceneManager::createSceneNode(void)
{
        SceneNode* sn = new KdTreeSceneNode(this);
        assert(mSceneNodes.find(sn->getName()) == mSceneNodes.end());
        mSceneNodes[sn->getName()] = sn;
        return sn;
}

SceneNode* KdTreeSceneManager::createSceneNode(const String& name)
{
        // Check name not used
        if (mSceneNodes.find(name) != mSceneNodes.end())
        {
                OGRE_EXCEPT(
                        Exception::ERR_DUPLICATE_ITEM,
                        "A scene node with the name " + name + " already exists",
                        "KdTreeSceneManager::createSceneNode" );
        }

        SceneNode* sn = new KdTreeSceneNode(this, name);
        mSceneNodes[sn->getName()] = sn;
        return sn;
}

Entity * KdTreeSceneManager::createEntity(const String& entityName, const String& meshName)
{
        Entity *ent = SceneManager::createEntity(entityName, meshName);
#ifdef GTP_VISIBILITY_MODIFIED_OGRE
        for (int i = 0; i < (int)ent->getNumSubEntities(); ++i)
        {
                ent->getSubEntity(i)->setId(mCurrentEntityId);
        }

        // increase counter of entity id values
        ++ mCurrentEntityId;
#endif
        return ent;
}

// make sure it's called only for non-empty nodes .. avoids one uneccessary funciton call
void KdTreeSceneManager::_updateNode(KdTreeSceneNode *node)
{
        //LogManager::getSingleton().logMessage("### _updateNode called for " + node->getName());

        /* Rebuild kdtree when it was wiped out
                * Usually this happens only before the first frame
                * The initial AABB shall enclose all objects present
                * in the scene at the time of construction
                * TODO: find a more appropriate place for it,
                * e.g., before the first render call
                * teh stupid thing is I can't find any other place so far ...
                */
        if (!mKdTree)
        {
                mKdTree = new KdTree(mMaxDepth, mBuildMethod);
                mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
                mKdTree->setEnhancedVis(mEnhancedVisiblity);
        }

        // if the node is in the tree and _updateNode was called, then the node was moved/rotated/resized/wahtever
        if (node->isAttached())
        {
                // TEST: perfomance when adding & removing for every frame
                //mKdTree->remove(node);
                //mKdTree->insert(node);
        }
        // there's a new node in town ... 
        else
        {                       
                // inserting single nodes yields sub-optimal results
                // rebuilding tree takes too long
                // "What now?", spoke Zeus ...

                //mKdTree->insert(node);
                
                //delete mKdTree;
                //mKdTree = new KdTree(mMaxDepth);
                //mKdTree->build(static_cast<KdTreeSceneNode *>(mSceneRoot));
        }

}

void KdTreeSceneManager::_updateSceneGraph(Camera* cam)
{
        mVisibilityManager->GetCullingManager()->SetHierarchyInterface(mHierarchyInterface);
        mHierarchyInterface->SetRenderSystem(mDestRenderSystem);

        SceneManager::_updateSceneGraph(cam);
}

void KdTreeSceneManager::_findVisibleObjects(Camera *cam, bool onlyShadowCasters)
{
        if (mRenderMethod == KdTree::KDRM_INTERNAL)
        {
                getRenderQueue()->clear(mDeleteQueueAfterRendering);
                if (mShowVisualization)
                {
                        PrepareVisualization(cam);
                }
                else
                {
                        mVisibleNodes.clear();
                        if (mKdTree)
                        {
                                // determine visibility
                                mKdTree->queueVisibleObjects(KDCAMPTR_CAST(cam), getRenderQueue(), onlyShadowCasters, mShowBoxes, mVisibleNodes);
                                // apply view cell pvs
                                updatePvs(cam);
                        }
                }
        }
        else
        {
                //-- show visible scene nodes and octree bounding boxes from last frame
                if (mShowVisualization)
                {
                        PrepareVisualization(cam);
                }
                else 
                {       
                        // for hierarchical culling, we interleave identification 
                        // and rendering of objects in _renderVisibibleObjects

                        // for the shadow pass we use only standard rendering
                        // because of low occlusion
                        if (mShadowTechnique == SHADOWTYPE_TEXTURE_MODULATIVE && 
                                mIlluminationStage == IRS_RENDER_TO_TEXTURE)
                        {
                                getRenderQueue()->clear();
                                if (mKdTree)
                                        mKdTree->queueVisibleObjects(KDCAMPTR_CAST(cam), getRenderQueue(), onlyShadowCasters, mShowBoxes, mVisibleNodes);
                        }

                        // only shadow casters will be rendered in shadow texture pass
                        if (0) mHierarchyInterface->SetOnlyShadowCasters(onlyShadowCasters);


                        //-- apply view cell pvs -
                        updatePvs(cam);
                }
                mVisibleNodes.clear();  
        }
}

void KdTreeSceneManager::_renderVisibleObjects()
{
        if (mRenderMethod == KdTree::KDRM_INTERNAL)
        {
                SceneManager::_renderVisibleObjects();
        }
        else
        {
                InitDepthPass();          // create material for depth pass
                InitItemBufferPass(); // create material for item buffer pass

                // save ambient light to reset later
                ColourValue savedAmbient = mAmbientLight;

                //-- apply standard rendering for some modes (e.g., visualization, shadow pass)

                if (mShowVisualization ||
                        (mShadowTechnique == SHADOWTYPE_TEXTURE_MODULATIVE && 
                        mIlluminationStage == IRS_RENDER_TO_TEXTURE))
                {       
                        IlluminationRenderStage savedStage = mIlluminationStage; 

                        if (mShowVisualization) 
                        {
                                // disable illumination stage to prevent rendering shadows
                                mIlluminationStage = IRS_NONE;
                        }

                        // standard rendering for shadow maps because of performance
                        SceneManager::_renderVisibleObjects();

                        mIlluminationStage = savedStage;
                }
                else //-- the hierarchical culling algorithm
                {
                        // this is also called in TerrainSceneManager: really necessary?
                        //mDestRenderSystem -> setLightingEnabled(false);

                        // don't render backgrounds for item buffer
                        if (mUseItemBuffer)
                        {
                                clearSpecialCaseRenderQueues();
                                getRenderQueue()->clear();
                        }

                        //-- hierarchical culling

                        // the objects of different layers (e.g., background, scene, 
                        // overlay) must be identified and rendered one after another

                        //-- render all early skies
                        clearSpecialCaseRenderQueues();
                        addSpecialCaseRenderQueue(RENDER_QUEUE_BACKGROUND);
                        addSpecialCaseRenderQueue(RENDER_QUEUE_SKIES_EARLY);
                        setSpecialCaseRenderQueueMode(SceneManager::SCRQM_INCLUDE);

                        SceneManager::_renderVisibleObjects();

#ifdef GTP_VISIBILITY_MODIFIED_OGRE
                        // delete previously rendered content
                        _deleteRenderedQueueGroups();
#endif

                        //-- prepare queue for visible objects (i.e., all but overlay and skies late)
                        clearSpecialCaseRenderQueues();
                        addSpecialCaseRenderQueue(RENDER_QUEUE_SKIES_LATE);
                        addSpecialCaseRenderQueue(RENDER_QUEUE_OVERLAY);

                        // exclude this queues from hierarchical rendering
                        setSpecialCaseRenderQueueMode(SceneManager::SCRQM_EXCLUDE);


                        // set all necessary parameters for 
                        // hierarchical visibility culling and rendering
                        InitVisibilityCulling(mCameraInProgress);


                        /** 
                        * the hierarchical culling algorithm
                        * for depth pass: we just find objects and update depth buffer
                        * for "delayed" rendering: we render some passes afterwards
                        * e.g., transparents, because they need front-to-back sorting
                        **/

                        mVisibilityManager->ApplyVisibilityCulling();

                        // delete remaining renderables from queue:
                        // all which are not in mLeavePassesInQueue
#ifdef GTP_VISIBILITY_MODIFIED_OGRE
                        _deleteRenderedQueueGroups(mLeavePassesInQueue);
#endif

                        //-- reset parameters
                        mIsDepthPassPhase = false;
                        mIsItemBufferPhase = false;
                        mSkipTransparents = false;
                        mIsHierarchicalCulling = false;

                        mLeavePassesInQueue = 0;

                        // add visible nodes found by the visibility culling algorithm
                        if (mUseDepthPass)
                        {
                                KdTree::NodeList::const_iterator it, end = mVisibleNodes.end();
                                for (it = mVisibleNodes.begin(); it != end; it++)
                                {
                                        (*it)->queueVisibleObjects(mHierarchyInterface->GetFrameId(), mCameraInProgress,
                                                getRenderQueue(), false, mShowBoxes);
                                }
                        }

                        //-- now we can render all remaining queue objects
                        //-- used for depth pass, transparents, overlay
                        clearSpecialCaseRenderQueues();

                        SceneManager::_renderVisibleObjects();
                } // hierarchical culling


                // reset ambient light
                setAmbientLight(savedAmbient);


                // almost same effect as below
                getRenderQueue()->clear(mDeleteQueueAfterRendering);

                //if (!mDeleteQueueAfterRendering)
                //      getRenderQueue()->clear(true); // finally clear render queue
                //else
                //      OGRE_DELETE(mRenderQueue); // HACK: should rather only be cleared ...

                if (0) WriteLog(); // write out stats
        }
}


void KdTreeSceneManager::_renderNode(KdTree::NodePtr node, Camera * cam, 
                                                                         bool onlyShadowCasters, int leavePassesInQueue)
{
        RenderQueueGroup *currentGroup = 
                getRenderQueue()->getQueueGroup(getRenderQueue()->getDefaultQueueGroup());
        currentGroup->clear(leavePassesInQueue);

        node->queueVisibleObjects(mHierarchyInterface->GetFrameId(), cam, getRenderQueue(),
                onlyShadowCasters, mShowBoxes);
        mVisibleNodes.push_back(node);

        _renderQueueGroupObjects(currentGroup, QueuedRenderableCollection::OM_PASS_GROUP);
}

//-----------------------------------------------------------------------
const Pass *KdTreeSceneManager::_setPass(const Pass* pass, bool evenIfSuppressed)
{
        if (mRenderMethod == KdTree::KDRM_INTERNAL)
        {
                return SceneManager::_setPass(pass);
        }

        // TODO: setting vertex program is not efficient
        //Pass *usedPass = ((mIsDepthPassPhase && !pass->hasVertexProgram()) ? mDepthPass : pass); 

        // set depth fill pass if we currently do not make an aabb occlusion query
        const bool useDepthPass = 
                (mIsDepthPassPhase && !mHierarchyInterface->IsBoundingBoxQuery());

        const IlluminationRenderStage savedStage = mIlluminationStage; 

        // set illumination stage to NONE so no shadow material is used 
        // for depth pass or for occlusion query
        if (mIsDepthPassPhase || mHierarchyInterface->IsBoundingBoxQuery())
        {
                mIlluminationStage = IRS_NONE;
        }

        // --- set vertex program of current pass in order to set correct depth
        if (mExecuteVertexProgramForAllPasses && 
                mIsDepthPassPhase && 
                pass->hasVertexProgram())
        {
                // add vertex program of current pass to depth pass
                mDepthPass->setVertexProgram(pass->getVertexProgramName());

                if (mDepthPass->hasVertexProgram())
                {
                        const GpuProgramPtr& prg = mDepthPass->getVertexProgram();
                        // Load this program if not done already
                        if (!prg->isLoaded())
                                prg->load();
                        // Copy params
                        mDepthPass->setVertexProgramParameters(pass->getVertexProgramParameters());
                }
        }
        else if (mDepthPass->hasVertexProgram()) // reset vertex program
        {
                mDepthPass->setVertexProgram("");
        }

        const Pass *usedPass = useDepthPass ? mDepthPass : pass;

        // save old depth write: needed for item buffer
        const bool IsDepthWrite = usedPass->getDepthWriteEnabled();

        // global option which enables / disables depth writes
        if (!mEnableDepthWrite)
        {
                //      usedPass->setDepthWriteEnabled(false);
        }
        //else if (mIsItemBufferPass) {usedPass = mItemBufferPass;}


        //-- set actual pass here
        const Pass *result = SceneManager::_setPass(usedPass);


        // reset depth write
        if (!mEnableDepthWrite)
        {
                //      usedPass->setDepthWriteEnabled(IsDepthWrite);
        }

        // reset illumination stage
        mIlluminationStage = savedStage;

        return result;
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderBasicQueueGroupObjects(RenderQueueGroup* pGroup,
                                                                                                          QueuedRenderableCollection::OrganisationMode om)
{
        // Basic render loop
        // Iterate through priorities
        RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

        while (groupIt.hasMoreElements())
        {
                RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

                // Sort the queue first
                pPriorityGrp->sort(mCameraInProgress);

                // Do solids
                renderObjects(pPriorityGrp->getSolidsBasic(), om, true);

                // for correct rendering, transparents must be rendered after hierarchical culling
                // => do nothing

                // Do transparents (always descending)
                if (mRenderMethod == KdTree::KDRM_INTERNAL || !mSkipTransparents)
                {
                        renderObjects(pPriorityGrp->getTransparents(), 
                                QueuedRenderableCollection::OM_SORT_DESCENDING, true);
                }


        }// for each priority
}
//-----------------------------------------------------------------------
bool KdTreeSceneManager::validatePassForRendering(Pass* pass)
{
        if (mRenderMethod == KdTree::KDRM_INTERNAL)
        {
                return SceneManager::validatePassForRendering(pass);
        }

        // skip all but first pass if we are doing the depth pass
        if ((mIsDepthPassPhase || mIsItemBufferPhase) && (pass->getIndex() > 0))
        {
                return false;
        }
        // all but first pass
        /*else if ((!mIsDepthPassPhase || mIsItemBufferPhase) && (pass->getIndex() != 0))
        {
        return false;
        }*/

        return SceneManager::validatePassForRendering(pass);
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::_renderQueueGroupObjects(RenderQueueGroup* pGroup, 
                                                                                                  QueuedRenderableCollection::OrganisationMode om)
{
        if (mRenderMethod == KdTree::KDRM_INTERNAL || !mIsItemBufferPhase)
        {
                SceneManager::_renderQueueGroupObjects(pGroup, om);
                return;
        }
#ifdef  ITEM_BUFFER
        //-- item buffer
        //-- item buffer: render objects using false colors

        // Iterate through priorities
        RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

        while (groupIt.hasMoreElements())
        {
                RenderItemBuffer(groupIt.getNext());
        }
#endif // ITEM_BUFFER
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderAdditiveStencilShadowedQueueGroupObjects(
        RenderQueueGroup* pGroup, QueuedRenderableCollection::OrganisationMode om)
{
        // only render solid passes during hierarchical culling
        if (mIsHierarchicalCulling)
        {
                RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();
                LightList lightList;

                while (groupIt.hasMoreElements())
                {
                        RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

                        // Sort the queue first
                        pPriorityGrp->sort(mCameraInProgress);

                        // Clear light list
                        lightList.clear();

                        // Render all the ambient passes first, no light iteration, no lights
                        /*** msz: no more IRS_AMBIENT, see OgreSceneManager.h ***/
                        // mIlluminationStage = IRS_AMBIENT;

                        SceneManager::renderObjects(pPriorityGrp->getSolidsBasic(), om, false, &lightList);
                        // Also render any objects which have receive shadows disabled
                        SceneManager::renderObjects(pPriorityGrp->getSolidsNoShadowReceive(), om, true);
                }
        }
        else // render the rest of the passes
        {
                SceneManager::renderAdditiveStencilShadowedQueueGroupObjects(pGroup, om);
        }
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::renderModulativeStencilShadowedQueueGroupObjects(
        RenderQueueGroup* pGroup, QueuedRenderableCollection::OrganisationMode om)
{
        if (mIsHierarchicalCulling)
        {
                // Iterate through priorities
                RenderQueueGroup::PriorityMapIterator groupIt = pGroup->getIterator();

                while (groupIt.hasMoreElements())
                {
                        RenderPriorityGroup* pPriorityGrp = groupIt.getNext();

                        // Sort the queue first
                        pPriorityGrp->sort(mCameraInProgress);

                        // Do (shadowable) solids
                        SceneManager::renderObjects(pPriorityGrp->getSolidsBasic(), om, true);
                }
        }
        else
        {
                SceneManager::renderModulativeStencilShadowedQueueGroupObjects(pGroup, om);
        }
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitDepthPass()
{
        MaterialPtr depthMat = MaterialManager::getSingleton().getByName("Visibility/DepthPass");

        if (depthMat.isNull())
        {
                depthMat = MaterialManager::getSingleton().create(
                        "Visibility/DepthPass",
                        ResourceGroupManager::DEFAULT_RESOURCE_GROUP_NAME);

                mDepthPass = depthMat->getTechnique(0)->getPass(0);
                mDepthPass->setColourWriteEnabled(false);
                mDepthPass->setDepthWriteEnabled(true);
                mDepthPass->setLightingEnabled(false);
        }
        else
        {
                mDepthPass = depthMat->getTechnique(0)->getPass(0);
        }
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitItemBufferPass()
{
        MaterialPtr itemBufferMat = MaterialManager::getSingleton().
                getByName("Visibility/ItemBufferPass");

        if (itemBufferMat.isNull())
        {
                // Init
                itemBufferMat = MaterialManager::getSingleton().create("Visibility/ItemBufferPass",
                        ResourceGroupManager::DEFAULT_RESOURCE_GROUP_NAME);

                mItemBufferPass = itemBufferMat->getTechnique(0)->getPass(0);
                mItemBufferPass->setColourWriteEnabled(true);
                mItemBufferPass->setDepthWriteEnabled(true);
                mItemBufferPass->setLightingEnabled(true);
                //mItemBufferPass->setLightingEnabled(false);
        }
        else
        {
                mItemBufferPass = itemBufferMat->getTechnique(0)->getPass(0);
        }
        //mItemBufferPass->setAmbient(1, 1, 0);
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::PrepareVisualization(Camera *cam)
{
        // add player camera for visualization purpose
        try 
        {
                Camera *c;
                if ((c = getCamera("PlayerCam")) != NULL)
                {
                        getRenderQueue()->addRenderable(c);
                }   
        }
        catch (...)
        {
                // ignore
        }

        if (mRenderNodesForViz || mRenderNodesContentForViz)
        {
                RenderQueue * queue = getRenderQueue();
                unsigned long frameid = 0;

                if (mRenderMethod == KdTree::KDRM_INTERNAL)
                        frameid = Root::getSingleton().getCurrentFrameNumber();
                else
                        frameid = mHierarchyInterface->GetFrameId();

                for (KdTree::NodeList::iterator it = mVisibleNodes.begin(); it != mVisibleNodes.end(); ++it)
                {
                        if (mRenderNodesForViz && (*it)->isLeaf())
                        {
                                WireBoundingBox * wirebox = (*it)->getWireBoundingBox();
                                wirebox->setMaterial("KdTree/BoxViz");
                                getRenderQueue()->addRenderable(wirebox);
                        }
                        // add renderables itself
                        if (mRenderNodesContentForViz) 
                        {
                                (*it)->queueVisibleObjects(frameid, cam, queue, false, false);
                        }
                }
        }       
}
//-----------------------------------------------------------------------
void KdTreeSceneManager::InitVisibilityCulling(Camera *cam)
{
        // reset culling manager stats
        mVisibilityManager->GetCullingManager()->InitFrame(mVisualizeCulledNodes);

        // set depth pass flag before rendering
        mIsDepthPassPhase = mUseDepthPass;

        mIsHierarchicalCulling = true; // during hierarchical culling

        // item buffer needs full ambient lighting to use item colors as unique id
        if (mUseItemBuffer) 
        {
                mIsItemBufferPhase = true;
                setAmbientLight(ColourValue(1,1,1,1));
        }


        // set passes which are stored in render queue 
        // for rendering AFTER hierarchical culling, i.e., passes which need 
        // a special rendering order

        mLeavePassesInQueue = 0;

        // if we have the depth pass or use an item buffer, no passes are left in the queue
        if (1 && !mUseDepthPass && !mUseItemBuffer)
        {
                if (mShadowTechnique == SHADOWTYPE_STENCIL_ADDITIVE)
                {
                        // TODO: remove this pass because it should be processed during hierarchical culling
                        //mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_NOSHADOW;

                        mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_DECAL;
                        mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_DIFFUSE_SPECULAR;
                        mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;

                        // just render ambient passes
                        /*** msz: no more IRS_AMBIENT, see OgreSceneManager.h ***/
                        // mIlluminationStage = IRS_AMBIENT; 
                        //getRenderQueue()->setSplitPassesByLightingType(true);
                }

                if (mShadowTechnique == SHADOWTYPE_STENCIL_MODULATIVE)
                {
                        mLeavePassesInQueue |= RenderPriorityGroup::SOLID_PASSES_NOSHADOW;
                        mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;
                }

                // transparents should be rendered after hierarchical culling to 
                // provide front-to-back ordering
                if (mDelayRenderTransparents)
                {
                        mLeavePassesInQueue |= RenderPriorityGroup::TRANSPARENT_PASSES;
                }
        }

        // skip rendering transparents during the hierarchical culling
        // (because they will be rendered afterwards)
        mSkipTransparents = 
                (mIsDepthPassPhase || (mLeavePassesInQueue & RenderPriorityGroup::TRANSPARENT_PASSES));

        // -- initialise interface for rendering traversal of the hierarchy
        mHierarchyInterface->SetHierarchyRoot(mKdTree->getRoot());

        // possible two cameras (one for culling, one for rendering)
        mHierarchyInterface->InitTraversal(mCameraInProgress, 
                /*mCullCamera ? getCamera("CullCamera") : */NULL,
                mLeavePassesInQueue);

}

//-------------------------------------------------------------------------
void KdTreeSceneManager::SetObjectsVisible(const bool visible)
{
        GtpVisibilityPreprocessor::ObjectContainer::iterator it, it_end = mObjects.end();

        for (it = mObjects.begin(); it != it_end; ++ it)
        {
                OgreMeshInstance *omi = static_cast<OgreMeshInstance *>(*it);
                Entity *ent = omi->GetEntity();

                ent->setVisible(visible);
        }
}
//-----------------------------------------------------------------------
bool KdTreeSceneManager::LoadViewCells(const String &filename)
{
        // objects are set to invisible initially
        SetObjectsVisible(false);

        const string bboxesFilename = mVisibilityManager->GetVisibilityEnvironment()->getViewCellsFileName();

        // converter between view cell ids and Ogre entites 
        GtpVisibilityPreprocessor::IndexedBoundingBoxContainer iboxes;
        KdTreeBoundingBoxConverter bconverter(this);

        // load the view cells assigning the found objects to the pvss
        mViewCellsManager = 
                GtpVisibilityPreprocessor::ViewCellsManager::
                        LoadViewCells(filename, mObjects, false, &bconverter);

        return (mViewCellsManager != NULL);
}
//-------------------------------------------------------------------------
void KdTreeSceneManager::applyViewCellPvs(GtpVisibilityPreprocessor::ViewCell *vc, 
                                                                                                        const bool load)
{       
        if (!vc) 
        {       
                // set everything visible for savety

                // NOTE: should not happen, rather apply view cell 
                // representing unbounded space then
                SetObjectsVisible(true);

                return;
        }

        //////////
        //-- set PVS of view cell visible

        GtpVisibilityPreprocessor::ObjectPvsIterator pit = vc->GetPvs().GetIterator();

        while (pit.HasMoreEntries())
        {               
                GtpVisibilityPreprocessor::Intersectable *entry = pit.Next();

                if (entry)
                {
                        OgreMeshInstance *omi = static_cast<OgreMeshInstance *>(entry);
                        omi->GetEntity()->setVisible(load);
                }
        }
}
//-------------------------------------------------------------------------
void KdTreeSceneManager::updatePvs(Camera *cam)
{
        if (!(mViewCellsLoaded && mUseViewCells))
                return;

        const GtpVisibilityPreprocessor::Vector3 viewPoint = 
                OgreTypeConverter::ConvertFromOgre(cam->getDerivedPosition());

        GtpVisibilityPreprocessor::ViewCell *newElementary = 
                mViewCellsManager->GetViewCell(viewPoint);

        // elementary view cell did not change => apply same pvs
        if (mElementaryViewCell == newElementary)
                return;

        mElementaryViewCell = newElementary;
        //LogManager::getSingleton().logMessage("unloading");
        //-- unload old pvs
        applyViewCellPvs(mCurrentViewCell, false);


        //-- the new view cell

        GtpVisibilityPreprocessor::ViewCell *viewCell;


        if (mUseVisibilityFilter)
        {
                //-- compute new filtered cell
                GtpVisibilityPreprocessor::PrVs prvs;
                mViewCellsManager->GetPrVS(viewPoint, prvs, 5);
                viewCell = prvs.mViewCell;
        }
        else
        {
                viewCell = newElementary;
        }
        //LogManager::getSingleton().logMessage("loading");
        //-- load new pvs
        applyViewCellPvs(viewCell, true);

        // store pvs
        mCurrentViewCell->SetPvs(viewCell->GetPvs());

        // delete merge tree of filtered view cell
        if (mUseVisibilityFilter)
                mViewCellsManager->DeleteLocalMergeTree(viewCell);
}

//-----------------------------------------------------------------------
void KdTreeSceneManager::WriteLog()
{
        std::stringstream d;

        d << "Depth pass: " << StringConverter::toString(mUseDepthPass) << ", "
                << "Delay transparents: " << StringConverter::toString(mDelayRenderTransparents) << ", "
                << "Use optimization: " << StringConverter::toString(mHierarchyInterface->GetTestGeometryForVisibleLeaves()) << ", "
                << "Algorithm type: " << mVisibilityManager->GetCullingManagerType() << ", "
                << "Hierarchy nodes: " << (mKdTree ? mKdTree->getTreeStats().mNumNodes : 0) << ", " 
                << "Traversed nodes: " << mHierarchyInterface->GetNumTraversedNodes() << ", "
                << "Rendered nodes: " << mHierarchyInterface->GetNumRenderedNodes() << ", "
                << "Query culled nodes: " << mVisibilityManager->GetCullingManager()->GetNumQueryCulledNodes() << ", "
                << "Frustum culled nodes: " << mVisibilityManager->GetCullingManager()->GetNumFrustumCulledNodes() << ", "
                << "Queries issued: " << mVisibilityManager->GetCullingManager()->GetNumQueriesIssued() << ", "
                << "Found objects: " << (int)mVisibleNodes.size() << "\n"
                ;

        LogManager::getSingleton().logMessage(d.str());
}

/************************************************************************/
/* Factory for KdTreeSceneManager                                       */
/************************************************************************/
//-----------------------------------------------------------------------
//-----------------------------------------------------------------------
const String KdTreeSceneManagerFactory::FACTORY_TYPE_NAME = "KdTreeSceneManager";
//-----------------------------------------------------------------------
void KdTreeSceneManagerFactory::initMetaData(void) const
{
        mMetaData.typeName = FACTORY_TYPE_NAME;
        mMetaData.description = "Scene manager that organises the scene based on a kd-tree";
        mMetaData.sceneTypeMask = 0xFFFF; // support all types of scenes (hopefully)
        mMetaData.worldGeometrySupported = false;
}
//-----------------------------------------------------------------------
SceneManager* KdTreeSceneManagerFactory::createInstance(
        const String& instanceName)
{
        return new KdTreeSceneManager(instanceName, visManager);
}
//-----------------------------------------------------------------------
void KdTreeSceneManagerFactory::destroyInstance(SceneManager* instance)
{
        delete instance;
}

} // namespace Ogre