tools/quake3/q3map2/map.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 MAP_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41 /* FIXME: remove these vars */
  42
  43 /* undefine to make plane finding use linear sort (note: really slow) */
  44 #define USE_HASHING
  45 #define PLANE_HASHES    8192
  46
  47 plane_t                 *planehash[ PLANE_HASHES ];
  48
  49 int c_boxbevels;
  50 int c_edgebevels;
  51 int c_areaportals;
  52 int c_detail;
  53 int c_structural;
  54
  55
  56
  57 /*
  58    PlaneEqual()
  59    ydnar: replaced with variable epsilon for djbob
  60  */
  61
  62 qboolean PlaneEqual( plane_t *p, vec3_t normal, vec_t dist ){
  63         float ne, de;
  64
  65
  66         /* get local copies */
  67         ne = normalEpsilon;
  68         de = distanceEpsilon;
  69
  70         /* compare */
  71         // We check equality of each component since we're using '<', not '<='
  72         // (the epsilons may be zero).  We want to use '<' intead of '<=' to be
  73         // consistent with the true meaning of "epsilon", and also because other
  74         // parts of the code uses this inequality.
  75         if ( ( p->dist == dist || fabs( p->dist - dist ) < de ) &&
  76                  ( p->normal[0] == normal[0] || fabs( p->normal[0] - normal[0] ) < ne ) &&
  77                  ( p->normal[1] == normal[1] || fabs( p->normal[1] - normal[1] ) < ne ) &&
  78                  ( p->normal[2] == normal[2] || fabs( p->normal[2] - normal[2] ) < ne ) ) {
  79                 return qtrue;
  80         }
  81
  82         /* different */
  83         return qfalse;
  84 }
  85
  86
  87
  88 /*
  89    AddPlaneToHash()
  90  */
  91
  92 void AddPlaneToHash( plane_t *p ){
  93         int hash;
  94
  95
  96         hash = ( PLANE_HASHES - 1 ) & (int) fabs( p->dist );
  97
  98         p->hash_chain = planehash[hash];
  99         planehash[hash] = p;
 100 }
 101
 102 /*
 103    ================
 104    CreateNewFloatPlane
 105    ================
 106  */
 107 int CreateNewFloatPlane( vec3_t normal, vec_t dist ){
 108         plane_t *p, temp;
 109
 110         if ( VectorLength( normal ) < 0.5 ) {
 111                 Sys_Printf( "FloatPlane: bad normal\n" );
 112                 return -1;
 113         }
 114
 115         // create a new plane
 116         if ( nummapplanes + 2 > MAX_MAP_PLANES ) {
 117                 Error( "MAX_MAP_PLANES" );
 118         }
 119
 120         p = &mapplanes[nummapplanes];
 121         VectorCopy( normal, p->normal );
 122         p->dist = dist;
 123         p->type = ( p + 1 )->type = PlaneTypeForNormal( p->normal );
 124
 125         VectorSubtract( vec3_origin, normal, ( p + 1 )->normal );
 126         ( p + 1 )->dist = -dist;
 127
 128         nummapplanes += 2;
 129
 130         // allways put axial planes facing positive first
 131         if ( p->type < 3 ) {
 132                 if ( p->normal[0] < 0 || p->normal[1] < 0 || p->normal[2] < 0 ) {
 133                         // flip order
 134                         temp = *p;
 135                         *p = *( p + 1 );
 136                         *( p + 1 ) = temp;
 137
 138                         AddPlaneToHash( p );
 139                         AddPlaneToHash( p + 1 );
 140                         return nummapplanes - 1;
 141                 }
 142         }
 143
 144         AddPlaneToHash( p );
 145         AddPlaneToHash( p + 1 );
 146         return nummapplanes - 2;
 147 }
 148
 149
 150
 151 /*
 152    SnapNormal()
 153    Snaps a near-axial normal vector.
 154    Returns qtrue if and only if the normal was adjusted.
 155  */
 156
 157 qboolean SnapNormal( vec3_t normal ){
 158 #if Q3MAP2_EXPERIMENTAL_SNAP_NORMAL_FIX
 159         int i;
 160         qboolean adjusted = qfalse;
 161
 162         // A change from the original SnapNormal() is that we snap each
 163         // component that's close to 0.  So for example if a normal is
 164         // (0.707, 0.707, 0.0000001), it will get snapped to lie perfectly in the
 165         // XY plane (its Z component will be set to 0 and its length will be
 166         // normalized).  The original SnapNormal() didn't snap such vectors - it
 167         // only snapped vectors that were near a perfect axis.
 168
 169         for ( i = 0; i < 3; i++ )
 170         {
 171                 if ( normal[i] != 0.0 && -normalEpsilon < normal[i] && normal[i] < normalEpsilon ) {
 172                         normal[i] = 0.0;
 173                         adjusted = qtrue;
 174                 }
 175         }
 176
 177         if ( adjusted ) {
 178                 VectorNormalize( normal, normal );
 179                 return qtrue;
 180         }
 181         return qfalse;
 182 #else
 183         int i;
 184
 185         // I would suggest that you uncomment the following code and look at the
 186         // results:
 187
 188         /*
 189            Sys_Printf("normalEpsilon is %f\n", normalEpsilon);
 190            for (i = 0;; i++)
 191            {
 192             normal[0] = 1.0;
 193             normal[1] = 0.0;
 194             normal[2] = i * 0.000001;
 195             VectorNormalize(normal, normal);
 196             if (1.0 - normal[0] >= normalEpsilon) {
 197                 Sys_Printf("(%f %f %f)\n", normal[0], normal[1], normal[2]);
 198                 Error("SnapNormal: test completed");
 199             }
 200            }
 201          */
 202
 203         // When the normalEpsilon is 0.00001, the loop will break out when normal is
 204         // (0.999990 0.000000 0.004469).  In other words, this is the vector closest
 205         // to axial that will NOT be snapped.  Anything closer will be snaped.  Now,
 206         // 0.004469 is close to 1/225.  The length of a circular quarter-arc of radius
 207         // 1 is PI/2, or about 1.57.  And 0.004469/1.57 is about 0.0028, or about
 208         // 1/350.  Expressed a different way, 1/350 is also about 0.26/90.
 209         // This means is that a normal with an angle that is within 1/4 of a degree
 210         // from axial will be "snapped".  My belief is that the person who wrote the
 211         // code below did not intend it this way.  I think the person intended that
 212         // the epsilon be measured against the vector components close to 0, not 1.0.
 213         // I think the logic should be: if 2 of the normal components are within
 214         // epsilon of 0, then the vector can be snapped to be perfectly axial.
 215         // We may consider adjusting the epsilon to a larger value when we make this
 216         // code fix.
 217
 218         for ( i = 0; i < 3; i++ )
 219         {
 220                 if ( fabs( normal[ i ] - 1 ) < normalEpsilon ) {
 221                         VectorClear( normal );
 222                         normal[ i ] = 1;
 223                         return qtrue;
 224                 }
 225                 if ( fabs( normal[ i ] - -1 ) < normalEpsilon ) {
 226                         VectorClear( normal );
 227                         normal[ i ] = -1;
 228                         return qtrue;
 229                 }
 230         }
 231         return qfalse;
 232 #endif
 233 }
 234
 235
 236
 237 /*
 238    SnapPlane()
 239    snaps a plane to normal/distance epsilons
 240  */
 241
 242 void SnapPlane( vec3_t normal, vec_t *dist ){
 243 // SnapPlane disabled by LordHavoc because it often messes up collision
 244 // brushes made from triangles of embedded models, and it has little effect
 245 // on anything else (axial planes are usually derived from snapped points)
 246 /*
 247    SnapPlane reenabled by namespace because of multiple reports of
 248    q3map2-crashes which were triggered by this patch.
 249  */
 250         SnapNormal( normal );
 251
 252         // TODO: Rambetter has some serious comments here as well.  First off,
 253         // in the case where a normal is non-axial, there is nothing special
 254         // about integer distances.  I would think that snapping a distance might
 255         // make sense for axial normals, but I'm not so sure about snapping
 256         // non-axial normals.  A shift by 0.01 in a plane, multiplied by a clipping
 257         // against another plane that is 5 degrees off, and we introduce 0.1 error
 258         // easily.  A 0.1 error in a vertex is where problems start to happen, such
 259         // as disappearing triangles.
 260
 261         // Second, assuming we have snapped the normal above, let's say that the
 262         // plane we just snapped was defined for some points that are actually
 263         // quite far away from normal * dist.  Well, snapping the normal in this
 264         // case means that we've just moved those points by potentially many units!
 265         // Therefore, if we are going to snap the normal, we need to know the
 266         // points we're snapping for so that the plane snaps with those points in
 267         // mind (points remain close to the plane).
 268
 269         // I would like to know exactly which problems SnapPlane() is trying to
 270         // solve so that we can better engineer it (I'm not saying that SnapPlane()
 271         // should be removed altogether).  Fix all this snapping code at some point!
 272
 273         if ( fabs( *dist - Q_rint( *dist ) ) < distanceEpsilon ) {
 274                 *dist = Q_rint( *dist );
 275         }
 276 }
 277
 278 /*
 279    SnapPlaneImproved()
 280    snaps a plane to normal/distance epsilons, improved code
 281  */
 282 void SnapPlaneImproved( vec3_t normal, vec_t *dist, int numPoints, const vec3_t *points ){
 283         int i;
 284         vec3_t center;
 285         vec_t distNearestInt;
 286
 287         if ( SnapNormal( normal ) ) {
 288                 if ( numPoints > 0 ) {
 289                         // Adjust the dist so that the provided points don't drift away.
 290                         VectorClear( center );
 291                         for ( i = 0; i < numPoints; i++ )
 292                         {
 293                                 VectorAdd( center, points[i], center );
 294                         }
 295                         for ( i = 0; i < 3; i++ ) { center[i] = center[i] / numPoints; }
 296                         *dist = DotProduct( normal, center );
 297                 }
 298         }
 299
 300         if ( VectorIsOnAxis( normal ) ) {
 301                 // Only snap distance if the normal is an axis.  Otherwise there
 302                 // is nothing "natural" about snapping the distance to an integer.
 303                 distNearestInt = Q_rint( *dist );
 304                 if ( -distanceEpsilon < *dist - distNearestInt && *dist - distNearestInt < distanceEpsilon ) {
 305                         *dist = distNearestInt;
 306                 }
 307         }
 308 }
 309
 310
 311 /*
 312    FindFloatPlane()
 313    ydnar: changed to allow a number of test points to be supplied that
 314    must be within an epsilon distance of the plane
 315  */
 316
 317 int FindFloatPlane( vec3_t normal, vec_t dist, int numPoints, vec3_t *points )
 318
 319 #ifdef USE_HASHING
 320
 321 {
 322         int i, j, hash, h;
 323         plane_t *p;
 324         vec_t d;
 325
 326
 327 #if Q3MAP2_EXPERIMENTAL_SNAP_PLANE_FIX
 328         SnapPlaneImproved( normal, &dist, numPoints, (const vec3_t *) points );
 329 #else
 330         SnapPlane( normal, &dist );
 331 #endif
 332         /* hash the plane */
 333         hash = ( PLANE_HASHES - 1 ) & (int) fabs( dist );
 334
 335         /* search the border bins as well */
 336         for ( i = -1; i <= 1; i++ )
 337         {
 338                 h = ( hash + i ) & ( PLANE_HASHES - 1 );
 339                 for ( p = planehash[ h ]; p != NULL; p = p->hash_chain )
 340                 {
 341                         /* do standard plane compare */
 342                         if ( !PlaneEqual( p, normal, dist ) ) {
 343                                 continue;
 344                         }
 345
 346                         /* ydnar: uncomment the following line for old-style plane finding */
 347                         //%     return p - mapplanes;
 348
 349                         /* ydnar: test supplied points against this plane */
 350                         for ( j = 0; j < numPoints; j++ )
 351                         {
 352                                 // NOTE: When dist approaches 2^16, the resolution of 32 bit floating
 353                                 // point number is greatly decreased.  The distanceEpsilon cannot be
 354                                 // very small when world coordinates extend to 2^16.  Making the
 355                                 // dot product here in 64 bit land will not really help the situation
 356                                 // because the error will already be carried in dist.
 357                                 d = DotProduct( points[ j ], normal ) - dist;
 358                                 d = fabs( d );
 359                                 if ( d != 0.0 && d >= distanceEpsilon ) {
 360                                         break; // Point is too far from plane.
 361                                 }
 362                         }
 363
 364                         /* found a matching plane */
 365                         if ( j >= numPoints ) {
 366                                 return p - mapplanes;
 367                         }
 368                 }
 369         }
 370
 371         /* none found, so create a new one */
 372         return CreateNewFloatPlane( normal, dist );
 373 }
 374
 375 #else
 376
 377 {
 378         int i;
 379         plane_t *p;
 380
 381 #if Q3MAP2_EXPERIMENTAL_SNAP_PLANE_FIX
 382         SnapPlaneImproved( normal, &dist, numPoints, (const vec3_t *) points );
 383 #else
 384         SnapPlane( normal, &dist );
 385 #endif
 386         for ( i = 0, p = mapplanes; i < nummapplanes; i++, p++ )
 387         {
 388                 if ( PlaneEqual( p, normal, dist ) ) {
 389                         return i;
 390                 }
 391                 // TODO: Note that the non-USE_HASHING code does not compute epsilons
 392                 // for the provided points.  It should do that.  I think this code
 393                 // is unmaintained because nobody sets USE_HASHING to off.
 394         }
 395
 396         return CreateNewFloatPlane( normal, dist );
 397 }
 398
 399 #endif
 400
 401
 402
 403 /*
 404    MapPlaneFromPoints()
 405    takes 3 points and finds the plane they lie in
 406  */
 407
 408 int MapPlaneFromPoints( vec3_t *p ){
 409 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 410         vec3_accu_t paccu[3];
 411         vec3_accu_t t1, t2, normalAccu;
 412         vec3_t normal;
 413         vec_t dist;
 414
 415         VectorCopyRegularToAccu( p[0], paccu[0] );
 416         VectorCopyRegularToAccu( p[1], paccu[1] );
 417         VectorCopyRegularToAccu( p[2], paccu[2] );
 418
 419         VectorSubtractAccu( paccu[0], paccu[1], t1 );
 420         VectorSubtractAccu( paccu[2], paccu[1], t2 );
 421         CrossProductAccu( t1, t2, normalAccu );
 422         VectorNormalizeAccu( normalAccu, normalAccu );
 423         // TODO: A 32 bit float for the plane distance isn't enough resolution
 424         // if the plane is 2^16 units away from the origin (the "epsilon" approaches
 425         // 0.01 in that case).
 426         dist = (vec_t) DotProductAccu( paccu[0], normalAccu );
 427         VectorCopyAccuToRegular( normalAccu, normal );
 428
 429         return FindFloatPlane( normal, dist, 3, p );
 430 #else
 431         vec3_t t1, t2, normal;
 432         vec_t dist;
 433
 434
 435         /* calc plane normal */
 436         VectorSubtract( p[ 0 ], p[ 1 ], t1 );
 437         VectorSubtract( p[ 2 ], p[ 1 ], t2 );
 438         CrossProduct( t1, t2, normal );
 439         VectorNormalize( normal, normal );
 440
 441         /* calc plane distance */
 442         dist = DotProduct( p[ 0 ], normal );
 443
 444         /* store the plane */
 445         return FindFloatPlane( normal, dist, 3, p );
 446 #endif
 447 }
 448
 449
 450
 451 /*
 452    SetBrushContents()
 453    the content flags and compile flags on all sides of a brush should be the same
 454  */
 455
 456 void SetBrushContents( brush_t *b ){
 457         int contentFlags, compileFlags;
 458         side_t      *s;
 459         int i;
 460         qboolean mixed;
 461
 462
 463         /* get initial compile flags from first side */
 464         s = &b->sides[ 0 ];
 465         contentFlags = s->contentFlags;
 466         compileFlags = s->compileFlags;
 467         b->contentShader = s->shaderInfo;
 468         mixed = qfalse;
 469
 470         /* get the content/compile flags for every side in the brush */
 471         for ( i = 1; i < b->numsides; i++, s++ )
 472         {
 473                 s = &b->sides[ i ];
 474                 if ( s->shaderInfo == NULL ) {
 475                         continue;
 476                 }
 477                 if ( s->contentFlags != contentFlags || s->compileFlags != compileFlags ) {
 478                         mixed = qtrue;
 479                 }
 480         }
 481
 482         /* ydnar: getting rid of this stupid warning */
 483         //%     if( mixed )
 484         //%             Sys_FPrintf( SYS_VRB,"Entity %i, Brush %i: mixed face contentFlags\n", b->entitynum, b->brushnum );
 485
 486         /* check for detail & structural */
 487         if ( ( compileFlags & C_DETAIL ) && ( compileFlags & C_STRUCTURAL ) ) {
 488                 xml_Select( "Mixed detail and structural (defaulting to structural)", mapEnt->mapEntityNum, entitySourceBrushes, qfalse );
 489                 compileFlags &= ~C_DETAIL;
 490         }
 491
 492         /* the fulldetail flag will cause detail brushes to be treated like normal brushes */
 493         if ( fulldetail ) {
 494                 compileFlags &= ~C_DETAIL;
 495         }
 496
 497         /* all translucent brushes that aren't specifically made structural will be detail */
 498         if ( ( compileFlags & C_TRANSLUCENT ) && !( compileFlags & C_STRUCTURAL ) ) {
 499                 compileFlags |= C_DETAIL;
 500         }
 501
 502         /* detail? */
 503         if ( compileFlags & C_DETAIL ) {
 504                 c_detail++;
 505                 b->detail = qtrue;
 506         }
 507         else
 508         {
 509                 c_structural++;
 510                 b->detail = qfalse;
 511         }
 512
 513         /* opaque? */
 514         if ( compileFlags & C_TRANSLUCENT ) {
 515                 b->opaque = qfalse;
 516         }
 517         else{
 518                 b->opaque = qtrue;
 519         }
 520
 521         /* areaportal? */
 522         if ( compileFlags & C_AREAPORTAL ) {
 523                 c_areaportals++;
 524         }
 525
 526         /* set brush flags */
 527         b->contentFlags = contentFlags;
 528         b->compileFlags = compileFlags;
 529 }
 530
 531
 532
 533 /*
 534    AddBrushBevels()
 535    adds any additional planes necessary to allow the brush being
 536    built to be expanded against axial bounding boxes
 537    ydnar 2003-01-20: added mrelusive fixes
 538  */
 539
 540 void AddBrushBevels( void ){
 541         int axis, dir;
 542         int i, j, k, l, order;
 543         side_t sidetemp;
 544         side_t      *s, *s2;
 545         winding_t   *w, *w2;
 546         vec3_t normal;
 547         float dist;
 548         vec3_t vec, vec2;
 549         float d, minBack;
 550
 551         //
 552         // add the axial planes
 553         //
 554         order = 0;
 555         for ( axis = 0; axis < 3; axis++ ) {
 556                 for ( dir = -1; dir <= 1; dir += 2, order++ ) {
 557                         // see if the plane is allready present
 558                         for ( i = 0, s = buildBrush->sides; i < buildBrush->numsides; i++, s++ )
 559                         {
 560                                 /* ydnar: testing disabling of mre code */
 561                                 #if 0
 562                                 if ( dir > 0 ) {
 563                                         if ( mapplanes[s->planenum].normal[axis] >= 0.9999f ) {
 564                                                 break;
 565                                         }
 566                                 }
 567                                 else {
 568                                         if ( mapplanes[s->planenum].normal[axis] <= -0.9999f ) {
 569                                                 break;
 570                                         }
 571                                 }
 572                                 #else
 573                                 if ( ( dir > 0 && mapplanes[ s->planenum ].normal[ axis ] == 1.0f ) ||
 574                                          ( dir < 0 && mapplanes[ s->planenum ].normal[ axis ] == -1.0f ) ) {
 575                                         break;
 576                                 }
 577                                 #endif
 578                         }
 579
 580                         if ( i == buildBrush->numsides ) {
 581                                 // add a new side
 582                                 if ( buildBrush->numsides == MAX_BUILD_SIDES ) {
 583                                         xml_Select( "MAX_BUILD_SIDES", buildBrush->entityNum, buildBrush->brushNum, qtrue );
 584                                 }
 585                                 memset( s, 0, sizeof( *s ) );
 586                                 buildBrush->numsides++;
 587                                 VectorClear( normal );
 588                                 normal[axis] = dir;
 589
 590                                 if ( dir == 1 ) {
 591                                         /* ydnar: adding bevel plane snapping for fewer bsp planes */
 592                                         if ( bevelSnap > 0 ) {
 593                                                 dist = floor( buildBrush->maxs[ axis ] / bevelSnap ) * bevelSnap;
 594                                         }
 595                                         else{
 596                                                 dist = buildBrush->maxs[ axis ];
 597                                         }
 598                                 }
 599                                 else
 600                                 {
 601                                         /* ydnar: adding bevel plane snapping for fewer bsp planes */
 602                                         if ( bevelSnap > 0 ) {
 603                                                 dist = -ceil( buildBrush->mins[ axis ] / bevelSnap ) * bevelSnap;
 604                                         }
 605                                         else{
 606                                                 dist = -buildBrush->mins[ axis ];
 607                                         }
 608                                 }
 609
 610                                 s->planenum = FindFloatPlane( normal, dist, 0, NULL );
 611                                 s->contentFlags = buildBrush->sides[ 0 ].contentFlags;
 612                                 s->bevel = qtrue;
 613                                 c_boxbevels++;
 614                         }
 615
 616                         // if the plane is not in it canonical order, swap it
 617                         if ( i != order ) {
 618                                 sidetemp = buildBrush->sides[order];
 619                                 buildBrush->sides[order] = buildBrush->sides[i];
 620                                 buildBrush->sides[i] = sidetemp;
 621                         }
 622                 }
 623         }
 624
 625         //
 626         // add the edge bevels
 627         //
 628         if ( buildBrush->numsides == 6 ) {
 629                 return;     // pure axial
 630         }
 631
 632         // test the non-axial plane edges
 633         for ( i = 6; i < buildBrush->numsides; i++ ) {
 634                 s = buildBrush->sides + i;
 635                 w = s->winding;
 636                 if ( !w ) {
 637                         continue;
 638                 }
 639                 for ( j = 0; j < w->numpoints; j++ ) {
 640                         k = ( j + 1 ) % w->numpoints;
 641                         VectorSubtract( w->p[j], w->p[k], vec );
 642                         if ( VectorNormalize( vec, vec ) < 0.5f ) {
 643                                 continue;
 644                         }
 645                         SnapNormal( vec );
 646                         for ( k = 0; k < 3; k++ ) {
 647                                 if ( vec[k] == -1.0f || vec[k] == 1.0f || ( vec[k] == 0.0f && vec[( k + 1 ) % 3] == 0.0f ) ) {
 648                                         break;  // axial
 649                                 }
 650                         }
 651                         if ( k != 3 ) {
 652                                 continue;   // only test non-axial edges
 653                         }
 654
 655                         /* debug code */
 656                         //%     Sys_Printf( "-------------\n" );
 657
 658                         // try the six possible slanted axials from this edge
 659                         for ( axis = 0; axis < 3; axis++ ) {
 660                                 for ( dir = -1; dir <= 1; dir += 2 ) {
 661                                         // construct a plane
 662                                         VectorClear( vec2 );
 663                                         vec2[axis] = dir;
 664                                         CrossProduct( vec, vec2, normal );
 665                                         if ( VectorNormalize( normal, normal ) < 0.5f ) {
 666                                                 continue;
 667                                         }
 668                                         dist = DotProduct( w->p[j], normal );
 669
 670                                         // if all the points on all the sides are
 671                                         // behind this plane, it is a proper edge bevel
 672                                         for ( k = 0; k < buildBrush->numsides; k++ ) {
 673
 674                                                 // if this plane has allready been used, skip it
 675                                                 if ( PlaneEqual( &mapplanes[buildBrush->sides[k].planenum], normal, dist ) ) {
 676                                                         break;
 677                                                 }
 678
 679                                                 w2 = buildBrush->sides[k].winding;
 680                                                 if ( !w2 ) {
 681                                                         continue;
 682                                                 }
 683                                                 minBack = 0.0f;
 684                                                 for ( l = 0; l < w2->numpoints; l++ ) {
 685                                                         d = DotProduct( w2->p[l], normal ) - dist;
 686                                                         if ( d > 0.1f ) {
 687                                                                 break;  // point in front
 688                                                         }
 689                                                         if ( d < minBack ) {
 690                                                                 minBack = d;
 691                                                         }
 692                                                 }
 693                                                 // if some point was at the front
 694                                                 if ( l != w2->numpoints ) {
 695                                                         break;
 696                                                 }
 697
 698                                                 // if no points at the back then the winding is on the bevel plane
 699                                                 if ( minBack > -0.1f ) {
 700                                                         //%     Sys_Printf( "On bevel plane\n" );
 701                                                         break;
 702                                                 }
 703                                         }
 704
 705                                         if ( k != buildBrush->numsides ) {
 706                                                 continue;   // wasn't part of the outer hull
 707                                         }
 708
 709                                         /* debug code */
 710                                         //%     Sys_Printf( "n = %f %f %f\n", normal[ 0 ], normal[ 1 ], normal[ 2 ] );
 711
 712                                         // add this plane
 713                                         if ( buildBrush->numsides == MAX_BUILD_SIDES ) {
 714                                                 xml_Select( "MAX_BUILD_SIDES", buildBrush->entityNum, buildBrush->brushNum, qtrue );
 715                                         }
 716                                         s2 = &buildBrush->sides[buildBrush->numsides];
 717                                         buildBrush->numsides++;
 718                                         memset( s2, 0, sizeof( *s2 ) );
 719
 720                                         s2->planenum = FindFloatPlane( normal, dist, 1, &w->p[ j ] );
 721                                         s2->contentFlags = buildBrush->sides[0].contentFlags;
 722                                         s2->bevel = qtrue;
 723                                         c_edgebevels++;
 724                                 }
 725                         }
 726                 }
 727         }
 728 }
 729
 730
 731
 732 /*
 733    FinishBrush()
 734    produces a final brush based on the buildBrush->sides array
 735    and links it to the current entity
 736  */
 737
 738 brush_t *FinishBrush( void ){
 739         brush_t     *b;
 740
 741
 742         /* create windings for sides and bounds for brush */
 743         if ( !CreateBrushWindings( buildBrush ) ) {
 744                 return NULL;
 745         }
 746
 747         /* origin brushes are removed, but they set the rotation origin for the rest of the brushes in the entity.
 748            after the entire entity is parsed, the planenums and texinfos will be adjusted for the origin brush */
 749         if ( buildBrush->compileFlags & C_ORIGIN ) {
 750                 char string[ 32 ];
 751                 vec3_t origin;
 752
 753                 if ( numEntities == 1 ) {
 754                         Sys_Printf( "Entity %i, Brush %i: origin brushes not allowed in world\n",
 755                                                 mapEnt->mapEntityNum, entitySourceBrushes );
 756                         return NULL;
 757                 }
 758
 759                 VectorAdd( buildBrush->mins, buildBrush->maxs, origin );
 760                 VectorScale( origin, 0.5, origin );
 761
 762                 sprintf( string, "%i %i %i", (int) origin[ 0 ], (int) origin[ 1 ], (int) origin[ 2 ] );
 763                 SetKeyValue( &entities[ numEntities - 1 ], "origin", string );
 764
 765                 VectorCopy( origin, entities[ numEntities - 1 ].origin );
 766
 767                 /* don't keep this brush */
 768                 return NULL;
 769         }
 770
 771         /* determine if the brush is an area portal */
 772         if ( buildBrush->compileFlags & C_AREAPORTAL ) {
 773                 if ( numEntities != 1 ) {
 774                         Sys_Printf( "Entity %i, Brush %i: areaportals only allowed in world\n", numEntities - 1, entitySourceBrushes );
 775                         return NULL;
 776                 }
 777         }
 778
 779         /* add bevel planes */
 780         AddBrushBevels();
 781
 782         /* keep it */
 783         b = CopyBrush( buildBrush );
 784
 785         /* set map entity and brush numbering */
 786         b->entityNum = mapEnt->mapEntityNum;
 787         b->brushNum = entitySourceBrushes;
 788
 789         /* set original */
 790         b->original = b;
 791
 792         /* link opaque brushes to head of list, translucent brushes to end */
 793         if ( b->opaque || mapEnt->lastBrush == NULL ) {
 794                 b->next = mapEnt->brushes;
 795                 mapEnt->brushes = b;
 796                 if ( mapEnt->lastBrush == NULL ) {
 797                         mapEnt->lastBrush = b;
 798                 }
 799         }
 800         else
 801         {
 802                 b->next = NULL;
 803                 mapEnt->lastBrush->next = b;
 804                 mapEnt->lastBrush = b;
 805         }
 806
 807         /* link colorMod volume brushes to the entity directly */
 808         if ( b->contentShader != NULL &&
 809                  b->contentShader->colorMod != NULL &&
 810                  b->contentShader->colorMod->type == CM_VOLUME ) {
 811                 b->nextColorModBrush = mapEnt->colorModBrushes;
 812                 mapEnt->colorModBrushes = b;
 813         }
 814
 815         /* return to sender */
 816         return b;
 817 }
 818
 819
 820
 821 /*
 822    TextureAxisFromPlane()
 823    determines best orthagonal axis to project a texture onto a wall
 824    (must be identical in radiant!)
 825  */
 826
 827 vec3_t baseaxis[18] =
 828 {
 829         {0,0,1}, {1,0,0}, {0,-1,0},         // floor
 830         {0,0,-1}, {1,0,0}, {0,-1,0},        // ceiling
 831         {1,0,0}, {0,1,0}, {0,0,-1},         // west wall
 832         {-1,0,0}, {0,1,0}, {0,0,-1},        // east wall
 833         {0,1,0}, {1,0,0}, {0,0,-1},         // south wall
 834         {0,-1,0}, {1,0,0}, {0,0,-1}         // north wall
 835 };
 836
 837 void TextureAxisFromPlane( plane_t *pln, vec3_t xv, vec3_t yv ){
 838         int bestaxis;
 839         vec_t dot,best;
 840         int i;
 841
 842         best = 0;
 843         bestaxis = 0;
 844
 845         for ( i = 0 ; i < 6 ; i++ )
 846         {
 847                 dot = DotProduct( pln->normal, baseaxis[i * 3] );
 848                 if ( dot > best + 0.0001f ) { /* ydnar: bug 637 fix, suggested by jmonroe */
 849                         best = dot;
 850                         bestaxis = i;
 851                 }
 852         }
 853
 854         VectorCopy( baseaxis[bestaxis * 3 + 1], xv );
 855         VectorCopy( baseaxis[bestaxis * 3 + 2], yv );
 856 }
 857
 858
 859
 860 /*
 861    QuakeTextureVecs()
 862    creates world-to-texture mapping vecs for crappy quake plane arrangements
 863  */
 864
 865 void QuakeTextureVecs( plane_t *plane, vec_t shift[ 2 ], vec_t rotate, vec_t scale[ 2 ], vec_t mappingVecs[ 2 ][ 4 ] ){
 866         vec3_t vecs[2];
 867         int sv, tv;
 868         vec_t ang, sinv, cosv;
 869         vec_t ns, nt;
 870         int i, j;
 871
 872
 873         TextureAxisFromPlane( plane, vecs[0], vecs[1] );
 874
 875         if ( !scale[0] ) {
 876                 scale[0] = 1;
 877         }
 878         if ( !scale[1] ) {
 879                 scale[1] = 1;
 880         }
 881
 882         // rotate axis
 883         if ( rotate == 0 ) {
 884                 sinv = 0 ; cosv = 1;
 885         }
 886         else if ( rotate == 90 ) {
 887                 sinv = 1 ; cosv = 0;
 888         }
 889         else if ( rotate == 180 ) {
 890                 sinv = 0 ; cosv = -1;
 891         }
 892         else if ( rotate == 270 ) {
 893                 sinv = -1 ; cosv = 0;
 894         }
 895         else
 896         {
 897                 ang = rotate / 180 * Q_PI;
 898                 sinv = sin( ang );
 899                 cosv = cos( ang );
 900         }
 901
 902         if ( vecs[0][0] ) {
 903                 sv = 0;
 904         }
 905         else if ( vecs[0][1] ) {
 906                 sv = 1;
 907         }
 908         else{
 909                 sv = 2;
 910         }
 911
 912         if ( vecs[1][0] ) {
 913                 tv = 0;
 914         }
 915         else if ( vecs[1][1] ) {
 916                 tv = 1;
 917         }
 918         else{
 919                 tv = 2;
 920         }
 921
 922         for ( i = 0 ; i < 2 ; i++ ) {
 923                 ns = cosv * vecs[i][sv] - sinv * vecs[i][tv];
 924                 nt = sinv * vecs[i][sv] +  cosv * vecs[i][tv];
 925                 vecs[i][sv] = ns;
 926                 vecs[i][tv] = nt;
 927         }
 928
 929         for ( i = 0 ; i < 2 ; i++ )
 930                 for ( j = 0 ; j < 3 ; j++ )
 931                         mappingVecs[i][j] = vecs[i][j] / scale[i];
 932
 933         mappingVecs[0][3] = shift[0];
 934         mappingVecs[1][3] = shift[1];
 935 }
 936
 937
 938
 939 /*
 940    ParseRawBrush()
 941    parses the sides into buildBrush->sides[], nothing else.
 942    no validation, back plane removal, etc.
 943
 944    Timo - 08/26/99
 945    added brush epairs parsing ( ignoring actually )
 946    Timo - 08/04/99
 947    added exclusive brush primitive parsing
 948    Timo - 08/08/99
 949    support for old brush format back in
 950    NOTE: it would be "cleaner" to have seperate functions to parse between old and new brushes
 951  */
 952
 953 static void ParseRawBrush( qboolean onlyLights ){
 954         side_t          *side;
 955         vec3_t planePoints[ 3 ];
 956         int planenum;
 957         shaderInfo_t    *si;
 958         vec_t shift[ 2 ];
 959         vec_t rotate;
 960         vec_t scale[ 2 ];
 961         char name[ MAX_QPATH ];
 962         char shader[ MAX_QPATH ];
 963         int flags;
 964
 965
 966         /* initial setup */
 967         buildBrush->numsides = 0;
 968         buildBrush->detail = qfalse;
 969
 970         /* bp */
 971         if ( g_bBrushPrimit == BPRIMIT_NEWBRUSHES ) {
 972                 MatchToken( "{" );
 973         }
 974
 975         /* parse sides */
 976         while ( 1 )
 977         {
 978                 if ( !GetToken( qtrue ) ) {
 979                         break;
 980                 }
 981                 if ( !strcmp( token, "}" ) ) {
 982                         break;
 983                 }
 984
 985                 /* ttimo : bp: here we may have to jump over brush epairs (only used in editor) */
 986                 if ( g_bBrushPrimit == BPRIMIT_NEWBRUSHES ) {
 987                         while ( 1 )
 988                         {
 989                                 if ( strcmp( token, "(" ) ) {
 990                                         GetToken( qfalse );
 991                                 }
 992                                 else{
 993                                         break;
 994                                 }
 995                                 GetToken( qtrue );
 996                         }
 997                 }
 998                 UnGetToken();
 999
1000                 /* test side count */
1001                 if ( buildBrush->numsides >= MAX_BUILD_SIDES ) {
1002                         xml_Select( "MAX_BUILD_SIDES", buildBrush->entityNum, buildBrush->brushNum, qtrue );
1003                 }
1004
1005                 /* add side */
1006                 side = &buildBrush->sides[ buildBrush->numsides ];
1007                 memset( side, 0, sizeof( *side ) );
1008                 buildBrush->numsides++;
1009
1010                 /* read the three point plane definition */
1011                 Parse1DMatrix( 3, planePoints[ 0 ] );
1012                 Parse1DMatrix( 3, planePoints[ 1 ] );
1013                 Parse1DMatrix( 3, planePoints[ 2 ] );
1014
1015                 /* bp: read the texture matrix */
1016                 if ( g_bBrushPrimit == BPRIMIT_NEWBRUSHES ) {
1017                         Parse2DMatrix( 2, 3, (float*) side->texMat );
1018                 }
1019
1020                 /* read shader name */
1021                 GetToken( qfalse );
1022                 strcpy( name, token );
1023
1024                 /* bp */
1025                 if ( g_bBrushPrimit == BPRIMIT_OLDBRUSHES ) {
1026                         GetToken( qfalse );
1027                         shift[ 0 ] = atof( token );
1028                         GetToken( qfalse );
1029                         shift[ 1 ] = atof( token );
1030                         GetToken( qfalse );
1031                         rotate = atof( token );
1032                         GetToken( qfalse );
1033                         scale[ 0 ] = atof( token );
1034                         GetToken( qfalse );
1035                         scale[ 1 ] = atof( token );
1036                 }
1037
1038                 /* set default flags and values */
1039                 sprintf( shader, "textures/%s", name );
1040                 if ( onlyLights ) {
1041                         si = &shaderInfo[ 0 ];
1042                 }
1043                 else{
1044                         si = ShaderInfoForShader( shader );
1045                 }
1046                 side->shaderInfo = si;
1047                 side->surfaceFlags = si->surfaceFlags;
1048                 side->contentFlags = si->contentFlags;
1049                 side->compileFlags = si->compileFlags;
1050                 side->value = si->value;
1051
1052                 /* ydnar: gs mods: bias texture shift */
1053                 if ( si->globalTexture == qfalse ) {
1054                         shift[ 0 ] -= ( floor( shift[ 0 ] / si->shaderWidth ) * si->shaderWidth );
1055                         shift[ 1 ] -= ( floor( shift[ 1 ] / si->shaderHeight ) * si->shaderHeight );
1056                 }
1057
1058                 /*
1059                     historically, there are 3 integer values at the end of a brushside line in a .map file.
1060                     in quake 3, the only thing that mattered was the first of these three values, which
1061                     was previously the content flags. and only then did a single bit matter, the detail
1062                     bit. because every game has its own special flags for specifying detail, the
1063                     traditionally game-specified CONTENTS_DETAIL flag was overridden for Q3Map 2.3.0
1064                     by C_DETAIL, defined in q3map2.h. the value is exactly as it was before, but
1065                     is stored in compileFlags, as opposed to contentFlags, for multiple-game
1066                     portability. :sigh:
1067                  */
1068
1069                 if ( TokenAvailable() ) {
1070                         /* get detail bit from map content flags */
1071                         GetToken( qfalse );
1072                         flags = atoi( token );
1073                         if ( flags & C_DETAIL ) {
1074                                 side->compileFlags |= C_DETAIL;
1075                         }
1076
1077                         /* historical */
1078                         GetToken( qfalse );
1079                         //% td.flags = atoi( token );
1080                         GetToken( qfalse );
1081                         //% td.value = atoi( token );
1082                 }
1083
1084                 /* find the plane number */
1085                 planenum = MapPlaneFromPoints( planePoints );
1086                 side->planenum = planenum;
1087
1088                 /* bp: get the texture mapping for this texturedef / plane combination */
1089                 if ( g_bBrushPrimit == BPRIMIT_OLDBRUSHES ) {
1090                         QuakeTextureVecs( &mapplanes[ planenum ], shift, rotate, scale, side->vecs );
1091                 }
1092         }
1093
1094         /* bp */
1095         if ( g_bBrushPrimit == BPRIMIT_NEWBRUSHES ) {
1096                 UnGetToken();
1097                 MatchToken( "}" );
1098                 MatchToken( "}" );
1099         }
1100 }
1101
1102
1103
1104 /*
1105    RemoveDuplicateBrushPlanes
1106    returns false if the brush has a mirrored set of planes,
1107    meaning it encloses no volume.
1108    also removes planes without any normal
1109  */
1110
1111 qboolean RemoveDuplicateBrushPlanes( brush_t *b ){
1112         int i, j, k;
1113         side_t      *sides;
1114
1115         sides = b->sides;
1116
1117         for ( i = 1 ; i < b->numsides ; i++ ) {
1118
1119                 // check for a degenerate plane
1120                 if ( sides[i].planenum == -1 ) {
1121                         xml_Select( "degenerate plane", b->entityNum, b->brushNum, qfalse );
1122                         // remove it
1123                         for ( k = i + 1 ; k < b->numsides ; k++ ) {
1124                                 sides[k - 1] = sides[k];
1125                         }
1126                         b->numsides--;
1127                         i--;
1128                         continue;
1129                 }
1130
1131                 // check for duplication and mirroring
1132                 for ( j = 0 ; j < i ; j++ ) {
1133                         if ( sides[i].planenum == sides[j].planenum ) {
1134                                 xml_Select( "duplicate plane", b->entityNum, b->brushNum, qfalse );
1135                                 // remove the second duplicate
1136                                 for ( k = i + 1 ; k < b->numsides ; k++ ) {
1137                                         sides[k - 1] = sides[k];
1138                                 }
1139                                 b->numsides--;
1140                                 i--;
1141                                 break;
1142                         }
1143
1144                         if ( sides[i].planenum == ( sides[j].planenum ^ 1 ) ) {
1145                                 // mirror plane, brush is invalid
1146                                 xml_Select( "mirrored plane", b->entityNum, b->brushNum, qfalse );
1147                                 return qfalse;
1148                         }
1149                 }
1150         }
1151         return qtrue;
1152 }
1153
1154
1155
1156 /*
1157    ParseBrush()
1158    parses a brush out of a map file and sets it up
1159  */
1160
1161 static void ParseBrush( qboolean onlyLights ){
1162         brush_t *b;
1163
1164
1165         /* parse the brush out of the map */
1166         ParseRawBrush( onlyLights );
1167
1168         /* only go this far? */
1169         if ( onlyLights ) {
1170                 return;
1171         }
1172
1173         /* set some defaults */
1174         buildBrush->portalareas[ 0 ] = -1;
1175         buildBrush->portalareas[ 1 ] = -1;
1176         buildBrush->entityNum = numMapEntities - 1;
1177         buildBrush->brushNum = entitySourceBrushes;
1178
1179         /* if there are mirrored planes, the entire brush is invalid */
1180         if ( !RemoveDuplicateBrushPlanes( buildBrush ) ) {
1181                 return;
1182         }
1183
1184         /* get the content for the entire brush */
1185         SetBrushContents( buildBrush );
1186
1187         /* allow detail brushes to be removed */
1188         if ( nodetail && ( buildBrush->compileFlags & C_DETAIL ) ) {
1189                 //%     FreeBrush( buildBrush );
1190                 return;
1191         }
1192
1193         /* allow liquid brushes to be removed */
1194         if ( nowater && ( buildBrush->compileFlags & C_LIQUID ) ) {
1195                 //%     FreeBrush( buildBrush );
1196                 return;
1197         }
1198
1199         /* ydnar: allow hint brushes to be removed */
1200         if ( noHint && ( buildBrush->compileFlags & C_HINT ) ) {
1201                 //%     FreeBrush( buildBrush );
1202                 return;
1203         }
1204
1205         /* finish the brush */
1206         b = FinishBrush();
1207 }
1208
1209
1210
1211 /*
1212    MoveBrushesToWorld()
1213    takes all of the brushes from the current entity and
1214    adds them to the world's brush list
1215    (used by func_group)
1216  */
1217
1218 void MoveBrushesToWorld( entity_t *ent ){
1219         brush_t     *b, *next;
1220         parseMesh_t *pm;
1221
1222
1223         /* move brushes */
1224         for ( b = ent->brushes; b != NULL; b = next )
1225         {
1226                 /* get next brush */
1227                 next = b->next;
1228
1229                 /* link opaque brushes to head of list, translucent brushes to end */
1230                 if ( b->opaque || entities[ 0 ].lastBrush == NULL ) {
1231                         b->next = entities[ 0 ].brushes;
1232                         entities[ 0 ].brushes = b;
1233                         if ( entities[ 0 ].lastBrush == NULL ) {
1234                                 entities[ 0 ].lastBrush = b;
1235                         }
1236                 }
1237                 else
1238                 {
1239                         b->next = NULL;
1240                         entities[ 0 ].lastBrush->next = b;
1241                         entities[ 0 ].lastBrush = b;
1242                 }
1243         }
1244         ent->brushes = NULL;
1245
1246         /* ydnar: move colormod brushes */
1247         if ( ent->colorModBrushes != NULL ) {
1248                 for ( b = ent->colorModBrushes; b->nextColorModBrush != NULL; b = b->nextColorModBrush ) ;
1249
1250                 b->nextColorModBrush = entities[ 0 ].colorModBrushes;
1251                 entities[ 0 ].colorModBrushes = ent->colorModBrushes;
1252
1253                 ent->colorModBrushes = NULL;
1254         }
1255
1256         /* move patches */
1257         if ( ent->patches != NULL ) {
1258                 for ( pm = ent->patches; pm->next != NULL; pm = pm->next ) ;
1259
1260                 pm->next = entities[ 0 ].patches;
1261                 entities[ 0 ].patches = ent->patches;
1262
1263                 ent->patches = NULL;
1264         }
1265 }
1266
1267
1268
1269 /*
1270    AdjustBrushesForOrigin()
1271  */
1272
1273 void AdjustBrushesForOrigin( entity_t *ent ){
1274
1275         int i;
1276         side_t      *s;
1277         vec_t newdist;
1278         brush_t     *b;
1279         parseMesh_t *p;
1280
1281
1282         /* walk brush list */
1283         for ( b = ent->brushes; b != NULL; b = b->next )
1284         {
1285                 /* offset brush planes */
1286                 for ( i = 0; i < b->numsides; i++ )
1287                 {
1288                         /* get brush side */
1289                         s = &b->sides[ i ];
1290
1291                         /* offset side plane */
1292                         newdist = mapplanes[ s->planenum ].dist - DotProduct( mapplanes[ s->planenum ].normal, ent->origin );
1293
1294                         /* find a new plane */
1295                         s->planenum = FindFloatPlane( mapplanes[ s->planenum ].normal, newdist, 0, NULL );
1296                 }
1297
1298                 /* rebuild brush windings (ydnar: just offsetting the winding above should be fine) */
1299                 CreateBrushWindings( b );
1300         }
1301
1302         /* walk patch list */
1303         for ( p = ent->patches; p != NULL; p = p->next )
1304         {
1305                 for ( i = 0; i < ( p->mesh.width * p->mesh.height ); i++ )
1306                         VectorSubtract( p->mesh.verts[ i ].xyz, ent->origin, p->mesh.verts[ i ].xyz );
1307         }
1308 }
1309
1310
1311
1312 /*
1313    SetEntityBounds() - ydnar
1314    finds the bounds of an entity's brushes (necessary for terrain-style generic metashaders)
1315  */
1316
1317 void SetEntityBounds( entity_t *e ){
1318         int i;
1319         brush_t *b;
1320         parseMesh_t *p;
1321         vec3_t mins, maxs;
1322         const char  *value;
1323
1324
1325
1326
1327         /* walk the entity's brushes/patches and determine bounds */
1328         ClearBounds( mins, maxs );
1329         for ( b = e->brushes; b; b = b->next )
1330         {
1331                 AddPointToBounds( b->mins, mins, maxs );
1332                 AddPointToBounds( b->maxs, mins, maxs );
1333         }
1334         for ( p = e->patches; p; p = p->next )
1335         {
1336                 for ( i = 0; i < ( p->mesh.width * p->mesh.height ); i++ )
1337                         AddPointToBounds( p->mesh.verts[ i ].xyz, mins, maxs );
1338         }
1339
1340         /* try to find explicit min/max key */
1341         value = ValueForKey( e, "min" );
1342         if ( value[ 0 ] != '\0' ) {
1343                 GetVectorForKey( e, "min", mins );
1344         }
1345         value = ValueForKey( e, "max" );
1346         if ( value[ 0 ] != '\0' ) {
1347                 GetVectorForKey( e, "max", maxs );
1348         }
1349
1350         /* store the bounds */
1351         for ( b = e->brushes; b; b = b->next )
1352         {
1353                 VectorCopy( mins, b->eMins );
1354                 VectorCopy( maxs, b->eMaxs );
1355         }
1356         for ( p = e->patches; p; p = p->next )
1357         {
1358                 VectorCopy( mins, p->eMins );
1359                 VectorCopy( maxs, p->eMaxs );
1360         }
1361 }
1362
1363
1364
1365 /*
1366    LoadEntityIndexMap() - ydnar
1367    based on LoadAlphaMap() from terrain.c, a little more generic
1368  */
1369
1370 void LoadEntityIndexMap( entity_t *e ){
1371         int i, size, numLayers, w, h;
1372         const char      *value, *indexMapFilename, *shader;
1373         char ext[ MAX_QPATH ], offset[ 4096 ], *search, *space;
1374         byte            *pixels;
1375         unsigned int    *pixels32;
1376         indexMap_t      *im;
1377         brush_t         *b;
1378         parseMesh_t     *p;
1379
1380
1381         /* this only works with bmodel ents */
1382         if ( e->brushes == NULL && e->patches == NULL ) {
1383                 return;
1384         }
1385
1386         /* determine if there is an index map (support legacy "alphamap" key as well) */
1387         value = ValueForKey( e, "_indexmap" );
1388         if ( value[ 0 ] == '\0' ) {
1389                 value = ValueForKey( e, "alphamap" );
1390         }
1391         if ( value[ 0 ] == '\0' ) {
1392                 return;
1393         }
1394         indexMapFilename = value;
1395
1396         /* get number of layers (support legacy "layers" key as well) */
1397         value = ValueForKey( e, "_layers" );
1398         if ( value[ 0 ] == '\0' ) {
1399                 value = ValueForKey( e, "layers" );
1400         }
1401         if ( value[ 0 ] == '\0' ) {
1402                 Sys_Printf( "WARNING: Entity with index/alpha map \"%s\" has missing \"_layers\" or \"layers\" key\n", indexMapFilename );
1403                 Sys_Printf( "Entity will not be textured properly. Check your keys/values.\n" );
1404                 return;
1405         }
1406         numLayers = atoi( value );
1407         if ( numLayers < 1 ) {
1408                 Sys_Printf( "WARNING: Entity with index/alpha map \"%s\" has < 1 layer (%d)\n", indexMapFilename, numLayers );
1409                 Sys_Printf( "Entity will not be textured properly. Check your keys/values.\n" );
1410                 return;
1411         }
1412
1413         /* get base shader name (support legacy "shader" key as well) */
1414         value = ValueForKey( mapEnt, "_shader" );
1415         if ( value[ 0 ] == '\0' ) {
1416                 value = ValueForKey( e, "shader" );
1417         }
1418         if ( value[ 0 ] == '\0' ) {
1419                 Sys_Printf( "WARNING: Entity with index/alpha map \"%s\" has missing \"_shader\" or \"shader\" key\n", indexMapFilename );
1420                 Sys_Printf( "Entity will not be textured properly. Check your keys/values.\n" );
1421                 return;
1422         }
1423         shader = value;
1424
1425         /* note it */
1426         Sys_FPrintf( SYS_VRB, "Entity %d (%s) has shader index map \"%s\"\n",  mapEnt->mapEntityNum, ValueForKey( e, "classname" ), indexMapFilename );
1427
1428         /* get index map file extension */
1429         ExtractFileExtension( indexMapFilename, ext );
1430
1431         /* handle tga image */
1432         if ( !Q_stricmp( ext, "tga" ) ) {
1433                 /* load it */
1434                 Load32BitImage( indexMapFilename, &pixels32, &w, &h );
1435
1436                 /* convert to bytes */
1437                 size = w * h;
1438                 pixels = safe_malloc( size );
1439                 for ( i = 0; i < size; i++ )
1440                 {
1441                         pixels[ i ] = ( ( pixels32[ i ] & 0xFF ) * numLayers ) / 256;
1442                         if ( pixels[ i ] >= numLayers ) {
1443                                 pixels[ i ] = numLayers - 1;
1444                         }
1445                 }
1446
1447                 /* free the 32 bit image */
1448                 free( pixels32 );
1449         }
1450         else
1451         {
1452                 /* load it */
1453                 Load256Image( indexMapFilename, &pixels, NULL, &w, &h );
1454
1455                 /* debug code */
1456                 //%     Sys_Printf( "-------------------------------" );
1457
1458                 /* fix up out-of-range values */
1459                 size = w * h;
1460                 for ( i = 0; i < size; i++ )
1461                 {
1462                         if ( pixels[ i ] >= numLayers ) {
1463                                 pixels[ i ] = numLayers - 1;
1464                         }
1465
1466                         /* debug code */
1467                         //%     if( (i % w) == 0 )
1468                         //%             Sys_Printf( "\n" );
1469                         //%     Sys_Printf( "%c", pixels[ i ] + '0' );
1470                 }
1471
1472                 /* debug code */
1473                 //%     Sys_Printf( "\n-------------------------------\n" );
1474         }
1475
1476         /* the index map must be at least 2x2 pixels */
1477         if ( w < 2 || h < 2 ) {
1478                 Sys_Printf( "WARNING: Entity with index/alpha map \"%s\" is smaller than 2x2 pixels\n", indexMapFilename );
1479                 Sys_Printf( "Entity will not be textured properly. Check your keys/values.\n" );
1480                 free( pixels );
1481                 return;
1482         }
1483
1484         /* create a new index map */
1485         im = safe_malloc( sizeof( *im ) );
1486         memset( im, 0, sizeof( *im ) );
1487
1488         /* set it up */
1489         im->w = w;
1490         im->h = h;
1491         im->numLayers = numLayers;
1492         strcpy( im->name, indexMapFilename );
1493         strcpy( im->shader, shader );
1494         im->pixels = pixels;
1495
1496         /* get height offsets */
1497         value = ValueForKey( mapEnt, "_offsets" );
1498         if ( value[ 0 ] == '\0' ) {
1499                 value = ValueForKey( e, "offsets" );
1500         }
1501         if ( value[ 0 ] != '\0' ) {
1502                 /* value is a space-seperated set of numbers */
1503                 strcpy( offset, value );
1504                 search = offset;
1505
1506                 /* get each value */
1507                 for ( i = 0; i < 256 && *search != '\0'; i++ )
1508                 {
1509                         space = strstr( search, " " );
1510                         if ( space != NULL ) {
1511                                 *space = '\0';
1512                         }
1513                         im->offsets[ i ] = atof( search );
1514                         if ( space == NULL ) {
1515                                 break;
1516                         }
1517                         search = space + 1;
1518                 }
1519         }
1520
1521         /* store the index map in every brush/patch in the entity */
1522         for ( b = e->brushes; b != NULL; b = b->next )
1523                 b->im = im;
1524         for ( p = e->patches; p != NULL; p = p->next )
1525                 p->im = im;
1526 }
1527
1528
1529
1530
1531
1532
1533
1534 /*
1535    ParseMapEntity()
1536    parses a single entity out of a map file
1537  */
1538
1539 static qboolean ParseMapEntity( qboolean onlyLights ){
1540         epair_t         *ep;
1541         const char      *classname, *value;
1542         float lightmapScale;
1543         char shader[ MAX_QPATH ];
1544         shaderInfo_t    *celShader = NULL;
1545         brush_t         *brush;
1546         parseMesh_t     *patch;
1547         qboolean funcGroup;
1548         int castShadows, recvShadows;
1549
1550
1551         /* eof check */
1552         if ( !GetToken( qtrue ) ) {
1553                 return qfalse;
1554         }
1555
1556         /* conformance check */
1557         if ( strcmp( token, "{" ) ) {
1558                 Sys_Printf( "WARNING: ParseEntity: { not found, found %s on line %d - last entity was at: <%4.2f, %4.2f, %4.2f>...\n"
1559                                         "Continuing to process map, but resulting BSP may be invalid.\n",
1560                                         token, scriptline, entities[ numEntities ].origin[ 0 ], entities[ numEntities ].origin[ 1 ], entities[ numEntities ].origin[ 2 ] );
1561                 return qfalse;
1562         }
1563
1564         /* range check */
1565         if ( numEntities >= MAX_MAP_ENTITIES ) {
1566                 Error( "numEntities == MAX_MAP_ENTITIES" );
1567         }
1568
1569         /* setup */
1570         entitySourceBrushes = 0;
1571         mapEnt = &entities[ numEntities ];
1572         numEntities++;
1573         memset( mapEnt, 0, sizeof( *mapEnt ) );
1574
1575         /* ydnar: true entity numbering */
1576         mapEnt->mapEntityNum = numMapEntities;
1577         numMapEntities++;
1578
1579         /* loop */
1580         while ( 1 )
1581         {
1582                 /* get initial token */
1583                 if ( !GetToken( qtrue ) ) {
1584                         Sys_Printf( "WARNING: ParseEntity: EOF without closing brace\n"
1585                                                 "Continuing to process map, but resulting BSP may be invalid.\n" );
1586                         return qfalse;
1587                 }
1588
1589                 if ( !strcmp( token, "}" ) ) {
1590                         break;
1591                 }
1592
1593                 if ( !strcmp( token, "{" ) ) {
1594                         /* parse a brush or patch */
1595                         if ( !GetToken( qtrue ) ) {
1596                                 break;
1597                         }
1598
1599                         /* check */
1600                         if ( !strcmp( token, "patchDef2" ) ) {
1601                                 numMapPatches++;
1602                                 ParsePatch( onlyLights );
1603                         }
1604                         else if ( !strcmp( token, "terrainDef" ) ) {
1605                                 //% ParseTerrain();
1606                                 Sys_Printf( "WARNING: Terrain entity parsing not supported in this build.\n" ); /* ydnar */
1607                         }
1608                         else if ( !strcmp( token, "brushDef" ) ) {
1609                                 if ( g_bBrushPrimit == BPRIMIT_OLDBRUSHES ) {
1610                                         Error( "Old brush format not allowed in new brush format map" );
1611                                 }
1612                                 g_bBrushPrimit = BPRIMIT_NEWBRUSHES;
1613
1614                                 /* parse brush primitive */
1615                                 ParseBrush( onlyLights );
1616                         }
1617                         else
1618                         {
1619                                 if ( g_bBrushPrimit == BPRIMIT_NEWBRUSHES ) {
1620                                         Error( "New brush format not allowed in old brush format map" );
1621                                 }
1622                                 g_bBrushPrimit = BPRIMIT_OLDBRUSHES;
1623
1624                                 /* parse old brush format */
1625                                 UnGetToken();
1626                                 ParseBrush( onlyLights );
1627                         }
1628                         entitySourceBrushes++;
1629                 }
1630                 else
1631                 {
1632                         /* parse a key / value pair */
1633                         ep = ParseEPair();
1634
1635                         /* ydnar: 2002-07-06 fixed wolf bug with empty epairs */
1636                         if ( ep->key[ 0 ] != '\0' && ep->value[ 0 ] != '\0' ) {
1637                                 ep->next = mapEnt->epairs;
1638                                 mapEnt->epairs = ep;
1639                         }
1640                 }
1641         }
1642
1643         /* ydnar: get classname */
1644         classname = ValueForKey( mapEnt, "classname" );
1645
1646         /* ydnar: only lights? */
1647         if ( onlyLights && Q_strncasecmp( classname, "light", 5 ) ) {
1648                 numEntities--;
1649                 return qtrue;
1650         }
1651
1652         /* ydnar: determine if this is a func_group */
1653         if ( !Q_stricmp( "func_group", classname ) ) {
1654                 funcGroup = qtrue;
1655         }
1656         else{
1657                 funcGroup = qfalse;
1658         }
1659
1660         /* worldspawn (and func_groups) default to cast/recv shadows in worldspawn group */
1661         if ( funcGroup || mapEnt->mapEntityNum == 0 ) {
1662                 //%     Sys_Printf( "World:  %d\n", mapEnt->mapEntityNum );
1663                 castShadows = WORLDSPAWN_CAST_SHADOWS;
1664                 recvShadows = WORLDSPAWN_RECV_SHADOWS;
1665         }
1666
1667         /* other entities don't cast any shadows, but recv worldspawn shadows */
1668         else
1669         {
1670                 //%     Sys_Printf( "Entity: %d\n", mapEnt->mapEntityNum );
1671                 castShadows = ENTITY_CAST_SHADOWS;
1672                 recvShadows = ENTITY_RECV_SHADOWS;
1673         }
1674
1675         /* get explicit shadow flags */
1676         GetEntityShadowFlags( mapEnt, NULL, &castShadows, &recvShadows );
1677
1678         /* ydnar: get lightmap scaling value for this entity */
1679         if ( strcmp( "", ValueForKey( mapEnt, "lightmapscale" ) ) ||
1680                  strcmp( "", ValueForKey( mapEnt, "_lightmapscale" ) ) ) {
1681                 /* get lightmap scale from entity */
1682                 lightmapScale = FloatForKey( mapEnt, "lightmapscale" );
1683                 if ( lightmapScale <= 0.0f ) {
1684                         lightmapScale = FloatForKey( mapEnt, "_lightmapscale" );
1685                 }
1686                 if ( lightmapScale > 0.0f ) {
1687                         Sys_Printf( "Entity %d (%s) has lightmap scale of %.4f\n", mapEnt->mapEntityNum, classname, lightmapScale );
1688                 }
1689         }
1690         else{
1691                 lightmapScale = 0.0f;
1692         }
1693
1694         /* ydnar: get cel shader :) for this entity */
1695         value = ValueForKey( mapEnt, "_celshader" );
1696         if ( value[ 0 ] == '\0' ) {
1697                 value = ValueForKey( &entities[ 0 ], "_celshader" );
1698         }
1699         if ( value[ 0 ] != '\0' ) {
1700                 sprintf( shader, "textures/%s", value );
1701                 celShader = ShaderInfoForShader( shader );
1702                 Sys_Printf( "Entity %d (%s) has cel shader %s\n", mapEnt->mapEntityNum, classname, celShader->shader );
1703         }
1704         else{
1705                 celShader = NULL;
1706         }
1707
1708         /* attach stuff to everything in the entity */
1709         for ( brush = mapEnt->brushes; brush != NULL; brush = brush->next )
1710         {
1711                 brush->entityNum = mapEnt->mapEntityNum;
1712                 brush->castShadows = castShadows;
1713                 brush->recvShadows = recvShadows;
1714                 brush->lightmapScale = lightmapScale;
1715                 brush->celShader = celShader;
1716         }
1717
1718         for ( patch = mapEnt->patches; patch != NULL; patch = patch->next )
1719         {
1720                 patch->entityNum = mapEnt->mapEntityNum;
1721                 patch->castShadows = castShadows;
1722                 patch->recvShadows = recvShadows;
1723                 patch->lightmapScale = lightmapScale;
1724                 patch->celShader = celShader;
1725         }
1726
1727         /* ydnar: gs mods: set entity bounds */
1728         SetEntityBounds( mapEnt );
1729
1730         /* ydnar: gs mods: load shader index map (equivalent to old terrain alphamap) */
1731         LoadEntityIndexMap( mapEnt );
1732
1733         /* get entity origin and adjust brushes */
1734         GetVectorForKey( mapEnt, "origin", mapEnt->origin );
1735         if ( mapEnt->origin[ 0 ] || mapEnt->origin[ 1 ] || mapEnt->origin[ 2 ] ) {
1736                 AdjustBrushesForOrigin( mapEnt );
1737         }
1738
1739         /* group_info entities are just for editor grouping (fixme: leak!) */
1740         if ( !Q_stricmp( "group_info", classname ) ) {
1741                 numEntities--;
1742                 return qtrue;
1743         }
1744
1745         /* group entities are just for editor convenience, toss all brushes into worldspawn */
1746         if ( funcGroup ) {
1747                 MoveBrushesToWorld( mapEnt );
1748                 numEntities--;
1749                 return qtrue;
1750         }
1751
1752         /* done */
1753         return qtrue;
1754 }
1755
1756
1757
1758 /*
1759    LoadMapFile()
1760    loads a map file into a list of entities
1761  */
1762
1763 void LoadMapFile( char *filename, qboolean onlyLights ){
1764         FILE        *file;
1765         brush_t     *b;
1766         int oldNumEntities, numMapBrushes;
1767
1768
1769         /* note it */
1770         Sys_FPrintf( SYS_VRB, "--- LoadMapFile ---\n" );
1771         Sys_Printf( "Loading %s\n", filename );
1772
1773         /* hack */
1774         file = SafeOpenRead( filename );
1775         fclose( file );
1776
1777         /* load the map file */
1778         LoadScriptFile( filename, -1 );
1779
1780         /* setup */
1781         if ( onlyLights ) {
1782                 oldNumEntities = numEntities;
1783         }
1784         else{
1785                 numEntities = 0;
1786         }
1787
1788         /* initial setup */
1789         numMapDrawSurfs = 0;
1790         c_detail = 0;
1791         g_bBrushPrimit = BPRIMIT_UNDEFINED;
1792
1793         /* allocate a very large temporary brush for building the brushes as they are loaded */
1794         buildBrush = AllocBrush( MAX_BUILD_SIDES );
1795
1796         /* parse the map file */
1797         while ( ParseMapEntity( onlyLights ) ) ;
1798
1799         /* light loading */
1800         if ( onlyLights ) {
1801                 /* emit some statistics */
1802                 Sys_FPrintf( SYS_VRB, "%9d light entities\n", numEntities - oldNumEntities );
1803         }
1804         else
1805         {
1806                 /* set map bounds */
1807                 ClearBounds( mapMins, mapMaxs );
1808                 for ( b = entities[ 0 ].brushes; b; b = b->next )
1809                 {
1810                         AddPointToBounds( b->mins, mapMins, mapMaxs );
1811                         AddPointToBounds( b->maxs, mapMins, mapMaxs );
1812                 }
1813
1814                 /* get brush counts */
1815                 numMapBrushes = CountBrushList( entities[ 0 ].brushes );
1816                 if ( (float) c_detail / (float) numMapBrushes < 0.10f && numMapBrushes > 500 ) {
1817                         Sys_Printf( "WARNING: Over 90 percent structural map detected. Compile time may be adversely affected.\n" );
1818                 }
1819
1820                 /* emit some statistics */
1821                 Sys_FPrintf( SYS_VRB, "%9d total world brushes\n", numMapBrushes );
1822                 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_detail );
1823                 Sys_FPrintf( SYS_VRB, "%9d patches\n", numMapPatches );
1824                 Sys_FPrintf( SYS_VRB, "%9d boxbevels\n", c_boxbevels );
1825                 Sys_FPrintf( SYS_VRB, "%9d edgebevels\n", c_edgebevels );
1826                 Sys_FPrintf( SYS_VRB, "%9d entities\n", numEntities );
1827                 Sys_FPrintf( SYS_VRB, "%9d planes\n", nummapplanes );
1828                 Sys_Printf( "%9d areaportals\n", c_areaportals );
1829                 Sys_Printf( "Size: %5.0f, %5.0f, %5.0f to %5.0f, %5.0f, %5.0f\n",
1830                                         mapMins[ 0 ], mapMins[ 1 ], mapMins[ 2 ],
1831                                         mapMaxs[ 0 ], mapMaxs[ 1 ], mapMaxs[ 2 ] );
1832
1833                 /* write bogus map */
1834                 if ( fakemap ) {
1835                         WriteBSPBrushMap( "fakemap.map", entities[ 0 ].brushes );
1836                 }
1837         }
1838 }