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                 IncDrawVerts();
2254                 dv = &bspDrawVerts[ numBSPDrawVerts - 1 ];
2255
2256                 /* copy it */
2257                 memcpy( dv, &ds->verts[ i ], sizeof( *dv ) );
2258
2259                 /* offset? */
2260                 if( offset != 0.0f )
2261                         VectorMA( dv->xyz, offset, dv->normal, dv->xyz );
2262
2263                 /* expand model bounds
2264                    necessary because of misc_model surfaces on entities
2265                    note: does not happen on worldspawn as its bounds is only used for determining lightgrid bounds */
2266                 if( numBSPModels > 0 )
2267                         AddPointToBounds( dv->xyz, bspModels[ numBSPModels ].mins, bspModels[ numBSPModels ].maxs );
2268
2269                 /* debug color? */
2270                 if( debugSurfaces )
2271                 {
2272                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
2273                                 VectorCopy( debugColors[ (ds - mapDrawSurfs) % 12 ], dv->color[ k ] );
2274                 }
2275         }
2276 }
2277
2278
2279
2280 /*
2281 FindDrawIndexes() - ydnar
2282 this attempts to find a run of indexes in the bsp that match the given indexes
2283 this tends to reduce the size of the bsp index pool by 1/3 or more
2284 returns numIndexes + 1 if the search failed
2285 */
2286
2287 int FindDrawIndexes( int numIndexes, int *indexes )
2288 {
2289         int             i, j, numTestIndexes;
2290
2291
2292         /* dummy check */
2293         if( numIndexes < 3 || numBSPDrawIndexes < numIndexes || indexes == NULL )
2294                 return numBSPDrawIndexes;
2295
2296         /* set limit */
2297         numTestIndexes = 1 + numBSPDrawIndexes - numIndexes;
2298
2299         /* handle 3 indexes as a special case for performance */
2300         if( numIndexes == 3 )
2301         {
2302                 /* run through all indexes */
2303                 for( i = 0; i < numTestIndexes; i++ )
2304                 {
2305                         /* test 3 indexes */
2306                         if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2307                                 indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2308                                 indexes[ 2 ] == bspDrawIndexes[ i + 2 ] )
2309                         {
2310                                 numRedundantIndexes += numIndexes;
2311                                 return i;
2312                         }
2313                 }
2314
2315                 /* failed */
2316                 return numBSPDrawIndexes;
2317         }
2318
2319         /* handle 4 or more indexes */
2320         for( i = 0; i < numTestIndexes; i++ )
2321         {
2322                 /* test first 4 indexes */
2323                 if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2324                         indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2325                         indexes[ 2 ] == bspDrawIndexes[ i + 2 ] &&
2326                         indexes[ 3 ] == bspDrawIndexes[ i + 3 ] )
2327                 {
2328                         /* handle 4 indexes */
2329                         if( numIndexes == 4 )
2330                                 return i;
2331
2332                         /* test the remainder */
2333                         for( j = 4; j < numIndexes; j++ )
2334                         {
2335                                 if( indexes[ j ] != bspDrawIndexes[ i + j ] )
2336                                         break;
2337                                 else if( j == (numIndexes - 1) )
2338                                 {
2339                                         numRedundantIndexes += numIndexes;
2340                                         return i;
2341                                 }
2342                         }
2343                 }
2344         }
2345
2346         /* failed */
2347         return numBSPDrawIndexes;
2348 }
2349
2350
2351
2352 /*
2353 EmitDrawIndexes() - ydnar
2354 attempts to find an existing run of drawindexes before adding new ones
2355 */
2356
2357 void EmitDrawIndexes( mapDrawSurface_t *ds, bspDrawSurface_t *out )
2358 {
2359         int                     i;
2360
2361
2362         /* attempt to use redundant indexing */
2363         out->firstIndex = FindDrawIndexes( ds->numIndexes, ds->indexes );
2364         out->numIndexes = ds->numIndexes;
2365         if( out->firstIndex == numBSPDrawIndexes )
2366         {
2367                 /* copy new unique indexes */
2368                 for( i = 0; i < ds->numIndexes; i++ )
2369                 {
2370                         if( numBSPDrawIndexes == MAX_MAP_DRAW_INDEXES )
2371                                 Error( "MAX_MAP_DRAW_INDEXES" );
2372                         bspDrawIndexes[ numBSPDrawIndexes ] = ds->indexes[ i ];
2373
2374                         /* validate the index */
2375                         if( ds->type != SURFACE_PATCH )
2376                         {
2377                                 if( bspDrawIndexes[ numBSPDrawIndexes ] < 0 || bspDrawIndexes[ numBSPDrawIndexes ] >= ds->numVerts )
2378                                 {
2379                                         Sys_Printf( "WARNING: %d %s has invalid index %d (%d)\n",
2380                                                 numBSPDrawSurfaces,
2381                                                 ds->shaderInfo->shader,
2382                                                 bspDrawIndexes[ numBSPDrawIndexes ],
2383                                                 i );
2384                                         bspDrawIndexes[ numBSPDrawIndexes ] = 0;
2385                                 }
2386                         }
2387
2388                         /* increment index count */
2389                         numBSPDrawIndexes++;
2390                 }
2391         }
2392 }
2393
2394
2395
2396
2397 /*
2398 EmitFlareSurface()
2399 emits a bsp flare drawsurface
2400 */
2401
2402 void EmitFlareSurface( mapDrawSurface_t *ds )
2403 {
2404         int                                             i;
2405         bspDrawSurface_t                *out;
2406
2407
2408         /* ydnar: nuking useless flare drawsurfaces */
2409         if( emitFlares == qfalse && ds->type != SURFACE_SHADER )
2410                 return;
2411
2412         /* limit check */
2413         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2414                 Error( "MAX_MAP_DRAW_SURFS" );
2415
2416         /* allocate a new surface */
2417         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2418                 Error( "MAX_MAP_DRAW_SURFS" );
2419         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2420         ds->outputNum = numBSPDrawSurfaces;
2421         numBSPDrawSurfaces++;
2422         memset( out, 0, sizeof( *out ) );
2423
2424         /* set it up */
2425         out->surfaceType = MST_FLARE;
2426         out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2427         out->fogNum = ds->fogNum;
2428
2429         /* RBSP */
2430         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2431         {
2432                 out->lightmapNum[ i ] = -3;
2433                 out->lightmapStyles[ i ] = LS_NONE;
2434                 out->vertexStyles[ i ] = LS_NONE;
2435         }
2436         out->lightmapStyles[ 0 ] = ds->lightStyle;
2437         out->vertexStyles[ 0 ] = ds->lightStyle;
2438
2439         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );                  /* origin */
2440         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );    /* color */
2441         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2442         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );    /* normal */
2443
2444         /* add to count */
2445         numSurfacesByType[ ds->type ]++;
2446 }
2447
2448
2449
2450 /*
2451 EmitPatchSurface()
2452 emits a bsp patch drawsurface
2453 */
2454
2455 void EmitPatchSurface( mapDrawSurface_t *ds )
2456 {
2457         int                                     i, j;
2458         bspDrawSurface_t        *out;
2459         int                                     surfaceFlags, contentFlags;
2460
2461
2462         /* invert the surface if necessary */
2463         if( ds->backSide || ds->shaderInfo->invert )
2464         {
2465                 bspDrawVert_t   *dv1, *dv2, temp;
2466
2467
2468                 /* walk the verts, flip the normal */
2469                 for( i = 0; i < ds->numVerts; i++ )
2470                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2471
2472                 /* walk the verts again, but this time reverse their order */
2473                 for( j = 0; j < ds->patchHeight; j++ )
2474                 {
2475                         for( i = 0; i < (ds->patchWidth / 2); i++ )
2476                         {
2477                                 dv1 = &ds->verts[ j * ds->patchWidth + i ];
2478                                 dv2 = &ds->verts[ j * ds->patchWidth + (ds->patchWidth - i - 1) ];
2479                                 memcpy( &temp, dv1, sizeof( bspDrawVert_t ) );
2480                                 memcpy( dv1, dv2, sizeof( bspDrawVert_t ) );
2481                                 memcpy( dv2, &temp, sizeof( bspDrawVert_t ) );
2482                         }
2483                 }
2484
2485                 /* invert facing */
2486                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2487         }
2488
2489         /* allocate a new surface */
2490         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2491                 Error( "MAX_MAP_DRAW_SURFS" );
2492         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2493         ds->outputNum = numBSPDrawSurfaces;
2494         numBSPDrawSurfaces++;
2495         memset( out, 0, sizeof( *out ) );
2496
2497         /* set it up */
2498         out->surfaceType = MST_PATCH;
2499         if( debugSurfaces )
2500                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2501         else if( patchMeta )
2502         {
2503                 /* patch meta requires that we have nodraw patches for collision */
2504                 surfaceFlags = ds->shaderInfo->surfaceFlags;
2505                 contentFlags = ds->shaderInfo->contentFlags;
2506                 ApplySurfaceParm( "nodraw", &contentFlags, &surfaceFlags, NULL );
2507                 ApplySurfaceParm( "pointlight", &contentFlags, &surfaceFlags, NULL );
2508
2509                 /* we don't want this patch getting lightmapped */
2510                 VectorClear( ds->lightmapVecs[ 2 ] );
2511                 VectorClear( ds->lightmapAxis );
2512                 ds->sampleSize = 0;
2513
2514                 /* emit the new fake shader */
2515                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &contentFlags, &surfaceFlags );
2516         }
2517         else
2518                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2519         out->patchWidth = ds->patchWidth;
2520         out->patchHeight = ds->patchHeight;
2521         out->fogNum = ds->fogNum;
2522
2523         /* RBSP */
2524         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2525         {
2526                 out->lightmapNum[ i ] = -3;
2527                 out->lightmapStyles[ i ] = LS_NONE;
2528                 out->vertexStyles[ i ] = LS_NONE;
2529         }
2530         out->lightmapStyles[ 0 ] = LS_NORMAL;
2531         out->vertexStyles[ 0 ] = LS_NORMAL;
2532
2533         /* ydnar: gs mods: previously, the lod bounds were stored in lightmapVecs[ 0 ] and [ 1 ], moved to bounds[ 0 ] and [ 1 ] */
2534         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2535         VectorCopy( ds->bounds[ 0 ], out->lightmapVecs[ 0 ] );
2536         VectorCopy( ds->bounds[ 1 ], out->lightmapVecs[ 1 ] );
2537         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2538
2539         /* ydnar: gs mods: clear out the plane normal */
2540         if( ds->planar == qfalse )
2541                 VectorClear( out->lightmapVecs[ 2 ] );
2542
2543         /* emit the verts and indexes */
2544         EmitDrawVerts( ds, out );
2545         EmitDrawIndexes( ds, out );
2546
2547         /* add to count */
2548         numSurfacesByType[ ds->type ]++;
2549 }
2550
2551
2552
2553 /*
2554 OptimizeTriangleSurface() - ydnar
2555 optimizes the vertex/index data in a triangle surface
2556 */
2557
2558 #define VERTEX_CACHE_SIZE       16
2559
2560 static void OptimizeTriangleSurface( mapDrawSurface_t *ds )
2561 {
2562         int             i, j, k, temp, first, best, bestScore, score;
2563         int             vertexCache[ VERTEX_CACHE_SIZE + 1 ];   /* one more for optimizing insert */
2564         int             *indexes;
2565
2566
2567         /* certain surfaces don't get optimized */
2568         if( ds->numIndexes <= VERTEX_CACHE_SIZE ||
2569                 ds->shaderInfo->autosprite )
2570                 return;
2571
2572         /* create index scratch pad */
2573         indexes = safe_malloc( ds->numIndexes * sizeof( *indexes ) );
2574         memcpy( indexes, ds->indexes, ds->numIndexes * sizeof( *indexes ) );
2575
2576         /* setup */
2577         for( i = 0; i <= VERTEX_CACHE_SIZE && i < ds->numIndexes; i++ )
2578                 vertexCache[ i ] = indexes[ i ];
2579
2580         /* add triangles in a vertex cache-aware order */
2581         for( i = 0; i < ds->numIndexes; i += 3 )
2582         {
2583                 /* find best triangle given the current vertex cache */
2584                 first = -1;
2585                 best = -1;
2586                 bestScore = -1;
2587                 for( j = 0; j < ds->numIndexes; j += 3 )
2588                 {
2589                         /* valid triangle? */
2590                         if( indexes[ j ] != -1 )
2591                         {
2592                                 /* set first if necessary */
2593                                 if( first < 0 )
2594                                         first = j;
2595
2596                                 /* score the triangle */
2597                                 score = 0;
2598                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2599                                 {
2600                                         if( indexes[ j ] == vertexCache[ k ] || indexes[ j + 1 ] == vertexCache[ k ] || indexes[ j + 2 ] == vertexCache[ k ] )
2601                                                 score++;
2602                                 }
2603
2604                                 /* better triangle? */
2605                                 if( score > bestScore )
2606                                 {
2607                                         bestScore = score;
2608                                         best = j;
2609                                 }
2610
2611                                 /* a perfect score of 3 means this triangle's verts are already present in the vertex cache */
2612                                 if( score == 3 )
2613                                         break;
2614                         }
2615                 }
2616
2617                 /* check if no decent triangle was found, and use first available */
2618                 if( best < 0 )
2619                         best = first;
2620
2621                 /* valid triangle? */
2622                 if( best >= 0 )
2623                 {
2624                         /* add triangle to vertex cache */
2625                         for( j = 0; j < 3; j++ )
2626                         {
2627                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2628                                 {
2629                                         if( indexes[ best + j ] == vertexCache[ k ] )
2630                                                 break;
2631                                 }
2632
2633                                 if( k >= VERTEX_CACHE_SIZE )
2634                                 {
2635                                         /* pop off top of vertex cache */
2636                                         for( k = VERTEX_CACHE_SIZE; k > 0; k-- )
2637                                                 vertexCache[ k ] = vertexCache[ k - 1 ];
2638
2639                                         /* add vertex */
2640                                         vertexCache[ 0 ] = indexes[ best + j ];
2641                                 }
2642                         }
2643
2644                         /* add triangle to surface */
2645                         ds->indexes[ i ] = indexes[ best ];
2646                         ds->indexes[ i + 1 ] = indexes[ best + 1 ];
2647                         ds->indexes[ i + 2 ] = indexes[ best + 2 ];
2648
2649                         /* clear from input pool */
2650                         indexes[ best ] = -1;
2651                         indexes[ best + 1 ] = -1;
2652                         indexes[ best + 2 ] = -1;
2653
2654                         /* sort triangle windings (312 -> 123) */
2655                         while( ds->indexes[ i ] > ds->indexes[ i + 1 ] || ds->indexes[ i ] > ds->indexes[ i + 2 ] )
2656                         {
2657                                 temp = ds->indexes[ i ];
2658                                 ds->indexes[ i ] = ds->indexes[ i + 1 ];
2659                                 ds->indexes[ i + 1 ] = ds->indexes[ i + 2 ];
2660                                 ds->indexes[ i + 2 ] = temp;
2661                         }
2662                 }
2663         }
2664
2665         /* clean up */
2666         free( indexes );
2667 }
2668
2669
2670
2671 /*
2672 EmitTriangleSurface()
2673 creates a bsp drawsurface from arbitrary triangle surfaces
2674 */
2675
2676 static void EmitTriangleSurface( mapDrawSurface_t *ds )
2677 {
2678         int                                             i, temp;
2679         bspDrawSurface_t                *out;
2680
2681
2682         /* invert the surface if necessary */
2683         if( ds->backSide || ds->shaderInfo->invert )
2684         {
2685                 /* walk the indexes, reverse the triangle order */
2686                 for( i = 0; i < ds->numIndexes; i += 3 )
2687                 {
2688                         temp = ds->indexes[ i ];
2689                         ds->indexes[ i ] = ds->indexes[ i + 1 ];
2690                         ds->indexes[ i + 1 ] = temp;
2691                 }
2692
2693                 /* walk the verts, flip the normal */
2694                 for( i = 0; i < ds->numVerts; i++ )
2695                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2696
2697                 /* invert facing */
2698                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2699         }
2700
2701         /* allocate a new surface */
2702         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2703                 Error( "MAX_MAP_DRAW_SURFS" );
2704         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2705         ds->outputNum = numBSPDrawSurfaces;
2706         numBSPDrawSurfaces++;
2707         memset( out, 0, sizeof( *out ) );
2708
2709         /* ydnar/sd: handle wolf et foliage surfaces */
2710         if( ds->type == SURFACE_FOLIAGE )
2711                 out->surfaceType = MST_FOLIAGE;
2712
2713         /* ydnar: gs mods: handle lightmapped terrain (force to planar type) */
2714         //%     else if( VectorLength( ds->lightmapAxis ) <= 0.0f || ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FOGHULL || debugSurfaces )
2715         else if( (VectorLength( ds->lightmapAxis ) <= 0.0f && ds->planar == qfalse) ||
2716                 ds->type == SURFACE_TRIANGLES ||
2717                 ds->type == SURFACE_FOGHULL ||
2718                 ds->numVerts > maxLMSurfaceVerts ||
2719                 debugSurfaces )
2720                 out->surfaceType = MST_TRIANGLE_SOUP;
2721
2722         /* set to a planar face */
2723         else
2724                 out->surfaceType = MST_PLANAR;
2725
2726         /* set it up */
2727         if( debugSurfaces )
2728                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2729         else
2730                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2731         out->patchWidth = ds->patchWidth;
2732         out->patchHeight = ds->patchHeight;
2733         out->fogNum = ds->fogNum;
2734
2735         /* debug inset (push each triangle vertex towards the center of each triangle it is on */
2736         if( debugInset )
2737         {
2738                 bspDrawVert_t   *a, *b, *c;
2739                 vec3_t                  cent, dir;
2740
2741
2742                 /* walk triangle list */
2743                 for( i = 0; i < ds->numIndexes; i += 3 )
2744                 {
2745                         /* get verts */
2746                         a = &ds->verts[ ds->indexes[ i ] ];
2747                         b = &ds->verts[ ds->indexes[ i + 1 ] ];
2748                         c = &ds->verts[ ds->indexes[ i + 2 ] ];
2749
2750                         /* calculate centroid */
2751                         VectorCopy( a->xyz, cent );
2752                         VectorAdd( cent, b->xyz, cent );
2753                         VectorAdd( cent, c->xyz, cent );
2754                         VectorScale( cent, 1.0f / 3.0f, cent );
2755
2756                         /* offset each vertex */
2757                         VectorSubtract( cent, a->xyz, dir );
2758                         VectorNormalize( dir, dir );
2759                         VectorAdd( a->xyz, dir, a->xyz );
2760                         VectorSubtract( cent, b->xyz, dir );
2761                         VectorNormalize( dir, dir );
2762                         VectorAdd( b->xyz, dir, b->xyz );
2763                         VectorSubtract( cent, c->xyz, dir );
2764                         VectorNormalize( dir, dir );
2765                         VectorAdd( c->xyz, dir, c->xyz );
2766                 }
2767         }
2768
2769         /* RBSP */
2770         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2771         {
2772                 out->lightmapNum[ i ] = -3;
2773                 out->lightmapStyles[ i ] = LS_NONE;
2774                 out->vertexStyles[ i ] = LS_NONE;
2775         }
2776         out->lightmapStyles[ 0 ] = LS_NORMAL;
2777         out->vertexStyles[ 0 ] = LS_NORMAL;
2778
2779         /* lightmap vectors (lod bounds for patches */
2780         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2781         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );
2782         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2783         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2784
2785         /* ydnar: gs mods: clear out the plane normal */
2786         if( ds->planar == qfalse )
2787                 VectorClear( out->lightmapVecs[ 2 ] );
2788
2789         /* optimize the surface's triangles */
2790         OptimizeTriangleSurface( ds );
2791
2792         /* emit the verts and indexes */
2793         EmitDrawVerts( ds, out );
2794         EmitDrawIndexes( ds, out );
2795
2796         /* add to count */
2797         numSurfacesByType[ ds->type ]++;
2798 }
2799
2800
2801
2802 /*
2803 EmitFaceSurface()
2804 emits a bsp planar winding (brush face) drawsurface
2805 */
2806
2807 static void EmitFaceSurface( mapDrawSurface_t *ds )
2808 {
2809         /* strip/fan finding was moved elsewhere */
2810         StripFaceSurface( ds );
2811         EmitTriangleSurface( ds );
2812 }
2813
2814
2815
2816 /*
2817 MakeDebugPortalSurfs_r() - ydnar
2818 generates drawsurfaces for passable portals in the bsp
2819 */
2820
2821 static void MakeDebugPortalSurfs_r( node_t *node, shaderInfo_t *si )
2822 {
2823         int                                     i, k, c, s;
2824         portal_t                        *p;
2825         winding_t                       *w;
2826         mapDrawSurface_t        *ds;
2827         bspDrawVert_t           *dv;
2828
2829
2830         /* recurse if decision node */
2831         if( node->planenum != PLANENUM_LEAF)
2832         {
2833                 MakeDebugPortalSurfs_r( node->children[ 0 ], si );
2834                 MakeDebugPortalSurfs_r( node->children[ 1 ], si );
2835                 return;
2836         }
2837
2838         /* don't bother with opaque leaves */
2839         if( node->opaque )
2840                 return;
2841
2842         /* walk the list of portals */
2843         for( c = 0, p = node->portals; p != NULL; c++, p = p->next[ s ] )
2844         {
2845                 /* get winding and side even/odd */
2846                 w = p->winding;
2847                 s = (p->nodes[ 1 ] == node);
2848
2849                 /* is this a valid portal for this leaf? */
2850                 if( w && p->nodes[ 0 ] == node )
2851                 {
2852                         /* is this portal passable? */
2853                         if( PortalPassable( p ) == qfalse )
2854                                 continue;
2855
2856                         /* check max points */
2857                         if( w->numpoints > 64 )
2858                                 Error( "MakePortalSurfs_r: w->numpoints = %d", w->numpoints );
2859
2860                         /* allocate a drawsurface */
2861                         ds = AllocDrawSurface( SURFACE_FACE );
2862                         ds->shaderInfo = si;
2863                         ds->planar = qtrue;
2864                         ds->sideRef = AllocSideRef( p->side, NULL );
2865                         ds->planeNum = FindFloatPlane( p->plane.normal, p->plane.dist, 0, NULL );
2866                         VectorCopy( p->plane.normal, ds->lightmapVecs[ 2 ] );
2867                         ds->fogNum = -1;
2868                         ds->numVerts = w->numpoints;
2869                         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2870                         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2871
2872                         /* walk the winding */
2873                         for( i = 0; i < ds->numVerts; i++ )
2874                         {
2875                                 /* get vert */
2876                                 dv = ds->verts + i;
2877
2878                                 /* set it */
2879                                 VectorCopy( w->p[ i ], dv->xyz );
2880                                 VectorCopy( p->plane.normal, dv->normal );
2881                                 dv->st[ 0 ] = 0;
2882                                 dv->st[ 1 ] = 0;
2883                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
2884                                 {
2885                                         VectorCopy( debugColors[ c % 12 ], dv->color[ k ] );
2886                                         dv->color[ k ][ 3 ] = 32;
2887                                 }
2888                         }
2889                 }
2890         }
2891 }
2892
2893
2894
2895 /*
2896 MakeDebugPortalSurfs() - ydnar
2897 generates drawsurfaces for passable portals in the bsp
2898 */
2899
2900 void MakeDebugPortalSurfs( tree_t *tree )
2901 {
2902         shaderInfo_t    *si;
2903
2904
2905         /* note it */
2906         Sys_FPrintf( SYS_VRB, "--- MakeDebugPortalSurfs ---\n" );
2907
2908         /* get portal debug shader */
2909         si = ShaderInfoForShader( "debugportals" );
2910
2911         /* walk the tree */
2912         MakeDebugPortalSurfs_r( tree->headnode, si );
2913 }
2914
2915
2916
2917 /*
2918 MakeFogHullSurfs()
2919 generates drawsurfaces for a foghull (this MUST use a sky shader)
2920 */
2921
2922 void MakeFogHullSurfs( entity_t *e, tree_t *tree, char *shader )
2923 {
2924         shaderInfo_t            *si;
2925         mapDrawSurface_t        *ds;
2926         vec3_t                          fogMins, fogMaxs;
2927         int                                     i, indexes[] =
2928                                                 {
2929                                                         0, 1, 2, 0, 2, 3,
2930                                                         4, 7, 5, 5, 7, 6,
2931                                                         1, 5, 6, 1, 6, 2,
2932                                                         0, 4, 5, 0, 5, 1,
2933                                                         2, 6, 7, 2, 7, 3,
2934                                                         3, 7, 4, 3, 4, 0
2935                                                 };
2936
2937
2938         /* dummy check */
2939         if( shader == NULL || shader[ 0 ] == '\0' )
2940                 return;
2941
2942         /* note it */
2943         Sys_FPrintf( SYS_VRB, "--- MakeFogHullSurfs ---\n" );
2944
2945         /* get hull bounds */
2946         VectorCopy( mapMins, fogMins );
2947         VectorCopy( mapMaxs, fogMaxs );
2948         for( i = 0; i < 3; i++ )
2949         {
2950                 fogMins[ i ] -= 128;
2951                 fogMaxs[ i ] += 128;
2952         }
2953
2954         /* get foghull shader */
2955         si = ShaderInfoForShader( shader );
2956
2957         /* allocate a drawsurface */
2958         ds = AllocDrawSurface( SURFACE_FOGHULL );
2959         ds->shaderInfo = si;
2960         ds->fogNum = -1;
2961         ds->numVerts = 8;
2962         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2963         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2964         ds->numIndexes = 36;
2965         ds->indexes = safe_malloc( ds->numIndexes * sizeof( *ds->indexes ) );
2966         memset( ds->indexes, 0, ds->numIndexes * sizeof( *ds->indexes ) );
2967
2968         /* set verts */
2969         VectorSet( ds->verts[ 0 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
2970         VectorSet( ds->verts[ 1 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
2971         VectorSet( ds->verts[ 2 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
2972         VectorSet( ds->verts[ 3 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
2973
2974         VectorSet( ds->verts[ 4 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
2975         VectorSet( ds->verts[ 5 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
2976         VectorSet( ds->verts[ 6 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
2977         VectorSet( ds->verts[ 7 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
2978
2979         /* set indexes */
2980         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( *ds->indexes ) );
2981 }
2982
2983
2984
2985 /*
2986 BiasSurfaceTextures()
2987 biases a surface's texcoords as close to 0 as possible
2988 */
2989
2990 void BiasSurfaceTextures( mapDrawSurface_t *ds )
2991 {
2992         int             i;
2993
2994
2995         /* calculate the surface texture bias */
2996         CalcSurfaceTextureRange( ds );
2997
2998         /* don't bias globaltextured shaders */
2999         if( ds->shaderInfo->globalTexture )
3000                 return;
3001
3002         /* bias the texture coordinates */
3003         for( i = 0; i < ds->numVerts; i++ )
3004         {
3005                 ds->verts[ i ].st[ 0 ] += ds->bias[ 0 ];
3006                 ds->verts[ i ].st[ 1 ] += ds->bias[ 1 ];
3007         }
3008 }
3009
3010
3011
3012 /*
3013 AddSurfaceModelsToTriangle_r()
3014 adds models to a specified triangle, returns the number of models added
3015 */
3016
3017 int AddSurfaceModelsToTriangle_r( mapDrawSurface_t *ds, surfaceModel_t *model, bspDrawVert_t **tri )
3018 {
3019         bspDrawVert_t   mid, *tri2[ 3 ];
3020         int                             max, n, localNumSurfaceModels;
3021
3022
3023         /* init */
3024         localNumSurfaceModels = 0;
3025
3026         /* subdivide calc */
3027         {
3028                 int                     i;
3029                 float           *a, *b, dx, dy, dz, dist, maxDist;
3030
3031
3032                 /* find the longest edge and split it */
3033                 max = -1;
3034                 maxDist = 0.0f;
3035                 for( i = 0; i < 3; i++ )
3036                 {
3037                         /* get verts */
3038                         a = tri[ i ]->xyz;
3039                         b = tri[ (i + 1) % 3 ]->xyz;
3040
3041                         /* get dists */
3042                         dx = a[ 0 ] - b[ 0 ];
3043                         dy = a[ 1 ] - b[ 1 ];
3044                         dz = a[ 2 ] - b[ 2 ];
3045                         dist = (dx * dx) + (dy * dy) + (dz * dz);
3046
3047                         /* longer? */
3048                         if( dist > maxDist )
3049                         {
3050                                 maxDist = dist;
3051                                 max = i;
3052                         }
3053                 }
3054
3055                 /* is the triangle small enough? */
3056                 if( max < 0 || maxDist <= (model->density * model->density) )
3057                 {
3058                         float   odds, r, angle;
3059                         vec3_t  origin, normal, scale, axis[ 3 ], angles;
3060                         m4x4_t  transform, temp;
3061
3062
3063                         /* roll the dice (model's odds scaled by vertex alpha) */
3064                         odds = model->odds * (tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ]) / 765.0f;
3065                         r = Random();
3066                         if( r > model->odds )
3067                                 return 0;
3068
3069                         /* calculate scale */
3070                         r = model->minScale + Random() * (model->maxScale - model->minScale);
3071                         VectorSet( scale, r, r, r );
3072
3073                         /* calculate angle */
3074                         angle = model->minAngle + Random() * (model->maxAngle - model->minAngle);
3075
3076                         /* calculate average origin */
3077                         VectorCopy( tri[ 0 ]->xyz, origin );
3078                         VectorAdd( origin, tri[ 1 ]->xyz, origin );
3079                         VectorAdd( origin, tri[ 2 ]->xyz, origin );
3080                         VectorScale( origin, (1.0f / 3.0f), origin );
3081
3082                         /* clear transform matrix */
3083                         m4x4_identity( transform );
3084
3085                         /* handle oriented models */
3086                         if( model->oriented )
3087                         {
3088                                 /* set angles */
3089                                 VectorSet( angles, 0.0f, 0.0f, angle );
3090
3091                                 /* calculate average normal */
3092                                 VectorCopy( tri[ 0 ]->normal, normal );
3093                                 VectorAdd( normal, tri[ 1 ]->normal, normal );
3094                                 VectorAdd( normal, tri[ 2 ]->normal, normal );
3095                                 if( VectorNormalize( normal, axis[ 2 ] ) == 0.0f )
3096                                         VectorCopy( tri[ 0 ]->normal, axis[ 2 ] );
3097
3098                                 /* make perpendicular vectors */
3099                                 MakeNormalVectors( axis[ 2 ], axis[ 1 ], axis[ 0 ] );
3100
3101                                 /* copy to matrix */
3102                                 m4x4_identity( temp );
3103                                 temp[ 0 ] = axis[ 0 ][ 0 ];     temp[ 1 ] = axis[ 0 ][ 1 ];     temp[ 2 ] = axis[ 0 ][ 2 ];
3104                                 temp[ 4 ] = axis[ 1 ][ 0 ];     temp[ 5 ] = axis[ 1 ][ 1 ];     temp[ 6 ] = axis[ 1 ][ 2 ];
3105                                 temp[ 8 ] = axis[ 2 ][ 0 ];     temp[ 9 ] = axis[ 2 ][ 1 ];     temp[ 10 ] = axis[ 2 ][ 2 ];
3106
3107                                 /* scale */
3108                                 m4x4_scale_by_vec3( temp, scale );
3109
3110                                 /* rotate around z axis */
3111                                 m4x4_rotate_by_vec3( temp, angles, eXYZ );
3112
3113                                 /* translate */
3114                                 m4x4_translate_by_vec3( transform, origin );
3115
3116                                 /* tranform into axis space */
3117                                 m4x4_multiply_by_m4x4( transform, temp );
3118                         }
3119
3120                         /* handle z-up models */
3121                         else
3122                         {
3123                                 /* set angles */
3124                                 VectorSet( angles, 0.0f, 0.0f, angle );
3125
3126                                 /* set matrix */
3127                                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
3128                         }
3129
3130                         /* insert the model */
3131                         InsertModel( (char *) model->model, 0, transform, NULL, ds->celShader, ds->entityNum, ds->castShadows, ds->recvShadows, 0, ds->lightmapScale );
3132
3133                         /* return to sender */
3134                         return 1;
3135                 }
3136         }
3137
3138         /* split the longest edge and map it */
3139         LerpDrawVert( tri[ max ], tri[ (max + 1) % 3 ], &mid );
3140
3141         /* recurse to first triangle */
3142         VectorCopy( tri, tri2 );
3143         tri2[ max ] = &mid;
3144         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3145         if( n < 0 )
3146                 return n;
3147         localNumSurfaceModels += n;
3148
3149         /* recurse to second triangle */
3150         VectorCopy( tri, tri2 );
3151         tri2[ (max + 1) % 3 ] = &mid;
3152         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3153         if( n < 0 )
3154                 return n;
3155         localNumSurfaceModels += n;
3156
3157         /* return count */
3158         return localNumSurfaceModels;
3159 }
3160
3161
3162
3163 /*
3164 AddSurfaceModels()
3165 adds a surface's shader models to the surface
3166 */
3167
3168 int AddSurfaceModels( mapDrawSurface_t *ds )
3169 {
3170         surfaceModel_t  *model;
3171         int                             i, x, y, n, pw[ 5 ], r, localNumSurfaceModels, iterations;
3172         mesh_t                  src, *mesh, *subdivided;
3173         bspDrawVert_t   centroid, *tri[ 3 ];
3174         float                   alpha;
3175
3176
3177         /* dummy check */
3178         if( ds == NULL || ds->shaderInfo == NULL || ds->shaderInfo->surfaceModel == NULL )
3179                 return 0;
3180
3181         /* init */
3182         localNumSurfaceModels = 0;
3183
3184         /* walk the model list */
3185         for( model = ds->shaderInfo->surfaceModel; model != NULL; model = model->next )
3186         {
3187                 /* switch on type */
3188                 switch( ds->type )
3189                 {
3190                         /* handle brush faces and decals */
3191                         case SURFACE_FACE:
3192                         case SURFACE_DECAL:
3193                                 /* calculate centroid */
3194                                 memset( &centroid, 0, sizeof( centroid ) );
3195                                 alpha = 0.0f;
3196
3197                                 /* walk verts */
3198                                 for( i = 0; i < ds->numVerts; i++ )
3199                                 {
3200                                         VectorAdd( centroid.xyz, ds->verts[ i ].xyz, centroid.xyz );
3201                                         VectorAdd( centroid.normal, ds->verts[ i ].normal, centroid.normal );
3202                                         centroid.st[ 0 ] += ds->verts[ i ].st[ 0 ];
3203                                         centroid.st[ 1 ] += ds->verts[ i ].st[ 1 ];
3204                                         alpha += ds->verts[ i ].color[ 0 ][ 3 ];
3205                                 }
3206
3207                                 /* average */
3208                                 centroid.xyz[ 0 ] /= ds->numVerts;
3209                                 centroid.xyz[ 1 ] /= ds->numVerts;
3210                                 centroid.xyz[ 2 ] /= ds->numVerts;
3211                                 if( VectorNormalize( centroid.normal, centroid.normal ) == 0.0f )
3212                                         VectorCopy( ds->verts[ 0 ].normal, centroid.normal );
3213                                 centroid.st[ 0 ]  /= ds->numVerts;
3214                                 centroid.st[ 1 ]  /= ds->numVerts;
3215                                 alpha /= ds->numVerts;
3216                                 centroid.color[ 0 ][ 0 ] = 0xFF;
3217                                 centroid.color[ 0 ][ 1 ] = 0xFF;
3218                                 centroid.color[ 0 ][ 2 ] = 0xFF;
3219                                 centroid.color[ 0 ][ 2 ] = (alpha > 255.0f ? 0xFF : alpha);
3220
3221                                 /* head vert is centroid */
3222                                 tri[ 0 ] = &centroid;
3223
3224                                 /* walk fanned triangles */
3225                                 for( i = 0; i < ds->numVerts; i++ )
3226                                 {
3227                                         /* set triangle */
3228                                         tri[ 1 ] = &ds->verts[ i ];
3229                                         tri[ 2 ] = &ds->verts[ (i + 1) % ds->numVerts ];
3230
3231                                         /* create models */
3232                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3233                                         if( n < 0 )
3234                                                 return n;
3235                                         localNumSurfaceModels += n;
3236                                 }
3237                                 break;
3238
3239                         /* handle patches */
3240                         case SURFACE_PATCH:
3241                                 /* subdivide the surface */
3242                                 src.width = ds->patchWidth;
3243                                 src.height = ds->patchHeight;
3244                                 src.verts = ds->verts;
3245                                 //%     subdivided = SubdivideMesh( src, 8.0f, 512 );
3246                                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
3247                                 subdivided = SubdivideMesh2( src, iterations );
3248
3249                                 /* fit it to the curve and remove colinear verts on rows/columns */
3250                                 PutMeshOnCurve( *subdivided );
3251                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
3252                                 FreeMesh( subdivided );
3253
3254                                 /* subdivide each quad to place the models */
3255                                 for( y = 0; y < (mesh->height - 1); y++ )
3256                                 {
3257                                         for( x = 0; x < (mesh->width - 1); x++ )
3258                                         {
3259                                                 /* set indexes */
3260                                                 pw[ 0 ] = x + (y * mesh->width);
3261                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
3262                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
3263                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
3264                                                 pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
3265
3266                                                 /* set radix */
3267                                                 r = (x + y) & 1;
3268
3269                                                 /* triangle 1 */
3270                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3271                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 1 ] ];
3272                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 2 ] ];
3273                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3274                                                 if( n < 0 )
3275                                                         return n;
3276                                                 localNumSurfaceModels += n;
3277
3278                                                 /* triangle 2 */
3279                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3280                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 2 ] ];
3281                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 3 ] ];
3282                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3283                                                 if( n < 0 )
3284                                                         return n;
3285                                                 localNumSurfaceModels += n;
3286                                         }
3287                                 }
3288
3289                                 /* free the subdivided mesh */
3290                                 FreeMesh( mesh );
3291                                 break;
3292
3293                         /* handle triangle surfaces */
3294                         case SURFACE_TRIANGLES:
3295                         case SURFACE_FORCED_META:
3296                         case SURFACE_META:
3297                                 /* walk the triangle list */
3298                                 for( i = 0; i < ds->numIndexes; i += 3 )
3299                                 {
3300                                         tri[ 0 ] = &ds->verts[ ds->indexes[ i ] ];
3301                                         tri[ 1 ] = &ds->verts[ ds->indexes[ i + 1 ] ];
3302                                         tri[ 2 ] = &ds->verts[ ds->indexes[ i + 2 ] ];
3303                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3304                                         if( n < 0 )
3305                                                 return n;
3306                                         localNumSurfaceModels += n;
3307                                 }
3308                                 break;
3309
3310                         /* no support for flares, foghull, etc */
3311                         default:
3312                                 break;
3313                 }
3314         }
3315
3316         /* return count */
3317         return localNumSurfaceModels;
3318 }
3319
3320
3321
3322 /*
3323 AddEntitySurfaceModels() - ydnar
3324 adds surfacemodels to an entity's surfaces
3325 */
3326
3327 void AddEntitySurfaceModels( entity_t *e )
3328 {
3329         int             i;
3330
3331
3332         /* note it */
3333         Sys_FPrintf( SYS_VRB, "--- AddEntitySurfaceModels ---\n" );
3334
3335         /* walk the surface list */
3336         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3337                 numSurfaceModels += AddSurfaceModels( &mapDrawSurfs[ i ] );
3338 }
3339
3340
3341
3342 /*
3343 VolumeColorMods() - ydnar
3344 applies brush/volumetric color/alpha modulation to vertexes
3345 */
3346
3347 static void VolumeColorMods( entity_t *e, mapDrawSurface_t *ds )
3348 {
3349         int                     i, j;
3350         float           d;
3351         brush_t         *b;
3352         plane_t         *plane;
3353
3354
3355         /* early out */
3356         if( e->colorModBrushes == NULL )
3357                 return;
3358
3359         /* iterate brushes */
3360         for( b = e->colorModBrushes; b != NULL; b = b->nextColorModBrush )
3361         {
3362                 /* worldspawn alpha brushes affect all, grouped ones only affect original entity */
3363                 if( b->entityNum != 0 && b->entityNum != ds->entityNum )
3364                         continue;
3365
3366                 /* test bbox */
3367                 if( b->mins[ 0 ] > ds->maxs[ 0 ] || b->maxs[ 0 ] < ds->mins[ 0 ] ||
3368                         b->mins[ 1 ] > ds->maxs[ 1 ] || b->maxs[ 1 ] < ds->mins[ 1 ] ||
3369                         b->mins[ 2 ] > ds->maxs[ 2 ] || b->maxs[ 2 ] < ds->mins[ 2 ] )
3370                         continue;
3371
3372                 /* iterate verts */
3373                 for( i = 0; i < ds->numVerts; i++ )
3374                 {
3375                         /* iterate planes */
3376                         for( j = 0; j < b->numsides; j++ )
3377                         {
3378                                 /* point-plane test */
3379                                 plane = &mapplanes[ b->sides[ j ].planenum ];
3380                                 d = DotProduct( ds->verts[ i ].xyz, plane->normal ) - plane->dist;
3381                                 if( d > 1.0f )
3382                                         break;
3383                         }
3384
3385                         /* apply colormods */
3386                         if( j == b->numsides )
3387                                 ColorMod( b->contentShader->colorMod, 1, &ds->verts[ i ] );
3388                 }
3389         }
3390 }
3391
3392
3393
3394 /*
3395 FilterDrawsurfsIntoTree()
3396 upon completion, all drawsurfs that actually generate a reference
3397 will have been emited to the bspfile arrays, and the references
3398 will have valid final indexes
3399 */
3400
3401 void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree )
3402 {
3403         int                                     i, j;
3404         mapDrawSurface_t        *ds;
3405         shaderInfo_t            *si;
3406         vec3_t                          origin, mins, maxs;
3407         int                                     refs;
3408         int                                     numSurfs, numRefs, numSkyboxSurfaces;
3409
3410
3411         /* note it */
3412         Sys_FPrintf( SYS_VRB, "--- FilterDrawsurfsIntoTree ---\n" );
3413
3414         /* filter surfaces into the tree */
3415         numSurfs = 0;
3416         numRefs = 0;
3417         numSkyboxSurfaces = 0;
3418         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
3419         {
3420                 /* get surface and try to early out */
3421                 ds = &mapDrawSurfs[ i ];
3422                 if( ds->numVerts == 0 && ds->type != SURFACE_FLARE && ds->type != SURFACE_SHADER )
3423                         continue;
3424
3425                 /* get shader */
3426                 si = ds->shaderInfo;
3427
3428                 /* ydnar: skybox surfaces are special */
3429                 if( ds->skybox )
3430                 {
3431                         refs = AddReferenceToTree_r( ds, tree->headnode, qtrue );
3432                         ds->skybox = qfalse;
3433                 }
3434                 else
3435                 {
3436                         /* refs initially zero */
3437                         refs = 0;
3438
3439                         /* apply texture coordinate mods */
3440                         for( j = 0; j < ds->numVerts; j++ )
3441                                 TCMod( si->mod, ds->verts[ j ].st );
3442
3443                         /* ydnar: apply shader colormod */
3444                         ColorMod( ds->shaderInfo->colorMod, ds->numVerts, ds->verts );
3445
3446                         /* ydnar: apply brush colormod */
3447                         VolumeColorMods( e, ds );
3448
3449                         /* ydnar: make fur surfaces */
3450                         if( si->furNumLayers > 0 )
3451                                 Fur( ds );
3452
3453                         /* ydnar/sd: make foliage surfaces */
3454                         if( si->foliage != NULL )
3455                                 Foliage( ds );
3456
3457                         /* create a flare surface if necessary */
3458                         if( si->flareShader != NULL && si->flareShader[ 0 ] )
3459                                 AddSurfaceFlare( ds, e->origin );
3460
3461                         /* ydnar: don't emit nodraw surfaces (like nodraw fog) */
3462                         if( si != NULL && (si->compileFlags & C_NODRAW) && ds->type != SURFACE_PATCH )
3463                                 continue;
3464
3465                         /* ydnar: bias the surface textures */
3466                         BiasSurfaceTextures( ds );
3467
3468                         /* ydnar: globalizing of fog volume handling (eek a hack) */
3469                         if( e != entities && si->noFog == qfalse )
3470                         {
3471                                 /* find surface origin and offset by entity origin */
3472                                 VectorAdd( ds->mins, ds->maxs, origin );
3473                                 VectorScale( origin, 0.5f, origin );
3474                                 VectorAdd( origin, e->origin, origin );
3475
3476                                 VectorAdd( ds->mins, e->origin, mins );
3477                                 VectorAdd( ds->maxs, e->origin, maxs );
3478
3479                                 /* set the fog number for this surface */
3480                                 ds->fogNum = FogForBounds( mins, maxs, 1.0f );  //%     FogForPoint( origin, 0.0f );
3481                         }
3482                 }
3483
3484                 /* ydnar: remap shader */
3485                 if( ds->shaderInfo->remapShader && ds->shaderInfo->remapShader[ 0 ] )
3486                         ds->shaderInfo = ShaderInfoForShader( ds->shaderInfo->remapShader );
3487
3488                 /* ydnar: gs mods: handle the various types of surfaces */
3489                 switch( ds->type )
3490                 {
3491                         /* handle brush faces */
3492                         case SURFACE_FACE:
3493                         case SURFACE_DECAL:
3494                                 if( refs == 0 )
3495                                         refs = FilterFaceIntoTree( ds, tree );
3496                                 if( refs > 0 )
3497                                         EmitFaceSurface( ds );
3498                                 break;
3499
3500                         /* handle patches */
3501                         case SURFACE_PATCH:
3502                                 if( refs == 0 )
3503                                         refs = FilterPatchIntoTree( ds, tree );
3504                                 if( refs > 0 )
3505                                         EmitPatchSurface( ds );
3506                                 break;
3507
3508                         /* handle triangle surfaces */
3509                         case SURFACE_TRIANGLES:
3510                         case SURFACE_FORCED_META:
3511                         case SURFACE_META:
3512                                 //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%1d] %4d verts %s\n", numSurfs, ds->planar, ds->numVerts, si->shader );
3513                                 if( refs == 0 )
3514                                         refs = FilterTrianglesIntoTree( ds, tree );
3515                                 if( refs > 0 )
3516                                         EmitTriangleSurface( ds );
3517                                 break;
3518
3519                         /* handle foliage surfaces (splash damage/wolf et) */
3520                         case SURFACE_FOLIAGE:
3521                                 //%     Sys_FPrintf( SYS_VRB, "Surface %4d: [%d] %4d verts %s\n", numSurfs, ds->numFoliageInstances, ds->numVerts, si->shader );
3522                                 if( refs == 0 )
3523                                         refs = FilterFoliageIntoTree( ds, tree );
3524                                 if( refs > 0 )
3525                                         EmitTriangleSurface( ds );
3526                                 break;
3527
3528                         /* handle foghull surfaces */
3529                         case SURFACE_FOGHULL:
3530                                 if( refs == 0 )
3531                                         refs = AddReferenceToTree_r( ds, tree->headnode, qfalse );
3532                                 if( refs > 0 )
3533                                         EmitTriangleSurface( ds );
3534                                 break;
3535
3536                         /* handle flares */
3537                         case SURFACE_FLARE:
3538                                 if( refs == 0 )
3539                                         refs = FilterFlareSurfIntoTree( ds, tree );
3540                                 if( refs > 0 )
3541                                         EmitFlareSurface( ds );
3542                                 break;
3543
3544                         /* handle shader-only surfaces */
3545                         case SURFACE_SHADER:
3546                                 refs = 1;
3547                                 EmitFlareSurface( ds );
3548                                 break;
3549
3550                         /* no references */
3551                         default:
3552                                 refs = 0;
3553                                 break;
3554                 }
3555
3556                 /* tot up the references */
3557                 if( refs > 0 )
3558                 {
3559                         /* tot up counts */
3560                         numSurfs++;
3561                         numRefs += refs;
3562
3563                         /* emit extra surface data */
3564                         SetSurfaceExtra( ds, numBSPDrawSurfaces - 1 );
3565                         //%     Sys_FPrintf( SYS_VRB, "%d verts %d indexes\n", ds->numVerts, ds->numIndexes );
3566
3567                         /* one last sanity check */
3568                         {
3569                                 bspDrawSurface_t        *out;
3570                                 out = &bspDrawSurfaces[ numBSPDrawSurfaces - 1 ];
3571                                 if( out->numVerts == 3 && out->numIndexes > 3 )
3572                                 {
3573                                         Sys_Printf( "\nWARNING: Potentially bad %s surface (%d: %d, %d)\n     %s\n",
3574                                                 surfaceTypes[ ds->type ],
3575                                                 numBSPDrawSurfaces - 1, out->numVerts, out->numIndexes, si->shader );
3576                                 }
3577                         }
3578
3579                         /* ydnar: handle skybox surfaces */
3580                         if( ds->skybox )
3581                         {
3582                                 MakeSkyboxSurface( ds );
3583                                 numSkyboxSurfaces++;
3584                         }
3585                 }
3586         }
3587
3588         /* emit some statistics */
3589         Sys_FPrintf( SYS_VRB, "%9d references\n", numRefs );
3590         Sys_FPrintf( SYS_VRB, "%9d (%d) emitted drawsurfs\n", numSurfs, numBSPDrawSurfaces );
3591         Sys_FPrintf( SYS_VRB, "%9d stripped face surfaces\n", numStripSurfaces );
3592         Sys_FPrintf( SYS_VRB, "%9d fanned face surfaces\n", numFanSurfaces );
3593         Sys_FPrintf( SYS_VRB, "%9d surface models generated\n", numSurfaceModels );
3594         Sys_FPrintf( SYS_VRB, "%9d skybox surfaces generated\n", numSkyboxSurfaces );
3595         for( i = 0; i < NUM_SURFACE_TYPES; i++ )
3596                 Sys_FPrintf( SYS_VRB, "%9d %s surfaces\n", numSurfacesByType[ i ], surfaceTypes[ i ] );
3597
3598         Sys_FPrintf( SYS_VRB, "%9d redundant indexes supressed, saving %d Kbytes\n", numRedundantIndexes, (numRedundantIndexes * 4 / 1024) );
3599 }
3600
3601
3602