tools/quake3/q3data/stripper.c

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