nevrax.org : docs

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "stdpacs.h"
+00027 
+00028 #include "nel/misc/file.h"
+00029 
+00030 #include "pacs/surface_quad.h"
+00031 
+00032 #include <vector>
+00033 
+00034 using namespace NLMISC;
+00035 using namespace std;
+00036 
+00037 NLPACS::CSurfaceQuadTree::CSurfaceQuadTree()
+00038 {
+00039         _Root = NULL;
+00040         _MaxThickness = FLT_MAX;
+00041         _MaxLevel = 1;
+00042         _BBox.setCenter(CVector::Null);
+00043         _BBox.setSize(CVector::Null);
+00044 }
+00045 
+00046 NLPACS::CSurfaceQuadTree::CSurfaceQuadTree(const NLPACS::CSurfaceQuadTree &quad)
+00047 {
+00048         *this = quad;
+00049 }
+00050 
+00051 NLPACS::CSurfaceQuadTree        &NLPACS::CSurfaceQuadTree::operator = (const NLPACS::CSurfaceQuadTree &quad)
+00052 {
+00053         if (&quad == this)
+00054                 return *this;
+00055 
+00056         _MaxThickness = quad._MaxThickness;
+00057         _MaxLevel = quad._MaxLevel;
+00058         _BBox = quad._BBox;
+00059 
+00060         _Root = NULL;
+00061         if (quad._Root != NULL)
+00062         {
+00063                 if (quad._Root->isLeaf())
+00064                 {
+00065                         CQuadLeaf       *newLeaf = new CQuadLeaf();
+00066                         *newLeaf = *((CQuadLeaf *)(quad._Root));
+00067                         _Root = newLeaf;
+00068                 }
+00069                 else
+00070                 {
+00071                         CQuadBranch     *newBranch = new CQuadBranch();
+00072                         *newBranch = *((CQuadBranch *)(quad._Root));
+00073                         _Root = newBranch;
+00074                 }
+00075         }
+00076 
+00077         return *this;
+00078 }
+00079 
+00080 void    NLPACS::CSurfaceQuadTree::clear()
+00081 {
+00082         delete _Root;
+00083         _Root = NULL;
+00084 }
+00085 
+00086 void    NLPACS::CSurfaceQuadTree::init(float maxThickness, uint maxLevel, const CVector &center, float halfSize)
+00087 {
+00088         nlassert(maxLevel > 0);
+00089         clear();
+00090         _MaxThickness = maxThickness;
+00091         _MaxLevel = maxLevel;
+00092         _BBox.setCenter(center);
+00093         _BBox.setHalfSize(CVector(halfSize, halfSize, 10000.0f));
+00094 }
+00095 
+00096 void    NLPACS::CSurfaceQuadTree::addVertex(const CVector &v)
+00097 {
+00098         if (!_BBox.include(v))
+00099                 return;
+00100 
+00101         if (_Root == NULL)
+00102         {
+00103                 if (_MaxLevel == 1)
+00104                 {
+00105                         _Root = new CQuadLeaf(_MaxLevel);
+00106                 }
+00107                 else
+00108                 {
+00109                         _Root = new CQuadBranch(_MaxLevel);
+00110                 }
+00111 
+00112                 _Root->_MaxThickness = _MaxThickness;
+00113                 _Root->_HalfSize = _BBox.getHalfSize().x;
+00114                 _Root->_MinHeight = FLT_MAX;
+00115                 _Root->_MaxHeight = -FLT_MAX;
+00116                 _Root->_XCenter = _BBox.getCenter().x;
+00117                 _Root->_YCenter = _BBox.getCenter().y;
+00118         }
+00119 
+00120         _Root->addVertex(v);
+00121 }
+00122 
+00123 void    NLPACS::CSurfaceQuadTree::compile()
+00124 {
+00125         if (_Root != NULL &&
+00126                 !_Root->isLeaf() &&
+00127                 _Root->getMaxHeight()-_Root->getMinHeight() <= _MaxThickness)
+00128         {
+00129                 CQuadLeaf       *leaf = new CQuadLeaf();
+00130                 *((IQuadNode *)leaf) = *_Root;
+00131                 delete _Root;
+00132                 _Root = leaf;
+00133         }
+00134         else if (_Root != NULL &&
+00135                          !_Root->isLeaf())
+00136         {
+00137                 ((CQuadBranch *)_Root)->reduceChildren();
+00138         }
+00139 }
+00140 
+00141 
+00142 NLPACS::CQuadBranch::CQuadBranch(const NLPACS::CQuadBranch &branch) : NLPACS::IQuadNode(branch)
+00143 {
+00144         *this = branch;
+00145 }
+00146 
+00147 NLPACS::CQuadBranch     &NLPACS::CQuadBranch::operator = (const NLPACS::CQuadBranch &branch)
+00148 {
+00149         IQuadNode::operator=(branch);
+00150 
+00151         uint    child;
+00152         for (child=0; child<4; ++child)
+00153         {
+00154                 _Children[child] = NULL;
+00155                 if (branch._Children[child] != NULL)
+00156                 {
+00157                         if (branch._Children[child]->isLeaf())
+00158                         {
+00159                                 CQuadLeaf       *newLeaf = new CQuadLeaf();
+00160                                 *newLeaf = *((CQuadLeaf *)(branch._Children[child]));
+00161                                 _Children[child] = newLeaf;
+00162                         }
+00163                         else
+00164                         {
+00165                                 CQuadBranch     *newBranch = new CQuadBranch();
+00166                                 *newBranch = *((CQuadBranch *)(branch._Children[child]));
+00167                                 _Children[child] = newBranch;
+00168                         }
+00169                 }
+00170         }
+00171         return *this;
+00172 }
+00173 
+00174 void    NLPACS::CQuadBranch::reduceChildren()
+00175 {
+00176         uint    i;
+00177 
+00178         for (i=0; i<4; ++i)
+00179         {
+00180                 if (_Children[i] != NULL &&
+00181                         !_Children[i]->isLeaf() &&
+00182                         _Children[i]->getMaxHeight()-_Children[i]->getMinHeight() <= _MaxThickness)
+00183                 {
+00184                         CQuadLeaf       *leaf = new CQuadLeaf();
+00185                         *((IQuadNode *)leaf) = *_Children[i];
+00186                         delete _Children[i];
+00187                         _Children[i] = leaf;
+00188                 }
+00189                 else if (_Children[i] != NULL &&
+00190                                  !_Children[i]->isLeaf())
+00191                 {
+00192                         ((CQuadBranch *)_Children[i])->reduceChildren();
+00193                 }
+00194         }
+00195 }
+00196 
+00197 void    NLPACS::CQuadBranch::addVertex(const CVector &v)
+00198 {
+00199         IQuadNode::addVertex(v);
+00200         uint    child;
+00201         if (v.x > _XCenter)
+00202                 child = (v.y > _YCenter) ? 2 : 1;
+00203         else
+00204                 child = (v.y > _YCenter) ? 3 : 0;
+00205 
+00206         if (_Children[child] == NULL)
+00207         {
+00208                 if (_Level == 2)
+00209                 {
+00210                         _Children[child] = new CQuadLeaf(_Level-1);
+00211                 }
+00212                 else
+00213                 {
+00214                         _Children[child] = new CQuadBranch(_Level-1);
+00215                 }
+00216 
+00217                 _Children[child]->_MaxThickness = _MaxThickness;
+00218                 _Children[child]->_HalfSize = _HalfSize/2.0f;
+00219                 _Children[child]->_MinHeight = FLT_MAX;
+00220                 _Children[child]->_MaxHeight = -FLT_MAX;
+00221                 _Children[child]->_XCenter = _XCenter+_Children[child]->_HalfSize*((child == 1 || child == 2) ? 1.0f : -1.0f);
+00222                 _Children[child]->_YCenter = _YCenter+_Children[child]->_HalfSize*((child == 2 || child == 3) ? 1.0f : -1.0f);
+00223         }
+00224 
+00225         _Children[child]->addVertex(v);
+00226 }
+00227 
+00228 bool    NLPACS::CQuadBranch::check() const
+00229 {
+00230         if (!IQuadNode::check())
+00231                 return false;
+00232 
+00233         uint    child;
+00234         for (child=0; child<4; ++child)
+00235                 if (_Children[child] != NULL && !_Children[child]->check())
+00236                         return false;
+00237         return true;
+00238 }
+00239 
+00240 
+00241 /*
+00242  * Serialization methods...
+00243  */
+00244 
+00245 
+00246 void    NLPACS::CQuadBranch::serial(NLMISC::IStream &f)
+00247 {
+00248         IQuadNode::serial(f);
+00249 
+00250         uint    child;
+00251         for (child=0; child<4; ++child)
+00252         {
+00253                 uint8   childType = 0;
+00254 
+00255                 if (f.isReading())
+00256                 {
+00257                         CQuadLeaf       *leaf; 
+00258                         CQuadBranch     *branch;
+00259                         f.serial(childType);
+00260                         switch (childType)
+00261                         {
+00262                         case NoChild:
+00263                                 _Children[child] = NULL;
+00264                                 break;
+00265                         case LeafChild:
+00266                                 leaf = new CQuadLeaf(); 
+00267                                 _Children[child] = leaf;
+00268                                 leaf->serial(f);
+00269                                 break;
+00270                         case BranchChild:
+00271                                 branch = new CQuadBranch();;
+00272                                 _Children[child] = branch;
+00273                                 branch->serial(f);
+00274                                 break;
+00275                         default:
+00276                                 nlerror("While serializing (read) CQuadBranch: unknown child type");
+00277                                 break;
+00278                         }
+00279                 }
+00280                 else
+00281                 {
+00282                         if (_Children[child] == NULL)
+00283                         {
+00284                                 childType = NoChild;
+00285                                 f.serial(childType);
+00286                         }
+00287                         else
+00288                         {
+00289                                 childType = (_Children[child]->isLeaf()) ? LeafChild : BranchChild;
+00290                                 f.serial(childType);
+00291                                 _Children[child]->serial(f);
+00292                         }
+00293                 }
+00294         }
+00295 }
+00296 
+00297 bool    NLPACS::CSurfaceQuadTree::check() const
+00298 {
+00299         if (_Root != NULL)
+00300                 return _Root->check();
+00301         return true;
+00302 }
+00303 
+00304 const NLPACS::CQuadLeaf *NLPACS::CSurfaceQuadTree::getLeaf(const CVector &v) const
+00305 {
+00306         CVector pos = CVector(v.x, v.y, 0.0f);
+00307         if (_Root == NULL || !_BBox.include(pos))
+00308                 return NULL;
+00309 
+00310         const IQuadNode *node = _Root;
+00311 
+00312         while (node != NULL && !node->isLeaf())
+00313         {
+00314                 nlassert(node->getBBox().include(pos));
+00315                 uint    child;
+00316 
+00317                 if (pos.x > node->_XCenter)
+00318                         child = ((pos.y > node->_YCenter) ? 2 : 1);
+00319                 else
+00320                         child = ((pos.y > node->_YCenter) ? 3 : 0);
+00321 
+00322                 node = node->getChild(child);
+00323         }
+00324 
+00325         return (const CQuadLeaf *)node;
+00326 }
+00327 
+00328 
+00329 void    NLPACS::CSurfaceQuadTree::serial(NLMISC::IStream &f)
+00330 {
+00331         /*
+00332         Version 0:
+00333                 - base version.
+00334         */
+00335         (void)f.serialVersion(0);
+00336 
+00337         uint8   childType = 0;
+00338         f.serial(_MaxThickness);
+00339         f.serial(_MaxLevel);
+00340         f.serial(_BBox);
+00341         if (f.isReading())
+00342         {
+00343                 CQuadLeaf       *leaf; 
+00344                 CQuadBranch     *branch;
+00345 
+00346                 f.serial(childType);
+00347                 switch (childType)
+00348                 {
+00349                 case CQuadBranch::NoChild:
+00350                         _Root = NULL;
+00351                         break;
+00352                 case CQuadBranch::LeafChild:
+00353                         leaf = new CQuadLeaf();
+00354                         _Root = leaf;
+00355                         leaf->serial(f);
+00356                         break;
+00357                 case CQuadBranch::BranchChild:
+00358                         branch = new CQuadBranch();
+00359                         _Root = branch;
+00360                         branch->serial(f);
+00361                         break;
+00362                 default:
+00363                         nlerror("While serializing (read) CQuadBranch: unknown child type");
+00364                         break;
+00365                 }
+00366         }
+00367         else
+00368         {
+00369                 if (_Root == NULL)
+00370                 {
+00371                         childType = CQuadBranch::NoChild;
+00372                         f.serial(childType);
+00373                 }
+00374                 else
+00375                 {
+00376                         childType = (_Root->isLeaf()) ? CQuadBranch::LeafChild : CQuadBranch::BranchChild;
+00377                         f.serial(childType);
+00378                         _Root->serial(f);
+00379                 }
+00380         }
+00381 }
+00382 
+00383 //
+00384 float   NLPACS::CSurfaceQuadTree::getInterpZ(const CVector &v) const
+00385 {
+00386         // first get final leaf for position
+00387         CVector pos = CVector(v.x, v.y, 0.0f);
+00388         if (_Root == NULL || !_BBox.include(pos))
+00389                 return v.z;     // return unmodified z
+00390 
+00391         const IQuadNode                         *node = _Root;
+00392         vector<uint>                            children;
+00393         vector<const IQuadNode*>        nodes;
+00394 
+00395         while (node != NULL && !node->isLeaf())
+00396         {
+00397                 nodes.push_back(node);
+00398 
+00399                 nlassert(node->getBBox().include(pos));
+00400                 uint    child;
+00401 
+00402                 if (pos.x > node->_XCenter)
+00403                         child = ((pos.y > node->_YCenter) ? 2 : 1);
+00404                 else
+00405                         child = ((pos.y > node->_YCenter) ? 3 : 0);
+00406 
+00407                 children.push_back(child);
+00408 
+00409                 node = node->getChild(child);
+00410         }
+00411 
+00412         if (node == NULL)
+00413                 return v.z;     // return unmodified z
+00414 
+00415         nodes.push_back(node);
+00416 
+00417         vector<const CQuadLeaf*>        leaves;
+00418         vector<const IQuadNode*>        explore;
+00419 
+00420         leaves.push_back((const CQuadLeaf*)node);
+00421 
+00422         // for each side of the leaf, find neighbor leaves
+00423         uint    side;
+00424         for (side=0; side<4; ++side)
+00425         {
+00426                 static const sint       ct[4][4] = { {-1, 1, 3,-1}, {-1,-1, 2, 0}, { 1,-1,-1, 3}, { 0, 2,-1,-1} };      // child table
+00427                 static const sint       nt[4][4] = { { 3, 1, 3, 1}, { 2, 0, 2, 0}, { 1, 3, 1, 3}, { 0, 2, 0, 2} };      // neighbor table
+00428 
+00429                 sint    nlev = nodes.size()-1;
+00430                 sint    child = -1;
+00431 
+00432                 while (nlev > 0)
+00433                 {
+00434                         child = ct[children[nlev-1]][side];
+00435 
+00436                         if (child >= 0)
+00437                                 break;
+00438 
+00439                         --nlev;
+00440                 }
+00441 
+00442                 // neighbor not found in root, leave
+00443                 if (nlev == 0)
+00444                         continue;
+00445 
+00446                 // get father
+00447                 node = nodes[nlev-1];
+00448 
+00449                 while (nlev < (sint)nodes.size() && node!=NULL && !node->isLeaf())
+00450                 {
+00451                         child = nt[children[nlev-1]][side];
+00452                         node = node->getChild(child);
+00453 
+00454                         ++nlev;
+00455                 }
+00456 
+00457                 if (node == NULL)
+00458                         continue;
+00459 
+00460                 if (node->isLeaf())
+00461                 {
+00462                         leaves.push_back((const CQuadLeaf*)node);
+00463                 }
+00464                 else
+00465                 {
+00466                         explore.push_back(node);
+00467 
+00468                         while (!explore.empty())
+00469                         {
+00470                                 node = explore.back();
+00471                                 explore.pop_back();
+00472 
+00473                                 if (node == NULL)
+00474                                         continue;
+00475 
+00476                                 if (node->isLeaf())
+00477                                         leaves.push_back((const CQuadLeaf*)node);
+00478                                 else
+00479                                 {
+00480                                         explore.push_back(node->getChild((side+2)&3));
+00481                                         explore.push_back(node->getChild((side+3)&3));
+00482                                 }
+00483                         }
+00484                 }
+00485         }
+00486 
+00487         uint                    i;
+00488         float                   di, wi;
+00489         float                   sum = 0.0;
+00490         float                   interpZ = 0.0;
+00491 
+00492         for (i=0; i<leaves.size(); ++i)
+00493         {
+00494                 di = (float)sqrt(sqr(v.x-leaves[i]->_XCenter)+sqr(v.y-leaves[i]->_YCenter))*(float)pow(1.5, leaves[i]->_Level);
+00495                 wi = 1.0f/di;
+00496                 sum += wi;
+00497                 interpZ += (leaves[i]->getMinHeight()+leaves[i]->getMaxHeight())*0.5f*wi;
+00498         }
+00499 
+00500         return interpZ / sum;
+00501 }
+
surface_quad.cpp
