Sort List
Sort Lists are delta encoded depth-sorted polygon lists. They are Type 4 entries. For each point in some camera path, a Type 4 entry encodes the depth order, when viewed from the position and orientation of the camera at that point, of all visible polygons in the [up to] 8 visible worlds of the path's parent zone. Each distinct camera path from a zone in the level refers to its own Type 4 entry. Thus, at every possible position and orientation of the camera, the painter's algorithm can be employed in rendering visible geometric content (worlds), given the corresponding decoded sort list.
Contents
Introduction
Each zone specifies up to 8 individual worlds. Together, these worlds compose the geometric content visible to the player at all possible positions/orientations of the camera along the zone's paths. The representative worlds for that zone shall naturally be observed as the camera travels along its paths, through the 3-dimensional space occupied by the zone.
The camera at any instant is positioned (i.e. translated) at a particular point on its current path with index given by its current progress along that path. Each point in the path is also associated with an orientation angle to which the camera is additionally rotated when it reaches that progress. Since each of a zone's camera path's points are indexed by [each possible] progress [that can be attained within that path], each subsequent point describes a further location and orientation for the camera to reach as the player makes a single, +1 = positive change in progress. Thus, for each change in progress, there is a change to a new predefined/fixed orientation and location for the camera, at which all polygons that compose the zone's representative geometry will have exhibited a change in relative location [from the camera]. At the camera's new location and orientation, some of these polygons will have naturally changed ordering to appear in front of some other polygons that, at the camera's previous location, they appeared to be behind. At this new location and orientation, there may also be some polygons that were previously off screen that should now be visible on screen-and some polygons that were previously visible on screen that should now be off screen.
The first and last items in a Sort List (Type 4) entry are important: they are the only purely raw, non-delta encoded polygon lists in the entry. Polygons are listed by Polygon ID. The first item in a Type 4 entry lists each visible polygon (belonging to the world models of the zone that contains the corresponding path) in sorted order from front to back when viewed from the camera position and orientation of the first camera path point (in the corresponding path). Conversely, the last item in a Type 4 entry lists each visible polygon in sorted order from front to back when viewed from the camera position and orientation of the last camera path point (in the corresponding path).
The items between the first and last items then encode the progressive changes in polygon ordering from the first to the last lists-hence the term delta encoding. The encoding also specifies any new onscreen polygons not previously observed and any old polygons no longer observed from one polygon list to the next.
Format
Item 1/Item N: Main Source/Target List
| Offset | Field | Size | Value |
|---|---|---|---|
| 0x0 | List Size (polygon ID count) | 2 bytes | c |
| 0x2 | List Type | 2 bytes | 0 |
| 0x4 | Polygon IDs | c x 2 bytes | * |
Polygon ID
Each Polygon ID has the following format:
PPPPPPPPPPPPWWWW
- W = index of world model
- P = index of polygon in world model
Thus, a polygon id refers to the Pth polygon of the Wth world model in the zone with a path that references this entry.
Item 2 to N-1: Difference List
| Offset | Field | Size | Value |
|---|---|---|---|
| 0x0 | List Size minus 2 (in hwords) | 2 bytes | c + 2 |
| 0x2 | List Type | 2 bytes | 1 |
| 0x4 | Rel. Index of end of adding nodes minus 2Rel. Index of start of removing nodes minus 2 | 2 bytes | a + 2 |
| 0x6 | Rel. Index of end of removing nodes minus 2Rel. Index of start of swapping nodes minus 2 | 2 bytes | r + 2 |
| Nodes/List | |||
| 0x8 | Adding Nodes | (a - 2) x 2 bytes | * |
| 0x8 + ((a - 2) x 2) | Removing Nodes | (r-a-2) x 2 bytes | * |
| 0x8 + ((r - 2) x 2) | Swapping Nodes | (c-r-a-2) x 2 bytes | * |
A difference list encodes changes in polygon ordering. Each change is encoded as a node. Each node specifies an individual operation performed in reordering the current polygon list to reach the form of the decoded [difference] list.
- Polygon reordering is encoded in these items for processing as swap operations between polygons [polygon ids] in the current polygon list.
- Changes from onscreen to offscreen are encoded in these items for processing as the operation of removing polygons from the current polygon list.
- Changes from offscreen to onscreen are encoded in these items for processing as the operation of adding polygons to the current polygon list.
Each node can be 1 of 3 types: a swapping node, an adding node, or a removing node. All nodes of one type are stored contiguously, in a region separate from that of nodes of other types; thus, a difference list has a swapping node region, an adding node region, and a removing node region.
Adding Nodes
TBD
Removing Nodes
TBD
Swapping Nodes
Format A: 1BBBBAAA AAAAAAAA [01DDDDDD DDDCCCCC]
Format B: 00**AAAA AAAAAAAA 00**BBBB BBBBBBBB [01DDDDDD DDDCCCCC]
A= index of Polygon ID AB= index of Polygon ID B relative to A + 1C= index of Polygon ID C relative to A + 17D= index of Polygon ID D relative to B
A swapping node is processed as a swap between the 2 respective polygon IDs A and B at the specified [possibly relative] indices. It may optionally be followed with up to one swapping node of the format 01DDDDDD DDDCCCCC-this particular node is processed as a swap between the 2 respective polygon IDs C and D at the specified indices (which are relative to those specified in the preceding node).
(By using an optional follow-up node, the somewhat limited range of relative destination indices available for specification using only the standard format is extended, along with the range of relative source indices, provided that the source index is within a given range of that of the preceding node's.)
Decoding
When a progress of 0 is attained in a path (i.e. the path is entered at the front), the corresponding source/target list (first item in the corresponding Type 4 entry) is copied in its entirety to overwrite the [game's] current polygon list. Similarly, when a progress of n is reached, where n is the maximum progress that can be attained in the path, the corresponding source/target list (last item in the corresponding Type 4 entry) is copied in its entirety to overwrite the current polygon list.
Assuming that progress is made and that the camera does not retrogress and exit the path, the next possible progress that can be attained after the path is entered at its entrance point/after progress 0 is progress 1. However, the corresponding list item in the Type 4 entry (progress 1 = item 2 = second item) is not in the format of a raw source/target list: it is in the format of an encoded difference list. Then, that difference list determines how the current polygon list (which, after progress 0, contains the content of the first list=entrance point's corresponding source/target list) shall be modified to yield the polygon list that it (the difference list) encodes. When progress 2 is attained, the corresponding difference list then works on the modified list in further modification; this continues in the same trend for further progresses, such that when progress n-1 is attained, the current polygon list has undergone enough modification that it is almost identical to the source/target list corresponding to progress n=last list.
The modification process consists of 2 stages: the first stage is a swapping stage, and the second stage is a rebuilding stage.
Swapping stage
The swapping stage begins by calculating the range of the swapping node region in the difference list; the beginning of the range-which is also the index of the first node in the region-is computed with (4+(r*2)), and the index of the last node in the list-which is also the index of the last node in the region-is computed with (4+(c-1)*2).
Working forwards/backwards through the region, starting with the first/last swapping node and ending with the last/first, each node is processed. The format section lists the possible swapping node formats and includes a description of how the nodes with those formats are processed. Ultimately, as a result of the swapping stage, the current polygon list will have undergone some rearrangement according to the swapping node specifications.
Rebuilding stage
The rebuilding stage begins by calculating the ranges of the adding and removing node regions, respectively, in the difference list. Adding nodes are sorted in ascending order by the indices into the current polygon list that they refer to; each encodes the operation of adding a specific polygon ID, or a specific sequence of polygon IDs, at some specific index within the current polygon list. Likewise, removing nodes are sorted in ascending order by the indices into the current display list that they refer to; each encodes the operation of removing a single polygon ID, or a specific number of polygon IDs, from some specific index within the current display list.
UNFINISHED
The current polygon list is double-buffered: the game allocates 2 separate regions of memory for holding 2 separate display lists; at any given time, one of these lists-the active display list-is the current display list, and the other list is the inactive display list.
At the start of the rebuilding stage, the current adding node and the current removing node are defined, respectively, as the first adding node and the first removing node in the difference list; the current 'source' point is then defined to be at the beginning of [the list of vertices in] the active/current display list, and the current insertion point is defined to be at the beginning of [the list of vertices in] the inactive display list.
If neither the current adding node nor the current removing node refer to an relative offset that equates to that of the source point, all vertices from that at the source point to the vertex at the closest offset-either that referred to by the current adding node or the current removing node-are copied to the inactive display list at the current insertion point; the current insertion point is then moved to the end of those vertices that were copied -to- the inactive display list, and the current source point is moved to the end of the corresponding vertices that were copied -from- in the active display list. If the current adding node refers to the closer offset (that of the current source point), then that node is processed, effectively appending additional vertices to the inactive display list at the current insertion point which is moved to the end of the appended vertices, and the current adding node is updated to the next adding node in the difference list. If the current removing node refers to the closer offset (that of the current source point), then -that- node is processed, effectively 'skipping' a number of source vertices by moving the source point ahead, and the current removing node is updated to the next removing node in the difference list. (If the current removing node and the current adding node both refer to the same offset-then both are processed as described above and updated to the next nodes in their respective regions.) The entire process described in this paragraph is then repeated until the source point reaches the end of the current display list.
