BVB Source Codes

CRYENGINE Show HashSpace.h Source code

Return Download CRYENGINE: download HashSpace.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. /********************************************************************
  4.    CryGame Source File.
  5.    -------------------------------------------------------------------------
  6.    File name:   HashSpace.h
  7.    Version:     v1.00
  8.    Description:
  9.  
  10.    -------------------------------------------------------------------------
  11.    History:
  12.    - 20:7:2005   Created by Danny Chapman
  13.  
  14.  *********************************************************************/
  15. #ifndef HASHSPACE_H
  16. #define HASHSPACE_H
  17.  
  18. #if _MSC_VER > 1000
  19.         #pragma once
  20. #endif
  21.  
  22. #include <CrySystem/File/CryFile.h>
  23.  
  24. #include <vector>
  25.  
  26. // [markusm] i will remove this comment
  27. //#pragma optimize("", off)
  28. //#pragma inline_depth(0)
  29.  
  30. template<typename T>
  31. class CHashSpaceTraits
  32. {
  33. public:
  34.         const Vec3& operator()(const T& item) const { return item.GetPos(); }
  35. };
  36.  
  37. /// Contains any type that can be represented with a single position, obtained
  38. /// through T::GetPos()
  39. template<typename T, typename TraitsT = CHashSpaceTraits<T>>
  40. class CHashSpace : public TraitsT
  41. {
  42. public:
  43.         typedef TraitsT Traits;
  44.  
  45.         //simple iterator encapsulating the lookup from processobjecstwithinrange
  46.         //to reduce code duplication
  47.         class CRadialIterator
  48.         {
  49.         public:
  50.  
  51.                 CRadialIterator(const Vec3& pos, float radius, const CHashSpace<T, TraitsT>& hashSpace) : m_curIndex(0), m_radiusSQ(square(radius)), m_Pos(pos), m_object(NULL), m_hashSpace(hashSpace)
  52.                 {
  53.                         int32 starti;
  54.                         hashSpace.GetIJKFromPosition(pos - Vec3(radius, radius, radius), starti, m_startJ, m_startK);
  55.                         hashSpace.GetIJKFromPosition(pos + Vec3(radius, radius, radius), m_endI, m_endJ, m_endK);
  56.  
  57.                         m_curI = starti;
  58.                         m_curJ = m_startJ;
  59.                         m_curK = m_startK;
  60.  
  61.                         operator++();
  62.                 }
  63.  
  64.                 ~CRadialIterator() {}
  65.  
  66.                 operator T*()
  67.                 {
  68.                         return const_cast<T*>(m_object);
  69.                 }
  70.  
  71.                 operator const T*() const
  72.                 {
  73.                         return m_object;
  74.                 }
  75.  
  76.                 float GetCurDistSQ() const
  77.                 {
  78.                         return m_curDistSQ;
  79.                 }
  80.  
  81.                 CRadialIterator operator++(int)
  82.                 {
  83.                         CRadialIterator temp = *this;
  84.  
  85.                         operator++();
  86.  
  87.                         return temp;
  88.                 }
  89.  
  90.                 void operator++()
  91.                 {
  92.                         m_object = NULL;
  93.  
  94.                         for (; m_curI <= m_endI; ++m_curI)
  95.                         {
  96.                                 for (; m_curJ <= m_endJ; ++m_curJ)
  97.                                 {
  98.                                         for (; m_curK <= m_endK; ++m_curK)
  99.                                         {
  100.                                                 unsigned index = m_hashSpace.GetHashBucketIndex(m_curI, m_curJ, m_curK);
  101.                                                 unsigned mask = m_hashSpace.GetLocationMask(m_curI, m_curJ, m_curK);
  102.                                                 const Objects& objects = m_hashSpace.m_cells[index].objects;
  103.                                                 const std::vector<unsigned>& masks = m_hashSpace.m_cells[index].masks;
  104.  
  105.                                                 uint32 count = objects.size();
  106.                                                 for (; m_curIndex < count; ++m_curIndex)
  107.                                                 {
  108.                                                         if (mask != masks[m_curIndex]) continue;
  109.                                                         const T& object = objects[m_curIndex];
  110.                                                         m_curDistSQ = Distance::Point_PointSq(m_Pos, m_hashSpace.GetPos(object));
  111.                                                         if (m_curDistSQ < m_radiusSQ)
  112.                                                         {
  113.                                                                 m_object = &object;
  114.                                                                 ++m_curIndex;
  115.                                                                 return;
  116.                                                         }
  117.                                                 }
  118.  
  119.                                                 m_curIndex = 0;
  120.                                         }
  121.  
  122.                                         m_curK = m_startK;
  123.                                 }
  124.  
  125.                                 m_curJ = m_startJ;
  126.                         }
  127.  
  128.                         m_curDistSQ = -1.0f;
  129.                 }
  130.  
  131.         private:
  132.  
  133.                 int32                         m_startJ;
  134.                 int32                         m_startK;
  135.  
  136.                 int32                         m_endI;
  137.                 int32                         m_endJ;
  138.                 int32                         m_endK;
  139.  
  140.                 int32                         m_curI;
  141.                 int32                         m_curJ;
  142.                 int32                         m_curK;
  143.  
  144.                 uint32                        m_curIndex;
  145.                 float                         m_radiusSQ;
  146.  
  147.                 Vec3                          m_Pos;
  148.  
  149.                 const T*                      m_object;
  150.                 float                         m_curDistSQ;
  151.  
  152.                 const CHashSpace<T, TraitsT>& m_hashSpace;
  153.         };
  154.  
  155.         // Note: bucket count must be power of 2!
  156.         CHashSpace(const Vec3& cellSize, int buckets);
  157.         CHashSpace(const Vec3& cellSize, int buckets, const Traits& traits);
  158.         ~CHashSpace();
  159.  
  160.         /// Adds a copy of the object
  161.         void AddObject(const T& object);
  162.         /// Removes all objects indicated by operator==
  163.         void RemoveObject(const T& object);
  164.         /// Removes all objects
  165.         void Clear(bool freeMemory);
  166.         /// Frees memory for unused cells
  167.         void Compact();
  168.  
  169.         /// the functor gets called and passed every object (and the distance-squared) that is within radius of
  170.         /// pos. Returns the number of objects within range
  171.         template<typename Functor>
  172.         void ProcessObjectsWithinRadius(const Vec3& pos, float radius, Functor& functor);
  173.  
  174.         template<typename Functor>
  175.         void ProcessObjectsWithinRadius(const Vec3& pos, float radius, Functor& functor) const;
  176.  
  177.         // in contrast to the two methods above this one assumes that the passed in
  178.         // functor returns a boolean. If the functor returns true the processing is stopped.
  179.         template<typename Functor>
  180.         bool GetObjectWithinRadius(const Vec3& pos, float radius, Functor& functor) const;
  181.  
  182.         /// returns the total number of objects
  183.         inline unsigned GetNumObjects() const                                  { return m_totalNumObjects; }
  184.         // Returns number of buckets in the hash space.
  185.         inline unsigned GetBucketCount() const                                 { return m_cells.size(); }
  186.         // Returns number of objects in the specified bucket.
  187.         inline unsigned GetObjectCountInBucket(unsigned bucket) const          { return m_cells[bucket].objects.size(); }
  188.         // Returns the indexed object in the specified bucket.
  189.         inline const T& GetObjectInBucket(unsigned obj, unsigned bucket) const { return m_cells[bucket].objects[obj]; }
  190.  
  191.         /// Gets the AABB associated with an i, j, k
  192.         void     GetAABBFromIJK(int i, int j, int k, AABB& aabb) const;
  193.         /// return the individual i, j, k for 3D array lookup
  194.         void     GetIJKFromPosition(const Vec3& pos, int& i, int& j, int& k) const;
  195.         /// returns bucket index from given i,j,k
  196.         unsigned GetHashBucketIndex(int i, int j, int k) const;
  197.  
  198.         /// Returns true if successful, false otherwise
  199.         bool ReadFromFile(CCryFile& file);
  200.  
  201.         /// Populates a given vector with information about bucket usage
  202.         bool RecordBucketUsage(const T& object, std::vector<uint32>& cellCounts);
  203.  
  204.         /// Reserves space in the buckets according to the supplied vector
  205.         bool ReserveSpaceInBuckets(const std::vector<uint32>& cellCounts);
  206.  
  207.         /// Returns the memory usage in bytes
  208.         size_t          MemStats() const;
  209.  
  210.         inline unsigned GetLocationMask(int i, int j, int k) const
  211.         {
  212.                 const unsigned mi = (1 << 12) - 1;
  213.                 const unsigned mj = (1 << 12) - 1;
  214.                 const unsigned mk = (1 << 8) - 1;
  215.                 unsigned x = (unsigned)(i & mi);
  216.                 unsigned y = (unsigned)(j & mj);
  217.                 unsigned z = (unsigned)(k & mk);
  218.                 return x | (y << 12) | (z << 24);
  219.         }
  220.  
  221. private:
  222.         const Vec3& GetPos(const T& item) const;
  223.  
  224.         typedef std::vector<T> Objects;
  225.         struct Cell
  226.         {
  227.                 std::vector<unsigned> masks;
  228.                 Objects               objects;
  229.         };
  230.         typedef std::vector<Cell> Cells;
  231.  
  232.         /// returns index into m_cells
  233.         unsigned GetCellIndexFromPosition(const Vec3& pos) const;
  234.  
  235.         Cells    m_cells;
  236.         Vec3     m_cellSize;
  237.         Vec3     m_cellScale;
  238.         int      m_buckets;
  239.  
  240.         unsigned m_totalNumObjects;
  241. };
  242.  
  243. //====================================================================
  244. // Inline implementation
  245. //====================================================================
  246.  
  247. //====================================================================
  248. // MemStats
  249. //====================================================================
  250. template<typename T, typename TraitsT>
  251. size_t CHashSpace<T, TraitsT >::MemStats() const
  252. {
  253.         size_t result = 0;
  254.         for (unsigned i = 0; i < m_cells.size(); ++i)
  255.         {
  256.                 result += sizeof(Cell) + m_cells[i].objects.capacity() * sizeof(T) + m_cells[i].masks.capacity() * sizeof(unsigned);
  257.         }
  258.         result += sizeof(*this);
  259.         return result;
  260. }
  261.  
  262. //====================================================================
  263. // CHashSpace
  264. //====================================================================
  265. template<typename T, typename TraitsT>
  266. inline CHashSpace<T, TraitsT>::CHashSpace(const Vec3& cellSize, int buckets, const Traits& traits) :
  267.         Traits(traits),
  268.         m_cellSize(cellSize),
  269.         m_cellScale(1.0f / cellSize.x, 1.0f / cellSize.y, 1.0f / cellSize.z),
  270.         m_buckets(buckets),
  271.         m_totalNumObjects(0)
  272. {
  273.         MEMSTAT_CONTEXT(EMemStatContextTypes::MSC_Navigation, 0, "HashSpace");
  274.         m_cells.resize(m_buckets);
  275. }
  276.  
  277. template<typename T, typename TraitsT>
  278. inline CHashSpace<T, TraitsT>::CHashSpace(const Vec3& cellSize, int buckets) :
  279.         m_cellSize(cellSize),
  280.         m_cellScale(1.0f / cellSize.x, 1.0f / cellSize.y, 1.0f / cellSize.z),
  281.         m_buckets(buckets),
  282.         m_totalNumObjects(0)
  283. {
  284.         MEMSTAT_CONTEXT(EMemStatContextTypes::MSC_Navigation, 0, "HashSpace");
  285.         m_cells.resize(m_buckets);
  286. }
  287.  
  288. //====================================================================
  289. // ~CHashSpace
  290. //====================================================================
  291. template<typename T, typename TraitsT>
  292. inline CHashSpace<T, TraitsT>::~CHashSpace()
  293. {
  294. }
  295.  
  296. //====================================================================
  297. // Clear
  298. //====================================================================
  299. template<typename T, typename TraitsT>
  300. inline void CHashSpace<T, TraitsT >::Clear(bool clearMemory)
  301. {
  302.         for (unsigned i = 0; i < m_cells.size(); ++i)
  303.         {
  304.                 if (clearMemory)
  305.                 {
  306.                         ClearVectorMemory(m_cells[i].objects);
  307.                         ClearVectorMemory(m_cells[i].masks);
  308.                 }
  309.                 else
  310.                 {
  311.                         m_cells[i].objects.resize(0);
  312.                         m_cells[i].masks.resize(0);
  313.                 }
  314.         }
  315.         m_totalNumObjects = 0;
  316. }
  317.  
  318. //====================================================================
  319. // Compact
  320. //====================================================================
  321. template<typename T, typename TraitsT>
  322. inline void CHashSpace<T, TraitsT >::Compact()
  323. {
  324.         for (unsigned i = 0; i < m_cells.size(); ++i)
  325.         {
  326.                 if (m_cells[i].objects.empty())
  327.                         ClearVectorMemory(m_cells[i].objects);
  328.                 if (m_cells[i].masks.empty())
  329.                         ClearVectorMemory(m_cells[i].masks);
  330.         }
  331. }
  332.  
  333. //====================================================================
  334. // GetIJKFromPosition
  335. //====================================================================
  336. template<typename T, typename TraitsT>
  337. inline void CHashSpace<T, TraitsT >::GetIJKFromPosition(const Vec3& pos, int& i, int& j, int& k) const
  338. {
  339.         i = (int)floorf(pos.x * m_cellScale.x);
  340.         j = (int)floorf(pos.y * m_cellScale.y);
  341.         k = (int)floorf(pos.z * m_cellScale.z);
  342. }
  343.  
  344. //====================================================================
  345. // GetHashBucketIndex
  346. //====================================================================
  347. template<typename T, typename TraitsT>
  348. inline unsigned CHashSpace<T, TraitsT >::GetHashBucketIndex(int i, int j, int k) const
  349. {
  350.         const int h1 = 0x8da6b343;
  351.         const int h2 = 0xd8163841;
  352.         const int h3 = 0xcb1ab31f;
  353.         int n = h1 * i + h2 * j + h3 * k;
  354.         return (unsigned)(n & (m_buckets - 1));
  355.  
  356.         /*      const int h1 = 73856093;
  357.            const int h2 = 19349663;
  358.            const int h3 = 83492791;
  359.            int n = (h1*i) ^ (h2*j) ^ (h3*k);
  360.            return (unsigned)(n & (m_buckets-1));*/
  361.  
  362.         /*      const int shift = 5;
  363.            const int mask = (1 << shift)-1;
  364.            int n = (i & mask) | ((j&mask) << shift) | ((k&mask) << (shift*2));
  365.            return (unsigned)(n & (m_buckets-1));*/
  366. }
  367.  
  368. //====================================================================
  369. // GetCellIndexFromPosition
  370. //====================================================================
  371. template<typename T, typename TraitsT>
  372. inline unsigned CHashSpace<T, TraitsT >::GetCellIndexFromPosition(const Vec3& pos) const
  373. {
  374.         int i, j, k;
  375.         GetIJKFromPosition(pos, i, j, k);
  376.         return GetHashBucketIndex(i, j, k);
  377. }
  378.  
  379. //====================================================================
  380. // GetAABBFromIJK
  381. //====================================================================
  382. template<typename T, typename TraitsT>
  383. inline void CHashSpace<T, TraitsT >::GetAABBFromIJK(int i, int j, int k, AABB& aabb) const
  384. {
  385.         aabb.min.Set(i * m_cellSize.x, j * m_cellSize.y, k * m_cellSize.z);
  386.         aabb.max = aabb.min + m_cellSize;
  387. }
  388.  
  389. //====================================================================
  390. // AddObject
  391. //====================================================================
  392. template<typename T, typename TraitsT>
  393. inline void CHashSpace<T, TraitsT >::AddObject(const T& object)
  394. {
  395.         int i, j, k;
  396.         GetIJKFromPosition(GetPos(object), i, j, k);
  397.         unsigned index = GetHashBucketIndex(i, j, k);
  398.         unsigned mask = GetLocationMask(i, j, k);
  399.  
  400.         m_cells[index].objects.push_back(object);
  401.         m_cells[index].masks.push_back(mask);
  402.  
  403.         ++m_totalNumObjects;
  404. }
  405.  
  406. //====================================================================
  407. // RemoveObject
  408. //====================================================================
  409. template<typename T, typename TraitsT>
  410. inline void CHashSpace<T, TraitsT >::RemoveObject(const T& object)
  411. {
  412.         unsigned index = GetCellIndexFromPosition(GetPos(object));
  413.         Cell& cell = m_cells[index];
  414.         for (unsigned i = 0, ni = cell.objects.size(); i < ni; )
  415.         {
  416.                 T& obj = cell.objects[i];
  417.                 if (obj == object)
  418.                 {
  419.                         cell.objects[i] = cell.objects.back();
  420.                         cell.objects.pop_back();
  421.                         cell.masks[i] = cell.masks.back();
  422.                         cell.masks.pop_back();
  423.                         --ni;
  424.                         --m_totalNumObjects;
  425.                 }
  426.                 else
  427.                 {
  428.                         ++i;
  429.                 }
  430.         }
  431. }
  432.  
  433. //====================================================================
  434. // ProcessObjectsWithinRadius
  435. //====================================================================
  436. template<typename T, typename TraitsT>
  437. template<typename Functor>
  438. void CHashSpace<T, TraitsT >::ProcessObjectsWithinRadius(const Vec3& pos, float radius, Functor& functor)
  439. {
  440.         T* obj = NULL;
  441.         for (typename CHashSpace<T, TraitsT>::CRadialIterator it(pos, radius, *this); obj = it; ++it)
  442.         {
  443.                 functor(*obj, it.GetCurDistSQ());
  444.         }
  445. }
  446.  
  447. //====================================================================
  448. // ProcessObjectsWithinRadius
  449. //====================================================================
  450. template<typename T, typename TraitsT>
  451. template<typename Functor>
  452. void CHashSpace<T, TraitsT >::ProcessObjectsWithinRadius(const Vec3& pos, float radius, Functor& functor) const
  453. {
  454.         T* obj = NULL;
  455.         for (typename CHashSpace<T, TraitsT>::CRadialIterator it(pos, radius, *this); obj = it; ++it)
  456.         {
  457.                 functor(*obj, it.GetCurDistSQ());
  458.         }
  459. }
  460.  
  461. //====================================================================
  462. // GetObjectWithinRadius
  463. //====================================================================
  464. template<typename T, typename TraitsT>
  465. template<typename Functor>
  466. bool CHashSpace<T, TraitsT >::GetObjectWithinRadius(const Vec3& pos, float radius, Functor& functor) const
  467. {
  468.         bool ret = false;
  469.  
  470.         const T* obj = NULL;
  471.         for (typename CHashSpace<T, TraitsT>::CRadialIterator it(pos, radius, *this); obj = it; ++it)
  472.         {
  473.                 if (functor(*obj, it.GetCurDistSQ()))
  474.                 {
  475.                         ret = true;
  476.                         break;
  477.                 }
  478.         }
  479.  
  480.         return ret;
  481. }
  482.  
  483. //====================================================================
  484. // ReadFromFile
  485. //====================================================================
  486. template<typename T, typename TraitsT>
  487. bool CHashSpace<T, TraitsT >::ReadFromFile(CCryFile& file)
  488. {
  489.         MEMSTAT_CONTEXT(EMemStatContextTypes::MSC_Navigation, 0, "HashSpace");
  490.  
  491.         Clear(false);
  492.         int version = 1;
  493.         file.Write(&version, sizeof(version));
  494.         file.Write(&m_buckets, sizeof(m_buckets));
  495.         file.ReadType(&m_cellSize);
  496.         m_cellScale.x = 1.0f / m_cellSize.x;
  497.         m_cellScale.y = 1.0f / m_cellSize.y;
  498.         m_cellScale.z = 1.0f / m_cellSize.z;
  499.         unsigned num;
  500.         file.ReadType(&num);
  501.         m_cells.resize(num);
  502.         for (unsigned i = 0; i < num; ++i)
  503.         {
  504.                 Cell& cell = m_cells[i];
  505.                 unsigned numObjects;
  506.                 file.ReadType(&numObjects);
  507.                 cell.objects.resize(numObjects);
  508.                 cell.masks.resize(numObjects);
  509.                 if (numObjects > 0)
  510.                 {
  511.                         file.ReadType(&cell.objects[0], numObjects);
  512.                         file.ReadType(&cell.masks[0], numObjects);
  513.                 }
  514.                 m_totalNumObjects += numObjects;
  515.         }
  516.         return true;
  517. }
  518.  
  519. //====================================================================
  520. // RecordBucketUsage
  521. //====================================================================
  522. template<typename T, typename TraitsT>
  523. bool CHashSpace<T, TraitsT >::RecordBucketUsage(const T& object, std::vector<uint32>& cellCounts)
  524. {
  525.         if (m_cells.size() == cellCounts.size())
  526.         {
  527.                 int i, j, k;
  528.                 GetIJKFromPosition(GetPos(object), i, j, k);
  529.                 unsigned index = GetHashBucketIndex(i, j, k);
  530.                 unsigned mask = GetLocationMask(i, j, k);
  531.  
  532.                 cellCounts[index]++;
  533.  
  534.                 return true;
  535.         }
  536.         return false;
  537. }
  538.  
  539. //====================================================================
  540. // ReserveSpaceInBuckets
  541. //====================================================================
  542. template<typename T, typename TraitsT>
  543. bool CHashSpace<T, TraitsT >::ReserveSpaceInBuckets(const std::vector<uint32>& cellCounts)
  544. {
  545.         if (m_cells.size() == cellCounts.size())
  546.         {
  547.                 typename Cells::iterator itEnd = m_cells.end();
  548.                 for (typename Cells::iterator it = m_cells.begin(); it != itEnd; ++it)
  549.                 {
  550.                         it->masks.reserve(cellCounts[it - m_cells.begin()]);
  551.                         it->objects.reserve(cellCounts[it - m_cells.begin()]);
  552.                 }
  553.  
  554.                 return true;
  555.         }
  556.         return false;
  557. }
  558.  
  559. //====================================================================
  560. // GetPos
  561. //====================================================================
  562. template<typename T, typename TraitsT>
  563. const Vec3& CHashSpace<T, TraitsT >::GetPos(const T& item) const
  564. {
  565.         return (*static_cast<const Traits*>(this))(item);
  566. }
  567.  
  568. // [markusm] i will remove this comment
  569. //#pragma optimize("", on)
  570. #endif
  571.  
downloadHashSpace.h Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top