imported>Jackoalan at 05:59, 19 October 2018

2018-10-19T05:59:56Z

New page

[[File:Octree2.svg|thumb|right|400px|Left: Recursive subdivision of a cube into [[wikipedia:octant (solid geometry)|octant]]s. Right: The corresponding octree.]]

Within [[MREA (File Format)|MREA]] resources, the '''AROT section''' stores an [[wikipedia:Octree|octree]] which
is used to accelerate rendering of areas in back-to-front order.

Octrees are a form of [[wikipedia:Binary Space Partitioning|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 [[wikipedia:Bit array|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 ===

{| class="wikitable"
! Data Type
! Element Count
! Description
! Notes
|-
| [[#Header|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 Entry]]
| node_count
| Node Entry Table
| Tightly-packed blob of nodes
|}

=== Header ===

{| class="wikitable"
! Offset
! Size
! Data Type
! Description
! Notes
|-
| 0x0
| 4
| long
| Magic
| <code>AROT</code>
|-
| 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 ===

{| class="wikitable"
! 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)
<ul>
<li>0x4 — Z subdivided</li>
<li>0x2 — Y subdivided</li>
<li>0x1 — X subdivided</li>
</ul>
'''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)
|}

AROT (MREA Section) - Revision history

imported>Jackoalan at 05:59, 19 October 2018