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