 |
Workspace 6.21.5
|
|
Workspace 6.21.5
|
A Linear spatial partitioning tree is a quadtree or octree compressed into a single contiguous array. More...
#include <Rendering/SceneComponents/linearspatialpartitioningtree.h>
Classes | |
| class | Cell |
| Describes an octree cell's location and physical geometry. More... | |
| class | MaxDepthExceededException |
| Thrown if the algorithm attempts to build a tree deeper than the maximum possible depth. More... | |
| class | TerminateExecutionRequestedException |
| Thrown whenever the caller wishes to terminate traversal due to user intervention. More... | |
Public Types | |
| using | CellList = std::vector< Cell > |
| using | CellListPtr = QSharedPointer< CellList > |
| using | const_pointer = const value_type * |
| using | const_reference = const value_type & |
| using | difference_type = ptrdiff_t |
| typedef quint64 | LocationDescriptor |
| The LocationDescriptor is a complete address to a cell from the root. | |
| using | pointer = value_type * |
| enum | QuadtreePlane { XY , XZ , YZ } |
| Defines the orientation of the quadtree, if the tree is layed out as a quadtree. More... | |
| using | reference = value_type & |
| using | size_type = size_t |
| enum | TreeLayout { Quadtree , Octree } |
| Defines the layout of the partitioning tree: a quadtree, where every cell splits into 4, or an octree, where each tree splits into 8. More... | |
| using | value_type = Point |
Public Member Functions | |
| LinearSpatialPartitioningTree (TreeLayout layout, Mesh::MeshNodesInterface &nodes, unsigned patchDepth, QuadtreePlane plane=XY) | |
| LinearSpatialPartitioningTree::iterator | begin () |
| LinearSpatialPartitioningTree::const_iterator | begin () const |
| LinearSpatialPartitioningTree::iterator | end () |
| LinearSpatialPartitioningTree::const_iterator | end () const |
| size_type | getDiminishingReturnsThreshold () const |
| quint8 | getMaxDepth () const |
| Mesh::MeshNodesInterface & | getNodes () |
| const Mesh::MeshNodesInterface & | getNodes () const |
| quint32 | getNumCellsPerLevel () const |
| Point & | operator[] (size_type i) |
| const Point & | operator[] (size_type i) const |
| quint8 | traverse (const std::function< Cell::VisitAction(const Cell &)> &preCellVisit, const std::function< void(const Cell &)> &postCellVisit, const Mesh::BoundingBox &cloudBounds, unsigned maxDepth) |
Static Public Member Functions | |
| static quint8 | getMaxDepth (LinearSpatialPartitioningTree::TreeLayout layout) |
Static Public Attributes | |
| static constexpr const quint64 | NumLocationBits = sizeof(LocationDescriptor) * 8 |
Each item in the array is a point, and the points are sorted by their location descriptor, which describes the location of the cell in which the point is contained.
We allow the tree to define the number of bits that it's going to use. The location descriptor is a single unsigned value where every 2 or 3 bits corresponds to a single cell identifier at a specific depth, for example, the cell location at the root level is defined in the first three bits of an octree:
000 = back lower left 001 = back lower right 010 = back upper left 011 = back upper right 100 = front lower left 101 = front lower right 110 = front upper left 111 = front upper right
or the first two bits of a quadtree:
00 = lower left 01 = lower right 10 = upper left 11 = upper right
The next three bits contain the cell location at the next depth and so on. When the octree array is properly sorted, enough information is encoded in each point's location descriptor to to allow all the points within a given cell to be looked up using a simple binary search.
| using CellListPtr = QSharedPointer<CellList> |
| using const_pointer = const value_type* |
| using const_reference = const value_type& |
| using difference_type = ptrdiff_t |
| typedef quint64 LocationDescriptor |
| using pointer = value_type* |
| using reference = value_type& |
| using size_type = size_t |
| using value_type = Point |
| enum QuadtreePlane |
| enum TreeLayout |
| LinearSpatialPartitioningTree | ( | TreeLayout | layout, |
| Mesh::MeshNodesInterface & | nodes, | ||
| unsigned | patchDepth, | ||
| QuadtreePlane | plane = XY |
||
| ) |
|
inline |
|
inline |
|
inline |
|
inline |
| LinearSpatialPartitioningTree::size_type getDiminishingReturnsThreshold | ( | ) | const |
| quint8 getMaxDepth | ( | ) | const |
|
static |
| Mesh::MeshNodesInterface & getNodes | ( | ) |
| const Mesh::MeshNodesInterface & getNodes | ( | ) | const |
| quint32 getNumCellsPerLevel | ( | ) | const |
|
inline |
|
inline |
| quint8 traverse | ( | const std::function< Cell::VisitAction(const Cell &)> & | preCellVisit, |
| const std::function< void(const Cell &)> & | postCellVisit, | ||
| const Mesh::BoundingBox & | cloudBounds, | ||
| unsigned | maxDepth | ||
| ) |
| preCellVisit | Function to invoke immediately prior to visiting a cell |
| postCellVisit | Function to invoke immediately after visiting a cell |
| cloudBounds | The bounding box of the point cloud |
| maxDepth | The maximum depth to which we should traverse |
Invoke this method to traverse the octree invoking the specified pre and post visit functions. Traversal is breadth first in order to ensure we can compute LOD data on-the-fly (i.e. only once one entire level of the tree is constructed can we proceed to the next level down).
|
staticconstexpr |