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