tools/quake3/q3map2/surface_meta.c

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