A splitting node in a kd-tree of points.
There is no dedicated kd-tree object in this implementation. The kd-tree branching structure is described by an array of PointSplit nodes, and it's leaf nodes and contents by an array of PointLeaf nodes. This allows the kd-tree to be easily extended with additional information, such as bounds information, without creating a single structure to rule all uses.
All kd-tree's start with one of these as their root node, so all tree have at least 1 split node. There is one special case where the tree only has a single leaf node, and therefore no actual splits. In this case the root node is a 'no split' node, which is indicated by a negative value in m_PointIdx.
The m_IdxGreaterIncl and m_IdxLess indices link to the two children of this split, where the type of object they link to is encoded in the sign of the index:
If > 0 it's a split index, else it's a negated leaf idx.
0 is always a leaf idx. The 0'th split is always the root split and always exists and so is never referenced.
The upper or greater child is described as 'inclusive' because it includes the splitting point.
| Name | Description |
|---|---|
| Geo::s32 m_AxisIdx | Which axis this splits on first. |
| Geo::s32 m_IdxGreaterIncl | The index of the upper/greater item. |
| Geo::s32 m_IdxLess | The index of the lower/less than item. |
| Geo::s32 m_PointIdx | The index of the point on which we are splitting, or a negative value for 'no split'. |