tools/quake3/q3data/stripper.c

   1 /*
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #include <stdio.h>
  23 #include <string.h>
  24 #include <stdlib.h>
  25
  26 static int s_used[8192];                // same as MD3_MAX_TRIANGLES
  27
  28 /*
  29 ** FindNextTriangleInStrip
  30 **
  31 ** Given a surface and triangle this tries to find the next triangle
  32 ** in the strip that would continue the strip.  The next triangle in
  33 ** the strip should have the same winding as this triangle.
  34 */
  35 static int FindNextTriangleInStripOrFan( int mesh[][3], int tri, int orientation, int numTris, int odd )
  36 {
  37         int t;
  38         int sum = 0;
  39         int currentTri[3];
  40         int side;
  41         int a, b, c;
  42         int refa, refb;
  43
  44         currentTri[0] = mesh[tri][(0+orientation)%3];
  45         currentTri[1] = mesh[tri][(1+orientation)%3];
  46         currentTri[2] = mesh[tri][(2+orientation)%3];
  47
  48         if ( odd )
  49         {
  50                 refa = currentTri[1];
  51                 refb = currentTri[2];
  52         }
  53         else
  54         {
  55                 refa = currentTri[2];
  56                 refb = currentTri[0];
  57         }
  58
  59         // go through all triangles and look for sides that match
  60         // this triangle's
  61         for ( t = 0; t < numTris; t++ )
  62         {
  63                 // don't check against self or against previously used triangles
  64                 if ( t == tri )
  65                         continue;
  66                 if ( s_used[t] )
  67                         continue;
  68
  69                 // check all three sides of the candidate triangle
  70                 for ( side = 0; side < 3; side++ )
  71                 {
  72                         // check only the second (abutting) side
  73                         if ( ( refa == mesh[t][(side+1)%3] ) &&
  74                                  ( refb == mesh[t][side] ) )
  75                         {
  76
  77                                 a = mesh[t][0];
  78                                 b = mesh[t][1];
  79                                 c = mesh[t][2];
  80
  81                                 // rotate the candidate triangle to align it properly in the strip
  82                                 if ( side == 1 )
  83                                 {
  84                                         mesh[t][0] = b;
  85                                         mesh[t][1] = c;
  86                                         mesh[t][2] = a;
  87                                 }
  88                                 else if ( side == 2 )
  89                                 {
  90                                         mesh[t][0] = c;
  91                                         mesh[t][1] = a;
  92                                         mesh[t][2] = b;
  93                                 }
  94
  95                                 return t;
  96                         }
  97 /*
  98                         else
  99                         {
 100                                 Error( "fans not implemented yet" );
 101
 102                                 // check only the third (abutting) side
 103                                 if ( ( currentTri[2] == pSurf->baseTriangles[t].v[side].index ) &&
 104                                         ( currentTri[0] == pSurf->baseTriangles[t].v[(side+1)%3].index ) )
 105                                 {
 106                                         return t;
 107                                 }
 108                         }
 109 */
 110                 }
 111         }
 112
 113         return -1;
 114 }
 115
 116 /*
 117 ** StripLength
 118 */
 119 static int StripLength( int mesh[][3], int strip[][3], int tri, int orientation, int numInputTris, int fillNo )
 120 {
 121         int stripIndex = 0;
 122         int next;
 123
 124         int odd = 1;
 125
 126         strip[stripIndex][0] = mesh[tri][(0+orientation)%3];
 127         strip[stripIndex][1] = mesh[tri][(1+orientation)%3];
 128         strip[stripIndex][2] = mesh[tri][(2+orientation)%3];
 129         s_used[tri] = fillNo;
 130         stripIndex++;
 131
 132         next = tri;
 133
 134         while ( ( next = FindNextTriangleInStripOrFan( mesh, next, orientation, numInputTris, odd ) ) != -1 )
 135         {
 136                 s_used[next] = fillNo;
 137                 odd = !odd;
 138                 strip[stripIndex][0] = mesh[next][0];
 139                 strip[stripIndex][1] = mesh[next][1];
 140                 strip[stripIndex][2] = mesh[next][2];
 141                 stripIndex++;
 142
 143                 // all iterations after first need to be with an unrotated reference triangle
 144                 orientation = 0;
 145         }
 146
 147         return stripIndex;
 148 }
 149
 150 /*
 151 ** BuildOptimizedList
 152 **
 153 ** Attempts to build the longest strip/fan possible.  Does not adhere
 154 ** to pure strip or fan, will intermix between the two so long as some
 155 ** type of connectivity can be maintained.
 156 */
 157 #define MAX_ORIENTATIONS                3
 158 #define MAX_MATCHED_SIDES               4
 159 #define MAX_SEED_TRIANGLES              16
 160
 161 static int BuildOptimizedList( int mesh[][3], int strip[][3], int numInputTris )
 162 {
 163         int t;
 164         int stripLen = 0;
 165         int startTri = -1;
 166         int bestTri = -1, bestLength = 0, bestOrientation = -1;
 167         int matchedSides = 0;
 168         int orientation = 0;
 169         int seedTriangles[MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES];
 170         int seedLengths[MAX_ORIENTATIONS][MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES];
 171         int numSeeds[MAX_MATCHED_SIDES] = { 0, 0, 0 };
 172         int i;
 173
 174         // build a ranked list of candidate seed triangles based on
 175         // number of offshoot strips.  Precedence goes to orphans,
 176         // then corners, then edges, and interiors.
 177         memset( seedTriangles, 0xff, sizeof( seedTriangles ) );
 178         memset( seedLengths, 0xff, sizeof( seedLengths ) );
 179
 180         for ( i = 0; i < MAX_MATCHED_SIDES; i++ )
 181         {
 182                 // find the triangle with lowest number of child strips
 183                 for ( t = 0; t < numInputTris; t++ )
 184                 {
 185                         int orientation;
 186                         int n;
 187
 188                         if ( s_used[t] )
 189                                 continue;
 190
 191                         // try the candidate triangle in three different orientations
 192                         matchedSides = 0;
 193                         for ( orientation = 0; orientation < 3; orientation++ )
 194                         {
 195                                 if ( ( n = FindNextTriangleInStripOrFan( mesh, t, orientation, numInputTris, 1 ) ) != -1 )
 196                                 {
 197                                         matchedSides++;
 198                                 }
 199                         }
 200
 201                         if ( matchedSides == i )
 202                         {
 203                                 seedTriangles[i][numSeeds[i]] = t;
 204                                 numSeeds[i]++;
 205                                 if ( numSeeds[i] == MAX_SEED_TRIANGLES )
 206                                         break;
 207                         }
 208                 }
 209         }
 210
 211         // we have a list of potential seed triangles, so we now go through each
 212         // potential candidate and look to see which produces the longest strip
 213         // and select our startTri based on this
 214         for ( i = 0; i < MAX_MATCHED_SIDES; i++ )
 215         {
 216                 int j;
 217
 218                 for ( j = 0; j < numSeeds[i]; j++ )
 219                 {
 220                         for ( orientation = 0; orientation < 3; orientation++ )
 221                         {
 222                                 int k;
 223
 224                                 seedLengths[orientation][i][j] = StripLength( mesh, strip, seedTriangles[i][j], orientation, numInputTris, 2 );
 225
 226                                 if ( seedLengths[orientation][i][j] > bestLength )
 227                                 {
 228                                         bestTri = seedTriangles[i][j];
 229                                         bestLength = seedLengths[orientation][i][j];
 230                                         bestOrientation = orientation;
 231                                 }
 232
 233                                 for ( k = 0; k < numInputTris; k++ )
 234                                 {
 235                                         if ( s_used[k] == 2 )
 236                                                 s_used[k] = 0;
 237                                 }
 238                         }
 239                 }
 240
 241                 if ( bestTri != -1 )
 242                 {
 243                         break;
 244                 }
 245         }
 246
 247         // build the strip for real
 248         if ( bestTri != -1 )
 249         {
 250                 stripLen = StripLength( mesh, strip, bestTri, bestOrientation, numInputTris, 1 );
 251         }
 252
 253         return stripLen;
 254 }
 255
 256 /*
 257 ** OrderMesh
 258 **
 259 ** Given an input mesh and an output mesh, this routine will reorder
 260 ** the triangles within the mesh into strips/fans.
 261 */
 262 void OrderMesh( int input[][3], int output[][3], int numTris )
 263 {
 264         int i;
 265         int sumStrippedTriangles = 0;
 266         int strippedTriangles;
 267         int totalStrips = 0;
 268         int strip[8192][3];                                     // could dump directly into 'output', but
 269                                                                                 // this helps with debugging
 270
 271         memset( s_used, 0, sizeof( s_used ) );
 272
 273 #if 0
 274         FILE *fp = fopen( "strip.txt", "wt" );
 275
 276         for ( i = 0; i < numTris; i++ )
 277         {
 278                 fprintf( fp, "%4d: %3d %3d %3d\n", i, input[i][0], input[i][1], input[i][2] );
 279         }
 280         fclose( fp );
 281 #endif
 282
 283         // while there are still triangles that are not part of a strip
 284         while ( sumStrippedTriangles < numTris )
 285         {
 286                 // build a strip
 287                 strippedTriangles = BuildOptimizedList( input, strip, numTris );
 288
 289                 for ( i = 0; i < strippedTriangles; i++ )
 290                 {
 291                         output[sumStrippedTriangles+i][0] = strip[i][0];
 292                         output[sumStrippedTriangles+i][1] = strip[i][1];
 293                         output[sumStrippedTriangles+i][2] = strip[i][2];
 294                 }
 295
 296                 sumStrippedTriangles += strippedTriangles;
 297                 totalStrips++;
 298         }
 299
 300         printf( "Triangles on surface:          %d\n", sumStrippedTriangles );
 301         printf( "Total strips from surface: %d\n", totalStrips );
 302         printf( "Average strip length:      %f\n", ( float ) sumStrippedTriangles / totalStrips );
 303 }