CDGrid.h

Go to the documentation of this file.

//    Copyright (C) 2004-2012 Dylan Blair
//
//    email: dblair@alumni.cs.utexas.edu
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef CDGRID_H
#define CDGRID_H

#include "../Utils_LIB/UHash.h"

#ifdef USE_EASTL
#include <EASTL/fixed_list.h>
#include <EASTL/fixed_map.h>
#endif //USE_EASTL

#include <vector>
#include <list>
#include <set>
#include <map>

#include "CDVolume.h"

namespace OpenSkyNet {
    namespace Utils {
        inline Utils::uint getCompositeKey(const Math::Point<Utils::uint>& bin_) {
            return getCompositeKey(bin_.x(), bin_.y(), bin_.z());
        }

        inline Utils::uint getCompositeKey(const Math::Point<int>& bin_) {
            assert(bin_.x() >= 0);
            assert(bin_.y() >= 0);
            assert(bin_.z() >= 0);
            return getCompositeKey(static_cast<Utils::uint>(bin_.x()), 
                static_cast<Utils::uint>(bin_.y()), static_cast<Utils::uint>(bin_.z()));
        }
    }

    namespace PF {
        class Manager;
    }

    namespace CD {
        enum DIRECTION { NONE, NEG_X, POS_X, NEG_Y, POS_Y, NEG_Z, POS_Z,
            //12 edges
            NEG_X_NEG_Y, NEG_X_POS_Y, NEG_X_NEG_Z, NEG_X_POS_Z,
            POS_X_NEG_Y, POS_X_POS_Y, POS_X_NEG_Z, POS_X_POS_Z,
            NEG_Y_NEG_Z, NEG_Y_POS_Z,
            POS_Y_NEG_Z, POS_Y_POS_Z,
            //8 corners
            NEG_X_NEG_Y_NEG_Z, NEG_X_NEG_Y_POS_Z, NEG_X_POS_Y_NEG_Z, NEG_X_POS_Y_POS_Z,
            POS_X_NEG_Y_NEG_Z, POS_X_NEG_Y_POS_Z, POS_X_POS_Y_NEG_Z, POS_X_POS_Y_POS_Z };

        const Utils::uint MAX_X_DIVISIONS_FOR_ALL_GRIDS = 64;

        const Utils::uint MAX_Y_DIVISIONS_FOR_ALL_GRIDS = 64;

        const Utils::uint MAX_Z_DIVISIONS_FOR_ALL_GRIDS = 64;

        extern Math::Point<int> g_binLookupTable[MAX_X_DIVISIONS_FOR_ALL_GRIDS][MAX_Y_DIVISIONS_FOR_ALL_GRIDS][MAX_Z_DIVISIONS_FOR_ALL_GRIDS];

        class Grid {
            #ifdef _WIN32
            #pragma warning(push)
            #pragma warning(disable:4100) //unreferenced formal parameter
            #endif
            Grid& operator=(const Grid& rhs_) { return *this; }
            #ifdef _WIN32
            #pragma warning(pop)
            #endif
        public:
            const Utils::uint INITIAL_X_DIVISIONS;

            const Utils::uint INITIAL_Y_DIVISIONS;

            const Utils::uint INITIAL_Z_DIVISIONS;

            const Utils::uint MAX_SUBDIVISIONS;

            const Utils::uint MAX_X_DIVISIONS;

            const Utils::uint MAX_Y_DIVISIONS;

            const Utils::uint MAX_Z_DIVISIONS;

            struct BinDir {
                const Math::Point<int>* _bin;
                DIRECTION _dir;
                BinDir(const Math::Point<int>& bin_, DIRECTION dir_) : _bin(&bin_), _dir(dir_) {}
            };

#ifdef USE_EASTL
            typedef eastl::fixed_list<CD::Volume*, 8> BinOccupiersList;
            typedef eastl::fixed_list<const Math::Point<int>*, 64> OccupiedBinsList;
            typedef eastl::fixed_map<const Math::Point<int>*, BinOccupiersList, 64> BinOccupiersMap;
            typedef eastl::fixed_map<CD::Volume*, OccupiedBinsList, 8> OccupiedBinsMap;
#else
            typedef std::list<CD::Volume*> BinOccupiersList;
            typedef std::list<const Math::Point<int>*> OccupiedBinsList;
            typedef std::map<const Math::Point<int>*, BinOccupiersList> BinOccupiersMap;
            typedef std::map<CD::Volume*, OccupiedBinsList> OccupiedBinsMap;
#endif
        protected:
            friend class PF::Manager;

            bool _didDynamicallyAllocateMem;

            const Math::Point<>** _corners;

            Math::Point<>* _maxCorner;

            Math::Point<>* _size;

            Math::Point<>* _binSize;

            std::set<CD::Volume*>** _nodes;

            bool _isSub;
            Utils::uint _subNum;
            Math::Point<Utils::uint> _axisDivisions;
            Math::Point<> _subBinSize;

            void makeSubGrid();

            void cullObjectOutside(int& minBinX_, int& maxBinX_, int& minBinY_, int& maxBinY_, int& minBinZ_, int& maxBinZ_) const;
            void cullObjectOutside(Math::Point<int>& bin_) const;

            void calcOccupiedBinsUsingOctalPartitioning(Volume* vol_, const Math::Point<Utils::uint>& minBin_, 
                const Math::Point<Utils::uint>& maxBin_, const Math::Point<>& maxCenter_);

            Utils::HashTableUIntKeys<unsigned short> _isBinOccupied;

            BinOccupiersMap _binOccupiers;
            OccupiedBinsMap _occupiedBins;
        public:
            Grid(Utils::uint initXDivs_, Utils::uint initYDivs_, Utils::uint initZDivs_, Utils::uint maxSubdivs_);
            Grid(const Grid& grid_);
            virtual ~Grid();


            static void init(Utils::uint initGlobalXDivs_, Utils::uint initGlobalYDivs_, Utils::uint initGlobalZDivs_, Utils::uint maxGlobalSubdivs_);

            void setCorners(const Math::Point<>* corners_);

            inline void setNodes(std::set<CD::Volume*>& nodes_) { *_nodes = &nodes_; }

            inline std::set<CD::Volume*>* getNodes() const { return *_nodes; }

            void resetGrid();

            static void resetAllGlobalGrids();


            virtual bool calcOccupiedBins(CD::Volume* vol_, bool calcPlanes_=true, bool useOctalPartitioning_=false, bool decrementPrevOccupiedBins_=false);

            virtual bool calcOccupiedBins(bool calcPlanes_=true, bool useOctalPartitioning_=false);

            inline const Math::Point<>& getMaxCorner() const { return *_maxCorner; }

            inline void translateMaxCorner() { *_maxCorner = (*_corners)[2]; }

            inline const Math::Point<>& getSize() const { return *_size; }

            inline const Math::Point<Utils::uint>& getAxisDivs() const { return _axisDivisions; }

            inline const Math::Point<>& getBinSize() const { return _subBinSize; }

            inline bool isSubdivided() const { return _isSub; }

            inline const Utils::uint& getSubNum() const { return _subNum; }

            inline void getBin(const Math::Point<>& p_, Math::Point<int>& bin_) const {
                bin_.x() = static_cast<int>(floor((_maxCorner->x()-p_.x())/_subBinSize.x()));
                bin_.y() = static_cast<int>(floor((_maxCorner->y()-p_.y())/_subBinSize.y()));
                bin_.z() = static_cast<int>(floor((_maxCorner->z()-p_.z())/_subBinSize.z()));
            }

            inline unsigned short getNumOccupants(const Math::Point<int>& bin_) {
                return _isBinOccupied.add(Utils::getCompositeKey(bin_));
            }

            inline bool decrementBin(const Math::Point<int>& bin_) {
                unsigned short& currVal = _isBinOccupied.add(Utils::getCompositeKey(bin_));
                //currVal == 0 iff this bin is not occupied
                if (currVal) {
                    --currVal;
                    return true;
                }
                return false;
            }

            inline void incrementBin(const Math::Point<int>& bin_) {
                ++_isBinOccupied.add(Utils::getCompositeKey(bin_));
            }

            inline void clearBin(const Math::Point<int>& bin_) {
                _isBinOccupied.add(Utils::getCompositeKey(bin_)) = 0;
            }

            bool isObjectOutside(const int& minBinX_, const int& maxBinX_, const int& minBinY_,
                const int& maxBinY_, const int& minBinZ_, const int& maxBinZ_) const;

            bool isObjectOutside(const Math::Point<int>& bin_) const;

            void getOccupiedBins(std::vector<const Math::Point<int>* >& bins_) const;

            inline OccupiedBinsList& getOccupiedBins(CD::Volume* vol_) {
                return _occupiedBins[vol_];
            }

            inline BinOccupiersList& getOccupiers(const Math::Point<int>* bin_) {
                return _binOccupiers[bin_];
            }

            void getNeighbors(const Math::Point<int>& bin_, 
                std::vector<BinDir>& neighbors_, Utils::uint numOccupants_=0, 
                bool allowDiagonals_=false, bool allowCorners_=false) const;

            Math::Point<> translatePointByBin(const Math::Point<>& p_, const Math::Point<int>& bin_) const;

            Math::Point<> getNearestBinCenter(const Math::Point<>& p_) const;

            static void shutDown();
        };

        extern CD::Grid* g_initialGrid;
        #define MAX_GLOBAL_GRID_SUBDIVISIONS 2
        #if MAX_GLOBAL_GRID_SUBDIVISIONS > 0
            extern CD::Grid* g_subdividedGrids[MAX_GLOBAL_GRID_SUBDIVISIONS];
        #else
            //can't have zero-sized array
            extern CD::Grid* g_subdividedGrids[1];
        #endif
    }
}

#endif //CDGRID_H