Resources/K-D Tree

K-D Tree

Resource Type	Acceleration Structures
Reverse Engineering Status	Done

K-D Tree is a resource encoding a k-d tree acceleration structure. It is used in various locations as a runtime resource in the engine, and also embedded in the Path resource. An extremely similar structure is also found in the SvCol and 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 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

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;
};

Top level data structure

The top level data structure holds the tree's maximum depth, and then 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 slices in the object list that belong to this leaf.
• The object list, which is a concatenated list of those slices of object indices

Node list

A k-d tree with depth 3.

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 ResKdTreeNodeData 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:

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 O(1) with the formula 2 ^ depth + index in layer.

The node data

As mentioned before, every node consists of 2 32 bit values:

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

The first property of this structure, deadZoneStartCoordOrLeafIndexAndNodeType, 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: SPLIT_X, SPLIT_Y, SPLIT_Z and LEAF:

• SPLIT_X: This node splits space along the X axis.
• SPLIT_Y: This node splits space along the Y axis.
• SPLIT_Z: This node splits space along the Z axis.
• LEAF: This node is a leaf node.

For the splitting node types, the upper 30 bits of deadZoneStartCoordOrLeafIndexAndNodeType 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. deadZoneEndCoord 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 instead contains the index of the ResKdTreeLeafNodeData structure in the leaves list describing this leaf node. deadZoneEndCoord 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 deadZoneStartCoordOrLeafIndexAndNodeType and deadZoneEndCoord. 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 deadZoneStartCoordOrLeafIndexAndNodeType and 0 for deadZoneEndCoord.