X-Git-Url: https://de.git.xonotic.org/?a=blobdiff_plain;f=misc%2Fsource%2Fnetradiant-src%2Ftools%2Fquake3%2Fq3data%2Fstripper.c;fp=misc%2Fsource%2Fnetradiant-src%2Ftools%2Fquake3%2Fq3data%2Fstripper.c;h=76fc96b3ed0a6de1327ba2936db3d6520f31eac5;hb=2376f1d3e3ea56046cca61d87cb8d648034e1a11;hp=0000000000000000000000000000000000000000;hpb=71c85af29fb024d5657f383c6e6f33720cd2c25e;p=voretournament%2Fvoretournament.git diff --git a/misc/source/netradiant-src/tools/quake3/q3data/stripper.c b/misc/source/netradiant-src/tools/quake3/q3data/stripper.c new file mode 100644 index 00000000..76fc96b3 --- /dev/null +++ b/misc/source/netradiant-src/tools/quake3/q3data/stripper.c @@ -0,0 +1,303 @@ +/* +Copyright (C) 1999-2006 Id Software, Inc. and contributors. +For a list of contributors, see the accompanying CONTRIBUTORS file. + +This file is part of GtkRadiant. + +GtkRadiant is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2 of the License, or +(at your option) any later version. + +GtkRadiant is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GtkRadiant; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA +*/ + +#include +#include +#include + +static int s_used[8192]; // same as MD3_MAX_TRIANGLES + +/* +** FindNextTriangleInStrip +** +** Given a surface and triangle this tries to find the next triangle +** in the strip that would continue the strip. The next triangle in +** the strip should have the same winding as this triangle. +*/ +static int FindNextTriangleInStripOrFan( int mesh[][3], int tri, int orientation, int numTris, int odd ) +{ + int t; + int sum = 0; + int currentTri[3]; + int side; + int a, b, c; + int refa, refb; + + currentTri[0] = mesh[tri][(0+orientation)%3]; + currentTri[1] = mesh[tri][(1+orientation)%3]; + currentTri[2] = mesh[tri][(2+orientation)%3]; + + if ( odd ) + { + refa = currentTri[1]; + refb = currentTri[2]; + } + else + { + refa = currentTri[2]; + refb = currentTri[0]; + } + + // go through all triangles and look for sides that match + // this triangle's + for ( t = 0; t < numTris; t++ ) + { + // don't check against self or against previously used triangles + if ( t == tri ) + continue; + if ( s_used[t] ) + continue; + + // check all three sides of the candidate triangle + for ( side = 0; side < 3; side++ ) + { + // check only the second (abutting) side + if ( ( refa == mesh[t][(side+1)%3] ) && + ( refb == mesh[t][side] ) ) + { + + a = mesh[t][0]; + b = mesh[t][1]; + c = mesh[t][2]; + + // rotate the candidate triangle to align it properly in the strip + if ( side == 1 ) + { + mesh[t][0] = b; + mesh[t][1] = c; + mesh[t][2] = a; + } + else if ( side == 2 ) + { + mesh[t][0] = c; + mesh[t][1] = a; + mesh[t][2] = b; + } + + return t; + } +/* + else + { + Error( "fans not implemented yet" ); + + // check only the third (abutting) side + if ( ( currentTri[2] == pSurf->baseTriangles[t].v[side].index ) && + ( currentTri[0] == pSurf->baseTriangles[t].v[(side+1)%3].index ) ) + { + return t; + } + } +*/ + } + } + + return -1; +} + +/* +** StripLength +*/ +static int StripLength( int mesh[][3], int strip[][3], int tri, int orientation, int numInputTris, int fillNo ) +{ + int stripIndex = 0; + int next; + + int odd = 1; + + strip[stripIndex][0] = mesh[tri][(0+orientation)%3]; + strip[stripIndex][1] = mesh[tri][(1+orientation)%3]; + strip[stripIndex][2] = mesh[tri][(2+orientation)%3]; + s_used[tri] = fillNo; + stripIndex++; + + next = tri; + + while ( ( next = FindNextTriangleInStripOrFan( mesh, next, orientation, numInputTris, odd ) ) != -1 ) + { + s_used[next] = fillNo; + odd = !odd; + strip[stripIndex][0] = mesh[next][0]; + strip[stripIndex][1] = mesh[next][1]; + strip[stripIndex][2] = mesh[next][2]; + stripIndex++; + + // all iterations after first need to be with an unrotated reference triangle + orientation = 0; + } + + return stripIndex; +} + +/* +** BuildOptimizedList +** +** Attempts to build the longest strip/fan possible. Does not adhere +** to pure strip or fan, will intermix between the two so long as some +** type of connectivity can be maintained. +*/ +#define MAX_ORIENTATIONS 3 +#define MAX_MATCHED_SIDES 4 +#define MAX_SEED_TRIANGLES 16 + +static int BuildOptimizedList( int mesh[][3], int strip[][3], int numInputTris ) +{ + int t; + int stripLen = 0; + int startTri = -1; + int bestTri = -1, bestLength = 0, bestOrientation = -1; + int matchedSides = 0; + int orientation = 0; + int seedTriangles[MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES]; + int seedLengths[MAX_ORIENTATIONS][MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES]; + int numSeeds[MAX_MATCHED_SIDES] = { 0, 0, 0 }; + int i; + + // build a ranked list of candidate seed triangles based on + // number of offshoot strips. Precedence goes to orphans, + // then corners, then edges, and interiors. + memset( seedTriangles, 0xff, sizeof( seedTriangles ) ); + memset( seedLengths, 0xff, sizeof( seedLengths ) ); + + for ( i = 0; i < MAX_MATCHED_SIDES; i++ ) + { + // find the triangle with lowest number of child strips + for ( t = 0; t < numInputTris; t++ ) + { + int orientation; + int n; + + if ( s_used[t] ) + continue; + + // try the candidate triangle in three different orientations + matchedSides = 0; + for ( orientation = 0; orientation < 3; orientation++ ) + { + if ( ( n = FindNextTriangleInStripOrFan( mesh, t, orientation, numInputTris, 1 ) ) != -1 ) + { + matchedSides++; + } + } + + if ( matchedSides == i ) + { + seedTriangles[i][numSeeds[i]] = t; + numSeeds[i]++; + if ( numSeeds[i] == MAX_SEED_TRIANGLES ) + break; + } + } + } + + // we have a list of potential seed triangles, so we now go through each + // potential candidate and look to see which produces the longest strip + // and select our startTri based on this + for ( i = 0; i < MAX_MATCHED_SIDES; i++ ) + { + int j; + + for ( j = 0; j < numSeeds[i]; j++ ) + { + for ( orientation = 0; orientation < 3; orientation++ ) + { + int k; + + seedLengths[orientation][i][j] = StripLength( mesh, strip, seedTriangles[i][j], orientation, numInputTris, 2 ); + + if ( seedLengths[orientation][i][j] > bestLength ) + { + bestTri = seedTriangles[i][j]; + bestLength = seedLengths[orientation][i][j]; + bestOrientation = orientation; + } + + for ( k = 0; k < numInputTris; k++ ) + { + if ( s_used[k] == 2 ) + s_used[k] = 0; + } + } + } + + if ( bestTri != -1 ) + { + break; + } + } + + // build the strip for real + if ( bestTri != -1 ) + { + stripLen = StripLength( mesh, strip, bestTri, bestOrientation, numInputTris, 1 ); + } + + return stripLen; +} + +/* +** OrderMesh +** +** Given an input mesh and an output mesh, this routine will reorder +** the triangles within the mesh into strips/fans. +*/ +void OrderMesh( int input[][3], int output[][3], int numTris ) +{ + int i; + int sumStrippedTriangles = 0; + int strippedTriangles; + int totalStrips = 0; + int strip[8192][3]; // could dump directly into 'output', but + // this helps with debugging + + memset( s_used, 0, sizeof( s_used ) ); + +#if 0 + FILE *fp = fopen( "strip.txt", "wt" ); + + for ( i = 0; i < numTris; i++ ) + { + fprintf( fp, "%4d: %3d %3d %3d\n", i, input[i][0], input[i][1], input[i][2] ); + } + fclose( fp ); +#endif + + // while there are still triangles that are not part of a strip + while ( sumStrippedTriangles < numTris ) + { + // build a strip + strippedTriangles = BuildOptimizedList( input, strip, numTris ); + + for ( i = 0; i < strippedTriangles; i++ ) + { + output[sumStrippedTriangles+i][0] = strip[i][0]; + output[sumStrippedTriangles+i][1] = strip[i][1]; + output[sumStrippedTriangles+i][2] = strip[i][2]; + } + + sumStrippedTriangles += strippedTriangles; + totalStrips++; + } + + printf( "Triangles on surface: %d\n", sumStrippedTriangles ); + printf( "Total strips from surface: %d\n", totalStrips ); + printf( "Average strip length: %f\n", ( float ) sumStrippedTriangles / totalStrips ); +}