* Particles are now depth sorted

3 files changed, 94 insertions, 3 deletions

diff --git a/src/cgame/cg_local.h b/src/cgame/cg_local.h
index b5b35a43..e6b2d7d4 100644
--- a/src/cgame/cg_local.h
+++ b/src/cgame/cg_local.h
@@ -344,6 +344,8 @@ typedef struct particle_s
   pLerpValues_t     rotation;
   
   qboolean          valid;
+
+  int               sortKey;
 } particle_t;
 
 
@@ -1396,7 +1398,7 @@ extern  vmCvar_t    cg_drawSurfNormal;
 extern  vmCvar_t    cg_debugAlloc;
 extern  vmCvar_t    cg_wwSmoothTime;
 extern  vmCvar_t    cg_wwFollow;
-extern  vmCvar_t    cg_zsortLEs;
+extern  vmCvar_t    cg_depthSortParticles;
 extern  vmCvar_t    cg_consoleLatency;
 extern  vmCvar_t    cg_lightFlare;
 extern  vmCvar_t    cg_debugParticles;
diff --git a/src/cgame/cg_main.c b/src/cgame/cg_main.c
index 93c0e431..e3f34df4 100644
--- a/src/cgame/cg_main.c
+++ b/src/cgame/cg_main.c
@@ -193,7 +193,7 @@ vmCvar_t  cg_drawSurfNormal;
 vmCvar_t  cg_debugAlloc;
 vmCvar_t  cg_wwSmoothTime;
 vmCvar_t  cg_wwFollow;
-vmCvar_t  cg_zsortLEs;
+vmCvar_t  cg_depthSortParticles;
 vmCvar_t  cg_consoleLatency;
 vmCvar_t  cg_lightFlare;
 vmCvar_t  cg_debugParticles;
@@ -289,7 +289,7 @@ static cvarTable_t cvarTable[ ] =
   { &cg_debugAlloc, "cg_debugAlloc", "0", 0 },
   { &cg_wwSmoothTime, "cg_wwSmoothTime", "300", CVAR_ARCHIVE },
   { &cg_wwFollow, "cg_wwFollow", "1", CVAR_ARCHIVE|CVAR_USERINFO },
-  { &cg_zsortLEs, "cg_zsortLEs", "1", CVAR_ARCHIVE },
+  { &cg_depthSortParticles, "cg_depthSortParticles", "1", CVAR_ARCHIVE },
   { &cg_consoleLatency, "cg_consoleLatency", "3000", CVAR_ARCHIVE },
   { &cg_lightFlare, "cg_lightFlare", "3", CVAR_ARCHIVE },
   { &cg_debugParticles, "cg_debugParticles", "0", CVAR_CHEAT },
diff --git a/src/cgame/cg_particles.c b/src/cgame/cg_particles.c
index fee11a04..9925afba 100644
--- a/src/cgame/cg_particles.c
+++ b/src/cgame/cg_particles.c
@@ -25,6 +25,7 @@ static int                    numBaseParticles = 0;
 static particleSystem_t     particleSystems[ MAX_PARTICLE_SYSTEMS ];
 static particleEjector_t    particleEjectors[ MAX_PARTICLE_EJECTORS ];
 static particle_t           particles[ MAX_PARTICLES ];
+static particle_t           sortParticles[ MAX_PARTICLES ];
 
 /*
 ===============
@@ -1650,6 +1651,89 @@ static void CG_EvaluateParticlePhysics( particle_t *p )
 }
 
 
+#define GETKEY(x,y) (((x)>>y)&0xFF)
+
+/*
+===============
+CG_Radix
+===============
+*/
+static void CG_Radix( int bits, int size, particle_t *source, particle_t *dest )
+{
+  int count[ 256 ];
+  int index[ 256 ];
+  int i;
+  
+  memset( count, 0, sizeof( count ) );
+  
+  for( i = 0; i < size; i++ )
+    count[ GETKEY( source[ i ].sortKey, bits ) ]++;
+
+  index[ 0 ] = 0;
+  
+  for( i = 1; i < 256; i++ )
+    index[ i ] = index[ i - 1 ] + count[ i - 1 ];
+  
+  for( i = 0; i < size; i++ )
+    dest[ index[ GETKEY( source[ i ].sortKey, bits ) ]++ ] = source[ i ];
+}
+
+/*
+===============
+CG_RadixSort
+
+Radix sort with 4 byte size buckets
+===============
+*/
+static void CG_RadixSort( particle_t *source, particle_t *temp, int size )
+{
+  CG_Radix( 0,   size, source, temp );
+  CG_Radix( 8,   size, temp, source );
+  CG_Radix( 16,  size, source, temp );
+  CG_Radix( 24,  size, temp, source );
+}
+
+/*
+===============
+CG_CompactAndSortParticles
+
+Depth sort the particles
+===============
+*/
+static void CG_CompactAndSortParticles( void )
+{
+  int     i, j = 0;
+  int     numParticles;
+  vec3_t  delta;
+
+  for( i = MAX_PARTICLES - 1; i >= 0; i-- )
+  {
+    if( particles[ i ].valid )
+    {
+      while( particles[ j ].valid )
+        j++;
+
+      //no more holes
+      if( j >= i )
+        break;
+
+      particles[ j ] = particles[ i ];
+      memset( &particles[ i ], 0, sizeof( particles[ 0 ] ) );
+    }
+  }
+
+  numParticles = i;
+  
+  //set sort keys
+  for( i = 0; i < numParticles; i++ )
+  {
+    VectorSubtract( particles[ i ].origin, cg.refdef.vieworg, delta );
+    particles[ i ].sortKey = DotProduct( delta, delta );
+  }
+  
+  CG_RadixSort( particles, sortParticles, numParticles );
+}
+
 /*
 ===============
 CG_RenderParticle
@@ -1742,11 +1826,16 @@ void CG_AddParticles( void )
   particle_t    *p;
   int           numPS = 0, numPE = 0, numP = 0;
   
+  //remove expired particle systems
   CG_GarbageCollectParticleSystems( );
   
   //check each ejector and introduce any new particles
   CG_SpawnNewParticles( );
 
+  //sorting
+  if( cg_depthSortParticles.integer )
+    CG_CompactAndSortParticles( );
+
   for( i = 0; i < MAX_PARTICLES; i++ )
   {
     p = &particles[ i ];