[size="5"]Introduction

There are many factors which govern the speed of a 3d engine. In the past polygon rendering has probably been the major factor but, due to the increasing number of hardware 3d accelerators this probably wont be an issue anymore. However, one of the factors that is still important is the method behind polygon sorting.

[size="5"] A basic sort algorithm

The simplest and probably slowest routine you could create for your 3d engine would go something like this:

There are several optimisations you could do to the code above:-

• Write it in assembler.
• Sort pointers to polygons and index into them to find z values.
• decrement num_polys_to_sort every iteration of the do..while loop as the highest z value is pushed to the back every iteration. However, at the end of the day the routine would still be butt slow so drop it! It would be great if we didn't have to sort ANY data and there are two ways we could get our wish but, they also have a downside:
  
  [size="3"] ( 1 ) Z Buffering
  
  One of the beauties of z buffering is you don't need to sort but, before you start coding a z buffer routine - stop! Software z buffering is slow and should be avoided like the plague.However, if your engine is being made for a hardware accelerator that handles z buffering -stop wasting time and implement it.
  
  [size="3"] ( 2 ) Binary Space Partition Trees ( BSP Trees )
  
  I love bsp trees and you will too if the objects in your world are static ( e.g a landscape ). However, if your world is comprised of many moving objects avoid bsp trees. It is difficult and slow to insert moving objects into a static bsp tree. Many flight simulators use bsp trees to represent the ground as moving objects ( planes ) rarely interfere with it. If your world isn't static and the objects in the world are all of similiar dimensions and never interpenetrate you could create bsp trees for individual objects and then sort on objects instead of polygons.
  
  Well, if none of the above is any good and we have to have a polygon sort routine let us at least have a one pass sort algorithm ( loops suck ). The best method I have seen for one pass sorting is the ordering table - this method is so cool that it was implemented into the Sony Playstation Hardware.
  
  [size="5"] Ordering Table
  
  If you have lots of polygons to sort then an ordering table is the way forward. If you only a small polygon count then don't bother with an ordering tables - it may be slower than the simple sort...... An ordering table ( ot ) is an array of pointers to polygons. Each array element represents a positive z value and there should be z viewing distance elements. As we setup a new polygon we work out its middle z and store a pointer to the polygon in ot[ middle z ]. After we have processed all polygons we scan the ot in back to front order drawing any polygons we encounter. This is really simple but, you are probably thinking - what if two polygons share the same z coordinate? To combat this problem we store a pointer to another polygon inside the polygon structure. Before we add a polygon to the ot we check if a polygon is already occupying the same slot - if it is then we place a pointer to the resident polygon into the polygon we are trying to insert, then we insert the new polygon in place of the resident polygon. Another point I should raise is that usually in an ot one element represents ? z values. We divide the z component by ? and then insert into the ot. The value ? is usually a power of two ( for speed reasons ) and exists to save memory. I'll now describe the polygon structures as they may appear in an engine......
  
  
  long ot[ OTSIZE ];
typedef struct {
u_char id, color, pad1, pad2;
long nextprim;
int x0, y0, x1, y1, x2, y2;
} POLY_F3;
typedef struct {
u_char id, color, pad1, pad2;
long nextprim;
int x0, y0, x1, y1, x2, y2, x3, y3;
} POLY_F4;
  
  You can have any kind of polygon as long as it has an id and a nextprim pointer at the same offset as all the other types. When you first create a new polygon set nextprim to NULL and set the id to a unique id for that polygon type.
  
  Now I'll now describe the actual ot process as it may appear in an engine......
  
  1. Clear all entries of the ordering table to NULL.
  
  
  long *scratch = ot;
for ( loop = 0; loop < OTSIZE; loop++ )
*scratch++ = NULL;
  
  2. After we setup a new polygon - add it to the ot e.g.
  
  
  polygon calculation code....
AverageZ = ( v0.z + v1.z + v2.z ) / 3;
AddPrim( ( long )&newpoly[ polycount ], AverageZ );
next poly......

void AddPrim( long poly, long z )
{
z /= ZDIVIDEFAC;

if ( ot[ z ] == NULL )
{
// Slot empty so add new poly to this slot.
ot[ z ] = poly;

// Clear next prim part of poly structure.
( ( long * )( poly + 1 ) ) = NULL;
}

else
{
// Slot full so set next prim pointer and....
( ( long * )( poly + 1 ) ) = ot[ z ];

// ...overwrite poly.
ot[ z ] = poly;
}
  
  3. After all polys have been added scan through the ot ( reverse order! ) and draw any polys encountered.
  
  
  long *p = &ot[ OTSIZE ];
char *prim;
for ( loop = 0; loop < OTSIZE; loop++ )
{
// Poly in this slot?
if ( *( --p ) )
{
// Point prim at polygon.
prim = ( char * )( *p );
saveprim = prim;

// Check for next prim pointer - remember prim + 4 is a pointer to next prim in
// all polygon types.
while ( ( ( long * )*( prim + 1 ) ) )
{
DrawPrim( prim );

// Point at new prim.
prim = ( ( long * )*( prim + 1 ) );
}

prim = saveprim;
DrawPrim( prim );
}
}

//------------------------------------------------------------
void DrawPrim( char *prim )
{
// remember first byte is the primitive id!
switch ( *prim )
{
case POLYF3 : Draw 3 vertex flat poly
break;

case POLYG4 : Draw 4 vertex gourard poly
etc... etc..
}
}