Sort List - Revision history

Chekwob: 5 revisions imported: Initial import from Wikia

2019-04-27T17:44:38Z

5 revisions imported: Initial import from Wikia

73.44.175.29: /* Adding/Removing Nodes */ Corrected adding/removing node format. Added adding/removing node polygon ID format and description of copy flag.

2017-04-16T21:50:02Z

‎Adding/Removing Nodes: Corrected adding/removing node format. Added adding/removing node polygon ID format and description of copy flag.

Wikia>WurlyFox at 05:34, 24 July 2016

2016-07-24T05:34:55Z

Wikia>WurlyFox: /* Decoding */

2015-08-15T04:47:20Z

‎Decoding

Wikia>WurlyFox: /* Adding Nodes */

2015-08-15T04:45:02Z

‎Adding Nodes

Show changes

Wikia>WurlyFox: Created page with "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 ..."

2015-08-14T10:30:03Z

Created page with "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 ..."

New page

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''. 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 ===
{| class="article-table"
!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:

<code>PPPPPPPPPPPPWWWW</code>
* W = index of world model
* P = index of polygon in world model
Thus, a polygon id refers to the ''P''th polygon of the ''W''th world model in the zone with a path that references this entry.

=== Item 2 to N-1: Difference List ===
{| class="article-table"
!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 2'''Rel. Index of start of removing nodes '''minus 2'''
|2 bytes
|a + 2
|-
|0x6
|Rel. Index of end of removing nodes '''minus 2'''Rel. Index of start of swapping nodes '''minus 2'''
|2 bytes
|r + 2
|-
| colspan="4" |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 ===
<code>Format A: 1BBBBAAA AAAAAAAA [01DDDDDD DDDCCCCC] </code>

<code>Format B: 00**AAAA AAAAAAAA 00**BBBB BBBBBBBB [01DDDDDD DDDCCCCC]</code>

* <code>A</code> = index of Polygon ID A
* <code>B</code> = index of Polygon ID B relative to A + 1
* <code>C</code> = index of Polygon ID C relative to A + 17
* <code>D</code> = 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 <code>01DDDDDD DDDCCCCC</code>-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.

@@ Line 96: / Line 96: @@
 Adding and Removing nodes have the same format:
-<code>ISSSSNNN NNNNNNNN (PPPPPPPP PPPPPPPP x (S+1))</code>
+<code>SSSSNNNN NNNNNNNN (PPPPPPPP PPPPPPPP x (S+1))</code>
 * <code>S</code> = add/skip count (number of polygon IDs to add/skip)
 * <code>N</code> = add/skip index (relative to source point)
 * <code>P</code> = polygon ID(s) to add when inserting
-* <code>I</code> = intermediate copy flag
+** These have the following format: <code>CWWWPPPPPPPPPPPP</code>
-The last adding/removing node in a region is indicated with the value <code>0xFFFF</code>.
+A value of <code>0xFFFF</code> 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.

@@ Line 132: / Line 132: @@
 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 further 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.
+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''.

← Older revision	Revision as of 17:44, 27 April 2019
(No difference)

@@ Line 38: / Line 38: @@
 Each Polygon ID has the following format:
-<code>PPPPPPPPPPPPWWWW</code>
+<code>*WWWPPPPPPPPPPPP</code>
 * W = index of world model
 * P = index of polygon in world model
@@ Line 61: / Line 61: @@
 |-
 |0x4
-|Rel. Index of end of adding nodes '''minus 2'''Rel. Index of start of removing nodes '''minus 2'''
+|Rel. Index of end of removing nodes '''minus 2'''Rel. Index of start of adding nodes '''minus 2'''
 |2 bytes
 |a + 2
 |-
 |0x6
-|Rel. Index of end of removing nodes '''minus 2'''Rel. Index of start of swapping nodes '''minus 2'''
+|Rel. Index of end of adding nodes '''minus 2'''Rel. Index of start of swapping nodes '''minus 2'''
 |2 bytes
 |r + 2
@@ Line 73: / Line 73: @@
 |-
 |0x8
-|Adding Nodes
+|Removing Nodes
 |(a - 2) x 2 bytes
 |*
 |-
 |0x8 + ((a - 2) x 2)
-|Removing Nodes
+|Adding Nodes
 |(r-a-2) x 2 bytes
 |*
@@ Line 100: / Line 100: @@
 * <code>N</code> = add/skip index (relative to source point)
 * <code>P</code> = polygon ID(s) to add when inserting
-* <code>I</code> = interleave flag
+* <code>I</code> = intermediate copy flag
 The last adding/removing node in a region is indicated with the value <code>0xFFFF</code>.
@@ Line 112: / Line 112: @@
 === Swapping Nodes ===
-<code>Format A: 1BBBBAAA AAAAAAAA [01DDDDDD DDDCCCCC] </code>
+<code>Format A: 1BBBBAAA AAAAAAAA [01CCCCCC CCCDDDDD] </code>
-<code>Format B: 00**AAAA AAAAAAAA  00**BBBB BBBBBBBB [01DDDDDD DDDCCCCC]</code>
+<code>Format B: 00**AAAA AAAAAAAA  00**BBBB BBBBBBBB [01CCCCCC CCCDDDDD]</code>
 * <code>A</code> = index of Polygon ID A
 * <code>B</code> = index of Polygon ID B relative to A + 1
-* <code>C</code> = index of Polygon ID C relative to A + 17
+* <code>C</code> = index of Polygon ID C relative to A
-* <code>D</code> = index of Polygon ID D relative to B
+* <code>D</code> = 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 <code>01DDDDDD DDDCCCCC</code>-this particular swapping 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).
+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 <code>01CCCCCC CCCDDDDD</code>-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.)
@@ Line 168: / Line 168: @@
 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 <code>tag</code> 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.