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