Editing Resources/K-D Tree (section)

== Node list ==
[[File:K-d tree diagram.png|thumb|A k-d tree with depth 4.]]
The node list is the main part of K-D tree, and the most complex to understand, as it's using an encoding that balances space efficiency and runtime efficiency. Essentially it's a array of tuples of 2 32-bit values, named <code>ResKdTreeNodeData</code> in the code above. Each tuple describes one node in the tree. Given the tree shown on the right, the nodes are laid out as follows:
{| class="wikitable"
|+
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
!13
!14
!15
!...
|-
|/
|a
|b
|c
|d
|e
|f
|g
|h
|i
|j
|k
|l
|m
|n
|o
|...
|}
The first item is intentionally unused. The advantage of this layout is that every node of the k-d tree can be efficiently indexed in <code>O(1)</code> with the formula <code>2 ^ depth + index in layer</code>.

=== The node data ===
As mentioned before, every node consists of 2 32 bit values:<syntaxhighlight lang="c++">struct ResKdTreeNodeData {
	unsigned int deadZoneStartCoordOrLeafIndexAndNodeType;
	float deadZoneEndCoord;
};</syntaxhighlight>The first property of this structure, <code>deadZoneStartCoordOrLeafIndexAndNodeType</code>, is a bitfield, of which the lower 2 bits define the "type" of the node, and the rest of the bits define another value depending on the node's type. There are 4 possible node types: <code>SPLIT_X</code>, <code>SPLIT_Y</code>, <code>SPLIT_Z</code> and <code>LEAF</code>:

* <code>SPLIT_X</code>: This node splits space along the X axis.
* <code>SPLIT_Y</code>: This node splits space along the Y axis.
* <code>SPLIT_Z</code>: This node splits space along the Z axis.
* <code>LEAF</code>: This node is a leaf node.

For the splitting node types, the upper 30 bits of <code>deadZoneStartCoordOrLeafIndexAndNodeType</code> are a float value, describing the position along the splitting axis where a part of space starts that does not contain any objects (the "dead zone"), in other words the end of the left child's area of space. <code>deadZoneEndCoord</code> describes the position along the splitting axis where the dead zone ends, i.e. where the area of space belonging to the right child begins.

For leaf nodes, the upper 30 bits is instead and unsigned integer that contains the index of the <code>ResKdTreeLeafNodeData</code> structure describing this leaf node in the leaves list. <code>deadZoneEndCoord</code> is 0.

Due to the nature of the node list encoding, some slots in the node list will correspond to non-existing nodes (index 0, and all indices that would belong to children of leaf nodes). These slots contain the value 0 for both <code>deadZoneStartCoordOrLeafIndexAndNodeType</code> and <code>deadZoneEndCoord</code>. This is also the only place where the K-D Tree node list differs from the k-d tree encodings in FxCol and SvCol: in FxCol and SvCol invalid nodes instead have the value -1 for <code>deadZoneStartCoordOrLeafIndexAndNodeType</code> and 0 for <code>deadZoneEndCoord</code>.