Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages | Search for 

NLPACS::CSurfaceQuadTree Class Reference

#include <surface_quad.h>


Public Member Functions

void addVertex (const NLMISC::CVector &v)
bool check () const
void clear ()
void compile ()
 CSurfaceQuadTree (const CSurfaceQuadTree &quad)
 CSurfaceQuadTree ()
const NLMISC::CAABBox & getBBox () const
float getInterpZ (const NLMISC::CVector &v) const
const CQuadLeaf * getLeaf (const NLMISC::CVector &v) const
uint8 getMaxLevel () const
float getMaxThickness () const
const IQuadNode * getRoot () const
void init (float maxThickness, uint maxLevel, const NLMISC::CVector &center, float halfSize=80.0f)
CSurfaceQuadTree & operator= (const CSurfaceQuadTree &quad)
void serial (NLMISC::IStream &f)
void translate (const NLMISC::CVector &translation)

Protected Attributes

NLMISC::CAABBox _BBox
uint8 _MaxLevel
float _MaxThickness
IQuadNode * _Root

Constructor & Destructor Documentation

NLPACS::CSurfaceQuadTree::CSurfaceQuadTree (   ) 
 

Definition at line 37 of file surface_quad.cpp.

References _MaxLevel, NLMISC::CAABBox::setCenter(), and NLMISC::CAABBox::setSize(). 

00038 {
00039         _Root = NULL;
00040         _MaxThickness = FLT_MAX;
00041         _MaxLevel = 1;
00042         _BBox.setCenter(CVector::Null);
00043         _BBox.setSize(CVector::Null);
00044 }

NLPACS::CSurfaceQuadTree::CSurfaceQuadTree (  const CSurfaceQuadTree &  quad  ) 
 

Definition at line 46 of file surface_quad.cpp. 

00047 {
00048         *this = quad;
00049 }

Member Function Documentation

void NLPACS::CSurfaceQuadTree::addVertex (  const NLMISC::CVector &  v  ) 
 

Definition at line 96 of file surface_quad.cpp.

References NLPACS::IQuadNode::_HalfSize, NLPACS::IQuadNode::_MaxHeight, _MaxLevel, NLPACS::IQuadNode::_MaxThickness, NLPACS::IQuadNode::_MinHeight, NLPACS::IQuadNode::_XCenter, NLPACS::IQuadNode::_YCenter, NLPACS::IQuadNode::addVertex(), NLMISC::CAABBox::getCenter(), NLMISC::CAABBox::getHalfSize(), NLMISC::CAABBox::include(), v, NLMISC::CVector::x, and NLMISC::CVector::y.

Referenced by NLPACS::computeSurfaceQuadTree(). 

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 }

bool NLPACS::CSurfaceQuadTree::check (   )  const
 

Definition at line 297 of file surface_quad.cpp.

References NLPACS::IQuadNode::check(). 

00298 {
00299         if (_Root != NULL)
00300                 return _Root->check();
00301         return true;
00302 }

void NLPACS::CSurfaceQuadTree::clear (   ) 
 

Definition at line 80 of file surface_quad.cpp.

Referenced by NLPACS::computeSurfaceQuadTree(), and init(). 

00081 {
00082         delete _Root;
00083         _Root = NULL;
00084 }

void NLPACS::CSurfaceQuadTree::compile (   ) 
 

Definition at line 123 of file surface_quad.cpp.

References NLPACS::IQuadNode::getMaxHeight(), NLPACS::IQuadNode::getMinHeight(), and NLPACS::IQuadNode::isLeaf().

Referenced by NLPACS::computeSurfaceQuadTree(). 

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 }

const NLMISC::CAABBox& NLPACS::CSurfaceQuadTree::getBBox (   )  const [inline]
 

Definition at line 172 of file surface_quad.h. 

00172 { return _BBox; }

float NLPACS::CSurfaceQuadTree::getInterpZ (  const NLMISC::CVector &  v  )  const
 

Definition at line 384 of file surface_quad.cpp.

References NLPACS::IQuadNode::_XCenter, NLPACS::IQuadNode::_YCenter, NLPACS::IQuadNode::getBBox(), NLPACS::CQuadLeaf::getChild(), NLPACS::IQuadNode::getChild(), NLMISC::CAABBox::include(), NLPACS::CQuadLeaf::isLeaf(), NLPACS::IQuadNode::isLeaf(), nlassert, sint, NLMISC::sqr(), uint, v, NLMISC::CVector::x, and NLMISC::CVector::y. 

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 }

const NLPACS::CQuadLeaf * NLPACS::CSurfaceQuadTree::getLeaf (  const NLMISC::CVector &  v  )  const
 

Definition at line 304 of file surface_quad.cpp.

References NLPACS::IQuadNode::_XCenter, NLPACS::IQuadNode::_YCenter, NLPACS::IQuadNode::getBBox(), NLPACS::IQuadNode::getChild(), NLMISC::CAABBox::include(), NLPACS::IQuadNode::isLeaf(), nlassert, uint, v, NLMISC::CVector::x, and NLMISC::CVector::y. 

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 }

uint8 NLPACS::CSurfaceQuadTree::getMaxLevel (   )  const [inline]
 

Definition at line 171 of file surface_quad.h.

References _MaxLevel, and uint8. 

00171 { return _MaxLevel; }

float NLPACS::CSurfaceQuadTree::getMaxThickness (   )  const [inline]
 

Definition at line 170 of file surface_quad.h. 

00170 { return _MaxThickness; }

const IQuadNode* NLPACS::CSurfaceQuadTree::getRoot (   )  const [inline]
 

Definition at line 169 of file surface_quad.h. 

00169 { return _Root; }

void NLPACS::CSurfaceQuadTree::init (  float  maxThickness,
uint  maxLevel,
const NLMISC::CVector &  center,
float  halfSize = 80.0f
) 
 

Definition at line 86 of file surface_quad.cpp.

References _MaxLevel, clear(), nlassert, NLMISC::CAABBox::setCenter(), NLMISC::CAABBox::setHalfSize(), and uint.

Referenced by NLPACS::computeSurfaceQuadTree(). 

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 }

NLPACS::CSurfaceQuadTree & NLPACS::CSurfaceQuadTree::operator= (  const CSurfaceQuadTree &  quad  ) 
 

Definition at line 51 of file surface_quad.cpp.

References _BBox, _MaxLevel, _MaxThickness, _Root, and NLPACS::IQuadNode::isLeaf(). 

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 }

void NLPACS::CSurfaceQuadTree::serial (  NLMISC::IStream &  f  ) 
 

Definition at line 329 of file surface_quad.cpp.

References _MaxLevel, NLPACS::IQuadNode::isLeaf(), NLMISC::IStream::isReading(), nlerror, NLPACS::IQuadNode::serial(), NLPACS::CQuadBranch::serial(), NLPACS::CQuadLeaf::serial(), NLMISC::IStream::serial(), NLMISC::IStream::serialVersion(), and uint8. 

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 }

void NLPACS::CSurfaceQuadTree::translate (  const NLMISC::CVector &  translation  )  [inline]
 

Definition at line 184 of file surface_quad.h.

References NLMISC::CAABBox::getCenter(), NLMISC::CAABBox::setCenter(), and NLPACS::IQuadNode::translate().

Referenced by NLPACS::CRetrievableSurface::translate(). 

00185         {
00186                 _BBox.setCenter(_BBox.getCenter()+translation);
00187                 if (_Root != NULL)
00188                         _Root->translate(translation);
00189         }

Field Documentation

NLMISC::CAABBox NLPACS::CSurfaceQuadTree::_BBox [protected]
 

Definition at line 161 of file surface_quad.h.

Referenced by operator=().

uint8 NLPACS::CSurfaceQuadTree::_MaxLevel [protected]
 

Definition at line 160 of file surface_quad.h.

Referenced by addVertex(), CSurfaceQuadTree(), getMaxLevel(), init(), operator=(), and serial().

float NLPACS::CSurfaceQuadTree::_MaxThickness [protected]
 

Definition at line 159 of file surface_quad.h.

Referenced by operator=().

IQuadNode* NLPACS::CSurfaceQuadTree::_Root [protected]
 

Definition at line 158 of file surface_quad.h.

Referenced by operator=().

The documentation for this class was generated from the following files:
Generated on Tue Mar 16 14:24:31 2004 for NeL by doxygen 1.3.6