tools/quake3/q3data/stripper.c

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