Class LooseOctree, where each tree node has a loose boundary which is exactly twice big as its exact, tight boundary During tree update, a primitive is moved around from node to node If removed from a node, the primitive is moving up to find the lowest node that tightly contains it, then it is inserted again from top-down, to a lowest level possible, stopping at a node that loosely contains it Pointer variables in tree and tree node are all raw pointers, not smart pointers, for fast operations. More...
#include <imstkLooseOctree.h>
Public Member Functions | |
| LooseOctree (const Vec3d ¢er, const double width, const double minWidth, const double minWidthRatio=1.0, const std::string name="LooseOctree") | |
| Octree constructor. More... | |
| virtual | ~LooseOctree () |
| virtual void | clear () |
| Clear all primitive and geometry data, but still keep allocated nodes in memory pool to recycle. | |
| void | clearPrimitive (const OctreePrimitiveType type) |
| Completely remove all data of the given primitive type in the tree. | |
| const Vec3d | getCenter () const |
| Return center of the tree. | |
| double | getWidth () const |
| Return width of the tree. | |
| double | getMinWidth () const |
| Return width of the lowest level tree nodes. | |
| uint32_t | getMaxDepth () const |
| Get the maximum depth in this tree, which is computed based on the minWidth value. | |
| uint32_t | getNumAllocatedNodes () const |
| Get the total number of tree nodes that have been allocated in memory. | |
| uint32_t | getNumActiveNodes () const |
| Get the number of active nodes in the tree (the non-leaf nodes or leaf nodes that contain primitives) | |
| OctreeNode * | getRootNode () const |
| Get the root node. | |
| size_t | getPrimitiveCount (const OctreePrimitiveType type) const |
| Get the number of primitives of the given type. | |
| uint32_t | getMaxNumPrimitivesInNodes () const |
| Count the maximum number of primitives stored in a tree node. | |
| size_t | getNumGeometries () const |
| Get number of geometries that have been added to the octree. | |
| bool | hasGeometry (uint32_t geomIdx) const |
| Check if a geometry with the given geometry index has been added to the octree before. | |
| uint32_t | addPointSet (const std::shared_ptr< PointSet > &pointset) |
| Add a PointSet geometry into the tree (the points will not be populated to tree nodes until calling to build()) | |
| uint32_t | addTriangleMesh (const std::shared_ptr< SurfaceMesh > &surfMesh) |
| Add a triangle mesh into the tree (the triangles of the mesh will not be populated to tree nodes until calling to build()) | |
| uint32_t | addAnalyticalGeometry (const std::shared_ptr< Geometry > &geometry) |
| Add an analytical geometry (such as plane/sphere/cube etc) into the tree (it will not be populated to tree nodes until calling to build()) | |
| void | setAlwaysRebuild (const bool bAlwaysRebuild) |
| Set the alwaysRebuild flag (true: rebuilt the tree from scratch in every update, false: incrementally update from the current state) | |
| void | build () |
| Build octree from the provided geometries. | |
| void | update () |
| Update tree (the tree is rebuilt from scratch if m_bAlwaysRebuild is true, otherwise it is incrementally updated) | |
Protected Member Functions | |
| void | addGeometry (const uint32_t geomIdx) |
| Add geometry to the internal geometry list to check for duplication. | |
| void | removeGeometry (const uint32_t geomIdx) |
| Remove geometry from the internal geometry list (does nothing if the geometry does not exist, or has been removed before) | |
| void | rebuild () |
| Rebuild the tree from scratch. | |
| void | populatePointPrimitives () |
| Populate point primitive to tree nodes, from top (root node) down to leaf nodes. | |
| void | populateNonPointPrimitives (const OctreePrimitiveType type) |
| Populate non-point primitive (triangle/analytical geometry) to tree nodes, from top (root node) down to leaf nodes. More... | |
| void | incrementalUpdate () |
| Incrementally update octree from current state. | |
| void | updatePositionAndCheckValidity () |
| For each point primitive, update its position from its parent geometry and check if it is still loosely contained in the tree node If the primitive is not loosely contained in tree node, set it to invalid state and set m_pNode to the lowest ancestor node that tightly contains it. | |
| void | updateBoundingBoxAndCheckValidity (const OctreePrimitiveType type) |
| For each non-point primitive, update its bounding box from its parent geometry and check if it is still loosely contained in the tree node If the primitive is not loosely contained in tree node, set it to invalid state and set m_pNode to the lowest ancestor node that tightly contains it. | |
| void | removeInvalidPrimitivesFromNodes () |
| Remove all invalid primitives from the tree nodes previously contained them. | |
| void | reinsertInvalidPrimitives (const OctreePrimitiveType type) |
| For each invalid primitive, insert it back to the tree in a top-down manner starting from the lowest ancestor node that tightly contains it (that node was found during validity check) | |
| void | computePrimitiveBoundingBox (OctreePrimitive *const pPrimitive, const OctreePrimitiveType type) |
| Compute the AABB bounding box of a non-point primitive. | |
| OctreeNodeBlock * | requestChildrenFromPool () |
| Request a block of 8 tree nodes from memory pool (this is called only during splitting node) If the memory pool is exhausted, 64 more blocks will be allocated from the system memory. | |
| void | returnChildrenToPool (OctreeNodeBlock *const pNodeBlock) |
| Return 8 children nodes to memory pool (this is called only during destroying descendant nodes) | |
| void | allocateMoreNodeBlock (const uint32_t numBlocks) |
| Pre-allocate a given number of node blocks (each block contains 8 nodes) and add them to the memory pool. | |
| void | deallocateMemoryPool () |
| Deallocate all node block in memory pool, called only during octree destructor. | |
Protected Attributes | |
| const std::string | m_Name |
| Name of the tree. | |
| const Vec3d | m_Center |
| Center of the tree. | |
| const double | m_Width |
| Width of the tree bounding box. | |
| const double | m_MinWidthRatio |
| If there is no point primitive, minWidth will be recomputed as minWidth = min(width of all non-point primitives) * minWidthRatio. | |
| double | m_MinWidth |
| Minimum width allowed for the tree nodes. | |
| uint32_t | m_MaxDepth |
| Max depth of the tree, which is computed based on m_MinWidth. | |
| bool | m_useMaxDepth |
| If on max depth specified by user will be used, otherwise maxdepth is based of minwidth. | |
| OctreeNode *const | m_pRootNode |
| Root node, should not be reassigned throughout the existence of the tree. | |
| OctreeNodeBlock * | m_pNodeBlockPoolHead = nullptr |
| The pool of tree nodes, storing pre-allocated nodes as a linked list. | |
| uint32_t | m_NumAvaiableBlocksInPool = 0 |
| Count the number of nodes available in memory pool. | |
| uint32_t | m_NumAllocatedNodes |
| Count the total number of allocated nodes so far. | |
| ParallelUtils::SpinLock | m_PoolLock |
| Atomic lock for multi-threading modification of the memory pool. | |
| tbb::concurrent_unordered_set< OctreeNodeBlock * > | m_sActiveTreeNodeBlocks |
| Set of node blocks that are in use (node blocks that have been taken from memory pool) | |
| std::vector< OctreeNodeBlock * > | m_pNodeBigBlocks |
| std::vector< OctreePrimitive * > | m_vPrimitivePtrs [OctreePrimitiveType::NumPrimitiveTypes] |
| Store pointers of primitives created from geometry elements, such as points, triangles, analytical geometries. | |
| std::vector< OctreePrimitive * > | m_pPrimitiveBlocks [OctreePrimitiveType::NumPrimitiveTypes] |
| std::unordered_set< uint32_t > | m_sGeometryIndices |
| List of all indices of the added geometries, to check for duplication such that one geometry cannot be mistakenly added multiple times. | |
| bool | m_bAlwaysRebuild = false |
| If true, the octree is always be rebuit from scratch every time calling to update() | |
| bool | m_bCompleteBuild = false |
| This is set to true after tree has been built, otherwise false. | |
| bool | m_bDrawNonEmptyParent = true |
Friends | |
| class | OctreeNode |
| class | LooseOctreeTest |
Detailed Description
Class LooseOctree, where each tree node has a loose boundary which is exactly twice big as its exact, tight boundary During tree update, a primitive is moved around from node to node If removed from a node, the primitive is moving up to find the lowest node that tightly contains it, then it is inserted again from top-down, to a lowest level possible, stopping at a node that loosely contains it Pointer variables in tree and tree node are all raw pointers, not smart pointers, for fast operations.
Definition at line 313 of file imstkLooseOctree.h.
Constructor & Destructor Documentation
◆ LooseOctree()
|
explicit |
Octree constructor.
- Parameters
-
center The center of the tree, which also is the center of the root node width Width of the octree bounding box minWidth Minimum allowed width of the tree nodes, valid only if there are only points primitives minWidthRatio If there is primitive that is not a point, minWidth will be recomputed as minWidth = min(width of all non-point primitives) * minWidthRatio name Name of the octree
Definition at line 266 of file imstkLooseOctree.cpp.
◆ ~LooseOctree()
|
virtual |
Destructor, doing memory cleanup
Definition at line 278 of file imstkLooseOctree.cpp.
Member Function Documentation
◆ populateNonPointPrimitives()
|
protected |
Populate non-point primitive (triangle/analytical geometry) to tree nodes, from top (root node) down to leaf nodes.
- Parameters
-
type Type of primitive (must not point, but triangle/analytical geometry)
Definition at line 580 of file imstkLooseOctree.cpp.
Member Data Documentation
◆ m_bDrawNonEmptyParent
|
protected |
If true, all non-empty nodes are rendered during debug rendering (including nodes containing primitives and all other non-leaf nodes) otherwise only nodes containing primitives are rendered
Definition at line 552 of file imstkLooseOctree.h.
◆ m_pNodeBigBlocks
|
protected |
During memory allocation for tree nodes, multiple node blocks are allocated at the same time from a big memory block This variable store the first address of such big memory block, used during memory pool deallocation
Definition at line 535 of file imstkLooseOctree.h.
◆ m_pPrimitiveBlocks
|
protected |
During memory allocation for primitives, multiple primitives are allocated at the same time from a big memory block This variable store the first address of such big memory block, used during primitive deallocation
Definition at line 542 of file imstkLooseOctree.h.
The documentation for this class was generated from the following files:
- Source/DataStructures/imstkLooseOctree.h
- Source/DataStructures/imstkLooseOctree.cpp
