scopeTracker.h
Engine/source/util/scopeTracker.h
A mechanism for continuous tracking of point/box intersections.
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