Technical Note : SLE0003
Author : Scott Evans
Created/Modified : 20/10/97
Description : Ordering tables

An ordering table on the Yaroze is simply an array. When the ordering table is initialised each element in the array will point to the next one in the array so forming a linked list structure. The last element points to a special value (0xffffff) which is used to terminate the list. Each element of the ordering table can be thought of as a header for another list, the primitive list. Any primitives added to this element will be added to the top of  this primitive list and the new primitive will point to the next element in the ordering table list or the next primitive in the primitive list

Say you have an ordering table with 2 elements in it OT1 and OT2, then the ordering table would look like this (after initialisation):

OT1--> OT2 --> end

If three primitives PRIM1, PRIM2 and PRIM3 were added to the ordering table in the order PRIM3, PRIM1, PRIM2 using the same priority (0) then the list would look like:

OT1--> PRIM2--> PRIM1--> PRIM3 --> OT2 --> end

When using this ordering table to render the display the GPU would execute the primitives in the order they appear in the ordering table so PRIM2 would be drawn first, then PRIM1 and then PRIM3. Since there are no more primitives in the list the links would be followed until the end is reached.

In 2D graphics you can determine which order the graphics are drawn by the order in which they are sorted into the ordering table. So if PRIM1, PRIM2 and PRIM3 were sprites which slightly overlapped each other then PRIM3 would be in front of PRIM1 and PRIM2 would be behind PRIM1.

In 3D graphics the ordering table is used as a Z buffer. A Z buffer is one way of achieving hidden surface removal. When 3D graphics are linked to an ordering table the position (or priority) they have in the ordering table is determined by the value of the Z co-ordinates. Polygons with larger Z co-ordinate values are placed nearer the start of the ordering table than polygons with smaller Z co-ordinate values. This means objects are drawn starting with the largest Z co-ordinate value and ending with the smallest Z co-ordinate value. After drawing is finished you end up with a correctly drawn 3D scene since the polygons drawn last will cover the previously drawn polygons.

Building an ordering table

A Yaroze ordering table before it is initialised is an array of GsOT_TAG structures. The GsOT_TAG structure is a 32 bit number, which is split into two bit fields tag and num. The tag field (24 bits) is a pointer to the next primitive (or another ordering table) in the list and the num field (8 bits) gives the size of the primitive (in words - Note : R3000 word is 32 bits, 4 bytes long) to draw.

The GsOT structure is the header for the list of tags.

The size of the ordering table is determined by the length member of GsOT. This can have a value between 1 and 14. The actual number of tags is 2^length. So a length of 1 will give an ordering table with 2 tags and a length of 14 will give 16384 tags. The org member is used to point to the start of the list of tags and should always point to the start of the tag list. The tag member is used to point to the current tag which is the start of the list. This will change as the ordering table is drawn and is reset by GsClearOt(). The offset member is not currently used but if it was would give the start of the ordering table, so if offset was 100 then the 100th tag of the ordering table would be considered the first tag. Point is used when merging two ordering tables, it determines the point at which the tables will be merged.

When using 3D graphics the larger the ordering table the greater Z resolution you have which allows more polygons to be sorted in the ordering table without problems when drawing them. If you have a relatively small ordering table compared to your polygons Z resolutions then most of the polygons will be in the same primitive list (Z co-ordinate values are scaled to the size of the ordering table) which can cause problems during drawing (polygons drawn in the wrong order). For example two primitives with different Z resolutions might get scaled to the same primitive list. In this case they will be drawn in the order they are added to the list and not depending on the value of the Z co-ordinates.

Once you have defined an ordering table during each frame of your program you have to initialise it, link the graphic primitives to it and then execute it.

At the start of each frame the ordering table must be cleared, with the GsClearOt() function. This sets all the tags in the ordering table pointing to the next tag and the last tag points to a terminating value. To link primitives to the ordering table the GsSort… functions are used.

For example the GsSortBoxFill() function will create a 4 sided polygon primitive with the attributes of the box and place it in the current active packet buffer. The ordering table tag will be set to point to the primitive and the pointer in the primitive will point to the next primitive or tag in the ordering table.

Once all the programs primitives have been placed in the ordering table the GsDrawOt() function will draw the contents of the ordering table on the screen. It does this by simply following the links in the ordering table and any primitives found at the links are drawn by the GPU. This is continued until the terminating tag is reached.

Multiple ordering tables

As mentioned above an ordering table with a small number of tags can cause problems when drawing polygons, which have a large range of Z co-ordinate values. To overcome this you could simply increase the size of the ordering table but this itself can cause another problem.

In some cases when using 3D graphics you will find that sections of a large ordering table are never used or not used that often. This means memory used by the wasted part of the ordering table could be used for other purposes. To improve this situation you can use multiple ordering tables.

Say you had 200 polygons that got scaled to the same primitive list. When drawing this primitive list you would see some glitches since all the polygons are grouped together in no particular order. To solve this problem we can use another ordering table, which has a greater Z resolution than the first. If a polygon will not fit into the first ordering table it can be sorted into the second larger ordering table and the two ordering tables can be combined into one ready for drawing.

This document in word format.
This document in text format.