reduce more diff noise
[xonotic/netradiant.git] / tools / quake3 / q3data / stripper.c
index 8229aba..a7a5137 100644 (file)
-#include <stdio.h>\r
-#include <string.h>\r
-#include <stdlib.h>\r
-\r
-static int s_used[8192];               // same as MD3_MAX_TRIANGLES\r
-\r
-/*\r
-** FindNextTriangleInStrip\r
-**\r
-** Given a surface and triangle this tries to find the next triangle \r
-** in the strip that would continue the strip.  The next triangle in\r
-** the strip should have the same winding as this triangle.\r
-*/\r
-static int FindNextTriangleInStripOrFan( int mesh[][3], int tri, int orientation, int numTris, int odd )\r
-{\r
-       int t;\r
-       int sum = 0;\r
-       int currentTri[3];\r
-       int side;\r
-       int a, b, c;\r
-       int refa, refb;\r
-\r
-       currentTri[0] = mesh[tri][(0+orientation)%3];\r
-       currentTri[1] = mesh[tri][(1+orientation)%3];\r
-       currentTri[2] = mesh[tri][(2+orientation)%3];\r
-\r
-       if ( odd )\r
-       {\r
-               refa = currentTri[1];\r
-               refb = currentTri[2];\r
-       }\r
-       else\r
-       {\r
-               refa = currentTri[2];\r
-               refb = currentTri[0];\r
-       }\r
-\r
-       // go through all triangles and look for sides that match\r
-       // this triangle's\r
-       for ( t = 0; t < numTris; t++ )\r
-       {\r
-               // don't check against self or against previously used triangles\r
-               if ( t == tri )\r
-                       continue;\r
-               if ( s_used[t] )\r
-                       continue;\r
-\r
-               // check all three sides of the candidate triangle\r
-               for ( side = 0; side < 3; side++ )\r
-               {\r
-                       // check only the second (abutting) side\r
-                       if ( ( refa == mesh[t][(side+1)%3] ) &&\r
-                                ( refb == mesh[t][side] ) )\r
-                       {\r
-\r
-                               a = mesh[t][0];\r
-                               b = mesh[t][1];\r
-                               c = mesh[t][2];\r
-\r
-                               // rotate the candidate triangle to align it properly in the strip\r
-                               if ( side == 1 )\r
-                               {\r
-                                       mesh[t][0] = b;\r
-                                       mesh[t][1] = c;\r
-                                       mesh[t][2] = a;\r
-                               }\r
-                               else if ( side == 2 )\r
-                               {\r
-                                       mesh[t][0] = c;\r
-                                       mesh[t][1] = a;\r
-                                       mesh[t][2] = b;\r
-                               }\r
-\r
-                               return t;\r
-                       }\r
-/*\r
-                       else\r
-                       {\r
-                               Error( "fans not implemented yet" );\r
-\r
-                               // check only the third (abutting) side\r
-                               if ( ( currentTri[2] == pSurf->baseTriangles[t].v[side].index ) &&\r
-                                       ( currentTri[0] == pSurf->baseTriangles[t].v[(side+1)%3].index ) )\r
-                               {\r
-                                       return t;\r
-                               }\r
-                       }\r
-*/\r
-               }\r
-       }\r
-\r
-       return -1;\r
-}\r
-\r
-/*\r
-** StripLength\r
-*/\r
-static int StripLength( int mesh[][3], int strip[][3], int tri, int orientation, int numInputTris, int fillNo )\r
-{\r
-       int stripIndex = 0;\r
-       int next;\r
-\r
-       int odd = 1;\r
-\r
-       strip[stripIndex][0] = mesh[tri][(0+orientation)%3];\r
-       strip[stripIndex][1] = mesh[tri][(1+orientation)%3];\r
-       strip[stripIndex][2] = mesh[tri][(2+orientation)%3];\r
-       s_used[tri] = fillNo;\r
-       stripIndex++;\r
-\r
-       next = tri;\r
-\r
-       while ( ( next = FindNextTriangleInStripOrFan( mesh, next, orientation, numInputTris, odd ) ) != -1 )\r
-       {\r
-               s_used[next] = fillNo;\r
-               odd = !odd;\r
-               strip[stripIndex][0] = mesh[next][0];\r
-               strip[stripIndex][1] = mesh[next][1];\r
-               strip[stripIndex][2] = mesh[next][2];\r
-               stripIndex++;\r
-\r
-               // all iterations after first need to be with an unrotated reference triangle\r
-               orientation = 0;\r
-       }\r
-\r
-       return stripIndex;\r
-}\r
-\r
-/*\r
-** BuildOptimizedList\r
-**\r
-** Attempts to build the longest strip/fan possible.  Does not adhere\r
-** to pure strip or fan, will intermix between the two so long as some\r
-** type of connectivity can be maintained.\r
-*/\r
-#define MAX_ORIENTATIONS               3\r
-#define MAX_MATCHED_SIDES              4\r
-#define MAX_SEED_TRIANGLES             16\r
-\r
-static int BuildOptimizedList( int mesh[][3], int strip[][3], int numInputTris )\r
-{\r
-       int t;\r
-       int stripLen = 0;\r
-       int startTri = -1;\r
-       int bestTri = -1, bestLength = 0, bestOrientation = -1;\r
-       int matchedSides = 0;\r
-       int orientation = 0;\r
-       int seedTriangles[MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES];\r
-       int seedLengths[MAX_ORIENTATIONS][MAX_MATCHED_SIDES][MAX_SEED_TRIANGLES];\r
-       int numSeeds[MAX_MATCHED_SIDES] = { 0, 0, 0 };\r
-       int i;\r
-\r
-       // build a ranked list of candidate seed triangles based on \r
-       // number of offshoot strips.  Precedence goes to orphans,\r
-       // then corners, then edges, and interiors.\r
-       memset( seedTriangles, 0xff, sizeof( seedTriangles ) );\r
-       memset( seedLengths, 0xff, sizeof( seedLengths ) );\r
-\r
-       for ( i = 0; i < MAX_MATCHED_SIDES; i++ )\r
-       {\r
-               // find the triangle with lowest number of child strips\r
-               for ( t = 0; t < numInputTris; t++ )\r
-               {\r
-                       int orientation;\r
-                       int n;\r
-\r
-                       if ( s_used[t] )\r
-                               continue;\r
-\r
-                       // try the candidate triangle in three different orientations\r
-                       matchedSides = 0;\r
-                       for ( orientation = 0; orientation < 3; orientation++ )\r
-                       {\r
-                               if ( ( n = FindNextTriangleInStripOrFan( mesh, t, orientation, numInputTris, 1 ) ) != -1 )\r
-                               {\r
-                                       matchedSides++;\r
-                               }\r
-                       }\r
-\r
-                       if ( matchedSides == i )\r
-                       {\r
-                               seedTriangles[i][numSeeds[i]] = t;\r
-                               numSeeds[i]++;\r
-                               if ( numSeeds[i] == MAX_SEED_TRIANGLES )\r
-                                       break;\r
-                       }\r
-               }\r
-       }\r
-\r
-       // we have a list of potential seed triangles, so we now go through each \r
-       // potential candidate and look to see which produces the longest strip\r
-       // and select our startTri based on this\r
-       for ( i = 0; i < MAX_MATCHED_SIDES; i++ )\r
-       {\r
-               int j;\r
-\r
-               for ( j = 0; j < numSeeds[i]; j++ )\r
-               {\r
-                       for ( orientation = 0; orientation < 3; orientation++ )\r
-                       {\r
-                               int k;\r
-\r
-                               seedLengths[orientation][i][j] = StripLength( mesh, strip, seedTriangles[i][j], orientation, numInputTris, 2 );\r
-\r
-                               if ( seedLengths[orientation][i][j] > bestLength )\r
-                               {\r
-                                       bestTri = seedTriangles[i][j];\r
-                                       bestLength = seedLengths[orientation][i][j];\r
-                                       bestOrientation = orientation;\r
-                               }\r
-\r
-                               for ( k = 0; k < numInputTris; k++ )\r
-                               {\r
-                                       if ( s_used[k] == 2 )\r
-                                               s_used[k] = 0;\r
-                               }\r
-                       }\r
-               }\r
-\r
-               if ( bestTri != -1 )\r
-               {\r
-                       break;\r
-               }\r
-       }\r
-\r
-       // build the strip for real\r
-       if ( bestTri != -1 )\r
-       {\r
-               stripLen = StripLength( mesh, strip, bestTri, bestOrientation, numInputTris, 1 );\r
-       }\r
-\r
-       return stripLen;\r
-}\r
-\r
-/*\r
-** OrderMesh\r
-**\r
-** Given an input mesh and an output mesh, this routine will reorder \r
-** the triangles within the mesh into strips/fans.\r
-*/\r
-void OrderMesh( int input[][3], int output[][3], int numTris )\r
-{\r
-       int i;\r
-       int sumStrippedTriangles = 0;\r
-       int strippedTriangles;\r
-       int totalStrips = 0;\r
-       int strip[8192][3];                                     // could dump directly into 'output', but \r
-                                                                               // this helps with debugging\r
-\r
-       memset( s_used, 0, sizeof( s_used ) );\r
-\r
-#if 0\r
-       FILE *fp = fopen( "strip.txt", "wt" );\r
-\r
-       for ( i = 0; i < numTris; i++ )\r
-       {\r
-               fprintf( fp, "%4d: %3d %3d %3d\n", i, input[i][0], input[i][1], input[i][2] );\r
-       }\r
-       fclose( fp );\r
-#endif\r
-\r
-       // while there are still triangles that are not part of a strip\r
-       while ( sumStrippedTriangles < numTris )\r
-       {\r
-               // build a strip\r
-               strippedTriangles = BuildOptimizedList( input, strip, numTris );\r
-\r
-               for ( i = 0; i < strippedTriangles; i++ )\r
-               {\r
-                       output[sumStrippedTriangles+i][0] = strip[i][0];\r
-                       output[sumStrippedTriangles+i][1] = strip[i][1];\r
-                       output[sumStrippedTriangles+i][2] = strip[i][2];\r
-               }\r
-\r
-               sumStrippedTriangles += strippedTriangles;\r
-               totalStrips++;\r
-       }\r
-\r
-       printf( "Triangles on surface:          %d\n", sumStrippedTriangles );\r
-       printf( "Total strips from surface: %d\n", totalStrips );\r
-       printf( "Average strip length:      %f\n", ( float ) sumStrippedTriangles / totalStrips );\r
-}\r
+/*
+   Copyright (C) 1999-2007 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 <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+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 );
+}