AROT (MREA Section)

Within MREA resources, the AROT section stores an octree which is used to accelerate rendering of areas in back-to-front order.

Left: Recursive subdivision of a cube into octants. Right: The corresponding octree.

Octrees are a form of BSP tree that subdivide an area in 3-dimensions. They are structured recursively, starting with a root node and traversing their way to individual leaf nodes. A full-branch octant will split sub-octants across 3-tiers, one for each dimension of euclidean space. Retro uses a Z-major convention with (up to) 8 child-nodes subdivided as: 2 nodes along Z, 4 nodes along Y, and 8 nodes along X. A set of three bit-flags in each node determines which dimensions are subdivided. Nodes that do not subdivide all 3 dimensions will parent less child nodes as a result.

Within each octant is an index to a bitmap relating that AABB-volume to a set of meshes within the MREA; they are sorted and frustum-culled accordingly. Actors, particle effects, and other visual entities are also sorted and frustum-culled according to which octant(s) they intersect.

Layout

Data Type Element Count Description Notes
Header 1 Octree Header
long round_up(bitmap_bit_count / 32) * bitmap_count Mesh Bitmap Array An array of word-packed bitmaps relating octant nodes to sets of MREA meshes
long node_count Node Indirection Table Since nodes use variable-length-encoding, there is an indirection table with byte-offsets (relative to first node)
Node Entry node_count Node Entry Table Tightly-packed blob of nodes

Header

Offset Size Data Type Description Notes
0x0 4 long Magic AROT
0x4 4 long Version Always 0x1
0x8 4 long Mesh-Bitmap Count Count of mesh-bitmaps
0xC 4 long Mesh-Bitmap Bit-Count Count of bits in each mesh-bitmap (matches MREA's mesh count)
0x10 4 long Node Count Number of octant nodes
0x14 24 float2x3 AABB AABB that fully-encloses area and serves as the octree's root-shape
0x2C 20 Alignment Padding Allows the following bitmaps to be data-cached with guaranteed 32-byte alignment

Node Entry

Offset Size Data Type Description Notes
0x0 2 short Bitmap Index Index of the mesh bitmap defining a set of MREA meshes for this octant node
0x2 2 short Dimensional Flags If non-zero, this half-word contains 3-bits specifying which dimensions are subdivided using the children specified (using Z-major convention)
  • 0x4 — Z subdivided
  • 0x2 — Y subdivided
  • 0x1 — X subdivided

If zero, this node-entry ends here

0x4 Varies short[] Node Child Indices Variable-length array of node-entry indices that are children of this node-entry (Z-major layout)