2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
26 static int s_used[8192]; // same as MD3_MAX_TRIANGLES
29 ** FindNextTriangleInStrip
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.
35 static int FindNextTriangleInStripOrFan( int mesh[][3], int tri, int orientation, int numTris, int odd ){
43 currentTri[0] = mesh[tri][( 0 + orientation ) % 3];
44 currentTri[1] = mesh[tri][( 1 + orientation ) % 3];
45 currentTri[2] = mesh[tri][( 2 + orientation ) % 3];
57 // go through all triangles and look for sides that match
59 for ( t = 0; t < numTris; t++ )
61 // don't check against self or against previously used triangles
69 // check all three sides of the candidate triangle
70 for ( side = 0; side < 3; side++ )
72 // check only the second (abutting) side
73 if ( ( refa == mesh[t][( side + 1 ) % 3] ) &&
74 ( refb == mesh[t][side] ) ) {
80 // rotate the candidate triangle to align it properly in the strip
86 else if ( side == 2 ) {
97 Error( "fans not implemented yet" );
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 ) )
116 static int StripLength( int mesh[][3], int strip[][3], int tri, int orientation, int numInputTris, int fillNo ){
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;
130 while ( ( next = FindNextTriangleInStripOrFan( mesh, next, orientation, numInputTris, odd ) ) != -1 )
132 s_used[next] = fillNo;
134 strip[stripIndex][0] = mesh[next][0];
135 strip[stripIndex][1] = mesh[next][1];
136 strip[stripIndex][2] = mesh[next][2];
139 // all iterations after first need to be with an unrotated reference triangle
147 ** BuildOptimizedList
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.
153 #define MAX_ORIENTATIONS 3
154 #define MAX_MATCHED_SIDES 4
155 #define MAX_SEED_TRIANGLES 16
157 static int BuildOptimizedList( int mesh[][3], int strip[][3], int numInputTris ){
161 int bestTri = -1, bestLength = 0, bestOrientation = -1;
162 int matchedSides = 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 };
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 ) );
175 for ( i = 0; i < MAX_MATCHED_SIDES; i++ )
177 // find the triangle with lowest number of child strips
178 for ( t = 0; t < numInputTris; t++ )
187 // try the candidate triangle in three different orientations
189 for ( orientation = 0; orientation < 3; orientation++ )
191 if ( ( n = FindNextTriangleInStripOrFan( mesh, t, orientation, numInputTris, 1 ) ) != -1 ) {
196 if ( matchedSides == i ) {
197 seedTriangles[i][numSeeds[i]] = t;
199 if ( numSeeds[i] == MAX_SEED_TRIANGLES ) {
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++ )
213 for ( j = 0; j < numSeeds[i]; j++ )
215 for ( orientation = 0; orientation < 3; orientation++ )
219 seedLengths[orientation][i][j] = StripLength( mesh, strip, seedTriangles[i][j], orientation, numInputTris, 2 );
221 if ( seedLengths[orientation][i][j] > bestLength ) {
222 bestTri = seedTriangles[i][j];
223 bestLength = seedLengths[orientation][i][j];
224 bestOrientation = orientation;
227 for ( k = 0; k < numInputTris; k++ )
229 if ( s_used[k] == 2 ) {
236 if ( bestTri != -1 ) {
241 // build the strip for real
242 if ( bestTri != -1 ) {
243 stripLen = StripLength( mesh, strip, bestTri, bestOrientation, numInputTris, 1 );
252 ** Given an input mesh and an output mesh, this routine will reorder
253 ** the triangles within the mesh into strips/fans.
255 void OrderMesh( int input[][3], int output[][3], int numTris ){
257 int sumStrippedTriangles = 0;
258 int strippedTriangles;
260 int strip[8192][3]; // could dump directly into 'output', but
261 // this helps with debugging
263 memset( s_used, 0, sizeof( s_used ) );
266 FILE *fp = fopen( "strip.txt", "wt" );
268 for ( i = 0; i < numTris; i++ )
270 fprintf( fp, "%4d: %3d %3d %3d\n", i, input[i][0], input[i][1], input[i][2] );
275 // while there are still triangles that are not part of a strip
276 while ( sumStrippedTriangles < numTris )
279 strippedTriangles = BuildOptimizedList( input, strip, numTris );
281 for ( i = 0; i < strippedTriangles; i++ )
283 output[sumStrippedTriangles + i][0] = strip[i][0];
284 output[sumStrippedTriangles + i][1] = strip[i][1];
285 output[sumStrippedTriangles + i][2] = strip[i][2];
288 sumStrippedTriangles += strippedTriangles;
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 );