neo/tools/radiant/CSG.CPP

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "qe3.h"
  33
  34 const float PLANE_EPSILON = 0.0001f;
  35
  36 /*
  37 =============
  38 CSG_MakeHollow
  39 =============
  40 */
  41 void CSG_MakeHollow (void)
  42 {
  43         brush_t         *b, *front, *back, *next;
  44         face_t          *f;
  45         face_t          split;
  46         idVec3          move;
  47         int                     i;
  48
  49         for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
  50         {
  51                 next = b->next;
  52
  53     if (b->owner->eclass->fixedsize || b->pPatch || b->hiddenBrush || b->modelHandle > 0)
  54                   continue;
  55
  56                 for ( f = b->brush_faces; f; f = f->next ) {
  57                         split = *f;
  58                         VectorScale (f->plane, g_qeglobals.d_gridsize, move);
  59                         for (i=0 ; i<3 ; i++)
  60                                 VectorSubtract (split.planepts[i], move, split.planepts[i]);
  61
  62                         Brush_SplitBrushByFace (b, &split, &front, &back);
  63                         if (back)
  64                                 Brush_Free (back);
  65                         if (front)
  66                                 Brush_AddToList (front, &selected_brushes);
  67                 }
  68                 Brush_Free (b);
  69         }
  70         Sys_UpdateWindows (W_ALL);
  71 }
  72
  73 /*
  74 =============
  75 Brush_Merge
  76
  77  Returns a new brush that is created by merging brush1 and brush2.
  78  May return NULL if brush1 and brush2 do not create a convex brush when merged.
  79  The input brushes brush1 and brush2 stay intact.
  80
  81  if onlyshape is true then the merge is allowed based on the shape only
  82  otherwise the texture/shader references of faces in the same plane have to
  83  be the same as well.
  84 =============
  85 */
  86 brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)
  87 {
  88         int i, shared;
  89         brush_t *newbrush;
  90         face_t *face1, *face2, *newface, *f;
  91
  92         // check for bounding box overlapp
  93         for (i = 0; i < 3; i++)
  94         {
  95                 if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
  96                                 || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)
  97                 {
  98                         // never merge if the brushes overlap
  99                         return NULL;
 100                 }
 101         }
 102         //
 103         shared = 0;
 104         // check if the new brush would be convex... flipped planes make a brush non-convex
 105         for (face1 = brush1->brush_faces; face1; face1 = face1->next)
 106         {
 107                 // don't check the faces of brush 1 and 2 touching each other
 108                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 109                 {
 110                         if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) )
 111                         {
 112                                 shared++;
 113                                 // there may only be ONE shared side
 114                                 if (shared > 1)
 115                                         return NULL;
 116                                 break;
 117                         }
 118                 }
 119                 // if this face plane is shared
 120                 if (face2) continue;
 121                 //
 122                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 123                 {
 124                         // don't check the faces of brush 1 and 2 touching each other
 125                         for ( f = brush1->brush_faces; f; f = f->next ) {
 126                                 if ( face2->plane.Compare( -f->plane, PLANE_EPSILON ) ) {
 127                                         break;
 128                                 }
 129                         }
 130                         if ( f ) {
 131                                 continue;
 132                         }
 133
 134                         if ( face1->plane.Compare( face2->plane, PLANE_EPSILON ) )
 135                         {
 136                                 //if the texture/shader references should be the same but are not
 137                                 if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0)
 138                                         return NULL;
 139                                 continue;
 140                         }
 141                         //
 142                         if ( face1->face_winding->PlanesConcave( *face2->face_winding,
 143                                                         face1->plane.Normal(), face2->plane.Normal(), -face1->plane[3], -face2->plane[3]))
 144                         {
 145                                 return NULL;
 146                         } //end if
 147                 } //end for
 148         } //end for
 149         //
 150         newbrush = Brush_Alloc();
 151         //
 152         for (face1 = brush1->brush_faces; face1; face1 = face1->next)
 153         {
 154                 // don't add the faces of brush 1 and 2 touching each other
 155                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 156                 {
 157                         if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
 158                                 break;
 159                         }
 160                 }
 161                 if ( face2 )
 162                         continue;
 163                 // don't add faces with the same plane twice
 164                 for (f = newbrush->brush_faces; f; f = f->next)
 165                 {
 166                         if ( face1->plane.Compare( f->plane, PLANE_EPSILON ) )
 167                                 break;
 168                         if ( face1->plane.Compare( -f->plane, PLANE_EPSILON ) )
 169                                 break;
 170                 }
 171                 if ( f ) {
 172                         continue;
 173                 }
 174
 175                 newface = Face_Alloc();
 176                 newface->texdef = face1->texdef;
 177                 VectorCopy(face1->planepts[0], newface->planepts[0]);
 178                 VectorCopy(face1->planepts[1], newface->planepts[1]);
 179                 VectorCopy(face1->planepts[2], newface->planepts[2]);
 180                 newface->plane = face1->plane;
 181                 newface->next = newbrush->brush_faces;
 182                 newbrush->brush_faces = newface;
 183         }
 184
 185         for (face2 = brush2->brush_faces; face2; face2 = face2->next) {
 186                 // don't add the faces of brush 1 and 2 touching each other
 187                 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
 188                 {
 189                         if ( face2->plane.Compare( -face1->plane, PLANE_EPSILON ) ) {
 190                                 break;
 191                         }
 192                 }
 193                 if (face1)
 194                         continue;
 195                 // don't add faces with the same plane twice
 196                 for (f = newbrush->brush_faces; f; f = f->next)
 197                 {
 198                         if ( face2->plane.Compare( f->plane, PLANE_EPSILON ) )
 199                                 break;
 200                         if ( face2->plane.Compare( -f->plane, PLANE_EPSILON ) )
 201                                 break;
 202                 }
 203                 if ( f ) {
 204                         continue;
 205                 }
 206                 //
 207                 newface = Face_Alloc();
 208                 newface->texdef = face2->texdef;
 209                 VectorCopy(face2->planepts[0], newface->planepts[0]);
 210                 VectorCopy(face2->planepts[1], newface->planepts[1]);
 211                 VectorCopy(face2->planepts[2], newface->planepts[2]);
 212                 newface->plane = face2->plane;
 213                 newface->next = newbrush->brush_faces;
 214                 newbrush->brush_faces = newface;
 215         }
 216         // link the new brush to an entity
 217         Entity_LinkBrush (brush1->owner, newbrush);
 218         // build windings for the faces
 219         Brush_BuildWindings( newbrush, false);
 220         return newbrush;
 221 }
 222
 223 /*
 224 =============
 225 Brush_MergeListPairs
 226
 227   Returns a list with merged brushes.
 228   Tries to merge brushes pair wise.
 229   The input list is destroyed.
 230   Input and output should be a single linked list using .next
 231 =============
 232 */
 233 brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)
 234 {
 235         int nummerges, merged;
 236         brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
 237         brush_t *lastb2;
 238
 239         if (!brushlist) return NULL;
 240
 241         nummerges = 0;
 242         do
 243         {
 244                 for (tail = brushlist; tail; tail = tail->next)
 245                 {
 246                         if (!tail->next) break;
 247                 }
 248                 merged = 0;
 249                 newbrushlist = NULL;
 250                 for (b1 = brushlist; b1; b1 = brushlist)
 251                 {
 252                         lastb2 = b1;
 253                         for (b2 = b1->next; b2; b2 = b2->next)
 254                         {
 255                                 newbrush = Brush_Merge(b1, b2, onlyshape);
 256                                 if (newbrush)
 257                                 {
 258                                         tail->next = newbrush;
 259                                         lastb2->next = b2->next;
 260                                         brushlist = brushlist->next;
 261                                         b1->next = b1->prev = NULL;
 262                                         b2->next = b2->prev = NULL;
 263                                         Brush_Free(b1);
 264                                         Brush_Free(b2);
 265                                         for (tail = brushlist; tail; tail = tail->next)
 266                                         {
 267                                                 if (!tail->next) break;
 268                                         } //end for
 269                                         merged++;
 270                                         nummerges++;
 271                                         break;
 272                                 }
 273                                 lastb2 = b2;
 274                         }
 275                         //if b1 can't be merged with any of the other brushes
 276                         if (!b2)
 277                         {
 278                                 brushlist = brushlist->next;
 279                                 //keep b1
 280                                 b1->next = newbrushlist;
 281                                 newbrushlist = b1;
 282                         }
 283                 }
 284                 brushlist = newbrushlist;
 285         } while(merged);
 286         return newbrushlist;
 287 }
 288
 289 /*
 290 =============
 291 Brush_MergeList
 292
 293  Tries to merge all brushes in the list into one new brush.
 294  The input brush list stays intact.
 295  Returns NULL if no merged brush can be created.
 296  To create a new brush the brushes in the list may not overlap and
 297  the outer faces of the brushes together should make a new convex brush.
 298
 299  if onlyshape is true then the merge is allowed based on the shape only
 300  otherwise the texture/shader references of faces in the same plane have to
 301  be the same as well.
 302 =============
 303 */
 304 brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)
 305 {
 306         brush_t *brush1, *brush2, *brush3, *newbrush;
 307         face_t *face1, *face2, *face3, *newface, *f;
 308
 309         if (!brushlist) return NULL;
 310         for (brush1 = brushlist; brush1; brush1 = brush1->next)
 311         {
 312                 // check if the new brush would be convex... flipped planes make a brush concave
 313                 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
 314                 {
 315                         // don't check face1 if it touches another brush
 316                         for (brush2 = brushlist; brush2; brush2 = brush2->next)
 317                         {
 318                                 if (brush2 == brush1) continue;
 319                                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 320                                 {
 321                                         if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
 322                                                 break;
 323                                         }
 324                                 }
 325                                 if (face2)
 326                                         break;
 327                         }
 328                         // if face1 touches another brush
 329                         if (brush2)
 330                                 continue;
 331                         //
 332                         for (brush2 = brush1->next; brush2; brush2 = brush2->next)
 333                         {
 334                                 // don't check the faces of brush 2 touching another brush
 335                                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 336                                 {
 337                                         for (brush3 = brushlist; brush3; brush3 = brush3->next)
 338                                         {
 339                                                 if (brush3 == brush2) continue;
 340                                                 for (face3 = brush3->brush_faces; face3; face3 = face3->next)
 341                                                 {
 342                                                         if ( face2->plane.Compare( -face3->plane, PLANE_EPSILON ) )
 343                                                                 break;
 344                                                 }
 345                                                 if (face3)
 346                                                         break;
 347                                         }
 348                                         // if face2 touches another brush
 349                                         if (brush3)
 350                                                 continue;
 351                                         //
 352                                         if ( face1->plane.Compare( face2->plane, PLANE_EPSILON ) )
 353                                         {
 354                                                 //if the texture/shader references should be the same but are not
 355                                                 if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0)
 356                                                         return NULL;
 357                                                 continue;
 358                                         }
 359                                         //
 360                                         if ( face1->face_winding->PlanesConcave( *face2->face_winding,
 361                                                         face1->plane.Normal(), face2->plane.Normal(), -face1->plane[3], -face2->plane[3]))
 362                                         {
 363                                                 return NULL;
 364                                         }
 365                                 }
 366                         }
 367                 }
 368         }
 369         //
 370         newbrush = Brush_Alloc();
 371         //
 372         for (brush1 = brushlist; brush1; brush1 = brush1->next)
 373         {
 374                 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
 375                 {
 376                         // don't add face1 to the new brush if it touches another brush
 377                         for (brush2 = brushlist; brush2; brush2 = brush2->next)
 378                         {
 379                                 if (brush2 == brush1) continue;
 380                                 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
 381                                 {
 382                                         if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
 383                                                 break;
 384                                         }
 385                                 }
 386                                 if (face2)
 387                                         break;
 388                         }
 389                         if (brush2)
 390                                 continue;
 391                         // don't add faces with the same plane twice
 392                         for (f = newbrush->brush_faces; f; f = f->next)
 393                         {
 394                                 if ( face1->plane.Compare( f->plane, PLANE_EPSILON ) )
 395                                         break;
 396                                 if ( face1->plane.Compare( -f->plane, PLANE_EPSILON ) )
 397                                         break;
 398                         }
 399                         if (f)
 400                                 continue;
 401                         //
 402                         newface = Face_Alloc();
 403                         newface->texdef = face1->texdef;
 404                         VectorCopy(face1->planepts[0], newface->planepts[0]);
 405                         VectorCopy(face1->planepts[1], newface->planepts[1]);
 406                         VectorCopy(face1->planepts[2], newface->planepts[2]);
 407                         newface->plane = face1->plane;
 408                         newface->next = newbrush->brush_faces;
 409                         newbrush->brush_faces = newface;
 410                 }
 411         }
 412         // link the new brush to an entity
 413         Entity_LinkBrush (brushlist->owner, newbrush);
 414         // build windings for the faces
 415         Brush_BuildWindings( newbrush, false);
 416         return newbrush;
 417 }
 418
 419 /*
 420 =============
 421 Brush_Subtract
 422
 423  Returns a list of brushes that remain after B is subtracted from A.
 424  May by empty if A is contained inside B.
 425  The originals are undisturbed.
 426 =============
 427 */
 428 brush_t *Brush_Subtract(brush_t *a, brush_t *b)
 429 {
 430         // a - b = out (list)
 431         brush_t *front, *back;
 432         brush_t *in, *out, *next;
 433         face_t *f;
 434
 435         in = a;
 436         out = NULL;
 437         for (f = b->brush_faces; f && in; f = f->next)
 438         {
 439                 Brush_SplitBrushByFace(in, f, &front, &back);
 440                 if (in != a) Brush_Free(in);
 441                 if (front)
 442                 {       // add to list
 443                         front->next = out;
 444                         out = front;
 445                 }
 446                 in = back;
 447         }
 448         //NOTE: in != a just in case brush b has no faces
 449         if (in && in != a)
 450         {
 451                 Brush_Free(in);
 452         }
 453         else
 454         {       //didn't really intersect
 455                 for (b = out; b; b = next)
 456                 {
 457                         next = b->next;
 458                         b->next = b->prev = NULL;
 459                         Brush_Free(b);
 460                 }
 461                 return a;
 462         }
 463         return out;
 464 }
 465
 466 /*
 467 =============
 468 CSG_Subtract
 469 =============
 470 */
 471 void CSG_Subtract (void)
 472 {
 473         brush_t         *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
 474         brush_t         fragmentlist;
 475         int                     i, numfragments, numbrushes;
 476
 477         Sys_Status ("Subtracting...\n");
 478
 479         if (selected_brushes.next == &selected_brushes)
 480         {
 481                 Sys_Status("No brushes selected.\n");
 482                 return;
 483         }
 484
 485         fragmentlist.next = &fragmentlist;
 486         fragmentlist.prev = &fragmentlist;
 487
 488         numfragments = 0;
 489         numbrushes = 0;
 490         for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
 491         {
 492                 next = b->next;
 493
 494                 if (b->owner->eclass->fixedsize || b->modelHandle > 0)
 495                         continue;       // can't use texture from a fixed entity, so don't subtract
 496
 497                 // chop all fragments further up
 498                 for (s = fragmentlist.next; s != &fragmentlist; s = snext)
 499                 {
 500                         snext = s->next;
 501
 502                         for (i=0 ; i<3 ; i++)
 503                                 if (b->mins[i] >= s->maxs[i] - ON_EPSILON
 504                                 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
 505                                         break;
 506                         if (i != 3)
 507                                 continue;       // definately don't touch
 508                         fragments = Brush_Subtract(s, b);
 509                         // if the brushes did not really intersect
 510                         if (fragments == s)
 511                                 continue;
 512                         // try to merge fragments
 513                         fragments = Brush_MergeListPairs(fragments, true);
 514                         // add the fragments to the list
 515                         for (frag = fragments; frag; frag = nextfragment)
 516                         {
 517                                 nextfragment = frag->next;
 518                                 frag->next = NULL;
 519                                 frag->owner = s->owner;
 520                                 Brush_AddToList(frag, &fragmentlist);
 521                         }
 522                         // free the original brush
 523                         Brush_Free(s);
 524                 }
 525
 526                 // chop any active brushes up
 527                 for (s = active_brushes.next; s != &active_brushes; s = snext)
 528                 {
 529                         snext = s->next;
 530
 531                         if (s->owner->eclass->fixedsize || s->pPatch || s->hiddenBrush || s->modelHandle > 0)
 532                                 continue;
 533
 534                         //face_t *pFace = s->brush_faces;
 535                         if ( s->brush_faces->d_texture && ( s->brush_faces->d_texture->GetContentFlags()& CONTENTS_NOCSG ) )
 536                         {
 537                                 continue;
 538                         }
 539
 540                         for (i=0 ; i<3 ; i++)
 541                                 if (b->mins[i] >= s->maxs[i] - ON_EPSILON
 542                                 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
 543                                         break;
 544                         if (i != 3)
 545                                 continue;       // definately don't touch
 546
 547                         fragments = Brush_Subtract(s, b);
 548                         // if the brushes did not really intersect
 549                         if (fragments == s)
 550                                 continue;
 551                         //
 552                         Undo_AddBrush(s);
 553                         // one extra brush chopped up
 554                         numbrushes++;
 555                         // try to merge fragments
 556                         fragments = Brush_MergeListPairs(fragments, true);
 557                         // add the fragments to the list
 558                         for (frag = fragments; frag; frag = nextfragment)
 559                         {
 560                                 nextfragment = frag->next;
 561                                 frag->next = NULL;
 562                                 frag->owner = s->owner;
 563                                 Brush_AddToList(frag, &fragmentlist);
 564                         }
 565                         // free the original brush
 566                         Brush_Free(s);
 567                 }
 568         }
 569
 570         // move all fragments to the active brush list
 571         for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)
 572         {
 573                 nextfragment = frag->next;
 574                 numfragments++;
 575                 Brush_RemoveFromList(frag);
 576                 Brush_AddToList(frag, &active_brushes);
 577                 Undo_EndBrush(frag);
 578         }
 579
 580         if (numfragments == 0)
 581         {
 582                 common->Printf("Selected brush%s did not intersect with any other brushes.\n",
 583                                         (selected_brushes.next->next == &selected_brushes) ? "":"es");
 584                 return;
 585         }
 586         Sys_Status("done.");
 587         common->Printf(" (created %d fragment%s out of %d brush%s)\n", numfragments, (numfragments == 1)?"":"s",
 588                                                         numbrushes, (numbrushes == 1)?"":"es");
 589         Sys_UpdateWindows(W_ALL);
 590 }
 591
 592 /*
 593 =============
 594 CSG_Merge
 595 =============
 596 */
 597 void CSG_Merge(void)
 598 {
 599         brush_t *b, *next, *newlist, *newbrush;
 600         struct entity_s *owner;
 601
 602         Sys_Status("Merging...\n");
 603
 604         if (selected_brushes.next == &selected_brushes)
 605         {
 606                 Sys_Status("No brushes selected.\n");
 607                 return;
 608         }
 609
 610         if (selected_brushes.next->next == &selected_brushes)
 611         {
 612                 Sys_Status("At least two brushes have to be selected.\n");
 613                 return;
 614         }
 615
 616         owner = selected_brushes.next->owner;
 617
 618         for (b = selected_brushes.next; b != &selected_brushes; b = next)
 619         {
 620                 next = b->next;
 621
 622                 if (b->owner->eclass->fixedsize || b->modelHandle > 0)
 623                 {
 624                         // can't use texture from a fixed entity, so don't subtract
 625                         Sys_Status("Cannot add fixed size entities.\n");
 626                         return;
 627                 }
 628
 629                 if (b->pPatch)
 630                 {
 631                         Sys_Status("Cannot add patches.\n");
 632                         return;
 633                 }
 634
 635                 if ( b->brush_faces->d_texture && ( b->brush_faces->d_texture->GetContentFlags() & CONTENTS_NOCSG ) )
 636                 {
 637                         Sys_Status("Cannot add brushes using shaders that don't allows CSG operations.\n");
 638                         return;
 639                 }
 640
 641                 if (b->owner != owner)
 642                 {
 643                         Sys_Status("Cannot add brushes from different entities.\n");
 644                         return;
 645                 }
 646
 647         }
 648
 649         newlist = NULL;
 650         for (b = selected_brushes.next; b != &selected_brushes; b = next)
 651         {
 652                 next = b->next;
 653
 654                 Brush_RemoveFromList(b);
 655                 b->next = newlist;
 656                 b->prev = NULL;
 657                 newlist = b;
 658         }
 659
 660         newbrush = Brush_MergeList(newlist, true);
 661         // if the new brush would not be convex
 662         if (!newbrush)
 663         {
 664                 // add the brushes back into the selection
 665                 for (b = newlist; b; b = next)
 666                 {
 667                         next = b->next;
 668                         b->next = NULL;
 669                         b->prev = NULL;
 670                         Brush_AddToList(b, &selected_brushes);
 671                 }
 672                 Sys_Status("Cannot add a set of brushes with a concave hull.\n");
 673                 return;
 674         }
 675         // free the original brushes
 676         for (b = newlist; b; b = next)
 677         {
 678                 next = b->next;
 679                 b->next = NULL;
 680                 b->prev = NULL;
 681                 Brush_Free(b);
 682         }
 683         Brush_AddToList(newbrush, &selected_brushes);
 684
 685         Sys_Status ("done.\n");
 686         Sys_UpdateWindows (W_ALL);
 687 }