tools/quake3/q3map2/surface.c

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