tools/quake3/q3data/stripper.c

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