-#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
+#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 );
+}
projects / xonotic / netradiant.git / blobdiff