OBD:OTLF: Difference between revisions
Jump to navigation
Jump to search
m (typos) |
(a few notes on the theoretical limits; and the obligatory "smaller boxes" joke) |
||
| Line 23: | Line 23: | ||
|} | |} | ||
[[Image:Penny_Arcade_-_EvilCorp_Too.png|thumb|300px]] | |||
;Intersected gunk quads | ;Intersected gunk quads | ||
:An octtree leaf (OTLF) stores its size and position and the gunk quads that intersect it. The first field contains an index/count pair that is used to access the first [[OBD:IDXA|IDXA]] field that is stored in the [[OBD:AKOT|AKOT]] that owns this leaf. This [[OBD:IDXA|IDXA]] contains the gunk quad numbers that intersect the leaf. In theory there can be at most 4096 gunk quads that intersect a leaf but in practice this number is much lower (max is 462). In addition the threshold limit used to build the octree seems to be 19 gunk quads per leaf. | :An octtree leaf (OTLF) stores its size and position and the gunk quads that intersect it. The first field contains an index/count pair that is used to access the first [[OBD:IDXA|IDXA]] field that is stored in the [[OBD:AKOT|AKOT]] that owns this leaf. This [[OBD:IDXA|IDXA]] contains the gunk quad numbers that intersect the leaf. In theory there can be at most 4096 gunk quads that intersect a leaf but in practice this number is much lower (max is 462). In addition the threshold limit used to build the octree seems to be 19 gunk quads per leaf. I.e., in Oni's levels, only the smallest leaves (with size 16x16x16) have more than 19 quads; larger leaves containing 20 and more quads are subdivided into "other, smaller boxes". | ||
;Intersected BNVs | ;Intersected BNVs | ||
:An octtree leaf can intersect some BNVs (see [[OBD:AKVA|AKVA]]). The last field contains the index and count of this list in the second [[OBD:IDXA|IDXA]] field of [[OBD:AKOT|AKOT]]. | :An octtree leaf can intersect some BNVs (see [[OBD:AKVA|AKVA]]). The last field contains the index and count of this list in the second [[OBD:IDXA|IDXA]] field of [[OBD:AKOT|AKOT]]. | ||
| Line 35: | Line 35: | ||
:*Maximum coordinate is (4096.0, 4096.0, 4096.0) | :*Maximum coordinate is (4096.0, 4096.0, 4096.0) | ||
:*Minimum leaf size is 16.0 | :*Minimum leaf size is 16.0 | ||
:*Maximum leaf size is 4096.0 (this means that there will always be at least 8 | :*Maximum leaf size is 4096.0 (this means that there will always be at least 8 leaves because the size of the environment is double). | ||
;Neighbours | ;Neighbours | ||
:A leaf can have 6 neighbours (one for each face). If a face does not have a neighbour (it's on an environment border) then the coresponding field is -1. If a neighbour field value has its high bit set then the value (without the high bit) is the index of another octtree leaf (this is the case when when the neighbour leaf is equal to or larger than the leaf). If the high bit is not set then the value is an index into a quadtree node array (the [[OBD:QTNA|QTNA]] field of [[OBD:AKOT|AKOT]]) (this is the case when there is more than one leaf neighbour for a face). | :A leaf can have 6 neighbours (one for each face). If a face does not have a neighbour (it's on an environment border) then the coresponding field is -1. If a neighbour field value has its high bit set then the value (without the high bit) is the index of another octtree leaf (this is the case when when the neighbour leaf is equal to or larger than the leaf). If the high bit is not set then the value is an index into a quadtree node array (the [[OBD:QTNA|QTNA]] field of [[OBD:AKOT|AKOT]]) (this is the case when there is more than one leaf neighbour for a face). | ||
;Example | ;Example | ||
:The above leaf does not intersect any quads, has its maximum corner at (-2048.0, -2048.0, -2048.0), a size of 2048.0, no neighbours for all negative faces ( | :The above leaf does not intersect any quads, has its maximum corner at (-2048.0, -2048.0, -2048.0), a size of 2048.0, no neighbours for all negative faces (it's right in the negative corner of the environment) and positive faces have leaves as neighbours (no quadtree nodes here). | ||
;Theoretical limits | |||
:If the 8192x8192x8192 environment is subdivided into 16x16x16 cubes in all three directions, the total number of leaves is 512x512x512 = 134,217,728. Theoretically the data structures allow for a densely packed level where each 16x16x16 volume has some quads inside it (theoretically up to 4096, i.e., a maximum of 549,755,813,888 quads per level). In practice, the engine imposes much more modest limitations: a maximum of 262144 quads per level (tentative, to be confirmed), and probably another limitation on the amount of polygons on-screen. Coincidentally, 262144=512x512 quads exactly correspond to a 8192x8192 floor paved (in two directions) with 16x16 quads. | |||
Revision as of 10:57, 30 July 2020
|
|
| Offset | Type | Raw Hex | Value | Description |
|---|---|---|---|---|
| 0x00 | res_id | 01 45 02 00 | 581 | 00581-.OTLF |
| 0x04 | lev_id | 01 00 00 06 | 3 | level 3 |
| 0x08 | char[20] | AD DE | dead | unused |
| 0x1C | int32 | 03 49 00 00 | 18691 | array size |
| First element (black outline) | ||||
| 0x00 | int12-20 | 00 00 00 00 | 0, 0 | bits 0-11 (12 bits) contain the number of gunk quads that intersect this leaf, bits 12-31 (20 bits) contain the index of the gunk quad list; see details below |
| 0x04 | int32hb | FF FF FF FF | -1 | negative x neighbour |
| 0x08 | int32hb | 01 00 00 80 | 1, high bit | positive x neighbour |
| 0x0C | int32hb | FF FF FF FF | -1 | negative y neighbour |
| 0x10 | int32hb | 02 00 00 80 | 2, high bit | positive y neighbour |
| 0x14 | int32hb | FF FF FF FF | -1 | negative z neighbour |
| 0x18 | int32hb | 04 00 00 80 | 4, high bit | positive z neighbour |
| 0x1C | int9-9-9-5 | 7F FE FC 39 | 127, 127, 127, 7 | bits 0-8 (9 bits) contain the index of max x, bits 9-17 (9 bits) contain the index of max y, bits 18-26 (9 bits) contain the index of max z and bits 27-31 (5 bits) contain the index of the size of this leaf; see details below |
| 0x20 | int8-24 | 00 00 00 00 | 0, 0 | bits 0-7 (8 bits) intersected BNV count, bits 8-31 (24 bits) BNV list index; see details below |
- Intersected gunk quads
- An octtree leaf (OTLF) stores its size and position and the gunk quads that intersect it. The first field contains an index/count pair that is used to access the first IDXA field that is stored in the AKOT that owns this leaf. This IDXA contains the gunk quad numbers that intersect the leaf. In theory there can be at most 4096 gunk quads that intersect a leaf but in practice this number is much lower (max is 462). In addition the threshold limit used to build the octree seems to be 19 gunk quads per leaf. I.e., in Oni's levels, only the smallest leaves (with size 16x16x16) have more than 19 quads; larger leaves containing 20 and more quads are subdivided into "other, smaller boxes".
- Intersected BNVs
- An octtree leaf can intersect some BNVs (see AKVA). The last field contains the index and count of this list in the second IDXA field of AKOT.
- Position and size
- The position (of leaf's positive corner) is stored as three 9 bit fields. These values are not the x, y and z coordinates themselves but they are indices into a constant table. This constant table has 512 entries starting with -4080.0 and going up to 4096.0 in 16 units increments.
- The size of leaf is stored in a 5 bit field and it is and index into another constant table. This table has 9 entries starting with 16.0 and going up to 4096.0 (each entry is double the previous one).
- Maximum environment size is (8192.0, 8192.0, 8192.0)
- Minimum coordinate is (-4096.0, -4096.0, -4096.0)
- Maximum coordinate is (4096.0, 4096.0, 4096.0)
- Minimum leaf size is 16.0
- Maximum leaf size is 4096.0 (this means that there will always be at least 8 leaves because the size of the environment is double).
- Neighbours
- A leaf can have 6 neighbours (one for each face). If a face does not have a neighbour (it's on an environment border) then the coresponding field is -1. If a neighbour field value has its high bit set then the value (without the high bit) is the index of another octtree leaf (this is the case when when the neighbour leaf is equal to or larger than the leaf). If the high bit is not set then the value is an index into a quadtree node array (the QTNA field of AKOT) (this is the case when there is more than one leaf neighbour for a face).
- Example
- The above leaf does not intersect any quads, has its maximum corner at (-2048.0, -2048.0, -2048.0), a size of 2048.0, no neighbours for all negative faces (it's right in the negative corner of the environment) and positive faces have leaves as neighbours (no quadtree nodes here).
- Theoretical limits
- If the 8192x8192x8192 environment is subdivided into 16x16x16 cubes in all three directions, the total number of leaves is 512x512x512 = 134,217,728. Theoretically the data structures allow for a densely packed level where each 16x16x16 volume has some quads inside it (theoretically up to 4096, i.e., a maximum of 549,755,813,888 quads per level). In practice, the engine imposes much more modest limitations: a maximum of 262144 quads per level (tentative, to be confirmed), and probably another limitation on the amount of polygons on-screen. Coincidentally, 262144=512x512 quads exactly correspond to a 8192x8192 floor paved (in two directions) with 16x16 quads.
| ONI BINARY DATA |
|---|
| OTIT << Other file types >> PLEA |
| OTLF : Oct Tree Leaf Node Array |
| Level file |