8d4f3c36ffdc009bdab45be92fa8b5600bbfbe49
[xonotic/netradiant.git] / tools / quake3 / q3map2 / surface_meta.c
1 /* -------------------------------------------------------------------------------
2
3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
4    For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6    This file is part of GtkRadiant.
7
8    GtkRadiant is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12
13    GtkRadiant is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with GtkRadiant; if not, write to the Free Software
20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21
22    ----------------------------------------------------------------------------------
23
24    This code has been altered significantly from its original form, to support
25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
26
27    ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define SURFACE_META_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 #define LIGHTMAP_EXCEEDED   -1
42 #define S_EXCEEDED          -2
43 #define T_EXCEEDED          -3
44 #define ST_EXCEEDED         -4
45 #define UNSUITABLE_TRIANGLE -10
46 #define VERTS_EXCEEDED      -1000
47 #define INDEXES_EXCEEDED    -2000
48
49 #define GROW_META_VERTS     1024
50 #define GROW_META_TRIANGLES 1024
51
52 static int numMetaSurfaces, numPatchMetaSurfaces;
53
54 static int maxMetaVerts = 0;
55 static int numMetaVerts = 0;
56 static int firstSearchMetaVert = 0;
57 static bspDrawVert_t        *metaVerts = NULL;
58
59 static int maxMetaTriangles = 0;
60 static int numMetaTriangles = 0;
61 static metaTriangle_t       *metaTriangles = NULL;
62
63
64
65 /*
66    ClearMetaVertexes()
67    called before staring a new entity to clear out the triangle list
68  */
69
70 void ClearMetaTriangles( void ){
71         numMetaVerts = 0;
72         numMetaTriangles = 0;
73 }
74
75
76
77 /*
78    FindMetaVertex()
79    finds a matching metavertex in the global list, returning its index
80  */
81
82 static int FindMetaVertex( bspDrawVert_t *src ){
83         int i;
84         bspDrawVert_t   *v, *temp;
85
86
87         /* try to find an existing drawvert */
88         for ( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
89         {
90                 if ( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 ) {
91                         return i;
92                 }
93         }
94
95         /* enough space? */
96         if ( numMetaVerts >= maxMetaVerts ) {
97                 /* reallocate more room */
98                 maxMetaVerts += GROW_META_VERTS;
99                 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
100                 if ( metaVerts != NULL ) {
101                         memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
102                         free( metaVerts );
103                 }
104                 metaVerts = temp;
105         }
106
107         /* add the triangle */
108         memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
109         numMetaVerts++;
110
111         /* return the count */
112         return ( numMetaVerts - 1 );
113 }
114
115
116
117 /*
118    AddMetaTriangle()
119    adds a new meta triangle, allocating more memory if necessary
120  */
121
122 static int AddMetaTriangle( void ){
123         metaTriangle_t  *temp;
124
125
126         /* enough space? */
127         if ( numMetaTriangles >= maxMetaTriangles ) {
128                 /* reallocate more room */
129                 maxMetaTriangles += GROW_META_TRIANGLES;
130                 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
131                 if ( metaTriangles != NULL ) {
132                         memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
133                         free( metaTriangles );
134                 }
135                 metaTriangles = temp;
136         }
137
138         /* increment and return */
139         numMetaTriangles++;
140         return numMetaTriangles - 1;
141 }
142
143
144
145 /*
146    FindMetaTriangle()
147    finds a matching metatriangle in the global list,
148    otherwise adds it and returns the index to the metatriangle
149  */
150
151 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum ){
152         int triIndex;
153         vec3_t dir;
154
155
156
157         /* detect degenerate triangles fixme: do something proper here */
158         VectorSubtract( a->xyz, b->xyz, dir );
159         if ( VectorLength( dir ) < 0.125f ) {
160                 return -1;
161         }
162         VectorSubtract( b->xyz, c->xyz, dir );
163         if ( VectorLength( dir ) < 0.125f ) {
164                 return -1;
165         }
166         VectorSubtract( c->xyz, a->xyz, dir );
167         if ( VectorLength( dir ) < 0.125f ) {
168                 return -1;
169         }
170
171         /* find plane */
172         if ( planeNum >= 0 ) {
173                 /* because of precision issues with small triangles, try to use the specified plane */
174                 src->planeNum = planeNum;
175                 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
176                 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
177         }
178         else
179         {
180                 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
181                 src->planeNum = -1;
182                 if ( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse ) {
183                         return -1;
184                 }
185         }
186
187         /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
188         if ( VectorLength( a->normal ) <= 0.0f ) {
189                 VectorCopy( src->plane, a->normal );
190         }
191         if ( VectorLength( b->normal ) <= 0.0f ) {
192                 VectorCopy( src->plane, b->normal );
193         }
194         if ( VectorLength( c->normal ) <= 0.0f ) {
195                 VectorCopy( src->plane, c->normal );
196         }
197
198         /* ydnar 2002-10-04: set lightmap axis if not already set */
199         if ( !( src->si->compileFlags & C_VERTEXLIT ) &&
200                  src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f ) {
201                 /* the shader can specify an explicit lightmap axis */
202                 if ( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] ) {
203                         VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
204                 }
205
206                 /* new axis-finding code */
207                 else{
208                         CalcLightmapAxis( src->plane, src->lightmapAxis );
209                 }
210         }
211
212         /* fill out the src triangle */
213         src->indexes[ 0 ] = FindMetaVertex( a );
214         src->indexes[ 1 ] = FindMetaVertex( b );
215         src->indexes[ 2 ] = FindMetaVertex( c );
216
217         /* try to find an existing triangle */
218         #ifdef USE_EXHAUSTIVE_SEARCH
219         {
220                 int i;
221                 metaTriangle_t  *tri;
222
223
224                 for ( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
225                 {
226                         if ( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 ) {
227                                 return i;
228                         }
229                 }
230         }
231         #endif
232
233         /* get a new triangle */
234         triIndex = AddMetaTriangle();
235
236         /* add the triangle */
237         memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
238
239         /* return the triangle index */
240         return triIndex;
241 }
242
243
244
245 /*
246    SurfaceToMetaTriangles()
247    converts a classified surface to metatriangles
248  */
249
250 static void SurfaceToMetaTriangles( mapDrawSurface_t *ds ){
251         int i;
252         metaTriangle_t src;
253         bspDrawVert_t a, b, c;
254
255
256         /* only handle certain types of surfaces */
257         if ( ds->type != SURFACE_FACE &&
258                  ds->type != SURFACE_META &&
259                  ds->type != SURFACE_FORCED_META &&
260                  ds->type != SURFACE_DECAL ) {
261                 return;
262         }
263
264         /* speed at the expense of memory */
265         firstSearchMetaVert = numMetaVerts;
266
267         /* only handle valid surfaces */
268         if ( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 ) {
269                 /* walk the indexes and create triangles */
270                 for ( i = 0; i < ds->numIndexes; i += 3 )
271                 {
272                         /* sanity check the indexes */
273                         if ( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
274                                  ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
275                                  ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] ) {
276                                 //%     Sys_Printf( "%d! ", ds->numVerts );
277                                 continue;
278                         }
279
280                         /* build a metatriangle */
281                         src.si = ds->shaderInfo;
282                         src.side = ( ds->sideRef != NULL ? ds->sideRef->side : NULL );
283                         src.entityNum = ds->entityNum;
284                         src.surfaceNum = ds->surfaceNum;
285                         src.planeNum = ds->planeNum;
286                         src.castShadows = ds->castShadows;
287                         src.recvShadows = ds->recvShadows;
288                         src.fogNum = ds->fogNum;
289                         src.sampleSize = ds->sampleSize;
290                         src.shadeAngleDegrees = ds->shadeAngleDegrees;
291                         VectorCopy( ds->lightmapAxis, src.lightmapAxis );
292
293                         /* copy drawverts */
294                         memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
295                         memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
296                         memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
297                         FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
298                 }
299
300                 /* add to count */
301                 numMetaSurfaces++;
302         }
303
304         /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
305         ClearSurface( ds );
306 }
307
308
309
310 /*
311    TriangulatePatchSurface()
312    creates triangles from a patch
313  */
314
315 void TriangulatePatchSurface( entity_t *e, mapDrawSurface_t *ds ){
316         int iterations, x, y, pw[ 5 ], r;
317         mapDrawSurface_t    *dsNew;
318         mesh_t src, *subdivided, *mesh;
319         int forcePatchMeta;
320         int patchQuality;
321         int patchSubdivision;
322
323         /* vortex: _patchMeta, _patchQuality, _patchSubdivide support */
324         forcePatchMeta = IntForKey( e, "_patchMeta" );
325         if ( !forcePatchMeta ) {
326                 forcePatchMeta = IntForKey( e, "patchMeta" );
327         }
328         patchQuality = IntForKey( e, "_patchQuality" );
329         if ( !patchQuality ) {
330                 patchQuality = IntForKey( e, "patchQuality" );
331         }
332         if ( !patchQuality ) {
333                 patchQuality = 1.0;
334         }
335         patchSubdivision = IntForKey( e, "_patchSubdivide" );
336         if ( !patchSubdivision ) {
337                 patchSubdivision = IntForKey( e, "patchSubdivide" );
338         }
339
340         /* try to early out */
341         if ( ds->numVerts == 0 || ds->type != SURFACE_PATCH || ( patchMeta == qfalse && !forcePatchMeta ) ) {
342                 return;
343         }
344         /* make a mesh from the drawsurf */
345         src.width = ds->patchWidth;
346         src.height = ds->patchHeight;
347         src.verts = ds->verts;
348         //%     subdivided = SubdivideMesh( src, 8, 999 );
349         if ( patchSubdivision ) {
350                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivision );
351         }
352         else{
353                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions / patchQuality );
354         }
355
356         subdivided = SubdivideMesh2( src, iterations ); //%     ds->maxIterations
357
358         /* fit it to the curve and remove colinear verts on rows/columns */
359         PutMeshOnCurve( *subdivided );
360         mesh = RemoveLinearMeshColumnsRows( subdivided );
361         FreeMesh( subdivided );
362         //% MakeMeshNormals( mesh );
363
364         /* make a copy of the drawsurface */
365         dsNew = AllocDrawSurface( SURFACE_META );
366         memcpy( dsNew, ds, sizeof( *ds ) );
367
368         /* if the patch is nonsolid, then discard it */
369         if ( !( ds->shaderInfo->compileFlags & C_SOLID ) ) {
370                 ClearSurface( ds );
371         }
372
373         /* set new pointer */
374         ds = dsNew;
375
376         /* basic transmogrification */
377         ds->type = SURFACE_META;
378         ds->numIndexes = 0;
379         ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
380
381         /* copy the verts in */
382         ds->numVerts = ( mesh->width * mesh->height );
383         ds->verts = mesh->verts;
384
385         /* iterate through the mesh quads */
386         for ( y = 0; y < ( mesh->height - 1 ); y++ )
387         {
388                 for ( x = 0; x < ( mesh->width - 1 ); x++ )
389                 {
390                         /* set indexes */
391                         pw[ 0 ] = x + ( y * mesh->width );
392                         pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
393                         pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
394                         pw[ 3 ] = x + 1 + ( y * mesh->width );
395                         pw[ 4 ] = x + ( y * mesh->width );    /* same as pw[ 0 ] */
396
397                         /* set radix */
398                         r = ( x + y ) & 1;
399
400                         /* make first triangle */
401                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
402                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
403                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
404
405                         /* make second triangle */
406                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
407                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
408                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
409                 }
410         }
411
412         /* free the mesh, but not the verts */
413         free( mesh );
414
415         /* add to count */
416         numPatchMetaSurfaces++;
417
418         /* classify it */
419         ClassifySurfaces( 1, ds );
420 }
421
422 #define TINY_AREA 1.0f
423 #define MAXAREA_MAXTRIES 8
424 int MaxAreaIndexes( bspDrawVert_t *vert, int cnt, int *indexes ){
425         int r, s, t, bestR = 0, bestS = 1, bestT = 2;
426         int i, j, try;
427         double A, bestA = -1, V, bestV = -1;
428         vec3_t ab, ac, bc, cross;
429         bspDrawVert_t *buf;
430         double shiftWidth;
431
432         if ( cnt < 3 ) {
433                 return 0;
434         }
435
436         /* calculate total area */
437         A = 0;
438         for ( i = 1; i + 1 < cnt; ++i )
439         {
440                 VectorSubtract( vert[i].xyz, vert[0].xyz, ab );
441                 VectorSubtract( vert[i + 1].xyz, vert[0].xyz, ac );
442                 CrossProduct( ab, ac, cross );
443                 A += VectorLength( cross );
444         }
445         V = 0;
446         for ( i = 0; i < cnt; ++i )
447         {
448                 VectorSubtract( vert[( i + 1 ) % cnt].xyz, vert[i].xyz, ab );
449                 V += VectorLength( ab );
450         }
451
452         /* calculate shift width from the area sensibly, assuming the polygon
453          * fits about 25% of the screen in both dimensions
454          * we assume 1280x1024
455          * 1 pixel is then about sqrt(A) / (0.25 * screenwidth)
456          * 8 pixels are then about sqrt(A) /  (0.25 * 1280) * 8
457          * 8 pixels are then about sqrt(A) * 0.025
458          * */
459         shiftWidth = sqrt( A ) * 0.0125;
460         /*     3->1 6->2 12->3 ... */
461         if ( A - ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * shiftWidth * 2 < 0 ) {
462                 /* printf("Small triangle detected (area %f, circumference %f), adjusting shiftWidth from %f to ", A, V, shiftWidth); */
463                 shiftWidth = A / ( ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * 2 );
464                 /* printf("%f\n", shiftWidth); */
465         }
466
467         /* find the triangle with highest area */
468         for ( r = 0; r + 2 < cnt; ++r )
469                 for ( s = r + 1; s + 1 < cnt; ++s )
470                         for ( t = s + 1; t < cnt; ++t )
471                         {
472                                 VectorSubtract( vert[s].xyz, vert[r].xyz, ab );
473                                 VectorSubtract( vert[t].xyz, vert[r].xyz, ac );
474                                 VectorSubtract( vert[t].xyz, vert[s].xyz, bc );
475                                 CrossProduct( ab, ac, cross );
476                                 A = VectorLength( cross );
477
478                                 V = A - ( VectorLength( ab ) - VectorLength( ac ) - VectorLength( bc ) ) * shiftWidth;
479                                 /* value = A - circumference * shiftWidth, i.e. we back out by shiftWidth units from each side, to prevent too acute triangles */
480                                 /* this kind of simulates "number of shiftWidth*shiftWidth fragments in the triangle not touched by an edge" */
481
482                                 if ( bestA < 0 || V > bestV ) {
483                                         bestA = A;
484                                         bestV = V;
485                                         bestR = r;
486                                         bestS = s;
487                                         bestT = t;
488                                 }
489                         }
490
491         /*
492            if(bestV < 0)
493             printf("value was REALLY bad\n");
494          */
495
496         for ( try = 0; try < MAXAREA_MAXTRIES; ++try )
497         {
498                 if ( try ) {
499                         bestR = rand() % cnt;
500                         bestS = rand() % cnt;
501                         bestT = rand() % cnt;
502                         if ( bestR == bestS || bestR == bestT || bestS == bestT ) {
503                                 continue;
504                         }
505                         // bubblesort inline
506                         // abc acb bac bca cab cba
507                         if ( bestR > bestS ) {
508                                 j = bestR;
509                                 bestR = bestS;
510                                 bestS = j;
511                         }
512                         // abc acb abc bca acb bca
513                         if ( bestS > bestT ) {
514                                 j = bestS;
515                                 bestS = bestT;
516                                 bestT = j;
517                         }
518                         // abc abc abc bac abc bac
519                         if ( bestR > bestS ) {
520                                 j = bestR;
521                                 bestR = bestS;
522                                 bestS = j;
523                         }
524                         // abc abc abc abc abc abc
525
526                         VectorSubtract( vert[bestS].xyz, vert[bestR].xyz, ab );
527                         VectorSubtract( vert[bestT].xyz, vert[bestR].xyz, ac );
528                         CrossProduct( ab, ac, cross );
529                         bestA = VectorLength( cross );
530                 }
531
532                 if ( bestA < TINY_AREA ) {
533                         /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
534                         continue;
535                 }
536
537                 i = 0;
538                 indexes[i++] = bestR;
539                 indexes[i++] = bestS;
540                 indexes[i++] = bestT;
541                 /* uses 3 */
542
543                 /* identify the other fragments */
544
545                 /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
546                  * 1. bestR..bestS
547                  * 2. bestS..bestT
548                  * 3. bestT..bestR
549                  */
550
551                 j = MaxAreaIndexes( vert + bestR, bestS - bestR + 1, indexes + i );
552                 if ( j < 0 ) {
553                         continue;
554                 }
555                 j += i;
556                 for (; i < j; ++i )
557                         indexes[i] += bestR;
558                 /* uses 3*(bestS-bestR+1)-6 */
559                 j = MaxAreaIndexes( vert + bestS, bestT - bestS + 1, indexes + i );
560                 if ( j < 0 ) {
561                         continue;
562                 }
563                 j += i;
564                 for (; i < j; ++i )
565                         indexes[i] += bestS;
566                 /* uses 3*(bestT-bestS+1)-6 */
567
568                 /* can'bestT recurse this one directly... therefore, buffering */
569                 if ( cnt + bestR - bestT + 1 >= 3 ) {
570                         buf = safe_malloc( sizeof( *vert ) * ( cnt + bestR - bestT + 1 ) );
571                         memcpy( buf, vert + bestT, sizeof( *vert ) * ( cnt - bestT ) );
572                         memcpy( buf + ( cnt - bestT ), vert, sizeof( *vert ) * ( bestR + 1 ) );
573                         j = MaxAreaIndexes( buf, cnt + bestR - bestT + 1, indexes + i );
574                         if ( j < 0 ) {
575                                 free( buf );
576                                 continue;
577                         }
578                         j += i;
579                         for (; i < j; ++i )
580                                 indexes[i] = ( indexes[i] + bestT ) % cnt;
581                         /* uses 3*(cnt+bestR-bestT+1)-6 */
582                         free( buf );
583                 }
584
585                 /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
586                 return i;
587         }
588
589         return -1;
590 }
591
592 /*
593    MaxAreaFaceSurface() - divVerent
594    creates a triangle list using max area indexes
595  */
596
597 void MaxAreaFaceSurface( mapDrawSurface_t *ds ){
598         int n;
599         /* try to early out  */
600         if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
601                 return;
602         }
603
604         /* is this a simple triangle? */
605         if ( ds->numVerts == 3 ) {
606                 ds->numIndexes = 3;
607                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
608                 VectorSet( ds->indexes, 0, 1, 2 );
609                 numMaxAreaSurfaces++;
610                 return;
611         }
612
613         /* do it! */
614         ds->numIndexes = 3 * ds->numVerts - 6;
615         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
616         n = MaxAreaIndexes( ds->verts, ds->numVerts, ds->indexes );
617         if ( n < 0 ) {
618                 /* whatever we do, it's degenerate */
619                 free( ds->indexes );
620                 ds->numIndexes = 0;
621                 StripFaceSurface( ds );
622                 return;
623         }
624         ds->numIndexes = n;
625
626         /* add to count */
627         numMaxAreaSurfaces++;
628
629         /* classify it */
630         ClassifySurfaces( 1, ds );
631 }
632
633
634 /*
635    FanFaceSurface() - ydnar
636    creates a tri-fan from a brush face winding
637    loosely based on SurfaceAsTriFan()
638  */
639
640 void FanFaceSurface( mapDrawSurface_t *ds ){
641         int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
642         bspDrawVert_t   *verts, *centroid, *dv;
643         double iv;
644
645
646         /* try to early out */
647         if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
648                 return;
649         }
650
651         /* add a new vertex at the beginning of the surface */
652         verts = safe_malloc( ( ds->numVerts + 1 ) * sizeof( bspDrawVert_t ) );
653         memset( verts, 0, sizeof( bspDrawVert_t ) );
654         memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
655         free( ds->verts );
656         ds->verts = verts;
657
658         /* add up the drawverts to create a centroid */
659         centroid = &verts[ 0 ];
660         memset( color, 0,  4 * MAX_LIGHTMAPS * sizeof( int ) );
661         for ( i = 1, dv = &verts[ 1 ]; i < ( ds->numVerts + 1 ); i++, dv++ )
662         {
663                 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
664                 VectorAdd( centroid->normal, dv->normal, centroid->normal );
665                 for ( j = 0; j < 4; j++ )
666                 {
667                         for ( k = 0; k < MAX_LIGHTMAPS; k++ )
668                                 color[ k ][ j ] += dv->color[ k ][ j ];
669                         if ( j < 2 ) {
670                                 centroid->st[ j ] += dv->st[ j ];
671                                 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
672                                         centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
673                         }
674                 }
675         }
676
677         /* average the centroid */
678         iv = 1.0f / ds->numVerts;
679         VectorScale( centroid->xyz, iv, centroid->xyz );
680         if ( VectorNormalize( centroid->normal, centroid->normal ) <= 0 ) {
681                 VectorCopy( verts[ 1 ].normal, centroid->normal );
682         }
683         for ( j = 0; j < 4; j++ )
684         {
685                 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
686                 {
687                         color[ k ][ j ] /= ds->numVerts;
688                         centroid->color[ k ][ j ] = ( color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255 );
689                 }
690                 if ( j < 2 ) {
691                         centroid->st[ j ] *= iv;
692                         for ( k = 0; k < MAX_LIGHTMAPS; k++ )
693                                 centroid->lightmap[ k ][ j ] *= iv;
694                 }
695         }
696
697         /* add to vert count */
698         ds->numVerts++;
699
700         /* fill indexes in triangle fan order */
701         ds->numIndexes = 0;
702         ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
703         for ( i = 1; i < ds->numVerts; i++ )
704         {
705                 a = 0;
706                 b = i;
707                 c = ( i + 1 ) % ds->numVerts;
708                 c = c ? c : 1;
709                 ds->indexes[ ds->numIndexes++ ] = a;
710                 ds->indexes[ ds->numIndexes++ ] = b;
711                 ds->indexes[ ds->numIndexes++ ] = c;
712         }
713
714         /* add to count */
715         numFanSurfaces++;
716
717         /* classify it */
718         ClassifySurfaces( 1, ds );
719 }
720
721
722
723 /*
724    StripFaceSurface() - ydnar
725    attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
726    based on SurfaceAsTriStrip()
727  */
728
729 #define MAX_INDEXES     1024
730
731 void StripFaceSurface( mapDrawSurface_t *ds ){
732         int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
733         vec_t       *v1, *v2;
734
735
736         /* try to early out  */
737         if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
738                 return;
739         }
740
741         /* is this a simple triangle? */
742         if ( ds->numVerts == 3 ) {
743                 numIndexes = 3;
744                 VectorSet( indexes, 0, 1, 2 );
745         }
746         else
747         {
748                 /* ydnar: find smallest coordinate */
749                 least = 0;
750                 if ( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse ) {
751                         for ( i = 0; i < ds->numVerts; i++ )
752                         {
753                                 /* get points */
754                                 v1 = ds->verts[ i ].xyz;
755                                 v2 = ds->verts[ least ].xyz;
756
757                                 /* compare */
758                                 if ( v1[ 0 ] < v2[ 0 ] ||
759                                          ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ] ) ||
760                                          ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ] ) ) {
761                                         least = i;
762                                 }
763                         }
764                 }
765
766                 /* determine the triangle strip order */
767                 numIndexes = ( ds->numVerts - 2 ) * 3;
768                 if ( numIndexes > MAX_INDEXES ) {
769                         Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
770                 }
771
772                 /* try all possible orderings of the points looking for a non-degenerate strip order */
773                 ni = 0;
774                 for ( r = 0; r < ds->numVerts; r++ )
775                 {
776                         /* set rotation */
777                         rotate = ( r + least ) % ds->numVerts;
778
779                         /* walk the winding in both directions */
780                         for ( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
781                         {
782                                 /* make indexes */
783                                 a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts;
784                                 b = ( i + rotate ) % ds->numVerts;
785                                 c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
786
787                                 /* test this triangle */
788                                 if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
789                                         break;
790                                 }
791                                 indexes[ ni++ ] = a;
792                                 indexes[ ni++ ] = b;
793                                 indexes[ ni++ ] = c;
794
795                                 /* handle end case */
796                                 if ( i + 1 != ds->numVerts - 1 - i ) {
797                                         /* make indexes */
798                                         a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
799                                         b = ( i + rotate ) % ds->numVerts;
800                                         c = ( i + 1 + rotate ) % ds->numVerts;
801
802                                         /* test triangle */
803                                         if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
804                                                 break;
805                                         }
806                                         indexes[ ni++ ] = a;
807                                         indexes[ ni++ ] = b;
808                                         indexes[ ni++ ] = c;
809                                 }
810                         }
811
812                         /* valid strip? */
813                         if ( ni == numIndexes ) {
814                                 break;
815                         }
816                 }
817
818                 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
819                 if ( ni < numIndexes ) {
820                         FanFaceSurface( ds );
821                         return;
822                 }
823         }
824
825         /* copy strip triangle indexes */
826         ds->numIndexes = numIndexes;
827         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
828         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
829
830         /* add to count */
831         numStripSurfaces++;
832
833         /* classify it */
834         ClassifySurfaces( 1, ds );
835 }
836
837
838 /*
839    EmitMetaStatictics
840    vortex: prints meta statistics in general output
841  */
842
843 void EmitMetaStats(){
844         Sys_Printf( "--- EmitMetaStats ---\n" );
845         Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
846         Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
847         Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
848         Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
849         Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
850         Sys_Printf( "%9d meta verts\n", numMetaVerts );
851         Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
852 }
853
854 /*
855    MakeEntityMetaTriangles()
856    builds meta triangles from brush faces (tristrips and fans)
857  */
858
859 void MakeEntityMetaTriangles( entity_t *e ){
860         int i, f, fOld, start;
861         mapDrawSurface_t    *ds;
862
863
864         /* note it */
865         Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
866
867         /* init pacifier */
868         fOld = -1;
869         start = I_FloatTime();
870
871         /* walk the list of surfaces in the entity */
872         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
873         {
874                 /* print pacifier */
875                 f = 10 * ( i - e->firstDrawSurf ) / ( numMapDrawSurfs - e->firstDrawSurf );
876                 if ( f != fOld ) {
877                         fOld = f;
878                         Sys_FPrintf( SYS_VRB, "%d...", f );
879                 }
880
881                 /* get surface */
882                 ds = &mapDrawSurfs[ i ];
883                 if ( ds->numVerts <= 0 ) {
884                         continue;
885                 }
886
887                 /* ignore autosprite surfaces */
888                 if ( ds->shaderInfo->autosprite ) {
889                         continue;
890                 }
891
892                 /* meta this surface? */
893                 if ( meta == qfalse && ds->shaderInfo->forceMeta == qfalse ) {
894                         continue;
895                 }
896
897                 /* switch on type */
898                 switch ( ds->type )
899                 {
900                 case SURFACE_FACE:
901                 case SURFACE_DECAL:
902                         if ( maxAreaFaceSurface ) {
903                                 MaxAreaFaceSurface( ds );
904                         }
905                         else{
906                                 StripFaceSurface( ds );
907                         }
908                         SurfaceToMetaTriangles( ds );
909                         break;
910
911                 case SURFACE_PATCH:
912                         TriangulatePatchSurface( e, ds );
913                         break;
914
915                 case SURFACE_TRIANGLES:
916                         break;
917
918                 case SURFACE_FORCED_META:
919                 case SURFACE_META:
920                         SurfaceToMetaTriangles( ds );
921                         break;
922
923                 default:
924                         break;
925                 }
926         }
927
928         /* print time */
929         if ( ( numMapDrawSurfs - e->firstDrawSurf ) ) {
930                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
931         }
932
933         /* emit some stats */
934         Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
935         Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
936         Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
937         Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
938         Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
939         Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
940         Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
941
942         /* tidy things up */
943         TidyEntitySurfaces( e );
944 }
945
946
947
948 /*
949    CreateEdge()
950    sets up an edge structure from a plane and 2 points that the edge ab falls lies in
951  */
952
953 typedef struct edge_s
954 {
955         vec3_t origin, edge;
956         vec_t length, kingpinLength;
957         int kingpin;
958         vec4_t plane;
959 }
960 edge_t;
961
962 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge ){
963         /* copy edge origin */
964         VectorCopy( a, edge->origin );
965
966         /* create vector aligned with winding direction of edge */
967         VectorSubtract( b, a, edge->edge );
968
969         if ( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) ) {
970                 edge->kingpin = 0;
971         }
972         else if ( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) ) {
973                 edge->kingpin = 1;
974         }
975         else{
976                 edge->kingpin = 2;
977         }
978         edge->kingpinLength = edge->edge[ edge->kingpin ];
979
980         VectorNormalize( edge->edge, edge->edge );
981         edge->edge[ 3 ] = DotProduct( a, edge->edge );
982         edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
983
984         /* create perpendicular plane that edge lies in */
985         CrossProduct( plane, edge->edge, edge->plane );
986         edge->plane[ 3 ] = DotProduct( a, edge->plane );
987 }
988
989
990
991 /*
992    FixMetaTJunctions()
993    fixes t-junctions on meta triangles
994  */
995
996 #define TJ_PLANE_EPSILON    ( 1.0f / 8.0f )
997 #define TJ_EDGE_EPSILON     ( 1.0f / 8.0f )
998 #define TJ_POINT_EPSILON    ( 1.0f / 8.0f )
999
1000 void FixMetaTJunctions( void ){
1001         int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
1002         metaTriangle_t  *tri, *newTri;
1003         shaderInfo_t    *si;
1004         bspDrawVert_t   *a, *b, *c, junc;
1005         float dist, amount;
1006         vec3_t pt;
1007         vec4_t plane;
1008         edge_t edges[ 3 ];
1009
1010
1011         /* this code is crap; revisit later */
1012         return;
1013
1014         /* note it */
1015         Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
1016
1017         /* init pacifier */
1018         fOld = -1;
1019         start = I_FloatTime();
1020
1021         /* walk triangle list */
1022         numTJuncs = 0;
1023         for ( i = 0; i < numMetaTriangles; i++ )
1024         {
1025                 /* get triangle */
1026                 tri = &metaTriangles[ i ];
1027
1028                 /* print pacifier */
1029                 f = 10 * i / numMetaTriangles;
1030                 if ( f != fOld ) {
1031                         fOld = f;
1032                         Sys_FPrintf( SYS_VRB, "%d...", f );
1033                 }
1034
1035                 /* attempt to early out */
1036                 si = tri->si;
1037                 if ( ( si->compileFlags & C_NODRAW ) || si->autosprite || si->notjunc ) {
1038                         continue;
1039                 }
1040
1041                 /* calculate planes */
1042                 VectorCopy( tri->plane, plane );
1043                 plane[ 3 ] = tri->plane[ 3 ];
1044                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1045                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1046                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1047
1048                 /* walk meta vert list */
1049                 for ( j = 0; j < numMetaVerts; j++ )
1050                 {
1051                         /* get vert */
1052                         VectorCopy( metaVerts[ j ].xyz, pt );
1053
1054                         /* determine if point lies in the triangle's plane */
1055                         dist = DotProduct( pt, plane ) - plane[ 3 ];
1056                         if ( fabs( dist ) > TJ_PLANE_EPSILON ) {
1057                                 continue;
1058                         }
1059
1060                         /* skip this point if it already exists in the triangle */
1061                         for ( k = 0; k < 3; k++ )
1062                         {
1063                                 if ( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1064                                          fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1065                                          fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON ) {
1066                                         break;
1067                                 }
1068                         }
1069                         if ( k < 3 ) {
1070                                 continue;
1071                         }
1072
1073                         /* walk edges */
1074                         for ( k = 0; k < 3; k++ )
1075                         {
1076                                 /* ignore bogus edges */
1077                                 if ( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON ) {
1078                                         continue;
1079                                 }
1080
1081                                 /* determine if point lies on the edge */
1082                                 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1083                                 if ( fabs( dist ) > TJ_EDGE_EPSILON ) {
1084                                         continue;
1085                                 }
1086
1087                                 /* determine how far along the edge the point lies */
1088                                 amount = ( pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ] ) / edges[ k ].kingpinLength;
1089                                 if ( amount <= 0.0f || amount >= 1.0f ) {
1090                                         continue;
1091                                 }
1092
1093                                 #if 0
1094                                 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1095                                 if ( dist <= -0.0f || dist >= edges[ k ].length ) {
1096                                         continue;
1097                                 }
1098                                 amount = dist / edges[ k ].length;
1099                                 #endif
1100
1101                                 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1102                                 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1103                                 b = &metaVerts[ tri->indexes[ ( k + 1 ) % 3 ] ];
1104                                 c = &metaVerts[ tri->indexes[ ( k + 2 ) % 3 ] ];
1105
1106                                 /* make new vert */
1107                                 LerpDrawVertAmount( a, b, amount, &junc );
1108                                 VectorCopy( pt, junc.xyz );
1109
1110                                 /* compare against existing verts */
1111                                 if ( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) ) {
1112                                         continue;
1113                                 }
1114
1115                                 /* see if we can just re-use the existing vert */
1116                                 if ( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) ) {
1117                                         vertIndex = j;
1118                                 }
1119                                 else
1120                                 {
1121                                         /* find new vertex (note: a and b are invalid pointers after this) */
1122                                         firstSearchMetaVert = numMetaVerts;
1123                                         vertIndex = FindMetaVertex( &junc );
1124                                         if ( vertIndex < 0 ) {
1125                                                 continue;
1126                                         }
1127                                 }
1128
1129                                 /* make new triangle */
1130                                 triIndex = AddMetaTriangle();
1131                                 if ( triIndex < 0 ) {
1132                                         continue;
1133                                 }
1134
1135                                 /* get triangles */
1136                                 tri = &metaTriangles[ i ];
1137                                 newTri = &metaTriangles[ triIndex ];
1138
1139                                 /* copy the triangle */
1140                                 memcpy( newTri, tri, sizeof( *tri ) );
1141
1142                                 /* fix verts */
1143                                 tri->indexes[ ( k + 1 ) % 3 ] = vertIndex;
1144                                 newTri->indexes[ k ] = vertIndex;
1145
1146                                 /* recalculate edges */
1147                                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1148                                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1149                                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1150
1151                                 /* debug code */
1152                                 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1153                                 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1154                                 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1155
1156                                 /* add to counter and end processing of this vert */
1157                                 numTJuncs++;
1158                                 break;
1159                         }
1160                 }
1161         }
1162
1163         /* print time */
1164         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1165
1166         /* emit some stats */
1167         Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1168 }
1169
1170
1171
1172 /*
1173    SmoothMetaTriangles()
1174    averages coincident vertex normals in the meta triangles
1175  */
1176
1177 #define MAX_SAMPLES             256
1178 #define THETA_EPSILON           0.000001
1179 #define EQUAL_NORMAL_EPSILON    0.01
1180
1181 void SmoothMetaTriangles( void ){
1182         int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1183         float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1184         metaTriangle_t  *tri;
1185         float           *shadeAngles;
1186         byte            *smoothed;
1187         vec3_t average, diff;
1188         int indexes[ MAX_SAMPLES ];
1189         vec3_t votes[ MAX_SAMPLES ];
1190
1191         /* note it */
1192         Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1193
1194         /* allocate shade angle table */
1195         shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1196         memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1197
1198         /* allocate smoothed table */
1199         cs = ( numMetaVerts / 8 ) + 1;
1200         smoothed = safe_malloc( cs );
1201         memset( smoothed, 0, cs );
1202
1203         /* set default shade angle */
1204         defaultShadeAngle = DEG2RAD( npDegrees );
1205         maxShadeAngle = 0.0f;
1206
1207         /* run through every surface and flag verts belonging to non-lightmapped surfaces
1208            and set per-vertex smoothing angle */
1209         for ( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1210         {
1211                 shadeAngle = defaultShadeAngle;
1212
1213                 /* get shade angle from shader */
1214                 if ( tri->si->shadeAngleDegrees > 0.0f ) {
1215                         shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1216                 }
1217                 /* get shade angle from entity */
1218                 else if ( tri->shadeAngleDegrees > 0.0f ) {
1219                         shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1220                 }
1221
1222                 if ( shadeAngle <= 0.0f ) {
1223                         shadeAngle = defaultShadeAngle;
1224                 }
1225
1226                 if ( shadeAngle > maxShadeAngle ) {
1227                         maxShadeAngle = shadeAngle;
1228                 }
1229
1230                 /* flag its verts */
1231                 for ( j = 0; j < 3; j++ )
1232                 {
1233                         shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1234                         if ( shadeAngle <= 0 ) {
1235                                 smoothed[ tri->indexes[ j ] >> 3 ] |= ( 1 << ( tri->indexes[ j ] & 7 ) );
1236                         }
1237                 }
1238         }
1239
1240         /* bail if no surfaces have a shade angle */
1241         if ( maxShadeAngle <= 0 ) {
1242                 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1243                 free( shadeAngles );
1244                 free( smoothed );
1245                 return;
1246         }
1247
1248         /* init pacifier */
1249         fOld = -1;
1250         start = I_FloatTime();
1251
1252         /* go through the list of vertexes */
1253         numSmoothed = 0;
1254         for ( i = 0; i < numMetaVerts; i++ )
1255         {
1256                 /* print pacifier */
1257                 f = 10 * i / numMetaVerts;
1258                 if ( f != fOld ) {
1259                         fOld = f;
1260                         Sys_FPrintf( SYS_VRB, "%d...", f );
1261                 }
1262
1263                 /* already smoothed? */
1264                 if ( smoothed[ i >> 3 ] & ( 1 << ( i & 7 ) ) ) {
1265                         continue;
1266                 }
1267
1268                 /* clear */
1269                 VectorClear( average );
1270                 numVerts = 0;
1271                 numVotes = 0;
1272
1273                 /* build a table of coincident vertexes */
1274                 for ( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1275                 {
1276                         /* already smoothed? */
1277                         if ( smoothed[ j >> 3 ] & ( 1 << ( j & 7 ) ) ) {
1278                                 continue;
1279                         }
1280
1281                         /* test vertexes */
1282                         if ( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse ) {
1283                                 continue;
1284                         }
1285
1286                         /* use smallest shade angle */
1287                         shadeAngle = ( shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ] );
1288
1289                         /* check shade angle */
1290                         dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1291                         if ( dot > 1.0 ) {
1292                                 dot = 1.0;
1293                         }
1294                         else if ( dot < -1.0 ) {
1295                                 dot = -1.0;
1296                         }
1297                         testAngle = acos( dot ) + THETA_EPSILON;
1298                         if ( testAngle >= shadeAngle ) {
1299                                 continue;
1300                         }
1301
1302                         /* add to the list */
1303                         indexes[ numVerts++ ] = j;
1304
1305                         /* flag vertex */
1306                         smoothed[ j >> 3 ] |= ( 1 << ( j & 7 ) );
1307
1308                         /* see if this normal has already been voted */
1309                         for ( k = 0; k < numVotes; k++ )
1310                         {
1311                                 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1312                                 if ( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1313                                          fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1314                                          fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON ) {
1315                                         break;
1316                                 }
1317                         }
1318
1319                         /* add a new vote? */
1320                         if ( k == numVotes && numVotes < MAX_SAMPLES ) {
1321                                 VectorAdd( average, metaVerts[ j ].normal, average );
1322                                 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1323                                 numVotes++;
1324                         }
1325                 }
1326
1327                 /* don't average for less than 2 verts */
1328                 if ( numVerts < 2 ) {
1329                         continue;
1330                 }
1331
1332                 /* average normal */
1333                 if ( VectorNormalize( average, average ) > 0 ) {
1334                         /* smooth */
1335                         for ( j = 0; j < numVerts; j++ )
1336                                 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1337                         numSmoothed++;
1338                 }
1339         }
1340
1341         /* free the tables */
1342         free( shadeAngles );
1343         free( smoothed );
1344
1345         /* print time */
1346         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1347
1348         /* emit some stats */
1349         Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1350 }
1351
1352
1353
1354 /*
1355    AddMetaVertToSurface()
1356    adds a drawvert to a surface unless an existing vert matching already exists
1357    returns the index of that vert (or < 0 on failure)
1358  */
1359
1360 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident ){
1361         int i;
1362         bspDrawVert_t   *dv2;
1363
1364
1365         /* go through the verts and find a suitable candidate */
1366         for ( i = 0; i < ds->numVerts; i++ )
1367         {
1368                 /* get test vert */
1369                 dv2 = &ds->verts[ i ];
1370
1371                 /* compare xyz and normal */
1372                 if ( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse ) {
1373                         continue;
1374                 }
1375                 if ( VectorCompare( dv1->normal, dv2->normal ) == qfalse ) {
1376                         continue;
1377                 }
1378
1379                 /* good enough at this point */
1380                 ( *coincident )++;
1381
1382                 /* compare texture coordinates and color */
1383                 if ( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] ) {
1384                         continue;
1385                 }
1386                 if ( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] ) {
1387                         continue;
1388                 }
1389
1390                 /* found a winner */
1391                 numMergedVerts++;
1392                 return i;
1393         }
1394
1395         /* overflow check */
1396         if ( ds->numVerts >= ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) ? maxSurfaceVerts : maxLMSurfaceVerts ) ) {
1397                 return VERTS_EXCEEDED;
1398         }
1399
1400         /* made it this far, add the vert and return */
1401         dv2 = &ds->verts[ ds->numVerts++ ];
1402         *dv2 = *dv1;
1403         return ( ds->numVerts - 1 );
1404 }
1405
1406
1407
1408
1409 /*
1410    AddMetaTriangleToSurface()
1411    attempts to add a metatriangle to a surface
1412    returns the score of the triangle added
1413  */
1414
1415 #define AXIS_SCORE          100000
1416 #define AXIS_MIN            100000
1417 #define VERT_SCORE          10000
1418 #define SURFACE_SCORE           1000
1419 #define ST_SCORE            50
1420 #define ST_SCORE2           ( 2 * ( ST_SCORE ) )
1421
1422 #define DEFAULT_ADEQUATE_SCORE      ( (AXIS_MIN) +1 * ( VERT_SCORE ) )
1423 #define DEFAULT_GOOD_SCORE      ( (AXIS_MIN) +2 * (VERT_SCORE)                   +4 * ( ST_SCORE ) )
1424 #define         PERFECT_SCORE       ( (AXIS_MIN) +3 * ( VERT_SCORE ) + (SURFACE_SCORE) +4 * ( ST_SCORE ) )
1425
1426 #define ADEQUATE_SCORE          ( metaAdequateScore >= 0 ? metaAdequateScore : DEFAULT_ADEQUATE_SCORE )
1427 #define GOOD_SCORE          ( metaGoodScore     >= 0 ? metaGoodScore     : DEFAULT_GOOD_SCORE )
1428
1429 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd ){
1430         vec3_t p;
1431         int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1432         float lmMax;
1433         vec3_t mins, maxs;
1434         qboolean inTexRange;
1435         mapDrawSurface_t old;
1436
1437
1438         /* overflow check */
1439         if ( ds->numIndexes >= maxSurfaceIndexes ) {
1440                 return 0;
1441         }
1442
1443         /* test the triangle */
1444         if ( ds->entityNum != tri->entityNum ) { /* ydnar: added 2002-07-06 */
1445                 return 0;
1446         }
1447         if ( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows ) {
1448                 return 0;
1449         }
1450         if ( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize ) {
1451                 return 0;
1452         }
1453         #if 0
1454         if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1455              //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1456                  DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f ) {
1457                 return 0;
1458         }
1459         #endif
1460
1461         /* planar surfaces will only merge with triangles in the same plane */
1462         if ( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 ) {
1463                 if ( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] ) {
1464                         return 0;
1465                 }
1466                 if ( tri->planeNum >= 0 && tri->planeNum != ds->planeNum ) {
1467                         return 0;
1468                 }
1469         }
1470
1471
1472
1473         if ( metaMaxBBoxDistance >= 0 ) {
1474                 if ( ds->numIndexes > 0 ) {
1475                         VectorCopy( ds->mins, mins );
1476                         VectorCopy( ds->maxs, maxs );
1477                         mins[0] -= metaMaxBBoxDistance;
1478                         mins[1] -= metaMaxBBoxDistance;
1479                         mins[2] -= metaMaxBBoxDistance;
1480                         maxs[0] += metaMaxBBoxDistance;
1481                         maxs[1] += metaMaxBBoxDistance;
1482                         maxs[2] += metaMaxBBoxDistance;
1483 #define CHECK_1D( mins, v, maxs ) ( ( mins ) <= ( v ) && ( v ) <= ( maxs ) )
1484 #define CHECK_3D( mins, v, maxs ) ( CHECK_1D( ( mins )[0], ( v )[0], ( maxs )[0] ) && CHECK_1D( ( mins )[1], ( v )[1], ( maxs )[1] ) && CHECK_1D( ( mins )[2], ( v )[2], ( maxs )[2] ) )
1485                         VectorCopy( metaVerts[ tri->indexes[ 0 ] ].xyz, p );
1486                         if ( !CHECK_3D( mins, p, maxs ) ) {
1487                                 VectorCopy( metaVerts[ tri->indexes[ 1 ] ].xyz, p );
1488                                 if ( !CHECK_3D( mins, p, maxs ) ) {
1489                                         VectorCopy( metaVerts[ tri->indexes[ 2 ] ].xyz, p );
1490                                         if ( !CHECK_3D( mins, p, maxs ) ) {
1491                                                 return 0;
1492                                         }
1493                                 }
1494                         }
1495 #undef CHECK_3D
1496 #undef CHECK_1D
1497                 }
1498         }
1499
1500         /* set initial score */
1501         score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1502
1503         /* score the the dot product of lightmap axis to plane */
1504         if ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) ) {
1505                 score += AXIS_SCORE;
1506         }
1507         else{
1508                 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1509         }
1510
1511         /* preserve old drawsurface if this fails */
1512         memcpy( &old, ds, sizeof( *ds ) );
1513
1514         /* attempt to add the verts */
1515         coincident = 0;
1516         ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1517         bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1518         ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1519
1520         /* check vertex underflow */
1521         if ( ai < 0 || bi < 0 || ci < 0 ) {
1522                 memcpy( ds, &old, sizeof( *ds ) );
1523                 return 0;
1524         }
1525
1526         /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1527         score += ( coincident * VERT_SCORE );
1528
1529         /* add new vertex bounds to mins/maxs */
1530         VectorCopy( ds->mins, mins );
1531         VectorCopy( ds->maxs, maxs );
1532         AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1533         AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1534         AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1535
1536         /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1537         if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1538                  ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1539                  ( VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse ) ) {
1540                 /* set maximum size before lightmap scaling (normally 2032 units) */
1541                 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1542                 /* 2004-04-11: reverting to actual lightmap size */
1543                 lmMax = ( ds->sampleSize * ( ds->shaderInfo->lmCustomWidth - 1 ) );
1544                 for ( i = 0; i < 3; i++ )
1545                 {
1546                         if ( ( maxs[ i ] - mins[ i ] ) > lmMax ) {
1547                                 memcpy( ds, &old, sizeof( *ds ) );
1548                                 return 0;
1549                         }
1550                 }
1551         }
1552
1553         /* check texture range overflow */
1554         oldTexRange[ 0 ] = ds->texRange[ 0 ];
1555         oldTexRange[ 1 ] = ds->texRange[ 1 ];
1556         inTexRange = CalcSurfaceTextureRange( ds );
1557
1558         if ( inTexRange == qfalse && ds->numIndexes > 0 ) {
1559                 memcpy( ds, &old, sizeof( *ds ) );
1560                 return UNSUITABLE_TRIANGLE;
1561         }
1562
1563         /* score texture range */
1564         if ( ds->texRange[ 0 ] <= oldTexRange[ 0 ] ) {
1565                 score += ST_SCORE2;
1566         }
1567         else if ( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] ) {
1568                 score += ST_SCORE;
1569         }
1570
1571         if ( ds->texRange[ 1 ] <= oldTexRange[ 1 ] ) {
1572                 score += ST_SCORE2;
1573         }
1574         else if ( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] ) {
1575                 score += ST_SCORE;
1576         }
1577
1578
1579         /* go through the indexes and try to find an existing triangle that matches abc */
1580         for ( i = 0; i < ds->numIndexes; i += 3 )
1581         {
1582                 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1583                 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ] ) ||
1584                          ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ] ) ||
1585                          ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ] ) ) {
1586                         /* triangle already present */
1587                         memcpy( ds, &old, sizeof( *ds ) );
1588                         tri->si = NULL;
1589                         return 0;
1590                 }
1591
1592                 /* rotate the triangle 3x to find an inverse triangle (error case) */
1593                 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ] ) ||
1594                          ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ] ) ||
1595                          ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ] ) ) {
1596                         /* warn about it */
1597                         Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1598                                                 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1599                                                 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1600                                                 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1601
1602                         /* reverse triangle already present */
1603                         memcpy( ds, &old, sizeof( *ds ) );
1604                         tri->si = NULL;
1605                         return 0;
1606                 }
1607         }
1608
1609         /* add the triangle indexes */
1610         if ( ds->numIndexes < maxSurfaceIndexes ) {
1611                 ds->indexes[ ds->numIndexes++ ] = ai;
1612         }
1613         if ( ds->numIndexes < maxSurfaceIndexes ) {
1614                 ds->indexes[ ds->numIndexes++ ] = bi;
1615         }
1616         if ( ds->numIndexes < maxSurfaceIndexes ) {
1617                 ds->indexes[ ds->numIndexes++ ] = ci;
1618         }
1619
1620         /* check index overflow */
1621         if ( ds->numIndexes >= maxSurfaceIndexes  ) {
1622                 memcpy( ds, &old, sizeof( *ds ) );
1623                 return 0;
1624         }
1625
1626         /* sanity check the indexes */
1627         if ( ds->numIndexes >= 3 &&
1628                  ( ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1629                    ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1630                    ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ] ) ) {
1631                 Sys_Printf( "DEG:%d! ", ds->numVerts );
1632         }
1633
1634         /* testing only? */
1635         if ( testAdd ) {
1636                 memcpy( ds, &old, sizeof( *ds ) );
1637         }
1638         else
1639         {
1640                 /* copy bounds back to surface */
1641                 VectorCopy( mins, ds->mins );
1642                 VectorCopy( maxs, ds->maxs );
1643
1644                 /* mark triangle as used */
1645                 tri->si = NULL;
1646         }
1647
1648         /* add a side reference */
1649         ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1650
1651         /* return to sender */
1652         return score;
1653 }
1654
1655
1656
1657 /*
1658    MetaTrianglesToSurface()
1659    creates map drawsurface(s) from the list of possibles
1660  */
1661
1662 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded ){
1663         int i, j, f, best, score, bestScore;
1664         metaTriangle_t      *seed, *test;
1665         mapDrawSurface_t    *ds;
1666         bspDrawVert_t       *verts;
1667         int                 *indexes;
1668         qboolean added;
1669
1670
1671         /* allocate arrays */
1672         verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1673         indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1674
1675         /* walk the list of triangles */
1676         for ( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1677         {
1678                 /* skip this triangle if it has already been merged */
1679                 if ( seed->si == NULL ) {
1680                         continue;
1681                 }
1682
1683                 /* -----------------------------------------------------------------
1684                    initial drawsurf construction
1685                    ----------------------------------------------------------------- */
1686
1687                 /* start a new drawsurface */
1688                 ds = AllocDrawSurface( SURFACE_META );
1689                 ds->entityNum = seed->entityNum;
1690                 ds->surfaceNum = seed->surfaceNum;
1691                 ds->castShadows = seed->castShadows;
1692                 ds->recvShadows = seed->recvShadows;
1693
1694                 ds->shaderInfo = seed->si;
1695                 ds->planeNum = seed->planeNum;
1696                 ds->fogNum = seed->fogNum;
1697                 ds->sampleSize = seed->sampleSize;
1698                 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1699                 ds->verts = verts;
1700                 ds->indexes = indexes;
1701                 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1702                 ds->sideRef = AllocSideRef( seed->side, NULL );
1703
1704                 ClearBounds( ds->mins, ds->maxs );
1705
1706                 /* clear verts/indexes */
1707                 memset( verts, 0, sizeof( verts ) );
1708                 memset( indexes, 0, sizeof( indexes ) );
1709
1710                 /* add the first triangle */
1711                 if ( AddMetaTriangleToSurface( ds, seed, qfalse ) ) {
1712                         ( *numAdded )++;
1713                 }
1714
1715                 /* -----------------------------------------------------------------
1716                    add triangles
1717                    ----------------------------------------------------------------- */
1718
1719                 /* progressively walk the list until no more triangles can be added */
1720                 added = qtrue;
1721                 while ( added )
1722                 {
1723                         /* print pacifier */
1724                         f = 10 * *numAdded / numMetaTriangles;
1725                         if ( f > *fOld ) {
1726                                 *fOld = f;
1727                                 Sys_FPrintf( SYS_VRB, "%d...", f );
1728                         }
1729
1730                         /* reset best score */
1731                         best = -1;
1732                         bestScore = 0;
1733                         added = qfalse;
1734
1735                         /* walk the list of possible candidates for merging */
1736                         for ( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1737                         {
1738                                 /* skip this triangle if it has already been merged */
1739                                 if ( test->si == NULL ) {
1740                                         continue;
1741                                 }
1742
1743                                 /* score this triangle */
1744                                 score = AddMetaTriangleToSurface( ds, test, qtrue );
1745                                 if ( score > bestScore ) {
1746                                         best = j;
1747                                         bestScore = score;
1748
1749                                         /* if we have a score over a certain threshold, just use it */
1750                                         if ( bestScore >= GOOD_SCORE ) {
1751                                                 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1752                                                         ( *numAdded )++;
1753                                                 }
1754
1755                                                 /* reset */
1756                                                 best = -1;
1757                                                 bestScore = 0;
1758                                                 added = qtrue;
1759                                         }
1760                                 }
1761                         }
1762
1763                         /* add best candidate */
1764                         if ( best >= 0 && bestScore > ADEQUATE_SCORE ) {
1765                                 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1766                                         ( *numAdded )++;
1767                                 }
1768
1769                                 /* reset */
1770                                 added = qtrue;
1771                         }
1772                 }
1773
1774                 /* copy the verts and indexes to the new surface */
1775                 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1776                 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1777                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1778                 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1779
1780                 /* classify the surface */
1781                 ClassifySurfaces( 1, ds );
1782
1783                 /* add to count */
1784                 numMergedSurfaces++;
1785         }
1786
1787         /* free arrays */
1788         free( verts );
1789         free( indexes );
1790 }
1791
1792
1793
1794 /*
1795    CompareMetaTriangles()
1796    compare function for qsort()
1797  */
1798
1799 static int CompareMetaTriangles( const void *a, const void *b ){
1800         int i, j, av, bv;
1801         vec3_t aMins, bMins;
1802
1803
1804         /* shader first */
1805         if ( ( (const metaTriangle_t*) a )->si < ( (const metaTriangle_t*) b )->si ) {
1806                 return 1;
1807         }
1808         else if ( ( (const metaTriangle_t*) a )->si > ( (const metaTriangle_t*) b )->si ) {
1809                 return -1;
1810         }
1811
1812         /* then fog */
1813         else if ( ( (const metaTriangle_t*) a )->fogNum < ( (const metaTriangle_t*) b )->fogNum ) {
1814                 return 1;
1815         }
1816         else if ( ( (const metaTriangle_t*) a )->fogNum > ( (const metaTriangle_t*) b )->fogNum ) {
1817                 return -1;
1818         }
1819
1820         /* then plane */
1821         #if 0
1822         else if ( npDegrees == 0.0f && ( (const metaTriangle_t*) a )->si->nonplanar == qfalse &&
1823                           ( (const metaTriangle_t*) a )->planeNum >= 0 && ( (const metaTriangle_t*) a )->planeNum >= 0 ) {
1824                 if ( ( (const metaTriangle_t*) a )->plane[ 3 ] < ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1825                         return 1;
1826                 }
1827                 else if ( ( (const metaTriangle_t*) a )->plane[ 3 ] > ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1828                         return -1;
1829                 }
1830                 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] < ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1831                         return 1;
1832                 }
1833                 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] > ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1834                         return -1;
1835                 }
1836                 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] < ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1837                         return 1;
1838                 }
1839                 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] > ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1840                         return -1;
1841                 }
1842                 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] < ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1843                         return 1;
1844                 }
1845                 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] > ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1846                         return -1;
1847                 }
1848         }
1849         #endif
1850
1851         /* then position in world */
1852
1853         /* find mins */
1854         VectorSet( aMins, 999999, 999999, 999999 );
1855         VectorSet( bMins, 999999, 999999, 999999 );
1856         for ( i = 0; i < 3; i++ )
1857         {
1858                 av = ( (const metaTriangle_t*) a )->indexes[ i ];
1859                 bv = ( (const metaTriangle_t*) b )->indexes[ i ];
1860                 for ( j = 0; j < 3; j++ )
1861                 {
1862                         if ( metaVerts[ av ].xyz[ j ] < aMins[ j ] ) {
1863                                 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1864                         }
1865                         if ( metaVerts[ bv ].xyz[ j ] < bMins[ j ] ) {
1866                                 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1867                         }
1868                 }
1869         }
1870
1871         /* test it */
1872         for ( i = 0; i < 3; i++ )
1873         {
1874                 if ( aMins[ i ] < bMins[ i ] ) {
1875                         return 1;
1876                 }
1877                 else if ( aMins[ i ] > bMins[ i ] ) {
1878                         return -1;
1879                 }
1880         }
1881
1882         /* functionally equivalent */
1883         return 0;
1884 }
1885
1886
1887
1888 /*
1889    MergeMetaTriangles()
1890    merges meta triangles into drawsurfaces
1891  */
1892
1893 void MergeMetaTriangles( void ){
1894         int i, j, fOld, start, numAdded;
1895         metaTriangle_t      *head, *end;
1896
1897
1898         /* only do this if there are meta triangles */
1899         if ( numMetaTriangles <= 0 ) {
1900                 return;
1901         }
1902
1903         /* note it */
1904         Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1905
1906         /* sort the triangles by shader major, fognum minor */
1907         qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1908
1909         /* init pacifier */
1910         fOld = -1;
1911         start = I_FloatTime();
1912         numAdded = 0;
1913
1914         /* merge */
1915         for ( i = 0, j = 0; i < numMetaTriangles; i = j )
1916         {
1917                 /* get head of list */
1918                 head = &metaTriangles[ i ];
1919
1920                 /* skip this triangle if it has already been merged */
1921                 if ( head->si == NULL ) {
1922                         continue;
1923                 }
1924
1925                 /* find end */
1926                 if ( j <= i ) {
1927                         for ( j = i + 1; j < numMetaTriangles; j++ )
1928                         {
1929                                 /* get end of list */
1930                                 end = &metaTriangles[ j ];
1931                                 if ( head->si != end->si || head->fogNum != end->fogNum ) {
1932                                         break;
1933                                 }
1934                         }
1935                 }
1936
1937                 /* try to merge this list of possible merge candidates */
1938                 MetaTrianglesToSurface( ( j - i ), head, &fOld, &numAdded );
1939         }
1940
1941         /* clear meta triangle list */
1942         ClearMetaTriangles();
1943
1944         /* print time */
1945         if ( i ) {
1946                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1947         }
1948
1949         /* emit some stats */
1950         Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1951         Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
1952 }