sceneZoneSpaceManager.cpp

Engine/source/scene/zones/sceneZoneSpaceManager.cpp

More...

Detailed Description

  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#include "platform/platform.h"
 25#include "scene/zones/sceneZoneSpaceManager.h"
 26
 27#include "platform/profiler.h"
 28#include "platform/platformMemory.h"
 29#include "scene/sceneContainer.h"
 30#include "scene/zones/sceneRootZone.h"
 31#include "scene/zones/sceneZoneSpace.h"
 32
 33
 34// Uncomment to enable verification code for debugging.  This slows the
 35// manager down significantly but will allow to find zoning state corruption
 36// much quicker.
 37//#define DEBUG_VERIFY
 38
 39//#define DEBUG_SPEW
 40
 41
 42ClassChunker< SceneObject::ZoneRef> SceneZoneSpaceManager::smZoneRefChunker;
 43
 44
 45//-----------------------------------------------------------------------------
 46
 47SceneZoneSpaceManager::SceneZoneSpaceManager( SceneContainer* container )
 48   : mRootZone( new SceneRootZone() ),
 49     mContainer( container ),
 50     mNumTotalAllocatedZones( 0 ),
 51     mNumActiveZones( 0 ),
 52     mDirtyArea( Box3F::Invalid )
 53{
 54   VECTOR_SET_ASSOCIATION( mZoneSpaces );
 55   VECTOR_SET_ASSOCIATION( mZoneLists );
 56   VECTOR_SET_ASSOCIATION( mZoneSpacesQueryList );
 57   VECTOR_SET_ASSOCIATION( mDirtyObjects );
 58   VECTOR_SET_ASSOCIATION( mDirtyZoneSpaces );
 59}
 60
 61//-----------------------------------------------------------------------------
 62
 63SceneZoneSpaceManager::~SceneZoneSpaceManager()
 64{
 65   // Delete root zone.
 66   SAFE_DELETE( mRootZone );
 67
 68   mNumTotalAllocatedZones = 0;
 69   mNumActiveZones = 0; 
 70}
 71
 72//-----------------------------------------------------------------------------
 73
 74void SceneZoneSpaceManager::registerZones( SceneZoneSpace* object, U32 numZones )
 75{
 76   AssertFatal( _getZoneSpaceIndex( object ) == -1, "SceneZoneSpaceManager::registerZones - Object already registered" );
 77   _compactZonesCheck();
 78
 79   const U32 zoneRangeStart = mNumTotalAllocatedZones;
 80
 81   mNumTotalAllocatedZones += numZones;
 82   mNumActiveZones += numZones;
 83
 84   object->mNumZones = numZones;
 85   object->mZoneRangeStart = zoneRangeStart;
 86
 87   // Allocate zone lists for all of the zones managed by the object.
 88   // Add an entry to each list that points back to the zone space.
 89
 90   mZoneLists.increment( numZones );
 91   for( U32 i = zoneRangeStart; i < mNumTotalAllocatedZones; ++ i )
 92   {
 93      SceneObject::ZoneRef* zoneRef = smZoneRefChunker.alloc();
 94
 95      zoneRef->object    = object;
 96      zoneRef->nextInBin = NULL;
 97      zoneRef->prevInBin = NULL;
 98      zoneRef->nextInObj = NULL;
 99      zoneRef->zone      = i;
100
101      mZoneLists[ i ] = zoneRef;
102   }
103
104   // Add space to list.
105
106   mZoneSpaces.push_back( object );
107   object->mManager = this;
108
109   // Set ZoneObjectType.
110
111   object->mTypeMask |= ZoneObjectType;
112
113   // Put the object on the dirty list.
114
115   if( !object->isRootZone() )
116   {
117      // Make sure the object gets on the zone space list even
118      // if it is already on the object dirty list.
119      object->mZoneRefDirty = false;
120
121      notifyObjectChanged( object );
122   }
123
124   #ifdef DEBUG_SPEW
125   Platform::outputDebugString( "[SceneZoneSpaceManager] Range %i-%i allocated to: %s",
126      zoneRangeStart, numZones, object->describeSelf().c_str() );
127   #endif
128}
129
130//-----------------------------------------------------------------------------
131
132void SceneZoneSpaceManager::unregisterZones( SceneZoneSpace* object )
133{
134   S32 zoneSpaceIndex = _getZoneSpaceIndex( object );
135   
136   AssertFatal( zoneSpaceIndex != -1, "SceneZoneSpaceManager::unregisterZones - Object not registered as zone space" );
137   AssertFatal( mNumActiveZones >= object->mNumZones, "SceneZoneSpaceManager::unregisterZones - Too many zones removed");
138
139   const U32 zoneRangeStart = object->getZoneRangeStart();
140   const U32 numZones = object->getZoneRange();
141
142   // Destroy the zone lists for the zones registered
143   // by the object.
144
145   for( U32 j = zoneRangeStart; j < zoneRangeStart + numZones; j ++ )
146   {
147      // Delete all object links.
148
149      _clearZoneList( j );
150
151      // Delete the first link which refers to the zone itself.
152
153      smZoneRefChunker.free( mZoneLists[ j ] );
154      mZoneLists[ j ] = NULL;
155   }
156
157   // Destroy the connections the zone space has.
158
159   object->_disconnectAllZoneSpaces();
160
161   // Remove the zone manager entry.
162
163   mNumActiveZones -= numZones;
164   mZoneSpaces.erase( zoneSpaceIndex );
165
166   // Clear ZoneObjectType.
167
168   object->mTypeMask &= ~<a href="/coding/file/objecttypes_8h/#objecttypes_8h_1ac18d4a11e9446825e48fd474d7529084ac49bd3304f0dd3ac67e1ba5b0febabc5">ZoneObjectType</a>;
169
170   // Clear zone assignments.
171
172   object->mZoneRangeStart = InvalidZoneId;
173   object->mNumZones = 0;
174   object->mManager = NULL;
175
176   // Mark the zone space's area as dirty.
177
178   mDirtyArea.intersect( object->getWorldBox() );
179
180   #ifdef DEBUG_SPEW
181   Platform::outputDebugString( "[SceneZoneSpaceManager] Range %i-%i released from: %s",
182      zoneRangeStart, numZones, object->describeSelf().c_str() );
183   #endif
184}
185
186//-----------------------------------------------------------------------------
187
188void SceneZoneSpaceManager::_rezoneObjects( const Box3F& area )
189{
190   static Vector< SceneObject*> sObjects( __FILE__, __LINE__ );
191
192   // Find all objects in the area.  We cannot use the callback
193   // version here and directly trigger rezoning since the rezoning
194   // itself does a container query.
195
196   sObjects.clear();
197   mContainer->findObjectList( area, 0xFFFFFFFF, &sObjects );
198
199   // Rezone the objects.
200
201   const U32 numObjects = sObjects.size();
202   for( U32 i = 0; i < numObjects; ++ i )
203   {
204      SceneObject* object = sObjects[ i ];
205      if( object != getRootZone() )
206         _rezoneObject( object );
207   }
208}
209
210//-----------------------------------------------------------------------------
211
212void SceneZoneSpaceManager::_compactZonesCheck()
213{
214   if( mNumActiveZones > ( mNumTotalAllocatedZones / 2 ) )
215      return;
216
217   // Redistribute the zone IDs among the current zone spaces
218   // so that the range of IDs is consecutive.
219
220   const U32 numZoneSpaces = mZoneSpaces.size();
221   U32 nextZoneId = 0;
222   
223   Vector< SceneObject::ZoneRef*> newZoneLists;
224   newZoneLists.setSize( mNumActiveZones );
225
226   for( U32 i = 0; i < numZoneSpaces; ++ i )
227   {
228      SceneZoneSpace* space = mZoneSpaces[ i ];
229
230      const U32 oldZoneRangeStart = space->getZoneRangeStart();
231      const U32 newZoneRangeStart = nextZoneId;
232      const U32 numZones = space->getZoneRange();
233
234      // Assign the new zone range start.
235
236      space->mZoneRangeStart = newZoneRangeStart;
237      nextZoneId += numZones;
238
239      // Relocate the zone lists to match the new zone IDs and update
240      // the contents of the zone lists to match the new IDs.
241
242      for( U32 n = 0; n < numZones; ++ n )
243      {
244         const U32 newZoneId = newZoneRangeStart + n;
245         const U32 oldZoneId = oldZoneRangeStart + n;
246
247         // Relocate list.
248
249         newZoneLists[ newZoneId ] = mZoneLists[ oldZoneId ];
250
251         // Update entries.
252
253         for( SceneObject::ZoneRef* ref = newZoneLists[ newZoneId ]; ref != NULL; ref = ref->nextInBin )
254            ref->zone = newZoneId;
255      }
256   }
257
258   mNumTotalAllocatedZones = nextZoneId;
259   mZoneLists = newZoneLists;
260
261   AssertFatal( mNumTotalAllocatedZones == mNumActiveZones, "SceneZoneSpaceManager::_compactZonesCheck - Error during compact; mismatch between active and allocated zones" );
262}
263
264//-----------------------------------------------------------------------------
265
266S32 SceneZoneSpaceManager::_getZoneSpaceIndex( SceneZoneSpace* object ) const
267{
268   const U32 numZoneSpaces = getNumZoneSpaces();
269   for( U32 i = 0; i < numZoneSpaces; ++ i )
270      if( mZoneSpaces[ i ] == object )
271         return i;
272
273   return -1;
274}
275
276//-----------------------------------------------------------------------------
277
278void SceneZoneSpaceManager::findZone( const Point3F& p, SceneZoneSpace*& owner, U32& zone ) const
279{
280   AssertFatal( mNumActiveZones >= 1, "SceneZoneSpaceManager::findZone - Must have at least one active zone in scene (outdoor zone)" );
281
282   // If there are no zones in the level other than the outdoor
283   // zone, just return that.
284
285   if( mNumActiveZones == 1 )
286   {
287      owner = getRootZone();
288      zone = RootZoneId;
289
290      return;
291   }
292   
293   PROFILE_SCOPE( SceneZoneSpaceManager_findZone );
294
295   // Query the scene container for zones with a query
296   // box that tightly fits around the point.
297
298   Box3F queryBox(   p.x - 0.1f, p.y - 0.1f, p.z - 0.1f,
299                     p.x + 0.1f, p.y + 0.1f, p.z + 0.1f );
300
301   _queryZoneSpaces( queryBox );
302
303   // Go through the zones and look for the first one that
304   // contains the given point.
305
306   const U32 numZones = mZoneSpacesQueryList.size();
307   for( U32 i = 0; i < numZones; ++ i )
308   {
309      SceneZoneSpace* zoneSpace = dynamic_cast< SceneZoneSpace* >( mZoneSpacesQueryList[ i ] );
310      if( !zoneSpace )
311         continue;
312
313      AssertFatal( zoneSpace != getRootZone(), "SceneZoneSpaceManager::findZone - SceneRootZone returned by zone manager query" );
314
315      // If the point is in one of the zones of this manager,
316      // then make this the result.
317
318      U32 inZone = zoneSpace->getPointZone( p );
319      if( inZone != InvalidZoneId )
320      {
321         owner = zoneSpace;
322         zone = inZone;
323
324         return;
325      }
326   }
327
328   // No other zone matched so return the outdoor zone.
329
330   owner = getRootZone();
331   zone = RootZoneId;
332}
333
334//-----------------------------------------------------------------------------
335
336U32 SceneZoneSpaceManager::findZones( const Box3F& area, Vector< U32>& outZones ) const
337{
338   // Query all zone spaces in the area.
339
340   _queryZoneSpaces( area );
341
342   // Query each zone space for overlaps with the given
343   // area and add the zones to outZones.
344
345   bool outsideIncluded = false;
346   U32 numTotalZones = 0;
347
348   const U32 numZoneSpaces = mZoneSpacesQueryList.size();
349   for( U32 i = 0; i < numZoneSpaces; ++ i )
350   {
351      SceneZoneSpace* zoneSpace = dynamic_cast< SceneZoneSpace* >( mZoneSpacesQueryList[ i ] );
352      if( !zoneSpace )
353         continue;
354
355      AssertFatal( zoneSpace != getRootZone(), "SceneZoneSpaceManager::findZones - SceneRootZone returned by zone manager query" );
356
357      // Query manager.
358
359      U32 zones[ SceneObject::MaxObjectZones ];
360      U32 numZones = 0;
361
362      outsideIncluded |= zoneSpace->getOverlappingZones( area, zones, numZones );
363
364      // Add overlapped zones.
365      
366      for( U32 n = 0; n < numZones; n ++ )
367      {
368         outZones.push_back( zones[ n ] );
369         numTotalZones ++;
370      }
371   }
372
373   // If the area box wasn't fully enclosed by the zones of the
374   // manager(s) or the query only returned the outside zone,
375   // add the outside zone to the list.
376
377   if( outsideIncluded || numTotalZones == 0 )
378   {
379      outZones.push_back( RootZoneId );
380      numTotalZones ++;
381   }
382
383   return numTotalZones;
384}
385
386//-----------------------------------------------------------------------------
387
388void SceneZoneSpaceManager::_rezoneObject( SceneObject* object )
389{
390   PROFILE_SCOPE( SceneZoneSpaceManager_rezoneObject );
391
392   AssertFatal( !dynamic_cast< SceneRootZone* >( object ), "SceneZoneSpaceManager::_rezoneObject - Cannot rezone the SceneRootZone!" );
393
394   // If the object is not yet assigned to zones,
395   // do so now and return.
396
397   if( !object->mNumCurrZones )
398   {
399      _zoneInsert( object );
400      return;
401   }
402
403   // If we have no zones in the scene other than the outdoor zone or if the
404   // object has global bounds on (and thus is always in the outdoor zone) or
405   // is an object that is restricted to the outdoor zone, leave the object's
406   // zoning state untouched.
407
408   if( mNumActiveZones == 1 || object->isGlobalBounds() || object->getTypeMask() & OUTDOOR_OBJECT_TYPEMASK )
409   {
410      object->mZoneRefDirty = false;
411      return;
412   }
413
414   // First, find out whether there's even a chance of the zoning to have changed
415   // for the object.
416
417   _queryZoneSpaces( object->getWorldBox() );
418
419   const U32 numZoneSpaces = mZoneSpacesQueryList.size();
420   if( !numZoneSpaces )
421   {
422      // There is no zone in the object's area.  If it is already assigned to the
423      // root zone, then we don't need an update.  Otherwise, we do.
424
425      if( object->mNumCurrZones == 1 &&
426          object->mZoneRefHead &&
427          object->mZoneRefHead->zone == RootZoneId )
428      {
429         object->mZoneRefDirty = false;
430         return;
431      }
432   }
433
434   // Update the object's zoning information by removing and recomputing
435   // its zoning information.
436
437   _zoneRemove( object );
438   _zoneInsert( object, true ); // Query already in place.
439}
440
441//-----------------------------------------------------------------------------
442
443void SceneZoneSpaceManager::registerObject( SceneObject* object )
444{
445   // Just put it on the dirty list.
446
447   notifyObjectChanged( object );
448}
449
450//-----------------------------------------------------------------------------
451
452void SceneZoneSpaceManager::unregisterObject( SceneObject* object )
453{
454   // Remove from dirty list.
455
456   mDirtyObjects.remove( object );
457
458   // Remove from zone lists.
459
460   _zoneRemove( object );
461
462   // If it's a zone space, unregister it.
463
464   if( object->getTypeMask() & ZoneObjectType && dynamic_cast< SceneZoneSpace* >( object ) )
465   {
466      SceneZoneSpace* zoneSpace = static_cast< SceneZoneSpace* >( object );
467      unregisterZones( zoneSpace );
468      mDirtyZoneSpaces.remove( zoneSpace );
469   }
470}
471
472//-----------------------------------------------------------------------------
473
474void SceneZoneSpaceManager::updateObject( SceneObject* object )
475{
476   // If no zone spaces have changed and the object's zoning
477   // state is clean, then there's nothing to do for this object.
478
479   if( mDirtyZoneSpaces.empty() && !object->mZoneRefDirty )
480      return;
481
482   // Otherwise update all the dirty zoning state.
483
484   updateZoningState();
485}
486
487//-----------------------------------------------------------------------------
488
489void SceneZoneSpaceManager::notifyObjectChanged( SceneObject* object )
490{
491   AssertFatal( object != getRootZone(), "SceneZoneSpaceManager::notifyObjectChanged - Cannot dirty root zone!" );
492
493   // Ignore if object is already on the dirty list.
494
495   if( object->mZoneRefDirty )
496      return;
497
498   // Put the object on the respective dirty list.
499
500   if( object->getTypeMask() & ZoneObjectType )
501   {
502      SceneZoneSpace* zoneSpace = dynamic_cast< SceneZoneSpace* >( object );
503      AssertFatal( zoneSpace != NULL, "SceneZoneSpaceManager::notifyObjectChanged - ZoneObjectType is not a SceneZoneSpace!" );
504
505      if( zoneSpace )
506         mDirtyZoneSpaces.push_back( zoneSpace );
507   }
508   else
509   {
510      mDirtyObjects.push_back( object );
511   }
512
513   // Mark object as dirty.
514
515   object->mZoneRefDirty = true;
516}
517
518//-----------------------------------------------------------------------------
519
520void SceneZoneSpaceManager::updateZoningState()
521{
522   // If there are no dirty objects, there's nothing to do.
523
524   if( mDirtyObjects.empty() &&
525       mDirtyZoneSpaces.empty() &&
526       mDirtyArea == Box3F::Invalid )
527      return;
528
529   // Otherwise, first update the zone spaces.  Do this in two passes:
530   // first take all the dirty zone spaces out of the zoning state and
531   // then rezone the combined area of all dirty zone spaces.
532   //
533   // Note that this path here is pretty much only relevant during loading
534   // or editing and thus can be less performant than the path for individual
535   // objects below.
536
537   while( !mDirtyZoneSpaces.empty() )
538   {
539      SceneZoneSpace* zoneSpace = mDirtyZoneSpaces.last();
540      mDirtyZoneSpaces.decrement();
541      
542      // Remove the zoning state of the object.
543
544      _zoneRemove( zoneSpace );
545
546      // Destroy all connections that this zone space has to
547      // other zone spaces.
548
549      zoneSpace->_disconnectAllZoneSpaces();
550
551      // Nuke its zone lists.
552
553      const U32 numZones = zoneSpace->getZoneRange();
554      for( U32 n = 0; n < numZones; ++ n )
555         _clearZoneList( zoneSpace->getZoneRangeStart() + n );
556
557      // Merge into dirty region.
558
559      mDirtyArea.intersect( zoneSpace->getWorldBox() );
560   }
561
562   if( mDirtyArea != Box3F::Invalid )
563   {
564      // Rezone everything in the dirty region.
565
566      _rezoneObjects( mDirtyArea );
567      mDirtyArea = Box3F::Invalid;
568
569      // Verify zoning state.
570
571      #ifdef DEBUG_VERIFY
572      verifyState();
573      #endif
574
575      // Fire the zoning changed signal to let interested parties
576      // know that the zoning setup of the scene has changed.
577
578      getZoningChangedSignal().trigger( this );
579   }
580
581   // And finally, update objects that have changed state.
582
583   while( !mDirtyObjects.empty() )
584   {
585      SceneObject* object = mDirtyObjects.last();
586      mDirtyObjects.decrement();
587
588      if( object->mZoneRefDirty )
589         _rezoneObject( object );
590
591      AssertFatal( !object->mZoneRefDirty, "SceneZoneSpaceManager::updateZoningState - Object still dirty!" );
592   }
593
594   AssertFatal( mDirtyObjects.empty(), "SceneZoneSpaceManager::updateZoningState - Still have dirty objects!" );
595   AssertFatal( mDirtyZoneSpaces.empty(), "SceneZoneSpaceManager::updateZoningState - Still have dirty zones!" );
596}
597
598//-----------------------------------------------------------------------------
599
600void SceneZoneSpaceManager::_zoneInsert( SceneObject* object, bool queryListInitialized ) 
601{
602   PROFILE_SCOPE( SceneZoneSpaceManager_zoneInsert );
603
604   AssertFatal( object->mNumCurrZones == 0, "SceneZoneSpaceManager::_zoneInsert - Object already in zone list" );
605   AssertFatal( object->getContainer() != NULL, "SceneZoneSpaceManager::_zoneInsert - Object must be in scene" );
606   AssertFatal( !dynamic_cast< SceneRootZone* >( object ), "SceneZoneSpaceManager::_zoneInsert - Must not be called on SceneRootZone" );
607
608   // If all we have is a single zone in the scene, then it must
609   // be the outdoor zone.  Simply assign the object to it.  Also do this
610   // if the object has global bounds on since we always assign these to
611   // just the outdoor zone.  Finally, also do it for all object types that
612   // we want to restrict to the outdoor zone.
613
614   if( mNumActiveZones == 1 || object->isGlobalBounds() || object->getTypeMask() & OUTDOOR_OBJECT_TYPEMASK )
615      _addToOutdoorZone( object );
616   else
617   {
618      // Otherwise find all zones spaces that intersect with the object's
619      // world box.
620
621      if( !queryListInitialized )
622         _queryZoneSpaces( object->getWorldBox() );
623
624      // Go through the zone spaces and link all zones that the object
625      // overlaps.
626
627      bool outsideIncluded = true;
628      const U32 numZoneSpaces = mZoneSpacesQueryList.size();
629      for( U32 i = 0; i < numZoneSpaces; ++ i )
630      {
631         SceneZoneSpace* zoneSpace = dynamic_cast< SceneZoneSpace* >( mZoneSpacesQueryList[ i ] );
632         if( !zoneSpace )
633            continue;
634
635         AssertFatal( zoneSpace != getRootZone(), "SceneZoneSpaceManager::_zoneInsert - SceneRootZone returned by zone space query" );
636
637         // If we are inserting a zone space, then the query will turn up
638         // the object itself at some point.  Skip it.
639
640         if( zoneSpace == object )
641            continue;
642
643         // Find the zones that the object overlaps within
644         // the zone space.
645
646         U32 numZones = 0;
647         U32 zones[ SceneObject::MaxObjectZones ];
648
649         bool overlapsOutside = zoneSpace->getOverlappingZones( object, zones, numZones );
650         AssertFatal( numZones != 0 || overlapsOutside,
651            "SceneZoneSpaceManager::_zoneInsert - Object must be fully contained in one or more zones or intersect the outside zone" );
652
653         outsideIncluded &= overlapsOutside; // Only include outside if *none* of the zones fully contains the object.
654
655         // Link the object to the zones.
656
657         for( U32 n = 0; n < numZones; ++ n )
658            _addToZoneList( zones[ n ], object );
659
660         // Let the zone manager know we have added objects to its
661         // zones.
662
663         if( numZones > 0 )
664            zoneSpace->_onZoneAddObject( object, zones, numZones );
665      }
666
667      // If the object crosses into the outside zone or hasn't been
668      // added to any zone above, add it to the outside zone.
669
670      if( outsideIncluded )
671         _addToOutdoorZone( object );
672   }
673
674   // Mark the zoning state of the object as current.
675
676   object->mZoneRefDirty = false;
677}
678
679//-----------------------------------------------------------------------------
680
681void SceneZoneSpaceManager::_zoneRemove( SceneObject* obj )
682{
683   PROFILE_SCOPE( SceneZoneSpaceManager_zoneRemove );
684
685   // Remove the object from the zone lists.
686
687   for( SceneObject::ZoneRef* walk = obj->mZoneRefHead; walk != NULL; )
688   {
689      // Let the zone owner know we are removing an object
690      // from its zones.
691
692      getZoneOwner( walk->zone )->_onZoneRemoveObject( walk->object );
693
694      // Now remove the ZoneRef link this object has in the
695      // zone list of the current zone.
696
697      SceneObject::ZoneRef* remove = walk;
698      walk = walk->nextInObj;
699
700      remove->prevInBin->nextInBin = remove->nextInBin;
701      if( remove->nextInBin )
702         remove->nextInBin->prevInBin = remove->prevInBin;
703
704      smZoneRefChunker.free( remove );
705   }
706
707   // Clear the object's zoning state.
708
709   obj->mZoneRefHead = NULL;
710   obj->mZoneRefDirty = false;
711   obj->mNumCurrZones = 0;
712}
713
714//-----------------------------------------------------------------------------
715
716void SceneZoneSpaceManager::_addToZoneList( U32 zoneId, SceneObject* object )
717{
718   SceneObject::ZoneRef* zoneList = mZoneLists[ zoneId ];
719
720   AssertFatal( zoneList != NULL, "SceneZoneSpaceManager::_addToZoneList - Zone list not initialized" );
721   AssertFatal( object != zoneList->object, "SCene::_addToZoneList - Cannot add zone to itself" );
722
723   SceneObject::ZoneRef* newRef = smZoneRefChunker.alloc();
724
725   // Add the object to the zone list.
726
727   newRef->zone      = zoneId;
728   newRef->object    = object;
729   newRef->nextInBin = zoneList->nextInBin;
730   newRef->prevInBin = zoneList;
731
732   if( zoneList->nextInBin )
733      zoneList->nextInBin->prevInBin = newRef;
734
735   zoneList->nextInBin = newRef;
736
737   // Add the zone to the object list.
738
739   newRef->nextInObj = object->mZoneRefHead;
740   object->mZoneRefHead = newRef;
741   object->mNumCurrZones ++;
742}
743
744//-----------------------------------------------------------------------------
745
746void SceneZoneSpaceManager::_clearZoneList( U32 zoneId )
747{
748   AssertFatal( zoneId < getNumZones(), "SceneZoneSpaceManager::_clearZoneList - Zone ID out of range" );
749
750   SceneObject::ZoneRef* list = mZoneLists[ zoneId ];
751   SceneZoneSpace* zoneSpace = getZoneOwner( zoneId );
752
753   // Go through the objects in the zone list and unlink and
754   // delete their zone entries.
755
756   for( SceneObject::ZoneRef* walk = list->nextInBin; walk != NULL; walk = walk->nextInBin )
757   {
758      SceneObject* object = walk->object;
759      AssertFatal( object != NULL, "SceneZoneSpaceManager::_clearZoneList - Object field not set on link" );
760
761      // The zone entry links on the objects are singly-linked lists
762      // linked through nextInObject so we need to find where in the
763      // objects zone entry list the node for the current zone is.
764
765      SceneObject::ZoneRef** ptrNext = &object->mZoneRefHead;
766      while( *ptrNext && *ptrNext != walk )
767         ptrNext = &( *ptrNext )->nextInObj;
768
769      AssertFatal( *ptrNext == walk, "SceneZoneSpaceManager::_clearZoneList - Zone entry not found on object in zone list!");
770
771      // Unlink and delete the entry.
772
773      *ptrNext = ( *ptrNext )->nextInObj;
774      smZoneRefChunker.free( walk );
775
776      object->mNumCurrZones --;
777
778      // If this is the only zone the object was in, mark
779      // its zoning state as dirty so it will get assigned
780      // to the outdoor zone on the next update.
781
782      if( !object->mZoneRefHead )
783         object->mZoneRefDirty = true;
784
785      // Let the zone know we have removed the object.
786
787      zoneSpace->_onZoneRemoveObject( object );
788   }
789
790   list->nextInBin = NULL;
791}
792
793//-----------------------------------------------------------------------------
794
795SceneObject::ZoneRef* SceneZoneSpaceManager::_findInZoneList( U32 zoneId, SceneObject* object ) const
796{
797   for( SceneObject::ZoneRef* ref = object->mZoneRefHead; ref != NULL; ref = ref->nextInObj )
798      if( ref->zone == zoneId )
799         return ref;
800
801   return NULL;
802}
803
804//-----------------------------------------------------------------------------
805
806void SceneZoneSpaceManager::_addToOutdoorZone( SceneObject* object )
807{
808   AssertFatal( !object->mZoneRefHead || !_findInZoneList( RootZoneId, object ),
809      "SceneZoneSpaceManager::_addToOutdoorZone - Object already added to outdoor zone" );
810
811   // Add the object to the outside's zone list.  This method is always called
812   // *last* after the object has already been assigned to any other zone it
813   // intersects.  Since we always prepend to the zoning lists, this means that
814   // the outdoor zone will always be *first* in the list of zones that an object
815   // is assigned to which generally is a good order.
816
817   _addToZoneList( RootZoneId, object );
818
819   // Let the zone know we added an object to it.
820
821   const U32 zoneId = RootZoneId;
822   static_cast< SceneZoneSpace* >( getRootZone() )->_onZoneAddObject( object, &zoneId, 1 );
823}
824
825//-----------------------------------------------------------------------------
826
827void SceneZoneSpaceManager::_queryZoneSpaces( const Box3F& area ) const
828{
829   mZoneSpacesQueryList.clear();
830   mContainer->findObjectList( area, ZoneObjectType, &mZoneSpacesQueryList );
831}
832
833//-----------------------------------------------------------------------------
834
835void SceneZoneSpaceManager::dumpZoneStates( bool update )
836{
837   if( update )
838      _rezoneObjects( getRootZone()->getWorldBox() );
839
840   const U32 numZoneSpaces = mZoneSpaces.size();
841   for( U32 i = 0; i < numZoneSpaces; ++ i )
842      mZoneSpaces[ i ]->dumpZoneState( false );
843}
844
845//-----------------------------------------------------------------------------
846
847void SceneZoneSpaceManager::verifyState()
848{
849   AssertFatal( mZoneSpaces.size() <= mNumActiveZones,
850      "SceneZoneSpaceManager::verifyState - More zone spaces than active zones!" );
851   AssertFatal( mNumTotalAllocatedZones >= mNumActiveZones,
852      "SceneZoneSpaceManager::verifyState - Fewer allocated than active zones!" );
853   AssertFatal( mRootZone->getZoneRangeStart() == 0,
854      "SceneZoneSpaceManager::verifyState - Invalid ID on root zone!" );
855   AssertFatal( mRootZone->getZoneRange() == 1,
856      "SceneZoneSpaceManager::verifyState - Invalid zone range on root zone!" );
857
858   // First validate the zone spaces themselves.
859
860   const U32 numZoneSpaces = mZoneSpaces.size();
861   for( U32 i = 0; i < numZoneSpaces; ++ i )
862   {
863      SceneZoneSpace* space = mZoneSpaces[ i ];
864
865      #ifndef TORQUE_DISABLE_MEMORY_MANAGER
866      Memory::checkPtr( space );
867      #endif
868
869      AssertFatal( space->getTypeMask() & ZoneObjectType, "SceneZoneSpaceManager::verifyState - Zone space is not a ZoneObjectType!" );
870
871      const U32 zoneRangeStart = space->getZoneRangeStart();
872      const U32 numZones = space->getZoneRange();
873
874      // Verify each of the allocated zones in this space.
875
876      for( U32 n = 0; n < numZones; ++ n )
877      {
878         const U32 zoneId = zoneRangeStart + n;
879
880         // Simple validation of zone ID.
881         AssertFatal( isValidZoneId( zoneId ), "SceneZoneSpaceManager::verifyState - Zone space is assigned in invalid zone ID!" );
882
883         AssertFatal( mZoneLists[ zoneId ] != NULL, "SceneZoneSpaceManager::verifyState - Zone list missing for zone!" );
884         AssertFatal( mZoneLists[ zoneId ]->object == space, "SceneZoneSpaceManager::verifyState - Zone list entry #0 is not referring back to zone!" );
885
886         for( SceneObject::ZoneRef* ref = mZoneLists[ zoneId ]; ref != NULL; ref = ref->nextInBin )
887         {
888            AssertFatal( ref->zone == zoneId, "SceneZoneSpaceManager::verifyState - Incorrect ID in zone list!" );
889            AssertFatal( ref->object != NULL, "SceneZoneSpaceManager::verifyState - Null object pointer in zone list!" );
890
891            #ifndef TORQUE_DISABLE_MEMORY_MANAGER
892            Memory::checkPtr( ref->object );
893            #endif
894         }
895      }
896
897      // Make sure no other zone space owns any of the same IDs.
898
899      for( U32 n = 0; n < numZoneSpaces; ++ n )
900      {
901         if( n == i )
902            continue;
903
904         SceneZoneSpace* otherSpace = mZoneSpaces[ n ];
905         AssertFatal( otherSpace->getZoneRangeStart() >= zoneRangeStart + numZones ||
906                      otherSpace->getZoneRangeStart() + otherSpace->getZoneRange() <= zoneRangeStart,
907            "SceneZoneSpaceManager::verifyState - Overlap between zone ID ranges of zone spaces!" );
908      }
909
910      // Make sure that all zone connections appear to be valid.
911
912      for( SceneZoneSpace::ZoneSpaceRef* ref = space->mConnectedZoneSpaces; ref != NULL; ref = ref->mNext )
913      {
914         #ifndef TORQUE_DISABLE_MEMORY_MANAGER
915         Memory::checkPtr( ref->mZoneSpace );
916         #endif
917
918         AssertFatal( _getZoneSpaceIndex( ref->mZoneSpace ) != -1, "SceneZoneSpaceManager::verifyState - Zone connected to invalid zone!" );
919         AssertFatal( ref->mZoneSpace->getTypeMask() & ZoneObjectType, "SceneZoneSpaceManager::verifyState - Zone space is not a ZoneObjectType!" );
920      }
921   }
922
923   //TODO: can do a lot more validation here
924}
925