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