class `TSpatialTree`

template<typename ElementType, typename Options, u32 Dimension>

Spatial partitioning tree for 1D/2D/3D space (i.e. quadtree for 2D, octree for 3D).

Template parameters

`ElementType`	Type of elements to be stored in the tree.
`Options`	Class that controls various options of the tree. It must provide the following enums: LoosePadding: Denominator used to determine how much padding to add to each child node. The extra padding percent is determined as (1.0f / LoosePadding). Larger padding ensures elements are less likely to get stuck on a higher node due to them straddling the boundary between the nodes. MinimumElementsPerNode: Determines at which point should node's children be removed and moved back into the parent (node is collapsed). This can occur on element removal, when the element count drops below the specified number. MaximumElementsPerNode: Determines at which point should a node be split into child nodes. If an element counter moves past this number the elements will be added to child nodes, if possible. If a node is already at maximum depth, this is ignored. MaximumDepth: Maximum depth of nodes in the tree. Nodes at this depth will not be subdivided even if they element counts go past MaximumElementsPerNode. It must also provide the following methods: "static typename TSpatialTreeTraits<Dimension>::SIMDBoundsType GetBounds(const ElementType&, void)" Returns the bounds for the provided element "static void SetElementId(const TSpatialTreeElementId&, void)" Gets called when element's ID is first assigned or subsequently modified

ElementType

Type of elements to be stored in the tree.

Options

Class that controls various options of the tree. It must provide the following enums:

LoosePadding: Denominator used to determine how much padding to add to each child node. The extra padding percent is determined as (1.0f / LoosePadding). Larger padding ensures elements are less likely to get stuck on a higher node due to them straddling the boundary between the nodes.
MinimumElementsPerNode: Determines at which point should node's children be removed and moved back into the parent (node is collapsed). This can occur on element removal, when the element count drops below the specified number.
MaximumElementsPerNode: Determines at which point should a node be split into child nodes. If an element counter moves past this number the elements will be added to child nodes, if possible. If a node is already at maximum depth, this is ignored.
MaximumDepth: Maximum depth of nodes in the tree. Nodes at this depth will not be subdivided even if they element counts go past MaximumElementsPerNode.

It must also provide the following methods:

"static typename TSpatialTreeTraits<Dimension>::SIMDBoundsType GetBounds(const ElementType&, void*)"
- Returns the bounds for the provided element
"static void SetElementId(const TSpatialTreeElementId&, void*)"
- Gets called when element's ID is first assigned or subsequently modified

Public

Constructors

TSpatialTree

TSpatialTree(const CenterType &center, float extent, void *context = nullptr)

Constructs a spatial tree with the specified bounds.

center: Origin of the root node.
extent: Extent (half-size) of the root node in all directions;
context: Optional user context that will be passed along to GetBounds() and SetElementId() methods on the provided Options class.

Methods

~TSpatialTree

~TSpatialTree()

AddElement

void AddElement(const ElementType &element)

Adds a new element to the tree.

RemoveElement

void RemoveElement(const SpatialTreeElementId &elementId)

Removes an existing element from the tree.

Private

Methods

AddElementToNode

void AddElementToNode(const ElementType &element, Node *node, const NodeBounds &nodeBounds)

Adds a new element to the specified node.

If the provided node is not a leaf node, traverses the hierarchy until it finds the correct node. Potentially also subdivides the leaf node if subdivision conditions have been reached.

AddElementToLeafNode

void AddElementToLeafNode(Node *node, const ElementType &element, const SIMDBoundsType &elementBounds)

Adds a new element to the node's element list.

This method does no additional checks so caller must ensure the node is a leaf node and does not need to be subdivided.

RemoveElementFromLeafNode

void RemoveElementFromLeafNode(Node *node, u32 elementIndexInNode)

Removes the specified element from the node's element list.

FreeElementData

void FreeElementData(NodeElementData &elementData)

Frees all elements from a node.

FreeNode

void FreeNode(Node *node)

Cleans up memory used by the provided node.

Should be called instead of the node destructor.

Fields

mRoot

Node mRoot

mRootBounds

NodeBounds mRootBounds

mMinimumNodeExtent

float mMinimumNodeExtent

mContext

void * mContext

mNodeAllocator

PoolAlloc<sizeof(Node)> mNodeAllocator

mElementBlockAllocator

PoolAlloc<sizeof(NodeElementSuballocationBlock)> mElementBlockAllocator

mElementBoundsBlockAllocator

PoolAlloc<sizeof(NodeElementBoundsSuballocationBlock), 512, 16> mElementBoundsBlockAllocator