tools/quake2/extra/qe4/brush.c

   1 /*
   2 ===========================================================================
   3 Copyright (C) 1997-2006 Id Software, Inc.
   4
   5 This file is part of Quake 2 Tools source code.
   6
   7 Quake 2 Tools source code is free software; you can redistribute it
   8 and/or modify it under the terms of the GNU General Public License as
   9 published by the Free Software Foundation; either version 2 of the License,
  10 or (at your option) any later version.
  11
  12 Quake 2 Tools source code is distributed in the hope that it will be
  13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Quake 2 Tools source code; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 ===========================================================================
  21 */
  22
  23 #include <assert.h>
  24 #include "qe3.h"
  25
  26 #define MAX_POINTS_ON_WINDING   64
  27
  28 face_t *Face_Alloc( void );
  29 void    Face_Free( face_t *f );
  30
  31 winding_t       *NewWinding (int points);
  32 void            FreeWinding (winding_t *w);
  33 winding_t       *Winding_Clone( winding_t *w );
  34 winding_t       *ClipWinding (winding_t *in, plane_t *split, qboolean keepon);
  35
  36 void PrintWinding (winding_t *w)
  37 {
  38         int             i;
  39
  40         printf ("-------------\n");
  41         for (i=0 ; i<w->numpoints ; i++)
  42                 printf ("(%5.2f, %5.2f, %5.2f)\n", w->points[i][0]
  43                 , w->points[i][1], w->points[i][2]);
  44 }
  45
  46 void PrintPlane (plane_t *p)
  47 {
  48     printf ("(%5.2f, %5.2f, %5.2f) : %5.2f\n",  p->normal[0],  p->normal[1],
  49     p->normal[2],  p->dist);
  50 }
  51
  52 void PrintVector (vec3_t v)
  53 {
  54      printf ("(%5.2f, %5.2f, %5.2f)\n",  v[0],  v[1], v[2]);
  55 }
  56
  57
  58 face_t  *Face_Clone (face_t *f)
  59 {
  60         face_t  *n;
  61
  62         n = Face_Alloc();
  63         n->texdef = f->texdef;
  64         memcpy (n->planepts, f->planepts, sizeof(n->planepts));
  65
  66         // all other fields are derived, and will be set by Brush_Build
  67         return n;
  68 }
  69
  70 //============================================================================
  71
  72 #define BOGUS_RANGE     18000
  73
  74
  75 /*
  76 ==================
  77 NewWinding
  78 ==================
  79 */
  80 winding_t *NewWinding (int points)
  81 {
  82         winding_t       *w;
  83         int                     size;
  84
  85         if (points > MAX_POINTS_ON_WINDING)
  86                 Error ("NewWinding: %i points", points);
  87
  88         size = (int)((winding_t *)0)->points[points];
  89         w = malloc (size);
  90         memset (w, 0, size);
  91         w->maxpoints = points;
  92
  93         return w;
  94 }
  95
  96
  97 void FreeWinding (winding_t *w)
  98 {
  99         free (w);
 100 }
 101
 102
 103 /*
 104 ==================
 105 Winding_Clone
 106 ==================
 107 */
 108 winding_t *Winding_Clone(winding_t *w)
 109 {
 110         int                     size;
 111         winding_t       *c;
 112
 113         size = (int)((winding_t *)0)->points[w->numpoints];
 114         c = qmalloc (size);
 115         memcpy (c, w, size);
 116         return c;
 117 }
 118
 119
 120 /*
 121 ==================
 122 ClipWinding
 123
 124 Clips the winding to the plane, returning the new winding on the positive side
 125 Frees the input winding.
 126 If keepon is true, an exactly on-plane winding will be saved, otherwise
 127 it will be clipped away.
 128 ==================
 129 */
 130 winding_t *ClipWinding (winding_t *in, plane_t *split, qboolean keepon)
 131 {
 132         vec_t   dists[MAX_POINTS_ON_WINDING];
 133         int             sides[MAX_POINTS_ON_WINDING];
 134         int             counts[3];
 135         vec_t   dot;
 136         int             i, j;
 137         vec_t   *p1, *p2;
 138         vec3_t  mid;
 139         winding_t       *neww;
 140         int             maxpts;
 141
 142         counts[0] = counts[1] = counts[2] = 0;
 143
 144 // determine sides for each point
 145         for (i=0 ; i<in->numpoints ; i++)
 146         {
 147                 dot = DotProduct (in->points[i], split->normal);
 148                 dot -= split->dist;
 149                 dists[i] = dot;
 150                 if (dot > ON_EPSILON)
 151                         sides[i] = SIDE_FRONT;
 152                 else if (dot < -ON_EPSILON)
 153                         sides[i] = SIDE_BACK;
 154                 else
 155                 {
 156                         sides[i] = SIDE_ON;
 157                 }
 158                 counts[sides[i]]++;
 159         }
 160         sides[i] = sides[0];
 161         dists[i] = dists[0];
 162
 163         if (keepon && !counts[0] && !counts[1])
 164                 return in;
 165
 166         if (!counts[0])
 167         {
 168                 FreeWinding (in);
 169                 return NULL;
 170         }
 171         if (!counts[1])
 172                 return in;
 173
 174         maxpts = in->numpoints+4;       // can't use counts[0]+2 because
 175                                                                 // of fp grouping errors
 176         neww = NewWinding (maxpts);
 177
 178         for (i=0 ; i<in->numpoints ; i++)
 179         {
 180                 p1 = in->points[i];
 181
 182                 if (sides[i] == SIDE_ON)
 183                 {
 184                         VectorCopy (p1, neww->points[neww->numpoints]);
 185                         neww->numpoints++;
 186                         continue;
 187                 }
 188
 189                 if (sides[i] == SIDE_FRONT)
 190                 {
 191                         VectorCopy (p1, neww->points[neww->numpoints]);
 192                         neww->numpoints++;
 193                 }
 194
 195                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
 196                         continue;
 197
 198         // generate a split point
 199                 p2 = in->points[(i+1)%in->numpoints];
 200
 201                 dot = dists[i] / (dists[i]-dists[i+1]);
 202                 for (j=0 ; j<3 ; j++)
 203                 {       // avoid round off error when possible
 204                         if (split->normal[j] == 1)
 205                                 mid[j] = split->dist;
 206                         else if (split->normal[j] == -1)
 207                                 mid[j] = -split->dist;
 208                         else
 209                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
 210                 }
 211
 212                 VectorCopy (mid, neww->points[neww->numpoints]);
 213                 neww->numpoints++;
 214         }
 215
 216         if (neww->numpoints > maxpts)
 217                 Error ("ClipWinding: points exceeded estimate");
 218
 219 // free the original winding
 220         FreeWinding (in);
 221
 222         return neww;
 223 }
 224
 225
 226
 227 /*
 228 =============================================================================
 229
 230                         TEXTURE COORDINATES
 231
 232 =============================================================================
 233 */
 234
 235
 236 /*
 237 ==================
 238 textureAxisFromPlane
 239 ==================
 240 */
 241 vec3_t  baseaxis[18] =
 242 {
 243 {0,0,1}, {1,0,0}, {0,-1,0},                     // floor
 244 {0,0,-1}, {1,0,0}, {0,-1,0},            // ceiling
 245 {1,0,0}, {0,1,0}, {0,0,-1},                     // west wall
 246 {-1,0,0}, {0,1,0}, {0,0,-1},            // east wall
 247 {0,1,0}, {1,0,0}, {0,0,-1},                     // south wall
 248 {0,-1,0}, {1,0,0}, {0,0,-1}                     // north wall
 249 };
 250
 251 void TextureAxisFromPlane(plane_t *pln, vec3_t xv, vec3_t yv)
 252 {
 253         int             bestaxis;
 254         float   dot,best;
 255         int             i;
 256
 257         best = 0;
 258         bestaxis = 0;
 259
 260         for (i=0 ; i<6 ; i++)
 261         {
 262                 dot = DotProduct (pln->normal, baseaxis[i*3]);
 263                 if (dot > best)
 264                 {
 265                         best = dot;
 266                         bestaxis = i;
 267                 }
 268         }
 269
 270         VectorCopy (baseaxis[bestaxis*3+1], xv);
 271         VectorCopy (baseaxis[bestaxis*3+2], yv);
 272 }
 273
 274
 275 float   lightaxis[3] = {0.6, 0.8, 1.0};
 276 /*
 277 ================
 278 SetShadeForPlane
 279
 280 Light different planes differently to
 281 improve recognition
 282 ================
 283 */
 284 float SetShadeForPlane (plane_t *p)
 285 {
 286         int             i;
 287         float   f;
 288
 289         // axial plane
 290         for (i=0 ; i<3 ; i++)
 291                 if (fabs(p->normal[i]) > 0.9)
 292                 {
 293                         f = lightaxis[i];
 294                         return f;
 295                 }
 296
 297         // between two axial planes
 298         for (i=0 ; i<3 ; i++)
 299                 if (fabs(p->normal[i]) < 0.1)
 300                 {
 301                         f = (lightaxis[(i+1)%3] + lightaxis[(i+2)%3])/2;
 302                         return f;
 303                 }
 304
 305         // other
 306         f= (lightaxis[0] + lightaxis[1] + lightaxis[2]) / 3;
 307         return f;
 308 }
 309
 310 vec3_t  vecs[2];
 311 float   shift[2];
 312
 313 /*
 314 ================
 315 BeginTexturingFace
 316 ================
 317 */
 318 void BeginTexturingFace (brush_t *b, face_t *f, qtexture_t *q)
 319 {
 320         vec3_t  pvecs[2];
 321         int             sv, tv;
 322         float   ang, sinv, cosv;
 323         float   ns, nt;
 324         int             i,j;
 325         float   shade;
 326
 327         // get natural texture axis
 328         TextureAxisFromPlane(&f->plane, pvecs[0], pvecs[1]);
 329
 330         // set shading for face
 331         shade = SetShadeForPlane (&f->plane);
 332         if (camera.draw_mode == cd_texture && !b->owner->eclass->fixedsize)
 333         {
 334                 f->d_color[0] =
 335                 f->d_color[1] =
 336                 f->d_color[2] = shade;
 337         }
 338         else
 339         {
 340                 f->d_color[0] = shade*q->color[0];
 341                 f->d_color[1] = shade*q->color[1];
 342                 f->d_color[2] = shade*q->color[2];
 343         }
 344
 345         if (camera.draw_mode != cd_texture)
 346                 return;
 347
 348         if (!f->texdef.scale[0])
 349                 f->texdef.scale[0] = 1;
 350         if (!f->texdef.scale[1])
 351                 f->texdef.scale[1] = 1;
 352
 353
 354 // rotate axis
 355         if (f->texdef.rotate == 0)
 356                 { sinv = 0 ; cosv = 1; }
 357         else if (f->texdef.rotate == 90)
 358                 { sinv = 1 ; cosv = 0; }
 359         else if (f->texdef.rotate == 180)
 360                 { sinv = 0 ; cosv = -1; }
 361         else if (f->texdef.rotate == 270)
 362                 { sinv = -1 ; cosv = 0; }
 363         else
 364         {
 365                 ang = f->texdef.rotate / 180 * Q_PI;
 366                 sinv = sin(ang);
 367                 cosv = cos(ang);
 368         }
 369
 370         if (pvecs[0][0])
 371                 sv = 0;
 372         else if (pvecs[0][1])
 373                 sv = 1;
 374         else
 375                 sv = 2;
 376
 377         if (pvecs[1][0])
 378                 tv = 0;
 379         else if (pvecs[1][1])
 380                 tv = 1;
 381         else
 382                 tv = 2;
 383
 384         for (i=0 ; i<2 ; i++)
 385         {
 386                 ns = cosv * pvecs[i][sv] - sinv * pvecs[i][tv];
 387                 nt = sinv * pvecs[i][sv] +  cosv * pvecs[i][tv];
 388                 vecs[i][sv] = ns;
 389                 vecs[i][tv] = nt;
 390         }
 391
 392         for (i=0 ; i<2 ; i++)
 393                 for (j=0 ; j<3 ; j++)
 394                         vecs[i][j] = vecs[i][j] / f->texdef.scale[i];
 395 }
 396
 397
 398 void _EmitTextureCoordinates (vec3_t v, qtexture_t *q)
 399 {
 400         float   s, t;
 401
 402         s = DotProduct (v, vecs[0]);
 403         t = DotProduct (v, vecs[1]);
 404
 405         s += shift[0];
 406         t += shift[1];
 407
 408         s /= q->width;
 409         t /= q->height;
 410
 411         glTexCoord2f (s, t);
 412 }
 413
 414 void EmitTextureCoordinates ( float *xyzst, qtexture_t *q, face_t *f)
 415 {
 416         float   s, t, ns, nt;
 417         float   ang, sinv, cosv;
 418         vec3_t  vecs[2];
 419         texdef_t        *td;
 420
 421         // get natural texture axis
 422         TextureAxisFromPlane(&f->plane, vecs[0], vecs[1]);
 423
 424         td = &f->texdef;
 425
 426         ang = td->rotate / 180 * Q_PI;
 427         sinv = sin(ang);
 428         cosv = cos(ang);
 429
 430         if (!td->scale[0])
 431                 td->scale[0] = 1;
 432         if (!td->scale[1])
 433                 td->scale[1] = 1;
 434
 435         s = DotProduct(xyzst, vecs[0]);
 436         t = DotProduct(xyzst, vecs[1]);
 437
 438         ns = cosv * s - sinv * t;
 439         nt = sinv * s +  cosv * t;
 440
 441         s = ns/td->scale[0] + td->shift[0];
 442         t = nt/td->scale[1] + td->shift[1];
 443
 444         // gl scales everything from 0 to 1
 445         s /= q->width;
 446         t /= q->height;
 447
 448         xyzst[3] = s;
 449         xyzst[4] = t;
 450 }
 451
 452 //==========================================================================
 453
 454
 455 /*
 456 =================
 457 BasePolyForPlane
 458 =================
 459 */
 460 winding_t *BasePolyForPlane (plane_t *p)
 461 {
 462         int             i, x;
 463         vec_t   max, v;
 464         vec3_t  org, vright, vup;
 465         winding_t       *w;
 466
 467 // find the major axis
 468
 469         max = -BOGUS_RANGE;
 470         x = -1;
 471         for (i=0 ; i<3; i++)
 472         {
 473                 v = fabs(p->normal[i]);
 474                 if (v > max)
 475                 {
 476                         x = i;
 477                         max = v;
 478                 }
 479         }
 480         if (x==-1)
 481                 Error ("BasePolyForPlane: no axis found");
 482
 483         VectorCopy (vec3_origin, vup);
 484         switch (x)
 485         {
 486         case 0:
 487         case 1:
 488                 vup[2] = 1;
 489                 break;
 490         case 2:
 491                 vup[0] = 1;
 492                 break;
 493         }
 494
 495
 496         v = DotProduct (vup, p->normal);
 497         VectorMA (vup, -v, p->normal, vup);
 498         VectorNormalize (vup);
 499
 500         VectorScale (p->normal, p->dist, org);
 501
 502         CrossProduct (vup, p->normal, vright);
 503
 504         VectorScale (vup, 8192, vup);
 505         VectorScale (vright, 8192, vright);
 506
 507 // project a really big axis aligned box onto the plane
 508         w = NewWinding (4);
 509
 510         VectorSubtract (org, vright, w->points[0]);
 511         VectorAdd (w->points[0], vup, w->points[0]);
 512
 513         VectorAdd (org, vright, w->points[1]);
 514         VectorAdd (w->points[1], vup, w->points[1]);
 515
 516         VectorAdd (org, vright, w->points[2]);
 517         VectorSubtract (w->points[2], vup, w->points[2]);
 518
 519         VectorSubtract (org, vright, w->points[3]);
 520         VectorSubtract (w->points[3], vup, w->points[3]);
 521
 522         w->numpoints = 4;
 523
 524         return w;
 525 }
 526
 527 void Brush_MakeFacePlanes (brush_t *b)
 528 {
 529         face_t  *f;
 530         int             j;
 531         vec3_t  t1, t2, t3;
 532
 533         for (f=b->brush_faces ; f ; f=f->next)
 534         {
 535         // convert to a vector / dist plane
 536                 for (j=0 ; j<3 ; j++)
 537                 {
 538                         t1[j] = f->planepts[0][j] - f->planepts[1][j];
 539                         t2[j] = f->planepts[2][j] - f->planepts[1][j];
 540                         t3[j] = f->planepts[1][j];
 541                 }
 542
 543                 CrossProduct(t1,t2, f->plane.normal);
 544                 if (VectorCompare (f->plane.normal, vec3_origin))
 545                         printf ("WARNING: brush plane with no normal\n");
 546                 VectorNormalize (f->plane.normal);
 547                 f->plane.dist = DotProduct (t3, f->plane.normal);
 548         }
 549 }
 550
 551 void DrawBrushEntityName (brush_t *b)
 552 {
 553         char    *name;
 554         float   a, s, c;
 555         vec3_t  mid;
 556         int             i;
 557
 558         if (!b->owner)
 559                 return;         // during contruction
 560
 561         if (b->owner == world_entity)
 562                 return;
 563
 564         if (b != b->owner->brushes.onext)
 565                 return; // not key brush
 566
 567         // draw the angle pointer
 568         a = FloatForKey (b->owner, "angle");
 569         if (a)
 570         {
 571                 s = sin (a/180*Q_PI);
 572                 c = cos (a/180*Q_PI);
 573                 for (i=0 ; i<3 ; i++)
 574                         mid[i] = (b->mins[i] + b->maxs[i])*0.5;
 575
 576                 glBegin (GL_LINE_STRIP);
 577                 glVertex3fv (mid);
 578                 mid[0] += c*8;
 579                 mid[1] += s*8;
 580                 glVertex3fv (mid);
 581                 mid[0] -= c*4;
 582                 mid[1] -= s*4;
 583                 mid[0] -= s*4;
 584                 mid[1] += c*4;
 585                 glVertex3fv (mid);
 586                 mid[0] += c*4;
 587                 mid[1] += s*4;
 588                 mid[0] += s*4;
 589                 mid[1] -= c*4;
 590                 glVertex3fv (mid);
 591                 mid[0] -= c*4;
 592                 mid[1] -= s*4;
 593                 mid[0] += s*4;
 594                 mid[1] -= c*4;
 595                 glVertex3fv (mid);
 596                 glEnd ();
 597         }
 598
 599         if (!g_qeglobals.d_savedinfo.show_names)
 600                 return;
 601
 602         name = ValueForKey (b->owner, "classname");
 603         glRasterPos2f (b->mins[0]+4, b->mins[1]+4);
 604         glCallLists (strlen(name), GL_UNSIGNED_BYTE, name);
 605 }
 606
 607 /*
 608 =================
 609 MakeFaceWinding
 610
 611 returns the visible polygon on a face
 612 =================
 613 */
 614 winding_t       *MakeFaceWinding (brush_t *b, face_t *face)
 615 {
 616         winding_t       *w;
 617         face_t          *clip;
 618         plane_t                 plane;
 619         qboolean                past;
 620
 621         // get a poly that covers an effectively infinite area
 622         w = BasePolyForPlane (&face->plane);
 623
 624         // chop the poly by all of the other faces
 625         past = false;
 626         for (clip = b->brush_faces ; clip && w ; clip=clip->next)
 627         {
 628                 if (clip == face)
 629                 {
 630                         past = true;
 631                         continue;
 632                 }
 633                 if (DotProduct (face->plane.normal, clip->plane.normal) > 0.999
 634                         && fabs(face->plane.dist - clip->plane.dist) < 0.01 )
 635                 {       // identical plane, use the later one
 636                         if (past)
 637                         {
 638                                 free (w);
 639                                 return NULL;
 640                         }
 641                         continue;
 642                 }
 643
 644                 // flip the plane, because we want to keep the back side
 645                 VectorSubtract (vec3_origin,clip->plane.normal, plane.normal);
 646                 plane.dist = -clip->plane.dist;
 647
 648                 w = ClipWinding (w, &plane, false);
 649                 if (!w)
 650                         return w;
 651         }
 652
 653         if (w->numpoints < 3)
 654         {
 655                 free(w);
 656                 w = NULL;
 657         }
 658
 659         if (!w)
 660                 printf ("unused plane\n");
 661
 662         return w;
 663 }
 664
 665
 666 void Brush_SnapPlanepts (brush_t *b)
 667 {
 668         int             i, j;
 669         face_t  *f;
 670
 671         for (f=b->brush_faces ; f; f=f->next)
 672                 for (i=0 ; i<3 ; i++)
 673                         for (j=0 ; j<3 ; j++)
 674                                 f->planepts[i][j] = floor (f->planepts[i][j] + 0.5);
 675 }
 676
 677 /*
 678 ** Brush_Build
 679 **
 680 ** Builds a brush rendering data and also sets the min/max bounds
 681 */
 682 #define ZERO_EPSILON    0.001
 683 void Brush_Build( brush_t *b )
 684 {
 685 //      int                             order;
 686 //      face_t                  *face;
 687 //      winding_t               *w;
 688         char                    title[1024];
 689
 690         if (modified != 1)
 691         {
 692                 modified = true;        // mark the map as changed
 693                 sprintf (title, "%s *", currentmap);
 694
 695                 QE_ConvertDOSToUnixName( title, title );
 696                 Sys_SetTitle (title);
 697         }
 698
 699         /*
 700         ** build the windings and generate the bounding box
 701         */
 702         Brush_BuildWindings( b );
 703
 704         /*
 705         ** move the points and edges if in select mode
 706         */
 707         if (g_qeglobals.d_select_mode == sel_vertex || g_qeglobals.d_select_mode == sel_edge)
 708                 SetupVertexSelection ();
 709 }
 710
 711 /*
 712 =================
 713 Brush_Parse
 714
 715 The brush is NOT linked to any list
 716 =================
 717 */
 718 brush_t *Brush_Parse (void)
 719 {
 720         brush_t         *b;
 721         face_t          *f;
 722         int                     i,j;
 723
 724         g_qeglobals.d_parsed_brushes++;
 725         b = qmalloc(sizeof(brush_t));
 726
 727         do
 728         {
 729                 if (!GetToken (true))
 730                         break;
 731                 if (!strcmp (token, "}") )
 732                         break;
 733
 734                 f = Face_Alloc();
 735
 736                 // add the brush to the end of the chain, so
 737                 // loading and saving a map doesn't reverse the order
 738
 739                 f->next = NULL;
 740                 if (!b->brush_faces)
 741                 {
 742                         b->brush_faces = f;
 743                 }
 744                 else
 745                 {
 746                         face_t *scan;
 747
 748                         for (scan=b->brush_faces ; scan->next ; scan=scan->next)
 749                                 ;
 750                         scan->next = f;
 751                 }
 752
 753                 // read the three point plane definition
 754                 for (i=0 ; i<3 ; i++)
 755                 {
 756                         if (i != 0)
 757                                 GetToken (true);
 758                         if (strcmp (token, "(") )
 759                                 Error ("parsing brush");
 760
 761                         for (j=0 ; j<3 ; j++)
 762                         {
 763                                 GetToken (false);
 764                                 f->planepts[i][j] = atoi(token);
 765                         }
 766
 767                         GetToken (false);
 768                         if (strcmp (token, ")") )
 769                                 Error ("parsing brush");
 770
 771                 }
 772
 773         // read the texturedef
 774                 GetToken (false);
 775                 strcpy(f->texdef.name, token);
 776                 GetToken (false);
 777                 f->texdef.shift[0] = atoi(token);
 778                 GetToken (false);
 779                 f->texdef.shift[1] = atoi(token);
 780                 GetToken (false);
 781                 f->texdef.rotate = atoi(token);
 782                 GetToken (false);
 783                 f->texdef.scale[0] = atof(token);
 784                 GetToken (false);
 785                 f->texdef.scale[1] = atof(token);
 786
 787                 // the flags and value field aren't necessarily present
 788                 f->d_texture = Texture_ForName( f->texdef.name );
 789                 f->texdef.flags = f->d_texture->flags;
 790                 f->texdef.value = f->d_texture->value;
 791                 f->texdef.contents = f->d_texture->contents;
 792
 793                 if (TokenAvailable ())
 794                 {
 795                         GetToken (false);
 796                         f->texdef.contents = atoi(token);
 797                         GetToken (false);
 798                         f->texdef.flags = atoi(token);
 799                         GetToken (false);
 800                         f->texdef.value = atoi(token);
 801                 }
 802         } while (1);
 803
 804         return b;
 805 }
 806
 807 /*
 808 =================
 809 Brush_Write
 810 =================
 811 */
 812 void Brush_Write (brush_t *b, FILE *f)
 813 {
 814         face_t  *fa;
 815         char *pname;
 816         int             i;
 817
 818         fprintf (f, "{\n");
 819         for (fa=b->brush_faces ; fa ; fa=fa->next)
 820         {
 821                 for (i=0 ; i<3 ; i++)
 822                         fprintf (f, "( %i %i %i ) ", (int)fa->planepts[i][0]
 823                         , (int)fa->planepts[i][1], (int)fa->planepts[i][2]);
 824
 825                 pname = fa->texdef.name;
 826                 if (pname[0] == 0)
 827                         pname = "unnamed";
 828
 829                 fprintf (f, "%s %i %i %i ", pname,
 830                         (int)fa->texdef.shift[0], (int)fa->texdef.shift[1],
 831                         (int)fa->texdef.rotate);
 832
 833                 if (fa->texdef.scale[0] == (int)fa->texdef.scale[0])
 834                         fprintf (f, "%i ", (int)fa->texdef.scale[0]);
 835                 else
 836                         fprintf (f, "%f ", (float)fa->texdef.scale[0]);
 837                 if (fa->texdef.scale[1] == (int)fa->texdef.scale[1])
 838                         fprintf (f, "%i", (int)fa->texdef.scale[1]);
 839                 else
 840                         fprintf (f, "%f", (float)fa->texdef.scale[1]);
 841
 842                 // only output flags and value if not default
 843                 if (fa->texdef.value != fa->d_texture->value
 844                         || fa->texdef.flags != fa->d_texture->flags
 845                         || fa->texdef.contents != fa->d_texture->contents)
 846                 {
 847                         fprintf (f, " %i %i %i", fa->texdef.contents, fa->texdef.flags, fa->texdef.value);
 848                 }
 849
 850                 fprintf (f, "\n");
 851         }
 852         fprintf (f, "}\n");
 853 }
 854
 855
 856 /*
 857 =============
 858 Brush_Create
 859
 860 Create non-textured blocks for entities
 861 The brush is NOT linked to any list
 862 =============
 863 */
 864 brush_t *Brush_Create (vec3_t mins, vec3_t maxs, texdef_t *texdef)
 865 {
 866         int             i, j;
 867         vec3_t  pts[4][2];
 868         face_t  *f;
 869         brush_t *b;
 870
 871         for (i=0 ; i<3 ; i++)
 872                 if (maxs[i] < mins[i])
 873                         Error ("Brush_InitSolid: backwards");
 874
 875         b = qmalloc (sizeof(brush_t));
 876
 877         pts[0][0][0] = mins[0];
 878         pts[0][0][1] = mins[1];
 879
 880         pts[1][0][0] = mins[0];
 881         pts[1][0][1] = maxs[1];
 882
 883         pts[2][0][0] = maxs[0];
 884         pts[2][0][1] = maxs[1];
 885
 886         pts[3][0][0] = maxs[0];
 887         pts[3][0][1] = mins[1];
 888
 889         for (i=0 ; i<4 ; i++)
 890         {
 891                 pts[i][0][2] = mins[2];
 892                 pts[i][1][0] = pts[i][0][0];
 893                 pts[i][1][1] = pts[i][0][1];
 894                 pts[i][1][2] = maxs[2];
 895         }
 896
 897         for (i=0 ; i<4 ; i++)
 898         {
 899                 f = Face_Alloc();
 900                 f->texdef = *texdef;
 901                 f->next = b->brush_faces;
 902                 b->brush_faces = f;
 903                 j = (i+1)%4;
 904
 905                 VectorCopy (pts[j][1], f->planepts[0]);
 906                 VectorCopy (pts[i][1], f->planepts[1]);
 907                 VectorCopy (pts[i][0], f->planepts[2]);
 908         }
 909
 910         f = Face_Alloc();
 911         f->texdef = *texdef;
 912         f->next = b->brush_faces;
 913         b->brush_faces = f;
 914
 915         VectorCopy (pts[0][1], f->planepts[0]);
 916         VectorCopy (pts[1][1], f->planepts[1]);
 917         VectorCopy (pts[2][1], f->planepts[2]);
 918
 919         f = Face_Alloc();
 920         f->texdef = *texdef;
 921         f->next = b->brush_faces;
 922         b->brush_faces = f;
 923
 924         VectorCopy (pts[2][0], f->planepts[0]);
 925         VectorCopy (pts[1][0], f->planepts[1]);
 926         VectorCopy (pts[0][0], f->planepts[2]);
 927
 928         return b;
 929 }
 930
 931
 932 /*
 933 =============
 934 Brush_MakeSided
 935
 936 Makes the current brushhave the given number of 2d sides
 937 =============
 938 */
 939 void Brush_MakeSided (int sides)
 940 {
 941         int             i;
 942         vec3_t  mins, maxs;
 943         brush_t *b;
 944         texdef_t        *texdef;
 945         face_t  *f;
 946         vec3_t  mid;
 947         float   width;
 948         float   sv, cv;
 949
 950         if (sides < 3)
 951         {
 952                 Sys_Status ("Bad sides number", 0);
 953                 return;
 954         }
 955
 956         if (!QE_SingleBrush ())
 957         {
 958                 Sys_Status ("Must have a single brush selected", 0 );
 959                 return;
 960         }
 961
 962         b = selected_brushes.next;
 963         VectorCopy (b->mins, mins);
 964         VectorCopy (b->maxs, maxs);
 965         texdef = &g_qeglobals.d_texturewin.texdef;
 966
 967         Brush_Free (b);
 968
 969         // find center of brush
 970         width = 8;
 971         for (i=0 ; i<2 ; i++)
 972         {
 973                 mid[i] = (maxs[i] + mins[i])*0.5;
 974                 if (maxs[i] - mins[i] > width)
 975                         width = maxs[i] - mins[i];
 976         }
 977         width /= 2;
 978
 979         b = qmalloc (sizeof(brush_t));
 980
 981         // create top face
 982         f = Face_Alloc();
 983         f->texdef = *texdef;
 984         f->next = b->brush_faces;
 985         b->brush_faces = f;
 986
 987 f->planepts[2][0] = mins[0];f->planepts[2][1] = mins[1];f->planepts[2][2] = maxs[2];
 988 f->planepts[1][0] = maxs[0];f->planepts[1][1] = mins[1];f->planepts[1][2] = maxs[2];
 989 f->planepts[0][0] = maxs[0];f->planepts[0][1] = maxs[1];f->planepts[0][2] = maxs[2];
 990
 991         // create bottom face
 992         f = Face_Alloc();
 993         f->texdef = *texdef;
 994         f->next = b->brush_faces;
 995         b->brush_faces = f;
 996
 997 f->planepts[0][0] = mins[0];f->planepts[0][1] = mins[1];f->planepts[0][2] = mins[2];
 998 f->planepts[1][0] = maxs[0];f->planepts[1][1] = mins[1];f->planepts[1][2] = mins[2];
 999 f->planepts[2][0] = maxs[0];f->planepts[2][1] = maxs[1];f->planepts[2][2] = mins[2];
1000
1001         for (i=0 ; i<sides ; i++)
1002         {
1003                 f = Face_Alloc();
1004                 f->texdef = *texdef;
1005                 f->next = b->brush_faces;
1006                 b->brush_faces = f;
1007
1008                 sv = sin (i*3.14159265*2/sides);
1009                 cv = cos (i*3.14159265*2/sides);
1010
1011                 f->planepts[0][0] = floor(mid[0]+width*cv+0.5);
1012                 f->planepts[0][1] = floor(mid[1]+width*sv+0.5);
1013                 f->planepts[0][2] = mins[2];
1014
1015                 f->planepts[1][0] = f->planepts[0][0];
1016                 f->planepts[1][1] = f->planepts[0][1];
1017                 f->planepts[1][2] = maxs[2];
1018
1019                 f->planepts[2][0] = floor(f->planepts[0][0] - width*sv + 0.5);
1020                 f->planepts[2][1] = floor(f->planepts[0][1] + width*cv + 0.5);
1021                 f->planepts[2][2] = maxs[2];
1022
1023         }
1024
1025         Brush_AddToList (b, &selected_brushes);
1026
1027         Entity_LinkBrush (world_entity, b);
1028
1029         Brush_Build( b );
1030
1031         Sys_UpdateWindows (W_ALL);
1032 }
1033
1034
1035 /*
1036 =============
1037 Brush_Free
1038
1039 Frees the brush with all of its faces and display list.
1040 Unlinks the brush from whichever chain it is in.
1041 Decrements the owner entity's brushcount.
1042 Removes owner entity if this was the last brush
1043 unless owner is the world.
1044 =============
1045 */
1046 void Brush_Free (brush_t *b)
1047 {
1048         face_t  *f, *next;
1049
1050         // free faces
1051         for (f=b->brush_faces ; f ; f=next)
1052         {
1053                 next = f->next;
1054                 Face_Free( f );
1055         }
1056
1057         /*
1058         for ( i = 0; i < b->d_numwindings; i++ )
1059         {
1060                 if ( b->d_windings[i] )
1061                 {
1062                         FreeWinding( b->d_windings[i] );
1063                         b->d_windings[i] = 0;
1064                 }
1065         }
1066         */
1067
1068         // unlink from active/selected list
1069         if (b->next)
1070                 Brush_RemoveFromList (b);
1071
1072         // unlink from entity list
1073         if (b->onext)
1074                 Entity_UnlinkBrush (b);
1075
1076         free (b);
1077 }
1078
1079 /*
1080 ============
1081 Brush_Move
1082 ============
1083 */
1084 void Brush_Move (brush_t *b, vec3_t move)
1085 {
1086         int             i;
1087         face_t  *f;
1088
1089         for (f=b->brush_faces ; f ; f=f->next)
1090                 for (i=0 ; i<3 ; i++)
1091                         VectorAdd (f->planepts[i], move, f->planepts[i]);
1092         Brush_Build( b );
1093 }
1094
1095 /*
1096 ============
1097 Brush_Clone
1098
1099 Does NOT add the new brush to any lists
1100 ============
1101 */
1102 brush_t *Brush_Clone (brush_t *b)
1103 {
1104         brush_t *n;
1105         face_t  *f, *nf;
1106
1107         n = qmalloc(sizeof(brush_t));
1108         n->owner = b->owner;
1109         for (f=b->brush_faces ; f ; f=f->next)
1110         {
1111                 nf = Face_Clone( f );
1112                 nf->next = n->brush_faces;
1113                 n->brush_faces = nf;
1114         }
1115         return n;
1116 }
1117
1118 /*
1119 ==============
1120 Brush_Ray
1121
1122 Itersects a ray with a brush
1123 Returns the face hit and the distance along the ray the intersection occured at
1124 Returns NULL and 0 if not hit at all
1125 ==============
1126 */
1127 face_t *Brush_Ray (vec3_t origin, vec3_t dir, brush_t *b, float *dist)
1128 {
1129         face_t  *f, *firstface;
1130         vec3_t  p1, p2;
1131         float   frac, d1, d2;
1132         int             i;
1133
1134         VectorCopy (origin, p1);
1135         for (i=0 ; i<3 ; i++)
1136                 p2[i] = p1[i] + dir[i]*16384;
1137
1138         for (f=b->brush_faces ; f ; f=f->next)
1139         {
1140                 d1 = DotProduct (p1, f->plane.normal) - f->plane.dist;
1141                 d2 = DotProduct (p2, f->plane.normal) - f->plane.dist;
1142                 if (d1 >= 0 && d2 >= 0)
1143                 {
1144                         *dist = 0;
1145                         return NULL;    // ray is on front side of face
1146                 }
1147                 if (d1 <=0 && d2 <= 0)
1148                         continue;
1149         // clip the ray to the plane
1150                 frac = d1 / (d1 - d2);
1151                 if (d1 > 0)
1152                 {
1153                         firstface = f;
1154                         for (i=0 ; i<3 ; i++)
1155                                 p1[i] = p1[i] + frac *(p2[i] - p1[i]);
1156                 }
1157                 else
1158                 {
1159                         for (i=0 ; i<3 ; i++)
1160                                 p2[i] = p1[i] + frac *(p2[i] - p1[i]);
1161                 }
1162         }
1163
1164         // find distance p1 is along dir
1165         VectorSubtract (p1, origin, p1);
1166         d1 = DotProduct (p1, dir);
1167
1168         *dist = d1;
1169
1170         return firstface;
1171 }
1172
1173 void    Brush_AddToList (brush_t *b, brush_t *list)
1174 {
1175         if (b->next || b->prev)
1176                 Error ("Brush_RemoveFromList: allready linked");
1177         b->next = list->next;
1178         list->next->prev = b;
1179         list->next = b;
1180         b->prev = list;
1181 }
1182
1183 void    Brush_RemoveFromList (brush_t *b)
1184 {
1185         if (!b->next || !b->prev)
1186                 Error ("Brush_RemoveFromList: not linked");
1187         b->next->prev = b->prev;
1188         b->prev->next = b->next;
1189         b->next = b->prev = NULL;
1190 }
1191
1192 void    Brush_SetTexture (brush_t *b, texdef_t *texdef)
1193 {
1194         face_t  *f;
1195
1196         for (f=b->brush_faces ; f ; f=f->next)
1197                 f->texdef = *texdef;
1198         Brush_Build( b );
1199 }
1200
1201
1202 qboolean ClipLineToFace (vec3_t p1, vec3_t p2, face_t *f)
1203 {
1204         float   d1, d2, fr;
1205         int             i;
1206         float   *v;
1207
1208         d1 = DotProduct (p1, f->plane.normal) - f->plane.dist;
1209         d2 = DotProduct (p2, f->plane.normal) - f->plane.dist;
1210
1211         if (d1 >= 0 && d2 >= 0)
1212                 return false;           // totally outside
1213         if (d1 <= 0 && d2 <= 0)
1214                 return true;            // totally inside
1215
1216         fr = d1 / (d1 - d2);
1217
1218         if (d1 > 0)
1219                 v = p1;
1220         else
1221                 v = p2;
1222
1223         for (i=0 ; i<3 ; i++)
1224                 v[i] = p1[i] + fr*(p2[i] - p1[i]);
1225
1226         return true;
1227 }
1228
1229
1230 int AddPlanept (float *f)
1231 {
1232         int             i;
1233
1234         for (i=0 ; i<g_qeglobals.d_num_move_points ; i++)
1235                 if (g_qeglobals.d_move_points[i] == f)
1236                         return 0;
1237         g_qeglobals.d_move_points[g_qeglobals.d_num_move_points++] = f;
1238         return 1;
1239 }
1240
1241 /*
1242 ==============
1243 Brush_SelectFaceForDragging
1244
1245 Adds the faces planepts to move_points, and
1246 rotates and adds the planepts of adjacent face if shear is set
1247 ==============
1248 */
1249 void Brush_SelectFaceForDragging (brush_t *b, face_t *f, qboolean shear)
1250 {
1251         int             i;
1252         face_t  *f2;
1253         winding_t       *w;
1254         float   d;
1255         brush_t *b2;
1256         int             c;
1257
1258         if (b->owner->eclass->fixedsize)
1259                 return;
1260
1261         c = 0;
1262         for (i=0 ; i<3 ; i++)
1263                 c += AddPlanept (f->planepts[i]);
1264         if (c == 0)
1265                 return;         // allready completely added
1266
1267         // select all points on this plane in all brushes the selection
1268         for (b2=selected_brushes.next ; b2 != &selected_brushes ; b2 = b2->next)
1269         {
1270                 if (b2 == b)
1271                         continue;
1272                 for (f2=b2->brush_faces ; f2 ; f2=f2->next)
1273                 {
1274                         for (i=0 ; i<3 ; i++)
1275                                 if (fabs(DotProduct(f2->planepts[i], f->plane.normal)
1276                                 -f->plane.dist) > ON_EPSILON)
1277                                         break;
1278                         if (i==3)
1279                         {       // move this face as well
1280                                 Brush_SelectFaceForDragging (b2, f2, shear);
1281                                 break;
1282                         }
1283                 }
1284         }
1285
1286
1287         // if shearing, take all the planes adjacent to
1288         // selected faces and rotate their points so the
1289         // edge clipped by a selcted face has two of the points
1290         if (!shear)
1291                 return;
1292
1293         for (f2=b->brush_faces ; f2 ; f2=f2->next)
1294         {
1295                 if (f2 == f)
1296                         continue;
1297                 w = MakeFaceWinding (b, f2);
1298                 if (!w)
1299                         continue;
1300
1301                 // any points on f will become new control points
1302                 for (i=0 ; i<w->numpoints ; i++)
1303                 {
1304                         d = DotProduct (w->points[i], f->plane.normal)
1305                                 - f->plane.dist;
1306                         if (d > -ON_EPSILON && d < ON_EPSILON)
1307                                 break;
1308                 }
1309
1310                 //
1311                 // if none of the points were on the plane,
1312                 // leave it alone
1313                 //
1314                 if (i != w->numpoints)
1315                 {
1316                         if (i == 0)
1317                         {       // see if the first clockwise point was the
1318                                 // last point on the winding
1319                                 d = DotProduct (w->points[w->numpoints-1]
1320                                         , f->plane.normal) - f->plane.dist;
1321                                 if (d > -ON_EPSILON && d < ON_EPSILON)
1322                                         i = w->numpoints - 1;
1323                         }
1324
1325                         AddPlanept (f2->planepts[0]);
1326
1327                         VectorCopy (w->points[i], f2->planepts[0]);
1328                         if (++i == w->numpoints)
1329                                 i = 0;
1330
1331                         // see if the next point is also on the plane
1332                         d = DotProduct (w->points[i]
1333                                 , f->plane.normal) - f->plane.dist;
1334                         if (d > -ON_EPSILON && d < ON_EPSILON)
1335                                 AddPlanept (f2->planepts[1]);
1336
1337                         VectorCopy (w->points[i], f2->planepts[1]);
1338                         if (++i == w->numpoints)
1339                                 i = 0;
1340
1341                         // the third point is never on the plane
1342
1343                         VectorCopy (w->points[i], f2->planepts[2]);
1344                 }
1345
1346                 free(w);
1347         }
1348 }
1349
1350 /*
1351 ==============
1352 Brush_SideSelect
1353
1354 The mouse click did not hit the brush, so grab one or more side
1355 planes for dragging
1356 ==============
1357 */
1358 void Brush_SideSelect (brush_t *b, vec3_t origin, vec3_t dir
1359                                            , qboolean shear)
1360 {
1361         face_t  *f, *f2;
1362         vec3_t  p1, p2;
1363
1364         for (f=b->brush_faces ; f ; f=f->next)
1365         {
1366                 VectorCopy (origin, p1);
1367                 VectorMA (origin, 16384, dir, p2);
1368
1369                 for (f2=b->brush_faces ; f2 ; f2=f2->next)
1370                 {
1371                         if (f2 == f)
1372                                 continue;
1373                         ClipLineToFace (p1, p2, f2);
1374                 }
1375
1376                 if (f2)
1377                         continue;
1378
1379                 if (VectorCompare (p1, origin))
1380                         continue;
1381                 if (ClipLineToFace (p1, p2, f))
1382                         continue;
1383
1384                 Brush_SelectFaceForDragging (b, f, shear);
1385         }
1386
1387
1388 }
1389
1390 void Brush_BuildWindings( brush_t *b )
1391 {
1392         winding_t *w;
1393         face_t    *face;
1394         vec_t      v;
1395
1396         Brush_SnapPlanepts( b );
1397
1398         // clear the mins/maxs bounds
1399         b->mins[0] = b->mins[1] = b->mins[2] = 99999;
1400         b->maxs[0] = b->maxs[1] = b->maxs[2] = -99999;
1401
1402         Brush_MakeFacePlanes (b);
1403
1404         face = b->brush_faces;
1405
1406         for ( ; face ; face=face->next)
1407         {
1408                 int i, j;
1409
1410                 w = face->face_winding = MakeFaceWinding (b, face);
1411                 face->d_texture = Texture_ForName( face->texdef.name );
1412
1413                 if (!w)
1414                 {
1415                         continue;
1416                 }
1417
1418             for (i=0 ; i<w->numpoints ; i++)
1419             {
1420                         // add to bounding box
1421                         for (j=0 ; j<3 ; j++)
1422                         {
1423                                 v = w->points[i][j];
1424                                 if (v > b->maxs[j])
1425                                         b->maxs[j] = v;
1426                                 if (v < b->mins[j])
1427                                         b->mins[j] = v;
1428                         }
1429             }
1430                 // setup s and t vectors, and set color
1431                 BeginTexturingFace( b, face, face->d_texture);
1432
1433
1434             for (i=0 ; i<w->numpoints ; i++)
1435             {
1436                         EmitTextureCoordinates( w->points[i], face->d_texture, face);
1437             }
1438         }
1439 }
1440
1441 /*
1442 ==================
1443 Brush_RemoveEmptyFaces
1444
1445 Frees any overconstraining faces
1446 ==================
1447 */
1448 void Brush_RemoveEmptyFaces ( brush_t *b )
1449 {
1450         face_t  *f, *next;
1451
1452         f = b->brush_faces;
1453         b->brush_faces = NULL;
1454
1455         for ( ; f ; f=next)
1456         {
1457                 next = f->next;
1458                 if (!f->face_winding)
1459                         Face_Free (f);
1460                 else
1461                 {
1462                         f->next = b->brush_faces;
1463                         b->brush_faces = f;
1464                 }
1465
1466         }
1467 }
1468
1469 void Brush_Draw( brush_t *b )
1470 {
1471         face_t                  *face;
1472         int                             i, order;
1473     qtexture_t          *prev = 0;
1474         winding_t *w;
1475
1476         if (b->owner->eclass->fixedsize && camera.draw_mode == cd_texture)
1477                 glDisable (GL_TEXTURE_2D);
1478
1479         // guarantee the texture will be set first
1480         prev = NULL;
1481         for (face = b->brush_faces,order = 0 ; face ; face=face->next, order++)
1482         {
1483                 w = face->face_winding;
1484                 if (!w)
1485                         continue;               // freed face
1486
1487                 if ( face->d_texture != prev && camera.draw_mode == cd_texture)
1488                 {
1489                         // set the texture for this face
1490                         prev = face->d_texture;
1491                         glBindTexture( GL_TEXTURE_2D, face->d_texture->texture_number );
1492                 }
1493
1494                 glColor3fv( face->d_color );
1495
1496                 // draw the polygon
1497                 glBegin(GL_POLYGON);
1498             for (i=0 ; i<w->numpoints ; i++)
1499                 {
1500                         if (camera.draw_mode == cd_texture)
1501                                 glTexCoord2fv( &w->points[i][3] );
1502                         glVertex3fv(w->points[i]);
1503                 }
1504                 glEnd();
1505         }
1506
1507         if (b->owner->eclass->fixedsize && camera.draw_mode == cd_texture)
1508                 glEnable (GL_TEXTURE_2D);
1509
1510         glBindTexture( GL_TEXTURE_2D, 0 );
1511 }
1512
1513 void Face_Draw( face_t *f )
1514 {
1515         int i;
1516
1517         if ( f->face_winding == 0 )
1518                 return;
1519         glBegin( GL_POLYGON );
1520         for ( i = 0 ; i < f->face_winding->numpoints; i++)
1521                 glVertex3fv( f->face_winding->points[i] );
1522         glEnd();
1523 }
1524
1525 void Brush_DrawXY( brush_t *b )
1526 {
1527         face_t *face;
1528         int     order;
1529         winding_t *w;
1530         int        i;
1531
1532         for (face = b->brush_faces,order = 0 ; face ; face=face->next, order++)
1533         {
1534                 // only draw up facing polygons
1535                 if (face->plane.normal[2] <= 0)
1536                         continue;
1537
1538                 w = face->face_winding;
1539                 if (!w)
1540                         continue;
1541
1542                 // draw the polygon
1543                 glBegin(GL_LINE_LOOP);
1544             for (i=0 ; i<w->numpoints ; i++)
1545                         glVertex3fv(w->points[i]);
1546                 glEnd();
1547         }
1548
1549         // optionally add a text label
1550         if ( g_qeglobals.d_savedinfo.show_names )
1551                 DrawBrushEntityName (b);
1552 }
1553
1554 face_t *Face_Alloc( void )
1555 {
1556         face_t *f = qmalloc( sizeof( *f ) );
1557
1558         return f;
1559 }
1560
1561 void Face_Free( face_t *f )
1562 {
1563         assert( f != 0 );
1564
1565         if ( f->face_winding )
1566                 free( f->face_winding ), f->face_winding = 0;
1567         free( f );
1568 }