tools/quake3/q3map2/surface.c

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