00001
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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 ¢er, 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
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
00333
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
00387 CVector pos = CVector(v.x, v.y, 0.0f);
00388 if (_Root == NULL || !_BBox.include(pos))
00389 return v.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;
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
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} };
00427 static const sint nt[4][4] = { { 3, 1, 3, 1}, { 2, 0, 2, 0}, { 1, 3, 1, 3}, { 0, 2, 0, 2} };
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
00443 if (nlev == 0)
00444 continue;
00445
00446
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 }
