00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef Octree_h
00040 #define Octree_h
00041
00042
00043 #include "OctreeImplementation.h"
00044
00045
00046
00047
00048 namespace hxa7241_graphics
00049 {
00050
00051
00095 template<class TYPE>
00096 class OctreeAgent
00097 : public OctreeAgentV
00098 {
00100 protected:
00101 OctreeAgent() {}
00102 public:
00103 virtual ~OctreeAgent() {}
00104 private:
00105 OctreeAgent( const OctreeAgent& );
00106 OctreeAgent& operator=( const OctreeAgent& );
00107
00108
00110 public:
00112 virtual bool isOverlappingCellV ( const void* pItem,
00113 const Vector3r& lowerCorner,
00114 const Vector3r& upperCorner ) const;
00115 virtual dword getSubcellOverlapsV( const void* pItem,
00116 const Vector3r& lower,
00117 const Vector3r& middle,
00118 const Vector3r& upper ) const;
00119
00120
00122 protected:
00124
00127 virtual bool isOverlappingCell ( const TYPE& item,
00128 const Vector3r& lowerCorner,
00129 const Vector3r& upperCorner ) const =0;
00150 virtual dword getSubcellOverlaps( const TYPE& item,
00151 const Vector3r& lowerCorner,
00152 const Vector3r& middlePoint,
00153 const Vector3r& upperCorner ) const;
00154 };
00155
00156
00157
00158
00160 template<class TYPE>
00161 inline
00162 bool OctreeAgent<TYPE>::isOverlappingCellV
00163 (
00164 const void* pItem,
00165 const Vector3r& lowerCorner,
00166 const Vector3r& upperCorner
00167 ) const
00168 {
00169 bool is = false;
00170
00171
00172
00173 {
00174 is = isOverlappingCell( *reinterpret_cast<const TYPE*>( pItem ),
00175 lowerCorner, upperCorner );
00176 }
00177
00178 return is;
00179 }
00180
00181
00182 template<class TYPE>
00183 inline
00184 dword OctreeAgent<TYPE>::getSubcellOverlapsV
00185 (
00186 const void* pItem,
00187 const Vector3r& lower,
00188 const Vector3r& middle,
00189 const Vector3r& upper
00190 ) const
00191 {
00192 dword ov = ALL_OUTSIDE;
00193
00194
00195
00196 {
00197 ov = getSubcellOverlaps( *reinterpret_cast<const TYPE*>( pItem ),
00198 lower, middle, upper );
00199 }
00200
00201 return ov;
00202 }
00203
00204
00206 template<class TYPE>
00207 dword OctreeAgent<TYPE>::getSubcellOverlaps
00208 (
00209 const TYPE& item,
00210 const Vector3r& lowerCorner,
00211 const Vector3r& middlePoint,
00212 const Vector3r& upperCorner
00213 ) const
00214 {
00215 dword flags = ALL_OUTSIDE;
00216
00217 const Vector3r* lowMidPoints[] = { &lowerCorner, &middlePoint };
00218 const Vector3r* midHighPoints[] = { &middlePoint, &upperCorner };
00219
00220
00221 for( dword i = 8; i-- > 0; )
00222 {
00223 const Vector3r cellLowerCorner( lowMidPoints[ i & 1]->getX(),
00224 lowMidPoints[(i >> 1) & 1]->getY(),
00225 lowMidPoints[(i >> 2) & 1]->getZ() );
00226 const Vector3r cellUpperCorner( midHighPoints[ i & 1]->getX(),
00227 midHighPoints[(i >> 1) & 1]->getY(),
00228 midHighPoints[(i >> 2) & 1]->getZ() );
00229
00230 flags |= static_cast<dword>(isOverlappingCell( item, cellLowerCorner,
00231 cellUpperCorner )) << i;
00232 }
00233
00234 return flags;
00235 }
00236
00237
00238
00239
00274 template<class TYPE>
00275 class OctreeVisitor
00276 : public OctreeVisitorV
00277 {
00279 protected:
00280 OctreeVisitor() {}
00281 public:
00282 virtual ~OctreeVisitor() {}
00283 private:
00284 OctreeVisitor( const OctreeVisitor& );
00285 OctreeVisitor& operator=( const OctreeVisitor& );
00286
00287
00289 public:
00291 virtual void visitRootV ( const OctreeCell* pRootCell,
00292 const OctreeData& octreeData );
00293 virtual void visitBranchV( const OctreeCell* subCells[8],
00294 const OctreeData& octreeData );
00295 virtual void visitLeafV ( const Array<const void*>& items,
00296 const OctreeData& octreeData );
00297
00298
00300 protected:
00302
00308 virtual void visitRoot ( const OctreeCell* pRootCell,
00309 const OctreeData& octreeData ) =0;
00317 virtual void visitBranch( const OctreeCell* subCells[8],
00318 const OctreeData& octreeData ) =0;
00323 virtual void visitLeaf ( const Array<const TYPE*>& items,
00324 const OctreeData& octreeData ) =0;
00325 };
00326
00327
00328
00329
00331 template<class TYPE>
00332 inline
00333 void OctreeVisitor<TYPE>::visitRootV
00334 (
00335 const OctreeCell* pRootCell,
00336 const OctreeData& octreeData
00337 )
00338 {
00339 visitRoot( pRootCell, octreeData );
00340 }
00341
00342
00343 template<class TYPE>
00344 inline
00345 void OctreeVisitor<TYPE>::visitBranchV
00346 (
00347 const OctreeCell* subCells[8],
00348 const OctreeData& octreeData
00349 )
00350 {
00351 visitBranch( subCells, octreeData );
00352 }
00353
00354
00355 template<class TYPE>
00356 inline
00357 void OctreeVisitor<TYPE>::visitLeafV
00358 (
00359 const Array<const void*>& items,
00360 const OctreeData& octreeData
00361 )
00362 {
00363 visitLeaf( reinterpret_cast<const Array<const TYPE*>&>( items ),
00364 octreeData );
00365 }
00366
00367
00368
00369
00370
00371
00372
00373
00411 template<class TYPE>
00412 class Octree
00413 {
00415 public:
00424 Octree( const Vector3r& positionOfLowerCorner,
00425 real sizeOfCube,
00426 dword maxItemCountPerCell,
00427 dword maxLevelCount,
00428 real minCellSize );
00429
00430 ~Octree();
00431 Octree( const Octree& );
00437 Octree& operator=( const Octree& );
00438
00439
00441
00452 bool insert( const TYPE& item,
00453 const OctreeAgent<TYPE>& agent );
00465 bool remove( const TYPE& item,
00466 const OctreeAgent<TYPE>& agent );
00467
00468
00470
00474 void visit( OctreeVisitor<TYPE>& visitor ) const;
00475
00479 bool isEmpty() const;
00488 void getInfo( dword& byteSize,
00489 dword& leafCount,
00490 dword& itemRefCount,
00491 dword& maxDepth ) const;
00492
00496 const Vector3r& getPosition() const;
00500 real getSize() const;
00504 dword getMaxItemCountPerCell() const;
00508 dword getMaxLevelCount() const;
00512 real getMinCellSize() const;
00513
00514
00516 private:
00517 OctreeRoot root_m;
00518 };
00519
00520
00521
00522
00524
00526 template<class TYPE>
00527 inline
00528 Octree<TYPE>::Octree
00529 (
00530 const Vector3r& position,
00531 const real sizeOfCube,
00532 const dword maxItemCountPerCell,
00533 const dword maxLevelCount,
00534 const real minCellSize
00535 )
00536 : root_m( position, sizeOfCube, maxItemCountPerCell, maxLevelCount,
00537 minCellSize )
00538 {
00539 }
00540
00541
00542 template<class TYPE>
00543 inline
00544 Octree<TYPE>::~Octree()
00545 {
00546 }
00547
00548
00549 template<class TYPE>
00550 inline
00551 Octree<TYPE>::Octree
00552 (
00553 const Octree& other
00554 )
00555 : root_m( other.root_m )
00556 {
00557 }
00558
00559
00560 template<class TYPE>
00561 inline
00562 Octree<TYPE>& Octree<TYPE>::operator=
00563 (
00564 const Octree& other
00565 )
00566 {
00567 root_m = other.root_m;
00568
00569 return *this;
00570 }
00571
00572
00573
00574
00576 template<class TYPE>
00577 inline
00578 bool Octree<TYPE>::insert
00579 (
00580 const TYPE& item,
00581 const OctreeAgent<TYPE>& agent
00582 )
00583 {
00584 return root_m.insert( &item, agent );
00585 }
00586
00587
00588 template<class TYPE>
00589 inline
00590 bool Octree<TYPE>::remove
00591 (
00592 const TYPE& item,
00593 const OctreeAgent<TYPE>& agent
00594 )
00595 {
00596 return root_m.remove( &item, agent );
00597 }
00598
00599
00600
00601
00603 template<class TYPE>
00604 inline
00605 void Octree<TYPE>::visit
00606 (
00607 OctreeVisitor<TYPE>& visitor
00608 ) const
00609 {
00610 root_m.visit( visitor );
00611 }
00612
00613
00614 template<class TYPE>
00615 inline
00616 bool Octree<TYPE>::isEmpty() const
00617 {
00618 return root_m.isEmpty();
00619 }
00620
00621
00622 template<class TYPE>
00623 inline
00624 void Octree<TYPE>::getInfo
00625 (
00626 dword& byteSize,
00627 dword& leafCount,
00628 dword& itemRefCount,
00629 dword& maxDepth
00630 ) const
00631 {
00632 root_m.getInfo( sizeof(*this), byteSize, leafCount, itemRefCount, maxDepth );
00633 }
00634
00635
00636 template<class TYPE>
00637 inline
00638 const Vector3r& Octree<TYPE>::getPosition() const
00639 {
00640 return root_m.getPosition();
00641 }
00642
00643
00644 template<class TYPE>
00645 inline
00646 real Octree<TYPE>::getSize() const
00647 {
00648 return root_m.getSize();
00649 }
00650
00651
00652 template<class TYPE>
00653 inline
00654 dword Octree<TYPE>::getMaxItemCountPerCell() const
00655 {
00656 return root_m.getMaxItemCountPerCell();
00657 }
00658
00659
00660 template<class TYPE>
00661 inline
00662 dword Octree<TYPE>::getMaxLevelCount() const
00663 {
00664 return root_m.getMaxLevelCount();
00665 }
00666
00667
00668 template<class TYPE>
00669 inline
00670 real Octree<TYPE>::getMinCellSize() const
00671 {
00672 return root_m.getMinCellSize();
00673 }
00674
00675
00676 }
00677
00678
00679
00680
00681 #endif//Octree_h