tools/quake3/q3map2/surface.c

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