tools/quake3/q3map2/surface_meta.c

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