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                 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                                 indexes[ ni++ ] = a;
 791                                 indexes[ ni++ ] = b;
 792                                 indexes[ ni++ ] = c;
 793
 794                                 /* handle end case */
 795                                 if( i + 1 != ds->numVerts - 1 - i )
 796                                 {
 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                                         indexes[ ni++ ] = a;
 806                                         indexes[ ni++ ] = b;
 807                                         indexes[ ni++ ] = c;
 808                                 }
 809                         }
 810
 811                         /* valid strip? */
 812                         if( ni == numIndexes )
 813                                 break;
 814                 }
 815
 816                 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
 817                 if( ni < numIndexes )
 818                 {
 819                         FanFaceSurface( ds );
 820                         return;
 821                 }
 822         }
 823
 824         /* copy strip triangle indexes */
 825         ds->numIndexes = numIndexes;
 826         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
 827         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
 828
 829         /* add to count */
 830         numStripSurfaces++;
 831
 832         /* classify it */
 833         ClassifySurfaces( 1, ds );
 834 }
 835
 836
 837 /*
 838 EmitMetaStatictics
 839 vortex: prints meta statistics in general output
 840 */
 841
 842 void EmitMetaStats()
 843 {
 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 {
 861         int                                     i, f, fOld, start;
 862         mapDrawSurface_t        *ds;
 863
 864
 865         /* note it */
 866         Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
 867
 868         /* init pacifier */
 869         fOld = -1;
 870         start = I_FloatTime();
 871
 872         /* walk the list of surfaces in the entity */
 873         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
 874         {
 875                 /* print pacifier */
 876                 f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
 877                 if( f != fOld )
 878                 {
 879                         fOld = f;
 880                         Sys_FPrintf( SYS_VRB, "%d...", f );
 881                 }
 882
 883                 /* get surface */
 884                 ds = &mapDrawSurfs[ i ];
 885                 if( ds->numVerts <= 0 )
 886                         continue;
 887
 888                 /* ignore autosprite surfaces */
 889                 if( ds->shaderInfo->autosprite )
 890                         continue;
 891
 892                 /* meta this surface? */
 893                 if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
 894                         continue;
 895
 896                 /* switch on type */
 897                 switch( ds->type )
 898                 {
 899                         case SURFACE_FACE:
 900                         case SURFACE_DECAL:
 901                                 if(maxAreaFaceSurface)
 902                                         MaxAreaFaceSurface( ds );
 903                                 else
 904                                         StripFaceSurface( ds );
 905                                 SurfaceToMetaTriangles( ds );
 906                                 break;
 907
 908                         case SURFACE_PATCH:
 909                                 TriangulatePatchSurface(e, ds );
 910                                 break;
 911
 912                         case SURFACE_TRIANGLES:
 913                                 break;
 914
 915                         case SURFACE_FORCED_META:
 916                         case SURFACE_META:
 917                                 SurfaceToMetaTriangles( ds );
 918                                 break;
 919
 920                         default:
 921                                 break;
 922                 }
 923         }
 924
 925         /* print time */
 926         if( (numMapDrawSurfs - e->firstDrawSurf) )
 927                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
 928
 929         /* emit some stats */
 930         Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
 931         Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
 932         Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
 933         Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
 934         Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
 935         Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
 936         Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
 937
 938         /* tidy things up */
 939         TidyEntitySurfaces( e );
 940 }
 941
 942
 943
 944 /*
 945 PointTriangleIntersect()
 946 assuming that all points lie in plane, determine if pt
 947 is inside the triangle abc
 948 code originally (c) 2001 softSurfer (www.softsurfer.com)
 949 */
 950
 951 #define MIN_OUTSIDE_EPSILON             -0.01f
 952 #define MAX_OUTSIDE_EPSILON             1.01f
 953
 954 static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
 955 {
 956         vec3_t  u, v, w;
 957         float   uu, uv, vv, wu, wv, d;
 958
 959
 960         /* make vectors */
 961         VectorSubtract( b, a, u );
 962         VectorSubtract( c, a, v );
 963         VectorSubtract( pt, a, w );
 964
 965         /* more setup */
 966         uu = DotProduct( u, u );
 967         uv = DotProduct( u, v );
 968         vv = DotProduct( v, v );
 969         wu = DotProduct( w, u );
 970         wv = DotProduct( w, v );
 971         d = uv * uv - uu * vv;
 972
 973         /* calculate barycentric coordinates */
 974         bary[ 1 ] = (uv * wv - vv * wu) / d;
 975         if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
 976                 return qfalse;
 977         bary[ 2 ] = (uv * wv - uu * wv) / d;
 978         if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
 979                 return qfalse;
 980         bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
 981
 982         /* point is in triangle */
 983         return qtrue;
 984 }
 985
 986
 987
 988 /*
 989 CreateEdge()
 990 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
 991 */
 992
 993 typedef struct edge_s
 994 {
 995         vec3_t  origin, edge;
 996         vec_t   length, kingpinLength;
 997         int             kingpin;
 998         vec4_t  plane;
 999 }
1000 edge_t;
1001
1002 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
1003 {
1004         /* copy edge origin */
1005         VectorCopy( a, edge->origin );
1006
1007         /* create vector aligned with winding direction of edge */
1008         VectorSubtract( b, a, edge->edge );
1009
1010         if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
1011                 edge->kingpin = 0;
1012         else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
1013                 edge->kingpin = 1;
1014         else
1015                 edge->kingpin = 2;
1016         edge->kingpinLength = edge->edge[ edge->kingpin ];
1017
1018         VectorNormalize( edge->edge, edge->edge );
1019         edge->edge[ 3 ] = DotProduct( a, edge->edge );
1020         edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
1021
1022         /* create perpendicular plane that edge lies in */
1023         CrossProduct( plane, edge->edge, edge->plane );
1024         edge->plane[ 3 ] = DotProduct( a, edge->plane );
1025 }
1026
1027
1028
1029 /*
1030 FixMetaTJunctions()
1031 fixes t-junctions on meta triangles
1032 */
1033
1034 #define TJ_PLANE_EPSILON        (1.0f / 8.0f)
1035 #define TJ_EDGE_EPSILON         (1.0f / 8.0f)
1036 #define TJ_POINT_EPSILON        (1.0f / 8.0f)
1037
1038 void FixMetaTJunctions( void )
1039 {
1040         int                             i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
1041         metaTriangle_t  *tri, *newTri;
1042         shaderInfo_t    *si;
1043         bspDrawVert_t   *a, *b, *c, junc;
1044         float                   dist, amount;
1045         vec3_t                  pt;
1046         vec4_t                  plane;
1047         edge_t                  edges[ 3 ];
1048
1049
1050         /* this code is crap; revisit later */
1051         return;
1052
1053         /* note it */
1054         Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
1055
1056         /* init pacifier */
1057         fOld = -1;
1058         start = I_FloatTime();
1059
1060         /* walk triangle list */
1061         numTJuncs = 0;
1062         for( i = 0; i < numMetaTriangles; i++ )
1063         {
1064                 /* get triangle */
1065                 tri = &metaTriangles[ i ];
1066
1067                 /* print pacifier */
1068                 f = 10 * i / numMetaTriangles;
1069                 if( f != fOld )
1070                 {
1071                         fOld = f;
1072                         Sys_FPrintf( SYS_VRB, "%d...", f );
1073                 }
1074
1075                 /* attempt to early out */
1076                 si = tri->si;
1077                 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
1078                         continue;
1079
1080                 /* calculate planes */
1081                 VectorCopy( tri->plane, plane );
1082                 plane[ 3 ] = tri->plane[ 3 ];
1083                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1084                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1085                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1086
1087                 /* walk meta vert list */
1088                 for( j = 0; j < numMetaVerts; j++ )
1089                 {
1090                         /* get vert */
1091                         VectorCopy( metaVerts[ j ].xyz, pt );
1092
1093                         /* debug code: darken verts */
1094                         if( i == 0 )
1095                                 VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
1096
1097                         /* determine if point lies in the triangle's plane */
1098                         dist = DotProduct( pt, plane ) - plane[ 3 ];
1099                         if( fabs( dist ) > TJ_PLANE_EPSILON )
1100                                 continue;
1101
1102                         /* skip this point if it already exists in the triangle */
1103                         for( k = 0; k < 3; k++ )
1104                         {
1105                                 if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1106                                         fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1107                                         fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
1108                                         break;
1109                         }
1110                         if( k < 3 )
1111                                 continue;
1112
1113                         /* walk edges */
1114                         for( k = 0; k < 3; k++ )
1115                         {
1116                                 /* ignore bogus edges */
1117                                 if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
1118                                         continue;
1119
1120                                 /* determine if point lies on the edge */
1121                                 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1122                                 if( fabs( dist ) > TJ_EDGE_EPSILON )
1123                                         continue;
1124
1125                                 /* determine how far along the edge the point lies */
1126                                 amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
1127                                 if( amount <= 0.0f || amount >= 1.0f )
1128                                         continue;
1129
1130                                 #if 0
1131                                 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1132                                 if( dist <= -0.0f || dist >= edges[ k ].length )
1133                                         continue;
1134                                 amount = dist / edges[ k ].length;
1135                                 #endif
1136
1137                                 /* debug code: brighten this point */
1138                                 //%     metaVerts[ j ].color[ 0 ][ 0 ] += 5;
1139                                 //%     metaVerts[ j ].color[ 0 ][ 1 ] += 4;
1140                                 VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
1141                                 VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
1142
1143
1144                                 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1145                                 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1146                                 b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
1147                                 c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
1148
1149                                 /* make new vert */
1150                                 LerpDrawVertAmount( a, b, amount, &junc );
1151                                 VectorCopy( pt, junc.xyz );
1152
1153                                 /* compare against existing verts */
1154                                 if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
1155                                         continue;
1156
1157                                 /* see if we can just re-use the existing vert */
1158                                 if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
1159                                         vertIndex = j;
1160                                 else
1161                                 {
1162                                         /* find new vertex (note: a and b are invalid pointers after this) */
1163                                         firstSearchMetaVert = numMetaVerts;
1164                                         vertIndex = FindMetaVertex( &junc );
1165                                         if( vertIndex < 0 )
1166                                                 continue;
1167                                 }
1168
1169                                 /* make new triangle */
1170                                 triIndex = AddMetaTriangle();
1171                                 if( triIndex < 0 )
1172                                         continue;
1173
1174                                 /* get triangles */
1175                                 tri = &metaTriangles[ i ];
1176                                 newTri = &metaTriangles[ triIndex ];
1177
1178                                 /* copy the triangle */
1179                                 memcpy( newTri, tri, sizeof( *tri ) );
1180
1181                                 /* fix verts */
1182                                 tri->indexes[ (k + 1) % 3 ] = vertIndex;
1183                                 newTri->indexes[ k ] = vertIndex;
1184
1185                                 /* recalculate edges */
1186                                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1187                                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1188                                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1189
1190                                 /* debug code */
1191                                 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1192                                 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1193                                 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1194
1195                                 /* add to counter and end processing of this vert */
1196                                 numTJuncs++;
1197                                 break;
1198                         }
1199                 }
1200         }
1201
1202         /* print time */
1203         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1204
1205         /* emit some stats */
1206         Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1207 }
1208
1209
1210
1211 /*
1212 SmoothMetaTriangles()
1213 averages coincident vertex normals in the meta triangles
1214 */
1215
1216 #define MAX_SAMPLES                             256
1217 #define THETA_EPSILON                   0.000001
1218 #define EQUAL_NORMAL_EPSILON    0.01
1219
1220 void SmoothMetaTriangles( void )
1221 {
1222         int                             i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1223         float                   shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1224         metaTriangle_t  *tri;
1225         float                   *shadeAngles;
1226         byte                    *smoothed;
1227         vec3_t                  average, diff;
1228         int                             indexes[ MAX_SAMPLES ];
1229         vec3_t                  votes[ MAX_SAMPLES ];
1230
1231         /* note it */
1232         Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1233
1234         /* allocate shade angle table */
1235         shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1236         memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1237
1238         /* allocate smoothed table */
1239         cs = (numMetaVerts / 8) + 1;
1240         smoothed = safe_malloc( cs );
1241         memset( smoothed, 0, cs );
1242
1243         /* set default shade angle */
1244         defaultShadeAngle = DEG2RAD( npDegrees );
1245         maxShadeAngle = 0.0f;
1246
1247         /* run through every surface and flag verts belonging to non-lightmapped surfaces
1248            and set per-vertex smoothing angle */
1249         for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1250         {
1251                 shadeAngle = defaultShadeAngle;
1252
1253                 /* get shade angle from shader */
1254                 if( tri->si->shadeAngleDegrees > 0.0f )
1255                         shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1256                 /* get shade angle from entity */
1257                 else if( tri->shadeAngleDegrees > 0.0f )
1258                         shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1259
1260                 if( shadeAngle <= 0.0f )
1261                         shadeAngle = defaultShadeAngle;
1262
1263                 if( shadeAngle > maxShadeAngle )
1264                         maxShadeAngle = shadeAngle;
1265
1266                 /* flag its verts */
1267                 for( j = 0; j < 3; j++ )
1268                 {
1269                         shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1270                         if( shadeAngle <= 0 )
1271                                 smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
1272                 }
1273         }
1274
1275         /* bail if no surfaces have a shade angle */
1276         if( maxShadeAngle <= 0 )
1277         {
1278                 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1279                 free( shadeAngles );
1280                 free( smoothed );
1281                 return;
1282         }
1283
1284         /* init pacifier */
1285         fOld = -1;
1286         start = I_FloatTime();
1287
1288         /* go through the list of vertexes */
1289         numSmoothed = 0;
1290         for( i = 0; i < numMetaVerts; i++ )
1291         {
1292                 /* print pacifier */
1293                 f = 10 * i / numMetaVerts;
1294                 if( f != fOld )
1295                 {
1296                         fOld = f;
1297                         Sys_FPrintf( SYS_VRB, "%d...", f );
1298                 }
1299
1300                 /* already smoothed? */
1301                 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
1302                         continue;
1303
1304                 /* clear */
1305                 VectorClear( average );
1306                 numVerts = 0;
1307                 numVotes = 0;
1308
1309                 /* build a table of coincident vertexes */
1310                 for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1311                 {
1312                         /* already smoothed? */
1313                         if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
1314                                 continue;
1315
1316                         /* test vertexes */
1317                         if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
1318                                 continue;
1319
1320                         /* use smallest shade angle */
1321                         shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
1322
1323                         /* check shade angle */
1324                         dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1325                         if( dot > 1.0 )
1326                                 dot = 1.0;
1327                         else if( dot < -1.0 )
1328                                 dot = -1.0;
1329                         testAngle = acos( dot ) + THETA_EPSILON;
1330                         if( testAngle >= shadeAngle )
1331                                 continue;
1332
1333                         /* add to the list */
1334                         indexes[ numVerts++ ] = j;
1335
1336                         /* flag vertex */
1337                         smoothed[ j >> 3 ] |= (1 << (j & 7));
1338
1339                         /* see if this normal has already been voted */
1340                         for( k = 0; k < numVotes; k++ )
1341                         {
1342                                 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1343                                 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1344                                         fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1345                                         fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
1346                                         break;
1347                         }
1348
1349                         /* add a new vote? */
1350                         if( k == numVotes && numVotes < MAX_SAMPLES )
1351                         {
1352                                 VectorAdd( average, metaVerts[ j ].normal, average );
1353                                 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1354                                 numVotes++;
1355                         }
1356                 }
1357
1358                 /* don't average for less than 2 verts */
1359                 if( numVerts < 2 )
1360                         continue;
1361
1362                 /* average normal */
1363                 if( VectorNormalize( average, average ) > 0 )
1364                 {
1365                         /* smooth */
1366                         for( j = 0; j < numVerts; j++ )
1367                                 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1368                         numSmoothed++;
1369                 }
1370         }
1371
1372         /* free the tables */
1373         free( shadeAngles );
1374         free( smoothed );
1375
1376         /* print time */
1377         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1378
1379         /* emit some stats */
1380         Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1381 }
1382
1383
1384
1385 /*
1386 AddMetaVertToSurface()
1387 adds a drawvert to a surface unless an existing vert matching already exists
1388 returns the index of that vert (or < 0 on failure)
1389 */
1390
1391 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
1392 {
1393         int                             i;
1394         bspDrawVert_t   *dv2;
1395
1396
1397         /* go through the verts and find a suitable candidate */
1398         for( i = 0; i < ds->numVerts; i++ )
1399         {
1400                 /* get test vert */
1401                 dv2 = &ds->verts[ i ];
1402
1403                 /* compare xyz and normal */
1404                 if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
1405                         continue;
1406                 if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
1407                         continue;
1408
1409                 /* good enough at this point */
1410                 (*coincident)++;
1411
1412                 /* compare texture coordinates and color */
1413                 if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
1414                         continue;
1415                 if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
1416                         continue;
1417
1418                 /* found a winner */
1419                 numMergedVerts++;
1420                 return i;
1421         }
1422
1423         /* overflow check */
1424         if( ds->numVerts >= ((ds->shaderInfo->compileFlags & C_VERTEXLIT) ? maxSurfaceVerts : maxLMSurfaceVerts) )
1425                 return VERTS_EXCEEDED;
1426
1427         /* made it this far, add the vert and return */
1428         dv2 = &ds->verts[ ds->numVerts++ ];
1429         *dv2 = *dv1;
1430         return (ds->numVerts - 1);
1431 }
1432
1433
1434
1435
1436 /*
1437 AddMetaTriangleToSurface()
1438 attempts to add a metatriangle to a surface
1439 returns the score of the triangle added
1440 */
1441
1442 #define AXIS_SCORE                      100000
1443 #define AXIS_MIN                        100000
1444 #define VERT_SCORE                      10000
1445 #define SURFACE_SCORE           1000
1446 #define ST_SCORE                        50
1447 #define ST_SCORE2                       (2 * (ST_SCORE))
1448
1449 #define ADEQUATE_SCORE          ((AXIS_MIN) + 1 * (VERT_SCORE))
1450 #define GOOD_SCORE                      ((AXIS_MIN) + 2 * (VERT_SCORE)                   + 4 * (ST_SCORE))
1451 #define PERFECT_SCORE           ((AXIS_MIN) + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
1452 //#define MAX_BBOX_DISTANCE   16
1453
1454 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
1455 {
1456         int                                     i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1457         float                           lmMax;
1458         vec3_t                          mins, maxs, p;
1459         qboolean                        inTexRange, es, et;
1460         mapDrawSurface_t        old;
1461
1462
1463         /* overflow check */
1464         if( ds->numIndexes >= maxSurfaceIndexes )
1465                 return 0;
1466
1467         /* test the triangle */
1468         if( ds->entityNum != tri->entityNum )   /* ydnar: added 2002-07-06 */
1469                 return 0;
1470         if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
1471                 return 0;
1472         if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
1473                 return 0;
1474         #if 0
1475                 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1476                         //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1477                         DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
1478                         return 0;
1479         #endif
1480
1481         /* planar surfaces will only merge with triangles in the same plane */
1482         if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
1483         {
1484                 if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
1485                         return 0;
1486                 if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
1487                         return 0;
1488         }
1489
1490 #if MAX_BBOX_DISTANCE > 0
1491         VectorCopy( ds->mins, mins );
1492         VectorCopy( ds->maxs, maxs );
1493         mins[0] -= MAX_BBOX_DISTANCE;
1494         mins[1] -= MAX_BBOX_DISTANCE;
1495         mins[2] -= MAX_BBOX_DISTANCE;
1496         maxs[0] += MAX_BBOX_DISTANCE;
1497         maxs[1] += MAX_BBOX_DISTANCE;
1498         maxs[2] += MAX_BBOX_DISTANCE;
1499 #define CHECK_1D(mins, v, maxs) ((mins) <= (v) && (v) <= (maxs))
1500 #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]))
1501         VectorCopy(metaVerts[ tri->indexes[ 0 ] ].xyz, p);
1502         if(!CHECK_3D(mins, p, maxs))
1503         {
1504                 VectorCopy(metaVerts[ tri->indexes[ 1 ] ].xyz, p);
1505                 if(!CHECK_3D(mins, p, maxs))
1506                 {
1507                         VectorCopy(metaVerts[ tri->indexes[ 2 ] ].xyz, p);
1508                         if(!CHECK_3D(mins, p, maxs))
1509                                 return 0;
1510                 }
1511         }
1512 #undef CHECK_3D
1513 #undef CHECK_1D
1514 #endif
1515
1516         /* set initial score */
1517         score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1518
1519         /* score the the dot product of lightmap axis to plane */
1520         if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
1521                 score += AXIS_SCORE;
1522         else
1523                 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1524
1525         /* preserve old drawsurface if this fails */
1526         memcpy( &old, ds, sizeof( *ds ) );
1527
1528         /* attempt to add the verts */
1529         coincident = 0;
1530         ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1531         bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1532         ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1533
1534         /* check vertex underflow */
1535         if( ai < 0 || bi < 0 || ci < 0 )
1536         {
1537                 memcpy( ds, &old, sizeof( *ds ) );
1538                 return 0;
1539         }
1540
1541         /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1542         score += (coincident * VERT_SCORE);
1543
1544         /* add new vertex bounds to mins/maxs */
1545         VectorCopy( ds->mins, mins );
1546         VectorCopy( ds->maxs, maxs );
1547         AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1548         AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1549         AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1550
1551         /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1552         if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1553                 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1554                 (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
1555         {
1556                 /* set maximum size before lightmap scaling (normally 2032 units) */
1557                 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1558                 /* 2004-04-11: reverting to actual lightmap size */
1559                 lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
1560                 for( i = 0; i < 3; i++ )
1561                 {
1562                         if( (maxs[ i ] - mins[ i ]) > lmMax )
1563                         {
1564                                 memcpy( ds, &old, sizeof( *ds ) );
1565                                 return 0;
1566                         }
1567                 }
1568         }
1569
1570         /* check texture range overflow */
1571         oldTexRange[ 0 ] = ds->texRange[ 0 ];
1572         oldTexRange[ 1 ] = ds->texRange[ 1 ];
1573         inTexRange = CalcSurfaceTextureRange( ds );
1574
1575         es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
1576         et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
1577
1578         if( inTexRange == qfalse && ds->numIndexes > 0 )
1579         {
1580                 memcpy( ds, &old, sizeof( *ds ) );
1581                 return UNSUITABLE_TRIANGLE;
1582         }
1583
1584         /* score texture range */
1585         if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
1586                 score += ST_SCORE2;
1587         else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
1588                 score += ST_SCORE;
1589
1590         if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
1591                 score += ST_SCORE2;
1592         else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
1593                 score += ST_SCORE;
1594
1595
1596         /* go through the indexes and try to find an existing triangle that matches abc */
1597         for( i = 0; i < ds->numIndexes; i += 3 )
1598         {
1599                 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1600                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
1601                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
1602                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
1603                 {
1604                         /* triangle already present */
1605                         memcpy( ds, &old, sizeof( *ds ) );
1606                         tri->si = NULL;
1607                         return 0;
1608                 }
1609
1610                 /* rotate the triangle 3x to find an inverse triangle (error case) */
1611                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
1612                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
1613                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
1614                 {
1615                         /* warn about it */
1616                         Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1617                                 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1618                                 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1619                                 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1620
1621                         /* reverse triangle already present */
1622                         memcpy( ds, &old, sizeof( *ds ) );
1623                         tri->si = NULL;
1624                         return 0;
1625                 }
1626         }
1627
1628         /* add the triangle indexes */
1629         if( ds->numIndexes < maxSurfaceIndexes )
1630                 ds->indexes[ ds->numIndexes++ ] = ai;
1631         if( ds->numIndexes < maxSurfaceIndexes )
1632                 ds->indexes[ ds->numIndexes++ ] = bi;
1633         if( ds->numIndexes < maxSurfaceIndexes )
1634                 ds->indexes[ ds->numIndexes++ ] = ci;
1635
1636         /* check index overflow */
1637         if( ds->numIndexes >= maxSurfaceIndexes  )
1638         {
1639                 memcpy( ds, &old, sizeof( *ds ) );
1640                 return 0;
1641         }
1642
1643         /* sanity check the indexes */
1644         if( ds->numIndexes >= 3 &&
1645                 (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1646                 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1647                 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
1648                 Sys_Printf( "DEG:%d! ", ds->numVerts );
1649
1650         /* testing only? */
1651         if( testAdd )
1652                 memcpy( ds, &old, sizeof( *ds ) );
1653         else
1654         {
1655                 /* copy bounds back to surface */
1656                 VectorCopy( mins, ds->mins );
1657                 VectorCopy( maxs, ds->maxs );
1658
1659                 /* mark triangle as used */
1660                 tri->si = NULL;
1661         }
1662
1663         /* add a side reference */
1664         ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1665
1666         /* return to sender */
1667         return score;
1668 }
1669
1670
1671
1672 /*
1673 MetaTrianglesToSurface()
1674 creates map drawsurface(s) from the list of possibles
1675 */
1676
1677 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
1678 {
1679         int                                     i, j, f, best, score, bestScore;
1680         metaTriangle_t          *seed, *test;
1681         mapDrawSurface_t        *ds;
1682         bspDrawVert_t           *verts;
1683         int                                     *indexes;
1684         qboolean                        added;
1685
1686
1687         /* allocate arrays */
1688         verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1689         indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1690
1691         /* walk the list of triangles */
1692         for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1693         {
1694                 /* skip this triangle if it has already been merged */
1695                 if( seed->si == NULL )
1696                         continue;
1697
1698                 /* -----------------------------------------------------------------
1699                    initial drawsurf construction
1700                    ----------------------------------------------------------------- */
1701
1702                 /* start a new drawsurface */
1703                 ds = AllocDrawSurface( SURFACE_META );
1704                 ds->entityNum = seed->entityNum;
1705                 ds->surfaceNum = seed->surfaceNum;
1706                 ds->castShadows = seed->castShadows;
1707                 ds->recvShadows = seed->recvShadows;
1708
1709                 ds->shaderInfo = seed->si;
1710                 ds->planeNum = seed->planeNum;
1711                 ds->fogNum = seed->fogNum;
1712                 ds->sampleSize = seed->sampleSize;
1713                 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1714                 ds->verts = verts;
1715                 ds->indexes = indexes;
1716                 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1717                 ds->sideRef = AllocSideRef( seed->side, NULL );
1718
1719                 ClearBounds( ds->mins, ds->maxs );
1720
1721                 /* clear verts/indexes */
1722                 memset( verts, 0, sizeof( verts ) );
1723                 memset( indexes, 0, sizeof( indexes ) );
1724
1725                 /* add the first triangle */
1726                 if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
1727                         (*numAdded)++;
1728
1729                 /* -----------------------------------------------------------------
1730                    add triangles
1731                    ----------------------------------------------------------------- */
1732
1733                 /* progressively walk the list until no more triangles can be added */
1734                 added = qtrue;
1735                 while( added )
1736                 {
1737                         /* print pacifier */
1738                         f = 10 * *numAdded / numMetaTriangles;
1739                         if( f > *fOld )
1740                         {
1741                                 *fOld = f;
1742                                 Sys_FPrintf( SYS_VRB, "%d...", f );
1743                         }
1744
1745                         /* reset best score */
1746                         best = -1;
1747                         bestScore = 0;
1748                         added = qfalse;
1749
1750                         /* walk the list of possible candidates for merging */
1751                         for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1752                         {
1753                                 /* skip this triangle if it has already been merged */
1754                                 if( test->si == NULL )
1755                                         continue;
1756
1757                                 /* score this triangle */
1758                                 score = AddMetaTriangleToSurface( ds, test, qtrue );
1759                                 if( score > bestScore )
1760                                 {
1761                                         best = j;
1762                                         bestScore = score;
1763
1764                                         /* if we have a score over a certain threshold, just use it */
1765                                         if( bestScore >= GOOD_SCORE )
1766                                         {
1767                                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1768                                                         (*numAdded)++;
1769
1770                                                 /* reset */
1771                                                 best = -1;
1772                                                 bestScore = 0;
1773                                                 added = qtrue;
1774                                         }
1775                                 }
1776                         }
1777
1778                         /* add best candidate */
1779                         if( best >= 0 && bestScore > ADEQUATE_SCORE )
1780                         {
1781                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1782                                         (*numAdded)++;
1783
1784                                 /* reset */
1785                                 added = qtrue;
1786                         }
1787                 }
1788
1789                 /* copy the verts and indexes to the new surface */
1790                 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1791                 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1792                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1793                 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1794
1795                 /* classify the surface */
1796                 ClassifySurfaces( 1, ds );
1797
1798                 /* add to count */
1799                 numMergedSurfaces++;
1800         }
1801
1802         /* free arrays */
1803         free( verts );
1804         free( indexes );
1805 }
1806
1807
1808
1809 /*
1810 CompareMetaTriangles()
1811 compare function for qsort()
1812 */
1813
1814 static int CompareMetaTriangles( const void *a, const void *b )
1815 {
1816         int             i, j, av, bv;
1817         vec3_t  aMins, bMins;
1818
1819
1820         /* shader first */
1821         if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
1822                 return 1;
1823         else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
1824                 return -1;
1825
1826         /* then fog */
1827         else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
1828                 return 1;
1829         else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
1830                 return -1;
1831
1832         /* then plane */
1833         #if 0
1834                 else if( npDegrees == 0.0f && ((metaTriangle_t*) a)->si->nonplanar == qfalse &&
1835                         ((metaTriangle_t*) a)->planeNum >= 0 && ((metaTriangle_t*) a)->planeNum >= 0 )
1836                 {
1837                         if( ((metaTriangle_t*) a)->plane[ 3 ] < ((metaTriangle_t*) b)->plane[ 3 ] )
1838                                 return 1;
1839                         else if( ((metaTriangle_t*) a)->plane[ 3 ] > ((metaTriangle_t*) b)->plane[ 3 ] )
1840                                 return -1;
1841                         else if( ((metaTriangle_t*) a)->plane[ 0 ] < ((metaTriangle_t*) b)->plane[ 0 ] )
1842                                 return 1;
1843                         else if( ((metaTriangle_t*) a)->plane[ 0 ] > ((metaTriangle_t*) b)->plane[ 0 ] )
1844                                 return -1;
1845                         else if( ((metaTriangle_t*) a)->plane[ 1 ] < ((metaTriangle_t*) b)->plane[ 1 ] )
1846                                 return 1;
1847                         else if( ((metaTriangle_t*) a)->plane[ 1 ] > ((metaTriangle_t*) b)->plane[ 1 ] )
1848                                 return -1;
1849                         else if( ((metaTriangle_t*) a)->plane[ 2 ] < ((metaTriangle_t*) b)->plane[ 2 ] )
1850                                 return 1;
1851                         else if( ((metaTriangle_t*) a)->plane[ 2 ] > ((metaTriangle_t*) b)->plane[ 2 ] )
1852                                 return -1;
1853                 }
1854         #endif
1855
1856         /* then position in world */
1857
1858         /* find mins */
1859         VectorSet( aMins, 999999, 999999, 999999 );
1860         VectorSet( bMins, 999999, 999999, 999999 );
1861         for( i = 0; i < 3; i++ )
1862         {
1863                 av = ((metaTriangle_t*) a)->indexes[ i ];
1864                 bv = ((metaTriangle_t*) b)->indexes[ i ];
1865                 for( j = 0; j < 3; j++ )
1866                 {
1867                         if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
1868                                 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1869                         if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
1870                                 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1871                 }
1872         }
1873
1874         /* test it */
1875         for( i = 0; i < 3; i++ )
1876         {
1877                 if( aMins[ i ] < bMins[ i ] )
1878                         return 1;
1879                 else if( aMins[ i ] > bMins[ i ] )
1880                         return -1;
1881         }
1882
1883         /* functionally equivalent */
1884         return 0;
1885 }
1886
1887
1888
1889 /*
1890 MergeMetaTriangles()
1891 merges meta triangles into drawsurfaces
1892 */
1893
1894 void MergeMetaTriangles( void )
1895 {
1896         int                                     i, j, fOld, start, numAdded;
1897         metaTriangle_t          *head, *end;
1898
1899
1900         /* only do this if there are meta triangles */
1901         if( numMetaTriangles <= 0 )
1902                 return;
1903
1904         /* note it */
1905         Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1906
1907         /* sort the triangles by shader major, fognum minor */
1908         qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1909
1910         /* init pacifier */
1911         fOld = -1;
1912         start = I_FloatTime();
1913         numAdded = 0;
1914
1915         /* merge */
1916         for( i = 0, j = 0; i < numMetaTriangles; i = j )
1917         {
1918                 /* get head of list */
1919                 head = &metaTriangles[ i ];
1920
1921                 /* skip this triangle if it has already been merged */
1922                 if( head->si == NULL )
1923                         continue;
1924
1925                 /* find end */
1926                 if( j <= i )
1927                 {
1928                         for( j = i + 1; j < numMetaTriangles; j++ )
1929                         {
1930                                 /* get end of list */
1931                                 end = &metaTriangles[ j ];
1932                                 if( head->si != end->si || head->fogNum != end->fogNum )
1933                                         break;
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         /* emit some stats */
1949         Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1950         Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
1951 }