Resources/K-D Tree - Revision history

Angryzor: /* Node list */

2025-01-19T16:36:31Z

Node list

← Older revision		Revision as of 16:36, 19 January 2025
Line 46:		Line 46:

	== Node list ==		== Node list ==
	[[File:K-d tree diagram.png\|thumb\|A k-d tree with depth 3.]]		[[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:		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"		{\| class="wikitable"

Angryzor: /* The node data */

2025-01-19T16:34:37Z

The node data

← Older revision		Revision as of 16:34, 19 January 2025
Line 101:		Line 101:
	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 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 instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list ~~describing this leaf node~~. <code>deadZoneEndCoord</code> is 0.		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>.		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>.

Angryzor: /* Top level data structure */

2025-01-19T16:33:22Z

Top level data structure

← Older revision		Revision as of 16:33, 19 January 2025
Line 42:		Line 42:

	* The node list, which describes all nodes of the k-d tree.		* 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 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		* The object list, which is a concatenated list of those slices of object indices

Angryzor: /* Top level data structure */

2025-01-19T16:31:28Z

Top level data structure

← Older revision		Revision as of 16:31, 19 January 2025
Line 39:		Line 39:

	== Top level data structure ==		== 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 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 node list, which describes all nodes of the k-d tree.

Angryzor at 16:30, 19 January 2025

2025-01-19T16:30:30Z

← Older revision		Revision as of 16:30, 19 January 2025
Line 1:		Line 1:
	{{Infobox Resource		{{Infobox Resource
	\| type = [[Resources#~~Set Objects~~\|~~Set Objects~~]]		\| type = [[Resources#Acceleration Structures\|Acceleration Structures]]
	\| status = Done		\| status = Done
	\| name=K-D Tree		\| name=K-D Tree

Angryzor at 16:27, 19 January 2025

2025-01-19T16:27:44Z

← Older revision		Revision as of 16:27, 19 January 2025
Line 1:		Line 1:
			{{Infobox Resource
			\| type = [[Resources#Set Objects\|Set Objects]]
			\| 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.		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.

Angryzor: /* The node data */

2025-01-19T16:21:56Z

The node data

← Older revision		Revision as of 16:21, 19 January 2025
Line 98:		Line 98:
	For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <code>deadZoneEndCoord</code> is 0.		For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <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 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 <code>deadZoneStartCoordOrLeafIndexAndNodeType</code> and 0 for <code>deadZoneEndCoord</code>.		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>.

Angryzor: /* Node list */

2025-01-19T16:19:37Z

Node list

← Older revision		Revision as of 16:19, 19 January 2025
Line 98:		Line 98:
	For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <code>deadZoneEndCoord</code> is 0.		For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <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 deadZoneStartCoordOrLeafIndexAndNodeType and deadZoneEndCoord. This is also the only place where 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>.		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 <code>deadZoneStartCoordOrLeafIndexAndNodeType</code> and 0 for <code>deadZoneEndCoord</code>.

Angryzor: /* The node data */

2025-01-19T16:19:09Z

The node data

← Older revision		Revision as of 16:19, 19 January 2025
Line 98:		Line 98:
	For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <code>deadZoneEndCoord</code> is 0.		For leaf nodes, the upper 30 bits instead contains the index of the <code>ResKdTreeLeafNodeData</code> structure in the leaves list describing this leaf node. <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 deadZoneStartCoordOrLeafIndexAndNodeType and deadZoneEndCoord. This is also the only place where K-D Tree 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>.		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 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>.

Angryzor: /* Node list */

2025-01-19T16:17:49Z

Node list

← Older revision		Revision as of 16:17, 19 January 2025
Line 81:		Line 81:
	\|...		\|...
	\|}		\|}
	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 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 ===		=== The node data ===