Difference between revisions of "Node"
From DoomWiki.org
| [unchecked revision] | [unchecked revision] |
(took a stab at it) |
m (fmt) |
||
| Line 12: | Line 12: | ||
| align="center" | 0 | | align="center" | 0 | ||
| align="center" | 2 | | align="center" | 2 | ||
| − | | Partition line x coordinate | + | | Partition line ''x'' coordinate |
|- | |- | ||
| align="center" | 2 | | align="center" | 2 | ||
| align="center" | 2 | | align="center" | 2 | ||
| − | | Partition line y coordinate | + | | Partition line ''y'' coordinate |
|- | |- | ||
| align="center" | 4 | | align="center" | 4 | ||
| align="center" | 2 | | align="center" | 2 | ||
| − | | Change in x to end of partition line | + | | Change in ''x'' to end of partition line |
|- | |- | ||
| align="center" | 6 | | align="center" | 6 | ||
| align="center" | 2 | | align="center" | 2 | ||
| − | | Change in y to end of partition line | + | | Change in ''y'' to end of partition line |
|- | |- | ||
| align="center" | 8 | | align="center" | 8 | ||
| Line 43: | Line 43: | ||
|} | |} | ||
| − | 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 <tt>short</tt> 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). | + | 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 <tt>short</tt> 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. | 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. | ||
Revision as of 21:43, 3 November 2005
NODES is the name of a WAD lump which is a component of a level. It is normally generated automatically from other data for the level using a node builder tool.
The nodes lump constitutes a binary space partition of the level. It is 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.
Node structure
| Doom level format |
|---|
| Offset | Size (bytes) | Description |
|---|---|---|
| 0 | 2 | Partition line x coordinate |
| 2 | 2 | Partition line y coordinate |
| 4 | 2 | Change in x to end of partition line |
| 6 | 2 | Change in y to end of partition line |
| 8 | 8 | Right bounding box |
| 16 | 8 | Left bounding box |
| 24 | 2 | Right child |
| 26 | 2 | 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.
