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