2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
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.
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.
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/>.
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.
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.
26 ===========================================================================
28 #include "../idlib/precompiled.h"
41 int R_MeshCost( int numIndexes, glIndex_t *indexes ) {
42 int inCache[CACHE_SIZE];
48 for ( i = 0 ; i < CACHE_SIZE ; i++ ) {
56 for ( i = 0 ; i < numIndexes ; i++ ) {
58 for ( j = 0 ; j < CACHE_SIZE ; j++ ) {
59 if ( inCache[ ( fifo + j ) % CACHE_SIZE ] == v ) {
63 if ( j == CACHE_SIZE ) {
65 inCache[ fifo % CACHE_SIZE ] = v;
67 } else if ( j < STALL_SIZE ) {
76 typedef struct vertRef_s {
77 struct vertRef_s *next;
85 Reorganizes the indexes so they will take best advantage
86 of the internal GPU vertex caches
89 void R_OrderIndexes( int numIndexes, glIndex_t *indexes ) {
92 glIndex_t *oldIndexes;
97 vertRef_t *vref, **vrefs, *vrefTable;
103 if ( !r_orderIndexes.GetBool() ) {
107 // save off the original indexes
108 oldIndexes = (glIndex_t *)_alloca( numIndexes * sizeof( *oldIndexes ) );
109 memcpy( oldIndexes, indexes, numIndexes * sizeof( *oldIndexes ) );
110 numOldIndexes = numIndexes;
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 ) );
117 // find the highest vertex number
119 for ( i = 0 ; i < numIndexes ; i++ ) {
120 if ( indexes[i] > numVerts ) {
121 numVerts = indexes[i];
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 ) );
130 vrefTable = (vertRef_t *)_alloca( numIndexes * sizeof( *vrefTable ) );
131 for ( i = 0 ; i < numIndexes ; i++ ) {
134 vrefTable[i].tri = tri;
135 vrefTable[i].next = vrefs[oldIndexes[i]];
136 vrefs[oldIndexes[i]] = &vrefTable[i];
139 // generate new indexes
142 while ( numIndexes != numOldIndexes ) {
143 // find a triangle that hasn't been used
144 for ( tri = 0 ; tri < numTris ; tri++ ) {
145 if ( !triangleUsed[tri] ) {
149 if ( tri == numTris ) {
150 common->Error( "R_OrderIndexes: ran out of unused tris" );
157 base = oldIndexes + tri * 3;
158 indexes[numIndexes+0] = base[0];
159 indexes[numIndexes+1] = base[1];
160 indexes[numIndexes+2] = base[2];
163 triangleUsed[tri] = true;
165 // try to find a shared edge to another unused tri
166 for ( i = 0 ; i < 3 ; i++ ) {
170 for ( vref = vrefs[v1] ; vref ; vref = vref->next ) {
172 if ( triangleUsed[tri] ) {
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 ) {
188 // if we couldn't chain off of any verts, we need to find a new one
195 c_cost = R_MeshCost( numIndexes, indexes );
202 add all triangles that can be specified by the vertexes in the last 14 cache positions
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
208 look for a vert that shares an edge with the vert about to be evicted