nel/src/pacs/surface_quad.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 "stdpacs.h"
  18 #include "nel/pacs/surface_quad.h"
  19
  20 #include "nel/misc/file.h"
  21
  22 #ifdef DEBUG_NEW
  23 #define new DEBUG_NEW
  24 #endif
  25
  26 using namespace NLMISC;
  27 using namespace std;
  28
  29 NLPACS::CSurfaceQuadTree::CSurfaceQuadTree()
  30 {
  31         _Root = NULL;
  32         _MaxThickness = FLT_MAX;
  33         _MaxLevel = 1;
  34         _BBox.setCenter(CVector::Null);
  35         _BBox.setSize(CVector::Null);
  36 }
  37
  38 NLPACS::CSurfaceQuadTree::CSurfaceQuadTree(const NLPACS::CSurfaceQuadTree &quad)
  39 {
  40         *this = quad;
  41 }
  42
  43 NLPACS::CSurfaceQuadTree        &NLPACS::CSurfaceQuadTree::operator = (const NLPACS::CSurfaceQuadTree &quad)
  44 {
  45         if (&quad == this)
  46                 return *this;
  47
  48         _MaxThickness = quad._MaxThickness;
  49         _MaxLevel = quad._MaxLevel;
  50         _BBox = quad._BBox;
  51
  52         _Root = NULL;
  53         if (quad._Root != NULL)
  54         {
  55                 if (quad._Root->isLeaf())
  56                 {
  57                         CQuadLeaf       *newLeaf = new CQuadLeaf();
  58                         *newLeaf = *((CQuadLeaf *)(quad._Root));
  59                         _Root = newLeaf;
  60                 }
  61                 else
  62                 {
  63                         CQuadBranch     *newBranch = new CQuadBranch();
  64                         *newBranch = *((CQuadBranch *)(quad._Root));
  65                         _Root = newBranch;
  66                 }
  67         }
  68
  69         return *this;
  70 }
  71
  72 void    NLPACS::CSurfaceQuadTree::clear()
  73 {
  74         delete _Root;
  75         _Root = NULL;
  76 }
  77
  78 void    NLPACS::CSurfaceQuadTree::init(float maxThickness, uint maxLevel, const CVector &center, float halfSize)
  79 {
  80         nlassert(maxLevel > 0);
  81         clear();
  82         _MaxThickness = maxThickness;
  83         _MaxLevel = uint8(maxLevel);
  84         _BBox.setCenter(center);
  85         _BBox.setHalfSize(CVector(halfSize, halfSize, 10000.0f));
  86 }
  87
  88 void    NLPACS::CSurfaceQuadTree::addVertex(const CVector &v)
  89 {
  90         if (!_BBox.include(v))
  91                 return;
  92
  93         if (_Root == NULL)
  94         {
  95                 if (_MaxLevel == 1)
  96                 {
  97                         _Root = new CQuadLeaf(_MaxLevel);
  98                 }
  99                 else
 100                 {
 101                         _Root = new CQuadBranch(_MaxLevel);
 102                 }
 103
 104                 _Root->_MaxThickness = _MaxThickness;
 105                 _Root->_HalfSize = _BBox.getHalfSize().x;
 106                 _Root->_MinHeight = FLT_MAX;
 107                 _Root->_MaxHeight = -FLT_MAX;
 108                 _Root->_XCenter = _BBox.getCenter().x;
 109                 _Root->_YCenter = _BBox.getCenter().y;
 110         }
 111
 112         _Root->addVertex(v);
 113 }
 114
 115 void    NLPACS::CSurfaceQuadTree::compile()
 116 {
 117         if (_Root != NULL &&
 118                 !_Root->isLeaf() &&
 119                 _Root->getMaxHeight()-_Root->getMinHeight() <= _MaxThickness)
 120         {
 121                 CQuadLeaf       *leaf = new CQuadLeaf();
 122                 *((IQuadNode *)leaf) = *_Root;
 123                 delete _Root;
 124                 _Root = leaf;
 125         }
 126         else if (_Root != NULL &&
 127                          !_Root->isLeaf())
 128         {
 129                 ((CQuadBranch *)_Root)->reduceChildren();
 130         }
 131 }
 132
 133
 134 NLPACS::CQuadBranch::CQuadBranch(const NLPACS::CQuadBranch &branch) : NLPACS::IQuadNode(branch)
 135 {
 136         *this = branch;
 137 }
 138
 139 NLPACS::CQuadBranch     &NLPACS::CQuadBranch::operator = (const NLPACS::CQuadBranch &branch)
 140 {
 141         IQuadNode::operator=(branch);
 142
 143         uint    child;
 144         for (child=0; child<4; ++child)
 145         {
 146                 _Children[child] = NULL;
 147                 if (branch._Children[child] != NULL)
 148                 {
 149                         if (branch._Children[child]->isLeaf())
 150                         {
 151                                 CQuadLeaf       *newLeaf = new CQuadLeaf();
 152                                 *newLeaf = *((CQuadLeaf *)(branch._Children[child]));
 153                                 _Children[child] = newLeaf;
 154                         }
 155                         else
 156                         {
 157                                 CQuadBranch     *newBranch = new CQuadBranch();
 158                                 *newBranch = *((CQuadBranch *)(branch._Children[child]));
 159                                 _Children[child] = newBranch;
 160                         }
 161                 }
 162         }
 163         return *this;
 164 }
 165
 166 void    NLPACS::CQuadBranch::reduceChildren()
 167 {
 168         uint    i;
 169
 170         for (i=0; i<4; ++i)
 171         {
 172                 if (_Children[i] != NULL &&
 173                         !_Children[i]->isLeaf() &&
 174                         _Children[i]->getMaxHeight()-_Children[i]->getMinHeight() <= _MaxThickness)
 175                 {
 176                         CQuadLeaf       *leaf = new CQuadLeaf();
 177                         *((IQuadNode *)leaf) = *_Children[i];
 178                         delete _Children[i];
 179                         _Children[i] = leaf;
 180                 }
 181                 else if (_Children[i] != NULL &&
 182                                  !_Children[i]->isLeaf())
 183                 {
 184                         ((CQuadBranch *)_Children[i])->reduceChildren();
 185                 }
 186         }
 187 }
 188
 189 void    NLPACS::CQuadBranch::addVertex(const CVector &v)
 190 {
 191         IQuadNode::addVertex(v);
 192         uint    child;
 193         if (v.x > _XCenter)
 194                 child = (v.y > _YCenter) ? 2 : 1;
 195         else
 196                 child = (v.y > _YCenter) ? 3 : 0;
 197
 198         if (_Children[child] == NULL)
 199         {
 200                 if (_Level == 2)
 201                 {
 202                         _Children[child] = new CQuadLeaf(_Level-1);
 203                 }
 204                 else
 205                 {
 206                         _Children[child] = new CQuadBranch(_Level-1);
 207                 }
 208
 209                 _Children[child]->_MaxThickness = _MaxThickness;
 210                 _Children[child]->_HalfSize = _HalfSize/2.0f;
 211                 _Children[child]->_MinHeight = FLT_MAX;
 212                 _Children[child]->_MaxHeight = -FLT_MAX;
 213                 _Children[child]->_XCenter = _XCenter+_Children[child]->_HalfSize*((child == 1 || child == 2) ? 1.0f : -1.0f);
 214                 _Children[child]->_YCenter = _YCenter+_Children[child]->_HalfSize*((child == 2 || child == 3) ? 1.0f : -1.0f);
 215         }
 216
 217         _Children[child]->addVertex(v);
 218 }
 219
 220 bool    NLPACS::CQuadBranch::check() const
 221 {
 222         if (!IQuadNode::check())
 223                 return false;
 224
 225         uint    child;
 226         for (child=0; child<4; ++child)
 227                 if (_Children[child] != NULL && !_Children[child]->check())
 228                         return false;
 229         return true;
 230 }
 231
 232
 233 /*
 234  * Serialization methods...
 235  */
 236
 237
 238 void    NLPACS::CQuadBranch::serial(NLMISC::IStream &f)
 239 {
 240         IQuadNode::serial(f);
 241
 242         uint    child;
 243         for (child=0; child<4; ++child)
 244         {
 245                 uint8   childType = 0;
 246
 247                 if (f.isReading())
 248                 {
 249                         CQuadLeaf       *leaf;
 250                         CQuadBranch     *branch;
 251                         f.serial(childType);
 252                         switch (childType)
 253                         {
 254                         case NoChild:
 255                                 _Children[child] = NULL;
 256                                 break;
 257                         case LeafChild:
 258                                 leaf = new CQuadLeaf();
 259                                 _Children[child] = leaf;
 260                                 leaf->serial(f);
 261                                 break;
 262                         case BranchChild:
 263                                 branch = new CQuadBranch();;
 264                                 _Children[child] = branch;
 265                                 branch->serial(f);
 266                                 break;
 267                         default:
 268                                 nlerror("While serializing (read) CQuadBranch: unknown child type");
 269                                 break;
 270                         }
 271                 }
 272                 else
 273                 {
 274                         if (_Children[child] == NULL)
 275                         {
 276                                 childType = NoChild;
 277                                 f.serial(childType);
 278                         }
 279                         else
 280                         {
 281                                 childType = uint8(_Children[child]->isLeaf() ? LeafChild : BranchChild);
 282                                 f.serial(childType);
 283                                 _Children[child]->serial(f);
 284                         }
 285                 }
 286         }
 287 }
 288
 289 bool    NLPACS::CSurfaceQuadTree::check() const
 290 {
 291         if (_Root != NULL)
 292                 return _Root->check();
 293         return true;
 294 }
 295
 296 const NLPACS::CQuadLeaf *NLPACS::CSurfaceQuadTree::getLeaf(const CVector &v) const
 297 {
 298         CVector pos = CVector(v.x, v.y, 0.0f);
 299         if (_Root == NULL || !_BBox.include(pos))
 300                 return NULL;
 301
 302         const IQuadNode *node = _Root;
 303
 304         while (node != NULL && !node->isLeaf())
 305         {
 306                 nlassert(node->getBBox().include(pos));
 307                 uint    child;
 308
 309                 if (pos.x > node->_XCenter)
 310                         child = ((pos.y > node->_YCenter) ? 2 : 1);
 311                 else
 312                         child = ((pos.y > node->_YCenter) ? 3 : 0);
 313
 314                 node = node->getChild(child);
 315         }
 316
 317         return (const CQuadLeaf *)node;
 318 }
 319
 320
 321 void    NLPACS::CSurfaceQuadTree::serial(NLMISC::IStream &f)
 322 {
 323         /*
 324         Version 0:
 325                 - base version.
 326         */
 327         (void)f.serialVersion(0);
 328
 329         uint8   childType = 0;
 330         f.serial(_MaxThickness);
 331         f.serial(_MaxLevel);
 332         f.serial(_BBox);
 333         if (f.isReading())
 334         {
 335                 CQuadLeaf       *leaf;
 336                 CQuadBranch     *branch;
 337
 338                 f.serial(childType);
 339                 switch (childType)
 340                 {
 341                 case CQuadBranch::NoChild:
 342                         _Root = NULL;
 343                         break;
 344                 case CQuadBranch::LeafChild:
 345                         leaf = new CQuadLeaf();
 346                         _Root = leaf;
 347                         leaf->serial(f);
 348                         break;
 349                 case CQuadBranch::BranchChild:
 350                         branch = new CQuadBranch();
 351                         _Root = branch;
 352                         branch->serial(f);
 353                         break;
 354                 default:
 355                         nlerror("While serializing (read) CQuadBranch: unknown child type");
 356                         break;
 357                 }
 358         }
 359         else
 360         {
 361                 if (_Root == NULL)
 362                 {
 363                         childType = CQuadBranch::NoChild;
 364                         f.serial(childType);
 365                 }
 366                 else
 367                 {
 368                         childType = uint8(_Root->isLeaf() ? CQuadBranch::LeafChild : CQuadBranch::BranchChild);
 369                         f.serial(childType);
 370                         _Root->serial(f);
 371                 }
 372         }
 373 }
 374
 375 //
 376 float   NLPACS::CSurfaceQuadTree::getInterpZ(const CVector &v) const
 377 {
 378         // first get final leaf for position
 379         CVector pos = CVector(v.x, v.y, 0.0f);
 380         if (_Root == NULL || !_BBox.include(pos))
 381                 return v.z;     // return unmodified z
 382
 383         const IQuadNode                         *node = _Root;
 384         vector<uint>                            children;
 385         vector<const IQuadNode*>        nodes;
 386
 387         while (node != NULL && !node->isLeaf())
 388         {
 389                 nodes.push_back(node);
 390
 391                 nlassert(node->getBBox().include(pos));
 392                 uint    child;
 393
 394                 if (pos.x > node->_XCenter)
 395                         child = ((pos.y > node->_YCenter) ? 2 : 1);
 396                 else
 397                         child = ((pos.y > node->_YCenter) ? 3 : 0);
 398
 399                 children.push_back(child);
 400
 401                 node = node->getChild(child);
 402         }
 403
 404         if (node == NULL)
 405                 return v.z;     // return unmodified z
 406
 407         nodes.push_back(node);
 408
 409         vector<const CQuadLeaf*>        leaves;
 410         vector<const IQuadNode*>        explore;
 411
 412         leaves.push_back((const CQuadLeaf*)node);
 413
 414         // for each side of the leaf, find neighbor leaves
 415         uint    side;
 416         for (side=0; side<4; ++side)
 417         {
 418                 static const sint       ct[4][4] = { {-1, 1, 3,-1}, {-1,-1, 2, 0}, { 1,-1,-1, 3}, { 0, 2,-1,-1} };      // child table
 419                 static const sint       nt[4][4] = { { 3, 1, 3, 1}, { 2, 0, 2, 0}, { 1, 3, 1, 3}, { 0, 2, 0, 2} };      // neighbor table
 420
 421                 sint    nlev = (sint)nodes.size()-1;
 422                 sint    child = -1;
 423
 424                 while (nlev > 0)
 425                 {
 426                         child = ct[children[nlev-1]][side];
 427
 428                         if (child >= 0)
 429                                 break;
 430
 431                         --nlev;
 432                 }
 433
 434                 // neighbor not found in root, leave
 435                 if (nlev == 0)
 436                         continue;
 437
 438                 // get father
 439                 node = nodes[nlev-1];
 440
 441                 while (nlev < (sint)nodes.size() && node!=NULL && !node->isLeaf())
 442                 {
 443                         child = nt[children[nlev-1]][side];
 444                         node = node->getChild(child);
 445
 446                         ++nlev;
 447                 }
 448
 449                 if (node == NULL)
 450                         continue;
 451
 452                 if (node->isLeaf())
 453                 {
 454                         leaves.push_back((const CQuadLeaf*)node);
 455                 }
 456                 else
 457                 {
 458                         explore.push_back(node);
 459
 460                         while (!explore.empty())
 461                         {
 462                                 node = explore.back();
 463                                 explore.pop_back();
 464
 465                                 if (node == NULL)
 466                                         continue;
 467
 468                                 if (node->isLeaf())
 469                                         leaves.push_back((const CQuadLeaf*)node);
 470                                 else
 471                                 {
 472                                         explore.push_back(node->getChild((side+2)&3));
 473                                         explore.push_back(node->getChild((side+3)&3));
 474                                 }
 475                         }
 476                 }
 477         }
 478
 479         uint                    i;
 480         float                   di, wi;
 481         float                   sum = 0.0;
 482         float                   interpZ = 0.0;
 483
 484         for (i=0; i<leaves.size(); ++i)
 485         {
 486                 di = (float)sqrt(sqr(v.x-leaves[i]->_XCenter)+sqr(v.y-leaves[i]->_YCenter))*(float)pow(1.5, leaves[i]->_Level);
 487                 wi = 1.0f/di;
 488                 sum += wi;
 489                 interpZ += (leaves[i]->getMinHeight()+leaves[i]->getMaxHeight())*0.5f*wi;
 490         }
 491
 492         return interpZ / sum;
 493 }