Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp @ 5

Last change on this file since 5 was 5, checked in by anonymous, 17 years ago

=hoffentlich gehts jetzt

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