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