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