forestCell.cpp

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 "forest/forestCell.h"
 26
 27#include "forest/forest.h"
 28#include "forest/forestCellBatch.h"
 29#include "forest/forestCollision.h"
 30#include "T3D/physics/physicsPlugin.h"
 31#include "T3D/physics/physicsBody.h"
 32#include "T3D/physics/physicsCollision.h"
 33#include "collision/concretePolyList.h"
 34
 35#include "gfx/gfxDrawUtil.h"
 36#include "math/util/frustum.h"
 37
 38
 39ForestCell::ForestCell( const RectF &rect ) :
 40   mRect( rect ),
 41   mBounds( Box3F::Invalid ),
 42   mIsDirty( false ),
 43   mLargestItem( ForestItem::Invalid ),
 44   mIsInteriorOnly( false )
 45{
 46   dMemset( mSubCells, 0, sizeof( mSubCells ) );
 47   dMemset( mPhysicsRep, 0, sizeof( mPhysicsRep ) );
 48}
 49
 50ForestCell::~ForestCell()
 51{
 52   mItems.clear();
 53
 54   for ( U32 i=0; i < 4; i++ )
 55      SAFE_DELETE( mSubCells[i] );
 56
 57   freeBatches();
 58
 59   SAFE_DELETE( mPhysicsRep[0] );
 60   SAFE_DELETE( mPhysicsRep[1] );
 61}
 62
 63void ForestCell::freeBatches()
 64{
 65   for ( U32 i=0; i < mBatches.size(); i++ )
 66      SAFE_DELETE( mBatches[i] );
 67
 68   mBatches.clear();
 69}
 70
 71void ForestCell::buildBatches()
 72{
 73   // Gather items for batches.
 74   Vector<ForestItem> items;
 75   getItems( &items );
 76
 77   // Ask the item to batch itself.
 78   Vector<ForestItem>::const_iterator item = items.begin();
 79   bool batched = false;
 80   for ( ; item != items.end(); item++ )
 81   {
 82      // Loop thru the batches till someone 
 83      // takes this guy off our hands.
 84      batched = false;
 85      for ( S32 i=0; i < mBatches.size(); i++ )
 86      {
 87         if ( mBatches[i]->add( *item ) )
 88         {
 89            batched = true;
 90            break;
 91         }
 92      }
 93
 94      if ( batched )
 95         continue;
 96      
 97      // Gotta create a new batch.
 98      ForestCellBatch *batch = item->getData()->allocateBatch();
 99      if ( batch )
100      {
101         batch->add( *item );
102         mBatches.push_back( batch );
103      }
104   }
105}
106
107S32 ForestCell::renderBatches( SceneRenderState *state, Frustum *culler )
108{
109   PROFILE_SCOPE( ForestCell_renderBatches );
110
111   if ( !hasBatches() )
112      return 0;
113
114   S32 renderedItems = 0;
115
116   for ( S32 i=0; i < mBatches.size(); i++ )
117   {
118      // Is this batch entirely culled?
119      if ( culler && culler->isCulled( mBatches[i]->getWorldBox() ) )
120         continue;
121
122      if( state->getCullingState().isOccludedWithExtraPlanesCull( mBatches[i]->getWorldBox() ) )
123         continue;
124
125      mBatches[i]->render( state );
126      renderedItems += mBatches[i]->getItemCount();
127   }
128
129   return renderedItems;
130}
131
132S32 ForestCell::render( TSRenderState *rdata, const Frustum *culler )
133{
134   PROFILE_SCOPE( ForestCell_render );
135
136   AssertFatal( isLeaf(), "ForestCell::render() - This shouldn't be called on non-leaf cells!" );
137       
138   U32 itemsRendered = 0;
139
140   // TODO: Items are generated in order of type,
141   // so we can maybe save some overhead by preparing
142   // the item for rendering once.
143
144   Vector<ForestItem>::iterator item = mItems.begin();
145   for ( ; item != mItems.end(); item++ )
146   {
147      // Do we need to cull individual items?
148      if ( culler && culler->isCulled( item->getWorldBox() ) )
149         continue;
150
151      if ( item->getData()->render( rdata, *item ) )
152         ++itemsRendered;
153   }
154
155   return itemsRendered;
156}
157
158void ForestCell::_updateBounds()
159{   
160   mIsDirty = false;
161   mBounds = Box3F::Invalid;
162   mLargestItem = ForestItem::Invalid;
163
164   F32 radius;
165
166   if ( isBranch() )
167   {
168      for ( U32 i=0; i < 4; i++ )
169      {
170         mBounds.intersect( mSubCells[i]->getBounds() );
171
172         radius = mSubCells[i]->mLargestItem.getRadius();
173         if ( radius > mLargestItem.getRadius() )
174            mLargestItem = mSubCells[i]->mLargestItem;
175      }
176
177      return;
178   }
179
180   // Loop thru all the items in this cell.
181   Vector<ForestItem>::const_iterator item = mItems.begin();
182   for ( ; item != mItems.end(); item++ )
183   {
184      mBounds.intersect( (*item).getWorldBox() );
185
186      radius = (*item).getRadius();
187      if ( radius > mLargestItem.getRadius() )
188         mLargestItem = (*item);
189   }
190}
191
192void ForestCell::_updateZoning( const SceneZoneSpaceManager *zoneManager )
193{
194   PROFILE_SCOPE( ForestCell_UpdateZoning );
195
196   mZoneOverlap.setSize( zoneManager->getNumZones() );
197   mZoneOverlap.clear();
198   mIsInteriorOnly = true;
199
200   if ( isLeaf() )
201   {
202      // Skip empty cells... they don't have valid bounds.
203      if ( mItems.empty() )
204         return;
205
206      Vector<U32> zones;
207      zoneManager->findZones( getBounds(), zones );
208
209      for ( U32 i=0; i < zones.size(); i++ )
210      {
211         // Set overlap bit for zone except it's the outdoor zone.
212         if( zones[ i ] != SceneZoneSpaceManager::RootZoneId )
213            mZoneOverlap.set( zones[i] );
214         else
215            mIsInteriorOnly = false;
216      }
217
218      return;
219   }
220
221   for ( U32 i = 0; i < 4; i++ )
222   {
223      ForestCell *cell = mSubCells[i];
224      cell->_updateZoning( zoneManager );
225      mZoneOverlap.combineOR( cell->getZoneOverlap() );
226      mIsInteriorOnly &= cell->mIsInteriorOnly;
227   }
228}
229
230bool ForestCell::findIndexByKey( ForestItemKey key, U32 *outIndex ) const
231{
232   // Do a simple binary search.
233
234   U32   i = 0,
235         lo = 0,
236         hi = mItems.size();
237   
238   const ForestItem *items = mItems.address();
239
240   while ( lo < hi ) 
241   {
242      i = (lo + hi) / 2;
243
244      if ( key < items[i].getKey() )
245         hi = i;
246      else if ( key > items[i].getKey() )
247         lo = i + 1;
248      else
249      {
250         *outIndex = i;
251         return true;
252      }
253   }
254
255   *outIndex = lo;
256   return false;
257}
258
259const ForestItem& ForestCell::insertItem( ForestItemKey key,
260                                          ForestItemData *data,
261                                          const MatrixF &xfm,
262                                          F32 scale )
263{
264   AssertFatal( key != 0, "ForestCell::insertItem() - Got null key!" );
265   AssertFatal( data != NULL, "ForestCell::insertItem() - Got null datablock!" );
266
267   // Make sure we update the bounds later.
268   mIsDirty = true;
269
270   // PhysicsBody is now invalid and must be rebuilt later.
271   SAFE_DELETE( mPhysicsRep[0] );
272   SAFE_DELETE( mPhysicsRep[1] );
273
274   // Destroy batches so we recreate it on
275   // the next next render.
276   freeBatches();
277
278   // Ok... do we need to split this cell?
279   if ( isLeaf() && mItems.size() > MaxItems )
280   {
281      // Add the children.
282      for ( U32 i=0; i < 4; i++ )
283         mSubCells[i] = new ForestCell( _makeChildRect( i ) );
284
285      // Now push all our current children down.
286      Vector<ForestItem>::iterator item = mItems.begin();
287      for ( ; item != mItems.end(); item++ )
288      {
289         U32 index = _getSubCell( item->getPosition().x, item->getPosition().y );
290
291         mSubCells[index]->insertItem( item->getKey(), 
292                                       item->getData(), 
293                                       item->getTransform(), 
294                                       item->getScale() );
295      }
296
297      // Clean up.
298      mItems.clear();
299      mItems.compact();
300   }
301
302   // Do we have children?
303   if ( isBranch() )
304   {
305      // Ok... kick this item down then.
306      U32 index = _getSubCell( xfm.getPosition().x, xfm.getPosition().y );
307      const ForestItem &result = mSubCells[index]->insertItem( key, data, xfm, scale );
308
309      AssertFatal( index == _getSubCell( result.getPosition().x, result.getPosition().y ), "ForestCell::insertItem() - binning is hosed." );
310
311      return result;
312   }
313
314   // Do the datablock preload here to insure it happens
315   // before an item is used in the scene.
316   data->preload();
317
318   // First see if we can find it.  This is nifty so
319   // I'll explain it a bit more.
320   // 
321   // The find function does a binary search thru the
322   // sorted item list.
323   //
324   // If found the index is the position of the item.
325   // 
326   // If not found the index is the correct insertion 
327   // position for adding the new item.
328   //
329   // So not only do we have a fast find which is worst
330   // case O(log n)... but we also have the proper insert
331   // position to maintain a sorted item list.
332   //
333   U32 index;
334   bool found = findIndexByKey( key, &index );
335   
336   // If we didn't find one then insert it.
337   if ( !found )
338      mItems.insert( index );
339
340   // Update the item settings.
341   ForestItem &item = mItems[ index ];   
342   item.setData( data );
343   item.setTransform( xfm, scale );
344
345   if ( !found )
346      item.setKey( key );
347
348   return item;
349}
350
351bool ForestCell::removeItem( ForestItemKey key, const Point3F &keyPos, bool deleteIfEmpty )
352{
353   PROFILE_SCOPE( ForestCell_removeItem );
354
355   AssertFatal( key != 0, "ForestCell::removeItem() - Got null key!" );
356
357   // If this cell has no items then check the children.
358   if ( mItems.empty() )
359   {
360      // Let the child deal with it.
361      U32 index = _getSubCell( keyPos.x, keyPos.y );
362      if ( !mSubCells[index]->removeItem( key, keyPos, deleteIfEmpty ) )
363      {
364         // For debugging lets make sure we didn't pick the wrong subCell...
365         
366         return false;
367      }
368
369      // If requested by the caller delete our empty subcells.      
370      // Note that by deleting SubCell[0] we have become a leaf with no items
371      // and will return true to our parent's isEmpty test.
372      if ( deleteIfEmpty &&
373           mSubCells[0]->isEmpty() && 
374           mSubCells[1]->isEmpty() && 
375           mSubCells[2]->isEmpty() &&
376           mSubCells[3]->isEmpty() )
377      {
378         SAFE_DELETE( mSubCells[0] );
379         SAFE_DELETE( mSubCells[1] );
380         SAFE_DELETE( mSubCells[2] );
381         SAFE_DELETE( mSubCells[3] );
382      }
383   }
384   else
385   {
386      // First see if we can find it.
387      U32 index;
388      if ( !findIndexByKey( key, &index ) )
389         return false;
390
391      // Erase it.
392      mItems.erase( index );
393   }
394
395   // Do a full bounds update on the next request.
396   mIsDirty = true;
397
398   // PhysicsBody is now invalid and must be rebuilt later.
399   SAFE_DELETE( mPhysicsRep[0] );
400   SAFE_DELETE( mPhysicsRep[1] );
401
402   // Destroy batches so we recreate it on
403   // the next next render.
404   freeBatches();
405
406   return true;
407}
408
409void ForestCell::getItems( Vector<ForestItem> *outItems ) const
410{
411   Vector<const ForestCell*> stack;
412   stack.push_back( this );
413
414   // Now loop till we run out of cells.
415   while ( !stack.empty() )
416   {
417      // Pop off the next cell.
418      const ForestCell *cell = stack.last();
419      stack.pop_back();
420
421      // Recurse thru non-leaf cells.
422      if ( !cell->isLeaf() )
423      {
424         stack.merge( cell->mSubCells, 4 );
425         continue;
426      }
427
428      // Get the items.
429      outItems->merge( cell->getItems() );
430   }
431}
432
433void ForestCell::buildPhysicsRep( Forest *forest )
434{   
435   AssertFatal( isLeaf(), "ForestCell::buildPhysicsRep() - This shouldn't be called on non-leaf cells!" );
436
437   bool isServer = forest->isServerObject();
438
439   // Already has a PhysicsBody, if it needed to be rebuilt it would
440   // already be null.
441   if ( mPhysicsRep[ isServer ] )
442      return;   
443
444   if ( !PHYSICSMGR )
445      return;
446
447   PhysicsCollision *colShape = NULL;
448
449   // If we can steal the collision shape from the server-side cell   
450   // then do so as it saves us alot of cpu time and memory.
451   if ( mPhysicsRep[ 1 ] )
452   {      
453      colShape = mPhysicsRep[ 1 ]->getColShape();
454   }
455   else
456   {
457      // We must pass a sphere to buildPolyList but it is not used.
458      const static SphereF dummySphere( Point3F::Zero, 0 );       
459
460      // Step thru them and build collision data.
461      ForestItemVector::iterator itemItr = mItems.begin();
462      ConcretePolyList polyList;
463      for ( ; itemItr != mItems.end(); itemItr++ )
464      {
465         const ForestItem &item = *itemItr;
466         const ForestItemData *itemData = item.getData();
467         
468         // If not collidable don't need to build anything.
469         if ( !itemData->mCollidable )
470            continue;
471
472         // TODO: When we add breakable tree support this is where
473         // we would need to store their collision data seperately.
474
475         item.buildPolyList( &polyList, item.getWorldBox(), dummySphere );
476
477         // TODO: Need to support multiple collision shapes
478         // for really big forests at some point in the future.
479      }
480
481      if ( !polyList.isEmpty() )
482      {
483         colShape = PHYSICSMGR->createCollision();
484         if ( !colShape->addTriangleMesh( polyList.mVertexList.address(),
485                                          polyList.mVertexList.size(),
486                                          polyList.mIndexList.address(),
487                                          polyList.mIndexList.size() / 3,
488                                          MatrixF::Identity ) )
489         {
490            SAFE_DELETE( colShape );
491         }
492      }
493   }
494
495   // We might not have any trees.
496   if ( !colShape )
497      return;
498
499   PhysicsWorld *world = PHYSICSMGR->getWorld( isServer ? "server" : "client" );
500   mPhysicsRep[ isServer ] = PHYSICSMGR->createBody();
501   mPhysicsRep[ isServer ]->init( colShape, 0, 0, forest, world );
502}
503
504void ForestCell::clearPhysicsRep( Forest *forest )
505{
506   bool isServer = forest->isServerObject();
507
508   SAFE_DELETE( mPhysicsRep[ isServer ] );
509}
510