BVB Source Codes

CRYENGINE Show AIQuadTree.h Source code

Return Download CRYENGINE: download AIQuadTree.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef AIQUADTREE_H
  4. #define AIQUADTREE_H
  5.  
  6. #if _MSC_VER > 1000
  7.         #pragma once
  8. #endif
  9.  
  10. #include <vector>
  11.  
  12. // The element stored in CAIQuadTree must provide the following interface:
  13. //
  14. // The z component of the AABB should be ignored:
  15. // bool DoesIntersectAABB(const AABB& aabb);
  16. //
  17. // const AABB &GetAABB();
  18. //
  19. // There should be a counter that CAIQuadTree can use internally - shouldn't
  20. // be used for anything else:
  21. // mutable int m_counter
  22. //
  23. // Returns some debug info about this element
  24. // const char *GetDebugName() const
  25.  
  26. template<typename SAIQuadTreeElement>
  27. class CAIQuadTree
  28. {
  29. public:
  30.         CAIQuadTree();
  31.         ~CAIQuadTree();
  32.  
  33.         /// Adds a element to the list of elements, but doesn't add it to the QuadTree
  34.         void AddElement(const SAIQuadTreeElement& element);
  35.  
  36.         /// Clears elements and cells
  37.         /// if the freeMemory is set to true, the element index array will be freed,
  38.         /// otherwise it will be reset preserving the allocated memory.
  39.         void Clear(bool freeMemory = true);
  40.  
  41.         /// Builds the QuadTree from scratch (not incrementally) - deleting any previous
  42.         /// tree.
  43.         /// Building the QuadTree will involve placing all elements into the root cell.
  44.         /// Then this cell gets pushed onto a stack of cells to examine. This stack
  45.         /// will get parsed and every cell containing more than maxElementsPerCell
  46.         /// will get split into 8 children, and all the original elements in that cell
  47.         /// will get partitioned between the children. A element can end up in multiple
  48.         /// cells (possibly a lot!) if it straddles a boundary. Therefore when intersection
  49.         /// tests are done SAIQuadTreeElement::m_counter can be set/tested using a counter to avoid
  50.         /// properly testing the triangle multiple times (the counter _might_ wrap around,
  51.         /// so when it wraps ALL the element flags should be cleared! Could do this
  52.         /// incrementally...).
  53.         void BuildQuadTree(int maxElementsPerCell, float minCellSize);
  54.  
  55.         /// Returns elements that claim to intersect the point (ignoring z), and the number.
  56.         unsigned GetElements(std::vector<const SAIQuadTreeElement*>& elements, const Vec3& point) const;
  57.  
  58.         /// Returns elements that claim to intersect the aabb (ignoring z), and the number.
  59.         unsigned GetElements(std::vector<const SAIQuadTreeElement*>& elements, const AABB& aabb) const;
  60.  
  61.         /// Dumps our contents
  62.         void Dump(const char* debugName) const;
  63.  
  64. private:
  65.         /// Internally we don't store pointers but store indices into a single contiguous
  66.         /// array of cells and triangles (so that the vectors can get resized).
  67.         ///
  68.         /// Each cell will either contain children OR contain triangles.
  69.         struct CQuadTreeCell
  70.         {
  71.                 /// constructor clears everything
  72.                 CQuadTreeCell();
  73.                 /// constructor clears everything
  74.                 CQuadTreeCell(const AABB& aabb);
  75.                 /// Sets all child indices to -1 and clears the triangle indices.
  76.                 void Clear();
  77.  
  78.                 /// Indicates if we contain triangles (if not then we should/might have children)
  79.                 bool IsLeaf() const { return m_childCellIndices[0] == -1; }
  80.  
  81.                 /// indices into the children - P means "plus" and M means "minus" and the
  82.                 /// letters are xy. So PM means +ve x, -ve y
  83.                 enum EChild
  84.                 {
  85.                         PP,
  86.                         PM,
  87.                         MP,
  88.                         MM,
  89.                         NUM_CHILDREN
  90.                 };
  91.  
  92.                 /// indices of the children (if not leaf). Will be -1 if there is no child
  93.                 int m_childCellIndices[NUM_CHILDREN];
  94.  
  95.                 /// indices of the elements (if leaf)
  96.                 std::vector<int> m_elementIndices;
  97.  
  98.                 /// Bounding box for the space we own
  99.                 AABB m_aabb;
  100.         };
  101.  
  102.         /// Functor that can be passed to std::sort so that it sorts equal sized cells along a specified
  103.         /// direction such that cells near the beginning of a line with dirPtr come at the end of the
  104.         /// sorted container. This means they get processed first when that container is used as a stack.
  105.         struct CCellSorter
  106.         {
  107.                 CCellSorter(const Vec3* dirPtr, const std::vector<CQuadTreeCell>* cellsPtr) : m_dirPtr(dirPtr), m_cellsPtr(cellsPtr) {}
  108.                 bool operator()(int cell1Index, int cell2Index) const
  109.                 {
  110.                         Vec3 delta = (*m_cellsPtr)[cell2Index].m_aabb.min - (*m_cellsPtr)[cell1Index].m_aabb.min;
  111.                         return (delta * *m_dirPtr) < 0.0f;
  112.                 }
  113.                 const Vec3*                       m_dirPtr;
  114.                 const std::vector<CQuadTreeCell>* m_cellsPtr;
  115.         };
  116.  
  117.         /// Create a bounding box appropriate for a child, based on a parents AABB
  118.         AABB CreateAABB(const AABB& aabb, typename CQuadTreeCell::EChild child) const;
  119.  
  120.         /// Returns true if the triangle intersects or is contained by a cell
  121.         bool DoesElementIntersectCell(const SAIQuadTreeElement& element, const CQuadTreeCell& cell) const;
  122.  
  123.         /// Increment our test counter, wrapping around if necessary and zapping the
  124.         /// triangle counters.
  125.         /// Const because we only modify mutable members.
  126.         void IncrementTestCounter() const;
  127.  
  128.         /// Dumps the cell and all its children, indented
  129.         void DumpCell(const CQuadTreeCell& cell, int indentLevel) const;
  130.  
  131.         /// All our cells. The only thing guaranteed about this is that m_cell[0] (if
  132.         /// it exists) is the root cell.
  133.         std::vector<CQuadTreeCell>      m_cells;
  134.         /// All our elements.
  135.         std::vector<SAIQuadTreeElement> m_elements;
  136.  
  137.         AABB                            m_boundingBox;
  138.  
  139.         /// During intersection testing we keep a stack of cells to test (rather than recursing) -
  140.         /// to avoid excessive memory allocation we don't free the memory between calls unless
  141.         /// the user calls FreeTemporaryMemory();
  142.         mutable std::vector<int> m_cellsToTest;
  143.  
  144.         /// Counter used to prevent multiple tests when triangles are contained in more than
  145.         /// one cell
  146.         mutable unsigned m_testCounter;
  147. };
  148.  
  149. #include "AIQuadTree.inl"
  150.  
  151. #endif
  152.  
downloadAIQuadTree.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