BVB Source Codes

CRYENGINE Show WorldOctree.h Source code

Return Download CRYENGINE: download WorldOctree.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:   WorldOctree.h
  7.    Version:     v1.00
  8.    Description:
  9.  
  10.    -------------------------------------------------------------------------
  11.    History:
  12.    - 23:2:2005   Created by Danny Chapman
  13.    - 2 Mar 2009                  : Evgeny Adamenkov: Removed IRenderer
  14.  
  15.  *********************************************************************/
  16. #ifndef WORLDOCTREE_H
  17. #define WORLDOCTREE_H
  18.  
  19. #if _MSC_VER > 1000
  20.         #pragma once
  21. #endif
  22.  
  23. /// Stores world collision data in an octree structure for quick ray testing
  24. class CWorldOctree
  25. {
  26. public:
  27.         CWorldOctree();
  28.         ~CWorldOctree();
  29.  
  30.         struct CTriangle
  31.         {
  32.                 CTriangle() {};
  33.                 CTriangle(const Vec3& v0, const Vec3& v1, const Vec3& v2) :
  34.                         m_v0(v0), m_v1(v1), m_v2(v2), m_counter(-1) {}
  35.                 Vec3 m_v0, m_v1, m_v2;
  36.                 /// marker - this will get set to the test number after this triangle has been
  37.                 /// checked in an intersection test so that it doesn't need to be checked more
  38.                 /// than once.
  39.                 mutable int m_counter;
  40.         };
  41.  
  42.         /// Adds a triangle to the list of triangles, but doesn't add it to the octree
  43.         void AddTriangle(const CTriangle& triangle);
  44.  
  45.         /// Clears triangles and cells
  46.         /// if the freeMemory is set to true, the triangle index array will be freed,
  47.         /// otherwise it will be reset preserving the allocated memory.
  48.         void Clear(bool freeMemory = true);
  49.  
  50.         /// Builds the octree from scratch (not incrementally) - deleting any previous
  51.         /// tree.
  52.         /// Building the octree will involve placing all triangles into the root cell.
  53.         /// Then this cell gets pushed onto a stack of cells to examine. This stack
  54.         /// will get parsed and every cell containing more than maxTrianglesPerCell
  55.         /// will get split into 8 children, and all the original triangles in that cell
  56.         /// will get partitioned between the children. A triangle can end up in multiple
  57.         /// cells (possibly a lot!) if it straddles a boundary. Therefore when intersection
  58.         /// tests are done CTriangle::m_counter can be set/tested using a counter to avoid
  59.         /// properly testing the triangle multiple times (the counter _might_ wrap around,
  60.         /// so when it wraps ALL the triangle flags should be cleared! Could do this
  61.         /// incrementally...).
  62.         void BuildOctree(int maxTrianglesPerCell, float minCellSize, const AABB& bbox);
  63.  
  64.         /// Simple overlap test of capsule with the triangles
  65.         bool OverlapCapsule(const Lineseg& lineseg, float radius);
  66.  
  67.         struct CIntersectionData
  68.         {
  69.                 float t;
  70.                 Vec3  pt, normal;
  71.         };
  72.         /// Intersect the line segment with the triangles - returns true if there is an intersection
  73.         /// and if so if data is non-zero it returns the data associated with the first
  74.         /// intersection. If data is zero it returns at the first intersection found (so
  75.         /// can be faster).
  76.         /// if twoSided = true then the test is two-sided (i.e. return hits with back-facing
  77.         /// triangles, in which case the normal is still the triangle normal)
  78.         /// startingCell indicates the cell to start the search from - should have been returned
  79.         /// from FindCellContainingAABB.
  80.         bool IntersectLineseg(CIntersectionData* data, Lineseg lineseg, bool twoSided, int startingCell = 0) const;
  81.  
  82.         /// As the other IntersectLineseg but this uses a list of cells that has previously been
  83.         /// obtained using GetCellsOverlappingAABB
  84.         bool IntersectLinesegFromCache(CIntersectionData* data, Lineseg lineseg, bool twoSided) const;
  85.  
  86.         /// As the other IntersectLineseg but this uses a list of cells that has previously been
  87.         /// obtained using GetCellsOverlappingAABB2
  88.         bool IntersectLinesegFromCache2(CIntersectionData* data, Lineseg lineseg, bool twoSided) const;
  89.  
  90.         /// Cache a list of all leaf cells overlapping aabb - these can be used by
  91.         /// IntersectLinesegFromCache for quick subsequent checks.
  92.         void CacheCellsOverlappingAABB(const AABB& aabb);
  93.  
  94.         /// Cache a list of all leaf cells overlapping sphere - these can be used by
  95.         /// IntersectLinesegFromCache for quick subsequent checks.
  96.         void CacheCellsOverlappingSphere(const Vec3& pos, float radius);
  97.  
  98.         /// Cache a list of all cells that are either (1) leaf cells that intersect or are contained
  99.         /// by the boundary of the aabb or (2) non-leaf cells that are completely within the aabb.
  100.         /// these can be used by IntersectLinesegFromCache2 for quick subsequent checks.
  101.         void CacheCellsOverlappingAABB2(const AABB& aabb);
  102.  
  103.         /// Cache a list of all cells that are either (1) leaf cells that intersect or are contained
  104.         /// by the boundary of the sphere or (2) non-leaf cells that are completely within the sphere.
  105.         /// these can be used by IntersectLinesegFromCache2 for quick subsequent checks.
  106.         void CacheCellsOverlappingSphere2(const Vec3& pos, float radius);
  107.  
  108.         /// Returns the smallest cell containg the aabb, for subsequent passing into IntersectLineseg
  109.         /// Only makes sense if the aabb is pretty small compared to the domain so that subsequent
  110.         /// tests can avoid a lot of cell tests.
  111.         int FindCellContainingAABB(const AABB& aabb) const;
  112.  
  113.         /// Intersection tests allocate memory but keep it from one test to the next - call
  114.         /// this to free this temporary memory.
  115.         void FreeTemporaryMemory() { ClearVectorMemory(m_cellsToTest); ClearVectorMemory(m_cachedCells); ClearVectorMemory(m_cachedCells2); }
  116.  
  117.         /// Dump some statistics and validate
  118.         void DumpStats() const;
  119.  
  120.         /// draw the cells/triangles etc
  121.         void DebugDraw() const;
  122.  
  123.         /// Get memory usage in bytes
  124.         size_t MemStats();
  125.  
  126. private:
  127.         /// Internally we don't store pointers but store indices into a single contiguous
  128.         /// array of cells and triangles owned by CWorldOctree (so that the vectors can
  129.         /// get resized).
  130.         ///
  131.         /// Each cell will either contain children OR contain triangles.
  132.         struct COctreeCell
  133.         {
  134.                 /// constructor clears everything
  135.                 COctreeCell();
  136.                 /// constructor clears everything
  137.                 COctreeCell(const AABB& aabb);
  138.                 /// Sets all child indices to -1 and clears the triangle indices.
  139.                 void Clear();
  140.  
  141.                 /// Indicates if we contain triangles (if not then we should/might have children)
  142.                 bool IsLeaf() const { return m_childCellIndices[0] == -1; }
  143.  
  144.                 /// indices into the children - P means "plus" and M means "minus" and the
  145.                 /// letters are xyz. So PPM means +ve x, +ve y, -ve z
  146.                 enum EChild
  147.                 {
  148.                         PPP,
  149.                         PPM,
  150.                         PMP,
  151.                         PMM,
  152.                         MPP,
  153.                         MPM,
  154.                         MMP,
  155.                         MMM,
  156.                         NUM_CHILDREN
  157.                 };
  158.  
  159.                 /// indices of the children (if not leaf). Will be -1 if there is no child
  160.                 int m_childCellIndices[NUM_CHILDREN];
  161.  
  162.                 /// indices of the triangles (if leaf)
  163.                 std::vector<int> m_triangleIndices;
  164.  
  165.                 /// Bounding box for the space we own
  166.                 AABB m_aabb;
  167.         };
  168.  
  169.         /// Functor that can be passed to std::sort so that it sorts equal sized cells along a specified
  170.         /// direction such that cells near the beginning of a line with dirPtr come at the end of the
  171.         /// sorted container. This means they get processed first when that container is used as a stack.
  172.         struct CCellSorter
  173.         {
  174.                 CCellSorter(const Vec3* dirPtr, const std::vector<COctreeCell>* cellsPtr) : m_dirPtr(dirPtr), m_cellsPtr(cellsPtr) {}
  175.                 bool operator()(int cell1Index, int cell2Index) const
  176.                 {
  177.                         Vec3 delta = (*m_cellsPtr)[cell2Index].m_aabb.min - (*m_cellsPtr)[cell1Index].m_aabb.min;
  178.                         return (delta * *m_dirPtr) < 0.0f;
  179.                 }
  180.                 const Vec3*                     m_dirPtr;
  181.                 const std::vector<COctreeCell>* m_cellsPtr;
  182.         };
  183.  
  184.         /// Create a bounding box appropriate for a child, based on a parents AABB
  185.         AABB CreateAABB(const AABB& aabb, COctreeCell::EChild child) const;
  186.  
  187.         /// Returns true if the triangle intersects or is contained by a cell
  188.         bool DoesTriangleIntersectCell(const CTriangle& triangle, const COctreeCell& cell) const;
  189.  
  190.         /// Increment our test counter, wrapping around if necessary and zapping the
  191.         /// triangle counters.
  192.         /// Const because we only modify mutable members.
  193.         void IncrementTestCounter() const;
  194.  
  195.         /// All our cells. The only thing guaranteed about this is that m_cell[0] (if
  196.         /// it exists) is the root cell.
  197.         std::vector<COctreeCell> m_cells;
  198.         /// All our triangles.
  199.         std::vector<CTriangle>   m_triangles;
  200.  
  201.         AABB                     m_boundingBox;
  202.  
  203.         /// During intersection testing we keep a stack of cells to test (rather than recursing) -
  204.         /// to avoid excessive memory allocation we don't free the memory between calls unless
  205.         /// the user calls FreeTemporaryMemory();
  206.         mutable std::vector<int> m_cellsToTest;
  207.  
  208.         /// cell indices cached from CacheCellsOverlappingAABB
  209.         std::vector<int> m_cachedCells;
  210.  
  211.         /// cell indices cached from CacheCellsOverlappingAABB2
  212.         /// This is mutable because during the intersection test we use it as a stack
  213.         /// but restore it at the end.
  214.         mutable std::vector<int> m_cachedCells2;
  215.  
  216.         /// Counter used to prevent multiple tests when triangles are contained in more than
  217.         /// one cell
  218.         mutable unsigned m_testCounter;
  219. };
  220.  
  221. #endif
  222.  
downloadWorldOctree.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