source: OGRE/trunk/ogrenew/PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp @ 692

Revision 692, 30.8 KB checked in by mattausch, 19 years ago (diff)

adding ogre 1.2 and dependencies

RevLine 
[692]1/*
2-----------------------------------------------------------------------------
3This source file is part of OGRE
4(Object-oriented Graphics Rendering Engine)
5For the latest info, see http://www.ogre3d.org/
6
7Copyright (c) 2000-2005 The OGRE Team
8Also see acknowledgements in Readme.html
9
10This program is free software; you can redistribute it and/or modify it under
11the terms of the GNU Lesser General Public License as published by the Free Software
12Foundation; either version 2 of the License, or (at your option) any later
13version.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
18
19You should have received a copy of the GNU Lesser General Public License along with
20this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21Place - Suite 330, Boston, MA 02111-1307, USA, or go to
22http://www.gnu.org/copyleft/lesser.txt.
23-----------------------------------------------------------------------------
24*/
25/***************************************************************************
26octreescenemanager.cpp  -  description
27-------------------
28begin                : Fri Sep 27 2002
29copyright            : (C) 2002 by Jon Anderson
30email                : janders@users.sf.net
31 
32Enhancements 2003 - 2004 (C) The OGRE Team
33 
34***************************************************************************/
35
36#include <OgreOctreeSceneManager.h>
37#include <OgreOctreeSceneQuery.h>
38#include <OgreOctreeNode.h>
39#include <OgreOctreeCamera.h>
40#include <OgreRenderSystem.h>
41
42
43extern "C"
44{
45    void findNodesInBox( Ogre::SceneManager *sm,
46                         const Ogre::AxisAlignedBox &box,
47                         std::list < Ogre::SceneNode * > &list,
48                         Ogre::SceneNode *exclude )
49    {
50        static_cast<Ogre::OctreeSceneManager*>( sm ) -> findNodesIn( box, list, exclude );
51    }
52    void findNodesInSphere( Ogre::SceneManager *sm,
53                            const Ogre::Sphere &sphere,
54                            std::list < Ogre::SceneNode * > &list,
55                            Ogre::SceneNode *exclude )
56    {
57        static_cast<Ogre::OctreeSceneManager*>( sm ) -> findNodesIn( sphere, list, exclude );
58    }
59}
60
61namespace Ogre
62{
63enum Intersection
64{
65    OUTSIDE=0,
66    INSIDE=1,
67    INTERSECT=2
68};
69int OctreeSceneManager::intersect_call = 0;
70
71Intersection intersect( const Ray &one, const AxisAlignedBox &two )
72{
73    OctreeSceneManager::intersect_call++;
74    // Null box?
75    if (two.isNull()) return OUTSIDE;
76
77    bool inside = true;
78    const Vector3* pCorners = two.getAllCorners();
79    Vector3 origin = one.getOrigin();
80    Vector3 dir = one.getDirection();
81
82    Vector3 maxT(-1, -1, -1);
83
84    int i = 0;
85    for(i=0; i<3; i++ )
86    {
87        if( origin[i] < pCorners[0][i] )
88        {
89            inside = false;
90            if( dir[i] > 0 )
91            {
92                maxT[i] = (pCorners[0][i] - origin[i])/ dir[i];
93            }
94        }
95        else if( origin[i] > pCorners[4][i] )
96        {
97            inside = false;
98            if( dir[i] < 0 )
99            {
100                maxT[i] = (pCorners[4][i] - origin[i]) / dir[i];
101            }
102        }
103    }
104
105    if( inside )
106    {
107        return INTERSECT;
108    }
109    int whichPlane = 0;
110    if( maxT[1] > maxT[whichPlane])
111        whichPlane = 1;
112    if( maxT[2] > maxT[whichPlane])
113        whichPlane = 2;
114
115    if( ((int)maxT[whichPlane]) & 0x80000000 )
116    {
117        return OUTSIDE;
118    }
119    for(i=0; i<3; i++ )
120    {
121        if( i!= whichPlane )
122        {
123            float f = origin[i] + maxT[whichPlane] * dir[i];
124            if ( f < (pCorners[0][i] - 0.00001f) ||
125                    f > (pCorners[4][i] +0.00001f ) )
126            {
127                return OUTSIDE;
128            }
129        }
130    }
131
132    return INTERSECT;
133
134}
135
136
137/** Checks how the second box intersects with the first.
138*/
139Intersection intersect( const PlaneBoundedVolume &one, const AxisAlignedBox &two )
140{
141    OctreeSceneManager::intersect_call++;
142    // Null box?
143    if (two.isNull()) return OUTSIDE;
144
145    // Get corners of the box
146    const Vector3* pCorners = two.getAllCorners();
147
148    // For each plane, see if all points are on the negative side
149    // If so, object is not visible.
150    // If one or more are, it's partial.
151    // If all aren't, full
152    int corners[ 8 ] = {0, 4, 3, 5, 2, 6, 1, 7};
153    bool all_inside = true;
154    PlaneList::const_iterator i, iend;
155    iend = one.planes.end();
156    for (i = one.planes.begin(); i != iend; ++i)
157    {
158        const Plane& plane = *i;
159        bool all_outside = true;
160
161        float distance = 0;
162
163        for ( int corner = 0; corner < 8; ++corner )
164        {
165            distance = plane.getDistance( pCorners[ corners[ corner ] ] );
166            all_outside = all_outside && ( distance < 0 );
167            all_inside = all_inside && ( distance >= 0 );
168
169            if ( !all_outside && !all_inside )
170                break;
171        }
172
173        if ( all_outside )
174            return OUTSIDE;
175    }
176
177    if ( all_inside )
178        return INSIDE;
179    else
180        return INTERSECT;
181
182}
183
184
185/** Checks how the second box intersects with the first.
186*/
187Intersection intersect( const AxisAlignedBox &one, const AxisAlignedBox &two )
188{
189    OctreeSceneManager::intersect_call++;
190    // Null box?
191    if (one.isNull() || two.isNull()) return OUTSIDE;
192
193    const Vector3 * outside = one.getAllCorners();
194    const Vector3 *inside = two.getAllCorners();
195
196    if ( inside[ 4 ].x < outside[ 0 ].x ||
197            inside[ 4 ].y < outside[ 0 ].y ||
198            inside[ 4 ].z < outside[ 0 ].z ||
199            inside[ 0 ].x > outside[ 4 ].x ||
200            inside[ 0 ].y > outside[ 4 ].y ||
201            inside[ 0 ].z > outside[ 4 ].z )
202    {
203        return OUTSIDE;
204    }
205
206    bool full = ( inside[ 0 ].x > outside[ 0 ].x &&
207                  inside[ 0 ].y > outside[ 0 ].y &&
208                  inside[ 0 ].z > outside[ 0 ].z &&
209                  inside[ 4 ].x < outside[ 4 ].x &&
210                  inside[ 4 ].y < outside[ 4 ].y &&
211                  inside[ 4 ].z < outside[ 4 ].z );
212
213    if ( full )
214        return INSIDE;
215    else
216        return INTERSECT;
217
218}
219
220/** Checks how the box intersects with the sphere.
221*/
222Intersection intersect( const Sphere &one, const AxisAlignedBox &two )
223{
224    OctreeSceneManager::intersect_call++;
225    // Null box?
226    if (two.isNull()) return OUTSIDE;
227
228    float sradius = one.getRadius();
229
230    sradius *= sradius;
231
232    Vector3 scenter = one.getCenter();
233
234    const Vector3 *corners = two.getAllCorners();
235
236    float s, d = 0;
237
238    Vector3 mndistance = ( corners[ 0 ] - scenter );
239    Vector3 mxdistance = ( corners[ 4 ] - scenter );
240
241    if ( mndistance.squaredLength() < sradius &&
242            mxdistance.squaredLength() < sradius )
243    {
244        return INSIDE;
245    }
246
247    //find the square of the distance
248    //from the sphere to the box
249    for ( int i = 0 ; i < 3 ; i++ )
250    {
251        if ( scenter[ i ] < corners[ 0 ][ i ] )
252        {
253            s = scenter[ i ] - corners[ 0 ][ i ];
254            d += s * s;
255        }
256
257        else if ( scenter[ i ] > corners[ 4 ][ i ] )
258        {
259            s = scenter[ i ] - corners[ 4 ][ i ];
260            d += s * s;
261        }
262
263    }
264
265    bool partial = ( d <= sradius );
266
267    if ( !partial )
268    {
269        return OUTSIDE;
270    }
271
272    else
273    {
274        return INTERSECT;
275    }
276
277
278}
279
280unsigned long white = 0xFFFFFFFF;
281
282unsigned short OctreeSceneManager::mIndexes[ 24 ] = {0, 1, 1, 2, 2, 3, 3, 0,       //back
283        0, 6, 6, 5, 5, 1,             //left
284        3, 7, 7, 4, 4, 2,             //right
285        6, 7, 5, 4 };          //front
286unsigned long OctreeSceneManager::mColors[ 8 ] = {white, white, white, white, white, white, white, white };
287
288
289OctreeSceneManager::OctreeSceneManager(const String& name) : SceneManager(name)
290{
291    AxisAlignedBox b( -10000, -10000, -10000, 10000, 10000, 10000 );
292    int depth = 8;
293    mOctree = 0;
294    init( b, depth );
295}
296
297OctreeSceneManager::OctreeSceneManager(const String& name, AxisAlignedBox &box, int max_depth )
298: SceneManager(name)
299{
300    mOctree = 0;
301    init( box, max_depth );
302}
303
304const String& OctreeSceneManager::getTypeName(void) const
305{
306        return OctreeSceneManagerFactory::FACTORY_TYPE_NAME;
307}
308
309void OctreeSceneManager::init( AxisAlignedBox &box, int depth )
310{
311    delete mSceneRoot; //get rid of old root.
312
313    // -- Changes by Steve
314    // Don't do it this way, it will add it to the mSceneNodes which we don't want
315    //mSceneRoot = createSceneNode( "SceneRoot" );
316    mSceneRoot = new OctreeNode( this, "SceneRoot" );
317        mSceneRoot->_notifyRootNode();
318    // -- End changes by Steve
319
320    if ( mOctree != 0 )
321        delete mOctree;
322
323    mOctree = new Octree( 0 );
324
325    mMaxDepth = depth;
326    mBox = box;
327
328    mOctree -> mBox = box;
329
330    Vector3 min = box.getMinimum();
331
332    Vector3 max = box.getMaximum();
333
334    mOctree -> mHalfSize = ( max - min ) / 2;
335
336
337    mShowBoxes = false;
338
339    mCullCamera = false;
340
341    mNumObjects = 0;
342
343    Vector3 v( 1.5, 1.5, 1.5 );
344
345    mScaleFactor.setScale( v );
346
347
348
349    // setDisplaySceneNodes( true );
350    // setShowBoxes( true );
351
352    //
353    //setUseCullCamera( true );
354    //mSceneRoot isn't put into the octree since it has no volume.
355
356}
357
358OctreeSceneManager::~OctreeSceneManager()
359{
360    // -- Changed by Steve
361    // Don't do this here, SceneManager will do it
362    /*
363    if( mSceneRoot )
364    delete mSceneRoot;
365    */
366    // --End Changes by Steve
367
368    if ( mOctree )
369        delete mOctree;
370}
371
372Camera * OctreeSceneManager::createCamera( const String &name )
373{
374    Camera * c = new OctreeCamera( name, this );
375    mCameras.insert( CameraList::value_type( name, c ) );
376    return c;
377}
378
379void OctreeSceneManager::destroySceneNode( const String &name )
380{
381    OctreeNode * on = static_cast < OctreeNode* > ( getSceneNode( name ) );
382
383    if ( on != 0 )
384        _removeOctreeNode( on );
385
386    SceneManager::destroySceneNode( name );
387}
388
389bool OctreeSceneManager::getOptionValues( const String & key, StringVector  &refValueList )
390{
391    return SceneManager::getOptionValues( key, refValueList );
392}
393
394bool OctreeSceneManager::getOptionKeys( StringVector & refKeys )
395{
396    SceneManager::getOptionKeys( refKeys );
397    refKeys.push_back( "CullCamera" );
398    refKeys.push_back( "Size" );
399    refKeys.push_back( "ShowOctree" );
400    refKeys.push_back( "Depth" );
401
402    return true;
403}
404
405
406void OctreeSceneManager::_updateOctreeNode( OctreeNode * onode )
407{
408    AxisAlignedBox box = onode -> _getWorldAABB();
409
410    if ( box.isNull() )
411        return ;
412
413
414    if ( onode -> getOctant() == 0 )
415    {
416        //if outside the octree, force into the root node.
417        if ( ! onode -> _isIn( mOctree -> mBox ) )
418            mOctree->_addNode( onode );
419        else
420            _addOctreeNode( onode, mOctree );
421        return ;
422    }
423
424    if ( ! onode -> _isIn( onode -> getOctant() -> mBox ) )
425    {
426        _removeOctreeNode( onode );
427
428        //if outside the octree, force into the root node.
429        if ( ! onode -> _isIn( mOctree -> mBox ) )
430            mOctree->_addNode( onode );
431        else
432            _addOctreeNode( onode, mOctree );
433    }
434}
435
436/** Only removes the node from the octree.  It leaves the octree, even if it's empty.
437*/
438void OctreeSceneManager::_removeOctreeNode( OctreeNode * n )
439{
440    Octree * oct = n -> getOctant();
441
442    if ( oct )
443    {
444        oct -> _removeNode( n );
445    }
446
447    n->setOctant(0);
448}
449
450
451void OctreeSceneManager::_addOctreeNode( OctreeNode * n, Octree *octant, int depth )
452{
453
454    AxisAlignedBox bx = n -> _getWorldAABB();
455
456
457    //if the octree is twice as big as the scene node,
458    //we will add it to a child.
459    if ( ( depth < mMaxDepth ) && octant -> _isTwiceSize( bx ) )
460    {
461        int x, y, z;
462        octant -> _getChildIndexes( bx, &x, &y, &z );
463
464        if ( octant -> mChildren[ x ][ y ][ z ] == 0 )
465        {
466            octant -> mChildren[ x ][ y ][ z ] = new Octree( octant );
467
468            const Vector3 *corners = octant -> mBox.getAllCorners();
469            Vector3 min, max;
470
471            if ( x == 0 )
472            {
473                min.x = corners[ 0 ].x;
474                max.x = ( corners[ 0 ].x + corners[ 4 ].x ) / 2;
475            }
476
477            else
478            {
479                min.x = ( corners[ 0 ].x + corners[ 4 ].x ) / 2;
480                max.x = corners[ 4 ].x;
481            }
482
483            if ( y == 0 )
484            {
485                min.y = corners[ 0 ].y;
486                max.y = ( corners[ 0 ].y + corners[ 4 ].y ) / 2;
487            }
488
489            else
490            {
491                min.y = ( corners[ 0 ].y + corners[ 4 ].y ) / 2;
492                max.y = corners[ 4 ].y;
493            }
494
495            if ( z == 0 )
496            {
497                min.z = corners[ 0 ].z;
498                max.z = ( corners[ 0 ].z + corners[ 4 ].z ) / 2;
499            }
500
501            else
502            {
503                min.z = ( corners[ 0 ].z + corners[ 4 ].z ) / 2;
504                max.z = corners[ 4 ].z;
505            }
506
507            octant -> mChildren[ x ][ y ][ z ] -> mBox.setExtents( min, max );
508            octant -> mChildren[ x ][ y ][ z ] -> mHalfSize = ( max - min ) / 2;
509        }
510
511        _addOctreeNode( n, octant -> mChildren[ x ][ y ][ z ], ++depth );
512
513    }
514
515    else
516    {
517        octant -> _addNode( n );
518    }
519}
520
521
522SceneNode * OctreeSceneManager::createSceneNode( void )
523{
524    OctreeNode * on = new OctreeNode( this );
525    mSceneNodes[ on->getName() ] = on;
526    return on;
527}
528
529SceneNode * OctreeSceneManager::createSceneNode( const String &name )
530{
531    // Check name not used
532    if (mSceneNodes.find(name) != mSceneNodes.end())
533    {
534        OGRE_EXCEPT(
535            Exception::ERR_DUPLICATE_ITEM,
536            "A scene node with the name " + name + " already exists",
537            "OctreeSceneManager::createSceneNode" );
538    }
539    OctreeNode * on = new OctreeNode( this, name );
540    mSceneNodes[ on->getName() ] = on;
541    return on;
542}
543
544void OctreeSceneManager::_updateSceneGraph( Camera * cam )
545{
546    SceneManager::_updateSceneGraph( cam );
547}
548
549void OctreeSceneManager::_alertVisibleObjects( void )
550{
551    OGRE_EXCEPT( Exception::UNIMPLEMENTED_FEATURE,
552        "Function doesn't do as advertised",
553        "OctreeSceneManager::_alertVisibleObjects" );
554
555    NodeList::iterator it = mVisible.begin();
556
557    while ( it != mVisible.end() )
558    {
559        OctreeNode * node = *it;
560
561        ++it;
562    }
563}
564
565void OctreeSceneManager::_findVisibleObjects( Camera * cam, bool onlyShadowCasters )
566{
567
568    getRenderQueue()->clear();
569    mBoxes.clear();
570    mVisible.clear();
571
572    if ( mCullCamera )
573    {
574        Camera * c = getCamera( "CullCamera" );
575
576        if ( c != 0 )
577            cam = c;
578    }
579
580    mNumObjects = 0;
581
582    //walk the octree, adding all visible Octreenodes nodes to the render queue.
583    walkOctree( static_cast < OctreeCamera * > ( cam ), getRenderQueue(), mOctree, false, onlyShadowCasters );
584
585
586    // Show the octree boxes & cull camera if required
587    if ( mShowBoxes || mCullCamera )
588    {
589
590
591
592        if ( mShowBoxes )
593        {
594            for ( BoxList::iterator it = mBoxes.begin(); it != mBoxes.end(); ++it )
595            {
596                getRenderQueue()->addRenderable(*it);
597            }
598        }
599
600        if ( mCullCamera )
601        {
602            OctreeCamera * c = static_cast<OctreeCamera*>(getCamera( "CullCamera" ));
603
604            if ( c != 0 )
605            {
606                getRenderQueue()->addRenderable(c);
607            }
608        }
609
610    }
611
612
613
614}
615
616void OctreeSceneManager::walkOctree( OctreeCamera *camera, RenderQueue *queue,
617                                     Octree *octant, bool foundvisible, bool onlyShadowCasters )
618{
619
620    //return immediately if nothing is in the node.
621    if ( octant -> numNodes() == 0 )
622        return ;
623
624    OctreeCamera::Visibility v = OctreeCamera::NONE;
625
626    if ( foundvisible )
627    {
628        v = OctreeCamera::FULL;
629    }
630
631    else if ( octant == mOctree )
632    {
633        v = OctreeCamera::PARTIAL;
634    }
635
636    else
637    {
638        AxisAlignedBox box;
639        octant -> _getCullBounds( &box );
640        v = camera -> getVisibility( box );
641    }
642
643
644    // if the octant is visible, or if it's the root node...
645    if ( v != OctreeCamera::NONE )
646    {
647
648        //Add stuff to be rendered;
649        NodeList::iterator it = octant -> mNodes.begin();
650
651        if ( mShowBoxes )
652        {
653            mBoxes.push_back( octant->getWireBoundingBox() );
654        }
655
656        bool vis = true;
657
658        while ( it != octant -> mNodes.end() )
659        {
660            OctreeNode * sn = *it;
661
662            // if this octree is partially visible, manually cull all
663            // scene nodes attached directly to this level.
664
665            if ( v == OctreeCamera::PARTIAL )
666                vis = camera -> isVisible( sn -> _getWorldAABB() );
667
668            if ( vis )
669            {
670
671                mNumObjects++;
672                sn -> _addToRenderQueue(camera, queue, onlyShadowCasters );
673
674                mVisible.push_back( sn );
675
676                if ( mDisplayNodes )
677                    queue -> addRenderable( sn );
678
679                // check if the scene manager or this node wants the bounding box shown.
680                if (sn->getShowBoundingBox() || mShowBoundingBoxes)
681                    sn->_addBoundingBoxToQueue(queue);
682            }
683
684            ++it;
685        }
686
687        Octree* child;
688        bool childfoundvisible = (v == OctreeCamera::FULL);
689        if ( (child = octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
690            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
691
692        if ( (child = octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
693            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
694
695        if ( (child = octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
696            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
697
698        if ( (child = octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
699            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
700
701        if ( (child = octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
702            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
703
704        if ( (child = octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
705            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
706
707        if ( (child = octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
708            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
709
710        if ( (child = octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
711            walkOctree( camera, queue, child, childfoundvisible, onlyShadowCasters );
712
713    }
714
715}
716
717// --- non template versions
718void _findNodes( const AxisAlignedBox &t, std::list < SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
719{
720
721        if ( !full )
722        {
723                AxisAlignedBox obox;
724                octant -> _getCullBounds( &obox );
725
726                Intersection isect = intersect( t, obox );
727
728                if ( isect == OUTSIDE )
729                        return ;
730
731                full = ( isect == INSIDE );
732        }
733
734
735        NodeList::iterator it = octant -> mNodes.begin();
736
737        while ( it != octant -> mNodes.end() )
738        {
739                OctreeNode * on = ( *it );
740
741                if ( on != exclude )
742                {
743                        if ( full )
744                        {
745                                list.push_back( on );
746                        }
747
748                        else
749                        {
750                                Intersection nsect = intersect( t, on -> _getWorldAABB() );
751
752                                if ( nsect != OUTSIDE )
753                                {
754                                        list.push_back( on );
755                                }
756                        }
757
758                }
759
760                ++it;
761        }
762
763        Octree* child;
764
765        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
766                _findNodes( t, list, exclude, full, child );
767
768        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
769                _findNodes( t, list, exclude, full, child );
770
771        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
772                _findNodes( t, list, exclude, full, child );
773
774        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
775                _findNodes( t, list, exclude, full, child );
776
777        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
778                _findNodes( t, list, exclude, full, child );
779
780        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
781                _findNodes( t, list, exclude, full, child );
782
783        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
784                _findNodes( t, list, exclude, full, child );
785
786        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
787                _findNodes( t, list, exclude, full, child );
788
789}
790
791void _findNodes( const Sphere &t, std::list < SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
792{
793
794        if ( !full )
795        {
796                AxisAlignedBox obox;
797                octant -> _getCullBounds( &obox );
798
799                Intersection isect = intersect( t, obox );
800
801                if ( isect == OUTSIDE )
802                        return ;
803
804                full = ( isect == INSIDE );
805        }
806
807
808        NodeList::iterator it = octant -> mNodes.begin();
809
810        while ( it != octant -> mNodes.end() )
811        {
812                OctreeNode * on = ( *it );
813
814                if ( on != exclude )
815                {
816                        if ( full )
817                        {
818                                list.push_back( on );
819                        }
820
821                        else
822                        {
823                                Intersection nsect = intersect( t, on -> _getWorldAABB() );
824
825                                if ( nsect != OUTSIDE )
826                                {
827                                        list.push_back( on );
828                                }
829                        }
830
831                }
832
833                ++it;
834        }
835
836        Octree* child;
837
838        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
839                _findNodes( t, list, exclude, full, child );
840
841        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
842                _findNodes( t, list, exclude, full, child );
843
844        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
845                _findNodes( t, list, exclude, full, child );
846
847        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
848                _findNodes( t, list, exclude, full, child );
849
850        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
851                _findNodes( t, list, exclude, full, child );
852
853        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
854                _findNodes( t, list, exclude, full, child );
855
856        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
857                _findNodes( t, list, exclude, full, child );
858
859        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
860                _findNodes( t, list, exclude, full, child );
861
862}
863
864
865void _findNodes( const PlaneBoundedVolume &t, std::list < SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
866{
867
868        if ( !full )
869        {
870                AxisAlignedBox obox;
871                octant -> _getCullBounds( &obox );
872
873                Intersection isect = intersect( t, obox );
874
875                if ( isect == OUTSIDE )
876                        return ;
877
878                full = ( isect == INSIDE );
879        }
880
881
882        NodeList::iterator it = octant -> mNodes.begin();
883
884        while ( it != octant -> mNodes.end() )
885        {
886                OctreeNode * on = ( *it );
887
888                if ( on != exclude )
889                {
890                        if ( full )
891                        {
892                                list.push_back( on );
893                        }
894
895                        else
896                        {
897                                Intersection nsect = intersect( t, on -> _getWorldAABB() );
898
899                                if ( nsect != OUTSIDE )
900                                {
901                                        list.push_back( on );
902                                }
903                        }
904
905                }
906
907                ++it;
908        }
909
910        Octree* child;
911
912        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
913                _findNodes( t, list, exclude, full, child );
914
915        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
916                _findNodes( t, list, exclude, full, child );
917
918        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
919                _findNodes( t, list, exclude, full, child );
920
921        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
922                _findNodes( t, list, exclude, full, child );
923
924        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
925                _findNodes( t, list, exclude, full, child );
926
927        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
928                _findNodes( t, list, exclude, full, child );
929
930        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
931                _findNodes( t, list, exclude, full, child );
932
933        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
934                _findNodes( t, list, exclude, full, child );
935
936}
937
938void _findNodes( const Ray &t, std::list < SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
939{
940
941        if ( !full )
942        {
943                AxisAlignedBox obox;
944                octant -> _getCullBounds( &obox );
945
946                Intersection isect = intersect( t, obox );
947
948                if ( isect == OUTSIDE )
949                        return ;
950
951                full = ( isect == INSIDE );
952        }
953
954
955        NodeList::iterator it = octant -> mNodes.begin();
956
957        while ( it != octant -> mNodes.end() )
958        {
959                OctreeNode * on = ( *it );
960
961                if ( on != exclude )
962                {
963                        if ( full )
964                        {
965                                list.push_back( on );
966                        }
967
968                        else
969                        {
970                                Intersection nsect = intersect( t, on -> _getWorldAABB() );
971
972                                if ( nsect != OUTSIDE )
973                                {
974                                        list.push_back( on );
975                                }
976                        }
977
978                }
979
980                ++it;
981        }
982
983        Octree* child;
984
985        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 0 ]) != 0 )
986                _findNodes( t, list, exclude, full, child );
987
988        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
989                _findNodes( t, list, exclude, full, child );
990
991        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
992                _findNodes( t, list, exclude, full, child );
993
994        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
995                _findNodes( t, list, exclude, full, child );
996
997        if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
998                _findNodes( t, list, exclude, full, child );
999
1000        if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
1001                _findNodes( t, list, exclude, full, child );
1002
1003        if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
1004                _findNodes( t, list, exclude, full, child );
1005
1006        if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
1007                _findNodes( t, list, exclude, full, child );
1008
1009}
1010
1011void OctreeSceneManager::findNodesIn( const AxisAlignedBox &box, std::list < SceneNode * > &list, SceneNode *exclude )
1012{
1013    _findNodes( box, list, exclude, false, mOctree );
1014}
1015
1016void OctreeSceneManager::findNodesIn( const Sphere &sphere, std::list < SceneNode * > &list, SceneNode *exclude )
1017{
1018    _findNodes( sphere, list, exclude, false, mOctree );
1019}
1020
1021void OctreeSceneManager::findNodesIn( const PlaneBoundedVolume &volume, std::list < SceneNode * > &list, SceneNode *exclude )
1022{
1023    _findNodes( volume, list, exclude, false, mOctree );
1024}
1025
1026void OctreeSceneManager::findNodesIn( const Ray &r, std::list < SceneNode * > &list, SceneNode *exclude )
1027{
1028    _findNodes( r, list, exclude, false, mOctree );
1029}
1030
1031void OctreeSceneManager::resize( const AxisAlignedBox &box )
1032{
1033    std::list < SceneNode * > nodes;
1034    std::list < SceneNode * > ::iterator it;
1035
1036    _findNodes( mOctree->mBox, nodes, 0, true, mOctree );
1037
1038    delete mOctree;
1039
1040    mOctree = new Octree( 0 );
1041    mOctree->mBox = box;
1042
1043        const Vector3 min = box.getMinimum();
1044        const Vector3 max = box.getMaximum();
1045        mOctree->mHalfSize = ( max - min ) * 0.5f;
1046
1047    it = nodes.begin();
1048
1049    while ( it != nodes.end() )
1050    {
1051        OctreeNode * on = static_cast < OctreeNode * > ( *it );
1052        on -> setOctant( 0 );
1053        _updateOctreeNode( on );
1054        ++it;
1055    }
1056
1057}
1058
1059bool OctreeSceneManager::setOption( const String & key, const void * val )
1060{
1061    if ( key == "Size" )
1062    {
1063        resize( * static_cast < const AxisAlignedBox * > ( val ) );
1064        return true;
1065    }
1066
1067    else if ( key == "Depth" )
1068    {
1069        mMaxDepth = * static_cast < const int * > ( val );
1070        resize( mOctree->mBox );
1071        return true;
1072    }
1073
1074    else if ( key == "ShowOctree" )
1075    {
1076        mShowBoxes = * static_cast < const bool * > ( val );
1077        return true;
1078    }
1079
1080    else if ( key == "CullCamera" )
1081    {
1082        mCullCamera = * static_cast < const bool * > ( val );
1083        return true;
1084    }
1085
1086    return SceneManager::setOption( key, val );
1087
1088
1089}
1090
1091bool OctreeSceneManager::getOption( const String & key, void *val )
1092{
1093    if ( key == "Size" )
1094    {
1095        AxisAlignedBox * b = static_cast < AxisAlignedBox * > ( val );
1096        b -> setExtents( mOctree->mBox.getMinimum(), mOctree->mBox.getMaximum() );
1097        return true;
1098    }
1099
1100    else if ( key == "Depth" )
1101    {
1102        * static_cast < int * > ( val ) = mMaxDepth;
1103        return true;
1104    }
1105
1106    else if ( key == "ShowOctree" )
1107    {
1108
1109        * static_cast < bool * > ( val ) = mShowBoxes;
1110        return true;
1111    }
1112
1113    else if ( key == "CullCamera" )
1114    {
1115        * static_cast < bool * > ( val ) = mCullCamera;
1116        return true;
1117    }
1118
1119    return SceneManager::getOption( key, val );
1120
1121}
1122
1123void OctreeSceneManager::clearScene(void)
1124{
1125    SceneManager::clearScene();
1126    init(mBox, mMaxDepth);
1127
1128}
1129
1130//---------------------------------------------------------------------
1131AxisAlignedBoxSceneQuery*
1132OctreeSceneManager::createAABBQuery(const AxisAlignedBox& box, unsigned long mask)
1133{
1134    OctreeAxisAlignedBoxSceneQuery* q = new OctreeAxisAlignedBoxSceneQuery(this);
1135    q->setBox(box);
1136    q->setQueryMask(mask);
1137    return q;
1138}
1139//---------------------------------------------------------------------
1140SphereSceneQuery*
1141OctreeSceneManager::createSphereQuery(const Sphere& sphere, unsigned long mask)
1142{
1143    OctreeSphereSceneQuery* q = new OctreeSphereSceneQuery(this);
1144    q->setSphere(sphere);
1145    q->setQueryMask(mask);
1146    return q;
1147}
1148//---------------------------------------------------------------------
1149PlaneBoundedVolumeListSceneQuery*
1150OctreeSceneManager::createPlaneBoundedVolumeQuery(const PlaneBoundedVolumeList& volumes,
1151        unsigned long mask)
1152{
1153    OctreePlaneBoundedVolumeListSceneQuery* q = new OctreePlaneBoundedVolumeListSceneQuery(this);
1154    q->setVolumes(volumes);
1155    q->setQueryMask(mask);
1156    return q;
1157}
1158
1159//---------------------------------------------------------------------
1160RaySceneQuery*
1161OctreeSceneManager::createRayQuery(const Ray& ray, unsigned long mask)
1162{
1163    OctreeRaySceneQuery* q = new OctreeRaySceneQuery(this);
1164    q->setRay(ray);
1165    q->setQueryMask(mask);
1166    return q;
1167}
1168//---------------------------------------------------------------------
1169IntersectionSceneQuery*
1170OctreeSceneManager::createIntersectionQuery(unsigned long mask)
1171{
1172
1173    // Octree implementation performs WORSE for < 500 objects
1174    // TODO: optimise it so it's better in all cases
1175    //OctreeIntersectionSceneQuery* q = new OctreeIntersectionSceneQuery(this);
1176    DefaultIntersectionSceneQuery* q = new DefaultIntersectionSceneQuery(this);
1177    q->setQueryMask(mask);
1178    return q;
1179}
1180//-----------------------------------------------------------------------
1181const String OctreeSceneManagerFactory::FACTORY_TYPE_NAME = "OctreeSceneManager";
1182//-----------------------------------------------------------------------
1183void OctreeSceneManagerFactory::initMetaData(void) const
1184{
1185        mMetaData.typeName = FACTORY_TYPE_NAME;
1186        mMetaData.description = "Scene manager organising the scene on the basis of an octree.";
1187        mMetaData.sceneTypeMask = 0xFFFF; // support all types
1188        mMetaData.worldGeometrySupported = false;
1189}
1190//-----------------------------------------------------------------------
1191SceneManager* OctreeSceneManagerFactory::createInstance(
1192        const String& instanceName)
1193{
1194        return new OctreeSceneManager(instanceName);
1195}
1196//-----------------------------------------------------------------------
1197void OctreeSceneManagerFactory::destroyInstance(SceneManager* instance)
1198{
1199        delete instance;
1200}
1201
1202
1203}
Note: See TracBrowser for help on using the repository browser.