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