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 ); /* not strict; we assume we always keep a winding */
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                 ClipWindingEpsilonStrict ( w, plane->normal, plane->dist,
1502                                 ON_EPSILON, &front, &back ); /* strict, we handle the "winding disappeared" case */
1503                 if(!front && !back)
1504                 {
1505                         /* in doubt, register it in both nodes */
1506                         front = CopyWinding(w);
1507                         back = CopyWinding(w);
1508                 }
1509                 FreeWinding( w );
1510
1511                 ClipSideIntoTree_r( front, side, node->children[0] );
1512                 ClipSideIntoTree_r( back, side, node->children[1] );
1513
1514                 return;
1515         }
1516
1517         // if opaque leaf, don't add
1518         if ( !node->opaque ) {
1519                 AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal );
1520         }
1521
1522         FreeWinding( w );
1523         return;
1524 }
1525
1526
1527
1528
1529
1530 static int g_numHiddenFaces, g_numCoinFaces;
1531
1532
1533
1534 /*
1535 CullVectorCompare() - ydnar
1536 compares two vectors with an epsilon
1537 */
1538
1539 #define CULL_EPSILON 0.1f
1540
1541 qboolean CullVectorCompare( const vec3_t v1, const vec3_t v2 )
1542 {
1543         int             i;
1544
1545
1546         for( i = 0; i < 3; i++ )
1547                 if( fabs( v1[ i ] - v2[ i ] ) > CULL_EPSILON )
1548                         return qfalse;
1549         return qtrue;
1550 }
1551
1552
1553
1554 /*
1555 SideInBrush() - ydnar
1556 determines if a brushside lies inside another brush
1557 */
1558
1559 qboolean SideInBrush( side_t *side, brush_t *b )
1560 {
1561         int                     i, s;
1562         plane_t         *plane;
1563
1564
1565         /* ignore sides w/o windings or shaders */
1566         if( side->winding == NULL || side->shaderInfo == NULL )
1567                 return qtrue;
1568
1569         /* ignore culled sides and translucent brushes */
1570         if( side->culled == qtrue || (b->compileFlags & C_TRANSLUCENT) )
1571                 return qfalse;
1572
1573         /* side iterator */
1574         for( i = 0; i < b->numsides; i++ )
1575         {
1576                 /* fail if any sides are caulk */
1577                 if( b->sides[ i ].compileFlags & C_NODRAW )
1578                         return qfalse;
1579
1580                 /* check if side's winding is on or behind the plane */
1581                 plane = &mapplanes[ b->sides[ i ].planenum ];
1582                 s = WindingOnPlaneSide( side->winding, plane->normal, plane->dist );
1583                 if( s == SIDE_FRONT || s == SIDE_CROSS )
1584                         return qfalse;
1585         }
1586
1587         /* don't cull autosprite or polygonoffset surfaces */
1588         if( side->shaderInfo )
1589         {
1590                 if( side->shaderInfo->autosprite || side->shaderInfo->polygonOffset )
1591                         return qfalse;
1592         }
1593
1594         /* inside */
1595         side->culled = qtrue;
1596         g_numHiddenFaces++;
1597         return qtrue;
1598 }
1599
1600
1601 /*
1602 CullSides() - ydnar
1603 culls obscured or buried brushsides from the map
1604 */
1605
1606 void CullSides( entity_t *e )
1607 {
1608         int                     numPoints;
1609         int                     i, j, k, l, first, second, dir;
1610         winding_t       *w1, *w2;
1611         brush_t *b1, *b2;
1612         side_t          *side1, *side2;
1613
1614
1615         /* note it */
1616         Sys_FPrintf( SYS_VRB, "--- CullSides ---\n" );
1617
1618         g_numHiddenFaces = 0;
1619         g_numCoinFaces = 0;
1620
1621         /* brush interator 1 */
1622         for( b1 = e->brushes; b1; b1 = b1->next )
1623         {
1624                 /* sides check */
1625                 if( b1->numsides < 1 )
1626                         continue;
1627
1628                 /* brush iterator 2 */
1629                 for( b2 = b1->next; b2; b2 = b2->next )
1630                 {
1631                         /* sides check */
1632                         if( b2->numsides < 1 )
1633                                 continue;
1634
1635                         /* original check */
1636                         if( b1->original == b2->original && b1->original != NULL )
1637                                 continue;
1638
1639                         /* bbox check */
1640                         j = 0;
1641                         for( i = 0; i < 3; i++ )
1642                                 if( b1->mins[ i ] > b2->maxs[ i ] || b1->maxs[ i ] < b2->mins[ i ] )
1643                                         j++;
1644                         if( j )
1645                                 continue;
1646
1647                         /* cull inside sides */
1648                         for( i = 0; i < b1->numsides; i++ )
1649                                 SideInBrush( &b1->sides[ i ], b2 );
1650                         for( i = 0; i < b2->numsides; i++ )
1651                                 SideInBrush( &b2->sides[ i ], b1 );
1652
1653                         /* side iterator 1 */
1654                         for( i = 0; i < b1->numsides; i++ )
1655                         {
1656                                 /* winding check */
1657                                 side1 = &b1->sides[ i ];
1658                                 w1 = side1->winding;
1659                                 if( w1 == NULL )
1660                                         continue;
1661                                 numPoints = w1->numpoints;
1662                                 if( side1->shaderInfo == NULL )
1663                                         continue;
1664
1665                                 /* side iterator 2 */
1666                                 for( j = 0; j < b2->numsides; j++ )
1667                                 {
1668                                         /* winding check */
1669                                         side2 = &b2->sides[ j ];
1670                                         w2 = side2->winding;
1671                                         if( w2 == NULL )
1672                                                 continue;
1673                                         if( side2->shaderInfo == NULL )
1674                                                 continue;
1675                                         if( w1->numpoints != w2->numpoints )
1676                                                 continue;
1677                                         if( side1->culled == qtrue && side2->culled == qtrue )
1678                                                 continue;
1679
1680                                         /* compare planes */
1681                                         if( (side1->planenum & ~0x00000001) != (side2->planenum & ~0x00000001) )
1682                                                 continue;
1683
1684                                         /* get autosprite and polygonoffset status */
1685                                         if( side1->shaderInfo &&
1686                                                 (side1->shaderInfo->autosprite || side1->shaderInfo->polygonOffset) )
1687                                                 continue;
1688                                         if( side2->shaderInfo &&
1689                                                 (side2->shaderInfo->autosprite || side2->shaderInfo->polygonOffset) )
1690                                                 continue;
1691
1692                                         /* find first common point */
1693                                         first = -1;
1694                                         for( k = 0; k < numPoints; k++ )
1695                                         {
1696                                                 if( VectorCompare( w1->p[ 0 ], w2->p[ k ] ) )
1697                                                 {
1698                                                         first = k;
1699                                                         k = numPoints;
1700                                                 }
1701                                         }
1702                                         if( first == -1 )
1703                                                 continue;
1704
1705                                         /* find second common point (regardless of winding order) */
1706                                         second = -1;
1707                                         dir = 0;
1708                                         if( (first + 1) < numPoints )
1709                                                 second = first + 1;
1710                                         else
1711                                                 second = 0;
1712                                         if( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) )
1713                                                 dir = 1;
1714                                         else
1715                                         {
1716                                                 if( first > 0 )
1717                                                         second = first - 1;
1718                                                 else
1719                                                         second = numPoints - 1;
1720                                                 if( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) )
1721                                                         dir = -1;
1722                                         }
1723                                         if( dir == 0 )
1724                                                 continue;
1725
1726                                         /* compare the rest of the points */
1727                                         l = first;
1728                                         for( k = 0; k < numPoints; k++ )
1729                                         {
1730                                                 if( !CullVectorCompare( w1->p[ k ], w2->p[ l ] ) )
1731                                                         k = 100000;
1732
1733                                                 l += dir;
1734                                                 if( l < 0 )
1735                                                         l = numPoints - 1;
1736                                                 else if( l >= numPoints )
1737                                                         l = 0;
1738                                         }
1739                                         if( k >= 100000 )
1740                                                 continue;
1741
1742                                         /* cull face 1 */
1743                                         if( !side2->culled && !(side2->compileFlags & C_TRANSLUCENT) && !(side2->compileFlags & C_NODRAW) )
1744                                         {
1745                                                 side1->culled = qtrue;
1746                                                 g_numCoinFaces++;
1747                                         }
1748
1749                                         if( side1->planenum == side2->planenum && side1->culled == qtrue )
1750                                                 continue;
1751
1752                                         /* cull face 2 */
1753                                         if( !side1->culled && !(side1->compileFlags & C_TRANSLUCENT) && !(side1->compileFlags & C_NODRAW) )
1754                                         {
1755                                                 side2->culled = qtrue;
1756                                                 g_numCoinFaces++;
1757                                         }
1758                                 }
1759                         }
1760                 }
1761         }
1762
1763         /* emit some stats */
1764         Sys_FPrintf( SYS_VRB, "%9d hidden faces culled\n", g_numHiddenFaces );
1765         Sys_FPrintf( SYS_VRB, "%9d coincident faces culled\n", g_numCoinFaces );
1766 }
1767
1768
1769
1770
1771 /*
1772 ClipSidesIntoTree()
1773
1774 creates side->visibleHull for all visible sides
1775
1776 the drawsurf for a side will consist of the convex hull of
1777 all points in non-opaque clusters, which allows overlaps
1778 to be trimmed off automatically.
1779 */
1780
1781 void ClipSidesIntoTree( entity_t *e, tree_t *tree )
1782 {
1783         brush_t         *b;
1784         int                             i;
1785         winding_t               *w;
1786         side_t                  *side, *newSide;
1787         shaderInfo_t    *si;
1788
1789
1790         /* ydnar: cull brush sides */
1791         CullSides( e );
1792
1793         /* note it */
1794         Sys_FPrintf( SYS_VRB, "--- ClipSidesIntoTree ---\n" );
1795
1796         /* walk the brush list */
1797         for( b = e->brushes; b; b = b->next )
1798         {
1799                 /* walk the brush sides */
1800                 for( i = 0; i < b->numsides; i++ )
1801                 {
1802                         /* get side */
1803                         side = &b->sides[ i ];
1804                         if( side->winding == NULL )
1805                                 continue;
1806
1807                         /* copy the winding */
1808                         w = CopyWinding( side->winding );
1809                         side->visibleHull = NULL;
1810                         ClipSideIntoTree_r( w, side, tree->headnode );
1811
1812                         /* anything left? */
1813                         w = side->visibleHull;
1814                         if( w == NULL )
1815                                 continue;
1816
1817                         /* shader? */
1818                         si = side->shaderInfo;
1819                         if( si == NULL )
1820                                 continue;
1821
1822                         /* don't create faces for non-visible sides */
1823                         /* ydnar: except indexed shaders, like common/terrain and nodraw fog surfaces */
1824                         if( (si->compileFlags & C_NODRAW) && si->indexed == qfalse && !(si->compileFlags & C_FOG) )
1825                                 continue;
1826
1827                         /* always use the original winding for autosprites and noclip faces */
1828                         if( si->autosprite || si->noClip )
1829                                 w = side->winding;
1830
1831                         /* save this winding as a visible surface */
1832                         DrawSurfaceForSide( e, b, side, w );
1833
1834                         /* make a back side for fog */
1835                         if( !(si->compileFlags & C_FOG) )
1836                                 continue;
1837
1838                         /* duplicate the up-facing side */
1839                         w = ReverseWinding( w );
1840                         newSide = safe_malloc( sizeof( *side ) );
1841                         *newSide = *side;
1842                         newSide->visibleHull = w;
1843                         newSide->planenum ^= 1;
1844
1845                         /* save this winding as a visible surface */
1846                         DrawSurfaceForSide( e, b, newSide, w );
1847                 }
1848         }
1849 }
1850
1851
1852
1853 /*
1854
1855 this section deals with filtering drawsurfaces into the bsp tree,
1856 adding references to each leaf a surface touches
1857
1858 */
1859
1860 /*
1861 AddReferenceToLeaf() - ydnar
1862 adds a reference to surface ds in the bsp leaf node
1863 */
1864
1865 int AddReferenceToLeaf( mapDrawSurface_t *ds, node_t *node )
1866 {
1867         drawSurfRef_t   *dsr;
1868
1869
1870         /* dummy check */
1871         if( node->planenum != PLANENUM_LEAF || node->opaque )
1872                 return 0;
1873
1874         /* try to find an existing reference */
1875         for( dsr = node->drawSurfReferences; dsr; dsr = dsr->nextRef )
1876         {
1877                 if( dsr->outputNum == numBSPDrawSurfaces )
1878                         return 0;
1879         }
1880
1881         /* add a new reference */
1882         dsr = safe_malloc( sizeof( *dsr ) );
1883         dsr->outputNum = numBSPDrawSurfaces;
1884         dsr->nextRef = node->drawSurfReferences;
1885         node->drawSurfReferences = dsr;
1886
1887         /* ydnar: sky/skybox surfaces */
1888         if( node->skybox )
1889                 ds->skybox = qtrue;
1890         if( ds->shaderInfo->compileFlags & C_SKY )
1891                 node->sky = qtrue;
1892
1893         /* return */
1894         return 1;
1895 }
1896
1897
1898
1899 /*
1900 AddReferenceToTree_r() - ydnar
1901 adds a reference to the specified drawsurface to every leaf in the tree
1902 */
1903
1904 int AddReferenceToTree_r( mapDrawSurface_t *ds, node_t *node, qboolean skybox )
1905 {
1906         int             i, refs = 0;
1907
1908
1909         /* dummy check */
1910         if( node == NULL )
1911                 return 0;
1912
1913         /* is this a decision node? */
1914         if( node->planenum != PLANENUM_LEAF )
1915         {
1916                 /* add to child nodes and return */
1917                 refs += AddReferenceToTree_r( ds, node->children[ 0 ], skybox );
1918                 refs += AddReferenceToTree_r( ds, node->children[ 1 ], skybox );
1919                 return refs;
1920         }
1921
1922         /* ydnar */
1923         if( skybox )
1924         {
1925                 /* skybox surfaces only get added to sky leaves */
1926                 if( !node->sky )
1927                         return 0;
1928
1929                 /* increase the leaf bounds */
1930                 for( i = 0; i < ds->numVerts; i++ )
1931                         AddPointToBounds( ds->verts[ i ].xyz, node->mins, node->maxs );
1932         }
1933
1934         /* add a reference */
1935         return AddReferenceToLeaf( ds, node );
1936 }
1937
1938
1939
1940 /*
1941 FilterPointIntoTree_r() - ydnar
1942 filters a single point from a surface into the tree
1943 */
1944
1945 int FilterPointIntoTree_r( vec3_t point, mapDrawSurface_t *ds, node_t *node )
1946 {
1947         float                   d;
1948         plane_t                 *plane;
1949         int                             refs = 0;
1950
1951
1952         /* is this a decision node? */
1953         if( node->planenum != PLANENUM_LEAF )
1954         {
1955                 /* classify the point in relation to the plane */
1956                 plane = &mapplanes[ node->planenum ];
1957                 d = DotProduct( point, plane->normal ) - plane->dist;
1958
1959                 /* filter by this plane */
1960                 refs = 0;
1961                 if( d >= -ON_EPSILON )
1962                         refs += FilterPointIntoTree_r( point, ds, node->children[ 0 ] );
1963                 if( d <= ON_EPSILON )
1964                         refs += FilterPointIntoTree_r( point, ds, node->children[ 1 ] );
1965
1966                 /* return */
1967                 return refs;
1968         }
1969
1970         /* add a reference */
1971         return AddReferenceToLeaf( ds, node );
1972 }
1973
1974 /*
1975 FilterPointConvexHullIntoTree_r() - ydnar
1976 filters the convex hull of multiple points from a surface into the tree
1977 */
1978
1979 int FilterPointConvexHullIntoTree_r( vec3_t **points, int npoints, mapDrawSurface_t *ds, node_t *node )
1980 {
1981         float                   d, dmin, dmax;
1982         plane_t                 *plane;
1983         int                             refs = 0;
1984         int                             i;
1985
1986         if(!points)
1987                 return 0;
1988
1989         /* is this a decision node? */
1990         if( node->planenum != PLANENUM_LEAF )
1991         {
1992                 /* classify the point in relation to the plane */
1993                 plane = &mapplanes[ node->planenum ];
1994
1995                 dmin = dmax = DotProduct( *(points[0]), plane->normal ) - plane->dist;
1996                 for(i = 1; i < npoints; ++i)
1997                 {
1998                         d = DotProduct( *(points[i]), plane->normal ) - plane->dist;
1999                         if(d > dmax)
2000                                 dmax = d;
2001                         if(d < dmin)
2002                                 dmin = d;
2003                 }
2004
2005                 /* filter by this plane */
2006                 refs = 0;
2007                 if( dmax >= -ON_EPSILON )
2008                         refs += FilterPointConvexHullIntoTree_r( points, npoints, ds, node->children[ 0 ] );
2009                 if( dmin <= ON_EPSILON )
2010                         refs += FilterPointConvexHullIntoTree_r( points, npoints, ds, node->children[ 1 ] );
2011
2012                 /* return */
2013                 return refs;
2014         }
2015
2016         /* add a reference */
2017         return AddReferenceToLeaf( ds, node );
2018 }
2019
2020
2021 /*
2022 FilterWindingIntoTree_r() - ydnar
2023 filters a winding from a drawsurface into the tree
2024 */
2025
2026 int FilterWindingIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node )
2027 {
2028         int                             i, refs = 0;
2029         plane_t                 *p1, *p2;
2030         vec4_t                  plane1, plane2, reverse;
2031         winding_t               *fat, *front, *back;
2032         shaderInfo_t    *si;
2033
2034
2035         /* get shaderinfo */
2036         si = ds->shaderInfo;
2037
2038         /* ydnar: is this the head node? */
2039         if( node->parent == NULL && si != NULL &&
2040                 (si->mins[ 0 ] != 0.0f || si->maxs[ 0 ] != 0.0f ||
2041                 si->mins[ 1 ] != 0.0f || si->maxs[ 1 ] != 0.0f ||
2042                 si->mins[ 2 ] != 0.0f || si->maxs[ 2 ] != 0.0f) )
2043         {
2044                 static qboolean warned = qfalse;
2045                 if(!warned)
2046                 {
2047                         Sys_Printf( "WARNING: this map uses the deformVertexes move hack\n" );
2048                         warned = qtrue;
2049                 }
2050
2051                 /* 'fatten' the winding by the shader mins/maxs (parsed from vertexDeform move) */
2052                 /* note this winding is completely invalid (concave, nonplanar, etc) */
2053                 fat = AllocWinding( w->numpoints * 3 + 3 );
2054                 fat->numpoints = w->numpoints * 3 + 3;
2055                 for( i = 0; i < w->numpoints; i++ )
2056                 {
2057                         VectorCopy( w->p[ i ], fat->p[ i ] );
2058                         VectorAdd( w->p[ i ], si->mins, fat->p[ i + (w->numpoints+1) ] );
2059                         VectorAdd( w->p[ i ], si->maxs, fat->p[ i + (w->numpoints+1) * 2 ] );
2060                 }
2061                 VectorCopy( w->p[ 0 ], fat->p[ i ] );
2062                 VectorAdd( w->p[ 0 ], si->mins, fat->p[ i + w->numpoints ] );
2063                 VectorAdd( w->p[ 0 ], si->maxs, fat->p[ i + w->numpoints * 2 ] );
2064
2065                 /*
2066                  * note: this winding is STILL not suitable for ClipWindingEpsilon, and
2067                  * also does not really fulfill the intention as it only contains
2068                  * origin, +mins, +maxs, but thanks to the "closing" points I just
2069                  * added to the three sub-windings, the fattening at least doesn't make
2070                  * it worse
2071                  */
2072
2073                 FreeWinding( w );
2074                 w = fat;
2075         }
2076
2077         /* is this a decision node? */
2078         if( node->planenum != PLANENUM_LEAF )
2079         {
2080                 /* get node plane */
2081                 p1 = &mapplanes[ node->planenum ];
2082                 VectorCopy( p1->normal, plane1 );
2083                 plane1[ 3 ] = p1->dist;
2084
2085                 /* check if surface is planar */
2086                 if( ds->planeNum >= 0 )
2087                 {
2088                         /* get surface plane */
2089                         p2 = &mapplanes[ ds->planeNum ];
2090                         VectorCopy( p2->normal, plane2 );
2091                         plane2[ 3 ] = p2->dist;
2092
2093                         #if 0
2094                                 /* div0: this is the plague (inaccurate) */
2095
2096                                 /* invert surface plane */
2097                                 VectorSubtract( vec3_origin, plane2, reverse );
2098                                 reverse[ 3 ] = -plane2[ 3 ];
2099
2100                                 /* compare planes */
2101                                 if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
2102                                         return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2103                                 if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
2104                                         return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2105                         #else
2106                                 /* div0: this is the cholera (doesn't hit enough) */
2107
2108                                 /* the drawsurf might have an associated plane, if so, force a filter here */
2109                                 if( ds->planeNum == node->planenum )
2110                                         return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2111                                 if( ds->planeNum == (node->planenum ^ 1) )
2112                                         return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2113                         #endif
2114                 }
2115
2116                 /* clip the winding by this plane */
2117                 ClipWindingEpsilonStrict( w, plane1, plane1[ 3 ], ON_EPSILON, &front, &back ); /* strict; we handle the "winding disappeared" case */
2118
2119                 /* filter by this plane */
2120                 refs = 0;
2121                 if( front == NULL && back == NULL )
2122                 {
2123                         /* same plane, this is an ugly hack */
2124                         /* but better too many than too few refs */
2125                         refs += FilterWindingIntoTree_r( CopyWinding(w), ds, node->children[ 0 ] );
2126                         refs += FilterWindingIntoTree_r( CopyWinding(w), ds, node->children[ 1 ] );
2127                 }
2128                 if( front != NULL )
2129                         refs += FilterWindingIntoTree_r( front, ds, node->children[ 0 ] );
2130                 if( back != NULL )
2131                         refs += FilterWindingIntoTree_r( back, ds, node->children[ 1 ] );
2132                 FreeWinding( w );
2133
2134                 /* return */
2135                 return refs;
2136         }
2137
2138         /* add a reference */
2139         return AddReferenceToLeaf( ds, node );
2140 }
2141
2142
2143
2144 /*
2145 FilterFaceIntoTree()
2146 filters a planar winding face drawsurface into the bsp tree
2147 */
2148
2149 int     FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2150 {
2151         winding_t       *w;
2152         int                     refs = 0;
2153
2154
2155         /* make a winding and filter it into the tree */
2156         w = WindingFromDrawSurf( ds );
2157         refs = FilterWindingIntoTree_r( w, ds, tree->headnode );
2158
2159         /* return */
2160         return refs;
2161 }
2162
2163
2164
2165 /*
2166 FilterPatchIntoTree()
2167 subdivides a patch into an approximate curve and filters it into the tree
2168 */
2169
2170 #define FILTER_SUBDIVISION              8
2171
2172 static int FilterPatchIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2173 {
2174         int                                     x, y, refs = 0;
2175
2176         for(y = 0; y + 2 < ds->patchHeight; y += 2)
2177                 for(x = 0; x + 2 < ds->patchWidth; x += 2)
2178                 {
2179                         vec3_t *points[9];
2180                         points[0] = &ds->verts[(y+0) * ds->patchWidth + (x+0)].xyz;
2181                         points[1] = &ds->verts[(y+0) * ds->patchWidth + (x+1)].xyz;
2182                         points[2] = &ds->verts[(y+0) * ds->patchWidth + (x+2)].xyz;
2183                         points[3] = &ds->verts[(y+1) * ds->patchWidth + (x+0)].xyz;
2184                         points[4] = &ds->verts[(y+1) * ds->patchWidth + (x+1)].xyz;
2185                         points[5] = &ds->verts[(y+1) * ds->patchWidth + (x+2)].xyz;
2186                         points[6] = &ds->verts[(y+2) * ds->patchWidth + (x+0)].xyz;
2187                         points[7] = &ds->verts[(y+2) * ds->patchWidth + (x+1)].xyz;
2188                         points[8] = &ds->verts[(y+2) * ds->patchWidth + (x+2)].xyz;
2189                         refs += FilterPointConvexHullIntoTree_r(points, 9, ds, tree->headnode);
2190                 }
2191
2192         return refs;
2193 }
2194
2195
2196
2197 /*
2198 FilterTrianglesIntoTree()
2199 filters a triangle surface (meta, model) into the bsp
2200 */
2201
2202 static int FilterTrianglesIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2203 {
2204         int                     i, refs;
2205         winding_t       *w;
2206
2207
2208         /* ydnar: gs mods: this was creating bogus triangles before */
2209         refs = 0;
2210         for( i = 0; i < ds->numIndexes; i += 3 )
2211         {
2212                 /* error check */
2213                 if( ds->indexes[ i ] >= ds->numVerts ||
2214                         ds->indexes[ i + 1 ] >= ds->numVerts ||
2215                         ds->indexes[ i + 2 ] >= ds->numVerts )
2216                         Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2217
2218                 /* make a triangle winding and filter it into the tree */
2219                 w = AllocWinding( 3 );
2220                 w->numpoints = 3;
2221                 VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2222                 VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2223                 VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2224                 refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2225         }
2226
2227         /* use point filtering as well */
2228         for( i = 0; i < ds->numVerts; i++ )
2229                 refs += FilterPointIntoTree_r( ds->verts[ i ].xyz, ds, tree->headnode );
2230
2231         return refs;
2232 }
2233
2234
2235
2236 /*
2237 FilterFoliageIntoTree()
2238 filters a foliage surface (wolf et/splash damage)
2239 */
2240
2241 static int FilterFoliageIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2242 {
2243         int                             f, i, refs;
2244         bspDrawVert_t   *instance;
2245         vec3_t                  xyz;
2246         winding_t               *w;
2247
2248
2249         /* walk origin list */
2250         refs = 0;
2251         for( f = 0; f < ds->numFoliageInstances; f++ )
2252         {
2253                 /* get instance */
2254                 instance = ds->verts + ds->patchHeight + f;
2255
2256                 /* walk triangle list */
2257                 for( i = 0; i < ds->numIndexes; i += 3 )
2258                 {
2259                         /* error check */
2260                         if( ds->indexes[ i ] >= ds->numVerts ||
2261                                 ds->indexes[ i + 1 ] >= ds->numVerts ||
2262                                 ds->indexes[ i + 2 ] >= ds->numVerts )
2263                                 Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2264
2265                         /* make a triangle winding and filter it into the tree */
2266                         w = AllocWinding( 3 );
2267                         w->numpoints = 3;
2268                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2269                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2270                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2271                         refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2272                 }
2273
2274                 /* use point filtering as well */
2275                 for( i = 0; i < (ds->numVerts - ds->numFoliageInstances); i++ )
2276                 {
2277                         VectorAdd( instance->xyz, ds->verts[ i ].xyz, xyz );
2278                         refs += FilterPointIntoTree_r( xyz, ds, tree->headnode );
2279                 }
2280         }
2281
2282         return refs;
2283 }
2284
2285
2286
2287 /*
2288 FilterFlareIntoTree()
2289 simple point filtering for flare surfaces
2290 */
2291 static int FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2292 {
2293         return FilterPointIntoTree_r( ds->lightmapOrigin, ds, tree->headnode );
2294 }
2295
2296
2297
2298 /*
2299 EmitDrawVerts() - ydnar
2300 emits bsp drawverts from a map drawsurface
2301 */
2302
2303 void EmitDrawVerts( mapDrawSurface_t *ds, bspDrawSurface_t *out )
2304 {
2305         int                             i, k;
2306         bspDrawVert_t   *dv;
2307         shaderInfo_t    *si;
2308         float                   offset;
2309
2310
2311         /* get stuff */
2312         si = ds->shaderInfo;
2313         offset = si->offset;
2314
2315         /* copy the verts */
2316         out->firstVert = numBSPDrawVerts;
2317         out->numVerts = ds->numVerts;
2318         for( i = 0; i < ds->numVerts; i++ )
2319         {
2320                 /* allocate a new vert */
2321                 IncDrawVerts();
2322                 dv = &bspDrawVerts[ numBSPDrawVerts - 1 ];
2323
2324                 /* copy it */
2325                 memcpy( dv, &ds->verts[ i ], sizeof( *dv ) );
2326
2327                 /* offset? */
2328                 if( offset != 0.0f )
2329                         VectorMA( dv->xyz, offset, dv->normal, dv->xyz );
2330
2331                 /* expand model bounds
2332                    necessary because of misc_model surfaces on entities
2333                    note: does not happen on worldspawn as its bounds is only used for determining lightgrid bounds */
2334                 if( numBSPModels > 0 )
2335                         AddPointToBounds( dv->xyz, bspModels[ numBSPModels ].mins, bspModels[ numBSPModels ].maxs );
2336
2337                 /* debug color? */
2338                 if( debugSurfaces )
2339                 {
2340                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
2341                                 VectorCopy( debugColors[ (ds - mapDrawSurfs) % 12 ], dv->color[ k ] );
2342                 }
2343         }
2344 }
2345
2346
2347
2348 /*
2349 FindDrawIndexes() - ydnar
2350 this attempts to find a run of indexes in the bsp that match the given indexes
2351 this tends to reduce the size of the bsp index pool by 1/3 or more
2352 returns numIndexes + 1 if the search failed
2353 */
2354
2355 int FindDrawIndexes( int numIndexes, int *indexes )
2356 {
2357         int             i, j, numTestIndexes;
2358
2359
2360         /* dummy check */
2361         if( numIndexes < 3 || numBSPDrawIndexes < numIndexes || indexes == NULL )
2362                 return numBSPDrawIndexes;
2363
2364         /* set limit */
2365         numTestIndexes = 1 + numBSPDrawIndexes - numIndexes;
2366
2367         /* handle 3 indexes as a special case for performance */
2368         if( numIndexes == 3 )
2369         {
2370                 /* run through all indexes */
2371                 for( i = 0; i < numTestIndexes; i++ )
2372                 {
2373                         /* test 3 indexes */
2374                         if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2375                                 indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2376                                 indexes[ 2 ] == bspDrawIndexes[ i + 2 ] )
2377                         {
2378                                 numRedundantIndexes += numIndexes;
2379                                 return i;
2380                         }
2381                 }
2382
2383                 /* failed */
2384                 return numBSPDrawIndexes;
2385         }
2386
2387         /* handle 4 or more indexes */
2388         for( i = 0; i < numTestIndexes; i++ )
2389         {
2390                 /* test first 4 indexes */
2391                 if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2392                         indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2393                         indexes[ 2 ] == bspDrawIndexes[ i + 2 ] &&
2394                         indexes[ 3 ] == bspDrawIndexes[ i + 3 ] )
2395                 {
2396                         /* handle 4 indexes */
2397                         if( numIndexes == 4 )
2398                                 return i;
2399
2400                         /* test the remainder */
2401                         for( j = 4; j < numIndexes; j++ )
2402                         {
2403                                 if( indexes[ j ] != bspDrawIndexes[ i + j ] )
2404                                         break;
2405                                 else if( j == (numIndexes - 1) )
2406                                 {
2407                                         numRedundantIndexes += numIndexes;
2408                                         return i;
2409                                 }
2410                         }
2411                 }
2412         }
2413
2414         /* failed */
2415         return numBSPDrawIndexes;
2416 }
2417
2418
2419
2420 /*
2421 EmitDrawIndexes() - ydnar
2422 attempts to find an existing run of drawindexes before adding new ones
2423 */
2424
2425 void EmitDrawIndexes( mapDrawSurface_t *ds, bspDrawSurface_t *out )
2426 {
2427         int                     i;
2428
2429
2430         /* attempt to use redundant indexing */
2431         out->firstIndex = FindDrawIndexes( ds->numIndexes, ds->indexes );
2432         out->numIndexes = ds->numIndexes;
2433         if( out->firstIndex == numBSPDrawIndexes )
2434         {
2435                 /* copy new unique indexes */
2436                 for( i = 0; i < ds->numIndexes; i++ )
2437                 {
2438                         AUTOEXPAND_BY_REALLOC_BSP(DrawIndexes, 1024);
2439                         bspDrawIndexes[ numBSPDrawIndexes ] = ds->indexes[ i ];
2440
2441                         /* validate the index */
2442                         if( ds->type != SURFACE_PATCH )
2443                         {
2444                                 if( bspDrawIndexes[ numBSPDrawIndexes ] < 0 || bspDrawIndexes[ numBSPDrawIndexes ] >= ds->numVerts )
2445                                 {
2446                                         Sys_Printf( "WARNING: %d %s has invalid index %d (%d)\n",
2447                                                 numBSPDrawSurfaces,
2448                                                 ds->shaderInfo->shader,
2449                                                 bspDrawIndexes[ numBSPDrawIndexes ],
2450                                                 i );
2451                                         bspDrawIndexes[ numBSPDrawIndexes ] = 0;
2452                                 }
2453                         }
2454
2455                         /* increment index count */
2456                         numBSPDrawIndexes++;
2457                 }
2458         }
2459 }
2460
2461
2462
2463
2464 /*
2465 EmitFlareSurface()
2466 emits a bsp flare drawsurface
2467 */
2468
2469 void EmitFlareSurface( mapDrawSurface_t *ds )
2470 {
2471         int                                             i;
2472         bspDrawSurface_t                *out;
2473
2474
2475         /* ydnar: nuking useless flare drawsurfaces */
2476         if( emitFlares == qfalse && ds->type != SURFACE_SHADER )
2477                 return;
2478
2479         /* limit check */
2480         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2481                 Error( "MAX_MAP_DRAW_SURFS" );
2482
2483         /* allocate a new surface */
2484         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2485                 Error( "MAX_MAP_DRAW_SURFS" );
2486         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2487         ds->outputNum = numBSPDrawSurfaces;
2488         numBSPDrawSurfaces++;
2489         memset( out, 0, sizeof( *out ) );
2490
2491         /* set it up */
2492         out->surfaceType = MST_FLARE;
2493         out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2494         out->fogNum = ds->fogNum;
2495
2496         /* RBSP */
2497         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2498         {
2499                 out->lightmapNum[ i ] = -3;
2500                 out->lightmapStyles[ i ] = LS_NONE;
2501                 out->vertexStyles[ i ] = LS_NONE;
2502         }
2503         out->lightmapStyles[ 0 ] = ds->lightStyle;
2504         out->vertexStyles[ 0 ] = ds->lightStyle;
2505
2506         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );                  /* origin */
2507         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );    /* color */
2508         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2509         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );    /* normal */
2510
2511         /* add to count */
2512         numSurfacesByType[ ds->type ]++;
2513 }
2514
2515 /*
2516 EmitPatchSurface()
2517 emits a bsp patch drawsurface
2518 */
2519
2520 void EmitPatchSurface( entity_t *e, mapDrawSurface_t *ds )
2521 {
2522         int                                     i, j;
2523         bspDrawSurface_t        *out;
2524         int                                     surfaceFlags, contentFlags;
2525         int                                     forcePatchMeta;
2526
2527         /* vortex: _patchMeta support */
2528         forcePatchMeta = IntForKey(e, "_patchMeta" );
2529         if (!forcePatchMeta)
2530                 forcePatchMeta = IntForKey(e, "patchMeta" );
2531
2532         /* invert the surface if necessary */
2533         if( ds->backSide || ds->shaderInfo->invert )
2534         {
2535                 bspDrawVert_t   *dv1, *dv2, temp;
2536
2537                 /* walk the verts, flip the normal */
2538                 for( i = 0; i < ds->numVerts; i++ )
2539                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2540
2541                 /* walk the verts again, but this time reverse their order */
2542                 for( j = 0; j < ds->patchHeight; j++ )
2543                 {
2544                         for( i = 0; i < (ds->patchWidth / 2); i++ )
2545                         {
2546                                 dv1 = &ds->verts[ j * ds->patchWidth + i ];
2547                                 dv2 = &ds->verts[ j * ds->patchWidth + (ds->patchWidth - i - 1) ];
2548                                 memcpy( &temp, dv1, sizeof( bspDrawVert_t ) );
2549                                 memcpy( dv1, dv2, sizeof( bspDrawVert_t ) );
2550                                 memcpy( dv2, &temp, sizeof( bspDrawVert_t ) );
2551                         }
2552                 }
2553
2554                 /* invert facing */
2555                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2556         }
2557
2558         /* allocate a new surface */
2559         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2560                 Error( "MAX_MAP_DRAW_SURFS" );
2561         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2562         ds->outputNum = numBSPDrawSurfaces;
2563         numBSPDrawSurfaces++;
2564         memset( out, 0, sizeof( *out ) );
2565
2566         /* set it up */
2567         out->surfaceType = MST_PATCH;
2568         if( debugSurfaces )
2569                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2570         else if( patchMeta || forcePatchMeta )
2571         {
2572                 /* patch meta requires that we have nodraw patches for collision */
2573                 surfaceFlags = ds->shaderInfo->surfaceFlags;
2574                 contentFlags = ds->shaderInfo->contentFlags;
2575                 ApplySurfaceParm( "nodraw", &contentFlags, &surfaceFlags, NULL );
2576                 ApplySurfaceParm( "pointlight", &contentFlags, &surfaceFlags, NULL );
2577
2578                 /* we don't want this patch getting lightmapped */
2579                 VectorClear( ds->lightmapVecs[ 2 ] );
2580                 VectorClear( ds->lightmapAxis );
2581                 ds->sampleSize = 0;
2582
2583                 /* emit the new fake shader */
2584                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &contentFlags, &surfaceFlags );
2585         }
2586         else
2587                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2588         out->patchWidth = ds->patchWidth;
2589         out->patchHeight = ds->patchHeight;
2590         out->fogNum = ds->fogNum;
2591
2592         /* RBSP */
2593         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2594         {
2595                 out->lightmapNum[ i ] = -3;
2596                 out->lightmapStyles[ i ] = LS_NONE;
2597                 out->vertexStyles[ i ] = LS_NONE;
2598         }
2599         out->lightmapStyles[ 0 ] = LS_NORMAL;
2600         out->vertexStyles[ 0 ] = LS_NORMAL;
2601
2602         /* ydnar: gs mods: previously, the lod bounds were stored in lightmapVecs[ 0 ] and [ 1 ], moved to bounds[ 0 ] and [ 1 ] */
2603         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2604         VectorCopy( ds->bounds[ 0 ], out->lightmapVecs[ 0 ] );
2605         VectorCopy( ds->bounds[ 1 ], out->lightmapVecs[ 1 ] );
2606         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2607
2608         /* ydnar: gs mods: clear out the plane normal */
2609         if( ds->planar == qfalse )
2610                 VectorClear( out->lightmapVecs[ 2 ] );
2611
2612         /* emit the verts and indexes */
2613         EmitDrawVerts( ds, out );
2614         EmitDrawIndexes( ds, out );
2615
2616         /* add to count */
2617         numSurfacesByType[ ds->type ]++;
2618 }
2619
2620 /*
2621 OptimizeTriangleSurface() - ydnar
2622 optimizes the vertex/index data in a triangle surface
2623 */
2624
2625 #define VERTEX_CACHE_SIZE       16
2626
2627 static void OptimizeTriangleSurface( mapDrawSurface_t *ds )
2628 {
2629         int             i, j, k, temp, first, best, bestScore, score;
2630         int             vertexCache[ VERTEX_CACHE_SIZE + 1 ];   /* one more for optimizing insert */
2631         int             *indexes;
2632
2633
2634         /* certain surfaces don't get optimized */
2635         if( ds->numIndexes <= VERTEX_CACHE_SIZE ||
2636                 ds->shaderInfo->autosprite )
2637                 return;
2638
2639         /* create index scratch pad */
2640         indexes = safe_malloc( ds->numIndexes * sizeof( *indexes ) );
2641         memcpy( indexes, ds->indexes, ds->numIndexes * sizeof( *indexes ) );
2642
2643         /* setup */
2644         for( i = 0; i <= VERTEX_CACHE_SIZE && i < ds->numIndexes; i++ )
2645                 vertexCache[ i ] = indexes[ i ];
2646
2647         /* add triangles in a vertex cache-aware order */
2648         for( i = 0; i < ds->numIndexes; i += 3 )
2649         {
2650                 /* find best triangle given the current vertex cache */
2651                 first = -1;
2652                 best = -1;
2653                 bestScore = -1;
2654                 for( j = 0; j < ds->numIndexes; j += 3 )
2655                 {
2656                         /* valid triangle? */
2657                         if( indexes[ j ] != -1 )
2658                         {
2659                                 /* set first if necessary */
2660                                 if( first < 0 )
2661                                         first = j;
2662
2663                                 /* score the triangle */
2664                                 score = 0;
2665                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2666                                 {
2667                                         if( indexes[ j ] == vertexCache[ k ] || indexes[ j + 1 ] == vertexCache[ k ] || indexes[ j + 2 ] == vertexCache[ k ] )
2668                                                 score++;
2669                                 }
2670
2671                                 /* better triangle? */
2672                                 if( score > bestScore )
2673                                 {
2674                                         bestScore = score;
2675                                         best = j;
2676                                 }
2677
2678                                 /* a perfect score of 3 means this triangle's verts are already present in the vertex cache */
2679                                 if( score == 3 )
2680                                         break;
2681                         }
2682                 }
2683
2684                 /* check if no decent triangle was found, and use first available */
2685                 if( best < 0 )
2686                         best = first;
2687
2688                 /* valid triangle? */
2689                 if( best >= 0 )
2690                 {
2691                         /* add triangle to vertex cache */
2692                         for( j = 0; j < 3; j++ )
2693                         {
2694                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2695                                 {
2696                                         if( indexes[ best + j ] == vertexCache[ k ] )
2697                                                 break;
2698                                 }
2699
2700                                 if( k >= VERTEX_CACHE_SIZE )
2701                                 {
2702                                         /* pop off top of vertex cache */
2703                                         for( k = VERTEX_CACHE_SIZE; k > 0; k-- )
2704                                                 vertexCache[ k ] = vertexCache[ k - 1 ];
2705
2706                                         /* add vertex */
2707                                         vertexCache[ 0 ] = indexes[ best + j ];
2708                                 }
2709                         }
2710
2711                         /* add triangle to surface */
2712                         ds->indexes[ i ] = indexes[ best ];
2713                         ds->indexes[ i + 1 ] = indexes[ best + 1 ];
2714                         ds->indexes[ i + 2 ] = indexes[ best + 2 ];
2715
2716                         /* clear from input pool */
2717                         indexes[ best ] = -1;
2718                         indexes[ best + 1 ] = -1;
2719                         indexes[ best + 2 ] = -1;
2720
2721                         /* sort triangle windings (312 -> 123) */
2722                         while( ds->indexes[ i ] > ds->indexes[ i + 1 ] || ds->indexes[ i ] > ds->indexes[ i + 2 ] )
2723                         {
2724                                 temp = ds->indexes[ i ];
2725                                 ds->indexes[ i ] = ds->indexes[ i + 1 ];
2726                                 ds->indexes[ i + 1 ] = ds->indexes[ i + 2 ];
2727                                 ds->indexes[ i + 2 ] = temp;
2728                         }
2729                 }
2730         }
2731
2732         /* clean up */
2733         free( indexes );
2734 }
2735
2736
2737
2738 /*
2739 EmitTriangleSurface()
2740 creates a bsp drawsurface from arbitrary triangle surfaces
2741 */
2742
2743 void EmitTriangleSurface( mapDrawSurface_t *ds )
2744 {
2745         int                                             i, temp;
2746         bspDrawSurface_t                *out;
2747
2748         /* invert the surface if necessary */
2749         if( ds->backSide || ds->shaderInfo->invert )
2750         {
2751                 /* walk the indexes, reverse the triangle order */
2752                 for( i = 0; i < ds->numIndexes; i += 3 )
2753                 {
2754                         temp = ds->indexes[ i ];
2755                         ds->indexes[ i ] = ds->indexes[ i + 1 ];
2756                         ds->indexes[ i + 1 ] = temp;
2757                 }
2758
2759                 /* walk the verts, flip the normal */
2760                 for( i = 0; i < ds->numVerts; i++ )
2761                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2762
2763                 /* invert facing */
2764                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2765         }
2766
2767         /* allocate a new surface */
2768         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2769                 Error( "MAX_MAP_DRAW_SURFS" );
2770         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2771         ds->outputNum = numBSPDrawSurfaces;
2772         numBSPDrawSurfaces++;
2773         memset( out, 0, sizeof( *out ) );
2774
2775         /* ydnar/sd: handle wolf et foliage surfaces */
2776         if( ds->type == SURFACE_FOLIAGE )
2777                 out->surfaceType = MST_FOLIAGE;
2778
2779         /* ydnar: gs mods: handle lightmapped terrain (force to planar type) */
2780         //%     else if( VectorLength( ds->lightmapAxis ) <= 0.0f || ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FOGHULL || debugSurfaces )
2781         else if( (VectorLength( ds->lightmapAxis ) <= 0.0f && ds->planar == qfalse) ||
2782                 ds->type == SURFACE_TRIANGLES ||
2783                 ds->type == SURFACE_FOGHULL ||
2784                 ds->numVerts > maxLMSurfaceVerts ||
2785                 debugSurfaces )
2786                 out->surfaceType = MST_TRIANGLE_SOUP;
2787
2788         /* set to a planar face */
2789         else
2790                 out->surfaceType = MST_PLANAR;
2791
2792         /* set it up */
2793         if( debugSurfaces )
2794                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2795         else
2796                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2797         out->patchWidth = ds->patchWidth;
2798         out->patchHeight = ds->patchHeight;
2799         out->fogNum = ds->fogNum;
2800
2801         /* debug inset (push each triangle vertex towards the center of each triangle it is on */
2802         if( debugInset )
2803         {
2804                 bspDrawVert_t   *a, *b, *c;
2805                 vec3_t                  cent, dir;
2806
2807
2808                 /* walk triangle list */
2809                 for( i = 0; i < ds->numIndexes; i += 3 )
2810                 {
2811                         /* get verts */
2812                         a = &ds->verts[ ds->indexes[ i ] ];
2813                         b = &ds->verts[ ds->indexes[ i + 1 ] ];
2814                         c = &ds->verts[ ds->indexes[ i + 2 ] ];
2815
2816                         /* calculate centroid */
2817                         VectorCopy( a->xyz, cent );
2818                         VectorAdd( cent, b->xyz, cent );
2819                         VectorAdd( cent, c->xyz, cent );
2820                         VectorScale( cent, 1.0f / 3.0f, cent );
2821
2822                         /* offset each vertex */
2823                         VectorSubtract( cent, a->xyz, dir );
2824                         VectorNormalize( dir, dir );
2825                         VectorAdd( a->xyz, dir, a->xyz );
2826                         VectorSubtract( cent, b->xyz, dir );
2827                         VectorNormalize( dir, dir );
2828                         VectorAdd( b->xyz, dir, b->xyz );
2829                         VectorSubtract( cent, c->xyz, dir );
2830                         VectorNormalize( dir, dir );
2831                         VectorAdd( c->xyz, dir, c->xyz );
2832                 }
2833         }
2834
2835         /* RBSP */
2836         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2837         {
2838                 out->lightmapNum[ i ] = -3;
2839                 out->lightmapStyles[ i ] = LS_NONE;
2840                 out->vertexStyles[ i ] = LS_NONE;
2841         }
2842         out->lightmapStyles[ 0 ] = LS_NORMAL;
2843         out->vertexStyles[ 0 ] = LS_NORMAL;
2844
2845         /* lightmap vectors (lod bounds for patches */
2846         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2847         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );
2848         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2849         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2850
2851         /* ydnar: gs mods: clear out the plane normal */
2852         if( ds->planar == qfalse )
2853                 VectorClear( out->lightmapVecs[ 2 ] );
2854
2855         /* optimize the surface's triangles */
2856         OptimizeTriangleSurface( ds );
2857
2858         /* emit the verts and indexes */
2859         EmitDrawVerts( ds, out );
2860         EmitDrawIndexes( ds, out );
2861
2862         /* add to count */
2863         numSurfacesByType[ ds->type ]++;
2864 }
2865
2866
2867
2868 /*
2869 EmitFaceSurface()
2870 emits a bsp planar winding (brush face) drawsurface
2871 */
2872
2873 static void EmitFaceSurface(mapDrawSurface_t *ds )
2874 {
2875         /* strip/fan finding was moved elsewhere */
2876         if(maxAreaFaceSurface)
2877                 MaxAreaFaceSurface( ds );
2878         else
2879                 StripFaceSurface( ds );
2880         EmitTriangleSurface(ds);
2881 }
2882
2883
2884 /*
2885 MakeDebugPortalSurfs_r() - ydnar
2886 generates drawsurfaces for passable portals in the bsp
2887 */
2888
2889 static void MakeDebugPortalSurfs_r( node_t *node, shaderInfo_t *si )
2890 {
2891         int                                     i, k, c, s;
2892         portal_t                        *p;
2893         winding_t                       *w;
2894         mapDrawSurface_t        *ds;
2895         bspDrawVert_t           *dv;
2896
2897
2898         /* recurse if decision node */
2899         if( node->planenum != PLANENUM_LEAF)
2900         {
2901                 MakeDebugPortalSurfs_r( node->children[ 0 ], si );
2902                 MakeDebugPortalSurfs_r( node->children[ 1 ], si );
2903                 return;
2904         }
2905
2906         /* don't bother with opaque leaves */
2907         if( node->opaque )
2908                 return;
2909
2910         /* walk the list of portals */
2911         for( c = 0, p = node->portals; p != NULL; c++, p = p->next[ s ] )
2912         {
2913                 /* get winding and side even/odd */
2914                 w = p->winding;
2915                 s = (p->nodes[ 1 ] == node);
2916
2917                 /* is this a valid portal for this leaf? */
2918                 if( w && p->nodes[ 0 ] == node )
2919                 {
2920                         /* is this portal passable? */
2921                         if( PortalPassable( p ) == qfalse )
2922                                 continue;
2923
2924                         /* check max points */
2925                         if( w->numpoints > 64 )
2926                                 Error( "MakePortalSurfs_r: w->numpoints = %d", w->numpoints );
2927
2928                         /* allocate a drawsurface */
2929                         ds = AllocDrawSurface( SURFACE_FACE );
2930                         ds->shaderInfo = si;
2931                         ds->planar = qtrue;
2932                         ds->sideRef = AllocSideRef( p->side, NULL );
2933                         ds->planeNum = FindFloatPlane( p->plane.normal, p->plane.dist, 0, NULL );
2934                         VectorCopy( p->plane.normal, ds->lightmapVecs[ 2 ] );
2935                         ds->fogNum = -1;
2936                         ds->numVerts = w->numpoints;
2937                         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2938                         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2939
2940                         /* walk the winding */
2941                         for( i = 0; i < ds->numVerts; i++ )
2942                         {
2943                                 /* get vert */
2944                                 dv = ds->verts + i;
2945
2946                                 /* set it */
2947                                 VectorCopy( w->p[ i ], dv->xyz );
2948                                 VectorCopy( p->plane.normal, dv->normal );
2949                                 dv->st[ 0 ] = 0;
2950                                 dv->st[ 1 ] = 0;
2951                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
2952                                 {
2953                                         VectorCopy( debugColors[ c % 12 ], dv->color[ k ] );
2954                                         dv->color[ k ][ 3 ] = 32;
2955                                 }
2956                         }
2957                 }
2958         }
2959 }
2960
2961
2962
2963 /*
2964 MakeDebugPortalSurfs() - ydnar
2965 generates drawsurfaces for passable portals in the bsp
2966 */
2967
2968 void MakeDebugPortalSurfs( tree_t *tree )
2969 {
2970         shaderInfo_t    *si;
2971
2972
2973         /* note it */
2974         Sys_FPrintf( SYS_VRB, "--- MakeDebugPortalSurfs ---\n" );
2975
2976         /* get portal debug shader */
2977         si = ShaderInfoForShader( "debugportals" );
2978
2979         /* walk the tree */
2980         MakeDebugPortalSurfs_r( tree->headnode, si );
2981 }
2982
2983
2984
2985 /*
2986 MakeFogHullSurfs()
2987 generates drawsurfaces for a foghull (this MUST use a sky shader)
2988 */
2989
2990 void MakeFogHullSurfs( entity_t *e, tree_t *tree, char *shader )
2991 {
2992         shaderInfo_t            *si;
2993         mapDrawSurface_t        *ds;
2994         vec3_t                          fogMins, fogMaxs;
2995         int                                     i, indexes[] =
2996                                                 {
2997                                                         0, 1, 2, 0, 2, 3,
2998                                                         4, 7, 5, 5, 7, 6,
2999                                                         1, 5, 6, 1, 6, 2,
3000                                                         0, 4, 5, 0, 5, 1,
3001                                                         2, 6, 7, 2, 7, 3,
3002                                                         3, 7, 4, 3, 4, 0
3003                                                 };
3004
3005
3006         /* dummy check */
3007         if( shader == NULL || shader[ 0 ] == '\0' )
3008                 return;
3009
3010         /* note it */
3011         Sys_FPrintf( SYS_VRB, "--- MakeFogHullSurfs ---\n" );
3012
3013         /* get hull bounds */
3014         VectorCopy( mapMins, fogMins );
3015         VectorCopy( mapMaxs, fogMaxs );
3016         for( i = 0; i < 3; i++ )
3017         {
3018                 fogMins[ i ] -= 128;
3019                 fogMaxs[ i ] += 128;
3020         }
3021
3022         /* get foghull shader */
3023         si = ShaderInfoForShader( shader );
3024
3025         /* allocate a drawsurface */
3026         ds = AllocDrawSurface( SURFACE_FOGHULL );
3027         ds->shaderInfo = si;
3028         ds->fogNum = -1;
3029         ds->numVerts = 8;
3030         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
3031         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
3032         ds->numIndexes = 36;
3033         ds->indexes = safe_malloc( ds->numIndexes * sizeof( *ds->indexes ) );
3034         memset( ds->indexes, 0, ds->numIndexes * sizeof( *ds->indexes ) );
3035
3036         /* set verts */
3037         VectorSet( ds->verts[ 0 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
3038         VectorSet( ds->verts[ 1 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
3039         VectorSet( ds->verts[ 2 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
3040         VectorSet( ds->verts[ 3 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
3041
3042         VectorSet( ds->verts[ 4 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
3043         VectorSet( ds->verts[ 5 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
3044         VectorSet( ds->verts[ 6 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
3045         VectorSet( ds->verts[ 7 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
3046
3047         /* set indexes */
3048         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( *ds->indexes ) );
3049 }
3050
3051
3052
3053 /*
3054 BiasSurfaceTextures()
3055 biases a surface's texcoords as close to 0 as possible
3056 */
3057
3058 void BiasSurfaceTextures( mapDrawSurface_t *ds )
3059 {
3060         int             i;
3061
3062
3063         /* calculate the surface texture bias */
3064         CalcSurfaceTextureRange( ds );
3065
3066         /* don't bias globaltextured shaders */
3067         if( ds->shaderInfo->globalTexture )
3068                 return;
3069
3070         /* bias the texture coordinates */
3071         for( i = 0; i < ds->numVerts; i++ )
3072         {
3073                 ds->verts[ i ].st[ 0 ] += ds->bias[ 0 ];
3074                 ds->verts[ i ].st[ 1 ] += ds->bias[ 1 ];
3075         }
3076 }
3077
3078
3079
3080 /*
3081 AddSurfaceModelsToTriangle_r()
3082 adds models to a specified triangle, returns the number of models added
3083 */
3084
3085 int AddSurfaceModelsToTriangle_r( mapDrawSurface_t *ds, surfaceModel_t *model, bspDrawVert_t **tri )
3086 {
3087         bspDrawVert_t   mid, *tri2[ 3 ];
3088         int                             max, n, localNumSurfaceModels;
3089
3090
3091         /* init */
3092         localNumSurfaceModels = 0;
3093
3094         /* subdivide calc */
3095         {
3096                 int                     i;
3097                 float           *a, *b, dx, dy, dz, dist, maxDist;
3098
3099
3100                 /* find the longest edge and split it */
3101                 max = -1;
3102                 maxDist = 0.0f;
3103                 for( i = 0; i < 3; i++ )
3104                 {
3105                         /* get verts */
3106                         a = tri[ i ]->xyz;
3107                         b = tri[ (i + 1) % 3 ]->xyz;
3108
3109                         /* get dists */
3110                         dx = a[ 0 ] - b[ 0 ];
3111                         dy = a[ 1 ] - b[ 1 ];
3112                         dz = a[ 2 ] - b[ 2 ];
3113                         dist = (dx * dx) + (dy * dy) + (dz * dz);
3114
3115                         /* longer? */
3116                         if( dist > maxDist )
3117                         {
3118                                 maxDist = dist;
3119                                 max = i;
3120                         }
3121                 }
3122
3123                 /* is the triangle small enough? */
3124                 if( max < 0 || maxDist <= (model->density * model->density) )
3125                 {
3126                         float   odds, r, angle;
3127                         vec3_t  origin, normal, scale, axis[ 3 ], angles;
3128                         m4x4_t  transform, temp;
3129
3130
3131                         /* roll the dice (model's odds scaled by vertex alpha) */
3132                         odds = model->odds * (tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ]) / 765.0f;
3133                         r = Random();
3134                         if( r > odds )
3135                                 return 0;
3136
3137                         /* calculate scale */
3138                         r = model->minScale + Random() * (model->maxScale - model->minScale);
3139                         VectorSet( scale, r, r, r );
3140
3141                         /* calculate angle */
3142                         angle = model->minAngle + Random() * (model->maxAngle - model->minAngle);
3143
3144                         /* calculate average origin */
3145                         VectorCopy( tri[ 0 ]->xyz, origin );
3146                         VectorAdd( origin, tri[ 1 ]->xyz, origin );
3147                         VectorAdd( origin, tri[ 2 ]->xyz, origin );
3148                         VectorScale( origin, (1.0f / 3.0f), origin );
3149
3150                         /* clear transform matrix */
3151                         m4x4_identity( transform );
3152
3153                         /* handle oriented models */
3154                         if( model->oriented )
3155                         {
3156                                 /* set angles */
3157                                 VectorSet( angles, 0.0f, 0.0f, angle );
3158
3159                                 /* calculate average normal */
3160                                 VectorCopy( tri[ 0 ]->normal, normal );
3161                                 VectorAdd( normal, tri[ 1 ]->normal, normal );
3162                                 VectorAdd( normal, tri[ 2 ]->normal, normal );
3163                                 if( VectorNormalize( normal, axis[ 2 ] ) == 0.0f )
3164                                         VectorCopy( tri[ 0 ]->normal, axis[ 2 ] );
3165
3166                                 /* make perpendicular vectors */
3167                                 MakeNormalVectors( axis[ 2 ], axis[ 1 ], axis[ 0 ] );
3168
3169                                 /* copy to matrix */
3170                                 m4x4_identity( temp );
3171                                 temp[ 0 ] = axis[ 0 ][ 0 ];     temp[ 1 ] = axis[ 0 ][ 1 ];     temp[ 2 ] = axis[ 0 ][ 2 ];
3172                                 temp[ 4 ] = axis[ 1 ][ 0 ];     temp[ 5 ] = axis[ 1 ][ 1 ];     temp[ 6 ] = axis[ 1 ][ 2 ];
3173                                 temp[ 8 ] = axis[ 2 ][ 0 ];     temp[ 9 ] = axis[ 2 ][ 1 ];     temp[ 10 ] = axis[ 2 ][ 2 ];
3174
3175                                 /* scale */
3176                                 m4x4_scale_by_vec3( temp, scale );
3177
3178                                 /* rotate around z axis */
3179                                 m4x4_rotate_by_vec3( temp, angles, eXYZ );
3180
3181                                 /* translate */
3182                                 m4x4_translate_by_vec3( transform, origin );
3183
3184                                 /* tranform into axis space */
3185                                 m4x4_multiply_by_m4x4( transform, temp );
3186                         }
3187
3188                         /* handle z-up models */
3189                         else
3190                         {
3191                                 /* set angles */
3192                                 VectorSet( angles, 0.0f, 0.0f, angle );
3193
3194                                 /* set matrix */
3195                                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
3196                         }
3197
3198                         /* insert the model */
3199                         InsertModel( (char *) model->model, 0, 0, transform, NULL, ds->celShader, ds->entityNum, ds->castShadows, ds->recvShadows, 0, ds->lightmapScale, 0, 0 );
3200
3201                         /* return to sender */
3202                         return 1;
3203                 }
3204         }
3205
3206         /* split the longest edge and map it */
3207         LerpDrawVert( tri[ max ], tri[ (max + 1) % 3 ], &mid );
3208
3209         /* recurse to first triangle */
3210         VectorCopy( tri, tri2 );
3211         tri2[ max ] = &mid;
3212         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3213         if( n < 0 )
3214                 return n;
3215         localNumSurfaceModels += n;
3216
3217         /* recurse to second triangle */
3218         VectorCopy( tri, tri2 );
3219         tri2[ (max + 1) % 3 ] = &mid;
3220         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3221         if( n < 0 )
3222                 return n;
3223         localNumSurfaceModels += n;
3224
3225         /* return count */
3226         return localNumSurfaceModels;
3227 }
3228
3229
3230
3231 /*
3232 AddSurfaceModels()
3233 adds a surface's shader models to the surface
3234 */
3235
3236 int AddSurfaceModels( mapDrawSurface_t *ds )
3237 {
3238         surfaceModel_t  *model;
3239         int                             i, x, y, n, pw[ 5 ], r, localNumSurfaceModels, iterations;
3240         mesh_t                  src, *mesh, *subdivided;
3241         bspDrawVert_t   centroid, *tri[ 3 ];
3242         float                   alpha;
3243
3244
3245         /* dummy check */
3246         if( ds == NULL || ds->shaderInfo == NULL || ds->shaderInfo->surfaceModel == NULL )
3247                 return 0;
3248
3249         /* init */
3250         localNumSurfaceModels = 0;
3251
3252         /* walk the model list */
3253         for( model = ds->shaderInfo->surfaceModel; model != NULL; model = model->next )
3254         {
3255                 /* switch on type */
3256                 switch( ds->type )
3257                 {
3258                         /* handle brush faces and decals */
3259                         case SURFACE_FACE:
3260                         case SURFACE_DECAL:
3261                                 /* calculate centroid */
3262                                 memset( &centroid, 0, sizeof( centroid ) );
3263                                 alpha = 0.0f;
3264
3265                                 /* walk verts */
3266                                 for( i = 0; i < ds->numVerts; i++ )
3267                                 {
3268                                         VectorAdd( centroid.xyz, ds->verts[ i ].xyz, centroid.xyz );
3269                                         VectorAdd( centroid.normal, ds->verts[ i ].normal, centroid.normal );
3270                                         centroid.st[ 0 ] += ds->verts[ i ].st[ 0 ];
3271                                         centroid.st[ 1 ] += ds->verts[ i ].st[ 1 ];
3272                                         alpha += ds->verts[ i ].color[ 0 ][ 3 ];
3273                                 }
3274
3275                                 /* average */
3276                                 centroid.xyz[ 0 ] /= ds->numVerts;
3277                                 centroid.xyz[ 1 ] /= ds->numVerts;
3278                                 centroid.xyz[ 2 ] /= ds->numVerts;
3279                                 if( VectorNormalize( centroid.normal, centroid.normal ) == 0.0f )
3280                                         VectorCopy( ds->verts[ 0 ].normal, centroid.normal );
3281                                 centroid.st[ 0 ]  /= ds->numVerts;
3282                                 centroid.st[ 1 ]  /= ds->numVerts;
3283                                 alpha /= ds->numVerts;
3284                                 centroid.color[ 0 ][ 0 ] = 0xFF;
3285                                 centroid.color[ 0 ][ 1 ] = 0xFF;
3286                                 centroid.color[ 0 ][ 2 ] = 0xFF;
3287                                 centroid.color[ 0 ][ 2 ] = (alpha > 255.0f ? 0xFF : alpha);
3288
3289                                 /* head vert is centroid */
3290                                 tri[ 0 ] = &centroid;
3291
3292                                 /* walk fanned triangles */
3293                                 for( i = 0; i < ds->numVerts; i++ )
3294                                 {
3295                                         /* set triangle */
3296                                         tri[ 1 ] = &ds->verts[ i ];
3297                                         tri[ 2 ] = &ds->verts[ (i + 1) % ds->numVerts ];
3298
3299                                         /* create models */
3300                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3301                                         if( n < 0 )
3302                                                 return n;
3303                                         localNumSurfaceModels += n;
3304                                 }
3305                                 break;
3306
3307                         /* handle patches */
3308                         case SURFACE_PATCH:
3309                                 /* subdivide the surface */
3310                                 src.width = ds->patchWidth;
3311                                 src.height = ds->patchHeight;
3312                                 src.verts = ds->verts;
3313                                 //%     subdivided = SubdivideMesh( src, 8.0f, 512 );
3314                                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
3315                                 subdivided = SubdivideMesh2( src, iterations );
3316
3317                                 /* fit it to the curve and remove colinear verts on rows/columns */
3318                                 PutMeshOnCurve( *subdivided );
3319                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
3320                                 FreeMesh( subdivided );
3321
3322                                 /* subdivide each quad to place the models */
3323                                 for( y = 0; y < (mesh->height - 1); y++ )
3324                                 {
3325                                         for( x = 0; x < (mesh->width - 1); x++ )
3326                                         {
3327                                                 /* set indexes */
3328                                                 pw[ 0 ] = x + (y * mesh->width);
3329                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
3330                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
3331                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
3332                                                 pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
3333
3334                                                 /* set radix */
3335                                                 r = (x + y) & 1;
3336
3337                                                 /* triangle 1 */
3338                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3339                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 1 ] ];
3340                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 2 ] ];
3341                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3342                                                 if( n < 0 )
3343                                                         return n;
3344                                                 localNumSurfaceModels += n;
3345
3346                                                 /* triangle 2 */
3347                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3348                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 2 ] ];
3349                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 3 ] ];
3350                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3351                                                 if( n < 0 )
3352                                                         return n;
3353                                                 localNumSurfaceModels += n;
3354                                         }
3355                                 }
3356
3357                                 /* free the subdivided mesh */
3358                                 FreeMesh( mesh );
3359                                 break;
3360
3361                         /* handle triangle surfaces */
3362                         case SURFACE_TRIANGLES:
3363                         case SURFACE_FORCED_META:
3364                         case SURFACE_META:
3365                                 /* walk the triangle list */
3366                                 for( i = 0; i < ds->numIndexes; i += 3 )
3367                                 {
3368                                         tri[ 0 ] = &ds->verts[ ds->indexes[ i ] ];
3369                                         tri[ 1 ] = &ds->verts[ ds->indexes[ i + 1 ] ];
3370                                         tri[ 2 ] = &ds->verts[ ds->indexes[ i + 2 ] ];
3371                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3372                                         if( n < 0 )
3373                                                 return n;
3374                                         localNumSurfaceModels += n;
3375                                 }
3376                                 break;
3377
3378                         /* no support for flares, foghull, etc */
3379                         default:
3380                                 break;
3381                 }
3382         }
3383
3384         /* return count */
3385         return localNumSurfaceModels;
3386 }
3387
3388
3389
3390 /*
3391 AddEntitySurfaceModels() - ydnar
3392 adds surfacemodels to an entity's surfaces
3393 */
3394
3395 void AddEntitySurfaceModels( entity_t *e )
3396 {
3397         int             i;
3398
3399
3400         /* note it */
3401         Sys_FPrintf( SYS_VRB, "--- AddEntitySurfaceModels ---\n" );
3402
3403         /* walk the surface list */
3404         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3405                 numSurfaceModels += AddSurfaceModels( &mapDrawSurfs[ i ] );
3406 }
3407
3408
3409
3410 /*
3411 VolumeColorMods() - ydnar
3412 applies brush/volumetric color/alpha modulation to vertexes
3413 */
3414
3415 static void VolumeColorMods( entity_t *e, mapDrawSurface_t *ds )
3416 {
3417         int                     i, j;
3418         float           d;
3419         brush_t         *b;
3420         plane_t         *plane;
3421
3422
3423         /* early out */
3424         if( e->colorModBrushes == NULL )
3425                 return;
3426
3427         /* iterate brushes */
3428         for( b = e->colorModBrushes; b != NULL; b = b->nextColorModBrush )
3429         {
3430                 /* worldspawn alpha brushes affect all, grouped ones only affect original entity */
3431                 if( b->entityNum != 0 && b->entityNum != ds->entityNum )
3432                         continue;
3433
3434                 /* test bbox */
3435                 if( b->mins[ 0 ] > ds->maxs[ 0 ] || b->maxs[ 0 ] < ds->mins[ 0 ] ||
3436                         b->mins[ 1 ] > ds->maxs[ 1 ] || b->maxs[ 1 ] < ds->mins[ 1 ] ||
3437                         b->mins[ 2 ] > ds->maxs[ 2 ] || b->maxs[ 2 ] < ds->mins[ 2 ] )
3438                         continue;
3439
3440                 /* iterate verts */
3441                 for( i = 0; i < ds->numVerts; i++ )
3442                 {
3443                         /* iterate planes */
3444                         for( j = 0; j < b->numsides; j++ )
3445                         {
3446                                 /* point-plane test */
3447                                 plane = &mapplanes[ b->sides[ j ].planenum ];
3448                                 d = DotProduct( ds->verts[ i ].xyz, plane->normal ) - plane->dist;
3449                                 if( d > 1.0f )
3450                                         break;
3451                         }
3452
3453                         /* apply colormods */
3454                         if( j == b->numsides )
3455                                 ColorMod( b->contentShader->colorMod, 1, &ds->verts[ i ] );
3456                 }
3457         }
3458 }
3459
3460
3461
3462 /*
3463 FilterDrawsurfsIntoTree()
3464 upon completion, all drawsurfs that actually generate a reference
3465 will have been emited to the bspfile arrays, and the references
3466 will have valid final indexes
3467 */
3468
3469 void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree )
3470 {
3471         int                                     i, j;
3472         mapDrawSurface_t        *ds;
3473         shaderInfo_t            *si;
3474         vec3_t                          origin, mins, maxs;
3475         int                                     refs;
3476         int                                     numSurfs, numRefs, numSkyboxSurfaces;
3477         qboolean        sb;
3478
3479
3480         /* note it */
3481         Sys_FPrintf( SYS_VRB, "--- FilterDrawsurfsIntoTree ---\n" );
3482
3483         /* filter surfaces into the tree */
3484         numSurfs = 0;
3485         numRefs = 0;
3486         numSkyboxSurfaces = 0;
3487         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3488         {
3489                 /* get surface and try to early out */
3490                 ds = &mapDrawSurfs[ i ];
3491                 if( ds->numVerts == 0 && ds->type != SURFACE_FLARE && ds->type != SURFACE_SHADER )
3492                         continue;
3493
3494                 /* get shader */
3495                 si = ds->shaderInfo;
3496
3497                 /* ydnar: skybox surfaces are special */
3498                 if( ds->skybox )
3499                 {
3500                         refs = AddReferenceToTree_r( ds, tree->headnode, qtrue );
3501                         ds->skybox = qfalse;
3502                         sb = qtrue;
3503                 }
3504                 else
3505                 {
3506                         sb = qfalse;
3507
3508                         /* refs initially zero */
3509                         refs = 0;
3510
3511                         /* apply texture coordinate mods */
3512                         for( j = 0; j < ds->numVerts; j++ )
3513                                 TCMod( si->mod, ds->verts[ j ].st );
3514
3515                         /* ydnar: apply shader colormod */
3516                         ColorMod( ds->shaderInfo->colorMod, ds->numVerts, ds->verts );
3517
3518                         /* ydnar: apply brush colormod */
3519                         VolumeColorMods( e, ds );
3520
3521                         /* ydnar: make fur surfaces */
3522                         if( si->furNumLayers > 0 )
3523                                 Fur( ds );
3524
3525                         /* ydnar/sd: make foliage surfaces */
3526                         if( si->foliage != NULL )
3527                                 Foliage( ds );
3528
3529                         /* create a flare surface if necessary */
3530                         if( si->flareShader != NULL && si->flareShader[ 0 ] )
3531                                 AddSurfaceFlare( ds, e->origin );
3532
3533                         /* ydnar: don't emit nodraw surfaces (like nodraw fog) */
3534                         if( si != NULL && (si->compileFlags & C_NODRAW) && ds->type != SURFACE_PATCH )
3535                                 continue;
3536
3537                         /* ydnar: bias the surface textures */
3538                         BiasSurfaceTextures( ds );
3539
3540                         /* ydnar: globalizing of fog volume handling (eek a hack) */
3541                         if( e != entities && si->noFog == qfalse )
3542                         {
3543                                 /* find surface origin and offset by entity origin */
3544                                 VectorAdd( ds->mins, ds->maxs, origin );
3545                                 VectorScale( origin, 0.5f, origin );
3546                                 VectorAdd( origin, e->origin, origin );
3547
3548                                 VectorAdd( ds->mins, e->origin, mins );
3549                                 VectorAdd( ds->maxs, e->origin, maxs );
3550
3551                                 /* set the fog number for this surface */
3552                                 ds->fogNum = FogForBounds( mins, maxs, 1.0f );  //%     FogForPoint( origin, 0.0f );
3553                         }
3554                 }
3555
3556                 /* ydnar: remap shader */
3557                 if( ds->shaderInfo->remapShader && ds->shaderInfo->remapShader[ 0 ] )
3558                         ds->shaderInfo = ShaderInfoForShader( ds->shaderInfo->remapShader );
3559
3560                 /* ydnar: gs mods: handle the various types of surfaces */
3561                 switch( ds->type )
3562                 {
3563                         /* handle brush faces */
3564                         case SURFACE_FACE:
3565                         case SURFACE_DECAL:
3566                                 if( refs == 0 )
3567                                         refs = FilterFaceIntoTree( ds, tree );
3568                                 if( refs > 0 )
3569                                         EmitFaceSurface( ds );
3570                                 break;
3571
3572                         /* handle patches */
3573                         case SURFACE_PATCH:
3574                                 if( refs == 0 )
3575                                         refs = FilterPatchIntoTree( ds, tree );
3576                                 if( refs > 0 )
3577                                         EmitPatchSurface( e, ds );
3578                                 break;
3579
3580                         /* handle triangle surfaces */
3581                         case SURFACE_TRIANGLES:
3582                         case SURFACE_FORCED_META:
3583                         case SURFACE_META:
3584                                 //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%1d] %4d verts %s\n", numSurfs, ds->planar, ds->numVerts, si->shader );
3585                                 if( refs == 0 )
3586                                         refs = FilterTrianglesIntoTree( ds, tree );
3587                                 if( refs > 0 )
3588                                         EmitTriangleSurface( ds );
3589                                 break;
3590
3591                         /* handle foliage surfaces (splash damage/wolf et) */
3592                         case SURFACE_FOLIAGE:
3593                                 //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%d] %4d verts %s\n", numSurfs, ds->numFoliageInstances, ds->numVerts, si->shader );
3594                                 if( refs == 0 )
3595                                         refs = FilterFoliageIntoTree( ds, tree );
3596                                 if( refs > 0 )
3597                                         EmitTriangleSurface( ds );
3598                                 break;
3599
3600                         /* handle foghull surfaces */
3601                         case SURFACE_FOGHULL:
3602                                 if( refs == 0 )
3603                                         refs = AddReferenceToTree_r( ds, tree->headnode, qfalse );
3604                                 if( refs > 0 )
3605                                         EmitTriangleSurface( ds );
3606                                 break;
3607
3608                         /* handle flares */
3609                         case SURFACE_FLARE:
3610                                 if( refs == 0 )
3611                                         refs = FilterFlareSurfIntoTree( ds, tree );
3612                                 if( refs > 0 )
3613                                         EmitFlareSurface( ds );
3614                                 break;
3615
3616                         /* handle shader-only surfaces */
3617                         case SURFACE_SHADER:
3618                                 refs = 1;
3619                                 EmitFlareSurface( ds );
3620                                 break;
3621
3622                         /* no references */
3623                         default:
3624                                 refs = 0;
3625                                 break;
3626                 }
3627
3628                 /* maybe surface got marked as skybox again */
3629                 /* if we keep that flag, it will get scaled up AGAIN */
3630                 if(sb)
3631                         ds->skybox = qfalse;
3632
3633                 /* tot up the references */
3634                 if( refs > 0 )
3635                 {
3636                         /* tot up counts */
3637                         numSurfs++;
3638                         numRefs += refs;
3639
3640                         /* emit extra surface data */
3641                         SetSurfaceExtra( ds, numBSPDrawSurfaces - 1 );
3642                         //%     Sys_FPrintf( SYS_VRB, "%d verts %d indexes\n", ds->numVerts, ds->numIndexes );
3643
3644                         /* one last sanity check */
3645                         {
3646                                 bspDrawSurface_t        *out;
3647                                 out = &bspDrawSurfaces[ numBSPDrawSurfaces - 1 ];
3648                                 if( out->numVerts == 3 && out->numIndexes > 3 )
3649                                 {
3650                                         Sys_Printf( "\nWARNING: Potentially bad %s surface (%d: %d, %d)\n     %s\n",
3651                                                 surfaceTypes[ ds->type ],
3652                                                 numBSPDrawSurfaces - 1, out->numVerts, out->numIndexes, si->shader );
3653                                 }
3654                         }
3655
3656                         /* ydnar: handle skybox surfaces */
3657                         if( ds->skybox )
3658                         {
3659                                 MakeSkyboxSurface( ds );
3660                                 numSkyboxSurfaces++;
3661                         }
3662                 }
3663         }
3664
3665         /* emit some statistics */
3666         Sys_FPrintf( SYS_VRB, "%9d references\n", numRefs );
3667         Sys_FPrintf( SYS_VRB, "%9d (%d) emitted drawsurfs\n", numSurfs, numBSPDrawSurfaces );
3668         Sys_FPrintf( SYS_VRB, "%9d stripped face surfaces\n", numStripSurfaces );
3669         Sys_FPrintf( SYS_VRB, "%9d fanned face surfaces\n", numFanSurfaces );
3670         Sys_FPrintf( SYS_VRB, "%9d maxarea'd face surfaces\n", numMaxAreaSurfaces );
3671         Sys_FPrintf( SYS_VRB, "%9d surface models generated\n", numSurfaceModels );
3672         Sys_FPrintf( SYS_VRB, "%9d skybox surfaces generated\n", numSkyboxSurfaces );
3673         for( i = 0; i < NUM_SURFACE_TYPES; i++ )
3674                 Sys_FPrintf( SYS_VRB, "%9d %s surfaces\n", numSurfacesByType[ i ], surfaceTypes[ i ] );
3675
3676         Sys_FPrintf( SYS_VRB, "%9d redundant indexes supressed, saving %d Kbytes\n", numRedundantIndexes, (numRedundantIndexes * 4 / 1024) );
3677 }
3678
3679
3680