1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
5 static int s_used;                // same as MD3_MAX_TRIANGLES
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[], int tri, int orientation, int numTris, int odd )
15 {
16         int t;
17         int sum = 0;
18         int currentTri;
19         int side;
20         int a, b, c;
21         int refa, refb;
23         currentTri = mesh[tri][(0+orientation)%3];
24         currentTri = mesh[tri][(1+orientation)%3];
25         currentTri = mesh[tri][(2+orientation)%3];
27         if ( odd )
28         {
29                 refa = currentTri;
30                 refb = currentTri;
31         }
32         else
33         {
34                 refa = currentTri;
35                 refb = currentTri;
36         }
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;
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                         {
56                                 a = mesh[t];
57                                 b = mesh[t];
58                                 c = mesh[t];
60                                 // rotate the candidate triangle to align it properly in the strip
61                                 if ( side == 1 )
62                                 {
63                                         mesh[t] = b;
64                                         mesh[t] = c;
65                                         mesh[t] = a;
66                                 }
67                                 else if ( side == 2 )
68                                 {
69                                         mesh[t] = c;
70                                         mesh[t] = a;
71                                         mesh[t] = b;
72                                 }
74                                 return t;
75                         }
76 /*
77                         else
78                         {
79                                 Error( "fans not implemented yet" );
81                                 // check only the third (abutting) side
82                                 if ( ( currentTri == pSurf->baseTriangles[t].v[side].index ) &&
83                                         ( currentTri == pSurf->baseTriangles[t].v[(side+1)%3].index ) )
84                                 {
85                                         return t;
86                                 }
87                         }
88 */
89                 }
90         }
92         return -1;
93 }
95 /*
96 ** StripLength
97 */
98 static int StripLength( int mesh[], int strip[], int tri, int orientation, int numInputTris, int fillNo )
99 {
100         int stripIndex = 0;
101         int next;
103         int odd = 1;
105         strip[stripIndex] = mesh[tri][(0+orientation)%3];
106         strip[stripIndex] = mesh[tri][(1+orientation)%3];
107         strip[stripIndex] = mesh[tri][(2+orientation)%3];
108         s_used[tri] = fillNo;
109         stripIndex++;
111         next = tri;
113         while ( ( next = FindNextTriangleInStripOrFan( mesh, next, orientation, numInputTris, odd ) ) != -1 )
114         {
115                 s_used[next] = fillNo;
116                 odd = !odd;
117                 strip[stripIndex] = mesh[next];
118                 strip[stripIndex] = mesh[next];
119                 strip[stripIndex] = mesh[next];
120                 stripIndex++;
122                 // all iterations after first need to be with an unrotated reference triangle
123                 orientation = 0;
124         }
126         return stripIndex;
127 }
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
140 static int BuildOptimizedList( int mesh[], int strip[], 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;
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 ) );
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;
167                         if ( s_used[t] )
168                                 continue;
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                         }
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         }
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;
197                 for ( j = 0; j < numSeeds[i]; j++ )
198                 {
199                         for ( orientation = 0; orientation < 3; orientation++ )
200                         {
201                                 int k;
203                                 seedLengths[orientation][i][j] = StripLength( mesh, strip, seedTriangles[i][j], orientation, numInputTris, 2 );
205                                 if ( seedLengths[orientation][i][j] > bestLength )
206                                 {
207                                         bestTri = seedTriangles[i][j];
208                                         bestLength = seedLengths[orientation][i][j];
209                                         bestOrientation = orientation;
210                                 }
212                                 for ( k = 0; k < numInputTris; k++ )
213                                 {
214                                         if ( s_used[k] == 2 )
215                                                 s_used[k] = 0;
216                                 }
217                         }
218                 }
220                 if ( bestTri != -1 )
221                 {
222                         break;
223                 }
224         }
226         // build the strip for real
227         if ( bestTri != -1 )
228         {
229                 stripLen = StripLength( mesh, strip, bestTri, bestOrientation, numInputTris, 1 );
230         }
232         return stripLen;
233 }
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[], int output[], int numTris )
242 {
243         int i;
244         int sumStrippedTriangles = 0;
245         int strippedTriangles;
246         int totalStrips = 0;
247         int strip;                                     // could dump directly into 'output', but
248                                                                                 // this helps with debugging
250         memset( s_used, 0, sizeof( s_used ) );
252 #if 0
253         FILE *fp = fopen( "strip.txt", "wt" );
255         for ( i = 0; i < numTris; i++ )
256         {
257                 fprintf( fp, "%4d: %3d %3d %3d\n", i, input[i], input[i], input[i] );
258         }
259         fclose( fp );
260 #endif
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 );
268                 for ( i = 0; i < strippedTriangles; i++ )
269                 {
270                         output[sumStrippedTriangles+i] = strip[i];
271                         output[sumStrippedTriangles+i] = strip[i];
272                         output[sumStrippedTriangles+i] = strip[i];
273                 }
275                 sumStrippedTriangles += strippedTriangles;
276                 totalStrips++;
277         }
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 }