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