scopeTracker.h

Engine/source/util/scopeTracker.h

A mechanism for continuous tracking of point/box intersections.

More...

Classes:

class

Helper class to track the position of a point in N-dimensional space relative to a collection of N-dimensional volumes.

class

Base class for objects registered with a ScopeTracker.

class

TrackingNodes are used to track object bounds along individual world axes.

Detailed Description

A mechanism for continuous tracking of point/box intersections.

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _SCOPETRACKER_H_
 25#define _SCOPETRACKER_H_
 26
 27#ifndef _TYPETRAITS_H_
 28   #include "platform/typetraits.h"
 29#endif
 30#ifndef _BITSET_H_
 31   #include "core/bitSet.h"
 32#endif
 33#ifndef _TVECTOR_H_
 34   #include "core/util/tVector.h"
 35#endif
 36#ifndef _CONSOLE_H_
 37   #include "console/console.h"
 38#endif
 39#ifndef _PROFILER_H_
 40   #include "platform/profiler.h"
 41#endif
 42
 43//#define DEBUG_SPEW
 44
 45
 46/// @file
 47/// A mechanism for continuous tracking of point/box intersections.
 48
 49
 50/// Base class for objects registered with a ScopeTracker.
 51template< S32 NUM_DIMENSIONS >
 52class ScopeTrackerObject
 53{
 54   public:
 55   
 56      typedef void Parent;
 57
 58      /// TrackingNodes are used to track object bounds along individual world axes.
 59      class TrackingNode
 60      {
 61         public:
 62         
 63            typedef void Parent;
 64            
 65            enum EFlags
 66            {
 67               FLAG_Min          = BIT( 0 ),
 68               FLAG_Max          = BIT( 1 ),
 69               FLAG_Reference    = BIT( 2 ),
 70            };
 71                     
 72            ///
 73            BitSet32 mFlags;
 74            
 75            ///
 76            TrackingNode* mOpposite;
 77            
 78            /// Distance along axis.
 79            F32 mPosition;
 80
 81            /// The object being tracked by this node or NULL.
 82            ScopeTrackerObject* mObject;
 83            
 84            /// Next node on axis tracking chain.
 85            TrackingNode* mNext;
 86            
 87            /// Previous node on axis tracking chain.
 88            TrackingNode* mPrev;
 89            
 90            ///
 91            TrackingNode()
 92               : mOpposite( NULL ), mPosition( 0.0f ), mObject( NULL ), mNext( NULL ), mPrev( NULL ) {}
 93               
 94            /// Return the object to which this tracking node belongs.
 95            ScopeTrackerObject* getObject() const { return mObject; }
 96            
 97            ///
 98            TrackingNode* getOpposite() const { return mOpposite; }
 99            
100            ///
101            F32 getPosition() const { return mPosition; }
102            
103            ///
104            void setPosition( F32 value ) { mPosition = value; }
105            
106            ///
107            TrackingNode* getNext() const { return mNext; }
108            
109            ///
110            void setNext( TrackingNode* node ) { mNext = node; }
111            
112            ///
113            TrackingNode* getPrev() const { return mPrev; }
114            
115            ///
116            void setPrev( TrackingNode* node ) { mPrev = node; }
117
118            /// Return true if this is left/lower bound node of an object.
119            bool isMin() const { return mFlags.test( FLAG_Min ); }
120            
121            /// Return true if this is the right/upper bound node of an object.
122            bool isMax() const { return mFlags.test( FLAG_Max ); }
123            
124            /// Return true if this is the reference center tracking node.  There will only
125            /// ever be one such node on each tracking list.
126            bool isReference() const { return mFlags.test( FLAG_Reference ); }
127      };
128      
129      enum
130      {
131         AllInScope = ( 0x01010101 >> ( ( 4 - NUM_DIMENSIONS ) * 8 ) )
132      };
133      
134   protected:
135         
136      ///
137      union
138      {
139         U8 mBytes[ 4 ];
140         U32 mDWord;
141      } mScopeMask;
142
143      ///
144      TrackingNode mTrackingNodes[ NUM_DIMENSIONS ][ 2 ];
145
146   public:
147   
148      ///
149      ScopeTrackerObject( U32 flags = 0 )
150      {
151         clearScopeMask();
152         for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
153         {
154            TrackingNode* minNode = getMinTrackingNode( n );
155            TrackingNode* maxNode = getMaxTrackingNode( n );
156            
157            minNode->mFlags    = flags;
158            maxNode->mFlags    = flags;
159            
160            minNode->mObject   = this;
161            maxNode->mObject   = this;
162            
163            minNode->mOpposite = maxNode;
164            maxNode->mOpposite = minNode;
165            
166            minNode->mFlags.set( TrackingNode::FLAG_Min );
167            maxNode->mFlags.set( TrackingNode::FLAG_Max );
168         }
169      }
170      
171      /// Return true if the object is currently being tracked.
172      bool isRegistered() const
173      {
174         for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
175            if( getMinTrackingNode( n )->getNext() != NULL )
176               return true;
177         return false;
178      }
179   
180      /// Return true if the reference center lies within the object bound's on all axes.
181      bool isInScope() const { return ( mScopeMask.mDWord == AllInScope ); }
182      
183      ///
184      bool isInScope( U32 dimension ) const { return mScopeMask.mBytes[ dimension ]; }
185      
186      ///
187      void setInScope( U32 dimension, bool state ) { mScopeMask.mBytes[ dimension ] = ( state ? 1 : 0 ); }
188      
189      ///
190      void clearScopeMask() { mScopeMask.mDWord = 0; }
191            
192      ///
193      TrackingNode* getMinTrackingNode( U32 dimension ) { return &mTrackingNodes[ dimension ][ 0 ]; }
194      const TrackingNode* getMinTrackingNode( U32 dimension ) const { return &mTrackingNodes[ dimension ][ 0 ]; }
195      
196      ///
197      TrackingNode* getMaxTrackingNode( U32 dimension ) { return &mTrackingNodes[ dimension ][ 1 ]; }
198      const TrackingNode* getMaxTrackingNode( U32 dimension ) const { return &mTrackingNodes[ dimension ][ 1 ]; }
199      
200      /// @name Implementor Interface
201      ///
202      /// The following methods must be implemented by the client.  They are defined here
203      /// just for reference.  If you don't override them, you'll get link errors.
204      ///
205      /// @{
206      
207      /// Return the position of the object in world-space.
208      void getPosition( F32 pos[ NUM_DIMENSIONS ] ) const;
209      
210      /// If this object is the reference object, this method should return the world-space pivot
211      /// point in the object that will be the world reference center.
212      void getReferenceCenter( F32 pos[ NUM_DIMENSIONS ] ) const;
213      
214      /// Return the object's bounding box in world-space.
215      void getBounds( F32 minBounds[ NUM_DIMENSIONS ], F32 maxBounds[ NUM_DIMENSIONS ] ) const;
216      
217      ///
218      String describeSelf() const;
219   
220      /// @}
221};
222
223
224/// Helper class to track the position of a point in N-dimensional space relative to a collection
225/// of N-dimensional volumes.
226///
227/// This class works by breaking the N-dimensional case down into N one-dimensional cases.  By tracking
228/// objects independently along each of their axes, intersection testing becomes a trivial matter of
229/// doing point-on-line tests.  The line segments can be conveniently represented as ordered linked
230/// lists along which the reference point is being moved.
231///
232/// To determine N-dimensional containment of the reference point, the result of each of the one-dimensional
233/// point-on-line tests simply has to be combined.  If the point lies on each of N 1D segments of a
234/// given volume, then the point is fully contained in the volume.
235///
236/// This class may be used in places where otherwise a spatial subdivision scheme would be necessary in
237/// order to limit the number of containment tests triggered by each movement of the reference point.
238/// Once the tracker has been set up, each position change of an object or the reference center will result
239/// in a usually small number of incremental list updates.
240///
241/// Another advantage is that this class makes it easy to reduce 3D tracking to 2D tracking if tracking on
242/// the height axis isn't important.
243///
244/// The following interface must be implemented by the given "Object" type:
245///
246/// @code
247/// struct Object : public ScopeTrackerObject< NUM_DIMENSIONS >
248/// {
249///    /// Return the position of the object in world-space.
250///    void getPosition( F32 pos[ NUM_DIMENSIONS ] ) const;
251///
252///    /// If this object is the reference object, this method should return the world-space pivot
253///    /// point in the object that will be the world reference center.
254///    void getReferenceCenter( F32 pos[ NUM_DIMENSIONS ] ) const;
255///
256///    /// Return the object's bounding box in world-space.
257///    void getBounds( F32 minBounds[ NUM_DIMENSIONS ], F32 maxBounds[ NUM_DIMENSIONS ] ) const;
258/// };
259/// @endcode
260///
261/// Terminology:
262///
263/// - "In Scope": A volume is in scope if it fully contains the reference center.
264/// - "Reference Object": Object that is the designated center of the world. 
265///
266/// @param NUM_DIMENSIONS Number of dimensions to track; must be <=4.
267/// @param Object Value type for objects tracked by the ScopeTracker.  Must have pointer behavior.
268template< S32 NUM_DIMENSIONS, typename Object >
269class ScopeTracker
270{
271   public:
272   
273      typedef void Parent;
274      typedef typename TypeTraits< Object >::BaseType ObjectType;
275      typedef typename ObjectType::TrackingNode NodeType;
276   
277   protected:
278   
279      enum
280      {
281         MIN = 0,
282         MAX = 1
283      };
284            
285      /// The reference object.  This is the center relative to which all
286      /// tracking occurs.  Any other object is in scope when it contains the
287      /// reference object.
288      Object mReferenceObject;
289      
290      ///
291      NodeType* mTrackingList[ NUM_DIMENSIONS ][ 2 ];
292      
293      ///
294      NodeType mBoundaryNodes[ NUM_DIMENSIONS ][ 2 ];
295      
296      ///
297      Vector< Object> mPotentialScopeInObjects;
298      
299      /// @name Scoping
300      /// @{
301      
302      virtual void _onScopeIn( Object object ) {}
303      
304      virtual void _onScopeOut( Object object ) {}
305      
306      /// Set the scoping state of the given object.
307      void _setScope( Object object );
308      
309      /// @}
310      
311      /// @name Tracking
312      /// @{
313
314      ///
315      void _insertTrackingNode( U32 dimension, NodeType* node );
316      
317      ///
318      void _removeTrackingNode( U32 dimension, NodeType* node );
319      
320      ///
321      void _moveTrackingNode( U32 dimension, NodeType* node, F32 newPos );
322      
323      ///
324      void _initTracking();
325      
326      ///
327      void _uninitTracking();
328            
329      /// @}
330   
331   public:
332   
333      ///
334      ScopeTracker();
335   
336      /// Add a volume object to the world.
337      void registerObject( Object object );
338      
339      /// Remove a volume object from the world.
340      void unregisterObject( Object object );
341      
342      /// Update the position of the object in the world.
343      void updateObject( Object object );
344      
345      ///
346      Object getReferenceObject() const { return mReferenceObject; }
347      
348      ///
349      ///
350      /// @note Switching reference centers is potentially costly.
351      void setReferenceObject( Object object );
352      
353      ///
354      void debugDump();
355};
356
357
358//-----------------------------------------------------------------------------
359
360template< S32 NUM_DIMENSIONS, class Object >
361ScopeTracker< NUM_DIMENSIONS, Object >::ScopeTracker()
362   : mReferenceObject( NULL )
363{
364   VECTOR_SET_ASSOCIATION( mPotentialScopeInObjects );
365   
366   // Initialize the tracking lists.  Put the boundary
367   // nodes in place that will always be the heads and tails
368   // of each list.
369   
370   dMemset( mTrackingList, 0, sizeof( mTrackingList ) );
371   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
372   {
373      mBoundaryNodes[ n ][ MIN ].setPosition( TypeTraits< F32 >::MIN );
374      mBoundaryNodes[ n ][ MAX ].setPosition( TypeTraits< F32 >::MAX );
375      
376      mBoundaryNodes[ n ][ MIN ].setNext( &mBoundaryNodes[ n ][ MAX ] );
377      mBoundaryNodes[ n ][ MAX ].setPrev( &mBoundaryNodes[ n ][ MIN ] );
378      
379      mBoundaryNodes[ n ][ MIN ].mOpposite = &mBoundaryNodes[ n ][ MAX ];
380      mBoundaryNodes[ n ][ MAX ].mOpposite = &mBoundaryNodes[ n ][ MIN ];
381            
382      mTrackingList[ n ][ MIN ] = &mBoundaryNodes[ n ][ MIN ];
383      mTrackingList[ n ][ MAX ] = &mBoundaryNodes[ n ][ MAX ];
384   }
385}
386
387//-----------------------------------------------------------------------------
388
389template< S32 NUM_DIMENSIONS, class Object >
390void ScopeTracker< NUM_DIMENSIONS, Object >::setReferenceObject( Object object )
391{
392   AssertFatal( !object || !Deref( object ).isRegistered(),
393      "ScopeTracker::setReferenceObject - reference object must not be volume object" );
394      
395   if( mReferenceObject == object )
396      return;
397      
398   // If object is invalid, remove the reference center
399   // tracking.
400
401   if( !object )
402   {
403      // Transition all objects to out-of-scope and
404      // deactivate tracking.
405
406      _uninitTracking();
407      mReferenceObject = object;
408      return;
409   }
410
411   if( mReferenceObject )
412   {
413      //RDFIXME: this is very disruptive
414      
415      // We have an existing reference object so we need to update
416      // the scoping to match it.  Brute-force this for now.
417
418      _uninitTracking();
419      mReferenceObject = object;
420      _initTracking();      
421   }
422   else
423   {
424      // No reference object yet.
425
426      mReferenceObject = object;
427      _initTracking();
428   }
429   
430   #ifdef DEBUG_SPEW
431   Platform::outputDebugString( "[ScopeTracker] Reference object is now 0x%x", object );
432   #endif
433}
434
435//-----------------------------------------------------------------------------
436
437template< S32 NUM_DIMENSIONS, class Object >
438void ScopeTracker< NUM_DIMENSIONS, Object >::registerObject( Object object )
439{
440   PROFILE_SCOPE( ScopeTracker_registerObject );
441   
442   // Get the object bounds.
443   
444   F32 minBounds[ NUM_DIMENSIONS ];
445   F32 maxBounds[ NUM_DIMENSIONS ];
446   
447   Deref( object ).getBounds( minBounds, maxBounds );
448   
449   // Insert the object's tracking nodes.
450
451   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
452   {
453      NodeType* minNode = Deref( object ).getMinTrackingNode( n );
454      NodeType* maxNode = Deref( object ).getMaxTrackingNode( n );
455
456      minNode->setPosition( minBounds[ n ] );
457      maxNode->setPosition( maxBounds[ n ] );
458      
459      // Insert max before min so that max always comes out
460      // to the right of min.
461
462      _insertTrackingNode( n, maxNode );
463      _insertTrackingNode( n, minNode );
464   }
465   
466   // Set the scoping state of the object.
467   
468   _setScope( object );
469}
470
471//-----------------------------------------------------------------------------
472
473template< S32 NUM_DIMENSIONS, class Object >
474void ScopeTracker< NUM_DIMENSIONS, Object >::unregisterObject( Object object )
475{
476   PROFILE_SCOPE( ScopeTracker_unregisterObject );
477   
478   if( !Deref( object ).isRegistered() )
479      return;
480      
481   // Clear its scoping state.
482   
483   if( Deref( object ).isInScope() )
484      _onScopeOut( object );
485   Deref( object ).clearScopeMask();
486   
487   // Remove the tracking state.
488
489   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
490   {
491      _removeTrackingNode( n, Deref( object ).getMinTrackingNode( n ) );
492      _removeTrackingNode( n, Deref( object ).getMaxTrackingNode( n ) );
493   }
494}
495
496//-----------------------------------------------------------------------------
497
498template< S32 NUM_DIMENSIONS, class Object >
499void ScopeTracker< NUM_DIMENSIONS, Object >::updateObject( Object object )
500{
501   PROFILE_SCOPE( ScopeTracker_updateObject );
502   
503   if( object == mReferenceObject )
504   {
505      // Get the reference center position.
506      
507      F32 position[ NUM_DIMENSIONS ];
508      Deref( mReferenceObject ).getReferenceCenter( position );
509      
510      // Move the reference tracking node.
511      
512      for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
513         _moveTrackingNode( n, Deref( mReferenceObject ).getMinTrackingNode( n ), position[ n ] );
514         
515      // Flush the potential-scope-in list.
516      
517      while( !mPotentialScopeInObjects.empty() )
518      {
519         Object obj = mPotentialScopeInObjects.last();
520         mPotentialScopeInObjects.decrement();
521         
522         if( Deref(obj).isInScope() )
523            _onScopeIn(obj);
524      }
525   }
526   else
527   {
528      // Get the object bounds.
529      
530      F32 minBounds[ NUM_DIMENSIONS ];
531      F32 maxBounds[ NUM_DIMENSIONS ];
532      
533      Deref( object ).getBounds( minBounds, maxBounds );
534      
535      // Move the object's tracking nodes.
536
537      bool wasInScope = Deref( object ).isInScope();
538      for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
539      {
540         NodeType* minNode = Deref( object ).getMinTrackingNode( n );
541         NodeType* maxNode = Deref( object ).getMaxTrackingNode( n );
542
543         _moveTrackingNode( n, minNode, minBounds[ n ] );
544         _moveTrackingNode( n, maxNode, maxBounds[ n ] );
545      }
546      
547      // Rescope the object, if necessary.
548      
549      if( wasInScope && !Deref( object ).isInScope() )
550         _onScopeOut( object );
551      else if( !wasInScope && Deref( object ).isInScope() )
552         _onScopeIn( object );
553   }
554}
555
556//-----------------------------------------------------------------------------
557
558template< S32 NUM_DIMENSIONS, class Object >
559void ScopeTracker< NUM_DIMENSIONS, Object >::_insertTrackingNode( U32 dimension, NodeType* node )
560{
561   //RDTODO: substitute brute-force search with some smarter insertion algorithm
562   // (at least dynamically decide on direction for search)
563
564   F32        pos      = node->getPosition();
565   NodeType*  current  = mTrackingList[ dimension ][ MIN ]->getNext();
566   NodeType*  prev     = mTrackingList[ dimension ][ MIN ];
567
568   while( current->getPosition() < pos )
569   {
570        prev      = current;
571        current   = current->getNext();
572   }
573   
574   prev->setNext( node );
575   current->setPrev( node );
576
577   node->setPrev( prev );
578   node->setNext( current );
579}
580
581//-----------------------------------------------------------------------------
582
583template< S32 NUM_DIMENSIONS, class Object >
584void ScopeTracker< NUM_DIMENSIONS, Object >::_removeTrackingNode( U32 dimension, NodeType* node )
585{
586   NodeType* next = node->getNext();
587   NodeType* prev = node->getPrev();
588   
589   AssertFatal( next != NULL, "ScopeTracker::_insertTrackingNode - invalid list state (no next node)!" );
590   AssertFatal( prev != NULL, "ScopeTracker::_insertTrackingNode - invalid list state (no prev node)!" );
591
592   next->setPrev( prev );
593   prev->setNext( next );
594   
595   node->setNext( NULL );
596   node->setPrev( NULL );
597}
598
599//-----------------------------------------------------------------------------
600
601template< S32 NUM_DIMENSIONS, class Object >
602void ScopeTracker< NUM_DIMENSIONS, Object >::_moveTrackingNode( U32 dimension, NodeType* node, F32 newPosition )
603{
604   PROFILE_SCOPE( ScopeTracker_moveTrackingNode );
605   
606   AssertFatal( TypeTraits< F32 >::MIN <= newPosition && newPosition <= TypeTraits< F32 >::MAX, "Invalid float in object coordinate!" );
607
608   enum EDirection
609   {
610      DIRECTION_Up,
611      DIRECTION_Down
612   };
613
614   // Determine in which direction we are sliding the node.
615
616   EDirection direction;
617   if( newPosition < node->getPosition() )
618   {
619      direction = DIRECTION_Down;
620      if( node->getPrev()->getPosition() <= newPosition )
621      {
622         node->setPosition( newPosition );
623         return; // Nothing to do.
624      }
625   }
626   else if( newPosition > node->getPosition() )
627   {
628      direction = DIRECTION_Up;
629      if( node->getNext()->getPosition() >= newPosition )
630      {
631         node->setPosition( newPosition );
632         return; // Nothing to do.
633      }
634   }
635   else
636      return; // Nothing to to.
637
638   const bool isReferenceNode = node->isReference();
639   
640   // Unlink the node.
641
642   NodeType* next = node->getNext();
643   NodeType* prev = node->getPrev();
644   
645   next->setPrev( prev );
646   prev->setNext( next );
647
648   // Iterate through to the node's new position.
649   
650   while(    ( direction == DIRECTION_Up && next->getPosition() < newPosition )
651          || ( direction == DIRECTION_Down && prev->getPosition() > newPosition ) )
652   {
653      NodeType* current = 0;
654      switch( direction )
655      {
656         case DIRECTION_Up:   current = next; break;
657         case DIRECTION_Down: current = prev; break;
658      }
659
660      if( isReferenceNode )
661      {
662         Object object = ( Object ) current->getObject();
663         if(    ( direction == DIRECTION_Up && current->isMin() )
664             || ( direction == DIRECTION_Down && current->isMax() ) )
665         {
666            Deref( object ).setInScope( dimension, true );
667            mPotentialScopeInObjects.push_back( object );
668         }
669         else
670         {
671            const bool wasInScope = Deref( object ).isInScope();
672            Deref( object ).setInScope( dimension, false );
673            if( wasInScope )
674               _onScopeOut( object );
675         }
676      }
677      else
678      {
679         if( current->isReference() )
680         {
681            Object object = ( Object ) node->getObject();
682            if(    ( direction == DIRECTION_Up && node->isMin() )
683                || ( direction == DIRECTION_Down && node->isMax() ) )
684               Deref( object ).setInScope( dimension, false );
685            else
686               Deref( object ).setInScope( dimension, true );
687         }
688      }
689      
690      switch( direction )
691      {
692         case DIRECTION_Down:
693            next = current;
694            prev = current->getPrev();
695            break;
696            
697         case DIRECTION_Up:
698            prev = current;
699            next = current->getNext();
700            break;
701      }
702   }
703   
704   // Relink the node.
705
706   prev->setNext( node );
707   next->setPrev( node );
708   
709   node->setPrev( prev );
710   node->setNext( next );
711
712   node->setPosition( newPosition );
713}
714
715//-----------------------------------------------------------------------------
716
717template< S32 NUM_DIMENSIONS, class Object >
718void ScopeTracker< NUM_DIMENSIONS, Object >::_setScope( Object object )
719{
720   // If there's no reference object, all objects are out of scope.
721   
722   if( !mReferenceObject || object == mReferenceObject )
723   {
724      Deref( object ).clearScopeMask();
725      return;
726   }
727
728   const bool wasInScope = Deref( object ).isInScope();
729
730   // Set the scoping state on each axis.
731   
732   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
733   {
734      const F32 referencePos  = Deref( mReferenceObject ).getMinTrackingNode( n )->getPosition();
735      const F32 objectMin     = Deref( object ).getMinTrackingNode( n )->getPosition();
736      const F32 objectMax     = Deref( object ).getMaxTrackingNode( n )->getPosition();
737
738      bool isInScope =  referencePos >= objectMin
739                     && referencePos <= objectMax;
740      
741      Deref( object ).setInScope( n, isInScope );
742   }
743   
744   // Scope in/out if the scoping state has changed.
745   
746   if( Deref( object ).isInScope() )
747   {
748      if( !wasInScope )
749         _onScopeIn( object );
750   }
751   else
752   {
753      if( wasInScope )
754         _onScopeOut( object );
755   }
756}
757
758//-----------------------------------------------------------------------------
759
760template< S32 NUM_DIMENSIONS, class Object >
761void ScopeTracker< NUM_DIMENSIONS, Object >::_initTracking()
762{
763   PROFILE_SCOPE( ScopeTracker_initTracking );
764   
765   AssertFatal( bool( getReferenceObject() ),
766      "ScopeTracker::_initTracking - can only be called with a valid reference object" );
767      
768   // Put a single tracking node onto each of the lists for
769   // the reference object center.
770      
771   F32 position[ NUM_DIMENSIONS ];
772   Deref( mReferenceObject ).getReferenceCenter( position );
773   
774   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
775   {
776      AssertFatal( TypeTraits< F32 >::MIN <= position[ n ] && position[ n ] <= TypeTraits< F32 >::MAX, "Invalid float in object coordinate!" );
777
778      NodeType* node = Deref( mReferenceObject ).getMinTrackingNode( n );
779      node->mFlags.set( NodeType::FLAG_Reference );
780      
781      node->setPosition( position[ n ] );
782      
783      _insertTrackingNode( n, node );
784   }
785
786   // Update the surroundings of the reference object
787   // in the tracking lists for each dimension.
788   
789   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
790   {
791      //TODO: this could be optimized by dynamically determining whether to walk upwards
792      // or downwards depending on which span has fewer nodes; finding that out is not immediately
793      // obvious, though
794      
795      // Walk from the left bound node upwards until we reach the
796      // reference object's marker.  Everything that has its max node
797      // past the reference object is in scope.
798      
799      F32 referencePos = Deref( mReferenceObject ).getMinTrackingNode( n )->getPosition();
800      for( NodeType* node = mTrackingList[ n ][ 0 ]->getNext(); node->getPosition() < referencePos; node = node->getNext() )
801         if( !node->isMax() && node->getOpposite()->getPosition() > referencePos )
802         {
803            node->getObject()->setInScope( n, true );
804            
805            // If this is the last dimension we're working on and
806            // the current object is in-scope on all dimension,
807            // promote to in-scope status.
808            
809            if( n == ( NUM_DIMENSIONS - 1 ) && node->getObject()->isInScope() )
810               _onScopeIn( ( Object ) node->getObject() );
811         }
812   }
813}
814
815//-----------------------------------------------------------------------------
816
817template< S32 NUM_DIMENSIONS, class Object >
818void ScopeTracker< NUM_DIMENSIONS, Object >::_uninitTracking()
819{
820   PROFILE_SCOPE( ScopeTracker_uninitTracking );
821   
822   AssertFatal( bool( getReferenceObject() ),
823      "ScopeTracker::_uninitTracking - can only be called with a valid reference object" );
824      
825   // Put all objects currently in scope, out of scope.
826      
827   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
828   {
829      U32 referencePos = Deref( mReferenceObject ).getMinTrackingNode( n )->getPosition();
830      for( NodeType* node = mTrackingList[ n ][ 0 ]->getNext(); node->getPosition() < referencePos; node = node->getNext() )
831      {
832         if( node->getObject()->isInScope() )
833            _onScopeOut( ( Object ) node->getObject() );
834         node->getObject()->clearScopeMask();
835      }
836   }
837   
838   // Remove the reference object's tracking nodes.
839   
840   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
841      _removeTrackingNode( n, Deref( mReferenceObject ).getMinTrackingNode( n ) );
842}
843
844//-----------------------------------------------------------------------------
845
846template< S32 NUM_DIMENSIONS, class Object >
847void ScopeTracker< NUM_DIMENSIONS, Object >::debugDump()
848{
849   for( U32 n = 0; n < NUM_DIMENSIONS; ++ n )
850   {
851      Con::printf( "Dimension %i", n );
852      Con::printf( "----------------" );
853      
854      for( NodeType* node = mTrackingList[ n ][ 0 ]; node != NULL; node = node->getNext() )
855      {
856         String desc;
857         if( node->getObject() )
858         {
859            Object object = ( Object ) node->getObject();
860            desc = Deref( object ).describeSelf();
861         }
862
863         Con::printf( "pos=%f, type=%s, scope=%s, object=%s",
864            node->getPosition(),
865            node->isReference() ? "reference" : node->isMin() ? "min" : "max",
866            node->getObject() ? node->getObject()->isInScope( n ) ? "1" : "0" : "0",
867            desc.c_str() );
868      }
869      
870      Con::printf( "" );
871   }
872}
873
874#endif // !_SCOPETRACKER_H_
875