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