Node

Root node division of GFZ1

Nodes are data structures which constitute a binary space partition of a map. They are generated by nodebuilders, and they make up a binary tree that sorts all the subsectors into the correct order for drawing. Each node entry has a partition line associated with it that divides the area that the node represents into a left child area and a right child area. Each child may be either another node entry (a subnode), or a subsector on the map.

The node divisions for a map can be viewed in Zone Builder by going to the "Nodes Viewer" mode and switching to the "Splits" tab.

Specification

The nodes for a map are stored in the NODES lump as a list, with the root node placed last. Each node has a 28-byte entry consisting of the following:

Bytes	Data type	Description
0–1	Signed 16-bit integer	Partition line x coordinate
2–3	Signed 16-bit integer	Partition line y coordinate
4–5	Signed 16-bit integer	Change in x to end of partition line
6–7	Signed 16-bit integer	Change in y to end of partition line
8–15	4-element array of signed 16-bit integers	Right bounding box
16–23	4-element array of signed 16-bit integers	Left bounding box
24–25	Unsigned 16-bit integer	Right child
26–27	Unsigned 16-bit integer	Left child

Each of the two bounding boxes describe a rectangle which is the area covered by each of the two child nodes respectively. A bounding box consists of four short values (top, bottom, left and right) giving the upper and lower bounds of the y coordinate and the lower and upper bounds of the x coordinate (in that order).

The type of each child field is determined by its sign bit (bit 15). If bit 15 is zero, the child field gives the node number of a subnode. If bit 15 is set, then bits 0–14 give the number of a subsector.