tools/quake3/q3map2/surface_meta.c

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