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 int MaxAreaIndexes(bspDrawVert_t *vert, int cnt, int *indexes)
 418 {
 419         int r, s, t, bestR = 0, bestS = 1, bestT = 2;
 420         int i, j;
 421         double A, bestA = -1, V, bestV = -1;
 422         vec3_t ab, ac, bc, cross;
 423         bspDrawVert_t *buf;
 424
 425         if(cnt < 3)
 426                 return 0;
 427
 428         /* find the triangle with highest area */
 429         for(r = 0; r+2 < cnt; ++r)
 430         for(s = r+1; s+1 < cnt; ++s)
 431         for(t = s+1; t < cnt; ++t)
 432         {
 433                 VectorSubtract(vert[s].xyz, vert[r].xyz, ab);
 434                 VectorSubtract(vert[t].xyz, vert[r].xyz, ac);
 435                 VectorSubtract(vert[t].xyz, vert[s].xyz, bc);
 436                 CrossProduct(ab, ac, cross);
 437                 A = VectorLength(cross);
 438
 439                 V = A - (VectorLength(ab) - VectorLength(ac) - VectorLength(bc)) * 0.2;
 440                 /* value = A - circumference * 0.2, i.e. we back out by 0.2 units from each side, to prevent too acute triangles */
 441                 /* this kind of simulates "number of 0.2x0.2 fragments in the triangle not touched by an edge" */
 442
 443                 if(bestA < 0 || V > bestV)
 444                 {
 445                         bestA = A;
 446                         bestV = V;
 447                         bestR = r;
 448                         bestS = s;
 449                         bestT = t;
 450                 }
 451         }
 452
 453         if(bestA < TINY_AREA)
 454                 /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
 455                 return 0;
 456
 457         i = 0;
 458         indexes[i++] = bestR;
 459         indexes[i++] = bestS;
 460         indexes[i++] = bestT;
 461                 /* uses 3 */
 462
 463         /* identify the other fragments */
 464
 465         /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
 466          * 1. bestR..bestS
 467          * 2. bestS..bestT
 468          * 3. bestT..bestR
 469          */
 470
 471         j = i + MaxAreaIndexes(vert + bestR, bestS - bestR + 1, indexes + i);
 472         for(; i < j; ++i)
 473                 indexes[i] += bestR;
 474                 /* uses 3*(bestS-bestR+1)-6 */
 475         j = i + MaxAreaIndexes(vert + bestS, bestT - bestS + 1, indexes + i);
 476         for(; i < j; ++i)
 477                 indexes[i] += bestS;
 478                 /* uses 3*(bestT-bestS+1)-6 */
 479
 480         /* can'bestT recurse this one directly... therefore, buffering */
 481         if(cnt + bestR - bestT + 1 >= 3)
 482         {
 483                 buf = safe_malloc(sizeof(*vert) * (cnt + bestR - bestT + 1));
 484                 memcpy(buf, vert + bestT, sizeof(*vert) * (cnt - bestT));
 485                 memcpy(buf + (cnt - bestT), vert, sizeof(*vert) * (bestR + 1));
 486                 j = i + MaxAreaIndexes(buf, cnt + bestR - bestT + 1, indexes + i);
 487                 for(; i < j; ++i)
 488                         indexes[i] = (indexes[i] + bestT) % cnt;
 489                         /* uses 3*(cnt+bestR-bestT+1)-6 */
 490                 free(buf);
 491         }
 492
 493         /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
 494
 495         return i;
 496 }
 497
 498 /*
 499 MaxAreaFaceSurface() - divVerent
 500 creates a triangle list using max area indexes
 501 */
 502
 503 void MaxAreaFaceSurface(mapDrawSurface_t *ds)
 504 {
 505         /* try to early out  */
 506         if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
 507                 return;
 508
 509         /* is this a simple triangle? */
 510         if( ds->numVerts == 3 )
 511         {
 512                 ds->numIndexes = 3;
 513                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
 514                 VectorSet( ds->indexes, 0, 1, 2 );
 515                 numMaxAreaSurfaces++;
 516                 return;
 517         }
 518
 519         /* do it! */
 520         ds->numIndexes = 3 * ds->numVerts - 6;
 521         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
 522         ds->numIndexes = MaxAreaIndexes(ds->verts, ds->numVerts, ds->indexes);
 523
 524         /* add to count */
 525         numMaxAreaSurfaces++;
 526
 527         /* classify it */
 528         ClassifySurfaces( 1, ds );
 529 }
 530
 531
 532 /*
 533 FanFaceSurface() - ydnar
 534 creates a tri-fan from a brush face winding
 535 loosely based on SurfaceAsTriFan()
 536 */
 537
 538 void FanFaceSurface( mapDrawSurface_t *ds )
 539 {
 540         int                             i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
 541         bspDrawVert_t   *verts, *centroid, *dv;
 542         double                  iv;
 543
 544
 545         /* try to early out */
 546         if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
 547                 return;
 548
 549         /* add a new vertex at the beginning of the surface */
 550         verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );
 551         memset( verts, 0, sizeof( bspDrawVert_t ) );
 552         memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
 553         free( ds->verts );
 554         ds->verts = verts;
 555
 556         /* add up the drawverts to create a centroid */
 557         centroid = &verts[ 0 ];
 558         memset( color, 0,  4 * MAX_LIGHTMAPS * sizeof( int ) );
 559         for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )
 560         {
 561                 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
 562                 VectorAdd( centroid->normal, dv->normal, centroid->normal );
 563                 for( j = 0; j < 4; j++ )
 564                 {
 565                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
 566                                 color[ k ][ j ] += dv->color[ k ][ j ];
 567                         if( j < 2 )
 568                         {
 569                                 centroid->st[ j ] += dv->st[ j ];
 570                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
 571                                         centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
 572                         }
 573                 }
 574         }
 575
 576         /* average the centroid */
 577         iv = 1.0f / ds->numVerts;
 578         VectorScale( centroid->xyz, iv, centroid->xyz );
 579         if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )
 580                 VectorCopy( verts[ 1 ].normal, centroid->normal );
 581         for( j = 0; j < 4; j++ )
 582         {
 583                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
 584                 {
 585                         color[ k ][ j ] /= ds->numVerts;
 586                         centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);
 587                 }
 588                 if( j < 2 )
 589                 {
 590                         centroid->st[ j ] *= iv;
 591                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
 592                                 centroid->lightmap[ k ][ j ] *= iv;
 593                 }
 594         }
 595
 596         /* add to vert count */
 597         ds->numVerts++;
 598
 599         /* fill indexes in triangle fan order */
 600         ds->numIndexes = 0;
 601         ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
 602         for( i = 1; i < ds->numVerts; i++ )
 603         {
 604                 a = 0;
 605                 b = i;
 606                 c = (i + 1) % ds->numVerts;
 607                 c = c ? c : 1;
 608                 ds->indexes[ ds->numIndexes++ ] = a;
 609                 ds->indexes[ ds->numIndexes++ ] = b;
 610                 ds->indexes[ ds->numIndexes++ ] = c;
 611         }
 612
 613         /* add to count */
 614         numFanSurfaces++;
 615
 616         /* classify it */
 617         ClassifySurfaces( 1, ds );
 618 }
 619
 620
 621
 622 /*
 623 StripFaceSurface() - ydnar
 624 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
 625 based on SurfaceAsTriStrip()
 626 */
 627
 628 #define MAX_INDEXES             1024
 629
 630 void StripFaceSurface( mapDrawSurface_t *ds )
 631 {
 632         int                     i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
 633         vec_t           *v1, *v2;
 634
 635
 636         /* try to early out  */
 637         if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
 638                 return;
 639
 640         /* is this a simple triangle? */
 641         if( ds->numVerts == 3 )
 642         {
 643                 numIndexes = 3;
 644                 VectorSet( indexes, 0, 1, 2 );
 645         }
 646         else
 647         {
 648                 /* ydnar: find smallest coordinate */
 649                 least = 0;
 650                 if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )
 651                 {
 652                         for( i = 0; i < ds->numVerts; i++ )
 653                         {
 654                                 /* get points */
 655                                 v1 = ds->verts[ i ].xyz;
 656                                 v2 = ds->verts[ least ].xyz;
 657
 658                                 /* compare */
 659                                 if( v1[ 0 ] < v2[ 0 ] ||
 660                                         (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||
 661                                         (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )
 662                                         least = i;
 663                         }
 664                 }
 665
 666                 /* determine the triangle strip order */
 667                 numIndexes = (ds->numVerts - 2) * 3;
 668                 if( numIndexes > MAX_INDEXES )
 669                         Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
 670
 671                 /* try all possible orderings of the points looking for a non-degenerate strip order */
 672                 for( r = 0; r < ds->numVerts; r++ )
 673                 {
 674                         /* set rotation */
 675                         rotate = (r + least) % ds->numVerts;
 676
 677                         /* walk the winding in both directions */
 678                         for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
 679                         {
 680                                 /* make indexes */
 681                                 a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;
 682                                 b = (i + rotate ) % ds->numVerts;
 683                                 c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;
 684
 685                                 /* test this triangle */
 686                                 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
 687                                         break;
 688                                 indexes[ ni++ ] = a;
 689                                 indexes[ ni++ ] = b;
 690                                 indexes[ ni++ ] = c;
 691
 692                                 /* handle end case */
 693                                 if( i + 1 != ds->numVerts - 1 - i )
 694                                 {
 695                                         /* make indexes */
 696                                         a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;
 697                                         b = (i + rotate ) % ds->numVerts;
 698                                         c = (i + 1 + rotate ) % ds->numVerts;
 699
 700                                         /* test triangle */
 701                                         if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
 702                                                 break;
 703                                         indexes[ ni++ ] = a;
 704                                         indexes[ ni++ ] = b;
 705                                         indexes[ ni++ ] = c;
 706                                 }
 707                         }
 708
 709                         /* valid strip? */
 710                         if( ni == numIndexes )
 711                                 break;
 712                 }
 713
 714                 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
 715                 if( ni < numIndexes )
 716                 {
 717                         FanFaceSurface( ds );
 718                         return;
 719                 }
 720         }
 721
 722         /* copy strip triangle indexes */
 723         ds->numIndexes = numIndexes;
 724         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
 725         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
 726
 727         /* add to count */
 728         numStripSurfaces++;
 729
 730         /* classify it */
 731         ClassifySurfaces( 1, ds );
 732 }
 733
 734
 735 /*
 736 EmitMetaStatictics
 737 vortex: prints meta statistics in general output
 738 */
 739
 740 void EmitMetaStats()
 741 {
 742         Sys_Printf( "--- EmitMetaStats ---\n" );
 743         Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
 744         Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
 745         Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
 746         Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
 747         Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
 748         Sys_Printf( "%9d meta verts\n", numMetaVerts );
 749         Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
 750 }
 751
 752 /*
 753 MakeEntityMetaTriangles()
 754 builds meta triangles from brush faces (tristrips and fans)
 755 */
 756
 757 void MakeEntityMetaTriangles( entity_t *e )
 758 {
 759         int                                     i, f, fOld, start;
 760         mapDrawSurface_t        *ds;
 761
 762
 763         /* note it */
 764         Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
 765
 766         /* init pacifier */
 767         fOld = -1;
 768         start = I_FloatTime();
 769
 770         /* walk the list of surfaces in the entity */
 771         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
 772         {
 773                 /* print pacifier */
 774                 f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
 775                 if( f != fOld )
 776                 {
 777                         fOld = f;
 778                         Sys_FPrintf( SYS_VRB, "%d...", f );
 779                 }
 780
 781                 /* get surface */
 782                 ds = &mapDrawSurfs[ i ];
 783                 if( ds->numVerts <= 0 )
 784                         continue;
 785
 786                 /* ignore autosprite surfaces */
 787                 if( ds->shaderInfo->autosprite )
 788                         continue;
 789
 790                 /* meta this surface? */
 791                 if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
 792                         continue;
 793
 794                 /* switch on type */
 795                 switch( ds->type )
 796                 {
 797                         case SURFACE_FACE:
 798                         case SURFACE_DECAL:
 799                                 if(maxAreaFaceSurface)
 800                                         MaxAreaFaceSurface( ds );
 801                                 else
 802                                         StripFaceSurface( ds );
 803                                 SurfaceToMetaTriangles( ds );
 804                                 break;
 805
 806                         case SURFACE_PATCH:
 807                                 TriangulatePatchSurface(e, ds );
 808                                 break;
 809
 810                         case SURFACE_TRIANGLES:
 811                                 break;
 812
 813                         case SURFACE_FORCED_META:
 814                         case SURFACE_META:
 815                                 SurfaceToMetaTriangles( ds );
 816                                 break;
 817
 818                         default:
 819                                 break;
 820                 }
 821         }
 822
 823         /* print time */
 824         if( (numMapDrawSurfs - e->firstDrawSurf) )
 825                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
 826
 827         /* emit some stats */
 828         Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
 829         Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
 830         Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
 831         Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
 832         Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
 833         Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
 834         Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
 835
 836         /* tidy things up */
 837         TidyEntitySurfaces( e );
 838 }
 839
 840
 841
 842 /*
 843 PointTriangleIntersect()
 844 assuming that all points lie in plane, determine if pt
 845 is inside the triangle abc
 846 code originally (c) 2001 softSurfer (www.softsurfer.com)
 847 */
 848
 849 #define MIN_OUTSIDE_EPSILON             -0.01f
 850 #define MAX_OUTSIDE_EPSILON             1.01f
 851
 852 static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
 853 {
 854         vec3_t  u, v, w;
 855         float   uu, uv, vv, wu, wv, d;
 856
 857
 858         /* make vectors */
 859         VectorSubtract( b, a, u );
 860         VectorSubtract( c, a, v );
 861         VectorSubtract( pt, a, w );
 862
 863         /* more setup */
 864         uu = DotProduct( u, u );
 865         uv = DotProduct( u, v );
 866         vv = DotProduct( v, v );
 867         wu = DotProduct( w, u );
 868         wv = DotProduct( w, v );
 869         d = uv * uv - uu * vv;
 870
 871         /* calculate barycentric coordinates */
 872         bary[ 1 ] = (uv * wv - vv * wu) / d;
 873         if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
 874                 return qfalse;
 875         bary[ 2 ] = (uv * wv - uu * wv) / d;
 876         if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
 877                 return qfalse;
 878         bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
 879
 880         /* point is in triangle */
 881         return qtrue;
 882 }
 883
 884
 885
 886 /*
 887 CreateEdge()
 888 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
 889 */
 890
 891 typedef struct edge_s
 892 {
 893         vec3_t  origin, edge;
 894         vec_t   length, kingpinLength;
 895         int             kingpin;
 896         vec4_t  plane;
 897 }
 898 edge_t;
 899
 900 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
 901 {
 902         /* copy edge origin */
 903         VectorCopy( a, edge->origin );
 904
 905         /* create vector aligned with winding direction of edge */
 906         VectorSubtract( b, a, edge->edge );
 907
 908         if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
 909                 edge->kingpin = 0;
 910         else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
 911                 edge->kingpin = 1;
 912         else
 913                 edge->kingpin = 2;
 914         edge->kingpinLength = edge->edge[ edge->kingpin ];
 915
 916         VectorNormalize( edge->edge, edge->edge );
 917         edge->edge[ 3 ] = DotProduct( a, edge->edge );
 918         edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
 919
 920         /* create perpendicular plane that edge lies in */
 921         CrossProduct( plane, edge->edge, edge->plane );
 922         edge->plane[ 3 ] = DotProduct( a, edge->plane );
 923 }
 924
 925
 926
 927 /*
 928 FixMetaTJunctions()
 929 fixes t-junctions on meta triangles
 930 */
 931
 932 #define TJ_PLANE_EPSILON        (1.0f / 8.0f)
 933 #define TJ_EDGE_EPSILON         (1.0f / 8.0f)
 934 #define TJ_POINT_EPSILON        (1.0f / 8.0f)
 935
 936 void FixMetaTJunctions( void )
 937 {
 938         int                             i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
 939         metaTriangle_t  *tri, *newTri;
 940         shaderInfo_t    *si;
 941         bspDrawVert_t   *a, *b, *c, junc;
 942         float                   dist, amount;
 943         vec3_t                  pt;
 944         vec4_t                  plane;
 945         edge_t                  edges[ 3 ];
 946
 947
 948         /* this code is crap; revisit later */
 949         return;
 950
 951         /* note it */
 952         Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
 953
 954         /* init pacifier */
 955         fOld = -1;
 956         start = I_FloatTime();
 957
 958         /* walk triangle list */
 959         numTJuncs = 0;
 960         for( i = 0; i < numMetaTriangles; i++ )
 961         {
 962                 /* get triangle */
 963                 tri = &metaTriangles[ i ];
 964
 965                 /* print pacifier */
 966                 f = 10 * i / numMetaTriangles;
 967                 if( f != fOld )
 968                 {
 969                         fOld = f;
 970                         Sys_FPrintf( SYS_VRB, "%d...", f );
 971                 }
 972
 973                 /* attempt to early out */
 974                 si = tri->si;
 975                 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
 976                         continue;
 977
 978                 /* calculate planes */
 979                 VectorCopy( tri->plane, plane );
 980                 plane[ 3 ] = tri->plane[ 3 ];
 981                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
 982                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
 983                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
 984
 985                 /* walk meta vert list */
 986                 for( j = 0; j < numMetaVerts; j++ )
 987                 {
 988                         /* get vert */
 989                         VectorCopy( metaVerts[ j ].xyz, pt );
 990
 991                         /* debug code: darken verts */
 992                         if( i == 0 )
 993                                 VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
 994
 995                         /* determine if point lies in the triangle's plane */
 996                         dist = DotProduct( pt, plane ) - plane[ 3 ];
 997                         if( fabs( dist ) > TJ_PLANE_EPSILON )
 998                                 continue;
 999
1000                         /* skip this point if it already exists in the triangle */
1001                         for( k = 0; k < 3; k++ )
1002                         {
1003                                 if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1004                                         fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1005                                         fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
1006                                         break;
1007                         }
1008                         if( k < 3 )
1009                                 continue;
1010
1011                         /* walk edges */
1012                         for( k = 0; k < 3; k++ )
1013                         {
1014                                 /* ignore bogus edges */
1015                                 if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
1016                                         continue;
1017
1018                                 /* determine if point lies on the edge */
1019                                 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1020                                 if( fabs( dist ) > TJ_EDGE_EPSILON )
1021                                         continue;
1022
1023                                 /* determine how far along the edge the point lies */
1024                                 amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
1025                                 if( amount <= 0.0f || amount >= 1.0f )
1026                                         continue;
1027
1028                                 #if 0
1029                                 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1030                                 if( dist <= -0.0f || dist >= edges[ k ].length )
1031                                         continue;
1032                                 amount = dist / edges[ k ].length;
1033                                 #endif
1034
1035                                 /* debug code: brighten this point */
1036                                 //%     metaVerts[ j ].color[ 0 ][ 0 ] += 5;
1037                                 //%     metaVerts[ j ].color[ 0 ][ 1 ] += 4;
1038                                 VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
1039                                 VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
1040
1041
1042                                 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1043                                 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1044                                 b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
1045                                 c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
1046
1047                                 /* make new vert */
1048                                 LerpDrawVertAmount( a, b, amount, &junc );
1049                                 VectorCopy( pt, junc.xyz );
1050
1051                                 /* compare against existing verts */
1052                                 if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
1053                                         continue;
1054
1055                                 /* see if we can just re-use the existing vert */
1056                                 if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
1057                                         vertIndex = j;
1058                                 else
1059                                 {
1060                                         /* find new vertex (note: a and b are invalid pointers after this) */
1061                                         firstSearchMetaVert = numMetaVerts;
1062                                         vertIndex = FindMetaVertex( &junc );
1063                                         if( vertIndex < 0 )
1064                                                 continue;
1065                                 }
1066
1067                                 /* make new triangle */
1068                                 triIndex = AddMetaTriangle();
1069                                 if( triIndex < 0 )
1070                                         continue;
1071
1072                                 /* get triangles */
1073                                 tri = &metaTriangles[ i ];
1074                                 newTri = &metaTriangles[ triIndex ];
1075
1076                                 /* copy the triangle */
1077                                 memcpy( newTri, tri, sizeof( *tri ) );
1078
1079                                 /* fix verts */
1080                                 tri->indexes[ (k + 1) % 3 ] = vertIndex;
1081                                 newTri->indexes[ k ] = vertIndex;
1082
1083                                 /* recalculate edges */
1084                                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1085                                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1086                                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1087
1088                                 /* debug code */
1089                                 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1090                                 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1091                                 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1092
1093                                 /* add to counter and end processing of this vert */
1094                                 numTJuncs++;
1095                                 break;
1096                         }
1097                 }
1098         }
1099
1100         /* print time */
1101         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1102
1103         /* emit some stats */
1104         Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1105 }
1106
1107
1108
1109 /*
1110 SmoothMetaTriangles()
1111 averages coincident vertex normals in the meta triangles
1112 */
1113
1114 #define MAX_SAMPLES                             256
1115 #define THETA_EPSILON                   0.000001
1116 #define EQUAL_NORMAL_EPSILON    0.01
1117
1118 void SmoothMetaTriangles( void )
1119 {
1120         int                             i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1121         float                   shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1122         metaTriangle_t  *tri;
1123         float                   *shadeAngles;
1124         byte                    *smoothed;
1125         vec3_t                  average, diff;
1126         int                             indexes[ MAX_SAMPLES ];
1127         vec3_t                  votes[ MAX_SAMPLES ];
1128
1129         /* note it */
1130         Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1131
1132         /* allocate shade angle table */
1133         shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1134         memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1135
1136         /* allocate smoothed table */
1137         cs = (numMetaVerts / 8) + 1;
1138         smoothed = safe_malloc( cs );
1139         memset( smoothed, 0, cs );
1140
1141         /* set default shade angle */
1142         defaultShadeAngle = DEG2RAD( npDegrees );
1143         maxShadeAngle = 0.0f;
1144
1145         /* run through every surface and flag verts belonging to non-lightmapped surfaces
1146            and set per-vertex smoothing angle */
1147         for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1148         {
1149                 shadeAngle = defaultShadeAngle;
1150
1151                 /* get shade angle from shader */
1152                 if( tri->si->shadeAngleDegrees > 0.0f )
1153                         shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1154                 /* get shade angle from entity */
1155                 else if( tri->shadeAngleDegrees > 0.0f )
1156                         shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1157
1158                 if( shadeAngle <= 0.0f )
1159                         shadeAngle = defaultShadeAngle;
1160
1161                 if( shadeAngle > maxShadeAngle )
1162                         maxShadeAngle = shadeAngle;
1163
1164                 /* flag its verts */
1165                 for( j = 0; j < 3; j++ )
1166                 {
1167                         shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1168                         if( shadeAngle <= 0 )
1169                                 smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
1170                 }
1171         }
1172
1173         /* bail if no surfaces have a shade angle */
1174         if( maxShadeAngle <= 0 )
1175         {
1176                 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1177                 free( shadeAngles );
1178                 free( smoothed );
1179                 return;
1180         }
1181
1182         /* init pacifier */
1183         fOld = -1;
1184         start = I_FloatTime();
1185
1186         /* go through the list of vertexes */
1187         numSmoothed = 0;
1188         for( i = 0; i < numMetaVerts; i++ )
1189         {
1190                 /* print pacifier */
1191                 f = 10 * i / numMetaVerts;
1192                 if( f != fOld )
1193                 {
1194                         fOld = f;
1195                         Sys_FPrintf( SYS_VRB, "%d...", f );
1196                 }
1197
1198                 /* already smoothed? */
1199                 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
1200                         continue;
1201
1202                 /* clear */
1203                 VectorClear( average );
1204                 numVerts = 0;
1205                 numVotes = 0;
1206
1207                 /* build a table of coincident vertexes */
1208                 for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1209                 {
1210                         /* already smoothed? */
1211                         if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
1212                                 continue;
1213
1214                         /* test vertexes */
1215                         if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
1216                                 continue;
1217
1218                         /* use smallest shade angle */
1219                         shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
1220
1221                         /* check shade angle */
1222                         dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1223                         if( dot > 1.0 )
1224                                 dot = 1.0;
1225                         else if( dot < -1.0 )
1226                                 dot = -1.0;
1227                         testAngle = acos( dot ) + THETA_EPSILON;
1228                         if( testAngle >= shadeAngle )
1229                                 continue;
1230
1231                         /* add to the list */
1232                         indexes[ numVerts++ ] = j;
1233
1234                         /* flag vertex */
1235                         smoothed[ j >> 3 ] |= (1 << (j & 7));
1236
1237                         /* see if this normal has already been voted */
1238                         for( k = 0; k < numVotes; k++ )
1239                         {
1240                                 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1241                                 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1242                                         fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1243                                         fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
1244                                         break;
1245                         }
1246
1247                         /* add a new vote? */
1248                         if( k == numVotes && numVotes < MAX_SAMPLES )
1249                         {
1250                                 VectorAdd( average, metaVerts[ j ].normal, average );
1251                                 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1252                                 numVotes++;
1253                         }
1254                 }
1255
1256                 /* don't average for less than 2 verts */
1257                 if( numVerts < 2 )
1258                         continue;
1259
1260                 /* average normal */
1261                 if( VectorNormalize( average, average ) > 0 )
1262                 {
1263                         /* smooth */
1264                         for( j = 0; j < numVerts; j++ )
1265                                 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1266                         numSmoothed++;
1267                 }
1268         }
1269
1270         /* free the tables */
1271         free( shadeAngles );
1272         free( smoothed );
1273
1274         /* print time */
1275         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1276
1277         /* emit some stats */
1278         Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1279 }
1280
1281
1282
1283 /*
1284 AddMetaVertToSurface()
1285 adds a drawvert to a surface unless an existing vert matching already exists
1286 returns the index of that vert (or < 0 on failure)
1287 */
1288
1289 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
1290 {
1291         int                             i;
1292         bspDrawVert_t   *dv2;
1293
1294
1295         /* go through the verts and find a suitable candidate */
1296         for( i = 0; i < ds->numVerts; i++ )
1297         {
1298                 /* get test vert */
1299                 dv2 = &ds->verts[ i ];
1300
1301                 /* compare xyz and normal */
1302                 if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
1303                         continue;
1304                 if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
1305                         continue;
1306
1307                 /* good enough at this point */
1308                 (*coincident)++;
1309
1310                 /* compare texture coordinates and color */
1311                 if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
1312                         continue;
1313                 if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
1314                         continue;
1315
1316                 /* found a winner */
1317                 numMergedVerts++;
1318                 return i;
1319         }
1320
1321         /* overflow check */
1322         if( ds->numVerts >= ((ds->shaderInfo->compileFlags & C_VERTEXLIT) ? maxSurfaceVerts : maxLMSurfaceVerts) )
1323                 return VERTS_EXCEEDED;
1324
1325         /* made it this far, add the vert and return */
1326         dv2 = &ds->verts[ ds->numVerts++ ];
1327         *dv2 = *dv1;
1328         return (ds->numVerts - 1);
1329 }
1330
1331
1332
1333
1334 /*
1335 AddMetaTriangleToSurface()
1336 attempts to add a metatriangle to a surface
1337 returns the score of the triangle added
1338 */
1339
1340 #define AXIS_SCORE                      100000
1341 #define AXIS_MIN                        100000
1342 #define VERT_SCORE                      10000
1343 #define SURFACE_SCORE           1000
1344 #define ST_SCORE                        50
1345 #define ST_SCORE2                       (2 * (ST_SCORE))
1346
1347 #define ADEQUATE_SCORE          ((AXIS_MIN) + 1 * (VERT_SCORE))
1348 #define GOOD_SCORE                      ((AXIS_MIN) + 2 * (VERT_SCORE)                   + 4 * (ST_SCORE))
1349 #define PERFECT_SCORE           ((AXIS_MIN) + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
1350 //#define MAX_BBOX_DISTANCE   16
1351
1352 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
1353 {
1354         int                                     i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1355         float                           lmMax;
1356         vec3_t                          mins, maxs, p;
1357         qboolean                        inTexRange, es, et;
1358         mapDrawSurface_t        old;
1359
1360
1361         /* overflow check */
1362         if( ds->numIndexes >= maxSurfaceIndexes )
1363                 return 0;
1364
1365         /* test the triangle */
1366         if( ds->entityNum != tri->entityNum )   /* ydnar: added 2002-07-06 */
1367                 return 0;
1368         if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
1369                 return 0;
1370         if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
1371                 return 0;
1372         #if 0
1373                 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1374                         //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1375                         DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
1376                         return 0;
1377         #endif
1378
1379         /* planar surfaces will only merge with triangles in the same plane */
1380         if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
1381         {
1382                 if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
1383                         return 0;
1384                 if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
1385                         return 0;
1386         }
1387
1388 #if MAX_BBOX_DISTANCE > 0
1389         VectorCopy( ds->mins, mins );
1390         VectorCopy( ds->maxs, maxs );
1391         mins[0] -= MAX_BBOX_DISTANCE;
1392         mins[1] -= MAX_BBOX_DISTANCE;
1393         mins[2] -= MAX_BBOX_DISTANCE;
1394         maxs[0] += MAX_BBOX_DISTANCE;
1395         maxs[1] += MAX_BBOX_DISTANCE;
1396         maxs[2] += MAX_BBOX_DISTANCE;
1397 #define CHECK_1D(mins, v, maxs) ((mins) <= (v) && (v) <= (maxs))
1398 #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]))
1399         VectorCopy(metaVerts[ tri->indexes[ 0 ] ].xyz, p);
1400         if(!CHECK_3D(mins, p, maxs))
1401         {
1402                 VectorCopy(metaVerts[ tri->indexes[ 1 ] ].xyz, p);
1403                 if(!CHECK_3D(mins, p, maxs))
1404                 {
1405                         VectorCopy(metaVerts[ tri->indexes[ 2 ] ].xyz, p);
1406                         if(!CHECK_3D(mins, p, maxs))
1407                                 return 0;
1408                 }
1409         }
1410 #undef CHECK_3D
1411 #undef CHECK_1D
1412 #endif
1413
1414         /* set initial score */
1415         score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1416
1417         /* score the the dot product of lightmap axis to plane */
1418         if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
1419                 score += AXIS_SCORE;
1420         else
1421                 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1422
1423         /* preserve old drawsurface if this fails */
1424         memcpy( &old, ds, sizeof( *ds ) );
1425
1426         /* attempt to add the verts */
1427         coincident = 0;
1428         ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1429         bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1430         ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1431
1432         /* check vertex underflow */
1433         if( ai < 0 || bi < 0 || ci < 0 )
1434         {
1435                 memcpy( ds, &old, sizeof( *ds ) );
1436                 return 0;
1437         }
1438
1439         /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1440         score += (coincident * VERT_SCORE);
1441
1442         /* add new vertex bounds to mins/maxs */
1443         VectorCopy( ds->mins, mins );
1444         VectorCopy( ds->maxs, maxs );
1445         AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1446         AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1447         AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1448
1449         /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1450         if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1451                 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1452                 (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
1453         {
1454                 /* set maximum size before lightmap scaling (normally 2032 units) */
1455                 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1456                 /* 2004-04-11: reverting to actual lightmap size */
1457                 lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
1458                 for( i = 0; i < 3; i++ )
1459                 {
1460                         if( (maxs[ i ] - mins[ i ]) > lmMax )
1461                         {
1462                                 memcpy( ds, &old, sizeof( *ds ) );
1463                                 return 0;
1464                         }
1465                 }
1466         }
1467
1468         /* check texture range overflow */
1469         oldTexRange[ 0 ] = ds->texRange[ 0 ];
1470         oldTexRange[ 1 ] = ds->texRange[ 1 ];
1471         inTexRange = CalcSurfaceTextureRange( ds );
1472
1473         es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
1474         et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
1475
1476         if( inTexRange == qfalse && ds->numIndexes > 0 )
1477         {
1478                 memcpy( ds, &old, sizeof( *ds ) );
1479                 return UNSUITABLE_TRIANGLE;
1480         }
1481
1482         /* score texture range */
1483         if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
1484                 score += ST_SCORE2;
1485         else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
1486                 score += ST_SCORE;
1487
1488         if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
1489                 score += ST_SCORE2;
1490         else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
1491                 score += ST_SCORE;
1492
1493
1494         /* go through the indexes and try to find an existing triangle that matches abc */
1495         for( i = 0; i < ds->numIndexes; i += 3 )
1496         {
1497                 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1498                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
1499                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
1500                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
1501                 {
1502                         /* triangle already present */
1503                         memcpy( ds, &old, sizeof( *ds ) );
1504                         tri->si = NULL;
1505                         return 0;
1506                 }
1507
1508                 /* rotate the triangle 3x to find an inverse triangle (error case) */
1509                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
1510                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
1511                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
1512                 {
1513                         /* warn about it */
1514                         Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1515                                 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1516                                 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1517                                 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1518
1519                         /* reverse triangle already present */
1520                         memcpy( ds, &old, sizeof( *ds ) );
1521                         tri->si = NULL;
1522                         return 0;
1523                 }
1524         }
1525
1526         /* add the triangle indexes */
1527         if( ds->numIndexes < maxSurfaceIndexes )
1528                 ds->indexes[ ds->numIndexes++ ] = ai;
1529         if( ds->numIndexes < maxSurfaceIndexes )
1530                 ds->indexes[ ds->numIndexes++ ] = bi;
1531         if( ds->numIndexes < maxSurfaceIndexes )
1532                 ds->indexes[ ds->numIndexes++ ] = ci;
1533
1534         /* check index overflow */
1535         if( ds->numIndexes >= maxSurfaceIndexes  )
1536         {
1537                 memcpy( ds, &old, sizeof( *ds ) );
1538                 return 0;
1539         }
1540
1541         /* sanity check the indexes */
1542         if( ds->numIndexes >= 3 &&
1543                 (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1544                 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1545                 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
1546                 Sys_Printf( "DEG:%d! ", ds->numVerts );
1547
1548         /* testing only? */
1549         if( testAdd )
1550                 memcpy( ds, &old, sizeof( *ds ) );
1551         else
1552         {
1553                 /* copy bounds back to surface */
1554                 VectorCopy( mins, ds->mins );
1555                 VectorCopy( maxs, ds->maxs );
1556
1557                 /* mark triangle as used */
1558                 tri->si = NULL;
1559         }
1560
1561         /* add a side reference */
1562         ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1563
1564         /* return to sender */
1565         return score;
1566 }
1567
1568
1569
1570 /*
1571 MetaTrianglesToSurface()
1572 creates map drawsurface(s) from the list of possibles
1573 */
1574
1575 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
1576 {
1577         int                                     i, j, f, best, score, bestScore;
1578         metaTriangle_t          *seed, *test;
1579         mapDrawSurface_t        *ds;
1580         bspDrawVert_t           *verts;
1581         int                                     *indexes;
1582         qboolean                        added;
1583
1584
1585         /* allocate arrays */
1586         verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1587         indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1588
1589         /* walk the list of triangles */
1590         for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1591         {
1592                 /* skip this triangle if it has already been merged */
1593                 if( seed->si == NULL )
1594                         continue;
1595
1596                 /* -----------------------------------------------------------------
1597                    initial drawsurf construction
1598                    ----------------------------------------------------------------- */
1599
1600                 /* start a new drawsurface */
1601                 ds = AllocDrawSurface( SURFACE_META );
1602                 ds->entityNum = seed->entityNum;
1603                 ds->surfaceNum = seed->surfaceNum;
1604                 ds->castShadows = seed->castShadows;
1605                 ds->recvShadows = seed->recvShadows;
1606
1607                 ds->shaderInfo = seed->si;
1608                 ds->planeNum = seed->planeNum;
1609                 ds->fogNum = seed->fogNum;
1610                 ds->sampleSize = seed->sampleSize;
1611                 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1612                 ds->verts = verts;
1613                 ds->indexes = indexes;
1614                 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1615                 ds->sideRef = AllocSideRef( seed->side, NULL );
1616
1617                 ClearBounds( ds->mins, ds->maxs );
1618
1619                 /* clear verts/indexes */
1620                 memset( verts, 0, sizeof( verts ) );
1621                 memset( indexes, 0, sizeof( indexes ) );
1622
1623                 /* add the first triangle */
1624                 if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
1625                         (*numAdded)++;
1626
1627                 /* -----------------------------------------------------------------
1628                    add triangles
1629                    ----------------------------------------------------------------- */
1630
1631                 /* progressively walk the list until no more triangles can be added */
1632                 added = qtrue;
1633                 while( added )
1634                 {
1635                         /* print pacifier */
1636                         f = 10 * *numAdded / numMetaTriangles;
1637                         if( f > *fOld )
1638                         {
1639                                 *fOld = f;
1640                                 Sys_FPrintf( SYS_VRB, "%d...", f );
1641                         }
1642
1643                         /* reset best score */
1644                         best = -1;
1645                         bestScore = 0;
1646                         added = qfalse;
1647
1648                         /* walk the list of possible candidates for merging */
1649                         for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1650                         {
1651                                 /* skip this triangle if it has already been merged */
1652                                 if( test->si == NULL )
1653                                         continue;
1654
1655                                 /* score this triangle */
1656                                 score = AddMetaTriangleToSurface( ds, test, qtrue );
1657                                 if( score > bestScore )
1658                                 {
1659                                         best = j;
1660                                         bestScore = score;
1661
1662                                         /* if we have a score over a certain threshold, just use it */
1663                                         if( bestScore >= GOOD_SCORE )
1664                                         {
1665                                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1666                                                         (*numAdded)++;
1667
1668                                                 /* reset */
1669                                                 best = -1;
1670                                                 bestScore = 0;
1671                                                 added = qtrue;
1672                                         }
1673                                 }
1674                         }
1675
1676                         /* add best candidate */
1677                         if( best >= 0 && bestScore > ADEQUATE_SCORE )
1678                         {
1679                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1680                                         (*numAdded)++;
1681
1682                                 /* reset */
1683                                 added = qtrue;
1684                         }
1685                 }
1686
1687                 /* copy the verts and indexes to the new surface */
1688                 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1689                 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1690                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1691                 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1692
1693                 /* classify the surface */
1694                 ClassifySurfaces( 1, ds );
1695
1696                 /* add to count */
1697                 numMergedSurfaces++;
1698         }
1699
1700         /* free arrays */
1701         free( verts );
1702         free( indexes );
1703 }
1704
1705
1706
1707 /*
1708 CompareMetaTriangles()
1709 compare function for qsort()
1710 */
1711
1712 static int CompareMetaTriangles( const void *a, const void *b )
1713 {
1714         int             i, j, av, bv;
1715         vec3_t  aMins, bMins;
1716
1717
1718         /* shader first */
1719         if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
1720                 return 1;
1721         else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
1722                 return -1;
1723
1724         /* then fog */
1725         else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
1726                 return 1;
1727         else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
1728                 return -1;
1729
1730         /* then plane */
1731         #if 0
1732                 else if( npDegrees == 0.0f && ((metaTriangle_t*) a)->si->nonplanar == qfalse &&
1733                         ((metaTriangle_t*) a)->planeNum >= 0 && ((metaTriangle_t*) a)->planeNum >= 0 )
1734                 {
1735                         if( ((metaTriangle_t*) a)->plane[ 3 ] < ((metaTriangle_t*) b)->plane[ 3 ] )
1736                                 return 1;
1737                         else if( ((metaTriangle_t*) a)->plane[ 3 ] > ((metaTriangle_t*) b)->plane[ 3 ] )
1738                                 return -1;
1739                         else if( ((metaTriangle_t*) a)->plane[ 0 ] < ((metaTriangle_t*) b)->plane[ 0 ] )
1740                                 return 1;
1741                         else if( ((metaTriangle_t*) a)->plane[ 0 ] > ((metaTriangle_t*) b)->plane[ 0 ] )
1742                                 return -1;
1743                         else if( ((metaTriangle_t*) a)->plane[ 1 ] < ((metaTriangle_t*) b)->plane[ 1 ] )
1744                                 return 1;
1745                         else if( ((metaTriangle_t*) a)->plane[ 1 ] > ((metaTriangle_t*) b)->plane[ 1 ] )
1746                                 return -1;
1747                         else if( ((metaTriangle_t*) a)->plane[ 2 ] < ((metaTriangle_t*) b)->plane[ 2 ] )
1748                                 return 1;
1749                         else if( ((metaTriangle_t*) a)->plane[ 2 ] > ((metaTriangle_t*) b)->plane[ 2 ] )
1750                                 return -1;
1751                 }
1752         #endif
1753
1754         /* then position in world */
1755
1756         /* find mins */
1757         VectorSet( aMins, 999999, 999999, 999999 );
1758         VectorSet( bMins, 999999, 999999, 999999 );
1759         for( i = 0; i < 3; i++ )
1760         {
1761                 av = ((metaTriangle_t*) a)->indexes[ i ];
1762                 bv = ((metaTriangle_t*) b)->indexes[ i ];
1763                 for( j = 0; j < 3; j++ )
1764                 {
1765                         if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
1766                                 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1767                         if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
1768                                 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1769                 }
1770         }
1771
1772         /* test it */
1773         for( i = 0; i < 3; i++ )
1774         {
1775                 if( aMins[ i ] < bMins[ i ] )
1776                         return 1;
1777                 else if( aMins[ i ] > bMins[ i ] )
1778                         return -1;
1779         }
1780
1781         /* functionally equivalent */
1782         return 0;
1783 }
1784
1785
1786
1787 /*
1788 MergeMetaTriangles()
1789 merges meta triangles into drawsurfaces
1790 */
1791
1792 void MergeMetaTriangles( void )
1793 {
1794         int                                     i, j, fOld, start, numAdded;
1795         metaTriangle_t          *head, *end;
1796
1797
1798         /* only do this if there are meta triangles */
1799         if( numMetaTriangles <= 0 )
1800                 return;
1801
1802         /* note it */
1803         Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1804
1805         /* sort the triangles by shader major, fognum minor */
1806         qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1807
1808         /* init pacifier */
1809         fOld = -1;
1810         start = I_FloatTime();
1811         numAdded = 0;
1812
1813         /* merge */
1814         for( i = 0, j = 0; i < numMetaTriangles; i = j )
1815         {
1816                 /* get head of list */
1817                 head = &metaTriangles[ i ];
1818
1819                 /* skip this triangle if it has already been merged */
1820                 if( head->si == NULL )
1821                         continue;
1822
1823                 /* find end */
1824                 if( j <= i )
1825                 {
1826                         for( j = i + 1; j < numMetaTriangles; j++ )
1827                         {
1828                                 /* get end of list */
1829                                 end = &metaTriangles[ j ];
1830                                 if( head->si != end->si || head->fogNum != end->fogNum )
1831                                         break;
1832                         }
1833                 }
1834
1835                 /* try to merge this list of possible merge candidates */
1836                 MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );
1837         }
1838
1839         /* clear meta triangle list */
1840         ClearMetaTriangles();
1841
1842         /* print time */
1843         if( i )
1844                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1845
1846         /* emit some stats */
1847         Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1848         Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
1849 }