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