PF_API 0.52

Code/Libs/CD_LIB/CDGrid.h

Go to the documentation of this file.
00001 
00002 //    Copyright (C) 2004-2011 Dylan Blair
00003 //
00004 //    email: dblair@alumni.cs.utexas.edu
00005 //
00006 //    This library is free software; you can redistribute it and/or
00007 //    modify it under the terms of the GNU Lesser General Public
00008 //    License as published by the Free Software Foundation; either
00009 //    version 2.1 of the License, or (at your option) any later version.
00010 //
00011 //    This library is distributed in the hope that it will be useful,
00012 //    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 //    Lesser General Public License for more details.
00015 //
00016 //    You should have received a copy of the GNU Lesser General Public
00017 //    License along with this library; if not, write to the Free Software
00018 //    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020 
00021 #ifndef CDGRID_H
00022 #define CDGRID_H
00023 
00024 #include <vector>
00025 #include <list>
00026 #include <set>
00027 #include <map>
00028 
00029 #include "../Utils_LIB/UHash.h"
00030 
00031 #include "CDVolume.h"
00032 
00033 namespace OpenSkyNet {
00034     namespace Utils {
00036         inline Utils::uint getCompositeKey(const Math::Point<Utils::uint>& bin_) {
00037             return getCompositeKey(bin_.x(), bin_.y(), bin_.z());
00038         }
00039 
00041         inline Utils::uint getCompositeKey(const Math::Point<int>& bin_) {
00042             assert(bin_.x() >= 0);
00043             assert(bin_.y() >= 0);
00044             assert(bin_.z() >= 0);
00045             return getCompositeKey(static_cast<Utils::uint>(bin_.x()), 
00046                 static_cast<Utils::uint>(bin_.y()), static_cast<Utils::uint>(bin_.z()));
00047         }
00048     }
00049 
00050     namespace PF {
00051         class Manager;
00052     }
00053 
00054     namespace CD {
00056         enum DIRECTION { NONE, NEG_X, POS_X, NEG_Y, POS_Y, NEG_Z, POS_Z,
00057             //12 edges
00058             NEG_X_NEG_Y, NEG_X_POS_Y, NEG_X_NEG_Z, NEG_X_POS_Z,
00059             POS_X_NEG_Y, POS_X_POS_Y, POS_X_NEG_Z, POS_X_POS_Z,
00060             NEG_Y_NEG_Z, NEG_Y_POS_Z,
00061             POS_Y_NEG_Z, POS_Y_POS_Z,
00062             //8 corners
00063             NEG_X_NEG_Y_NEG_Z, NEG_X_NEG_Y_POS_Z, NEG_X_POS_Y_NEG_Z, NEG_X_POS_Y_POS_Z,
00064             POS_X_NEG_Y_NEG_Z, POS_X_NEG_Y_POS_Z, POS_X_POS_Y_NEG_Z, POS_X_POS_Y_POS_Z };
00065 
00067         const Utils::uint MAX_X_DIVISIONS_FOR_ALL_GRIDS = 64;
00068 
00070         const Utils::uint MAX_Y_DIVISIONS_FOR_ALL_GRIDS = 64;
00071 
00073         const Utils::uint MAX_Z_DIVISIONS_FOR_ALL_GRIDS = 64;
00074 
00079         extern Math::Point<int> g_binLookupTable[MAX_X_DIVISIONS_FOR_ALL_GRIDS][MAX_Y_DIVISIONS_FOR_ALL_GRIDS][MAX_Z_DIVISIONS_FOR_ALL_GRIDS];
00080 
00087         class Grid {
00088             #ifdef _WIN32
00089             #pragma warning(push)
00090             #pragma warning(disable:4100) //unreferenced formal parameter
00091             #endif
00092             Grid& operator=(const Grid& rhs_) { return *this; }
00093             #ifdef _WIN32
00094             #pragma warning(pop)
00095             #endif
00096         public:
00098             const Utils::uint INITIAL_X_DIVISIONS;
00099 
00101             const Utils::uint INITIAL_Y_DIVISIONS;
00102 
00104             const Utils::uint INITIAL_Z_DIVISIONS;
00105 
00107             const Utils::uint MAX_SUBDIVISIONS;
00108 
00110             const Utils::uint MAX_X_DIVISIONS;
00111 
00113             const Utils::uint MAX_Y_DIVISIONS;
00114 
00116             const Utils::uint MAX_Z_DIVISIONS;
00117 
00123             struct BinDir {
00124                 const Math::Point<int>* _bin;
00125                 DIRECTION _dir;
00126                 BinDir(const Math::Point<int>& bin_, DIRECTION dir_) : _bin(&bin_), _dir(dir_) {}
00127             };
00128         protected:
00129             friend class PF::Manager;
00130 
00131             bool _didDynamicallyAllocateMem;
00132 
00133             const Math::Point<>** _corners;
00134 
00136             Math::Point<>* _maxCorner;
00137 
00138             Math::Point<>* _size;
00139 
00142             Math::Point<>* _binSize;
00143 
00144             std::set<CD::Volume*>** _nodes;
00145 
00146             bool _isSub;
00147             Utils::uint _subNum;
00148             Math::Point<Utils::uint> _axisDivisions;
00149             Math::Point<> _subBinSize;
00150 
00151             void makeSubGrid();
00152 
00153             void cullObjectOutside(int& minBinX_, int& maxBinX_, int& minBinY_, int& maxBinY_, int& minBinZ_, int& maxBinZ_) const;
00154             void cullObjectOutside(Math::Point<int>& bin_) const;
00155 
00156             void calcOccupiedBinsUsingOctalPartitioning(Volume* vol_, const Math::Point<Utils::uint>& minBin_, 
00157                 const Math::Point<Utils::uint>& maxBin_, const Math::Point<>& maxCenter_);
00158 
00159             Utils::HashTableUIntKeys<unsigned short> _isBinOccupied;
00160 
00162             std::map<const Math::Point<int>*, std::list<CD::Volume*> > _binOccupiers;
00163             std::map<const CD::Volume*, std::list<const Math::Point<int>*> > _occupiedBins;
00164         public:
00165             Grid(Utils::uint initXDivs_, Utils::uint initYDivs_, Utils::uint initZDivs_, Utils::uint maxSubdivs_);
00166             Grid(const Grid& grid_);
00167             virtual ~Grid();
00168 
00171 
00172             static void init(Utils::uint initGlobalXDivs_, Utils::uint initGlobalYDivs_, Utils::uint initGlobalZDivs_, Utils::uint maxGlobalSubdivs_);
00173 
00182             void setCorners(const Math::Point<>* corners_);
00183 
00185             inline void setNodes(std::set<CD::Volume*>& nodes_) { *_nodes = &nodes_; }
00186 
00187             inline std::set<CD::Volume*>* getNodes() const { return *_nodes; }
00188 
00189             void resetGrid();
00190 
00193             static void resetAllGlobalGrids();
00194 
00196 
00202             virtual bool calcOccupiedBins(CD::Volume* vol_, bool calcPlanes_=true, bool useOctalPartitioning_=false, bool decrementPrevOccupiedBins_=false);
00203 
00208             virtual bool calcOccupiedBins(bool calcPlanes_=true, bool useOctalPartitioning_=false);
00209 
00211             inline const Math::Point<>& getMaxCorner() const { return *_maxCorner; }
00212 
00215             inline void translateMaxCorner() { *_maxCorner = (*_corners)[2]; }
00216 
00218             inline const Math::Point<>& getSize() const { return *_size; }
00219 
00221             inline const Math::Point<Utils::uint>& getAxisDivs() const { return _axisDivisions; }
00222 
00225             inline const Math::Point<>& getBinSize() const { return _subBinSize; }
00226 
00227             inline bool isSubdivided() const { return _isSub; }
00228 
00230             inline const Utils::uint& getSubNum() const { return _subNum; }
00231 
00233             inline void getBin(const Math::Point<>& p_, Math::Point<int>& bin_) const {
00234                 bin_.x() = static_cast<int>(floor((_maxCorner->x()-p_.x())/_subBinSize.x()));
00235                 bin_.y() = static_cast<int>(floor((_maxCorner->y()-p_.y())/_subBinSize.y()));
00236                 bin_.z() = static_cast<int>(floor((_maxCorner->z()-p_.z())/_subBinSize.z()));
00237             }
00238 
00239             inline unsigned short getNumOccupants(const Math::Point<int>& bin_) {
00240                 return _isBinOccupied.add(Utils::getCompositeKey(bin_));
00241             }
00242 
00244             inline bool decrementBin(const Math::Point<int>& bin_) {
00245                 unsigned short& currVal = _isBinOccupied.add(Utils::getCompositeKey(bin_));
00246                 //currVal == 0 iff this bin is not occupied
00247                 if (currVal) {
00248                     --currVal;
00249                     return true;
00250                 }
00251                 return false;
00252             }
00253 
00255             inline void incrementBin(const Math::Point<int>& bin_) {
00256                 ++_isBinOccupied.add(Utils::getCompositeKey(bin_));
00257             }
00258 
00260             inline void clearBin(const Math::Point<int>& bin_) {
00261                 _isBinOccupied.add(Utils::getCompositeKey(bin_)) = 0;
00262             }
00263 
00265             bool isObjectOutside(const int& minBinX_, const int& maxBinX_, const int& minBinY_,
00266                 const int& maxBinY_, const int& minBinZ_, const int& maxBinZ_) const;
00267 
00268             bool isObjectOutside(const Math::Point<int>& bin_) const;
00269 
00271             void getOccupiedBins(std::vector<const Math::Point<int>* >& bins_) const;
00272 
00273             inline std::list<const Math::Point<int>*>& getOccupiedBins(const CD::Volume* vol_) {
00274                 return _occupiedBins[vol_];
00275             }
00276 
00277             inline std::list<CD::Volume*>& getOccupiers(const Math::Point<int>* bin_) {
00278                 return _binOccupiers[bin_];
00279             }
00280 
00281             void getNeighbors(const Math::Point<int>& bin_, 
00282                 std::vector<BinDir>& neighbors_, Utils::uint numOccupants_=0, 
00283                 bool allowDiagonals_=false, bool allowCorners_=false) const;
00284 
00285             Math::Point<> translatePointByBin(const Math::Point<>& p_, const Math::Point<int>& bin_) const;
00286 
00287             Math::Point<> getNearestBinCenter(const Math::Point<>& p_) const;
00288 
00291             static void shutDown();
00293         };
00294 
00295         extern CD::Grid* g_initialGrid;
00296         #define MAX_GLOBAL_GRID_SUBDIVISIONS 2
00297         #if MAX_GLOBAL_GRID_SUBDIVISIONS > 0
00298             extern CD::Grid* g_subdividedGrids[MAX_GLOBAL_GRID_SUBDIVISIONS];
00299         #else
00300             //can't have zero-sized array
00301             extern CD::Grid* g_subdividedGrids[1];
00302         #endif
00303     }
00304 }
00305 
00306 #endif //CDGRID_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines