Editing Resources/K-D Tree

{{Infobox Resource
| type = [[Resources#Acceleration Structures|Acceleration Structures]]
| status = Done
| name=K-D Tree
}}
K-D Tree is a resource encoding a [[wikipedia:K-d_tree|k-d tree]] acceleration structure. It is used in various locations as a runtime resource in the engine, and also embedded in the [[Resources/Path|Path]] resource. An extremely similar structure is also found in the [[Resources/SvCol|SvCol]] and [[Resources/FxCol|FxCol]] resources. Presumably ResKdTree was built as a reusable generalization of these structures, as at least HE2 does not use the one embedded in SvCol at all, and only minimally uses the one embedded in FxCol, instead building a ResKdTree at runtime.

Since K-D tree is meant to be a reusable k-d tree encoding, it does not directly refer to any objects in the k-d tree's leaves, instead only referring to them by 32 bit indices. It is meant to be used in conjunction with some other datastructure that maps these indices to actual objects. In runtime-generated K-D trees this is done through the [[HE2/BvWorld|BvWorld]] class.

ResKdTree has never been seen separately in its own resource file, so it does not have a designated container. When embedded it's usually found in a BinaryFile container.

== Structure ==
<syntaxhighlight lang="c++">enum class ResKdTreeNodeType {
	SPLIT_X,
	SPLIT_Y,
	SPLIT_Z,
	LEAF,
};

struct ResKdTreeNodeData {
	unsigned int deadZoneStartCoordOrLeafIndexAndNodeType;
	float deadZoneEndCoord;
};

struct ResKdTreeLeafNodeData {
	int objectCount;
	int objectsOffset;
};

struct ResKdTreeData {
	int depth;
	int nodeCount;
	ResKdTreeNodeData* nodes;
	int leafCount;
	ResKdTreeLeafNodeData* leaves;
	int objectCount;
	unsigned int* objects;
};</syntaxhighlight>

== Top level data structure ==
The top level data structure holds the tree's maximum depth and 3 arrays specified as C style count + array pointer tuples:

* The node list, which describes all nodes of the k-d tree.
* The leaf list, which for each leaf describes a slice in the object list that contains the object ids belonging to this leaf.
* The object list, which is a concatenated list of those slices of object indices

== 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>.