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