tools/quake3/q3map2/surface.c

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