neo/renderer/tr_orderIndexes.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28 #include "../idlib/precompiled.h"
  29 #pragma hdrstop
  30
  31 #include "tr_local.h"
  32
  33
  34 /*
  35 ===============
  36 R_MeshCost
  37 ===============
  38 */
  39 #define CACHE_SIZE      24
  40 #define STALL_SIZE      8
  41 int     R_MeshCost( int numIndexes, glIndex_t *indexes ) {
  42         int     inCache[CACHE_SIZE];
  43         int     i, j, v;
  44         int     c_stalls;
  45         int     c_loads;
  46         int     fifo;
  47
  48         for ( i = 0 ; i < CACHE_SIZE ; i++ ) {
  49                 inCache[i] = -1;
  50         }
  51
  52         c_loads = 0;
  53         c_stalls = 0;
  54         fifo = 0;
  55
  56         for ( i = 0 ; i < numIndexes ; i++ ) {
  57                 v = indexes[i];
  58                 for ( j = 0 ; j < CACHE_SIZE ; j++ ) {
  59                         if ( inCache[ ( fifo + j ) % CACHE_SIZE ] == v ) {
  60                                 break;
  61                         }
  62                 }
  63                 if ( j == CACHE_SIZE ) {
  64                         c_loads++;
  65                         inCache[ fifo % CACHE_SIZE ] = v;
  66                         fifo++;
  67                 } else if ( j < STALL_SIZE ) {
  68                         c_stalls++;
  69                 }
  70         }
  71
  72         return c_loads;
  73 }
  74
  75
  76 typedef struct vertRef_s {
  77         struct vertRef_s        *next;
  78         int                     tri;
  79 } vertRef_t;
  80
  81 /*
  82 ====================
  83 R_OrderIndexes
  84
  85 Reorganizes the indexes so they will take best advantage
  86 of the internal GPU vertex caches
  87 ====================
  88 */
  89 void R_OrderIndexes( int numIndexes, glIndex_t *indexes ) {
  90         bool    *triangleUsed;
  91         int                     numTris;
  92         glIndex_t       *oldIndexes;
  93         glIndex_t       *base;
  94         int                     numOldIndexes;
  95         int                     tri;
  96         int                     i;
  97         vertRef_t       *vref, **vrefs, *vrefTable;
  98         int                     numVerts;
  99         int                     v1, v2;
 100         int                     c_starts;
 101         int                     c_cost;
 102
 103         if ( !r_orderIndexes.GetBool() ) {
 104                 return;
 105         }
 106
 107         // save off the original indexes
 108         oldIndexes = (glIndex_t *)_alloca( numIndexes * sizeof( *oldIndexes ) );
 109         memcpy( oldIndexes, indexes, numIndexes * sizeof( *oldIndexes ) );
 110         numOldIndexes = numIndexes;
 111
 112         // make a table to mark the triangles when they are emited
 113         numTris = numIndexes / 3;
 114         triangleUsed = (bool *)_alloca( numTris * sizeof( *triangleUsed ) );
 115         memset( triangleUsed, 0, numTris * sizeof( *triangleUsed ) );
 116
 117         // find the highest vertex number
 118         numVerts = 0;
 119         for ( i = 0 ; i < numIndexes ; i++ ) {
 120                 if ( indexes[i] > numVerts ) {
 121                         numVerts = indexes[i];
 122                 }
 123         }
 124         numVerts++;
 125
 126         // create a table of triangles used by each vertex
 127         vrefs = (vertRef_t **)_alloca( numVerts * sizeof( *vrefs ) );
 128         memset( vrefs, 0, numVerts * sizeof( *vrefs ) );
 129
 130         vrefTable = (vertRef_t *)_alloca( numIndexes * sizeof( *vrefTable ) );
 131         for ( i = 0 ; i < numIndexes ; i++ ) {
 132                 tri = i / 3;
 133
 134                 vrefTable[i].tri = tri;
 135                 vrefTable[i].next = vrefs[oldIndexes[i]];
 136                 vrefs[oldIndexes[i]] = &vrefTable[i];
 137         }
 138
 139         // generate new indexes
 140         numIndexes = 0;
 141         c_starts = 0;
 142         while ( numIndexes != numOldIndexes ) {
 143                 // find a triangle that hasn't been used
 144                 for ( tri = 0 ; tri < numTris ; tri++ ) {
 145                         if ( !triangleUsed[tri] ) {
 146                                 break;
 147                         }
 148                 }
 149                 if ( tri == numTris ) {
 150                         common->Error( "R_OrderIndexes: ran out of unused tris" );
 151                 }
 152
 153                 c_starts++;
 154
 155                 do {
 156                         // emit this tri
 157                         base = oldIndexes + tri * 3;
 158                         indexes[numIndexes+0] = base[0];
 159                         indexes[numIndexes+1] = base[1];
 160                         indexes[numIndexes+2] = base[2];
 161                         numIndexes += 3;
 162
 163                         triangleUsed[tri] = true;
 164
 165                         // try to find a shared edge to another unused tri
 166                         for ( i = 0 ; i < 3 ; i++ ) {
 167                                 v1 = base[i];
 168                                 v2 = base[(i+1)%3];
 169
 170                                 for ( vref = vrefs[v1] ; vref ; vref = vref->next ) {
 171                                         tri = vref->tri;
 172                                         if ( triangleUsed[tri] ) {
 173                                                 continue;
 174                                         }
 175
 176                                         // if this triangle also uses v2, grab it
 177                                         if ( oldIndexes[tri*3+0] == v2
 178                                                 || oldIndexes[tri*3+1] == v2
 179                                                 || oldIndexes[tri*3+2] == v2 ) {
 180                                                 break;
 181                                         }
 182                                 }
 183                                 if ( vref ) {
 184                                         break;
 185                                 }
 186                         }
 187
 188                         // if we couldn't chain off of any verts, we need to find a new one
 189                         if ( i == 3 ) {
 190                                 break;
 191                         }
 192                 } while ( 1 );
 193         }
 194
 195         c_cost = R_MeshCost( numIndexes, indexes );
 196
 197 }
 198
 199
 200 /*
 201
 202   add all triangles that can be specified by the vertexes in the last 14 cache positions
 203
 204   pick a new vert to add to the cache
 205   don't pick one in the 24 previous cache positions
 206   try to pick one that will enable the creation of as many triangles as possible
 207
 208   look for a vert that shares an edge with the vert about to be evicted
 209
 210
 211 */
 212