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