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.

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. These items also encode the retrogressive changes in polygon ordering from the last to first lists. The encoding also specifies any new onscreen polygons not previously visible and any old polygons no longer visible 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:

*WWWPPPPPPPPPPPP

• 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 removing nodes minus 2Rel. Index of start of adding nodes minus 2	2 bytes	a + 2
0x6	Rel. Index of end of adding nodes minus 2Rel. Index of start of swapping nodes minus 2	2 bytes	r + 2
Nodes/List
0x8	Removing Nodes	(a - 2) x 2 bytes	*
0x8 + ((a - 2) x 2)	Adding 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 modifying 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/Removing Nodes

Adding and Removing nodes have the same format:

SSSSNNNN NNNNNNNN (PPPPPPPP PPPPPPPP x (S+1))

• S = add/skip count (number of polygon IDs to add/skip)
• N = add/skip index (relative to source point)
• P = polygon ID(s) to add when inserting
  • These have the following format: CWWWPPPPPPPPPPPP
    • W = index of world model
    • P = index of polygon in world model
    • C = copy flag (determines whether the ID is included or excluded from the addition/removal)

A value of 0xFFFF is sometimes used as an indicator of the last adding/removing node in a region, however this is not always the case. If a node with this value is encountered during processing of a region, it is simply skipped.

Adding nodes are sorted in ascending order by the indices into the current polygon list that they refer to.

• During a gain in progress (progression), an adding node is processed by adding its specified polygon ID, or sequence of polygon IDs, at the specified index within the current polygon list.
• During a loss in progress (retrogression), an adding node is processed as if it were a removing node-that is, by removing the specified number of polygon IDs (skip count), from the specified index (skip index) within the current polygon list.

Likewise, removing nodes are sorted in ascending order by the indices into the current polygon list that they refer to.

• During a gain in progress (progression), a removing node is processed by removing the specified number of polygon IDs (skip count), from the specified index (skip index) within the current polygon list.
• During a loss in progress (retrogression), a removing node is processed as if it were an adding node-that is, by adding its specified polygon ID, or sequence of polygon IDs, at the specified index within the current polygon list.

Swapping Nodes

Format A: 1BBBBAAA AAAAAAAA [01CCCCCC CCCDDDDD]

Format B: 00**AAAA AAAAAAAA 00**BBBB BBBBBBBB [01CCCCCC CCCDDDDD]

• A = index of Polygon ID A
• B = index of Polygon ID B relative to A + 1
• C = index of Polygon ID C relative to A
• D = index of Polygon ID D relative to C + 17

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 01CCCCCC CCCDDDDD-this particular swapping node is processed as a swap between the 2 respective polygon IDs C and D at the specified indices (the first of which is relative to that 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.)

Whether during a progression or retrogression, a swapping node is processed as a swap between the 2 respective polygon IDs at the same 2 specified indices.

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. Both lists are raw polygon lists, so no decoding [and thus a direct copy] is involved.

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.

Assuming that progress is lost, i.e. the camera retrogresses, and that the camera does not progress and exit the path (at its exit point), the next possible progress that can be attained after the path is entered at its exit point/after progress n is progress n-1. However, the corresponding list item in the Type 4 entry (progress n-1 = item n - 1 = second-to-last 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 n, contains the content of the last list=exit point's corresponding source/target list) shall be modified to yield the polygon list that it (the difference list) encodes. When progress n-2 is attained, the corresponding difference list then works on the modified list in further modification; this continues in the same trend for nearer progresses, such that when progress 1 is attained, the current polygon list has undergone enough modification that it is almost identical to the source/target list corresponding to progress 0=first list. 

The modification process consists of 2 stages: the first stage is a swapping stage, and the second stage is a rebuilding stage.

• During a progression, the swapping stage comes after the rebuilding stage
• During a retrogression, the swapping stage comes before the 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).

During a progression, the swapping stage works forward through the region, processing each node, starting with the first swapping node and ending with the last. During a retrogression, the swapping stage works backward through the region as it processes each node, starting with the last swapping node and ending with the first. 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.

The current polygon list is double-buffered: the game allocates 2 separate regions of memory for holding 2 separate polygon buffers; at any given time, one of these lists-the active polygon list-is the current polygon list, and the other list is the inactive polygon list.

At the start of the rebuilding stage, the current adding node and the current removing node are defined, respectively, as the first adding and removing nodes in the difference list. The current source point is then set to the beginning of [the list of polygon IDs in] the active/current polygon list, and the current insertion point is set to the beginning of [the list of polygon IDs in] the inactive display list.

Until the current source point reaches the end of the current polygon list, the following steps are repeated:

1. If neither the current adding node nor the current removing node reference the node at the current source point, all polygon IDs from the source point to the polygon ID at the nearest index (smallest)-either that referred to by the current adding node or the current removing node-are copied to the inactive polygon list at the current insertion point.
2. The current insertion point is then moved to the end of the polygon IDs that were copied to the inactive polygon list, and the current source point is moved to the end of the corresponding polygon IDs that were copied from [in] the active polygon list.
   • If the current adding node refers to the polygon ID at the nearest index (at the current source point), then that node is processed, effectively appending additional polygon IDs to the inactive polygon list at the current insertion point; the current insertion point is then moved to the end of the appended polygon IDs, and the current adding node is updated to the next adding node in the difference list.
   • If the current removing node refers to the polygon ID at the nearest index (at the current source point), then that node is processed, effectively skipping a number of polygon IDs by moving the source point ahead; the current removing node is then updated to the next removing node in the difference list.
   • If the current removing node and the current adding node both refer to [a polygon ID at] the same index, then both are processed as described above and updated to the next nodes in their respective regions.

Additional Notes

Note that, during a retrogression, adding nodes are processed as removing nodes and removing nodes are processed as adding nodes. Thus, the adding node region becomes the removing node region and vice-versa. The difference lists are said to encode the changes from the first source/target polygon list to the last source/target polygon list progressively and retrogressively. Assuming the camera starts at the path's first/entrance/initial [progress] point, when progressing along the path to a new progress, some polygons at the initial progress that were not visible/off screen will become visible/on screen at the new progress and vice versa. After reaching the new progress, if the camera then retrogresses back to the initial progress, the same polygons that were added/that previously became visible should be removed, thus returning to their initial state of visibility (not visible), and the same polygons that were removed/that previously became off screen (not visible) should be added, thus returning to their initial visible, on screen state.

The same correlation can be made between a change in obstruction between polygons and a swap of their polygon IDs during a progression or retrogression. Given any 2 polygons such that one appears behind and then in front of the other (or vice versa), respectively, before and after a progression, they are the same 2 polygons such that one appears in front of and then behind the other (or vice versa) before and after a countering retrogression. Thus, whether during a progression or retrogression, a swapping node is processed as a swap between the 2 respective polygon IDs at the same 2 specified indices-that is, the same swap operation between the same 2 polygons is performed in either case. Note that, while a change in sort order via swap is equivalent to its counteractive operation, and thus the same swap operation is decoded for both progression and retrogression, a change in visibility via add is not equivalent to the counteractive remove and vice-versa, hence the differing decoding process from progression to retrogression and vice-versa for adding/removing nodes.

The usage of forward slash in source/target list indicates that, neither the first nor the last list in a Type 4 entry are strictly a source or target list. When entering a path at its entrance point (progress 0), if the camera continues to progress along the path, the source list = the first list (copied as the active polygon list) should ultimately reach the form of the target list = the last list, lists being the lists in the corresponding Type 4 entry. When entering a path at its exit point (progress n), if the camera continues to retrogress back to the beginning of the path, the source list = the last list (copied as the active polygon list) should ultimately reach the form of the target list = the first list. 

Conclusion

The decoding process will have accomplished creating a modified version of the active polygon list in the inactive polygon list, using the encoded difference list. The inactive polygon list is finally swapped with the active/current polygon list, thus redefining the current polygon list as the modified list.

During world model primitive creation and transformation, for each polygon ID in the current polygon list from the end to the beginning, a representative 3-point polygon primitive is created (using the vertex data for the polygon with that ID, in one of the 8 current zone world models) and transformed accordingly; for each primitive created, its tag field is pointed to the representative primitive for the previous polygon [ID] in the list (when it is created). This creates a linked list of primitives starting with that created for the last polygon and ending with that created for the first. Since the polygon list sorts IDs by depth of their corresponding polygons, the primitive linked list sorts their corresponding primitives [by depth] from back to front. During the rendering stage, the GPU then steps through this list, rendering each polygon primitive in the appropriately specified order from back to front.

External Links

• https://news.ycombinator.com/item?id=9277569 - brief write-up on the sort lists