tools/quake3/q3map2/surface.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_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41 /*
  42    AllocDrawSurface()
  43    ydnar: gs mods: changed to force an explicit type when allocating
  44  */
  45
  46 mapDrawSurface_t *AllocDrawSurface( surfaceType_t type ){
  47         mapDrawSurface_t    *ds;
  48
  49
  50         /* ydnar: gs mods: only allocate valid types */
  51         if ( type <= SURFACE_BAD || type >= NUM_SURFACE_TYPES ) {
  52                 Error( "AllocDrawSurface: Invalid surface type %d specified", type );
  53         }
  54
  55         /* bounds check */
  56         if ( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS ) {
  57                 Error( "MAX_MAP_DRAW_SURFS (%d) exceeded", MAX_MAP_DRAW_SURFS );
  58         }
  59         ds = &mapDrawSurfs[ numMapDrawSurfs ];
  60         numMapDrawSurfs++;
  61
  62         /* ydnar: do initial surface setup */
  63         memset( ds, 0, sizeof( mapDrawSurface_t ) );
  64         ds->type = type;
  65         ds->planeNum = -1;
  66         ds->fogNum = defaultFogNum;             /* ydnar 2003-02-12 */
  67         ds->outputNum = -1;                     /* ydnar 2002-08-13 */
  68         ds->surfaceNum = numMapDrawSurfs - 1;   /* ydnar 2003-02-16 */
  69
  70         return ds;
  71 }
  72
  73
  74
  75 /*
  76    FinishSurface()
  77    ydnar: general surface finish pass
  78  */
  79
  80 void FinishSurface( mapDrawSurface_t *ds ){
  81         mapDrawSurface_t    *ds2;
  82
  83
  84         /* dummy check */
  85         if ( ds == NULL || ds->shaderInfo == NULL || ds->type <= SURFACE_BAD || ds->type >= NUM_SURFACE_TYPES ) {
  86                 return;
  87         }
  88
  89         /* ydnar: rocking tek-fu celshading */
  90         if ( ds->celShader != NULL ) {
  91                 MakeCelSurface( ds, ds->celShader );
  92         }
  93
  94         /* backsides stop here */
  95         if ( ds->backSide ) {
  96                 return;
  97         }
  98
  99         /* ydnar: rocking surface cloning (fur baby yeah!) */
 100         if ( ds->shaderInfo->cloneShader != NULL && ds->shaderInfo->cloneShader[ 0 ] != '\0' ) {
 101                 CloneSurface( ds, ShaderInfoForShader( ds->shaderInfo->cloneShader ) );
 102         }
 103
 104         /* ydnar: q3map_backShader support */
 105         if ( ds->shaderInfo->backShader != NULL && ds->shaderInfo->backShader[ 0 ] != '\0' ) {
 106                 ds2 = CloneSurface( ds, ShaderInfoForShader( ds->shaderInfo->backShader ) );
 107                 ds2->backSide = qtrue;
 108         }
 109 }
 110
 111
 112
 113 /*
 114    CloneSurface()
 115    clones a map drawsurface, using the specified shader
 116  */
 117
 118 mapDrawSurface_t *CloneSurface( mapDrawSurface_t *src, shaderInfo_t *si ){
 119         mapDrawSurface_t    *ds;
 120
 121
 122         /* dummy check */
 123         if ( src == NULL || si == NULL ) {
 124                 return NULL;
 125         }
 126
 127         /* allocate a new surface */
 128         ds = AllocDrawSurface( src->type );
 129         if ( ds == NULL ) {
 130                 return NULL;
 131         }
 132
 133         /* copy it */
 134         memcpy( ds, src, sizeof( *ds ) );
 135
 136         /* destroy side reference */
 137         ds->sideRef = NULL;
 138
 139         /* set shader */
 140         ds->shaderInfo = si;
 141
 142         /* copy verts */
 143         if ( ds->numVerts > 0 ) {
 144                 ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
 145                 memcpy( ds->verts, src->verts, ds->numVerts * sizeof( *ds->verts ) );
 146         }
 147
 148         /* copy indexes */
 149         if ( ds->numIndexes <= 0 ) {
 150                 return ds;
 151         }
 152         ds->indexes = safe_malloc( ds->numIndexes * sizeof( *ds->indexes ) );
 153         memcpy( ds->indexes, src->indexes, ds->numIndexes * sizeof( *ds->indexes ) );
 154
 155         /* return the surface */
 156         return ds;
 157 }
 158
 159
 160
 161 /*
 162    MakeCelSurface() - ydnar
 163    makes a copy of a surface, but specific to cel shading
 164  */
 165
 166 mapDrawSurface_t *MakeCelSurface( mapDrawSurface_t *src, shaderInfo_t *si ){
 167         mapDrawSurface_t    *ds;
 168
 169
 170         /* dummy check */
 171         if ( src == NULL || si == NULL ) {
 172                 return NULL;
 173         }
 174
 175         /* don't create cel surfaces for certain types of shaders */
 176         if ( ( src->shaderInfo->compileFlags & C_TRANSLUCENT ) ||
 177                  ( src->shaderInfo->compileFlags & C_SKY ) ) {
 178                 return NULL;
 179         }
 180
 181         /* make a copy */
 182         ds = CloneSurface( src, si );
 183         if ( ds == NULL ) {
 184                 return NULL;
 185         }
 186
 187         /* do some fixups for celshading */
 188         ds->planar = qfalse;
 189         ds->planeNum = -1;
 190         ds->celShader = NULL; /* don't cel shade cels :P */
 191
 192         /* return the surface */
 193         return ds;
 194 }
 195
 196
 197
 198 /*
 199    MakeSkyboxSurface() - ydnar
 200    generates a skybox surface, viewable from everywhere there is sky
 201  */
 202
 203 mapDrawSurface_t *MakeSkyboxSurface( mapDrawSurface_t *src ){
 204         int i;
 205         mapDrawSurface_t    *ds;
 206
 207
 208         /* dummy check */
 209         if ( src == NULL ) {
 210                 return NULL;
 211         }
 212
 213         /* make a copy */
 214         ds = CloneSurface( src, src->shaderInfo );
 215         if ( ds == NULL ) {
 216                 return NULL;
 217         }
 218
 219         /* set parent */
 220         ds->parent = src;
 221
 222         /* scale the surface vertexes */
 223         for ( i = 0; i < ds->numVerts; i++ )
 224         {
 225                 m4x4_transform_point( skyboxTransform, ds->verts[ i ].xyz );
 226
 227                 /* debug code */
 228                 //%     bspDrawVerts[ bspDrawSurfaces[ ds->outputNum ].firstVert + i ].color[ 0 ][ 1 ] = 0;
 229                 //%     bspDrawVerts[ bspDrawSurfaces[ ds->outputNum ].firstVert + i ].color[ 0 ][ 2 ] = 0;
 230         }
 231
 232         /* so backface culling creep doesn't bork the surface */
 233         VectorClear( ds->lightmapVecs[ 2 ] );
 234
 235         /* return the surface */
 236         return ds;
 237 }
 238
 239
 240
 241 /*
 242    IsTriangleDegenerate
 243    returns qtrue if all three points are colinear, backwards, or the triangle is just plain bogus
 244  */
 245
 246 #define TINY_AREA   1.0f
 247
 248 qboolean IsTriangleDegenerate( bspDrawVert_t *points, int a, int b, int c ){
 249         vec3_t v1, v2, v3;
 250         float d;
 251
 252
 253         /* calcuate the area of the triangle */
 254         VectorSubtract( points[ b ].xyz, points[ a ].xyz, v1 );
 255         VectorSubtract( points[ c ].xyz, points[ a ].xyz, v2 );
 256         CrossProduct( v1, v2, v3 );
 257         d = VectorLength( v3 );
 258
 259         /* assume all very small or backwards triangles will cause problems */
 260         if ( d < TINY_AREA ) {
 261                 return qtrue;
 262         }
 263
 264         /* must be a good triangle */
 265         return qfalse;
 266 }
 267
 268
 269
 270 /*
 271    ClearSurface() - ydnar
 272    clears a surface and frees any allocated memory
 273  */
 274
 275 void ClearSurface( mapDrawSurface_t *ds ){
 276         ds->type = SURFACE_BAD;
 277         ds->planar = qfalse;
 278         ds->planeNum = -1;
 279         ds->numVerts = 0;
 280         if ( ds->verts != NULL ) {
 281                 free( ds->verts );
 282         }
 283         ds->verts = NULL;
 284         ds->numIndexes = 0;
 285         if ( ds->indexes != NULL ) {
 286                 free( ds->indexes );
 287         }
 288         ds->indexes = NULL;
 289         numClearedSurfaces++;
 290 }
 291
 292
 293
 294 /*
 295    TidyEntitySurfaces() - ydnar
 296    deletes all empty or bad surfaces from the surface list
 297  */
 298
 299 void TidyEntitySurfaces( entity_t *e ){
 300         int i, j, deleted;
 301         mapDrawSurface_t    *out, *in = NULL;
 302
 303
 304         /* note it */
 305         Sys_FPrintf( SYS_VRB, "--- TidyEntitySurfaces ---\n" );
 306
 307         /* walk the surface list */
 308         deleted = 0;
 309         for ( i = e->firstDrawSurf, j = e->firstDrawSurf; j < numMapDrawSurfs; i++, j++ )
 310         {
 311                 /* get out surface */
 312                 out = &mapDrawSurfs[ i ];
 313
 314                 /* walk the surface list again until a proper surface is found */
 315                 for ( ; j < numMapDrawSurfs; j++ )
 316                 {
 317                         /* get in surface */
 318                         in = &mapDrawSurfs[ j ];
 319
 320                         /* this surface ok? */
 321                         if ( in->type == SURFACE_FLARE || in->type == SURFACE_SHADER ||
 322                                  ( in->type != SURFACE_BAD && in->numVerts > 0 ) ) {
 323                                 break;
 324                         }
 325
 326                         /* nuke it */
 327                         ClearSurface( in );
 328                         deleted++;
 329                 }
 330
 331                 /* copy if necessary */
 332                 if ( i != j ) {
 333                         memcpy( out, in, sizeof( mapDrawSurface_t ) );
 334                 }
 335         }
 336
 337         /* set the new number of drawsurfs */
 338         numMapDrawSurfs = i;
 339
 340         /* emit some stats */
 341         Sys_FPrintf( SYS_VRB, "%9d empty or malformed surfaces deleted\n", deleted );
 342 }
 343
 344
 345
 346 /*
 347    CalcSurfaceTextureRange() - ydnar
 348    calculates the clamped texture range for a given surface, returns qtrue if it's within [-texRange,texRange]
 349  */
 350
 351 qboolean CalcSurfaceTextureRange( mapDrawSurface_t *ds ){
 352         int i, j, v, size[ 2 ];
 353         float mins[ 2 ], maxs[ 2 ];
 354
 355
 356         /* try to early out */
 357         if ( ds->numVerts <= 0 ) {
 358                 return qtrue;
 359         }
 360
 361         /* walk the verts and determine min/max st values */
 362         mins[ 0 ] = 999999;
 363         mins[ 1 ] = 999999;
 364         maxs[ 0 ] = -999999;
 365         maxs[ 1 ] = -999999;
 366         for ( i = 0; i < ds->numVerts; i++ )
 367         {
 368                 for ( j = 0; j < 2; j++ )
 369                 {
 370                         if ( ds->verts[ i ].st[ j ] < mins[ j ] ) {
 371                                 mins[ j ] = ds->verts[ i ].st[ j ];
 372                         }
 373                         if ( ds->verts[ i ].st[ j ] > maxs[ j ] ) {
 374                                 maxs[ j ] = ds->verts[ i ].st[ j ];
 375                         }
 376                 }
 377         }
 378
 379         /* clamp to integer range and calculate surface bias values */
 380         for ( j = 0; j < 2; j++ )
 381                 ds->bias[ j ] = -floor( 0.5f * ( mins[ j ] + maxs[ j ] ) );
 382
 383         /* find biased texture coordinate mins/maxs */
 384         size[ 0 ] = ds->shaderInfo->shaderWidth;
 385         size[ 1 ] = ds->shaderInfo->shaderHeight;
 386         ds->texMins[ 0 ] = 999999;
 387         ds->texMins[ 1 ] = 999999;
 388         ds->texMaxs[ 0 ] = -999999;
 389         ds->texMaxs[ 1 ] = -999999;
 390         for ( i = 0; i < ds->numVerts; i++ )
 391         {
 392                 for ( j = 0; j < 2; j++ )
 393                 {
 394                         v = ( (float) ds->verts[ i ].st[ j ] + ds->bias[ j ] ) * size[ j ];
 395                         if ( v < ds->texMins[ j ] ) {
 396                                 ds->texMins[ j ] = v;
 397                         }
 398                         if ( v > ds->texMaxs[ j ] ) {
 399                                 ds->texMaxs[ j ] = v;
 400                         }
 401                 }
 402         }
 403
 404         /* calc ranges */
 405         for ( j = 0; j < 2; j++ )
 406                 ds->texRange[ j ] = ( ds->texMaxs[ j ] - ds->texMins[ j ] );
 407
 408         /* if range is zero, then assume unlimited precision */
 409         if ( texRange == 0 ) {
 410                 return qtrue;
 411         }
 412
 413         /* within range? */
 414         for ( j = 0; j < 2; j++ )
 415         {
 416                 if ( ds->texMins[ j ] < -texRange || ds->texMaxs[ j ] > texRange ) {
 417                         return qfalse;
 418                 }
 419         }
 420
 421         /* within range */
 422         return qtrue;
 423 }
 424
 425
 426
 427 /*
 428    CalcLightmapAxis() - ydnar
 429    gives closed lightmap axis for a plane normal
 430  */
 431
 432 qboolean CalcLightmapAxis( vec3_t normal, vec3_t axis ){
 433         vec3_t absolute;
 434
 435
 436         /* test */
 437         if ( normal[ 0 ] == 0.0f && normal[ 1 ] == 0.0f && normal[ 2 ] == 0.0f ) {
 438                 VectorClear( axis );
 439                 return qfalse;
 440         }
 441
 442         /* get absolute normal */
 443         absolute[ 0 ] = fabs( normal[ 0 ] );
 444         absolute[ 1 ] = fabs( normal[ 1 ] );
 445         absolute[ 2 ] = fabs( normal[ 2 ] );
 446
 447         /* test and set */
 448         if ( absolute[ 2 ] > absolute[ 0 ] - 0.0001f && absolute[ 2 ] > absolute[ 1 ] - 0.0001f ) {
 449                 if ( normal[ 2 ] > 0.0f ) {
 450                         VectorSet( axis, 0.0f, 0.0f, 1.0f );
 451                 }
 452                 else{
 453                         VectorSet( axis, 0.0f, 0.0f, -1.0f );
 454                 }
 455         }
 456         else if ( absolute[ 0 ] > absolute[ 1 ] - 0.0001f && absolute[ 0 ] > absolute[ 2 ] - 0.0001f ) {
 457                 if ( normal[ 0 ] > 0.0f ) {
 458                         VectorSet( axis, 1.0f, 0.0f, 0.0f );
 459                 }
 460                 else{
 461                         VectorSet( axis, -1.0f, 0.0f, 0.0f );
 462                 }
 463         }
 464         else
 465         {
 466                 if ( normal[ 1 ] > 0.0f ) {
 467                         VectorSet( axis, 0.0f, 1.0f, 0.0f );
 468                 }
 469                 else{
 470                         VectorSet( axis, 0.0f, -1.0f, 0.0f );
 471                 }
 472         }
 473
 474         /* return ok */
 475         return qtrue;
 476 }
 477
 478
 479
 480 /*
 481    ClassifySurfaces() - ydnar
 482    fills out a bunch of info in the surfaces, including planar status, lightmap projection, and bounding box
 483  */
 484
 485 #define PLANAR_EPSILON  0.5f    //% 0.126f 0.25f
 486
 487 void ClassifySurfaces( int numSurfs, mapDrawSurface_t *ds ){
 488         int i, bestAxis;
 489         float dist;
 490         vec4_t plane;
 491         shaderInfo_t        *si;
 492         static vec3_t axii[ 6 ] =
 493         {
 494                 { 0, 0, -1 },
 495                 { 0, 0, 1 },
 496                 { -1, 0, 0 },
 497                 { 1, 0, 0 },
 498                 { 0, -1, 0 },
 499                 { 0, 1, 0 }
 500         };
 501
 502
 503         /* walk the list of surfaces */
 504         for ( ; numSurfs > 0; numSurfs--, ds++ )
 505         {
 506                 /* ignore bogus (or flare) surfaces */
 507                 if ( ds->type == SURFACE_BAD || ds->numVerts <= 0 ) {
 508                         continue;
 509                 }
 510
 511                 /* get shader */
 512                 si = ds->shaderInfo;
 513
 514                 /* -----------------------------------------------------------------
 515                    force meta if vertex count is too high or shader requires it
 516                    ----------------------------------------------------------------- */
 517
 518                 if ( ds->type != SURFACE_PATCH && ds->type != SURFACE_FACE ) {
 519                         if ( ds->numVerts > SHADER_MAX_VERTEXES ) {
 520                                 ds->type = SURFACE_FORCED_META;
 521                         }
 522                 }
 523
 524                 /* -----------------------------------------------------------------
 525                    plane and bounding box classification
 526                    ----------------------------------------------------------------- */
 527
 528                 /* set surface bounding box */
 529                 ClearBounds( ds->mins, ds->maxs );
 530                 for ( i = 0; i < ds->numVerts; i++ )
 531                         AddPointToBounds( ds->verts[ i ].xyz, ds->mins, ds->maxs );
 532
 533                 /* try to get an existing plane */
 534                 if ( ds->planeNum >= 0 ) {
 535                         VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
 536                         plane[ 3 ] = mapplanes[ ds->planeNum ].dist;
 537                 }
 538
 539                 /* construct one from the first vert with a valid normal */
 540                 else
 541                 {
 542                         VectorClear( plane );
 543                         plane[ 3 ] = 0.0f;
 544                         for ( i = 0; i < ds->numVerts; i++ )
 545                         {
 546                                 if ( ds->verts[ i ].normal[ 0 ] != 0.0f && ds->verts[ i ].normal[ 1 ] != 0.0f && ds->verts[ i ].normal[ 2 ] != 0.0f ) {
 547                                         VectorCopy( ds->verts[ i ].normal, plane );
 548                                         plane[ 3 ] = DotProduct( ds->verts[ i ].xyz, plane );
 549                                         break;
 550                                 }
 551                         }
 552                 }
 553
 554                 /* test for bogus plane */
 555                 if ( VectorLength( plane ) <= 0.0f ) {
 556                         ds->planar = qfalse;
 557                         ds->planeNum = -1;
 558                 }
 559                 else
 560                 {
 561                         /* determine if surface is planar */
 562                         ds->planar = qtrue;
 563
 564                         /* test each vert */
 565                         for ( i = 0; i < ds->numVerts; i++ )
 566                         {
 567                                 /* point-plane test */
 568                                 dist = DotProduct( ds->verts[ i ].xyz, plane ) - plane[ 3 ];
 569                                 if ( fabs( dist ) > PLANAR_EPSILON ) {
 570                                         //%     if( ds->planeNum >= 0 )
 571                                         //%     {
 572                                         //%             Sys_FPrintf( SYS_WRN, "WARNING: Planar surface marked unplanar (%f > %f)\n", fabs( dist ), PLANAR_EPSILON );
 573                                         //%             ds->verts[ i ].color[ 0 ][ 0 ] = ds->verts[ i ].color[ 0 ][ 2 ] = 0;
 574                                         //%     }
 575                                         ds->planar = qfalse;
 576                                         break;
 577                                 }
 578                         }
 579                 }
 580
 581                 /* find map plane if necessary */
 582                 if ( ds->planar ) {
 583                         if ( ds->planeNum < 0 ) {
 584                                 ds->planeNum = FindFloatPlane( plane, plane[ 3 ], 1, &ds->verts[ 0 ].xyz );
 585                         }
 586                         VectorCopy( plane, ds->lightmapVecs[ 2 ] );
 587                 }
 588                 else
 589                 {
 590                         ds->planeNum = -1;
 591                         VectorClear( ds->lightmapVecs[ 2 ] );
 592                         //% if( ds->type == SURF_META || ds->type == SURF_FACE )
 593                         //%             Sys_FPrintf( SYS_WRN, "WARNING: Non-planar face (%d): %s\n", ds->planeNum, ds->shaderInfo->shader );
 594                 }
 595
 596                 /* -----------------------------------------------------------------
 597                    lightmap bounds and axis projection
 598                    ----------------------------------------------------------------- */
 599
 600                 /* vertex lit surfaces don't need this information */
 601                 if ( si->compileFlags & C_VERTEXLIT || ds->type == SURFACE_TRIANGLES || nolm == qtrue ) {
 602                         VectorClear( ds->lightmapAxis );
 603                         //%     VectorClear( ds->lightmapVecs[ 2 ] );
 604                         ds->sampleSize = 0;
 605                         continue;
 606                 }
 607
 608                 /* the shader can specify an explicit lightmap axis */
 609                 if ( si->lightmapAxis[ 0 ] || si->lightmapAxis[ 1 ] || si->lightmapAxis[ 2 ] ) {
 610                         VectorCopy( si->lightmapAxis, ds->lightmapAxis );
 611                 }
 612                 else if ( ds->type == SURFACE_FORCED_META ) {
 613                         VectorClear( ds->lightmapAxis );
 614                 }
 615                 else if ( ds->planar ) {
 616                         CalcLightmapAxis( plane, ds->lightmapAxis );
 617                 }
 618                 else
 619                 {
 620                         /* find best lightmap axis */
 621                         for ( bestAxis = 0; bestAxis < 6; bestAxis++ )
 622                         {
 623                                 for ( i = 0; i < ds->numVerts && bestAxis < 6; i++ )
 624                                 {
 625                                         //% Sys_Printf( "Comparing %1.3f %1.3f %1.3f to %1.3f %1.3f %1.3f\n",
 626                                         //%     ds->verts[ i ].normal[ 0 ], ds->verts[ i ].normal[ 1 ], ds->verts[ i ].normal[ 2 ],
 627                                         //%     axii[ bestAxis ][ 0 ], axii[ bestAxis ][ 1 ], axii[ bestAxis ][ 2 ] );
 628                                         if ( DotProduct( ds->verts[ i ].normal, axii[ bestAxis ] ) < 0.25f ) { /* fixme: adjust this tolerance to taste */
 629                                                 break;
 630                                         }
 631                                 }
 632
 633                                 if ( i == ds->numVerts ) {
 634                                         break;
 635                                 }
 636                         }
 637
 638                         /* set axis if possible */
 639                         if ( bestAxis < 6 ) {
 640                                 //% if( ds->type == SURFACE_PATCH )
 641                                 //%     Sys_Printf( "Mapped axis %d onto patch\n", bestAxis );
 642                                 VectorCopy( axii[ bestAxis ], ds->lightmapAxis );
 643                         }
 644
 645                         /* debug code */
 646                         //% if( ds->type == SURFACE_PATCH )
 647                         //%     Sys_Printf( "Failed to map axis %d onto patch\n", bestAxis );
 648                 }
 649
 650                 /* calculate lightmap sample size */
 651                 if ( ds->shaderInfo->lightmapSampleSize > 0 ) { /* shader value overrides every other */
 652                         ds->sampleSize = ds->shaderInfo->lightmapSampleSize;
 653                 }
 654                 else if ( ds->sampleSize <= 0 ) { /* may contain the entity asigned value */
 655                         ds->sampleSize = sampleSize; /* otherwise use global default */
 656
 657                 }
 658                 if ( ds->lightmapScale > 0.0f ) { /* apply surface lightmap scaling factor */
 659                         ds->sampleSize = ds->lightmapScale * (float)ds->sampleSize;
 660                         ds->lightmapScale = 0; /* applied */
 661                 }
 662
 663                 if ( ds->sampleSize < minSampleSize ) {
 664                         ds->sampleSize = minSampleSize;
 665                 }
 666
 667                 if ( ds->sampleSize < 1 ) {
 668                         ds->sampleSize = 1;
 669                 }
 670
 671                 if ( ds->sampleSize > 16384 ) { /* powers of 2 are preferred */
 672                         ds->sampleSize = 16384;
 673                 }
 674         }
 675 }
 676
 677
 678
 679 /*
 680    ClassifyEntitySurfaces() - ydnar
 681    classifies all surfaces in an entity
 682  */
 683
 684 void ClassifyEntitySurfaces( entity_t *e ){
 685         int i;
 686
 687
 688         /* note it */
 689         Sys_FPrintf( SYS_VRB, "--- ClassifyEntitySurfaces ---\n" );
 690
 691         /* walk the surface list */
 692         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
 693         {
 694                 FinishSurface( &mapDrawSurfs[ i ] );
 695                 ClassifySurfaces( 1, &mapDrawSurfs[ i ] );
 696         }
 697
 698         /* tidy things up */
 699         TidyEntitySurfaces( e );
 700 }
 701
 702
 703
 704 /*
 705    GetShaderIndexForPoint() - ydnar
 706    for shader-indexed surfaces (terrain), find a matching index from the indexmap
 707  */
 708
 709 byte GetShaderIndexForPoint( indexMap_t *im, vec3_t eMins, vec3_t eMaxs, vec3_t point ){
 710         int i, x, y;
 711         float s, t;
 712         vec3_t mins, maxs, size;
 713
 714
 715         /* early out if no indexmap */
 716         if ( im == NULL ) {
 717                 return 0;
 718         }
 719
 720         /* this code is really broken */
 721         #if 0
 722         /* legacy precision fudges for terrain */
 723         for ( i = 0; i < 3; i++ )
 724         {
 725                 mins[ i ] = floor( eMins[ i ] + 0.1 );
 726                 maxs[ i ] = floor( eMaxs[ i ] + 0.1 );
 727                 size[ i ] = maxs[ i ] - mins[ i ];
 728         }
 729
 730         /* find st (fixme: support more than just z-axis projection) */
 731         s = floor( point[ 0 ] + 0.1f - mins[ 0 ] ) / size[ 0 ];
 732         t = floor( maxs[ 1 ] - point[ 1 ] + 0.1f ) / size[ 1 ];
 733         if ( s < 0.0f ) {
 734                 s = 0.0f;
 735         }
 736         else if ( s > 1.0f ) {
 737                 s = 1.0f;
 738         }
 739         if ( t < 0.0f ) {
 740                 t = 0.0f;
 741         }
 742         else if ( t > 1.0f ) {
 743                 t = 1.0f;
 744         }
 745
 746         /* make xy */
 747         x = ( im->w - 1 ) * s;
 748         y = ( im->h - 1 ) * t;
 749         #else
 750         /* get size */
 751         for ( i = 0; i < 3; i++ )
 752         {
 753                 mins[ i ] = eMins[ i ];
 754                 maxs[ i ] = eMaxs[ i ];
 755                 size[ i ] = maxs[ i ] - mins[ i ];
 756         }
 757
 758         /* calc st */
 759         s = ( point[ 0 ] - mins[ 0 ] ) / size[ 0 ];
 760         t = ( maxs[ 1 ] - point[ 1 ] ) / size[ 1 ];
 761
 762         /* calc xy */
 763         x = s * im->w;
 764         y = t * im->h;
 765         if ( x < 0 ) {
 766                 x = 0;
 767         }
 768         else if ( x > ( im->w - 1 ) ) {
 769                 x = ( im->w - 1 );
 770         }
 771         if ( y < 0 ) {
 772                 y = 0;
 773         }
 774         else if ( y > ( im->h - 1 ) ) {
 775                 y = ( im->h - 1 );
 776         }
 777         #endif
 778
 779         /* return index */
 780         return im->pixels[ y * im->w + x ];
 781 }
 782
 783
 784 #define snprintf_ignore(s, n, format, ...) do { \
 785     size_t __n = snprintf(s, n, format, __VA_ARGS__); \
 786     if (n >= n) {} /* truncated, ignore */ \
 787 } while (0)
 788
 789 /*
 790    GetIndexedShader() - ydnar
 791    for a given set of indexes and an indexmap, get a shader and set the vertex alpha in-place
 792    this combines a couple different functions from terrain.c
 793  */
 794
 795 shaderInfo_t *GetIndexedShader( shaderInfo_t *parent, indexMap_t *im, int numPoints, byte *shaderIndexes ){
 796         int i;
 797         byte minShaderIndex, maxShaderIndex;
 798         char shader[ MAX_QPATH ];
 799         shaderInfo_t    *si;
 800
 801
 802         /* early out if bad data */
 803         if ( im == NULL || numPoints <= 0 || shaderIndexes == NULL ) {
 804                 return ShaderInfoForShader( "default" );
 805         }
 806
 807         /* determine min/max index */
 808         minShaderIndex = 255;
 809         maxShaderIndex = 0;
 810         for ( i = 0; i < numPoints; i++ )
 811         {
 812                 if ( shaderIndexes[ i ] < minShaderIndex ) {
 813                         minShaderIndex = shaderIndexes[ i ];
 814                 }
 815                 if ( shaderIndexes[ i ] > maxShaderIndex ) {
 816                         maxShaderIndex = shaderIndexes[ i ];
 817                 }
 818         }
 819
 820         /* set alpha inline */
 821         for ( i = 0; i < numPoints; i++ )
 822         {
 823                 /* straight rip from terrain.c */
 824                 if ( shaderIndexes[ i ] < maxShaderIndex ) {
 825                         shaderIndexes[ i ] = 0;
 826                 }
 827                 else{
 828                         shaderIndexes[ i ] = 255;
 829                 }
 830         }
 831
 832         /* make a shader name */
 833         if ( minShaderIndex == maxShaderIndex ) {
 834                 snprintf_ignore( shader, sizeof shader, "textures/%s_%d", im->shader, maxShaderIndex );
 835         }
 836         else{
 837                 snprintf_ignore( shader, sizeof shader, "textures/%s_%dto%d", im->shader, minShaderIndex, maxShaderIndex );
 838         }
 839
 840         /* get the shader */
 841         si = ShaderInfoForShader( shader );
 842
 843         /* inherit a few things from parent shader */
 844         if ( parent->globalTexture ) {
 845                 si->globalTexture = qtrue;
 846         }
 847         if ( parent->forceMeta ) {
 848                 si->forceMeta = qtrue;
 849         }
 850         if ( parent->nonplanar ) {
 851                 si->nonplanar = qtrue;
 852         }
 853         if ( si->shadeAngleDegrees == 0.0 ) {
 854                 si->shadeAngleDegrees = parent->shadeAngleDegrees;
 855         }
 856         if ( parent->tcGen && si->tcGen == qfalse ) {
 857                 /* set xy texture projection */
 858                 si->tcGen = qtrue;
 859                 VectorCopy( parent->vecs[ 0 ], si->vecs[ 0 ] );
 860                 VectorCopy( parent->vecs[ 1 ], si->vecs[ 1 ] );
 861         }
 862         if ( VectorLength( parent->lightmapAxis ) > 0.0f && VectorLength( si->lightmapAxis ) <= 0.0f ) {
 863                 /* set lightmap projection axis */
 864                 VectorCopy( parent->lightmapAxis, si->lightmapAxis );
 865         }
 866
 867         /* return the shader */
 868         return si;
 869 }
 870
 871
 872
 873
 874 /*
 875    DrawSurfaceForSide()
 876    creates a SURF_FACE drawsurface from a given brush side and winding
 877  */
 878
 879 #define SNAP_FLOAT_TO_INT   8
 880 #define SNAP_INT_TO_FLOAT   ( 1.0 / SNAP_FLOAT_TO_INT )
 881
 882 mapDrawSurface_t *DrawSurfaceForSide( entity_t *e, brush_t *b, side_t *s, winding_t *w ){
 883         int i, j, k;
 884         mapDrawSurface_t    *ds;
 885         shaderInfo_t        *si, *parent;
 886         bspDrawVert_t       *dv;
 887         vec3_t texX, texY;
 888         vec_t x, y;
 889         vec3_t vTranslated;
 890         qboolean indexed;
 891         byte shaderIndexes[ 256 ];
 892         float offsets[ 256 ];
 893         char tempShader[ MAX_QPATH ];
 894
 895
 896         /* ydnar: don't make a drawsurf for culled sides */
 897         if ( s->culled ) {
 898                 return NULL;
 899         }
 900
 901         /* range check */
 902         if ( w->numpoints > MAX_POINTS_ON_WINDING ) {
 903                 Error( "DrawSurfaceForSide: w->numpoints = %d (> %d)", w->numpoints, MAX_POINTS_ON_WINDING );
 904         }
 905
 906         /* get shader */
 907         si = s->shaderInfo;
 908
 909         /* ydnar: gs mods: check for indexed shader */
 910         if ( si->indexed && b->im != NULL ) {
 911                 /* indexed */
 912                 indexed = qtrue;
 913
 914                 /* get shader indexes for each point */
 915                 for ( i = 0; i < w->numpoints; i++ )
 916                 {
 917                         shaderIndexes[ i ] = GetShaderIndexForPoint( b->im, b->eMins, b->eMaxs, w->p[ i ] );
 918                         offsets[ i ] = b->im->offsets[ shaderIndexes[ i ] ];
 919                         //%     Sys_Printf( "%f ", offsets[ i ] );
 920                 }
 921
 922                 /* get matching shader and set alpha */
 923                 parent = si;
 924                 si = GetIndexedShader( parent, b->im, w->numpoints, shaderIndexes );
 925         }
 926         else{
 927                 indexed = qfalse;
 928         }
 929
 930         /* ydnar: sky hack/fix for GL_CLAMP borders on ati cards */
 931         if ( skyFixHack && si->skyParmsImageBase[ 0 ] != '\0' ) {
 932                 //%     Sys_FPrintf( SYS_VRB, "Enabling sky hack for shader %s using env %s\n", si->shader, si->skyParmsImageBase );
 933                 snprintf_ignore( tempShader, sizeof tempShader, "%s_lf", si->skyParmsImageBase );
 934                 DrawSurfaceForShader( tempShader );
 935                 snprintf_ignore( tempShader, sizeof tempShader, "%s_rt", si->skyParmsImageBase );
 936                 DrawSurfaceForShader( tempShader );
 937                 snprintf_ignore( tempShader, sizeof tempShader, "%s_ft", si->skyParmsImageBase );
 938                 DrawSurfaceForShader( tempShader );
 939                 snprintf_ignore( tempShader, sizeof tempShader, "%s_bk", si->skyParmsImageBase );
 940                 DrawSurfaceForShader( tempShader );
 941                 snprintf_ignore( tempShader, sizeof tempShader, "%s_up", si->skyParmsImageBase );
 942                 DrawSurfaceForShader( tempShader );
 943                 snprintf_ignore( tempShader, sizeof tempShader, "%s_dn", si->skyParmsImageBase );
 944                 DrawSurfaceForShader( tempShader );
 945         }
 946
 947         /* ydnar: gs mods */
 948         ds = AllocDrawSurface( SURFACE_FACE );
 949         ds->entityNum = b->entityNum;
 950         ds->castShadows = b->castShadows;
 951         ds->recvShadows = b->recvShadows;
 952
 953         ds->planar = qtrue;
 954         ds->planeNum = s->planenum;
 955         VectorCopy( mapplanes[ s->planenum ].normal, ds->lightmapVecs[ 2 ] );
 956
 957         ds->shaderInfo = si;
 958         ds->mapBrush = b;
 959         ds->sideRef = AllocSideRef( s, NULL );
 960         ds->fogNum = -1;
 961         ds->sampleSize = b->lightmapSampleSize;
 962         ds->lightmapScale = b->lightmapScale;
 963         ds->numVerts = w->numpoints;
 964         ds->verts = safe_malloc0( ds->numVerts * sizeof( *ds->verts ) );
 965
 966         /* compute s/t coordinates from brush primitive texture matrix (compute axis base) */
 967         ComputeAxisBase( mapplanes[ s->planenum ].normal, texX, texY );
 968
 969         /* create the vertexes */
 970         for ( j = 0; j < w->numpoints; j++ )
 971         {
 972                 /* get the drawvert */
 973                 dv = ds->verts + j;
 974
 975                 /* copy xyz and do potential z offset */
 976                 VectorCopy( w->p[ j ], dv->xyz );
 977                 if ( indexed ) {
 978                         dv->xyz[ 2 ] += offsets[ j ];
 979                 }
 980
 981                 /* round the xyz to a given precision and translate by origin */
 982                 for ( i = 0 ; i < 3 ; i++ )
 983                         dv->xyz[ i ] = SNAP_INT_TO_FLOAT * floor( dv->xyz[ i ] * SNAP_FLOAT_TO_INT + 0.5f );
 984                 VectorAdd( dv->xyz, e->origin, vTranslated );
 985
 986                 /* ydnar: tek-fu celshading support for flat shaded shit */
 987                 if ( flat ) {
 988                         dv->st[ 0 ] = si->stFlat[ 0 ];
 989                         dv->st[ 1 ] = si->stFlat[ 1 ];
 990                 }
 991
 992                 /* ydnar: gs mods: added support for explicit shader texcoord generation */
 993                 else if ( si->tcGen ) {
 994                         dv->st[ 0 ] = DotProduct( si->vecs[ 0 ], vTranslated );
 995                         dv->st[ 1 ] = DotProduct( si->vecs[ 1 ], vTranslated );
 996                 }
 997
 998                 /* old quake-style texturing */
 999                 else if ( g_bBrushPrimit == BPRIMIT_OLDBRUSHES ) {
1000                         /* nearest-axial projection */
1001                         dv->st[ 0 ] = s->vecs[ 0 ][ 3 ] + DotProduct( s->vecs[ 0 ], vTranslated );
1002                         dv->st[ 1 ] = s->vecs[ 1 ][ 3 ] + DotProduct( s->vecs[ 1 ], vTranslated );
1003                         dv->st[ 0 ] /= si->shaderWidth;
1004                         dv->st[ 1 ] /= si->shaderHeight;
1005                 }
1006
1007                 /* brush primitive texturing */
1008                 else
1009                 {
1010                         /* calculate texture s/t from brush primitive texture matrix */
1011                         x = DotProduct( vTranslated, texX );
1012                         y = DotProduct( vTranslated, texY );
1013                         dv->st[ 0 ] = s->texMat[ 0 ][ 0 ] * x + s->texMat[ 0 ][ 1 ] * y + s->texMat[ 0 ][ 2 ];
1014                         dv->st[ 1 ] = s->texMat[ 1 ][ 0 ] * x + s->texMat[ 1 ][ 1 ] * y + s->texMat[ 1 ][ 2 ];
1015                 }
1016
1017                 /* copy normal */
1018                 VectorCopy( mapplanes[ s->planenum ].normal, dv->normal );
1019
1020                 /* ydnar: set color */
1021                 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
1022                 {
1023                         dv->color[ k ][ 0 ] = 255;
1024                         dv->color[ k ][ 1 ] = 255;
1025                         dv->color[ k ][ 2 ] = 255;
1026
1027                         /* ydnar: gs mods: handle indexed shader blending */
1028                         dv->color[ k ][ 3 ] = ( indexed ? shaderIndexes[ j ] : 255 );
1029                 }
1030         }
1031
1032         /* set cel shader */
1033         ds->celShader = b->celShader;
1034
1035         /* set shade angle */
1036         if ( b->shadeAngleDegrees > 0.0f ) {
1037                 ds->shadeAngleDegrees = b->shadeAngleDegrees;
1038         }
1039
1040         /* ydnar: gs mods: moved st biasing elsewhere */
1041         return ds;
1042 }
1043
1044
1045
1046 /*
1047    DrawSurfaceForMesh()
1048    moved here from patch.c
1049  */
1050
1051 #define YDNAR_NORMAL_EPSILON 0.50f
1052
1053 qboolean VectorCompareExt( vec3_t n1, vec3_t n2, float epsilon ){
1054         int i;
1055
1056
1057         /* test */
1058         for ( i = 0; i < 3; i++ )
1059                 if ( fabs( n1[ i ] - n2[ i ] ) > epsilon ) {
1060                         return qfalse;
1061                 }
1062         return qtrue;
1063 }
1064
1065 mapDrawSurface_t *DrawSurfaceForMesh( entity_t *e, parseMesh_t *p, mesh_t *mesh ){
1066         int i, k, numVerts;
1067         vec4_t plane;
1068         qboolean planar;
1069         float dist;
1070         mapDrawSurface_t    *ds;
1071         shaderInfo_t        *si, *parent;
1072         bspDrawVert_t       *dv;
1073         vec3_t vTranslated;
1074         mesh_t              *copy;
1075         qboolean indexed;
1076         byte shaderIndexes[ MAX_EXPANDED_AXIS * MAX_EXPANDED_AXIS ];
1077         float offsets[ MAX_EXPANDED_AXIS * MAX_EXPANDED_AXIS ];
1078
1079
1080         /* get mesh and shader shader */
1081         if ( mesh == NULL ) {
1082                 mesh = &p->mesh;
1083         }
1084         si = p->shaderInfo;
1085         if ( mesh == NULL || si == NULL ) {
1086                 return NULL;
1087         }
1088
1089         /* get vertex count */
1090         numVerts = mesh->width * mesh->height;
1091
1092         /* to make valid normals for patches with degenerate edges,
1093            we need to make a copy of the mesh and put the aproximating
1094            points onto the curve */
1095
1096         /* create a copy of the mesh */
1097         copy = CopyMesh( mesh );
1098
1099         /* store off the original (potentially bad) normals */
1100         MakeMeshNormals( *copy );
1101         for ( i = 0; i < numVerts; i++ )
1102                 VectorCopy( copy->verts[ i ].normal, mesh->verts[ i ].normal );
1103
1104         /* put the mesh on the curve */
1105         PutMeshOnCurve( *copy );
1106
1107         /* find new normals (to take into account degenerate/flipped edges */
1108         MakeMeshNormals( *copy );
1109         for ( i = 0; i < numVerts; i++ )
1110         {
1111                 /* ydnar: only copy normals that are significantly different from the originals */
1112                 if ( DotProduct( copy->verts[ i ].normal, mesh->verts[ i ].normal ) < 0.75f ) {
1113                         VectorCopy( copy->verts[ i ].normal, mesh->verts[ i ].normal );
1114                 }
1115         }
1116
1117         /* free the old mesh */
1118         FreeMesh( copy );
1119
1120         /* ydnar: gs mods: check for indexed shader */
1121         if ( si->indexed && p->im != NULL ) {
1122                 /* indexed */
1123                 indexed = qtrue;
1124
1125                 /* get shader indexes for each point */
1126                 for ( i = 0; i < numVerts; i++ )
1127                 {
1128                         shaderIndexes[ i ] = GetShaderIndexForPoint( p->im, p->eMins, p->eMaxs, mesh->verts[ i ].xyz );
1129                         offsets[ i ] = p->im->offsets[ shaderIndexes[ i ] ];
1130                 }
1131
1132                 /* get matching shader and set alpha */
1133                 parent = si;
1134                 si = GetIndexedShader( parent, p->im, numVerts, shaderIndexes );
1135         }
1136         else{
1137                 indexed = qfalse;
1138         }
1139
1140
1141         /* ydnar: gs mods */
1142         ds = AllocDrawSurface( SURFACE_PATCH );
1143         ds->entityNum = p->entityNum;
1144         ds->castShadows = p->castShadows;
1145         ds->recvShadows = p->recvShadows;
1146
1147         ds->shaderInfo = si;
1148         ds->mapMesh = p;
1149         ds->sampleSize = p->lightmapSampleSize;
1150         ds->lightmapScale = p->lightmapScale;   /* ydnar */
1151         ds->patchWidth = mesh->width;
1152         ds->patchHeight = mesh->height;
1153         ds->numVerts = ds->patchWidth * ds->patchHeight;
1154         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
1155         memcpy( ds->verts, mesh->verts, ds->numVerts * sizeof( *ds->verts ) );
1156
1157         ds->fogNum = -1;
1158         ds->planeNum = -1;
1159
1160         ds->longestCurve = p->longestCurve;
1161         ds->maxIterations = p->maxIterations;
1162
1163         /* construct a plane from the first vert */
1164         VectorCopy( mesh->verts[ 0 ].normal, plane );
1165         plane[ 3 ] = DotProduct( mesh->verts[ 0 ].xyz, plane );
1166         planar = qtrue;
1167
1168         /* spew forth errors */
1169         if ( VectorLength( plane ) < 0.001f ) {
1170                 Sys_Printf( "DrawSurfaceForMesh: bogus plane\n" );
1171         }
1172
1173         /* test each vert */
1174         for ( i = 1; i < ds->numVerts && planar; i++ )
1175         {
1176                 /* normal test */
1177                 if ( VectorCompare( plane, mesh->verts[ i ].normal ) == qfalse ) {
1178                         planar = qfalse;
1179                 }
1180
1181                 /* point-plane test */
1182                 dist = DotProduct( mesh->verts[ i ].xyz, plane ) - plane[ 3 ];
1183                 if ( fabs( dist ) > EQUAL_EPSILON ) {
1184                         planar = qfalse;
1185                 }
1186         }
1187
1188         /* add a map plane */
1189         if ( planar ) {
1190                 /* make a map plane */
1191                 ds->planeNum = FindFloatPlane( plane, plane[ 3 ], 1, &mesh->verts[ 0 ].xyz );
1192                 VectorCopy( plane, ds->lightmapVecs[ 2 ] );
1193
1194                 /* push this normal to all verts (ydnar 2003-02-14: bad idea, small patches get screwed up) */
1195                 for ( i = 0; i < ds->numVerts; i++ )
1196                         VectorCopy( plane, ds->verts[ i ].normal );
1197         }
1198
1199         /* walk the verts to do special stuff */
1200         for ( i = 0; i < ds->numVerts; i++ )
1201         {
1202                 /* get the drawvert */
1203                 dv = &ds->verts[ i ];
1204
1205                 /* ydnar: tek-fu celshading support for flat shaded shit */
1206                 if ( flat ) {
1207                         dv->st[ 0 ] = si->stFlat[ 0 ];
1208                         dv->st[ 1 ] = si->stFlat[ 1 ];
1209                 }
1210
1211                 /* ydnar: gs mods: added support for explicit shader texcoord generation */
1212                 else if ( si->tcGen ) {
1213                         /* translate by origin and project the texture */
1214                         VectorAdd( dv->xyz, e->origin, vTranslated );
1215                         dv->st[ 0 ] = DotProduct( si->vecs[ 0 ], vTranslated );
1216                         dv->st[ 1 ] = DotProduct( si->vecs[ 1 ], vTranslated );
1217                 }
1218
1219                 /* ydnar: set color */
1220                 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
1221                 {
1222                         dv->color[ k ][ 0 ] = 255;
1223                         dv->color[ k ][ 1 ] = 255;
1224                         dv->color[ k ][ 2 ] = 255;
1225
1226                         /* ydnar: gs mods: handle indexed shader blending */
1227                         dv->color[ k ][ 3 ] = ( indexed ? shaderIndexes[ i ] : 255 );
1228                 }
1229
1230                 /* ydnar: offset */
1231                 if ( indexed ) {
1232                         dv->xyz[ 2 ] += offsets[ i ];
1233                 }
1234         }
1235
1236         /* set cel shader */
1237         ds->celShader = p->celShader;
1238
1239         /* return the drawsurface */
1240         return ds;
1241 }
1242
1243
1244
1245 /*
1246    DrawSurfaceForFlare() - ydnar
1247    creates a flare draw surface
1248  */
1249
1250 mapDrawSurface_t *DrawSurfaceForFlare( int entNum, vec3_t origin, vec3_t normal, vec3_t color, const char *flareShader, int lightStyle ){
1251         mapDrawSurface_t    *ds;
1252
1253
1254         /* emit flares? */
1255         if ( emitFlares == qfalse ) {
1256                 return NULL;
1257         }
1258
1259         /* allocate drawsurface */
1260         ds = AllocDrawSurface( SURFACE_FLARE );
1261         ds->entityNum = entNum;
1262
1263         /* set it up */
1264         if ( flareShader != NULL && flareShader[ 0 ] != '\0' ) {
1265                 ds->shaderInfo = ShaderInfoForShader( flareShader );
1266         }
1267         else{
1268                 ds->shaderInfo = ShaderInfoForShader( game->flareShader );
1269         }
1270         if ( origin != NULL ) {
1271                 VectorCopy( origin, ds->lightmapOrigin );
1272         }
1273         if ( normal != NULL ) {
1274                 VectorCopy( normal, ds->lightmapVecs[ 2 ] );
1275         }
1276         if ( color != NULL ) {
1277                 VectorCopy( color, ds->lightmapVecs[ 0 ] );
1278         }
1279
1280         /* store light style */
1281         ds->lightStyle = lightStyle;
1282         if ( ds->lightStyle < 0 || ds->lightStyle >= LS_NONE ) {
1283                 ds->lightStyle = LS_NORMAL;
1284         }
1285
1286         /* fixme: fog */
1287
1288         /* return to sender */
1289         return ds;
1290 }
1291
1292
1293
1294 /*
1295    DrawSurfaceForShader() - ydnar
1296    creates a bogus surface to forcing the game to load a shader
1297  */
1298
1299 mapDrawSurface_t *DrawSurfaceForShader( char *shader ){
1300         int i;
1301         shaderInfo_t        *si;
1302         mapDrawSurface_t    *ds;
1303
1304
1305         /* get shader */
1306         si = ShaderInfoForShader( shader );
1307
1308         /* find existing surface */
1309         for ( i = 0; i < numMapDrawSurfs; i++ )
1310         {
1311                 /* get surface */
1312                 ds = &mapDrawSurfs[ i ];
1313
1314                 /* check it */
1315                 if ( ds->shaderInfo == si ) {
1316                         return ds;
1317                 }
1318         }
1319
1320         /* create a new surface */
1321         ds = AllocDrawSurface( SURFACE_SHADER );
1322         ds->entityNum = 0;
1323         ds->shaderInfo = ShaderInfoForShader( shader );
1324
1325         /* return to sender */
1326         return ds;
1327 }
1328
1329
1330
1331 /*
1332    AddSurfaceFlare() - ydnar
1333    creates flares (coronas) centered on surfaces
1334  */
1335
1336 static void AddSurfaceFlare( mapDrawSurface_t *ds, vec3_t entityOrigin ){
1337         vec3_t origin;
1338         int i;
1339
1340
1341         /* find centroid */
1342         VectorClear( origin );
1343         for ( i = 0; i < ds->numVerts; i++ )
1344                 VectorAdd( origin, ds->verts[ i ].xyz, origin );
1345         VectorScale( origin, ( 1.0f / ds->numVerts ), origin );
1346         if ( entityOrigin != NULL ) {
1347                 VectorAdd( origin, entityOrigin, origin );
1348         }
1349
1350         /* push origin off surface a bit */
1351         VectorMA( origin, 2.0f,  ds->lightmapVecs[ 2 ], origin );
1352
1353         /* create the drawsurface */
1354         DrawSurfaceForFlare( ds->entityNum, origin, ds->lightmapVecs[ 2 ], ds->shaderInfo->color, ds->shaderInfo->flareShader, ds->shaderInfo->lightStyle );
1355 }
1356
1357
1358
1359 /*
1360    SubdivideFace()
1361    subdivides a face surface until it is smaller than the specified size (subdivisions)
1362  */
1363
1364 static void SubdivideFace_r( entity_t *e, brush_t *brush, side_t *side, winding_t *w, int fogNum, float subdivisions ){
1365         int i;
1366         int axis;
1367         vec3_t bounds[ 2 ];
1368         const float epsilon = 0.1;
1369         int subFloor, subCeil;
1370         winding_t           *frontWinding, *backWinding;
1371         mapDrawSurface_t    *ds;
1372
1373
1374         /* dummy check */
1375         if ( w == NULL ) {
1376                 return;
1377         }
1378         if ( w->numpoints < 3 ) {
1379                 Error( "SubdivideFace_r: Bad w->numpoints (%d < 3)", w->numpoints );
1380         }
1381
1382         /* determine surface bounds */
1383         ClearBounds( bounds[ 0 ], bounds[ 1 ] );
1384         for ( i = 0; i < w->numpoints; i++ )
1385                 AddPointToBounds( w->p[ i ], bounds[ 0 ], bounds[ 1 ] );
1386
1387         /* split the face */
1388         for ( axis = 0; axis < 3; axis++ )
1389         {
1390                 vec3_t planePoint = { 0, 0, 0 };
1391                 vec3_t planeNormal = { 0, 0, 0 };
1392                 float d;
1393
1394
1395                 /* create an axial clipping plane */
1396                 subFloor = floor( bounds[ 0 ][ axis ] / subdivisions ) * subdivisions;
1397                 subCeil = ceil( bounds[ 1 ][ axis ] / subdivisions ) * subdivisions;
1398                 planePoint[ axis ] = subFloor + subdivisions;
1399                 planeNormal[ axis ] = -1;
1400                 d = DotProduct( planePoint, planeNormal );
1401
1402                 /* subdivide if necessary */
1403                 if ( ( subCeil - subFloor ) > subdivisions ) {
1404                         /* clip the winding */
1405                         ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding ); /* not strict; we assume we always keep a winding */
1406
1407                         /* the clip may not produce two polygons if it was epsilon close */
1408                         if ( frontWinding == NULL ) {
1409                                 w = backWinding;
1410                         }
1411                         else if ( backWinding == NULL ) {
1412                                 w = frontWinding;
1413                         }
1414                         else
1415                         {
1416                                 SubdivideFace_r( e, brush, side, frontWinding, fogNum, subdivisions );
1417                                 SubdivideFace_r( e, brush, side, backWinding, fogNum, subdivisions );
1418                                 return;
1419                         }
1420                 }
1421         }
1422
1423         /* create a face surface */
1424         ds = DrawSurfaceForSide( e, brush, side, w );
1425
1426         /* set correct fog num */
1427         ds->fogNum = fogNum;
1428 }
1429
1430
1431
1432 /*
1433    SubdivideFaceSurfaces()
1434    chop up brush face surfaces that have subdivision attributes
1435    ydnar: and subdivide surfaces that exceed specified texture coordinate range
1436  */
1437
1438 void SubdivideFaceSurfaces( entity_t *e, tree_t *tree ){
1439         int i, j, numBaseDrawSurfs, fogNum;
1440         mapDrawSurface_t    *ds;
1441         brush_t             *brush;
1442         side_t              *side;
1443         shaderInfo_t        *si;
1444         winding_t           *w;
1445         float range, size, subdivisions, s2;
1446
1447
1448         /* note it */
1449         Sys_FPrintf( SYS_VRB, "--- SubdivideFaceSurfaces ---\n" );
1450
1451         /* walk the list of surfaces */
1452         numBaseDrawSurfs = numMapDrawSurfs;
1453         for ( i = e->firstDrawSurf; i < numBaseDrawSurfs; i++ )
1454         {
1455                 /* get surface */
1456                 ds = &mapDrawSurfs[ i ];
1457
1458                 /* only subdivide brush sides */
1459                 if ( ds->type != SURFACE_FACE || ds->mapBrush == NULL || ds->sideRef == NULL || ds->sideRef->side == NULL ) {
1460                         continue;
1461                 }
1462
1463                 /* get bits */
1464                 brush = ds->mapBrush;
1465                 side = ds->sideRef->side;
1466
1467                 /* check subdivision for shader */
1468                 si = side->shaderInfo;
1469                 if ( si == NULL ) {
1470                         continue;
1471                 }
1472
1473                 /* ydnar: don't subdivide sky surfaces */
1474                 if ( si->compileFlags & C_SKY ) {
1475                         continue;
1476                 }
1477
1478                 /* do texture coordinate range check */
1479                 ClassifySurfaces( 1, ds );
1480                 if ( CalcSurfaceTextureRange( ds ) == qfalse ) {
1481                         /* calculate subdivisions texture range (this code is shit) */
1482                         range = ( ds->texRange[ 0 ] > ds->texRange[ 1 ] ? ds->texRange[ 0 ] : ds->texRange[ 1 ] );
1483                         size = ds->maxs[ 0 ] - ds->mins[ 0 ];
1484                         for ( j = 1; j < 3; j++ )
1485                                 if ( ( ds->maxs[ j ] - ds->mins[ j ] ) > size ) {
1486                                         size = ds->maxs[ j ] - ds->mins[ j ];
1487                                 }
1488                         subdivisions = ( size / range ) * texRange;
1489                         subdivisions = ceil( subdivisions / 2 ) * 2;
1490                         for ( j = 1; j < 8; j++ )
1491                         {
1492                                 s2 = ceil( (float) texRange / j );
1493                                 if ( fabs( subdivisions - s2 ) <= 4.0 ) {
1494                                         subdivisions = s2;
1495                                         break;
1496                                 }
1497                         }
1498                 }
1499                 else{
1500                         subdivisions = si->subdivisions;
1501                 }
1502
1503                 /* get subdivisions from shader */
1504                 if ( si->subdivisions > 0 && si->subdivisions < subdivisions ) {
1505                         subdivisions = si->subdivisions;
1506                 }
1507                 if ( subdivisions < 1.0f ) {
1508                         continue;
1509                 }
1510
1511                 /* preserve fog num */
1512                 fogNum = ds->fogNum;
1513
1514                 /* make a winding and free the surface */
1515                 w = WindingFromDrawSurf( ds );
1516                 ClearSurface( ds );
1517
1518                 /* subdivide it */
1519                 SubdivideFace_r( e, brush, side, w, fogNum, subdivisions );
1520         }
1521 }
1522
1523
1524
1525 /*
1526    ====================
1527    ClipSideIntoTree_r
1528
1529    Adds non-opaque leaf fragments to the convex hull
1530    ====================
1531  */
1532
1533 void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node ){
1534         plane_t         *plane;
1535         winding_t       *front, *back;
1536
1537         if ( !w ) {
1538                 return;
1539         }
1540
1541         if ( node->planenum != PLANENUM_LEAF ) {
1542                 if ( side->planenum == node->planenum ) {
1543                         ClipSideIntoTree_r( w, side, node->children[0] );
1544                         return;
1545                 }
1546                 if ( side->planenum == ( node->planenum ^ 1 ) ) {
1547                         ClipSideIntoTree_r( w, side, node->children[1] );
1548                         return;
1549                 }
1550
1551                 plane = &mapplanes[ node->planenum ];
1552                 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1553                                                                   ON_EPSILON, &front, &back ); /* strict, we handle the "winding disappeared" case */
1554                 if ( !front && !back ) {
1555                         /* in doubt, register it in both nodes */
1556                         front = CopyWinding( w );
1557                         back = CopyWinding( w );
1558                 }
1559                 FreeWinding( w );
1560
1561                 ClipSideIntoTree_r( front, side, node->children[0] );
1562                 ClipSideIntoTree_r( back, side, node->children[1] );
1563
1564                 return;
1565         }
1566
1567         // if opaque leaf, don't add
1568         if ( !node->opaque ) {
1569                 AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal );
1570         }
1571
1572         FreeWinding( w );
1573         return;
1574 }
1575
1576
1577
1578
1579
1580 static int g_numHiddenFaces, g_numCoinFaces;
1581
1582
1583
1584 /*
1585    CullVectorCompare() - ydnar
1586    compares two vectors with an epsilon
1587  */
1588
1589 #define CULL_EPSILON 0.1f
1590
1591 qboolean CullVectorCompare( const vec3_t v1, const vec3_t v2 ){
1592         int i;
1593
1594
1595         for ( i = 0; i < 3; i++ )
1596                 if ( fabs( v1[ i ] - v2[ i ] ) > CULL_EPSILON ) {
1597                         return qfalse;
1598                 }
1599         return qtrue;
1600 }
1601
1602
1603
1604 /*
1605    SideInBrush() - ydnar
1606    determines if a brushside lies inside another brush
1607  */
1608
1609 qboolean SideInBrush( side_t *side, brush_t *b ){
1610         int i, s;
1611         plane_t     *plane;
1612
1613
1614         /* ignore sides w/o windings or shaders */
1615         if ( side->winding == NULL || side->shaderInfo == NULL ) {
1616                 return qtrue;
1617         }
1618
1619         /* ignore culled sides and translucent brushes */
1620         if ( side->culled == qtrue || ( b->compileFlags & C_TRANSLUCENT ) ) {
1621                 return qfalse;
1622         }
1623
1624         /* side iterator */
1625         for ( i = 0; i < b->numsides; i++ )
1626         {
1627                 /* fail if any sides are caulk */
1628                 if ( b->sides[ i ].compileFlags & C_NODRAW ) {
1629                         return qfalse;
1630                 }
1631
1632                 /* check if side's winding is on or behind the plane */
1633                 plane = &mapplanes[ b->sides[ i ].planenum ];
1634                 s = WindingOnPlaneSide( side->winding, plane->normal, plane->dist );
1635                 if ( s == SIDE_FRONT || s == SIDE_CROSS ) {
1636                         return qfalse;
1637                 }
1638         }
1639
1640         /* don't cull autosprite or polygonoffset surfaces */
1641         if ( side->shaderInfo ) {
1642                 if ( side->shaderInfo->autosprite || side->shaderInfo->polygonOffset ) {
1643                         return qfalse;
1644                 }
1645         }
1646
1647         /* inside */
1648         side->culled = qtrue;
1649         g_numHiddenFaces++;
1650         return qtrue;
1651 }
1652
1653
1654 /*
1655    CullSides() - ydnar
1656    culls obscured or buried brushsides from the map
1657  */
1658
1659 void CullSides( entity_t *e ){
1660         int numPoints;
1661         int i, j, k, l, first, second, dir;
1662         winding_t   *w1, *w2;
1663         brush_t *b1, *b2;
1664         side_t      *side1, *side2;
1665
1666
1667         /* note it */
1668         Sys_FPrintf( SYS_VRB, "--- CullSides ---\n" );
1669
1670         g_numHiddenFaces = 0;
1671         g_numCoinFaces = 0;
1672
1673         /* brush interator 1 */
1674         for ( b1 = e->brushes; b1; b1 = b1->next )
1675         {
1676                 /* sides check */
1677                 if ( b1->numsides < 1 ) {
1678                         continue;
1679                 }
1680
1681                 /* brush iterator 2 */
1682                 for ( b2 = b1->next; b2; b2 = b2->next )
1683                 {
1684                         /* sides check */
1685                         if ( b2->numsides < 1 ) {
1686                                 continue;
1687                         }
1688
1689                         /* original check */
1690                         if ( b1->original == b2->original && b1->original != NULL ) {
1691                                 continue;
1692                         }
1693
1694                         /* bbox check */
1695                         j = 0;
1696                         for ( i = 0; i < 3; i++ )
1697                                 if ( b1->mins[ i ] > b2->maxs[ i ] || b1->maxs[ i ] < b2->mins[ i ] ) {
1698                                         j++;
1699                                 }
1700                         if ( j ) {
1701                                 continue;
1702                         }
1703
1704                         /* cull inside sides */
1705                         for ( i = 0; i < b1->numsides; i++ )
1706                                 SideInBrush( &b1->sides[ i ], b2 );
1707                         for ( i = 0; i < b2->numsides; i++ )
1708                                 SideInBrush( &b2->sides[ i ], b1 );
1709
1710                         /* side iterator 1 */
1711                         for ( i = 0; i < b1->numsides; i++ )
1712                         {
1713                                 /* winding check */
1714                                 side1 = &b1->sides[ i ];
1715                                 w1 = side1->winding;
1716                                 if ( w1 == NULL ) {
1717                                         continue;
1718                                 }
1719                                 numPoints = w1->numpoints;
1720                                 if ( side1->shaderInfo == NULL ) {
1721                                         continue;
1722                                 }
1723
1724                                 /* side iterator 2 */
1725                                 for ( j = 0; j < b2->numsides; j++ )
1726                                 {
1727                                         /* winding check */
1728                                         side2 = &b2->sides[ j ];
1729                                         w2 = side2->winding;
1730                                         if ( w2 == NULL ) {
1731                                                 continue;
1732                                         }
1733                                         if ( side2->shaderInfo == NULL ) {
1734                                                 continue;
1735                                         }
1736                                         if ( w1->numpoints != w2->numpoints ) {
1737                                                 continue;
1738                                         }
1739                                         if ( side1->culled == qtrue && side2->culled == qtrue ) {
1740                                                 continue;
1741                                         }
1742
1743                                         /* compare planes */
1744                                         if ( ( side1->planenum & ~0x00000001 ) != ( side2->planenum & ~0x00000001 ) ) {
1745                                                 continue;
1746                                         }
1747
1748                                         /* get autosprite and polygonoffset status */
1749                                         if ( side1->shaderInfo &&
1750                                                  ( side1->shaderInfo->autosprite || side1->shaderInfo->polygonOffset ) ) {
1751                                                 continue;
1752                                         }
1753                                         if ( side2->shaderInfo &&
1754                                                  ( side2->shaderInfo->autosprite || side2->shaderInfo->polygonOffset ) ) {
1755                                                 continue;
1756                                         }
1757
1758                                         /* find first common point */
1759                                         first = -1;
1760                                         for ( k = 0; k < numPoints; k++ )
1761                                         {
1762                                                 if ( VectorCompare( w1->p[ 0 ], w2->p[ k ] ) ) {
1763                                                         first = k;
1764                                                         k = numPoints;
1765                                                 }
1766                                         }
1767                                         if ( first == -1 ) {
1768                                                 continue;
1769                                         }
1770
1771                                         /* find second common point (regardless of winding order) */
1772                                         second = -1;
1773                                         dir = 0;
1774                                         if ( ( first + 1 ) < numPoints ) {
1775                                                 second = first + 1;
1776                                         }
1777                                         else{
1778                                                 second = 0;
1779                                         }
1780                                         if ( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) ) {
1781                                                 dir = 1;
1782                                         }
1783                                         else
1784                                         {
1785                                                 if ( first > 0 ) {
1786                                                         second = first - 1;
1787                                                 }
1788                                                 else{
1789                                                         second = numPoints - 1;
1790                                                 }
1791                                                 if ( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) ) {
1792                                                         dir = -1;
1793                                                 }
1794                                         }
1795                                         if ( dir == 0 ) {
1796                                                 continue;
1797                                         }
1798
1799                                         /* compare the rest of the points */
1800                                         l = first;
1801                                         for ( k = 0; k < numPoints; k++ )
1802                                         {
1803                                                 if ( !CullVectorCompare( w1->p[ k ], w2->p[ l ] ) ) {
1804                                                         k = 100000;
1805                                                 }
1806
1807                                                 l += dir;
1808                                                 if ( l < 0 ) {
1809                                                         l = numPoints - 1;
1810                                                 }
1811                                                 else if ( l >= numPoints ) {
1812                                                         l = 0;
1813                                                 }
1814                                         }
1815                                         if ( k >= 100000 ) {
1816                                                 continue;
1817                                         }
1818
1819                                         /* cull face 1 */
1820                                         if ( !side2->culled && !( side2->compileFlags & C_TRANSLUCENT ) && !( side2->compileFlags & C_NODRAW ) ) {
1821                                                 side1->culled = qtrue;
1822                                                 g_numCoinFaces++;
1823                                         }
1824
1825                                         if ( side1->planenum == side2->planenum && side1->culled == qtrue ) {
1826                                                 continue;
1827                                         }
1828
1829                                         /* cull face 2 */
1830                                         if ( !side1->culled && !( side1->compileFlags & C_TRANSLUCENT ) && !( side1->compileFlags & C_NODRAW ) ) {
1831                                                 side2->culled = qtrue;
1832                                                 g_numCoinFaces++;
1833                                         }
1834                                 }
1835                         }
1836                 }
1837         }
1838
1839         /* emit some stats */
1840         Sys_FPrintf( SYS_VRB, "%9d hidden faces culled\n", g_numHiddenFaces );
1841         Sys_FPrintf( SYS_VRB, "%9d coincident faces culled\n", g_numCoinFaces );
1842 }
1843
1844
1845
1846
1847 /*
1848    ClipSidesIntoTree()
1849
1850    creates side->visibleHull for all visible sides
1851
1852    the drawsurf for a side will consist of the convex hull of
1853    all points in non-opaque clusters, which allows overlaps
1854    to be trimmed off automatically.
1855  */
1856
1857 void ClipSidesIntoTree( entity_t *e, tree_t *tree ){
1858         brush_t     *b;
1859         int i;
1860         winding_t       *w;
1861         side_t          *side, *newSide;
1862         shaderInfo_t    *si;
1863
1864
1865         /* ydnar: cull brush sides */
1866         CullSides( e );
1867
1868         /* note it */
1869         Sys_FPrintf( SYS_VRB, "--- ClipSidesIntoTree ---\n" );
1870
1871         /* walk the brush list */
1872         for ( b = e->brushes; b; b = b->next )
1873         {
1874                 /* walk the brush sides */
1875                 for ( i = 0; i < b->numsides; i++ )
1876                 {
1877                         /* get side */
1878                         side = &b->sides[ i ];
1879                         if ( side->winding == NULL ) {
1880                                 continue;
1881                         }
1882
1883                         /* copy the winding */
1884                         w = CopyWinding( side->winding );
1885                         side->visibleHull = NULL;
1886                         ClipSideIntoTree_r( w, side, tree->headnode );
1887
1888                         /* anything left? */
1889                         w = side->visibleHull;
1890                         if ( w == NULL ) {
1891                                 continue;
1892                         }
1893
1894                         /* shader? */
1895                         si = side->shaderInfo;
1896                         if ( si == NULL ) {
1897                                 continue;
1898                         }
1899
1900                         /* don't create faces for non-visible sides */
1901                         /* ydnar: except indexed shaders, like common/terrain and nodraw fog surfaces */
1902                         if ( ( si->compileFlags & C_NODRAW ) && si->indexed == qfalse && !( si->compileFlags & C_FOG ) ) {
1903                                 continue;
1904                         }
1905
1906                         /* always use the original winding for autosprites and noclip faces */
1907                         if ( si->autosprite || si->noClip ) {
1908                                 w = side->winding;
1909                         }
1910
1911                         /* save this winding as a visible surface */
1912                         DrawSurfaceForSide( e, b, side, w );
1913
1914                         /* make a back side for fog */
1915                         if ( !( si->compileFlags & C_FOG ) ) {
1916                                 continue;
1917                         }
1918
1919                         /* duplicate the up-facing side */
1920                         w = ReverseWinding( w );
1921                         newSide = safe_malloc( sizeof( *side ) );
1922                         *newSide = *side;
1923                         newSide->visibleHull = w;
1924                         newSide->planenum ^= 1;
1925
1926                         /* save this winding as a visible surface */
1927                         DrawSurfaceForSide( e, b, newSide, w );
1928                 }
1929         }
1930 }
1931
1932
1933
1934 /*
1935
1936    this section deals with filtering drawsurfaces into the bsp tree,
1937    adding references to each leaf a surface touches
1938
1939  */
1940
1941 /*
1942    AddReferenceToLeaf() - ydnar
1943    adds a reference to surface ds in the bsp leaf node
1944  */
1945
1946 int AddReferenceToLeaf( mapDrawSurface_t *ds, node_t *node ){
1947         drawSurfRef_t   *dsr;
1948
1949
1950         /* dummy check */
1951         if ( node->planenum != PLANENUM_LEAF || node->opaque ) {
1952                 return 0;
1953         }
1954
1955         /* try to find an existing reference */
1956         for ( dsr = node->drawSurfReferences; dsr; dsr = dsr->nextRef )
1957         {
1958                 if ( dsr->outputNum == numBSPDrawSurfaces ) {
1959                         return 0;
1960                 }
1961         }
1962
1963         /* add a new reference */
1964         dsr = safe_malloc( sizeof( *dsr ) );
1965         dsr->outputNum = numBSPDrawSurfaces;
1966         dsr->nextRef = node->drawSurfReferences;
1967         node->drawSurfReferences = dsr;
1968
1969         /* ydnar: sky/skybox surfaces */
1970         if ( node->skybox ) {
1971                 ds->skybox = qtrue;
1972         }
1973         if ( ds->shaderInfo->compileFlags & C_SKY ) {
1974                 node->sky = qtrue;
1975         }
1976
1977         /* return */
1978         return 1;
1979 }
1980
1981
1982
1983 /*
1984    AddReferenceToTree_r() - ydnar
1985    adds a reference to the specified drawsurface to every leaf in the tree
1986  */
1987
1988 int AddReferenceToTree_r( mapDrawSurface_t *ds, node_t *node, qboolean skybox ){
1989         int i, refs = 0;
1990
1991
1992         /* dummy check */
1993         if ( node == NULL ) {
1994                 return 0;
1995         }
1996
1997         /* is this a decision node? */
1998         if ( node->planenum != PLANENUM_LEAF ) {
1999                 /* add to child nodes and return */
2000                 refs += AddReferenceToTree_r( ds, node->children[ 0 ], skybox );
2001                 refs += AddReferenceToTree_r( ds, node->children[ 1 ], skybox );
2002                 return refs;
2003         }
2004
2005         /* ydnar */
2006         if ( skybox ) {
2007                 /* skybox surfaces only get added to sky leaves */
2008                 if ( !node->sky ) {
2009                         return 0;
2010                 }
2011
2012                 /* increase the leaf bounds */
2013                 for ( i = 0; i < ds->numVerts; i++ )
2014                         AddPointToBounds( ds->verts[ i ].xyz, node->mins, node->maxs );
2015         }
2016
2017         /* add a reference */
2018         return AddReferenceToLeaf( ds, node );
2019 }
2020
2021
2022
2023 /*
2024    FilterPointIntoTree_r() - ydnar
2025    filters a single point from a surface into the tree
2026  */
2027
2028 int FilterPointIntoTree_r( vec3_t point, mapDrawSurface_t *ds, node_t *node ){
2029         float d;
2030         plane_t         *plane;
2031         int refs = 0;
2032
2033
2034         /* is this a decision node? */
2035         if ( node->planenum != PLANENUM_LEAF ) {
2036                 /* classify the point in relation to the plane */
2037                 plane = &mapplanes[ node->planenum ];
2038                 d = DotProduct( point, plane->normal ) - plane->dist;
2039
2040                 /* filter by this plane */
2041                 refs = 0;
2042                 if ( d >= -ON_EPSILON ) {
2043                         refs += FilterPointIntoTree_r( point, ds, node->children[ 0 ] );
2044                 }
2045                 if ( d <= ON_EPSILON ) {
2046                         refs += FilterPointIntoTree_r( point, ds, node->children[ 1 ] );
2047                 }
2048
2049                 /* return */
2050                 return refs;
2051         }
2052
2053         /* add a reference */
2054         return AddReferenceToLeaf( ds, node );
2055 }
2056
2057
2058
2059 /*
2060    FilterPointConvexHullIntoTree_r() - ydnar
2061    filters the convex hull of multiple points from a surface into the tree
2062  */
2063
2064 int FilterPointConvexHullIntoTree_r( vec3_t **points, int npoints, mapDrawSurface_t *ds, node_t *node ){
2065         float d, dmin, dmax;
2066         plane_t         *plane;
2067         int refs = 0;
2068         int i;
2069
2070         if ( !points ) {
2071                 return 0;
2072         }
2073
2074         /* is this a decision node? */
2075         if ( node->planenum != PLANENUM_LEAF ) {
2076                 /* classify the point in relation to the plane */
2077                 plane = &mapplanes[ node->planenum ];
2078
2079                 dmin = dmax = DotProduct( *( points[0] ), plane->normal ) - plane->dist;
2080                 for ( i = 1; i < npoints; ++i )
2081                 {
2082                         d = DotProduct( *( points[i] ), plane->normal ) - plane->dist;
2083                         if ( d > dmax ) {
2084                                 dmax = d;
2085                         }
2086                         if ( d < dmin ) {
2087                                 dmin = d;
2088                         }
2089                 }
2090
2091                 /* filter by this plane */
2092                 refs = 0;
2093                 if ( dmax >= -ON_EPSILON ) {
2094                         refs += FilterPointConvexHullIntoTree_r( points, npoints, ds, node->children[ 0 ] );
2095                 }
2096                 if ( dmin <= ON_EPSILON ) {
2097                         refs += FilterPointConvexHullIntoTree_r( points, npoints, ds, node->children[ 1 ] );
2098                 }
2099
2100                 /* return */
2101                 return refs;
2102         }
2103
2104         /* add a reference */
2105         return AddReferenceToLeaf( ds, node );
2106 }
2107
2108
2109
2110 /*
2111    FilterWindingIntoTree_r() - ydnar
2112    filters a winding from a drawsurface into the tree
2113  */
2114
2115 int FilterWindingIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node ){
2116         int i, refs = 0;
2117         plane_t         *p1;
2118         vec4_t plane1;
2119         winding_t       *fat, *front, *back;
2120         shaderInfo_t    *si;
2121
2122
2123         /* get shaderinfo */
2124         si = ds->shaderInfo;
2125
2126         /* ydnar: is this the head node? */
2127         if ( node->parent == NULL && si != NULL &&
2128                  ( si->mins[ 0 ] != 0.0f || si->maxs[ 0 ] != 0.0f ||
2129                    si->mins[ 1 ] != 0.0f || si->maxs[ 1 ] != 0.0f ||
2130                    si->mins[ 2 ] != 0.0f || si->maxs[ 2 ] != 0.0f ) ) {
2131                 static qboolean warned = qfalse;
2132                 if ( !warned ) {
2133                         Sys_FPrintf( SYS_WRN, "WARNING: this map uses the deformVertexes move hack\n" );
2134                         warned = qtrue;
2135                 }
2136
2137                 /* 'fatten' the winding by the shader mins/maxs (parsed from vertexDeform move) */
2138                 /* note this winding is completely invalid (concave, nonplanar, etc) */
2139                 fat = AllocWinding( w->numpoints * 3 + 3 );
2140                 fat->numpoints = w->numpoints * 3 + 3;
2141                 for ( i = 0; i < w->numpoints; i++ )
2142                 {
2143                         VectorCopy( w->p[ i ], fat->p[ i ] );
2144                         VectorAdd( w->p[ i ], si->mins, fat->p[ i + ( w->numpoints + 1 ) ] );
2145                         VectorAdd( w->p[ i ], si->maxs, fat->p[ i + ( w->numpoints + 1 ) * 2 ] );
2146                 }
2147                 VectorCopy( w->p[ 0 ], fat->p[ i ] );
2148                 VectorAdd( w->p[ 0 ], si->mins, fat->p[ i + w->numpoints ] );
2149                 VectorAdd( w->p[ 0 ], si->maxs, fat->p[ i + w->numpoints * 2 ] );
2150
2151                 /*
2152                  * note: this winding is STILL not suitable for ClipWindingEpsilon, and
2153                  * also does not really fulfill the intention as it only contains
2154                  * origin, +mins, +maxs, but thanks to the "closing" points I just
2155                  * added to the three sub-windings, the fattening at least doesn't make
2156                  * it worse
2157                  */
2158
2159                 FreeWinding( w );
2160                 w = fat;
2161         }
2162
2163         /* is this a decision node? */
2164         if ( node->planenum != PLANENUM_LEAF ) {
2165                 /* get node plane */
2166                 p1 = &mapplanes[ node->planenum ];
2167                 VectorCopy( p1->normal, plane1 );
2168                 plane1[ 3 ] = p1->dist;
2169
2170                 /* check if surface is planar */
2171                 if ( ds->planeNum >= 0 ) {
2172                         #if 0
2173                         plane_t *p2;
2174                         vec4_t plane2;
2175
2176                         /* get surface plane */
2177                         p2 = &mapplanes[ ds->planeNum ];
2178                         VectorCopy( p2->normal, plane2 );
2179                         plane2[ 3 ] = p2->dist;
2180
2181                         /* div0: this is the plague (inaccurate) */
2182                         vec4_t reverse;
2183
2184                         /* invert surface plane */
2185                         VectorSubtract( vec3_origin, plane2, reverse );
2186                         reverse[ 3 ] = -plane2[ 3 ];
2187
2188                         /* compare planes */
2189                         if ( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f ) {
2190                                 return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2191                         }
2192                         if ( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f ) {
2193                                 return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2194                         }
2195                         #else
2196                         /* div0: this is the cholera (doesn't hit enough) */
2197
2198                         /* the drawsurf might have an associated plane, if so, force a filter here */
2199                         if ( ds->planeNum == node->planenum ) {
2200                                 return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2201                         }
2202                         if ( ds->planeNum == ( node->planenum ^ 1 ) ) {
2203                                 return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2204                         }
2205                         #endif
2206                 }
2207
2208                 /* clip the winding by this plane */
2209                 ClipWindingEpsilonStrict( w, plane1, plane1[ 3 ], ON_EPSILON, &front, &back ); /* strict; we handle the "winding disappeared" case */
2210
2211                 /* filter by this plane */
2212                 refs = 0;
2213                 if ( front == NULL && back == NULL ) {
2214                         /* same plane, this is an ugly hack */
2215                         /* but better too many than too few refs */
2216                         refs += FilterWindingIntoTree_r( CopyWinding( w ), ds, node->children[ 0 ] );
2217                         refs += FilterWindingIntoTree_r( CopyWinding( w ), ds, node->children[ 1 ] );
2218                 }
2219                 if ( front != NULL ) {
2220                         refs += FilterWindingIntoTree_r( front, ds, node->children[ 0 ] );
2221                 }
2222                 if ( back != NULL ) {
2223                         refs += FilterWindingIntoTree_r( back, ds, node->children[ 1 ] );
2224                 }
2225                 FreeWinding( w );
2226
2227                 /* return */
2228                 return refs;
2229         }
2230
2231         /* add a reference */
2232         return AddReferenceToLeaf( ds, node );
2233 }
2234
2235
2236
2237 /*
2238    FilterFaceIntoTree()
2239    filters a planar winding face drawsurface into the bsp tree
2240  */
2241
2242 int FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree ){
2243         winding_t   *w;
2244         int refs = 0;
2245
2246
2247         /* make a winding and filter it into the tree */
2248         w = WindingFromDrawSurf( ds );
2249         refs = FilterWindingIntoTree_r( w, ds, tree->headnode );
2250
2251         /* return */
2252         return refs;
2253 }
2254
2255
2256
2257 /*
2258    FilterPatchIntoTree()
2259    subdivides a patch into an approximate curve and filters it into the tree
2260  */
2261
2262 #define FILTER_SUBDIVISION      8
2263
2264 static int FilterPatchIntoTree( mapDrawSurface_t *ds, tree_t *tree ){
2265         int x, y, refs = 0;
2266
2267         for ( y = 0; y + 2 < ds->patchHeight; y += 2 )
2268                 for ( x = 0; x + 2 < ds->patchWidth; x += 2 )
2269                 {
2270                         vec3_t *points[9];
2271                         points[0] = &ds->verts[( y + 0 ) * ds->patchWidth + ( x + 0 )].xyz;
2272                         points[1] = &ds->verts[( y + 0 ) * ds->patchWidth + ( x + 1 )].xyz;
2273                         points[2] = &ds->verts[( y + 0 ) * ds->patchWidth + ( x + 2 )].xyz;
2274                         points[3] = &ds->verts[( y + 1 ) * ds->patchWidth + ( x + 0 )].xyz;
2275                         points[4] = &ds->verts[( y + 1 ) * ds->patchWidth + ( x + 1 )].xyz;
2276                         points[5] = &ds->verts[( y + 1 ) * ds->patchWidth + ( x + 2 )].xyz;
2277                         points[6] = &ds->verts[( y + 2 ) * ds->patchWidth + ( x + 0 )].xyz;
2278                         points[7] = &ds->verts[( y + 2 ) * ds->patchWidth + ( x + 1 )].xyz;
2279                         points[8] = &ds->verts[( y + 2 ) * ds->patchWidth + ( x + 2 )].xyz;
2280                         refs += FilterPointConvexHullIntoTree_r( points, 9, ds, tree->headnode );
2281                 }
2282
2283         return refs;
2284 }
2285
2286
2287
2288 /*
2289    FilterTrianglesIntoTree()
2290    filters a triangle surface (meta, model) into the bsp
2291  */
2292
2293 static int FilterTrianglesIntoTree( mapDrawSurface_t *ds, tree_t *tree ){
2294         int i, refs;
2295         winding_t   *w;
2296
2297
2298         /* ydnar: gs mods: this was creating bogus triangles before */
2299         refs = 0;
2300         for ( i = 0; i < ds->numIndexes; i += 3 )
2301         {
2302                 /* error check */
2303                 if ( ds->indexes[ i ] >= ds->numVerts ||
2304                          ds->indexes[ i + 1 ] >= ds->numVerts ||
2305                          ds->indexes[ i + 2 ] >= ds->numVerts ) {
2306                         Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2307                 }
2308
2309                 /* make a triangle winding and filter it into the tree */
2310                 w = AllocWinding( 3 );
2311                 w->numpoints = 3;
2312                 VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2313                 VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2314                 VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2315                 refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2316         }
2317
2318         /* use point filtering as well */
2319         for ( i = 0; i < ds->numVerts; i++ )
2320                 refs += FilterPointIntoTree_r( ds->verts[ i ].xyz, ds, tree->headnode );
2321
2322         return refs;
2323 }
2324
2325
2326
2327 /*
2328    FilterFoliageIntoTree()
2329    filters a foliage surface (wolf et/splash damage)
2330  */
2331
2332 static int FilterFoliageIntoTree( mapDrawSurface_t *ds, tree_t *tree ){
2333         int f, i, refs;
2334         bspDrawVert_t   *instance;
2335         vec3_t xyz;
2336         winding_t       *w;
2337
2338
2339         /* walk origin list */
2340         refs = 0;
2341         for ( f = 0; f < ds->numFoliageInstances; f++ )
2342         {
2343                 /* get instance */
2344                 instance = ds->verts + ds->patchHeight + f;
2345
2346                 /* walk triangle list */
2347                 for ( i = 0; i < ds->numIndexes; i += 3 )
2348                 {
2349                         /* error check */
2350                         if ( ds->indexes[ i ] >= ds->numVerts ||
2351                                  ds->indexes[ i + 1 ] >= ds->numVerts ||
2352                                  ds->indexes[ i + 2 ] >= ds->numVerts ) {
2353                                 Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2354                         }
2355
2356                         /* make a triangle winding and filter it into the tree */
2357                         w = AllocWinding( 3 );
2358                         w->numpoints = 3;
2359                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2360                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2361                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2362                         refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2363                 }
2364
2365                 /* use point filtering as well */
2366                 for ( i = 0; i < ( ds->numVerts - ds->numFoliageInstances ); i++ )
2367                 {
2368                         VectorAdd( instance->xyz, ds->verts[ i ].xyz, xyz );
2369                         refs += FilterPointIntoTree_r( xyz, ds, tree->headnode );
2370                 }
2371         }
2372
2373         return refs;
2374 }
2375
2376
2377
2378 /*
2379    FilterFlareIntoTree()
2380    simple point filtering for flare surfaces
2381  */
2382 static int FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ){
2383         return FilterPointIntoTree_r( ds->lightmapOrigin, ds, tree->headnode );
2384 }
2385
2386
2387
2388 /*
2389    EmitDrawVerts() - ydnar
2390    emits bsp drawverts from a map drawsurface
2391  */
2392
2393 void EmitDrawVerts( mapDrawSurface_t *ds, bspDrawSurface_t *out ){
2394         int i, k;
2395         bspDrawVert_t   *dv;
2396         shaderInfo_t    *si;
2397         float offset;
2398
2399
2400         /* get stuff */
2401         si = ds->shaderInfo;
2402         offset = si->offset;
2403
2404         /* copy the verts */
2405         out->firstVert = numBSPDrawVerts;
2406         out->numVerts = ds->numVerts;
2407         for ( i = 0; i < ds->numVerts; i++ )
2408         {
2409                 /* allocate a new vert */
2410                 IncDrawVerts();
2411                 dv = &bspDrawVerts[ numBSPDrawVerts - 1 ];
2412
2413                 /* copy it */
2414                 memcpy( dv, &ds->verts[ i ], sizeof( *dv ) );
2415
2416                 /* offset? */
2417                 if ( offset != 0.0f ) {
2418                         VectorMA( dv->xyz, offset, dv->normal, dv->xyz );
2419                 }
2420
2421                 /* expand model bounds
2422                    necessary because of misc_model surfaces on entities
2423                    note: does not happen on worldspawn as its bounds is only used for determining lightgrid bounds */
2424                 if ( numBSPModels > 0 ) {
2425                         AddPointToBounds( dv->xyz, bspModels[ numBSPModels ].mins, bspModels[ numBSPModels ].maxs );
2426                 }
2427
2428                 /* debug color? */
2429                 if ( debugSurfaces ) {
2430                         for ( k = 0; k < MAX_LIGHTMAPS; k++ )
2431                                 VectorCopy( debugColors[ ( ds - mapDrawSurfs ) % 12 ], dv->color[ k ] );
2432                 }
2433         }
2434 }
2435
2436
2437
2438 /*
2439    FindDrawIndexes() - ydnar
2440    this attempts to find a run of indexes in the bsp that match the given indexes
2441    this tends to reduce the size of the bsp index pool by 1/3 or more
2442    returns numIndexes + 1 if the search failed
2443  */
2444
2445 int FindDrawIndexes( int numIndexes, int *indexes ){
2446         int i, j, numTestIndexes;
2447
2448
2449         /* dummy check */
2450         if ( numIndexes < 3 || numBSPDrawIndexes < numIndexes || indexes == NULL ) {
2451                 return numBSPDrawIndexes;
2452         }
2453
2454         /* set limit */
2455         numTestIndexes = 1 + numBSPDrawIndexes - numIndexes;
2456
2457         /* handle 3 indexes as a special case for performance */
2458         if ( numIndexes == 3 ) {
2459                 /* run through all indexes */
2460                 for ( i = 0; i < numTestIndexes; i++ )
2461                 {
2462                         /* test 3 indexes */
2463                         if ( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2464                                  indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2465                                  indexes[ 2 ] == bspDrawIndexes[ i + 2 ] ) {
2466                                 numRedundantIndexes += numIndexes;
2467                                 return i;
2468                         }
2469                 }
2470
2471                 /* failed */
2472                 return numBSPDrawIndexes;
2473         }
2474
2475         /* handle 4 or more indexes */
2476         for ( i = 0; i < numTestIndexes; i++ )
2477         {
2478                 /* test first 4 indexes */
2479                 if ( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2480                          indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2481                          indexes[ 2 ] == bspDrawIndexes[ i + 2 ] &&
2482                          indexes[ 3 ] == bspDrawIndexes[ i + 3 ] ) {
2483                         /* handle 4 indexes */
2484                         if ( numIndexes == 4 ) {
2485                                 return i;
2486                         }
2487
2488                         /* test the remainder */
2489                         for ( j = 4; j < numIndexes; j++ )
2490                         {
2491                                 if ( indexes[ j ] != bspDrawIndexes[ i + j ] ) {
2492                                         break;
2493                                 }
2494                                 else if ( j == ( numIndexes - 1 ) ) {
2495                                         numRedundantIndexes += numIndexes;
2496                                         return i;
2497                                 }
2498                         }
2499                 }
2500         }
2501
2502         /* failed */
2503         return numBSPDrawIndexes;
2504 }
2505
2506
2507
2508 /*
2509    EmitDrawIndexes() - ydnar
2510    attempts to find an existing run of drawindexes before adding new ones
2511  */
2512
2513 void EmitDrawIndexes( mapDrawSurface_t *ds, bspDrawSurface_t *out ){
2514         int i;
2515
2516
2517         /* attempt to use redundant indexing */
2518         out->firstIndex = FindDrawIndexes( ds->numIndexes, ds->indexes );
2519         out->numIndexes = ds->numIndexes;
2520         if ( out->firstIndex == numBSPDrawIndexes ) {
2521                 /* copy new unique indexes */
2522                 for ( i = 0; i < ds->numIndexes; i++ )
2523                 {
2524                         AUTOEXPAND_BY_REALLOC_BSP( DrawIndexes, 1024 );
2525                         bspDrawIndexes[ numBSPDrawIndexes ] = ds->indexes[ i ];
2526
2527                         /* validate the index */
2528                         if ( ds->type != SURFACE_PATCH ) {
2529                                 if ( bspDrawIndexes[ numBSPDrawIndexes ] < 0 || bspDrawIndexes[ numBSPDrawIndexes ] >= ds->numVerts ) {
2530                                         Sys_FPrintf( SYS_WRN, "WARNING: %d %s has invalid index %d (%d)\n",
2531                                                                 numBSPDrawSurfaces,
2532                                                                 ds->shaderInfo->shader,
2533                                                                 bspDrawIndexes[ numBSPDrawIndexes ],
2534                                                                 i );
2535                                         bspDrawIndexes[ numBSPDrawIndexes ] = 0;
2536                                 }
2537                         }
2538
2539                         /* increment index count */
2540                         numBSPDrawIndexes++;
2541                 }
2542         }
2543 }
2544
2545
2546
2547
2548 /*
2549    EmitFlareSurface()
2550    emits a bsp flare drawsurface
2551  */
2552
2553 void EmitFlareSurface( mapDrawSurface_t *ds ){
2554         int i;
2555         bspDrawSurface_t        *out;
2556
2557
2558         /* ydnar: nuking useless flare drawsurfaces */
2559         if ( emitFlares == qfalse && ds->type != SURFACE_SHADER ) {
2560                 return;
2561         }
2562
2563         /* limit check */
2564         if ( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
2565                 Error( "MAX_MAP_DRAW_SURFS" );
2566         }
2567
2568         /* allocate a new surface */
2569         if ( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
2570                 Error( "MAX_MAP_DRAW_SURFS" );
2571         }
2572         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2573         ds->outputNum = numBSPDrawSurfaces;
2574         numBSPDrawSurfaces++;
2575         memset( out, 0, sizeof( *out ) );
2576
2577         /* set it up */
2578         out->surfaceType = MST_FLARE;
2579         out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2580         out->fogNum = ds->fogNum;
2581
2582         /* RBSP */
2583         for ( i = 0; i < MAX_LIGHTMAPS; i++ )
2584         {
2585                 out->lightmapNum[ i ] = -3;
2586                 out->lightmapStyles[ i ] = LS_NONE;
2587                 out->vertexStyles[ i ] = LS_NONE;
2588         }
2589         out->lightmapStyles[ 0 ] = ds->lightStyle;
2590         out->vertexStyles[ 0 ] = ds->lightStyle;
2591
2592         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );          /* origin */
2593         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );    /* color */
2594         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2595         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );    /* normal */
2596
2597         /* add to count */
2598         numSurfacesByType[ ds->type ]++;
2599 }
2600
2601
2602
2603 /*
2604    EmitPatchSurface()
2605    emits a bsp patch drawsurface
2606  */
2607
2608 void EmitPatchSurface( entity_t *e, mapDrawSurface_t *ds ){
2609         int i, j;
2610         bspDrawSurface_t    *out;
2611         int surfaceFlags, contentFlags;
2612         int forcePatchMeta;
2613
2614         /* vortex: _patchMeta support */
2615         forcePatchMeta = IntForKey( e, "_patchMeta" );
2616         if ( !forcePatchMeta ) {
2617                 forcePatchMeta = IntForKey( e, "patchMeta" );
2618         }
2619
2620         /* invert the surface if necessary */
2621         if ( ds->backSide || ds->shaderInfo->invert ) {
2622                 bspDrawVert_t   *dv1, *dv2, temp;
2623
2624                 /* walk the verts, flip the normal */
2625                 for ( i = 0; i < ds->numVerts; i++ )
2626                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2627
2628                 /* walk the verts again, but this time reverse their order */
2629                 for ( j = 0; j < ds->patchHeight; j++ )
2630                 {
2631                         for ( i = 0; i < ( ds->patchWidth / 2 ); i++ )
2632                         {
2633                                 dv1 = &ds->verts[ j * ds->patchWidth + i ];
2634                                 dv2 = &ds->verts[ j * ds->patchWidth + ( ds->patchWidth - i - 1 ) ];
2635                                 memcpy( &temp, dv1, sizeof( bspDrawVert_t ) );
2636                                 memcpy( dv1, dv2, sizeof( bspDrawVert_t ) );
2637                                 memcpy( dv2, &temp, sizeof( bspDrawVert_t ) );
2638                         }
2639                 }
2640
2641                 /* invert facing */
2642                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2643         }
2644
2645         /* allocate a new surface */
2646         if ( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
2647                 Error( "MAX_MAP_DRAW_SURFS" );
2648         }
2649         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2650         ds->outputNum = numBSPDrawSurfaces;
2651         numBSPDrawSurfaces++;
2652         memset( out, 0, sizeof( *out ) );
2653
2654         /* set it up */
2655         out->surfaceType = MST_PATCH;
2656         if ( debugSurfaces ) {
2657                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2658         }
2659         else if ( patchMeta || forcePatchMeta ) {
2660                 /* patch meta requires that we have nodraw patches for collision */
2661                 surfaceFlags = ds->shaderInfo->surfaceFlags;
2662                 contentFlags = ds->shaderInfo->contentFlags;
2663                 ApplySurfaceParm( "nodraw", &contentFlags, &surfaceFlags, NULL );
2664                 ApplySurfaceParm( "pointlight", &contentFlags, &surfaceFlags, NULL );
2665
2666                 /* we don't want this patch getting lightmapped */
2667                 VectorClear( ds->lightmapVecs[ 2 ] );
2668                 VectorClear( ds->lightmapAxis );
2669                 ds->sampleSize = 0;
2670
2671                 /* emit the new fake shader */
2672                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &contentFlags, &surfaceFlags );
2673         }
2674         else{
2675                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2676         }
2677         out->patchWidth = ds->patchWidth;
2678         out->patchHeight = ds->patchHeight;
2679         out->fogNum = ds->fogNum;
2680
2681         /* RBSP */
2682         for ( i = 0; i < MAX_LIGHTMAPS; i++ )
2683         {
2684                 out->lightmapNum[ i ] = -3;
2685                 out->lightmapStyles[ i ] = LS_NONE;
2686                 out->vertexStyles[ i ] = LS_NONE;
2687         }
2688         out->lightmapStyles[ 0 ] = LS_NORMAL;
2689         out->vertexStyles[ 0 ] = LS_NORMAL;
2690
2691         /* ydnar: gs mods: previously, the lod bounds were stored in lightmapVecs[ 0 ] and [ 1 ], moved to bounds[ 0 ] and [ 1 ] */
2692         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2693         VectorCopy( ds->bounds[ 0 ], out->lightmapVecs[ 0 ] );
2694         VectorCopy( ds->bounds[ 1 ], out->lightmapVecs[ 1 ] );
2695         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2696
2697         /* ydnar: gs mods: clear out the plane normal */
2698         if ( ds->planar == qfalse ) {
2699                 VectorClear( out->lightmapVecs[ 2 ] );
2700         }
2701
2702         /* emit the verts and indexes */
2703         EmitDrawVerts( ds, out );
2704         EmitDrawIndexes( ds, out );
2705
2706         /* add to count */
2707         numSurfacesByType[ ds->type ]++;
2708 }
2709
2710
2711
2712 /*
2713    OptimizeTriangleSurface() - ydnar
2714    optimizes the vertex/index data in a triangle surface
2715  */
2716
2717 #define VERTEX_CACHE_SIZE   16
2718
2719 static void OptimizeTriangleSurface( mapDrawSurface_t *ds ){
2720         int i, j, k, temp, first, best, bestScore, score;
2721         int vertexCache[ VERTEX_CACHE_SIZE + 1 ];       /* one more for optimizing insert */
2722         int     *indexes;
2723
2724
2725         /* certain surfaces don't get optimized */
2726         if ( ds->numIndexes <= VERTEX_CACHE_SIZE ||
2727                  ds->shaderInfo->autosprite ) {
2728                 return;
2729         }
2730
2731         /* create index scratch pad */
2732         indexes = safe_malloc( ds->numIndexes * sizeof( *indexes ) );
2733         memcpy( indexes, ds->indexes, ds->numIndexes * sizeof( *indexes ) );
2734
2735         /* setup */
2736         for ( i = 0; i <= VERTEX_CACHE_SIZE && i < ds->numIndexes; i++ )
2737                 vertexCache[ i ] = indexes[ i ];
2738
2739         /* add triangles in a vertex cache-aware order */
2740         for ( i = 0; i < ds->numIndexes; i += 3 )
2741         {
2742                 /* find best triangle given the current vertex cache */
2743                 first = -1;
2744                 best = -1;
2745                 bestScore = -1;
2746                 for ( j = 0; j < ds->numIndexes; j += 3 )
2747                 {
2748                         /* valid triangle? */
2749                         if ( indexes[ j ] != -1 ) {
2750                                 /* set first if necessary */
2751                                 if ( first < 0 ) {
2752                                         first = j;
2753                                 }
2754
2755                                 /* score the triangle */
2756                                 score = 0;
2757                                 for ( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2758                                 {
2759                                         if ( indexes[ j ] == vertexCache[ k ] || indexes[ j + 1 ] == vertexCache[ k ] || indexes[ j + 2 ] == vertexCache[ k ] ) {
2760                                                 score++;
2761                                         }
2762                                 }
2763
2764                                 /* better triangle? */
2765                                 if ( score > bestScore ) {
2766                                         bestScore = score;
2767                                         best = j;
2768                                 }
2769
2770                                 /* a perfect score of 3 means this triangle's verts are already present in the vertex cache */
2771                                 if ( score == 3 ) {
2772                                         break;
2773                                 }
2774                         }
2775                 }
2776
2777                 /* check if no decent triangle was found, and use first available */
2778                 if ( best < 0 ) {
2779                         best = first;
2780                 }
2781
2782                 /* valid triangle? */
2783                 if ( best >= 0 ) {
2784                         /* add triangle to vertex cache */
2785                         for ( j = 0; j < 3; j++ )
2786                         {
2787                                 for ( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2788                                 {
2789                                         if ( indexes[ best + j ] == vertexCache[ k ] ) {
2790                                                 break;
2791                                         }
2792                                 }
2793
2794                                 if ( k >= VERTEX_CACHE_SIZE ) {
2795                                         /* pop off top of vertex cache */
2796                                         for ( k = VERTEX_CACHE_SIZE; k > 0; k-- )
2797                                                 vertexCache[ k ] = vertexCache[ k - 1 ];
2798
2799                                         /* add vertex */
2800                                         vertexCache[ 0 ] = indexes[ best + j ];
2801                                 }
2802                         }
2803
2804                         /* add triangle to surface */
2805                         ds->indexes[ i ] = indexes[ best ];
2806                         ds->indexes[ i + 1 ] = indexes[ best + 1 ];
2807                         ds->indexes[ i + 2 ] = indexes[ best + 2 ];
2808
2809                         /* clear from input pool */
2810                         indexes[ best ] = -1;
2811                         indexes[ best + 1 ] = -1;
2812                         indexes[ best + 2 ] = -1;
2813
2814                         /* sort triangle windings (312 -> 123) */
2815                         while ( ds->indexes[ i ] > ds->indexes[ i + 1 ] || ds->indexes[ i ] > ds->indexes[ i + 2 ] )
2816                         {
2817                                 temp = ds->indexes[ i ];
2818                                 ds->indexes[ i ] = ds->indexes[ i + 1 ];
2819                                 ds->indexes[ i + 1 ] = ds->indexes[ i + 2 ];
2820                                 ds->indexes[ i + 2 ] = temp;
2821                         }
2822                 }
2823         }
2824
2825         /* clean up */
2826         free( indexes );
2827 }
2828
2829
2830
2831 /*
2832    EmitTriangleSurface()
2833    creates a bsp drawsurface from arbitrary triangle surfaces
2834  */
2835
2836 void EmitTriangleSurface( mapDrawSurface_t *ds ){
2837         int i, temp;
2838         bspDrawSurface_t        *out;
2839
2840         /* invert the surface if necessary */
2841         if ( ds->backSide || ds->shaderInfo->invert ) {
2842                 /* walk the indexes, reverse the triangle order */
2843                 for ( i = 0; i < ds->numIndexes; i += 3 )
2844                 {
2845                         temp = ds->indexes[ i ];
2846                         ds->indexes[ i ] = ds->indexes[ i + 1 ];
2847                         ds->indexes[ i + 1 ] = temp;
2848                 }
2849
2850                 /* walk the verts, flip the normal */
2851                 for ( i = 0; i < ds->numVerts; i++ )
2852                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2853
2854                 /* invert facing */
2855                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2856         }
2857
2858         /* allocate a new surface */
2859         if ( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
2860                 Error( "MAX_MAP_DRAW_SURFS" );
2861         }
2862         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2863         ds->outputNum = numBSPDrawSurfaces;
2864         numBSPDrawSurfaces++;
2865         memset( out, 0, sizeof( *out ) );
2866
2867         /* ydnar/sd: handle wolf et foliage surfaces */
2868         if ( ds->type == SURFACE_FOLIAGE ) {
2869                 out->surfaceType = MST_FOLIAGE;
2870         }
2871
2872         /* ydnar: gs mods: handle lightmapped terrain (force to planar type) */
2873         //%     else if( VectorLength( ds->lightmapAxis ) <= 0.0f || ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FOGHULL || debugSurfaces )
2874         else if ( ( VectorLength( ds->lightmapAxis ) <= 0.0f && ds->planar == qfalse ) ||
2875                           ds->type == SURFACE_TRIANGLES ||
2876                           ds->type == SURFACE_FOGHULL ||
2877                           ds->numVerts > maxLMSurfaceVerts ||
2878                           debugSurfaces ) {
2879                 out->surfaceType = MST_TRIANGLE_SOUP;
2880         }
2881
2882         /* set to a planar face */
2883         else{
2884                 out->surfaceType = MST_PLANAR;
2885         }
2886
2887         /* set it up */
2888         if ( debugSurfaces ) {
2889                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2890         }
2891         else{
2892                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2893         }
2894         out->patchWidth = ds->patchWidth;
2895         out->patchHeight = ds->patchHeight;
2896         out->fogNum = ds->fogNum;
2897
2898         /* debug inset (push each triangle vertex towards the center of each triangle it is on */
2899         if ( debugInset ) {
2900                 bspDrawVert_t   *a, *b, *c;
2901                 vec3_t cent, dir;
2902
2903
2904                 /* walk triangle list */
2905                 for ( i = 0; i < ds->numIndexes; i += 3 )
2906                 {
2907                         /* get verts */
2908                         a = &ds->verts[ ds->indexes[ i ] ];
2909                         b = &ds->verts[ ds->indexes[ i + 1 ] ];
2910                         c = &ds->verts[ ds->indexes[ i + 2 ] ];
2911
2912                         /* calculate centroid */
2913                         VectorCopy( a->xyz, cent );
2914                         VectorAdd( cent, b->xyz, cent );
2915                         VectorAdd( cent, c->xyz, cent );
2916                         VectorScale( cent, 1.0f / 3.0f, cent );
2917
2918                         /* offset each vertex */
2919                         VectorSubtract( cent, a->xyz, dir );
2920                         VectorNormalize( dir, dir );
2921                         VectorAdd( a->xyz, dir, a->xyz );
2922                         VectorSubtract( cent, b->xyz, dir );
2923                         VectorNormalize( dir, dir );
2924                         VectorAdd( b->xyz, dir, b->xyz );
2925                         VectorSubtract( cent, c->xyz, dir );
2926                         VectorNormalize( dir, dir );
2927                         VectorAdd( c->xyz, dir, c->xyz );
2928                 }
2929         }
2930
2931         /* RBSP */
2932         for ( i = 0; i < MAX_LIGHTMAPS; i++ )
2933         {
2934                 out->lightmapNum[ i ] = -3;
2935                 out->lightmapStyles[ i ] = LS_NONE;
2936                 out->vertexStyles[ i ] = LS_NONE;
2937         }
2938         out->lightmapStyles[ 0 ] = LS_NORMAL;
2939         out->vertexStyles[ 0 ] = LS_NORMAL;
2940
2941         /* lightmap vectors (lod bounds for patches */
2942         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2943         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );
2944         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2945         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2946
2947         /* ydnar: gs mods: clear out the plane normal */
2948         if ( ds->planar == qfalse ) {
2949                 VectorClear( out->lightmapVecs[ 2 ] );
2950         }
2951
2952         /* optimize the surface's triangles */
2953         OptimizeTriangleSurface( ds );
2954
2955         /* emit the verts and indexes */
2956         EmitDrawVerts( ds, out );
2957         EmitDrawIndexes( ds, out );
2958
2959         /* add to count */
2960         numSurfacesByType[ ds->type ]++;
2961 }
2962
2963
2964
2965 /*
2966    EmitFaceSurface()
2967    emits a bsp planar winding (brush face) drawsurface
2968  */
2969
2970 static void EmitFaceSurface( mapDrawSurface_t *ds ){
2971         /* strip/fan finding was moved elsewhere */
2972         if ( maxAreaFaceSurface ) {
2973                 MaxAreaFaceSurface( ds );
2974         }
2975         else{
2976                 StripFaceSurface( ds );
2977         }
2978         EmitTriangleSurface( ds );
2979 }
2980
2981
2982
2983 /*
2984    MakeDebugPortalSurfs_r() - ydnar
2985    generates drawsurfaces for passable portals in the bsp
2986  */
2987
2988 static void MakeDebugPortalSurfs_r( node_t *node, shaderInfo_t *si ){
2989         int i, k, c, s;
2990         portal_t            *p;
2991         winding_t           *w;
2992         mapDrawSurface_t    *ds;
2993         bspDrawVert_t       *dv;
2994
2995
2996         /* recurse if decision node */
2997         if ( node->planenum != PLANENUM_LEAF ) {
2998                 MakeDebugPortalSurfs_r( node->children[ 0 ], si );
2999                 MakeDebugPortalSurfs_r( node->children[ 1 ], si );
3000                 return;
3001         }
3002
3003         /* don't bother with opaque leaves */
3004         if ( node->opaque ) {
3005                 return;
3006         }
3007
3008         /* walk the list of portals */
3009         for ( c = 0, p = node->portals; p != NULL; c++, p = p->next[ s ] )
3010         {
3011                 /* get winding and side even/odd */
3012                 w = p->winding;
3013                 s = ( p->nodes[ 1 ] == node );
3014
3015                 /* is this a valid portal for this leaf? */
3016                 if ( w && p->nodes[ 0 ] == node ) {
3017                         /* is this portal passable? */
3018                         if ( PortalPassable( p ) == qfalse ) {
3019                                 continue;
3020                         }
3021
3022                         /* check max points */
3023                         if ( w->numpoints > 64 ) {
3024                                 Error( "MakePortalSurfs_r: w->numpoints = %d", w->numpoints );
3025                         }
3026
3027                         /* allocate a drawsurface */
3028                         ds = AllocDrawSurface( SURFACE_FACE );
3029                         ds->shaderInfo = si;
3030                         ds->planar = qtrue;
3031                         ds->sideRef = AllocSideRef( p->side, NULL );
3032                         ds->planeNum = FindFloatPlane( p->plane.normal, p->plane.dist, 0, NULL );
3033                         VectorCopy( p->plane.normal, ds->lightmapVecs[ 2 ] );
3034                         ds->fogNum = -1;
3035                         ds->numVerts = w->numpoints;
3036                         ds->verts = safe_malloc0( ds->numVerts * sizeof( *ds->verts ) );
3037
3038                         /* walk the winding */
3039                         for ( i = 0; i < ds->numVerts; i++ )
3040                         {
3041                                 /* get vert */
3042                                 dv = ds->verts + i;
3043
3044                                 /* set it */
3045                                 VectorCopy( w->p[ i ], dv->xyz );
3046                                 VectorCopy( p->plane.normal, dv->normal );
3047                                 dv->st[ 0 ] = 0;
3048                                 dv->st[ 1 ] = 0;
3049                                 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
3050                                 {
3051                                         VectorCopy( debugColors[ c % 12 ], dv->color[ k ] );
3052                                         dv->color[ k ][ 3 ] = 32;
3053                                 }
3054                         }
3055                 }
3056         }
3057 }
3058
3059
3060
3061 /*
3062    MakeDebugPortalSurfs() - ydnar
3063    generates drawsurfaces for passable portals in the bsp
3064  */
3065
3066 void MakeDebugPortalSurfs( tree_t *tree ){
3067         shaderInfo_t    *si;
3068
3069
3070         /* note it */
3071         Sys_FPrintf( SYS_VRB, "--- MakeDebugPortalSurfs ---\n" );
3072
3073         /* get portal debug shader */
3074         si = ShaderInfoForShader( "debugportals" );
3075
3076         /* walk the tree */
3077         MakeDebugPortalSurfs_r( tree->headnode, si );
3078 }
3079
3080
3081
3082 /*
3083    MakeFogHullSurfs()
3084    generates drawsurfaces for a foghull (this MUST use a sky shader)
3085  */
3086
3087 void MakeFogHullSurfs( entity_t *e, tree_t *tree, char *shader ){
3088         shaderInfo_t        *si;
3089         mapDrawSurface_t    *ds;
3090         vec3_t fogMins, fogMaxs;
3091         int i, indexes[] =
3092         {
3093                 0, 1, 2, 0, 2, 3,
3094                 4, 7, 5, 5, 7, 6,
3095                 1, 5, 6, 1, 6, 2,
3096                 0, 4, 5, 0, 5, 1,
3097                 2, 6, 7, 2, 7, 3,
3098                 3, 7, 4, 3, 4, 0
3099         };
3100
3101
3102         /* dummy check */
3103         if ( shader == NULL || shader[ 0 ] == '\0' ) {
3104                 return;
3105         }
3106
3107         /* note it */
3108         Sys_FPrintf( SYS_VRB, "--- MakeFogHullSurfs ---\n" );
3109
3110         /* get hull bounds */
3111         VectorCopy( mapMins, fogMins );
3112         VectorCopy( mapMaxs, fogMaxs );
3113         for ( i = 0; i < 3; i++ )
3114         {
3115                 fogMins[ i ] -= 128;
3116                 fogMaxs[ i ] += 128;
3117         }
3118
3119         /* get foghull shader */
3120         si = ShaderInfoForShader( shader );
3121
3122         /* allocate a drawsurface */
3123         ds = AllocDrawSurface( SURFACE_FOGHULL );
3124         ds->shaderInfo = si;
3125         ds->fogNum = -1;
3126         ds->numVerts = 8;
3127         ds->verts = safe_malloc0( ds->numVerts * sizeof( *ds->verts ) );
3128         ds->numIndexes = 36;
3129         ds->indexes = safe_malloc0( ds->numIndexes * sizeof( *ds->indexes ) );
3130
3131         /* set verts */
3132         VectorSet( ds->verts[ 0 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
3133         VectorSet( ds->verts[ 1 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
3134         VectorSet( ds->verts[ 2 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
3135         VectorSet( ds->verts[ 3 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
3136
3137         VectorSet( ds->verts[ 4 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
3138         VectorSet( ds->verts[ 5 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
3139         VectorSet( ds->verts[ 6 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
3140         VectorSet( ds->verts[ 7 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
3141
3142         /* set indexes */
3143         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( *ds->indexes ) );
3144 }
3145
3146
3147
3148 /*
3149    BiasSurfaceTextures()
3150    biases a surface's texcoords as close to 0 as possible
3151  */
3152
3153 void BiasSurfaceTextures( mapDrawSurface_t *ds ){
3154         int i;
3155
3156
3157         /* calculate the surface texture bias */
3158         CalcSurfaceTextureRange( ds );
3159
3160         /* don't bias globaltextured shaders */
3161         if ( ds->shaderInfo->globalTexture ) {
3162                 return;
3163         }
3164
3165         /* bias the texture coordinates */
3166         for ( i = 0; i < ds->numVerts; i++ )
3167         {
3168                 ds->verts[ i ].st[ 0 ] += ds->bias[ 0 ];
3169                 ds->verts[ i ].st[ 1 ] += ds->bias[ 1 ];
3170         }
3171 }
3172
3173
3174
3175 /*
3176    AddSurfaceModelsToTriangle_r()
3177    adds models to a specified triangle, returns the number of models added
3178  */
3179
3180 int AddSurfaceModelsToTriangle_r( mapDrawSurface_t *ds, surfaceModel_t *model, bspDrawVert_t **tri ){
3181         bspDrawVert_t mid, *tri2[ 3 ];
3182         int max, n, localNumSurfaceModels;
3183
3184
3185         /* init */
3186         localNumSurfaceModels = 0;
3187
3188         /* subdivide calc */
3189         {
3190                 int i;
3191                 float       *a, *b, dx, dy, dz, dist, maxDist;
3192
3193
3194                 /* find the longest edge and split it */
3195                 max = -1;
3196                 maxDist = 0.0f;
3197                 for ( i = 0; i < 3; i++ )
3198                 {
3199                         /* get verts */
3200                         a = tri[ i ]->xyz;
3201                         b = tri[ ( i + 1 ) % 3 ]->xyz;
3202
3203                         /* get dists */
3204                         dx = a[ 0 ] - b[ 0 ];
3205                         dy = a[ 1 ] - b[ 1 ];
3206                         dz = a[ 2 ] - b[ 2 ];
3207                         dist = ( dx * dx ) + ( dy * dy ) + ( dz * dz );
3208
3209                         /* longer? */
3210                         if ( dist > maxDist ) {
3211                                 maxDist = dist;
3212                                 max = i;
3213                         }
3214                 }
3215
3216                 /* is the triangle small enough? */
3217                 if ( max < 0 || maxDist <= ( model->density * model->density ) ) {
3218                         float odds, r, angle;
3219                         vec3_t origin, normal, scale, axis[ 3 ], angles;
3220                         m4x4_t transform, temp;
3221
3222
3223                         /* roll the dice (model's odds scaled by vertex alpha) */
3224                         odds = model->odds * ( tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ] ) / 765.0f;
3225                         r = Random();
3226                         if ( r > odds ) {
3227                                 return 0;
3228                         }
3229
3230                         /* calculate scale */
3231                         r = model->minScale + Random() * ( model->maxScale - model->minScale );
3232                         VectorSet( scale, r, r, r );
3233
3234                         /* calculate angle */
3235                         angle = model->minAngle + Random() * ( model->maxAngle - model->minAngle );
3236
3237                         /* calculate average origin */
3238                         VectorCopy( tri[ 0 ]->xyz, origin );
3239                         VectorAdd( origin, tri[ 1 ]->xyz, origin );
3240                         VectorAdd( origin, tri[ 2 ]->xyz, origin );
3241                         VectorScale( origin, ( 1.0f / 3.0f ), origin );
3242
3243                         /* clear transform matrix */
3244                         m4x4_identity( transform );
3245
3246                         /* handle oriented models */
3247                         if ( model->oriented ) {
3248                                 /* set angles */
3249                                 VectorSet( angles, 0.0f, 0.0f, angle );
3250
3251                                 /* calculate average normal */
3252                                 VectorCopy( tri[ 0 ]->normal, normal );
3253                                 VectorAdd( normal, tri[ 1 ]->normal, normal );
3254                                 VectorAdd( normal, tri[ 2 ]->normal, normal );
3255                                 if ( VectorNormalize( normal, axis[ 2 ] ) == 0.0f ) {
3256                                         VectorCopy( tri[ 0 ]->normal, axis[ 2 ] );
3257                                 }
3258
3259                                 /* make perpendicular vectors */
3260                                 MakeNormalVectors( axis[ 2 ], axis[ 1 ], axis[ 0 ] );
3261
3262                                 /* copy to matrix */
3263                                 m4x4_identity( temp );
3264                                 temp[ 0 ] = axis[ 0 ][ 0 ]; temp[ 1 ] = axis[ 0 ][ 1 ]; temp[ 2 ] = axis[ 0 ][ 2 ];
3265                                 temp[ 4 ] = axis[ 1 ][ 0 ]; temp[ 5 ] = axis[ 1 ][ 1 ]; temp[ 6 ] = axis[ 1 ][ 2 ];
3266                                 temp[ 8 ] = axis[ 2 ][ 0 ]; temp[ 9 ] = axis[ 2 ][ 1 ]; temp[ 10 ] = axis[ 2 ][ 2 ];
3267
3268                                 /* scale */
3269                                 m4x4_scale_by_vec3( temp, scale );
3270
3271                                 /* rotate around z axis */
3272                                 m4x4_rotate_by_vec3( temp, angles, eXYZ );
3273
3274                                 /* translate */
3275                                 m4x4_translate_by_vec3( transform, origin );
3276
3277                                 /* tranform into axis space */
3278                                 m4x4_multiply_by_m4x4( transform, temp );
3279                         }
3280
3281                         /* handle z-up models */
3282                         else
3283                         {
3284                                 /* set angles */
3285                                 VectorSet( angles, 0.0f, 0.0f, angle );
3286
3287                                 /* set matrix */
3288                                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
3289                         }
3290
3291                         /* insert the model */
3292                         InsertModel( (char *) model->model, 0, 0, transform, NULL, ds->celShader, ds->entityNum, ds->castShadows, ds->recvShadows, 0, ds->lightmapScale, 0, 0, clipDepthGlobal );
3293
3294                         /* return to sender */
3295                         return 1;
3296                 }
3297         }
3298
3299         /* split the longest edge and map it */
3300         LerpDrawVert( tri[ max ], tri[ ( max + 1 ) % 3 ], &mid );
3301
3302         /* recurse to first triangle */
3303         VectorCopy( tri, tri2 );
3304         tri2[ max ] = &mid;
3305         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3306         if ( n < 0 ) {
3307                 return n;
3308         }
3309         localNumSurfaceModels += n;
3310
3311         /* recurse to second triangle */
3312         VectorCopy( tri, tri2 );
3313         tri2[ ( max + 1 ) % 3 ] = &mid;
3314         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3315         if ( n < 0 ) {
3316                 return n;
3317         }
3318         localNumSurfaceModels += n;
3319
3320         /* return count */
3321         return localNumSurfaceModels;
3322 }
3323
3324
3325
3326 /*
3327    AddSurfaceModels()
3328    adds a surface's shader models to the surface
3329  */
3330
3331 int AddSurfaceModels( mapDrawSurface_t *ds ){
3332         surfaceModel_t  *model;
3333         int i, x, y, n, pw[ 5 ], r, localNumSurfaceModels, iterations;
3334         mesh_t src, *mesh, *subdivided;
3335         bspDrawVert_t centroid, *tri[ 3 ];
3336         float alpha;
3337
3338
3339         /* dummy check */
3340         if ( ds == NULL || ds->shaderInfo == NULL || ds->shaderInfo->surfaceModel == NULL ) {
3341                 return 0;
3342         }
3343
3344         /* init */
3345         localNumSurfaceModels = 0;
3346
3347         /* walk the model list */
3348         for ( model = ds->shaderInfo->surfaceModel; model != NULL; model = model->next )
3349         {
3350                 /* switch on type */
3351                 switch ( ds->type )
3352                 {
3353                 /* handle brush faces and decals */
3354                 case SURFACE_FACE:
3355                 case SURFACE_DECAL:
3356                         /* calculate centroid */
3357                         memset( &centroid, 0, sizeof( centroid ) );
3358                         alpha = 0.0f;
3359
3360                         /* walk verts */
3361                         for ( i = 0; i < ds->numVerts; i++ )
3362                         {
3363                                 VectorAdd( centroid.xyz, ds->verts[ i ].xyz, centroid.xyz );
3364                                 VectorAdd( centroid.normal, ds->verts[ i ].normal, centroid.normal );
3365                                 centroid.st[ 0 ] += ds->verts[ i ].st[ 0 ];
3366                                 centroid.st[ 1 ] += ds->verts[ i ].st[ 1 ];
3367                                 alpha += ds->verts[ i ].color[ 0 ][ 3 ];
3368                         }
3369
3370                         /* average */
3371                         centroid.xyz[ 0 ] /= ds->numVerts;
3372                         centroid.xyz[ 1 ] /= ds->numVerts;
3373                         centroid.xyz[ 2 ] /= ds->numVerts;
3374                         if ( VectorNormalize( centroid.normal, centroid.normal ) == 0.0f ) {
3375                                 VectorCopy( ds->verts[ 0 ].normal, centroid.normal );
3376                         }
3377                         centroid.st[ 0 ]  /= ds->numVerts;
3378                         centroid.st[ 1 ]  /= ds->numVerts;
3379                         alpha /= ds->numVerts;
3380                         centroid.color[ 0 ][ 0 ] = 0xFF;
3381                         centroid.color[ 0 ][ 1 ] = 0xFF;
3382                         //centroid.color[ 0 ][ 2 ] = 0xFF;
3383                         centroid.color[ 0 ][ 2 ] = ( alpha > 255.0f ? 0xFF : alpha );
3384
3385                         /* head vert is centroid */
3386                         tri[ 0 ] = &centroid;
3387
3388                         /* walk fanned triangles */
3389                         for ( i = 0; i < ds->numVerts; i++ )
3390                         {
3391                                 /* set triangle */
3392                                 tri[ 1 ] = &ds->verts[ i ];
3393                                 tri[ 2 ] = &ds->verts[ ( i + 1 ) % ds->numVerts ];
3394
3395                                 /* create models */
3396                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3397                                 if ( n < 0 ) {
3398                                         return n;
3399                                 }
3400                                 localNumSurfaceModels += n;
3401                         }
3402                         break;
3403
3404                 /* handle patches */
3405                 case SURFACE_PATCH:
3406                         /* subdivide the surface */
3407                         src.width = ds->patchWidth;
3408                         src.height = ds->patchHeight;
3409                         src.verts = ds->verts;
3410                         //%     subdivided = SubdivideMesh( src, 8.0f, 512 );
3411                         iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
3412                         subdivided = SubdivideMesh2( src, iterations );
3413
3414                         /* fit it to the curve and remove colinear verts on rows/columns */
3415                         PutMeshOnCurve( *subdivided );
3416                         mesh = RemoveLinearMeshColumnsRows( subdivided );
3417                         FreeMesh( subdivided );
3418
3419                         /* subdivide each quad to place the models */
3420                         for ( y = 0; y < ( mesh->height - 1 ); y++ )
3421                         {
3422                                 for ( x = 0; x < ( mesh->width - 1 ); x++ )
3423                                 {
3424                                         /* set indexes */
3425                                         pw[ 0 ] = x + ( y * mesh->width );
3426                                         pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
3427                                         pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
3428                                         pw[ 3 ] = x + 1 + ( y * mesh->width );
3429                                         pw[ 4 ] = x + ( y * mesh->width );      /* same as pw[ 0 ] */
3430
3431                                         /* set radix */
3432                                         r = ( x + y ) & 1;
3433
3434                                         /* triangle 1 */
3435                                         tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3436                                         tri[ 1 ] = &mesh->verts[ pw[ r + 1 ] ];
3437                                         tri[ 2 ] = &mesh->verts[ pw[ r + 2 ] ];
3438                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3439                                         if ( n < 0 ) {
3440                                                 return n;
3441                                         }
3442                                         localNumSurfaceModels += n;
3443
3444                                         /* triangle 2 */
3445                                         tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3446                                         tri[ 1 ] = &mesh->verts[ pw[ r + 2 ] ];
3447                                         tri[ 2 ] = &mesh->verts[ pw[ r + 3 ] ];
3448                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3449                                         if ( n < 0 ) {
3450                                                 return n;
3451                                         }
3452                                         localNumSurfaceModels += n;
3453                                 }
3454                         }
3455
3456                         /* free the subdivided mesh */
3457                         FreeMesh( mesh );
3458                         break;
3459
3460                 /* handle triangle surfaces */
3461                 case SURFACE_TRIANGLES:
3462                 case SURFACE_FORCED_META:
3463                 case SURFACE_META:
3464                         /* walk the triangle list */
3465                         for ( i = 0; i < ds->numIndexes; i += 3 )
3466                         {
3467                                 tri[ 0 ] = &ds->verts[ ds->indexes[ i ] ];
3468                                 tri[ 1 ] = &ds->verts[ ds->indexes[ i + 1 ] ];
3469                                 tri[ 2 ] = &ds->verts[ ds->indexes[ i + 2 ] ];
3470                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3471                                 if ( n < 0 ) {
3472                                         return n;
3473                                 }
3474                                 localNumSurfaceModels += n;
3475                         }
3476                         break;
3477
3478                 /* no support for flares, foghull, etc */
3479                 default:
3480                         break;
3481                 }
3482         }
3483
3484         /* return count */
3485         return localNumSurfaceModels;
3486 }
3487
3488
3489
3490 /*
3491    AddEntitySurfaceModels() - ydnar
3492    adds surfacemodels to an entity's surfaces
3493  */
3494
3495 void AddEntitySurfaceModels( entity_t *e ){
3496         int i;
3497
3498
3499         /* note it */
3500         Sys_FPrintf( SYS_VRB, "--- AddEntitySurfaceModels ---\n" );
3501
3502         /* walk the surface list */
3503         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3504                 numSurfaceModels += AddSurfaceModels( &mapDrawSurfs[ i ] );
3505 }
3506
3507
3508
3509 /*
3510    VolumeColorMods() - ydnar
3511    applies brush/volumetric color/alpha modulation to vertexes
3512  */
3513
3514 static void VolumeColorMods( entity_t *e, mapDrawSurface_t *ds ){
3515         int i, j;
3516         float d;
3517         brush_t     *b;
3518         plane_t     *plane;
3519
3520
3521         /* early out */
3522         if ( e->colorModBrushes == NULL ) {
3523                 return;
3524         }
3525
3526         /* iterate brushes */
3527         for ( b = e->colorModBrushes; b != NULL; b = b->nextColorModBrush )
3528         {
3529                 /* worldspawn alpha brushes affect all, grouped ones only affect original entity */
3530                 if ( b->entityNum != 0 && b->entityNum != ds->entityNum ) {
3531                         continue;
3532                 }
3533
3534                 /* test bbox */
3535                 if ( b->mins[ 0 ] > ds->maxs[ 0 ] || b->maxs[ 0 ] < ds->mins[ 0 ] ||
3536                          b->mins[ 1 ] > ds->maxs[ 1 ] || b->maxs[ 1 ] < ds->mins[ 1 ] ||
3537                          b->mins[ 2 ] > ds->maxs[ 2 ] || b->maxs[ 2 ] < ds->mins[ 2 ] ) {
3538                         continue;
3539                 }
3540
3541                 /* iterate verts */
3542                 for ( i = 0; i < ds->numVerts; i++ )
3543                 {
3544                         /* iterate planes */
3545                         for ( j = 0; j < b->numsides; j++ )
3546                         {
3547                                 /* point-plane test */
3548                                 plane = &mapplanes[ b->sides[ j ].planenum ];
3549                                 d = DotProduct( ds->verts[ i ].xyz, plane->normal ) - plane->dist;
3550                                 if ( d > 1.0f ) {
3551                                         break;
3552                                 }
3553                         }
3554
3555                         /* apply colormods */
3556                         if ( j == b->numsides ) {
3557                                 ColorMod( b->contentShader->colorMod, 1, &ds->verts[ i ] );
3558                         }
3559                 }
3560         }
3561 }
3562
3563
3564
3565 /*
3566    FilterDrawsurfsIntoTree()
3567    upon completion, all drawsurfs that actually generate a reference
3568    will have been emited to the bspfile arrays, and the references
3569    will have valid final indexes
3570  */
3571
3572 void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree ){
3573         int i, j;
3574         mapDrawSurface_t    *ds;
3575         shaderInfo_t        *si;
3576         vec3_t origin, mins, maxs;
3577         int refs;
3578         int numSurfs, numRefs, numSkyboxSurfaces;
3579         qboolean sb;
3580
3581
3582         /* note it */
3583         Sys_FPrintf( SYS_VRB, "--- FilterDrawsurfsIntoTree ---\n" );
3584
3585         /* filter surfaces into the tree */
3586         numSurfs = 0;
3587         numRefs = 0;
3588         numSkyboxSurfaces = 0;
3589         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3590         {
3591                 /* get surface and try to early out */
3592                 ds = &mapDrawSurfs[ i ];
3593                 if ( ds->numVerts == 0 && ds->type != SURFACE_FLARE && ds->type != SURFACE_SHADER ) {
3594                         continue;
3595                 }
3596
3597                 /* get shader */
3598                 si = ds->shaderInfo;
3599
3600                 /* ydnar: skybox surfaces are special */
3601                 if ( ds->skybox ) {
3602                         refs = AddReferenceToTree_r( ds, tree->headnode, qtrue );
3603                         ds->skybox = qfalse;
3604                         sb = qtrue;
3605                 }
3606                 else
3607                 {
3608                         sb = qfalse;
3609
3610                         /* refs initially zero */
3611                         refs = 0;
3612
3613                         /* apply texture coordinate mods */
3614                         for ( j = 0; j < ds->numVerts; j++ )
3615                                 TCMod( si->mod, ds->verts[ j ].st );
3616
3617                         /* ydnar: apply shader colormod */
3618                         ColorMod( ds->shaderInfo->colorMod, ds->numVerts, ds->verts );
3619
3620                         /* ydnar: apply brush colormod */
3621                         VolumeColorMods( e, ds );
3622
3623                         /* ydnar: make fur surfaces */
3624                         if ( si->furNumLayers > 0 ) {
3625                                 Fur( ds );
3626                         }
3627
3628                         /* ydnar/sd: make foliage surfaces */
3629                         if ( si->foliage != NULL ) {
3630                                 Foliage( ds );
3631                         }
3632
3633                         /* create a flare surface if necessary */
3634                         if ( si->flareShader != NULL && si->flareShader[ 0 ] ) {
3635                                 AddSurfaceFlare( ds, e->origin );
3636                         }
3637
3638                         /* ydnar: don't emit nodraw surfaces (like nodraw fog) */
3639                         if ( ( si->compileFlags & C_NODRAW ) && ds->type != SURFACE_PATCH ) {
3640                                 continue;
3641                         }
3642
3643                         /* ydnar: bias the surface textures */
3644                         BiasSurfaceTextures( ds );
3645
3646                         /* ydnar: globalizing of fog volume handling (eek a hack) */
3647                         if ( e != entities && si->noFog == qfalse ) {
3648                                 /* find surface origin and offset by entity origin */
3649                                 VectorAdd( ds->mins, ds->maxs, origin );
3650                                 VectorScale( origin, 0.5f, origin );
3651                                 VectorAdd( origin, e->origin, origin );
3652
3653                                 VectorAdd( ds->mins, e->origin, mins );
3654                                 VectorAdd( ds->maxs, e->origin, maxs );
3655
3656                                 /* set the fog number for this surface */
3657                                 ds->fogNum = FogForBounds( mins, maxs, 1.0f );  //%     FogForPoint( origin, 0.0f );
3658                         }
3659                 }
3660
3661                 /* ydnar: remap shader */
3662 /*              if ( ds->shaderInfo->remapShader && ds->shaderInfo->remapShader[ 0 ] ) {
3663                         ds->shaderInfo = ShaderInfoForShader( ds->shaderInfo->remapShader );
3664                 }
3665 */
3666                 /* ydnar: gs mods: handle the various types of surfaces */
3667                 switch ( ds->type )
3668                 {
3669                 /* handle brush faces */
3670                 case SURFACE_FACE:
3671                 case SURFACE_DECAL:
3672                         if ( refs == 0 ) {
3673                                 refs = FilterFaceIntoTree( ds, tree );
3674                         }
3675                         if ( refs > 0 ) {
3676                                 EmitFaceSurface( ds );
3677                         }
3678                         break;
3679
3680                 /* handle patches */
3681                 case SURFACE_PATCH:
3682                         if ( refs == 0 ) {
3683                                 refs = FilterPatchIntoTree( ds, tree );
3684                         }
3685                         if ( refs > 0 ) {
3686                                 EmitPatchSurface( e, ds );
3687                         }
3688                         break;
3689
3690                 /* handle triangle surfaces */
3691                 case SURFACE_TRIANGLES:
3692                 case SURFACE_FORCED_META:
3693                 case SURFACE_META:
3694                         //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%1d] %4d verts %s\n", numSurfs, ds->planar, ds->numVerts, si->shader );
3695                         if ( refs == 0 ) {
3696                                 refs = FilterTrianglesIntoTree( ds, tree );
3697                         }
3698                         if ( refs > 0 ) {
3699                                 EmitTriangleSurface( ds );
3700                         }
3701                         break;
3702
3703                 /* handle foliage surfaces (splash damage/wolf et) */
3704                 case SURFACE_FOLIAGE:
3705                         //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%d] %4d verts %s\n", numSurfs, ds->numFoliageInstances, ds->numVerts, si->shader );
3706                         if ( refs == 0 ) {
3707                                 refs = FilterFoliageIntoTree( ds, tree );
3708                         }
3709                         if ( refs > 0 ) {
3710                                 EmitTriangleSurface( ds );
3711                         }
3712                         break;
3713
3714                 /* handle foghull surfaces */
3715                 case SURFACE_FOGHULL:
3716                         if ( refs == 0 ) {
3717                                 refs = AddReferenceToTree_r( ds, tree->headnode, qfalse );
3718                         }
3719                         if ( refs > 0 ) {
3720                                 EmitTriangleSurface( ds );
3721                         }
3722                         break;
3723
3724                 /* handle flares */
3725                 case SURFACE_FLARE:
3726                         if ( refs == 0 ) {
3727                                 refs = FilterFlareSurfIntoTree( ds, tree );
3728                         }
3729                         if ( refs > 0 ) {
3730                                 EmitFlareSurface( ds );
3731                         }
3732                         break;
3733
3734                 /* handle shader-only surfaces */
3735                 case SURFACE_SHADER:
3736                         refs = 1;
3737                         EmitFlareSurface( ds );
3738                         break;
3739
3740                 /* no references */
3741                 default:
3742                         refs = 0;
3743                         break;
3744                 }
3745
3746                 /* maybe surface got marked as skybox again */
3747                 /* if we keep that flag, it will get scaled up AGAIN */
3748                 if ( sb ) {
3749                         ds->skybox = qfalse;
3750                 }
3751
3752                 /* tot up the references */
3753                 if ( refs > 0 ) {
3754                         /* tot up counts */
3755                         numSurfs++;
3756                         numRefs += refs;
3757
3758                         /* emit extra surface data */
3759                         SetSurfaceExtra( ds, numBSPDrawSurfaces - 1 );
3760                         //%     Sys_FPrintf( SYS_VRB, "%d verts %d indexes\n", ds->numVerts, ds->numIndexes );
3761
3762                         /* one last sanity check */
3763                         {
3764                                 bspDrawSurface_t    *out;
3765                                 out = &bspDrawSurfaces[ numBSPDrawSurfaces - 1 ];
3766                                 if ( out->numVerts == 3 && out->numIndexes > 3 ) {
3767                                         Sys_FPrintf( SYS_WRN, "WARNING: Potentially bad %s surface (%d: %d, %d)\n     %s\n",
3768                                                                 surfaceTypes[ ds->type ],
3769                                                                 numBSPDrawSurfaces - 1, out->numVerts, out->numIndexes, si->shader );
3770                                 }
3771                         }
3772
3773                         /* ydnar: handle skybox surfaces */
3774                         if ( ds->skybox ) {
3775                                 MakeSkyboxSurface( ds );
3776                                 numSkyboxSurfaces++;
3777                         }
3778                 }
3779         }
3780
3781         /* emit some statistics */
3782         Sys_FPrintf( SYS_VRB, "%9d references\n", numRefs );
3783         Sys_FPrintf( SYS_VRB, "%9d (%d) emitted drawsurfs\n", numSurfs, numBSPDrawSurfaces );
3784         Sys_FPrintf( SYS_VRB, "%9d stripped face surfaces\n", numStripSurfaces );
3785         Sys_FPrintf( SYS_VRB, "%9d fanned face surfaces\n", numFanSurfaces );
3786         Sys_FPrintf( SYS_VRB, "%9d maxarea'd face surfaces\n", numMaxAreaSurfaces );
3787         Sys_FPrintf( SYS_VRB, "%9d surface models generated\n", numSurfaceModels );
3788         Sys_FPrintf( SYS_VRB, "%9d skybox surfaces generated\n", numSkyboxSurfaces );
3789         for ( i = 0; i < NUM_SURFACE_TYPES; i++ )
3790                 Sys_FPrintf( SYS_VRB, "%9d %s surfaces\n", numSurfacesByType[ i ], surfaceTypes[ i ] );
3791
3792         Sys_FPrintf( SYS_VRB, "%9d redundant indexes supressed, saving %d Kbytes\n", numRedundantIndexes, ( numRedundantIndexes * 4 / 1024 ) );
3793 }