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