/src/ogre/PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp

Source
/*
-----------------------------------------------------------------------------
This source file is part of OGRE
(Object-oriented Graphics Rendering Engine)
For the latest info, see http://www.ogre3d.org/

Copyright (c) 2000-2014 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.
-----------------------------------------------------------------------------
*/
/***************************************************************************
octreescenemanager.cpp  -  description
-------------------
begin                : Fri Sep 27 2002
copyright            : (C) 2002 by Jon Anderson
email                : janders@users.sf.net
  
***************************************************************************/

#include "OgreOctreeSceneManager.h"
#include "OgreOctreeSceneQuery.h"
#include "OgreOctreeNode.h"
#include "OgreOctreeCamera.h"
#include "OgreWireBoundingBox.h"

namespace Ogre
{
enum Intersection
{
    OUTSIDE=0,
    INSIDE=1,
    INTERSECT=2
};
int OctreeSceneManager::intersect_call = 0;

static Intersection intersect( const Ray &one, const AxisAlignedBox &two )
{
    OctreeSceneManager::intersect_call++;
    // Null box?
    if (two.isNull()) return OUTSIDE;
    // Infinite box?
    if (two.isInfinite()) return INTERSECT;

    bool inside = true;
    const Vector3& twoMin = two.getMinimum();
    const Vector3& twoMax = two.getMaximum();
    Vector3 origin = one.getOrigin();
    Vector3 dir = one.getDirection();

    Vector3 maxT(-1, -1, -1);

    int i = 0;
    for(i=0; i<3; i++ )
    {
        if( origin[i] < twoMin[i] )
        {
            inside = false;
            if( dir[i] > 0 )
            {
                maxT[i] = (twoMin[i] - origin[i])/ dir[i];
            }
        }
        else if( origin[i] > twoMax[i] )
        {
            inside = false;
            if( dir[i] < 0 )
            {
                maxT[i] = (twoMax[i] - origin[i]) / dir[i];
            }
        }
    }

    if( inside )
    {
        return INTERSECT;
    }
    int whichPlane = 0;
    if( maxT[1] > maxT[whichPlane])
        whichPlane = 1;
    if( maxT[2] > maxT[whichPlane])
        whichPlane = 2;

    if( ((int)maxT[whichPlane]) & 0x80000000 )
    {
        return OUTSIDE;
    }
    for(i=0; i<3; i++ )
    {
        if( i!= whichPlane )
        {
            float f = origin[i] + maxT[whichPlane] * dir[i];
            if ( f < (twoMin[i] - 0.00001f) ||
                    f > (twoMax[i] +0.00001f ) )
            {
                return OUTSIDE;
            }
        }
    }

    return INTERSECT;

}


/** Checks how the second box intersects with the first.
*/
static Intersection intersect( const PlaneBoundedVolume &one, const AxisAlignedBox &two )
{
    OctreeSceneManager::intersect_call++;
    // Null box?
    if (two.isNull()) return OUTSIDE;
    // Infinite box?
    if (two.isInfinite()) return INTERSECT;

    // Get centre of the box
    Vector3 centre = two.getCenter();
    // Get the half-size of the box
    Vector3 halfSize = two.getHalfSize();

    // For each plane, see if all points are on the negative side
    // If so, object is not visible.
    // If one or more are, it's partial.
    // If all aren't, full
    bool all_inside = true;
    PlaneList::const_iterator i, iend;
    iend = one.planes.end();
    for (i = one.planes.begin(); i != iend; ++i)
    {
        const Plane& plane = *i;

        Plane::Side side = plane.getSide(centre, halfSize);
        if(side == one.outside)
                return OUTSIDE;
        if(side == Plane::BOTH_SIDE)
                all_inside = false; 
    }

    if ( all_inside )
        return INSIDE;
    else
        return INTERSECT;

}


/** Checks how the second box intersects with the first.
*/
static Intersection intersect( const AxisAlignedBox &one, const AxisAlignedBox &two )
{
    OctreeSceneManager::intersect_call++;
    // Null box?
    if (one.isNull() || two.isNull()) return OUTSIDE;
    if (one.isInfinite()) return INSIDE;
    if (two.isInfinite()) return INTERSECT;


    const Vector3& insideMin = two.getMinimum();
    const Vector3& insideMax = two.getMaximum();

    const Vector3& outsideMin = one.getMinimum();
    const Vector3& outsideMax = one.getMaximum();

    if (    insideMax.x < outsideMin.x ||
            insideMax.y < outsideMin.y ||
            insideMax.z < outsideMin.z ||
            insideMin.x > outsideMax.x ||
            insideMin.y > outsideMax.y ||
            insideMin.z > outsideMax.z )
    {
        return OUTSIDE;
    }

    bool full = ( insideMin.x > outsideMin.x &&
                  insideMin.y > outsideMin.y &&
                  insideMin.z > outsideMin.z &&
                  insideMax.x < outsideMax.x &&
                  insideMax.y < outsideMax.y &&
                  insideMax.z < outsideMax.z );

    if ( full )
        return INSIDE;
    else
        return INTERSECT;

}

/** Checks how the box intersects with the sphere.
*/
static Intersection intersect( const Sphere &one, const AxisAlignedBox &two )
{
    OctreeSceneManager::intersect_call++;
    // Null box?
    if (two.isNull()) return OUTSIDE;
    if (two.isInfinite()) return INTERSECT;

    float sradius = one.getRadius();

    sradius *= sradius;

    Vector3 scenter = one.getCenter();

    const Vector3& twoMin = two.getMinimum();
    const Vector3& twoMax = two.getMaximum();

    float s, d = 0;

    Vector3 mndistance = ( twoMin - scenter );
    Vector3 mxdistance = ( twoMax - scenter );

    if ( mndistance.squaredLength() < sradius &&
            mxdistance.squaredLength() < sradius )
    {
        return INSIDE;
    }

    //find the square of the distance
    //from the sphere to the box
    for ( int i = 0 ; i < 3 ; i++ )
    {
        if ( scenter[ i ] < twoMin[ i ] )
        {
            s = scenter[ i ] - twoMin[ i ];
            d += s * s;
        }

        else if ( scenter[ i ] > twoMax[ i ] )
        {
            s = scenter[ i ] - twoMax[ i ];
            d += s * s;
        }

    }

    bool partial = ( d <= sradius );

    if ( !partial )
    {
        return OUTSIDE;
    }

    else
    {
        return INTERSECT;
    }


}

unsigned long white = 0xFFFFFFFF;

unsigned short OctreeSceneManager::mIndexes[ 24 ] = {0, 1, 1, 2, 2, 3, 3, 0,       //back
        0, 6, 6, 5, 5, 1,             //left
        3, 7, 7, 4, 4, 2,             //right
        6, 7, 5, 4 };          //front
unsigned long OctreeSceneManager::mColors[ 8 ] = {white, white, white, white, white, white, white, white };


OctreeSceneManager::OctreeSceneManager(const String& name) : SceneManager(name)
{
    AxisAlignedBox b( -10000, -10000, -10000, 10000, 10000, 10000 );
    int depth = 8; 
    mOctree = 0;
    init( b, depth );
}

OctreeSceneManager::OctreeSceneManager(const String& name, AxisAlignedBox &box, int max_depth ) 
: SceneManager(name)
{
    mOctree = 0;
    init( box, max_depth );
}

const String& OctreeSceneManager::getTypeName(void) const
{
    return OctreeSceneManagerFactory::FACTORY_TYPE_NAME;
}

void OctreeSceneManager::init( AxisAlignedBox &box, int depth )
{

    if ( mOctree != 0 )
        OGRE_DELETE mOctree;

    mOctree = OGRE_NEW Octree( 0 );

    mMaxDepth = depth;
    mBox = box;

    mOctree -> mBox = box;

    Vector3 min = box.getMinimum();

    Vector3 max = box.getMaximum();

    mOctree -> mHalfSize = ( max - min ) / 2;


    mShowBoxes = false;

    mNumObjects = 0;

    Vector3 v( 1.5, 1.5, 1.5 );

    mScaleFactor.setScale( v );



    // setDisplaySceneNodes( true );
    // setShowBoxes( true );

    //
    //mSceneRoot isn't put into the octree since it has no volume.

}

OctreeSceneManager::~OctreeSceneManager()
{

    if ( mOctree )
    {
        OGRE_DELETE mOctree;
        mOctree = 0;
    }
}

Camera * OctreeSceneManager::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",
            "OctreeSceneManager::createCamera" );
    }

    Camera * c = OGRE_NEW OctreeCamera( name, this );
    mCameras.emplace(name, c);

    // create visible bounds aab map entry
    mCamVisibleObjectsMap[c] = VisibleObjectsBoundsInfo();
    
    return c;
}

void OctreeSceneManager::destroySceneNode( SceneNode* sn )
{
    OctreeNode * on = static_cast < OctreeNode* > ( sn );

    if ( on != 0 )
        _removeOctreeNode( on );

    SceneManager::destroySceneNode( sn );
}

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

bool OctreeSceneManager::getOptionKeys( StringVector & refKeys )
{
    SceneManager::getOptionKeys( refKeys );
    refKeys.push_back( "Size" );
    refKeys.push_back( "ShowOctree" );
    refKeys.push_back( "Depth" );

    return true;
}


void OctreeSceneManager::_updateOctreeNode( OctreeNode * onode )
{
    const AxisAlignedBox& box = onode -> _getWorldAABB();

    if ( box.isNull() )
        return ;

    // Skip if octree has been destroyed (shutdown conditions)
    if (!mOctree)
        return;

    if ( onode -> getOctant() == 0 )
    {
        //if outside the octree, force into the root node.
        if ( ! onode -> _isIn( mOctree -> mBox ) )
            mOctree->_addNode( onode );
        else
            _addOctreeNode( onode, mOctree );
        return ;
    }

    if ( ! onode -> _isIn( onode -> getOctant() -> mBox ) )
    {
        _removeOctreeNode( onode );

        //if outside the octree, force into the root node.
        if ( ! onode -> _isIn( mOctree -> mBox ) )
            mOctree->_addNode( onode );
        else
            _addOctreeNode( onode, mOctree );
    }
}

/** Only removes the node from the octree.  It leaves the octree, even if it's empty.
*/
void OctreeSceneManager::_removeOctreeNode( OctreeNode * n )
{
    // Skip if octree has been destroyed (shutdown conditions)
    if (!mOctree)
        return;

    Octree * oct = n -> getOctant();

    if ( oct )
    {
        oct -> _removeNode( n );
    }

    n->setOctant(0);
}


void OctreeSceneManager::_addOctreeNode( OctreeNode * n, Octree *octant, int depth )
{

    // Skip if octree has been destroyed (shutdown conditions)
    if (!mOctree)
        return;

    const AxisAlignedBox& bx = n -> _getWorldAABB();


    //if the octree is twice as big as the scene node,
    //we will add it to a child.
    if ( ( depth < mMaxDepth ) && octant -> _isTwiceSize( bx ) )
    {
        int x, y, z;
        octant -> _getChildIndexes( bx, &x, &y, &z );

        if ( octant -> mChildren[ x ][ y ][ z ] == 0 )
        {
            octant -> mChildren[ x ][ y ][ z ] = OGRE_NEW Octree( octant );
            const Vector3& octantMin = octant -> mBox.getMinimum();
            const Vector3& octantMax = octant -> mBox.getMaximum();
            Vector3 min, max;

            if ( x == 0 )
            {
                min.x = octantMin.x;
                max.x = ( octantMin.x + octantMax.x ) / 2;
            }

            else
            {
                min.x = ( octantMin.x + octantMax.x ) / 2;
                max.x = octantMax.x;
            }

            if ( y == 0 )
            {
                min.y = octantMin.y;
                max.y = ( octantMin.y + octantMax.y ) / 2;
            }

            else
            {
                min.y = ( octantMin.y + octantMax.y ) / 2;
                max.y = octantMax.y;
            }

            if ( z == 0 )
            {
                min.z = octantMin.z;
                max.z = ( octantMin.z + octantMax.z ) / 2;
            }

            else
            {
                min.z = ( octantMin.z + octantMax.z ) / 2;
                max.z = octantMax.z;
            }

            octant -> mChildren[ x ][ y ][ z ] -> mBox.setExtents( min, max );
            octant -> mChildren[ x ][ y ][ z ] -> mHalfSize = ( max - min ) / 2;
        }

        _addOctreeNode( n, octant -> mChildren[ x ][ y ][ z ], ++depth );

    }

    else
    {
        octant -> _addNode( n );
    }
}


SceneNode * OctreeSceneManager::createSceneNodeImpl( void )
{
    return OGRE_NEW OctreeNode( this );
}

SceneNode * OctreeSceneManager::createSceneNodeImpl( const String &name )
{
    return OGRE_NEW OctreeNode( this, name );
}

void OctreeSceneManager::_updateSceneGraph( Camera * cam )
{
    SceneManager::_updateSceneGraph( cam );
}

void OctreeSceneManager::_findVisibleObjects(Camera * cam, 
    VisibleObjectsBoundsInfo* visibleBounds, bool onlyShadowCasters )
{

    getRenderQueue()->clear();
    mBoxes.clear();
    mVisible.clear();

    mNumObjects = 0;

    //walk the octree, adding all visible Octreenodes nodes to the render queue.
    walkOctree( static_cast < OctreeCamera * > ( cam ), getRenderQueue(), mOctree, 
                visibleBounds, false, onlyShadowCasters );

    // Show the octree boxes & cull camera if required
    if ( mShowBoxes )
    {
        for ( BoxList::iterator it = mBoxes.begin(); it != mBoxes.end(); ++it )
        {
            getRenderQueue()->addRenderable(*it);
        }
    }
}

void OctreeSceneManager::walkOctree( OctreeCamera *camera, RenderQueue *queue, 
    Octree *octant, VisibleObjectsBoundsInfo* visibleBounds, 
    bool foundvisible, bool onlyShadowCasters )
{

    //return immediately if nothing is in the node.
    if ( octant -> numNodes() == 0 )
        return ;

    OctreeCamera::Visibility v = OctreeCamera::NONE;

    if ( foundvisible )
    {
        v = OctreeCamera::FULL;
    }

    else if ( octant == mOctree )
    {
        v = OctreeCamera::PARTIAL;
    }

    else
    {
        AxisAlignedBox box;
        octant -> _getCullBounds( &box );
        v = camera -> getVisibility( box );
    }


    // if the octant is visible, or if it's the root node...
    if ( v != OctreeCamera::NONE )
    {

        //Add stuff to be rendered;
        Octree::NodeList::iterator it = octant -> mNodes.begin();

        if ( mShowBoxes )
        {
            mBoxes.push_back( octant->getWireBoundingBox() );
        }

        bool vis = true;

        while ( it != octant -> mNodes.end() )
        {
            OctreeNode * sn = *it;

            // if this octree is partially visible, manually cull all
            // scene nodes attached directly to this level.

            if ( v == OctreeCamera::PARTIAL )
                vis = camera -> isVisible( sn -> _getWorldAABB() );

            if ( vis )
            {

                mNumObjects++;
                sn -> _addToRenderQueue(camera, queue, onlyShadowCasters, visibleBounds );

                mVisible.push_back( sn );

                if (getDebugDrawer())
                    getDebugDrawer()->drawSceneNode(sn);
            }

            ++it;
        }

        Octree* child;
        bool childfoundvisible = (v == OctreeCamera::FULL);
        if ( (child = octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

        if ( (child = octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
            walkOctree( camera, queue, child, visibleBounds, childfoundvisible, onlyShadowCasters );

    }

}

// --- non template versions
static void _findNodes( const AxisAlignedBox &t, std::list< SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
{

    if ( !full )
    {
        AxisAlignedBox obox;
        octant -> _getCullBounds( &obox );

        Intersection isect = intersect( t, obox );

        if ( isect == OUTSIDE )
            return ;

        full = ( isect == INSIDE );
    }


    Octree::NodeList::iterator it = octant -> mNodes.begin();

    while ( it != octant -> mNodes.end() )
    {
        OctreeNode * on = ( *it );

        if ( on != exclude )
        {
            if ( full )
            {
                list.push_back( on );
            }

            else
            {
                Intersection nsect = intersect( t, on -> _getWorldAABB() );

                if ( nsect != OUTSIDE )
                {
                    list.push_back( on );
                }
            }

        }

        ++it;
    }

    Octree* child;

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

}

static void _findNodes( const Sphere &t, std::list< SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
{

    if ( !full )
    {
        AxisAlignedBox obox;
        octant -> _getCullBounds( &obox );

        Intersection isect = intersect( t, obox );

        if ( isect == OUTSIDE )
            return ;

        full = ( isect == INSIDE );
    }


    Octree::NodeList::iterator it = octant -> mNodes.begin();

    while ( it != octant -> mNodes.end() )
    {
        OctreeNode * on = ( *it );

        if ( on != exclude )
        {
            if ( full )
            {
                list.push_back( on );
            }

            else
            {
                Intersection nsect = intersect( t, on -> _getWorldAABB() );

                if ( nsect != OUTSIDE )
                {
                    list.push_back( on );
                }
            }

        }

        ++it;
    }

    Octree* child;

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

}


static void _findNodes( const PlaneBoundedVolume &t, std::list< SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
{

    if ( !full )
    {
        AxisAlignedBox obox;
        octant -> _getCullBounds( &obox );

        Intersection isect = intersect( t, obox );

        if ( isect == OUTSIDE )
            return ;

        full = ( isect == INSIDE );
    }


    Octree::NodeList::iterator it = octant -> mNodes.begin();

    while ( it != octant -> mNodes.end() )
    {
        OctreeNode * on = ( *it );

        if ( on != exclude )
        {
            if ( full )
            {
                list.push_back( on );
            }

            else
            {
                Intersection nsect = intersect( t, on -> _getWorldAABB() );

                if ( nsect != OUTSIDE )
                {
                    list.push_back( on );
                }
            }

        }

        ++it;
    }

    Octree* child;

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

}

static void _findNodes( const Ray &t, std::list< SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
{

    if ( !full )
    {
        AxisAlignedBox obox;
        octant -> _getCullBounds( &obox );

        Intersection isect = intersect( t, obox );

        if ( isect == OUTSIDE )
            return ;

        full = ( isect == INSIDE );
    }


    Octree::NodeList::iterator it = octant -> mNodes.begin();

    while ( it != octant -> mNodes.end() )
    {
        OctreeNode * on = ( *it );

        if ( on != exclude )
        {
            if ( full )
            {
                list.push_back( on );
            }

            else
            {
                Intersection nsect = intersect( t, on -> _getWorldAABB() );

                if ( nsect != OUTSIDE )
                {
                    list.push_back( on );
                }
            }

        }

        ++it;
    }

    Octree* child;

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

    if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
        _findNodes( t, list, exclude, full, child );

}

void OctreeSceneManager::findNodesIn( const AxisAlignedBox &box, std::list< SceneNode * > &list, SceneNode *exclude )
{
    _findNodes( box, list, exclude, false, mOctree );
}

void OctreeSceneManager::findNodesIn( const Sphere &sphere, std::list< SceneNode * > &list, SceneNode *exclude )
{
    _findNodes( sphere, list, exclude, false, mOctree );
}

void OctreeSceneManager::findNodesIn( const PlaneBoundedVolume &volume, std::list< SceneNode * > &list, SceneNode *exclude )
{
    _findNodes( volume, list, exclude, false, mOctree );
}

void OctreeSceneManager::findNodesIn( const Ray &r, std::list< SceneNode * > &list, SceneNode *exclude )
{
    _findNodes( r, list, exclude, false, mOctree );
}

void OctreeSceneManager::resize( const AxisAlignedBox &box )
{
    std::list< SceneNode * > nodes;
    std::list< SceneNode * > ::iterator it;

    _findNodes( mOctree->mBox, nodes, 0, true, mOctree );

    OGRE_DELETE mOctree;

    mOctree = OGRE_NEW Octree( 0 );
    mOctree->mBox = box;

    const Vector3 &min = box.getMinimum();
    const Vector3 &max = box.getMaximum();
    mOctree->mHalfSize = ( max - min ) * 0.5f;

    it = nodes.begin();

    while ( it != nodes.end() )
    {
        OctreeNode * on = static_cast < OctreeNode * > ( *it );
        on -> setOctant( 0 );
        _updateOctreeNode( on );
        ++it;
    }

}

bool OctreeSceneManager::setOption( const String & key, const void * val )
{
    if ( key == "Size" )
    {
        resize( * static_cast < const AxisAlignedBox * > ( val ) );
        return true;
    }

    else if ( key == "Depth" )
    {
        mMaxDepth = * static_cast < const int * > ( val );
        // copy the box since resize will delete mOctree and reference won't work
        AxisAlignedBox box = mOctree->mBox;
        resize(box);
        return true;
    }

    else if ( key == "ShowOctree" )
    {
        mShowBoxes = * static_cast < const bool * > ( val );
        return true;
    }


    return SceneManager::setOption( key, val );


}

bool OctreeSceneManager::getOption( const String & key, void *val )
{
    if ( key == "Size" )
    {
        AxisAlignedBox * b = static_cast < AxisAlignedBox * > ( val );
        b -> setExtents( mOctree->mBox.getMinimum(), mOctree->mBox.getMaximum() );
        return true;
    }

    else if ( key == "Depth" )
    {
        * static_cast < int * > ( val ) = mMaxDepth;
        return true;
    }

    else if ( key == "ShowOctree" )
    {

        * static_cast < bool * > ( val ) = mShowBoxes;
        return true;
    }


    return SceneManager::getOption( key, val );

}

void OctreeSceneManager::clearScene(void)
{
    SceneManager::clearScene();
    init(mBox, mMaxDepth);

}

//---------------------------------------------------------------------
AxisAlignedBoxSceneQuery*
OctreeSceneManager::createAABBQuery(const AxisAlignedBox& box, uint32 mask)
{
    OctreeAxisAlignedBoxSceneQuery* q = OGRE_NEW OctreeAxisAlignedBoxSceneQuery(this);
    q->setBox(box);
    q->setQueryMask(mask);
    return q;
}
//---------------------------------------------------------------------
SphereSceneQuery*
OctreeSceneManager::createSphereQuery(const Sphere& sphere, uint32 mask)
{
    OctreeSphereSceneQuery* q = OGRE_NEW OctreeSphereSceneQuery(this);
    q->setSphere(sphere);
    q->setQueryMask(mask);
    return q;
}
//---------------------------------------------------------------------
PlaneBoundedVolumeListSceneQuery*
OctreeSceneManager::createPlaneBoundedVolumeQuery(const PlaneBoundedVolumeList& volumes,
        uint32 mask)
{
    OctreePlaneBoundedVolumeListSceneQuery* q = OGRE_NEW OctreePlaneBoundedVolumeListSceneQuery(this);
    q->setVolumes(volumes);
    q->setQueryMask(mask);
    return q;
}

//---------------------------------------------------------------------
RaySceneQuery*
OctreeSceneManager::createRayQuery(const Ray& ray, uint32 mask)
{
    OctreeRaySceneQuery* q = OGRE_NEW OctreeRaySceneQuery(this);
    q->setRay(ray);
    q->setQueryMask(mask);
    return q;
}
//---------------------------------------------------------------------
IntersectionSceneQuery*
OctreeSceneManager::createIntersectionQuery(uint32 mask)
{

    // Octree implementation performs WORSE for < 500 objects
    // TODO: optimise it so it's better in all cases
    //OctreeIntersectionSceneQuery* q = OGRE_NEW OctreeIntersectionSceneQuery(this);
    DefaultIntersectionSceneQuery* q = OGRE_NEW DefaultIntersectionSceneQuery(this);
    q->setQueryMask(mask);
    return q;
}
//-----------------------------------------------------------------------
const String OctreeSceneManagerFactory::FACTORY_TYPE_NAME = "OctreeSceneManager";
//-----------------------------------------------------------------------
SceneManager* OctreeSceneManagerFactory::createInstance(
    const String& instanceName)
{
    return OGRE_NEW OctreeSceneManager(instanceName);
}

}

Coverage Report

Created: 2026-02-26 07:02