Octree.h

Go to the documentation of this file.
00001 /*------------------------------------------------------------------------------
00002 
00003    Octree Component, version 2.1
00004    Copyright (c) 2004-2007,  Harrison Ainsworth / HXA7241.
00005 
00006    http://www.hxa7241.org/
00007 
00008 ------------------------------------------------------------------------------*/
00009 
00010 /*------------------------------------------------------------------------------
00011 
00012 Copyright (c) 2004-2007, Harrison Ainsworth / HXA7241.
00013 
00014 Redistribution and use in source and binary forms, with or without modification,
00015 are permitted provided that the following conditions are met:
00016 
00017 * Redistributions of source code must retain the above copyright notice, this
00018   list of conditions and the following disclaimer.
00019 * Redistributions in binary form must reproduce the above copyright notice, this
00020   list of conditions and the following disclaimer in the documentation and/or
00021   other materials provided with the distribution.
00022 * The name of the author may not be used to endorse or promote products derived
00023   from this software without specific prior written permission.
00024 
00025 THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR IMPLIED
00026 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
00027 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
00028 SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00029 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
00030 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00031 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00032 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
00033 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
00034 OF SUCH DAMAGE.
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    // null check unnecessary because Octree interface disallows nulls
00172    //if( pItem )
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    // null check unnecessary because Octree interface disallows nulls
00195    //if( pItem )
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    // step through each subcell
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       // delegate to single-cell test
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 }//namespace
00677 
00678 
00679 
00680 
00681 #endif//Octree_h

Generated on Fri Feb 13 13:58:10 2009 for meshmorph by  doxygen 1.5.1