Difference between revisions of "AROT (MREA Section)"

From Retro Modding Wiki
Jump to: navigation, search
 
(13 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
Octrees are a form of [[wikipedia:Binary Space Partitioning|BSP tree]] that subdivide an area in 3-dimensions.
 
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.
 
They are structured recursively, starting with a ''root'' node and traversing their way to individual ''leaf'' nodes.
−
A valid octant will split sub-octants across 3-tiers, one for each dimension of euclidean space.
+
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 ===
 
=== Header ===
Line 39: Line 75:
 
| long
 
| long
 
| Mesh-Bitmap Bit-Count
 
| Mesh-Bitmap Bit-Count
−
| Count of bits in each mesh-bitmap
+
| Count of bits in each mesh-bitmap (matches MREA's mesh count)
 
|-
 
|-
 
| 0x10
 
| 0x10
Line 52: Line 88:
 
| AABB
 
| AABB
 
| AABB that fully-encloses area and serves as the octree's root-shape
 
| 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)
 
|}
 
|}

Latest revision as of 23:59, 18 October 2018

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

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

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)
Retrieved from "http://www.metroid2002.com/retromodding/index.php?title=AROT_(MREA_Section)&oldid=1951"