nel/src/3d/quad_grid_clip_cluster.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/quad_grid_clip_cluster.h"
  20 #include "nel/misc/hierarchical_timer.h"
  21 #include "nel/3d/transform_shape.h"
  22 #include "nel/3d/cluster.h"
  23
  24
  25 using namespace NLMISC;
  26 using namespace std;
  27
  28 #ifdef DEBUG_NEW
  29 #define new DEBUG_NEW
  30 #endif
  31
  32 namespace NL3D
  33 {
  34
  35
  36 H_AUTO_DECL( NL3D_QuadClip_ClusterClip );
  37 H_AUTO_DECL( NL3D_QuadClip_SonsShowNoClip );
  38
  39
  40 // ***************************************************************************
  41 // 3 -> 400,200,100,50
  42 #define NL3D_QUADGRID_CLIP_CLUSTER_DEPTH                                2
  43
  44
  45 // ***************************************************************************
  46 #define NL3D_QCC_LEFT_DOWN              0
  47 #define NL3D_QCC_RIGHT_DOWN             1
  48 #define NL3D_QCC_LEFT_UP                2
  49 #define NL3D_QCC_RIGHT_UP               3
  50
  51
  52 // ***************************************************************************
  53 // ***************************************************************************
  54 // ***************************************************************************
  55 // ***************************************************************************
  56
  57
  58 // ***************************************************************************
  59 void            CQuadGridClipClusterListDist::clipSons(uint minDistSetup)
  60 {
  61         for(uint i=minDistSetup; i<Models.size();i++)
  62         {
  63                 CTransformShape ** pModel= Models[i].begin();
  64                 uint    nSons= Models[i].size();
  65                 for(;nSons>0;nSons--, pModel++)
  66                 {
  67                         (*pModel)->traverseClip();
  68                 }
  69         }
  70 }
  71
  72 // ***************************************************************************
  73 void            CQuadGridClipClusterListDist::insertModel(uint distSetup, CTransformShape *model)
  74 {
  75         Models[distSetup].insert(model, &model->_QuadClusterListNode);
  76 }
  77
  78
  79 // ***************************************************************************
  80 void            CQuadGridClipClusterListDist::resetSons(CClipTrav *clipTrav)
  81 {
  82         for(uint i=0; i<Models.size();i++)
  83         {
  84                 // clean up model list
  85                 CTransformShape ** pModel= Models[i].begin();
  86                 uint    nSons= Models[i].size();
  87                 for(;nSons>0;nSons--, pModel++)
  88                 {
  89                         // link the model to the rootCluster
  90                         clipTrav->RootCluster->clipAddChild(*pModel);
  91                 }
  92                 // unlink all my sons from me
  93                 Models[i].clear();
  94         }
  95 }
  96
  97
  98 // ***************************************************************************
  99 // ***************************************************************************
 100 // ***************************************************************************
 101 // ***************************************************************************
 102
 103
 104 // ***************************************************************************
 105 CQuadGridClipClusterQTreeNode::CQuadGridClipClusterQTreeNode()
 106 {
 107         Sons[0]=NULL;
 108         Sons[1]=NULL;
 109         Sons[2]=NULL;
 110         Sons[3]=NULL;
 111         Empty= true;
 112         Owner= NULL;
 113         RootNode= false;
 114         LeafNode= false;
 115 }
 116
 117
 118 // ***************************************************************************
 119 void    CQuadGridClipClusterQTreeNode::init(CQuadGridClipCluster *owner, uint level, bool rootNode, const NLMISC::CAABBox &pivot)
 120 {
 121         Owner= owner;
 122         RootNode= rootNode;
 123         PivotBBox= pivot;
 124
 125         // If not a leaf, create sons
 126         if(level>0)
 127         {
 128                 LeafNode= false;
 129
 130                 // split pivot for sons
 131                 CAABBox pivotSon;
 132                 pivotSon.setSize(PivotBBox.getHalfSize());
 133                 float   xMin= PivotBBox.getMin().x/2;
 134                 float   yMin= PivotBBox.getMin().y/2;
 135                 float   xMax= PivotBBox.getMax().x/2;
 136                 float   yMax= PivotBBox.getMax().y/2;
 137                 float   xCenter= PivotBBox.getCenter().x/2;
 138                 float   yCenter= PivotBBox.getCenter().y/2;
 139                 // LeftDown
 140                 pivotSon.setCenter( CVector(xMin+xCenter,yMin+yCenter,0) );
 141                 Sons[NL3D_QCC_LEFT_DOWN]= new CQuadGridClipClusterQTreeNode;
 142                 Sons[NL3D_QCC_LEFT_DOWN]->init(owner, level-1, false, pivotSon);
 143                 // RightDown
 144                 pivotSon.setCenter( CVector(xMax+xCenter,yMin+yCenter,0) );
 145                 Sons[NL3D_QCC_RIGHT_DOWN]= new CQuadGridClipClusterQTreeNode;
 146                 Sons[NL3D_QCC_RIGHT_DOWN]->init(owner, level-1, false, pivotSon);
 147                 // LeftUp
 148                 pivotSon.setCenter( CVector(xMin+xCenter,yMax+yCenter,0) );
 149                 Sons[NL3D_QCC_LEFT_UP]= new CQuadGridClipClusterQTreeNode;
 150                 Sons[NL3D_QCC_LEFT_UP]->init(owner, level-1, false, pivotSon);
 151                 // RithgUp
 152                 pivotSon.setCenter( CVector(xMax+xCenter,yMax+yCenter,0) );
 153                 Sons[NL3D_QCC_RIGHT_UP]= new CQuadGridClipClusterQTreeNode;
 154                 Sons[NL3D_QCC_RIGHT_UP]->init(owner, level-1, false, pivotSon);
 155         }
 156         else
 157         {
 158                 LeafNode= true;
 159         }
 160
 161         // Create the distMax list only if root or leaf. No models in interleaved branches.
 162         if( LeafNode)
 163                 ListNode.Models.resize(Owner->_NumDistTotal);
 164 }
 165
 166
 167 // ***************************************************************************
 168 CQuadGridClipClusterQTreeNode::~CQuadGridClipClusterQTreeNode()
 169 {
 170         // erase sons
 171         uint i;
 172         for(i=0; i<4;i++)
 173         {
 174                 if(Sons[i])
 175                         delete Sons[i];
 176                 Sons[i]= NULL;
 177         }
 178
 179         // check my list
 180         for(i=0; i<ListNode.Models.size();i++)
 181         {
 182                 nlassert(ListNode.Models[i].empty());
 183         }
 184 }
 185
 186 // ***************************************************************************
 187 void            CQuadGridClipClusterQTreeNode::clip(CClipTrav *clipTrav)
 188 {
 189         // if empty (test important for branch and leave clusters)
 190         if(Empty)
 191                 return;
 192
 193         H_BEFORE( NL3D_QuadClip_NodeClip );
 194
 195         // Then clip against pyramid
 196         bool    unspecified= false;
 197         bool    visible= true;
 198         for(sint i=0;i<(sint)clipTrav->WorldPyramid.size();i++)
 199         {
 200                 // We are sure that pyramid has normalized plane normals.
 201                 if(!BBoxExt.clipBack(clipTrav->WorldPyramid[i]))
 202                 {
 203                         visible= false;
 204                         break;
 205                 }
 206                 // else test is the bbox is partially or fully in the plane
 207                 else if(!unspecified)
 208                 {
 209                         // if clipFront AND clipBack, it means partially.
 210                         if(BBoxExt.clipFront(clipTrav->WorldPyramid[i]))
 211                                 unspecified= true;
 212                 }
 213         }
 214
 215         H_AFTER( NL3D_QuadClip_NodeClip );
 216
 217         // if visible, parse sons
 218         if(visible)
 219         {
 220                 // clip sons or cluster sons
 221                 if(unspecified)
 222                 {
 223                         if( LeafNode)
 224                         {
 225                                 // clip DistMax.
 226                                 CVector         c= BBoxExt.getCenter();
 227                                 float           dist= (c - clipTrav->CamPos).norm();
 228                                 dist-= BBoxExt.getRadius();
 229                                 sint    minDistSetup= (sint)floor(Owner->_NumDist*dist/Owner->_DistMax);
 230                                 // NB if too far, set _NumDist (ie will clip only the infinite objects ones)
 231                                 clamp(minDistSetup, 0, (sint)Owner->_NumDist);
 232
 233                                 // clip the sons individually
 234                                 H_AUTO( NL3D_QuadClip_SonsClip );
 235                                 ListNode.clipSons(minDistSetup);
 236                         }
 237                         else
 238                         {
 239                                 // clip cluster sons
 240                                 Sons[0]->clip(clipTrav);
 241                                 Sons[1]->clip(clipTrav);
 242                                 Sons[2]->clip(clipTrav);
 243                                 Sons[3]->clip(clipTrav);
 244                         }
 245                 }
 246                 else
 247                 {
 248                         // udpdate the sons, but don't clip, because we know they are fully visible.
 249                         clipTrav->ForceNoFrustumClip= true;
 250
 251                         // show all cluster sons or sons
 252                         noFrustumClip(clipTrav);
 253
 254                         // reset flag
 255                         clipTrav->ForceNoFrustumClip= false;
 256                 }
 257         }
 258 }
 259
 260
 261 // ***************************************************************************
 262 void            CQuadGridClipClusterQTreeNode::noFrustumClip(CClipTrav *clipTrav)
 263 {
 264         // if empty (test important for branch and leave clusters)
 265         if(Empty)
 266                 return;
 267
 268         // clip the sons
 269         if( LeafNode)
 270         {
 271                 // clip DistMax.
 272                 CVector         c= BBoxExt.getCenter();
 273                 float           dist= (c - clipTrav->CamPos).norm();
 274                 dist-= BBoxExt.getRadius();
 275                 sint minDistSetup= (sint)floor(Owner->_NumDist*dist/Owner->_DistMax);
 276                 // NB if too far, set _NumDist (ie will clip only the infinite objects ones)
 277                 clamp(minDistSetup, 0, (sint)Owner->_NumDist);
 278
 279                 // clip the sons
 280                 H_AUTO_USE( NL3D_QuadClip_SonsShowNoClip );
 281                 ListNode.clipSons(minDistSetup);
 282         }
 283         else
 284         {
 285                 // forceShow of cluster sons
 286                 Sons[0]->noFrustumClip(clipTrav);
 287                 Sons[1]->noFrustumClip(clipTrav);
 288                 Sons[2]->noFrustumClip(clipTrav);
 289                 Sons[3]->noFrustumClip(clipTrav);
 290         }
 291 }
 292
 293
 294 // ***************************************************************************
 295 void            CQuadGridClipClusterQTreeNode::insertModel(const NLMISC::CAABBox &worldBBox, uint distSetup, CTransformShape *model)
 296 {
 297         // if leaf node, insert the model in the list
 298         if( LeafNode )
 299         {
 300                 if(Empty)
 301                 {
 302                         Empty= false;
 303                         BBox= worldBBox;
 304                 }
 305                 else
 306                 {
 307                         // extend the bbox with 2 corners of the incoming bbox (sufficient for an AABBox).
 308                         BBox.extend( worldBBox.getCenter() + worldBBox.getHalfSize() );
 309                         BBox.extend( worldBBox.getCenter() - worldBBox.getHalfSize() );
 310                 }
 311
 312                 // insert in list
 313                 ListNode.insertModel(distSetup, model);
 314         }
 315         // else, recurs insert in branch
 316         else
 317         {
 318                 // choose what son according to pivot.
 319                 CQuadGridClipClusterQTreeNode   *selectSon;
 320                 if( worldBBox.getCenter().y<PivotBBox.getCenter().y )
 321                 {
 322                         if( worldBBox.getCenter().x<PivotBBox.getCenter().x )
 323                                 selectSon= Sons[NL3D_QCC_LEFT_DOWN];
 324                         else
 325                                 selectSon= Sons[NL3D_QCC_RIGHT_DOWN];
 326                 }
 327                 else
 328                 {
 329                         if( worldBBox.getCenter().x<PivotBBox.getCenter().x )
 330                                 selectSon= Sons[NL3D_QCC_LEFT_UP];
 331                         else
 332                                 selectSon= Sons[NL3D_QCC_RIGHT_UP];
 333                 }
 334
 335                 // insert in this cluster
 336                 selectSon->insertModel(worldBBox, distSetup, model);
 337
 338                 // extend my boox according to this son cluster.
 339                 if(Empty)
 340                 {
 341                         Empty= false;
 342                         BBox= selectSon->BBox;
 343                 }
 344                 else
 345                 {
 346                         // extend the bbox with 2 corners of the son bbox (sufficient for an AABBox).
 347                         BBox.extend( selectSon->BBox.getCenter() + selectSon->BBox.getHalfSize() );
 348                         BBox.extend( selectSon->BBox.getCenter() - selectSon->BBox.getHalfSize() );
 349                 }
 350         }
 351
 352         // update bboxExt
 353         BBoxExt= BBox;
 354 }
 355
 356 // ***************************************************************************
 357 void            CQuadGridClipClusterQTreeNode::resetSons(CClipTrav *clipTrav)
 358 {
 359         ListNode.resetSons(clipTrav);
 360         if(Sons[0])
 361         {
 362                 Sons[0]->resetSons(clipTrav);
 363                 Sons[1]->resetSons(clipTrav);
 364                 Sons[2]->resetSons(clipTrav);
 365                 Sons[3]->resetSons(clipTrav);
 366         }
 367 }
 368
 369
 370 // ***************************************************************************
 371 void            CQuadGridClipClusterQTreeNode::profileNumChildren(uint distLevel, uint &result) const
 372 {
 373         if(distLevel<ListNode.Models.size())
 374                 result+= ListNode.Models[distLevel].size();
 375         // Add cluster sons
 376         if(Sons[0])
 377         {
 378                 Sons[0]->profileNumChildren(distLevel, result);
 379                 Sons[1]->profileNumChildren(distLevel, result);
 380                 Sons[2]->profileNumChildren(distLevel, result);
 381                 Sons[3]->profileNumChildren(distLevel, result);
 382         }
 383 }
 384
 385
 386 // ***************************************************************************
 387 // ***************************************************************************
 388 // ***************************************************************************
 389 // ***************************************************************************
 390
 391
 392 // ***************************************************************************
 393 CQuadGridClipCluster::CQuadGridClipCluster(uint numDist, float distMax, const NLMISC::CAABBox &pivot)
 394 {
 395         _DistMax= distMax;
 396         _NumDist= numDist;
 397         _NumDistTotal= _NumDist+1;
 398
 399         _Root.init(this, NL3D_QUADGRID_CLIP_CLUSTER_DEPTH, true, pivot);
 400 }
 401
 402 // ***************************************************************************
 403 CQuadGridClipCluster::~CQuadGridClipCluster()
 404 {
 405 }
 406
 407 // ***************************************************************************
 408 void            CQuadGridClipCluster::addModel(const NLMISC::CAABBox &worldBBox, CTransformShape *model)
 409 {
 410         // check not already inserted
 411         nlassert(!model->_QuadClusterListNode.isLinked());
 412
 413         // Add the model to the good distance list
 414         float   modelDistMax= model->getDistMax();
 415         sint    distSetup;
 416         if(modelDistMax<0)
 417                 distSetup= _NumDist;
 418         else
 419         {
 420                 distSetup= (sint)floor(_NumDist*modelDistMax/_DistMax);
 421                 // NB: if >=_DistMax, then distSetup==_NumDist, meaning infinite distance (never dist clipped)
 422                 clamp(distSetup, 0, (sint)_NumDist);
 423         }
 424
 425         // add / recurs to the quadtree
 426         _Root.insertModel(worldBBox, distSetup, model);
 427 }
 428
 429
 430 // ***************************************************************************
 431 void            CQuadGridClipCluster::removeModel(CTransformShape *model)
 432 {
 433         model->_QuadClusterListNode.unlink();
 434 }
 435
 436
 437 // ***************************************************************************
 438 void            CQuadGridClipCluster::clip(CClipTrav *clipTrav)
 439 {
 440         H_AUTO_USE( NL3D_QuadClip_ClusterClip );
 441
 442         // clip the quadtree
 443         _Root.clip(clipTrav);
 444 }
 445
 446 // ***************************************************************************
 447 void            CQuadGridClipCluster::resetSons(CClipTrav *clipTrav)
 448 {
 449         _Root.resetSons(clipTrav);
 450 }
 451
 452
 453 // ***************************************************************************
 454 sint            CQuadGridClipCluster::profileNumChildren(uint distLevel) const
 455 {
 456         uint    result= 0;
 457         _Root.profileNumChildren(distLevel, result);
 458         return result;
 459 }
 460
 461
 462 } // NL3D