2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
32 void Brush_Scale(brush_t* b)
34 for (face_t* f = b->brush_faces ; f ; f=f->next)
36 for (int i=0 ; i<3 ; i++)
38 VectorScale (f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i]);
43 void CSG_MakeHollow (void)
45 brush_t *b, *front, *back, *next;
51 for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
55 if (b->owner->eclass->fixedsize || b->patchBrush || b->bFiltered)
58 for (f = b->brush_faces ; f ; f=f->next)
61 VectorScale (f->plane.normal, g_qeglobals.d_gridsize, move);
63 VectorSubtract (split.planepts[i], move, split.planepts[i]);
65 Brush_SplitBrushByFace (b, &split, &front, &back);
69 Brush_AddToList (front, &selected_brushes);
73 Sys_UpdateWindows (W_ALL);
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.
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
89 brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)
93 face_t *face1, *face2, *newface, *f;
95 // check for bounding box overlapp
96 for (i = 0; i < 3; i++)
98 if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
99 || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)
101 // never merge if the brushes overlap
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)
110 // don't check the faces of brush 1 and 2 touching each other
111 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
113 if (Plane_Equal(&face1->plane, &face2->plane, true))
116 // there may only be ONE shared side
122 // if this face plane is shared
125 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
127 // don't check the faces of brush 1 and 2 touching each other
128 for (f = brush1->brush_faces; f; f = f->next)
130 if (Plane_Equal(&face2->plane, &f->plane, true)) break;
135 if (Plane_Equal(&face1->plane, &face2->plane, false))
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;
142 if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
143 face1->plane.normal, face2->plane.normal,
144 face1->plane.dist, face2->plane.dist))
151 newbrush = Brush_Alloc();
153 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
155 // don't add the faces of brush 1 and 2 touching each other
156 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
158 if (Plane_Equal(&face1->plane, &face2->plane, true))
163 // don't add faces with the same plane twice
164 for (f = newbrush->brush_faces; f; f = f->next)
166 if (Plane_Equal(&face1->plane, &f->plane, false))
168 if (Plane_Equal(&face1->plane, &f->plane, true))
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;
184 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)
189 if (Plane_Equal(&face2->plane, &face1->plane, true))
194 // don't add faces with the same plane twice
195 for (f = newbrush->brush_faces; f; f = f->next)
197 if (Plane_Equal(&face2->plane, &f->plane, false))
199 if (Plane_Equal(&face2->plane, &f->plane, true))
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;
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);
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
232 brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)
234 int nummerges, merged;
235 brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
238 if (!brushlist) return NULL;
243 for (tail = brushlist; tail; tail = tail->next)
245 if (!tail->next) break;
249 for (b1 = brushlist; b1; b1 = brushlist)
252 for (b2 = b1->next; b2; b2 = b2->next)
254 newbrush = Brush_Merge(b1, b2, onlyshape);
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;
264 for (tail = brushlist; tail; tail = tail->next)
266 if (!tail->next) break;
274 //if b1 can't be merged with any of the other brushes
277 brushlist = brushlist->next;
279 b1->next = newbrushlist;
283 brushlist = newbrushlist;
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.
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
303 brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)
305 brush_t *brush1, *brush2, *brush3, *newbrush;
306 face_t *face1, *face2, *face3, *newface, *f;
308 if (!brushlist) return NULL;
309 for (brush1 = brushlist; brush1; brush1 = brush1->next)
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)
314 // don't check face1 if it touches another brush
315 for (brush2 = brushlist; brush2; brush2 = brush2->next)
317 if (brush2 == brush1) continue;
318 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
320 if (Plane_Equal(&face1->plane, &face2->plane, true))
327 // if face1 touches another brush
328 if (brush2) continue;
330 for (brush2 = brush1->next; brush2; brush2 = brush2->next)
332 // don't check the faces of brush 2 touching another brush
333 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
335 for (brush3 = brushlist; brush3; brush3 = brush3->next)
337 if (brush3 == brush2) continue;
338 for (face3 = brush3->brush_faces; face3; face3 = face3->next)
340 if (Plane_Equal(&face2->plane, &face3->plane, true)) break;
344 // if face2 touches another brush
345 if (brush3) continue;
347 if (Plane_Equal(&face1->plane, &face2->plane, false))
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;
354 if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
355 face1->plane.normal, face2->plane.normal,
356 face1->plane.dist, face2->plane.dist))
365 newbrush = Brush_Alloc();
367 for (brush1 = brushlist; brush1; brush1 = brush1->next)
369 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
371 // don't add face1 to the new brush if it touches another brush
372 for (brush2 = brushlist; brush2; brush2 = brush2->next)
374 if (brush2 == brush1) continue;
375 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
377 if (Plane_Equal(&face1->plane, &face2->plane, true))
384 if (brush2) continue;
385 // don't add faces with the same plane twice
386 for (f = newbrush->brush_faces; f; f = f->next)
388 if (Plane_Equal(&face1->plane, &f->plane, false))
390 if (Plane_Equal(&face1->plane, &f->plane, true))
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;
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);
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.
423 brush_t *Brush_Subtract(brush_t *a, brush_t *b)
425 // a - b = out (list)
426 brush_t *front, *back;
427 brush_t *in, *out, *next;
432 for (f = b->brush_faces; f && in; f = f->next)
434 Brush_SplitBrushByFace(in, f, &front, &back);
435 if (in != a) Brush_Free(in);
443 //NOTE: in != a just in case brush b has no faces
449 { //didn't really intersect
450 for (b = out; b; b = next)
453 b->next = b->prev = NULL;
466 void CSG_Subtract (void)
468 brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
469 brush_t fragmentlist;
470 int i, numfragments, numbrushes;
472 Sys_Printf ("Subtracting...\n");
474 if (selected_brushes.next == &selected_brushes)
476 Sys_Printf("No brushes selected.\n");
480 fragmentlist.next = &fragmentlist;
481 fragmentlist.prev = &fragmentlist;
485 for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
489 if (b->owner->eclass->fixedsize)
490 continue; // can't use texture from a fixed entity, so don't subtract
492 // chop all fragments further up
493 for (s = fragmentlist.next; s != &fragmentlist; s = snext)
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)
502 continue; // definately don't touch
503 fragments = Brush_Subtract(s, b);
504 // if the brushes did not really intersect
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)
512 nextfragment = frag->next;
514 frag->owner = s->owner;
515 Brush_AddToList(frag, &fragmentlist);
517 // free the original brush
521 // chop any active brushes up
522 for (s = active_brushes.next; s != &active_brushes; s = snext)
526 if (s->owner->eclass->fixedsize || s->patchBrush || s->bFiltered)
529 if (s->brush_faces->pShader->getFlags() & QER_NOCARVE)
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)
539 continue; // definately don't touch
541 fragments = Brush_Subtract(s, b);
542 // if the brushes did not really intersect
547 // one extra brush chopped up
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)
554 nextfragment = frag->next;
556 frag->owner = s->owner;
557 Brush_AddToList(frag, &fragmentlist);
559 // free the original brush
564 // move all fragments to the active brush list
565 for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)
567 nextfragment = frag->next;
569 Brush_RemoveFromList(frag);
570 Brush_AddToList(frag, &active_brushes);
574 /*if (numfragments == 0)
576 Sys_Printf("Selected brush%s did not intersect with any other brushes.\n",
577 (selected_brushes.next->next == &selected_brushes) ? "":"es");
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);
592 brush_t *b, *next, *newlist, *newbrush;
593 struct entity_s *owner;
595 Sys_Printf ("Merging...\n");
597 if (selected_brushes.next == &selected_brushes)
599 Sys_Printf("No brushes selected.\n");
603 if (selected_brushes.next->next == &selected_brushes)
605 Sys_Printf("At least two brushes have to be selected.\n");
609 owner = selected_brushes.next->owner;
611 for (b = selected_brushes.next; b != &selected_brushes; b = next)
615 if (b->owner->eclass->fixedsize)
617 // can't use texture from a fixed entity, so don't subtract
618 Sys_Printf("Cannot add fixed size entities.\n");
624 Sys_Printf("Cannot add patches.\n");
629 // disable the qer_nocarve for CSG-MERGE operations
631 if (b->brush_faces->d_texture->bFromShader && (b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE))
633 Sys_Printf("Cannot add brushes using shaders that don't allows CSG operations.\n");
638 if (b->owner != owner)
640 Sys_Printf("Cannot add brushes from different entities.\n");
647 for (b = selected_brushes.next; b != &selected_brushes; b = next)
651 Brush_RemoveFromList(b);
657 newbrush = Brush_MergeList(newlist, true);
658 // if the new brush would not be convex
661 // add the brushes back into the selection
662 for (b = newlist; b; b = next)
667 Brush_AddToList(b, &selected_brushes);
669 Sys_Printf("Cannot add a set of brushes with a concave hull.\n");
672 // free the original brushes
673 for (b = newlist; b; b = next)
681 newbrush->bFiltered = FilterBrush(newbrush); // spog - set filters for the new brush
683 Brush_AddToList(newbrush, &selected_brushes);
685 Sys_Printf ("done.\n");
686 Sys_UpdateWindows (W_ALL);