-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-*/\r
-\r
-#include "stdafx.h"\r
-#include "winding.h"\r
-#include "filters.h"\r
-\r
-/*\r
-=============\r
-CSG_MakeHollow\r
-=============\r
-*/\r
-\r
-void Brush_Scale(brush_t* b)\r
-{\r
- for (face_t* f = b->brush_faces ; f ; f=f->next)\r
- {\r
- for (int i=0 ; i<3 ; i++)\r
- {\r
- VectorScale (f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i]);\r
- }\r
- }\r
-}\r
-\r
-void CSG_MakeHollow (void)\r
-{\r
- brush_t *b, *front, *back, *next;\r
- face_t *f;\r
- face_t split;\r
- vec3_t move;\r
- int i;\r
-\r
- for (b = selected_brushes.next ; b != &selected_brushes ; b=next)\r
- {\r
- next = b->next;\r
-\r
- if (b->owner->eclass->fixedsize || b->patchBrush || b->bFiltered)\r
- continue;\r
-\r
- for (f = b->brush_faces ; f ; f=f->next)\r
- {\r
- split = *f;\r
- VectorScale (f->plane.normal, g_qeglobals.d_gridsize, move);\r
- for (i=0 ; i<3 ; i++)\r
- VectorSubtract (split.planepts[i], move, split.planepts[i]);\r
-\r
- Brush_SplitBrushByFace (b, &split, &front, &back);\r
- if (back)\r
- Brush_Free (back);\r
- if (front)\r
- Brush_AddToList (front, &selected_brushes);\r
- }\r
- Brush_Free (b);\r
- }\r
- Sys_UpdateWindows (W_ALL);\r
-}\r
-\r
-/*\r
-=============\r
-Brush_Merge\r
-\r
- Returns a new brush that is created by merging brush1 and brush2.\r
- May return NULL if brush1 and brush2 do not create a convex brush when merged.\r
- The input brushes brush1 and brush2 stay intact.\r
-\r
- if onlyshape is true then the merge is allowed based on the shape only\r
- otherwise the texture/shader references of faces in the same plane have to\r
- be the same as well.\r
-=============\r
-*/\r
-brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)\r
-{\r
- int i, shared;\r
- brush_t *newbrush;\r
- face_t *face1, *face2, *newface, *f;\r
-\r
- // check for bounding box overlapp\r
- for (i = 0; i < 3; i++)\r
- {\r
- if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON\r
- || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)\r
- {\r
- // never merge if the brushes overlap\r
- return NULL;\r
- }\r
- }\r
- //\r
- shared = 0;\r
- // check if the new brush would be convex... flipped planes make a brush non-convex\r
- for (face1 = brush1->brush_faces; face1; face1 = face1->next)\r
- {\r
- // don't check the faces of brush 1 and 2 touching each other\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &face2->plane, true))\r
- {\r
- shared++;\r
- // there may only be ONE shared side\r
- if (shared > 1)\r
- return NULL;\r
- break;\r
- }\r
- }\r
- // if this face plane is shared\r
- if (face2) continue;\r
- //\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- // don't check the faces of brush 1 and 2 touching each other\r
- for (f = brush1->brush_faces; f; f = f->next)\r
- {\r
- if (Plane_Equal(&face2->plane, &f->plane, true)) break;\r
- }\r
- if (f)\r
- continue;\r
- //\r
- if (Plane_Equal(&face1->plane, &face2->plane, false))\r
- {\r
- //if the texture/shader references should be the same but are not\r
- if (!onlyshape && stricmp(face1->texdef.GetName(), face2->texdef.GetName()) != 0) return NULL;\r
- continue;\r
- }\r
- //\r
- if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,\r
- face1->plane.normal, face2->plane.normal,\r
- face1->plane.dist, face2->plane.dist))\r
- {\r
- return NULL;\r
- } //end if\r
- } //end for\r
- } //end for\r
- //\r
- newbrush = Brush_Alloc();\r
- //\r
- for (face1 = brush1->brush_faces; face1; face1 = face1->next)\r
- {\r
- // don't add the faces of brush 1 and 2 touching each other\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &face2->plane, true))\r
- break;\r
- }\r
- if (face2)\r
- continue;\r
- // don't add faces with the same plane twice\r
- for (f = newbrush->brush_faces; f; f = f->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &f->plane, false))\r
- break;\r
- if (Plane_Equal(&face1->plane, &f->plane, true))\r
- break;\r
- }\r
- if (f)\r
- continue;\r
- //\r
- newface = Face_Alloc();\r
- newface->texdef = face1->texdef;\r
- VectorCopy(face1->planepts[0], newface->planepts[0]);\r
- VectorCopy(face1->planepts[1], newface->planepts[1]);\r
- VectorCopy(face1->planepts[2], newface->planepts[2]);\r
- newface->plane = face1->plane;\r
- newface->next = newbrush->brush_faces;\r
- newbrush->brush_faces = newface;\r
- }\r
- //\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- // don't add the faces of brush 1 and 2 touching each other\r
- for (face1 = brush1->brush_faces; face1; face1 = face1->next)\r
- {\r
- if (Plane_Equal(&face2->plane, &face1->plane, true))\r
- break;\r
- }\r
- if (face1)\r
- continue;\r
- // don't add faces with the same plane twice\r
- for (f = newbrush->brush_faces; f; f = f->next)\r
- {\r
- if (Plane_Equal(&face2->plane, &f->plane, false))\r
- break;\r
- if (Plane_Equal(&face2->plane, &f->plane, true))\r
- break;\r
- }\r
- if (f)\r
- continue;\r
- //\r
- newface = Face_Alloc();\r
- newface->texdef = face2->texdef;\r
- VectorCopy(face2->planepts[0], newface->planepts[0]);\r
- VectorCopy(face2->planepts[1], newface->planepts[1]);\r
- VectorCopy(face2->planepts[2], newface->planepts[2]);\r
- newface->plane = face2->plane;\r
- newface->next = newbrush->brush_faces;\r
- newbrush->brush_faces = newface;\r
- }\r
- // link the new brush to an entity\r
- Entity_LinkBrush (brush1->owner, newbrush);\r
- // build windings for the faces\r
- Brush_BuildWindings( newbrush, false);\r
-\r
- return newbrush;\r
-}\r
-\r
-/*\r
-=============\r
-Brush_MergeListPairs\r
-\r
- Returns a list with merged brushes.\r
- Tries to merge brushes pair wise.\r
- The input list is destroyed.\r
- Input and output should be a single linked list using .next\r
-=============\r
-*/\r
-brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)\r
-{\r
- int nummerges, merged;\r
- brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;\r
- brush_t *lastb2;\r
-\r
- if (!brushlist) return NULL;\r
-\r
- nummerges = 0;\r
- do\r
- {\r
- for (tail = brushlist; tail; tail = tail->next)\r
- {\r
- if (!tail->next) break;\r
- }\r
- merged = 0;\r
- newbrushlist = NULL;\r
- for (b1 = brushlist; b1; b1 = brushlist)\r
- {\r
- lastb2 = b1;\r
- for (b2 = b1->next; b2; b2 = b2->next)\r
- {\r
- newbrush = Brush_Merge(b1, b2, onlyshape);\r
- if (newbrush)\r
- {\r
- tail->next = newbrush;\r
- lastb2->next = b2->next;\r
- brushlist = brushlist->next;\r
- b1->next = b1->prev = NULL;\r
- b2->next = b2->prev = NULL;\r
- Brush_Free(b1);\r
- Brush_Free(b2);\r
- for (tail = brushlist; tail; tail = tail->next)\r
- {\r
- if (!tail->next) break;\r
- } //end for\r
- merged++;\r
- nummerges++;\r
- break;\r
- }\r
- lastb2 = b2;\r
- }\r
- //if b1 can't be merged with any of the other brushes\r
- if (!b2)\r
- {\r
- brushlist = brushlist->next;\r
- //keep b1\r
- b1->next = newbrushlist;\r
- newbrushlist = b1;\r
- }\r
- }\r
- brushlist = newbrushlist;\r
- } while(merged);\r
- return newbrushlist;\r
-}\r
-\r
-/*\r
-=============\r
-Brush_MergeList\r
-\r
- Tries to merge all brushes in the list into one new brush.\r
- The input brush list stays intact.\r
- Returns NULL if no merged brush can be created.\r
- To create a new brush the brushes in the list may not overlap and\r
- the outer faces of the brushes together should make a new convex brush.\r
-\r
- if onlyshape is true then the merge is allowed based on the shape only\r
- otherwise the texture/shader references of faces in the same plane have to\r
- be the same as well.\r
-=============\r
-*/\r
-brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)\r
-{\r
- brush_t *brush1, *brush2, *brush3, *newbrush;\r
- face_t *face1, *face2, *face3, *newface, *f;\r
-\r
- if (!brushlist) return NULL;\r
- for (brush1 = brushlist; brush1; brush1 = brush1->next)\r
- {\r
- // check if the new brush would be convex... flipped planes make a brush concave\r
- for (face1 = brush1->brush_faces; face1; face1 = face1->next)\r
- {\r
- // don't check face1 if it touches another brush\r
- for (brush2 = brushlist; brush2; brush2 = brush2->next)\r
- {\r
- if (brush2 == brush1) continue;\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &face2->plane, true))\r
- {\r
- break;\r
- }\r
- }\r
- if (face2) break;\r
- }\r
- // if face1 touches another brush\r
- if (brush2) continue;\r
- //\r
- for (brush2 = brush1->next; brush2; brush2 = brush2->next)\r
- {\r
- // don't check the faces of brush 2 touching another brush\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- for (brush3 = brushlist; brush3; brush3 = brush3->next)\r
- {\r
- if (brush3 == brush2) continue;\r
- for (face3 = brush3->brush_faces; face3; face3 = face3->next)\r
- {\r
- if (Plane_Equal(&face2->plane, &face3->plane, true)) break;\r
- }\r
- if (face3) break;\r
- }\r
- // if face2 touches another brush\r
- if (brush3) continue;\r
- //\r
- if (Plane_Equal(&face1->plane, &face2->plane, false))\r
- {\r
- //if the texture/shader references should be the same but are not\r
- if (!onlyshape && stricmp(face1->texdef.GetName(), face2->texdef.GetName()) != 0) return NULL;\r
- continue;\r
- }\r
- //\r
- if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,\r
- face1->plane.normal, face2->plane.normal,\r
- face1->plane.dist, face2->plane.dist))\r
- {\r
- return NULL;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- //\r
- newbrush = Brush_Alloc();\r
- //\r
- for (brush1 = brushlist; brush1; brush1 = brush1->next)\r
- {\r
- for (face1 = brush1->brush_faces; face1; face1 = face1->next)\r
- {\r
- // don't add face1 to the new brush if it touches another brush\r
- for (brush2 = brushlist; brush2; brush2 = brush2->next)\r
- {\r
- if (brush2 == brush1) continue;\r
- for (face2 = brush2->brush_faces; face2; face2 = face2->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &face2->plane, true))\r
- {\r
- break;\r
- }\r
- }\r
- if (face2) break;\r
- }\r
- if (brush2) continue;\r
- // don't add faces with the same plane twice\r
- for (f = newbrush->brush_faces; f; f = f->next)\r
- {\r
- if (Plane_Equal(&face1->plane, &f->plane, false))\r
- break;\r
- if (Plane_Equal(&face1->plane, &f->plane, true))\r
- break;\r
- }\r
- if (f)\r
- continue;\r
- //\r
- newface = Face_Alloc();\r
- newface->texdef = face1->texdef;\r
- VectorCopy(face1->planepts[0], newface->planepts[0]);\r
- VectorCopy(face1->planepts[1], newface->planepts[1]);\r
- VectorCopy(face1->planepts[2], newface->planepts[2]);\r
- newface->plane = face1->plane;\r
- newface->next = newbrush->brush_faces;\r
- newbrush->brush_faces = newface;\r
- }\r
- }\r
- // link the new brush to an entity\r
- Entity_LinkBrush (brushlist->owner, newbrush);\r
- // build windings for the faces\r
- Brush_BuildWindings( newbrush, false);\r
-\r
- return newbrush;\r
-}\r
-\r
-/*\r
-=============\r
-Brush_Subtract\r
-\r
- Returns a list of brushes that remain after B is subtracted from A.\r
- May by empty if A is contained inside B.\r
- The originals are undisturbed.\r
-=============\r
-*/\r
-brush_t *Brush_Subtract(brush_t *a, brush_t *b)\r
-{\r
- // a - b = out (list)\r
- brush_t *front, *back;\r
- brush_t *in, *out, *next;\r
- face_t *f;\r
-\r
- in = a;\r
- out = NULL;\r
- for (f = b->brush_faces; f && in; f = f->next)\r
- {\r
- Brush_SplitBrushByFace(in, f, &front, &back);\r
- if (in != a) Brush_Free(in);\r
- if (front)\r
- { // add to list\r
- front->next = out;\r
- out = front;\r
- }\r
- in = back;\r
- }\r
- //NOTE: in != a just in case brush b has no faces\r
- if (in && in != a)\r
- {\r
- Brush_Free(in);\r
- }\r
- else\r
- { //didn't really intersect\r
- for (b = out; b; b = next)\r
- {\r
- next = b->next;\r
- b->next = b->prev = NULL;\r
- Brush_Free(b);\r
- }\r
- return a;\r
- }\r
- return out;\r
-}\r
-\r
-/*\r
-=============\r
-CSG_Subtract\r
-=============\r
-*/\r
-void CSG_Subtract (void)\r
-{\r
- brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext;\r
- brush_t fragmentlist;\r
- int i, numfragments, numbrushes;\r
-\r
- Sys_Printf ("Subtracting...\n");\r
-\r
- if (selected_brushes.next == &selected_brushes)\r
- {\r
- Sys_Printf("No brushes selected.\n");\r
- return;\r
- }\r
-\r
- fragmentlist.next = &fragmentlist;\r
- fragmentlist.prev = &fragmentlist;\r
-\r
- numfragments = 0;\r
- numbrushes = 0;\r
- for (b = selected_brushes.next ; b != &selected_brushes ; b=next)\r
- {\r
- next = b->next;\r
-\r
- if (b->owner->eclass->fixedsize)\r
- continue; // can't use texture from a fixed entity, so don't subtract\r
-\r
- // chop all fragments further up\r
- for (s = fragmentlist.next; s != &fragmentlist; s = snext)\r
- {\r
- snext = s->next;\r
-\r
- for (i=0 ; i<3 ; i++)\r
- if (b->mins[i] >= s->maxs[i] - ON_EPSILON \r
- || b->maxs[i] <= s->mins[i] + ON_EPSILON)\r
- break;\r
- if (i != 3)\r
- continue; // definately don't touch\r
- fragments = Brush_Subtract(s, b);\r
- // if the brushes did not really intersect\r
- if (fragments == s)\r
- continue;\r
- // try to merge fragments\r
- fragments = Brush_MergeListPairs(fragments, true);\r
- // add the fragments to the list\r
- for (frag = fragments; frag; frag = nextfragment)\r
- {\r
- nextfragment = frag->next;\r
- frag->next = NULL;\r
- frag->owner = s->owner;\r
- Brush_AddToList(frag, &fragmentlist);\r
- }\r
- // free the original brush\r
- Brush_Free(s);\r
- }\r
-\r
- // chop any active brushes up\r
- for (s = active_brushes.next; s != &active_brushes; s = snext)\r
- {\r
- snext = s->next;\r
-\r
- if (s->owner->eclass->fixedsize || s->patchBrush || s->bFiltered)\r
- continue;\r
-\r
- if (s->brush_faces->pShader->getFlags() & QER_NOCARVE)\r
- {\r
- continue;\r
- }\r
-\r
- for (i=0 ; i<3 ; i++)\r
- if (b->mins[i] >= s->maxs[i] - ON_EPSILON \r
- || b->maxs[i] <= s->mins[i] + ON_EPSILON)\r
- break;\r
- if (i != 3)\r
- continue; // definately don't touch\r
-\r
- fragments = Brush_Subtract(s, b);\r
- // if the brushes did not really intersect\r
- if (fragments == s)\r
- continue;\r
- //\r
- Undo_AddBrush(s);\r
- // one extra brush chopped up\r
- numbrushes++;\r
- // try to merge fragments\r
- fragments = Brush_MergeListPairs(fragments, true);\r
- // add the fragments to the list\r
- for (frag = fragments; frag; frag = nextfragment)\r
- {\r
- nextfragment = frag->next;\r
- frag->next = NULL;\r
- frag->owner = s->owner;\r
- Brush_AddToList(frag, &fragmentlist);\r
- }\r
- // free the original brush\r
- Brush_Free(s);\r
- }\r
- }\r
-\r
- // move all fragments to the active brush list\r
- for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)\r
- {\r
- nextfragment = frag->next;\r
- numfragments++;\r
- Brush_RemoveFromList(frag);\r
- Brush_AddToList(frag, &active_brushes);\r
- Undo_EndBrush(frag);\r
- }\r
-\r
- /*if (numfragments == 0)\r
- {\r
- Sys_Printf("Selected brush%s did not intersect with any other brushes.\n",\r
- (selected_brushes.next->next == &selected_brushes) ? "":"es");\r
- return;\r
- }*/\r
- Sys_Printf("done. (created %d fragment%s out of %d brush%s)\n", numfragments, (numfragments == 1)?"":"s",\r
- numbrushes, (numbrushes == 1)?"":"es");\r
- Sys_UpdateWindows(W_ALL);\r
-}\r
-\r
-/*\r
-=============\r
-CSG_Merge\r
-=============\r
-*/\r
-void CSG_Merge(void)\r
-{\r
- brush_t *b, *next, *newlist, *newbrush;\r
- struct entity_s *owner;\r
-\r
- Sys_Printf ("Merging...\n");\r
-\r
- if (selected_brushes.next == &selected_brushes)\r
- {\r
- Sys_Printf("No brushes selected.\n");\r
- return;\r
- }\r
-\r
- if (selected_brushes.next->next == &selected_brushes)\r
- {\r
- Sys_Printf("At least two brushes have to be selected.\n");\r
- return;\r
- }\r
-\r
- owner = selected_brushes.next->owner;\r
-\r
- for (b = selected_brushes.next; b != &selected_brushes; b = next)\r
- {\r
- next = b->next;\r
-\r
- if (b->owner->eclass->fixedsize)\r
- {\r
- // can't use texture from a fixed entity, so don't subtract\r
- Sys_Printf("Cannot add fixed size entities.\n");\r
- return;\r
- }\r
-\r
- if (b->patchBrush)\r
- {\r
- Sys_Printf("Cannot add patches.\n");\r
- return;\r
- }\r
-\r
- // TTimo: cleanup\r
- // disable the qer_nocarve for CSG-MERGE operations\r
-#if 0\r
- if (b->brush_faces->d_texture->bFromShader && (b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE))\r
- {\r
- Sys_Printf("Cannot add brushes using shaders that don't allows CSG operations.\n");\r
- return;\r
- }\r
-#endif\r
-\r
- if (b->owner != owner)\r
- {\r
- Sys_Printf("Cannot add brushes from different entities.\n");\r
- return;\r
- }\r
-\r
- }\r
-\r
- newlist = NULL;\r
- for (b = selected_brushes.next; b != &selected_brushes; b = next)\r
- {\r
- next = b->next;\r
-\r
- Brush_RemoveFromList(b);\r
- b->next = newlist;\r
- b->prev = NULL;\r
- newlist = b;\r
- }\r
-\r
- newbrush = Brush_MergeList(newlist, true);\r
- // if the new brush would not be convex\r
- if (!newbrush)\r
- {\r
- // add the brushes back into the selection\r
- for (b = newlist; b; b = next)\r
- {\r
- next = b->next;\r
- b->next = NULL;\r
- b->prev = NULL;\r
- Brush_AddToList(b, &selected_brushes);\r
- }\r
- Sys_Printf("Cannot add a set of brushes with a concave hull.\n");\r
- return;\r
- }\r
- // free the original brushes\r
- for (b = newlist; b; b = next)\r
- {\r
- next = b->next;\r
- b->next = NULL;\r
- b->prev = NULL;\r
- Brush_Free(b);\r
- }\r
-\r
- newbrush->bFiltered = FilterBrush(newbrush); // spog - set filters for the new brush\r
-\r
- Brush_AddToList(newbrush, &selected_brushes);\r
-\r
- Sys_Printf ("done.\n");\r
- Sys_UpdateWindows (W_ALL);\r
-}\r
+/*
+ Copyright (C) 1999-2006 Id Software, Inc. and contributors.
+ For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+ This file is part of GtkRadiant.
+
+ GtkRadiant is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ GtkRadiant is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GtkRadiant; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "csg.h"
+
+#include "debugging/debugging.h"
+
+#include <list>
+
+#include "map.h"
+#include "brushmanip.h"
+#include "brushnode.h"
+#include "grid.h"
+
+void Face_makeBrush( Face& face, const Brush& brush, brush_vector_t& out, float offset ){
+ if ( face.contributes() ) {
+ out.push_back( new Brush( brush ) );
+ Face* newFace = out.back()->addFace( face );
+ if ( newFace != 0 ) {
+ newFace->flipWinding();
+ newFace->getPlane().offset( offset );
+ newFace->planeChanged();
+ }
+ }
+}
+
+class FaceMakeBrush
+{
+const Brush& brush;
+brush_vector_t& out;
+float offset;
+public:
+FaceMakeBrush( const Brush& brush, brush_vector_t& out, float offset )
+ : brush( brush ), out( out ), offset( offset ){
+}
+void operator()( Face& face ) const {
+ Face_makeBrush( face, brush, out, offset );
+}
+};
+
+void Brush_makeHollow( const Brush& brush, brush_vector_t& out, float offset ){
+ Brush_forEachFace( brush, FaceMakeBrush( brush, out, offset ) );
+}
+
+class BrushHollowSelectedWalker : public scene::Graph::Walker
+{
+float m_offset;
+public:
+BrushHollowSelectedWalker( float offset )
+ : m_offset( offset ){
+}
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ if ( path.top().get().visible() ) {
+ Brush* brush = Node_getBrush( path.top() );
+ if ( brush != 0
+ && Instance_getSelectable( instance )->isSelected()
+ && path.size() > 1 ) {
+ brush_vector_t out;
+ Brush_makeHollow( *brush, out, m_offset );
+ for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
+ {
+ ( *i )->removeEmptyFaces();
+ NodeSmartReference node( ( new BrushNode() )->node() );
+ Node_getBrush( node )->copy( *( *i ) );
+ delete ( *i );
+ Node_getTraversable( path.parent() )->insert( node );
+ }
+ }
+ }
+ return true;
+}
+};
+
+typedef std::list<Brush*> brushlist_t;
+
+class BrushGatherSelected : public scene::Graph::Walker
+{
+brush_vector_t& m_brushlist;
+public:
+BrushGatherSelected( brush_vector_t& brushlist )
+ : m_brushlist( brushlist ){
+}
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ if ( path.top().get().visible() ) {
+ Brush* brush = Node_getBrush( path.top() );
+ if ( brush != 0
+ && Instance_getSelectable( instance )->isSelected() ) {
+ m_brushlist.push_back( brush );
+ }
+ }
+ return true;
+}
+};
+
+class BrushDeleteSelected : public scene::Graph::Walker
+{
+public:
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ return true;
+}
+void post( const scene::Path& path, scene::Instance& instance ) const {
+ if ( path.top().get().visible() ) {
+ Brush* brush = Node_getBrush( path.top() );
+ if ( brush != 0
+ && Instance_getSelectable( instance )->isSelected()
+ && path.size() > 1 ) {
+ Path_deleteTop( path );
+ }
+ }
+}
+};
+
+void Scene_BrushMakeHollow_Selected( scene::Graph& graph ){
+ GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize() ) );
+ GlobalSceneGraph().traverse( BrushDeleteSelected() );
+}
+
+/*
+ =============
+ CSG_MakeHollow
+ =============
+ */
+
+void CSG_MakeHollow( void ){
+ UndoableCommand undo( "brushHollow" );
+
+ Scene_BrushMakeHollow_Selected( GlobalSceneGraph() );
+
+ SceneChangeNotify();
+}
+
+template<typename Type>
+class RemoveReference
+{
+public:
+typedef Type type;
+};
+
+template<typename Type>
+class RemoveReference<Type&>
+{
+public:
+typedef Type type;
+};
+
+template<typename Functor>
+class Dereference
+{
+const Functor& functor;
+public:
+typedef typename RemoveReference<typename Functor::first_argument_type>::type* first_argument_type;
+typedef typename Functor::result_type result_type;
+Dereference( const Functor& functor ) : functor( functor ){
+}
+result_type operator()( first_argument_type firstArgument ) const {
+ return functor( *firstArgument );
+}
+};
+
+template<typename Functor>
+inline Dereference<Functor> makeDereference( const Functor& functor ){
+ return Dereference<Functor>( functor );
+}
+
+typedef Face* FacePointer;
+const FacePointer c_nullFacePointer = 0;
+
+template<typename Predicate>
+Face* Brush_findIf( const Brush& brush, const Predicate& predicate ){
+ Brush::const_iterator i = std::find_if( brush.begin(), brush.end(), makeDereference( predicate ) );
+ return i == brush.end() ? c_nullFacePointer : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
+}
+
+template<typename Caller>
+class BindArguments1
+{
+typedef typename Caller::second_argument_type FirstBound;
+FirstBound firstBound;
+public:
+typedef typename Caller::result_type result_type;
+typedef typename Caller::first_argument_type first_argument_type;
+BindArguments1( FirstBound firstBound )
+ : firstBound( firstBound ){
+}
+result_type operator()( first_argument_type firstArgument ) const {
+ return Caller::call( firstArgument, firstBound );
+}
+};
+
+template<typename Caller>
+class BindArguments2
+{
+typedef typename Caller::second_argument_type FirstBound;
+typedef typename Caller::third_argument_type SecondBound;
+FirstBound firstBound;
+SecondBound secondBound;
+public:
+typedef typename Caller::result_type result_type;
+typedef typename Caller::first_argument_type first_argument_type;
+BindArguments2( FirstBound firstBound, SecondBound secondBound )
+ : firstBound( firstBound ), secondBound( secondBound ){
+}
+result_type operator()( first_argument_type firstArgument ) const {
+ return Caller::call( firstArgument, firstBound, secondBound );
+}
+};
+
+template<typename Caller, typename FirstBound, typename SecondBound>
+BindArguments2<Caller> bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){
+ return BindArguments2<Caller>( firstBound, secondBound );
+}
+
+inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){
+ return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped );
+}
+typedef Function3<const Face&, const Plane3&, bool, bool, Face_testPlane> FaceTestPlane;
+
+
+
+/// \brief Returns true if
+/// \li !flipped && brush is BACK or ON
+/// \li flipped && brush is FRONT or ON
+bool Brush_testPlane( const Brush& brush, const Plane3& plane, bool flipped ){
+ brush.evaluateBRep();
+#if 1
+ for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
+ {
+ if ( Face_testPlane( *( *i ), plane, flipped ) ) {
+ return false;
+ }
+ }
+ return true;
+#else
+ return Brush_findIf( brush, bindArguments( FaceTestPlane(), makeReference( plane ), flipped ) ) == 0;
+#endif
+}
+
+brushsplit_t Brush_classifyPlane( const Brush& brush, const Plane3& plane ){
+ brush.evaluateBRep();
+ brushsplit_t split;
+ for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
+ {
+ if ( ( *i )->contributes() ) {
+ split += Winding_ClassifyPlane( ( *i )->getWinding(), plane );
+ }
+ }
+ return split;
+}
+
+bool Brush_subtract( const Brush& brush, const Brush& other, brush_vector_t& ret_fragments ){
+ if ( aabb_intersects_aabb( brush.localAABB(), other.localAABB() ) ) {
+ brush_vector_t fragments;
+ fragments.reserve( other.size() );
+ Brush back( brush );
+
+ for ( Brush::const_iterator i( other.begin() ); i != other.end(); ++i )
+ {
+ if ( ( *i )->contributes() ) {
+ brushsplit_t split = Brush_classifyPlane( back, ( *i )->plane3() );
+ if ( split.counts[ePlaneFront] != 0
+ && split.counts[ePlaneBack] != 0 ) {
+ fragments.push_back( new Brush( back ) );
+ Face* newFace = fragments.back()->addFace( *( *i ) );
+ if ( newFace != 0 ) {
+ newFace->flipWinding();
+ }
+ back.addFace( *( *i ) );
+ }
+ else if ( split.counts[ePlaneBack] == 0 ) {
+ for ( brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i )
+ {
+ delete( *i );
+ }
+ return false;
+ }
+ }
+ }
+ ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() );
+ return true;
+ }
+ return false;
+}
+
+class SubtractBrushesFromUnselected : public scene::Graph::Walker
+{
+const brush_vector_t& m_brushlist;
+std::size_t& m_before;
+std::size_t& m_after;
+public:
+SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after )
+ : m_brushlist( brushlist ), m_before( before ), m_after( after ){
+}
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ return true;
+}
+void post( const scene::Path& path, scene::Instance& instance ) const {
+ if ( path.top().get().visible() ) {
+ Brush* brush = Node_getBrush( path.top() );
+ if ( brush != 0
+ && !Instance_getSelectable( instance )->isSelected() ) {
+ brush_vector_t buffer[2];
+ bool swap = false;
+ Brush* original = new Brush( *brush );
+ buffer[static_cast<std::size_t>( swap )].push_back( original );
+
+ {
+ for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
+ {
+ for ( brush_vector_t::iterator j( buffer[static_cast<std::size_t>( swap )].begin() ); j != buffer[static_cast<std::size_t>( swap )].end(); ++j )
+ {
+ if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
+ delete ( *j );
+ }
+ else
+ {
+ buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
+ }
+ }
+ buffer[static_cast<std::size_t>( swap )].clear();
+ swap = !swap;
+ }
+ }
+
+ brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];
+
+ if ( out.size() == 1 && out.back() == original ) {
+ delete original;
+ }
+ else
+ {
+ ++m_before;
+ for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
+ {
+ ++m_after;
+ ( *i )->removeEmptyFaces();
+ if ( !( *i )->empty() ) {
+ NodeSmartReference node( ( new BrushNode() )->node() );
+ Node_getBrush( node )->copy( *( *i ) );
+ delete ( *i );
+ Node_getTraversable( path.parent() )->insert( node );
+ }
+ else{
+ delete ( *i );
+ }
+ }
+ Path_deleteTop( path );
+ }
+ }
+ }
+}
+};
+
+void CSG_Subtract(){
+ brush_vector_t selected_brushes;
+ GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
+
+ if ( selected_brushes.empty() ) {
+ globalOutputStream() << "CSG Subtract: No brushes selected.\n";
+ }
+ else
+ {
+ globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n";
+
+ UndoableCommand undo( "brushSubtract" );
+
+ // subtract selected from unselected
+ std::size_t before = 0;
+ std::size_t after = 0;
+ GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) );
+ globalOutputStream() << "CSG Subtract: Result: "
+ << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" )
+ << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n";
+
+ SceneChangeNotify();
+ }
+}
+
+class BrushSplitByPlaneSelected : public scene::Graph::Walker
+{
+const Vector3& m_p0;
+const Vector3& m_p1;
+const Vector3& m_p2;
+const char* m_shader;
+const TextureProjection& m_projection;
+EBrushSplit m_split;
+public:
+BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split )
+ : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){
+}
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ return true;
+}
+void post( const scene::Path& path, scene::Instance& instance ) const {
+ if ( path.top().get().visible() ) {
+ Brush* brush = Node_getBrush( path.top() );
+ if ( brush != 0
+ && Instance_getSelectable( instance )->isSelected() ) {
+ Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
+ if ( plane3_valid( plane ) ) {
+ brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane );
+ if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) {
+ // the plane intersects this brush
+ if ( m_split == eFrontAndBack ) {
+ NodeSmartReference node( ( new BrushNode() )->node() );
+ Brush* fragment = Node_getBrush( node );
+ fragment->copy( *brush );
+ Face* newFace = fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
+ if ( newFace != 0 && m_split != eFront ) {
+ newFace->flipWinding();
+ }
+ fragment->removeEmptyFaces();
+ ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" );
+
+ Node_getTraversable( path.parent() )->insert( node );
+ {
+ scene::Path fragmentPath = path;
+ fragmentPath.top() = makeReference( node.get() );
+ selectPath( fragmentPath, true );
+ }
+ }
+
+ Face* newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
+ if ( newFace != 0 && m_split == eFront ) {
+ newFace->flipWinding();
+ }
+ brush->removeEmptyFaces();
+ ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" );
+ }
+ else
+ // the plane does not intersect this brush
+ if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) {
+ // the brush is "behind" the plane
+ Path_deleteTop( path );
+ }
+ }
+ }
+ }
+}
+};
+
+void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split ){
+ TextureProjection projection;
+ TexDef_Construct_Default( projection );
+ graph.traverse( BrushSplitByPlaneSelected( p0, p1, p2, shader, projection, split ) );
+ SceneChangeNotify();
+}
+
+
+class BrushInstanceSetClipPlane : public scene::Graph::Walker
+{
+Plane3 m_plane;
+public:
+BrushInstanceSetClipPlane( const Plane3& plane )
+ : m_plane( plane ){
+}
+bool pre( const scene::Path& path, scene::Instance& instance ) const {
+ BrushInstance* brush = Instance_getBrush( instance );
+ if ( brush != 0
+ && path.top().get().visible()
+ && brush->isSelected() ) {
+ BrushInstance& brushInstance = *brush;
+ brushInstance.setClipPlane( m_plane );
+ }
+ return true;
+}
+};
+
+void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
+ graph.traverse( BrushInstanceSetClipPlane( plane ) );
+}
+
+/*
+ =============
+ CSG_Merge
+ =============
+ */
+bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
+ // gather potential outer faces
+
+ {
+ typedef std::vector<const Face*> Faces;
+ Faces faces;
+ for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i )
+ {
+ ( *i )->evaluateBRep();
+ for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j )
+ {
+ if ( !( *j )->contributes() ) {
+ continue;
+ }
+
+ const Face& face1 = *( *j );
+
+ bool skip = false;
+ // test faces of all input brushes
+ //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
+ for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k )
+ {
+ if ( k != i ) { // don't test a brush against itself
+ for ( Brush::const_iterator l( ( *k )->begin() ); !skip && l != ( *k )->end(); ++l )
+ {
+ const Face& face2 = *( *l );
+
+ // face opposes another face
+ if ( plane3_opposing( face1.plane3(), face2.plane3() ) ) {
+ // skip opposing planes
+ skip = true;
+ break;
+ }
+ }
+ }
+ }
+
+ // check faces already stored
+ for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m )
+ {
+ const Face& face2 = *( *m );
+
+ // face equals another face
+ if ( plane3_equal( face1.plane3(), face2.plane3() ) ) {
+ //if the texture/shader references should be the same but are not
+ if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) {
+ return false;
+ }
+ // skip duplicate planes
+ skip = true;
+ break;
+ }
+
+ // face1 plane intersects face2 winding or vice versa
+ if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) {
+ // result would not be convex
+ return false;
+ }
+ }
+
+ if ( !skip ) {
+ faces.push_back( &face1 );
+ }
+ }
+ }
+ for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
+ {
+ if ( !brush.addFace( *( *i ) ) ) {
+ // result would have too many sides
+ return false;
+ }
+ }
+ }
+
+ brush.removeEmptyFaces();
+
+ return true;
+}
+
+void CSG_Merge( void ){
+ brush_vector_t selected_brushes;
+
+ // remove selected
+ GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
+
+ if ( selected_brushes.empty() ) {
+ globalOutputStream() << "CSG Merge: No brushes selected.\n";
+ return;
+ }
+
+ if ( selected_brushes.size() < 2 ) {
+ globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
+ return;
+ }
+
+ globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n";
+
+ UndoableCommand undo( "brushMerge" );
+
+ scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
+
+ NodeSmartReference node( ( new BrushNode() )->node() );
+ Brush* brush = Node_getBrush( node );
+ // if the new brush would not be convex
+ if ( !Brush_merge( *brush, selected_brushes, true ) ) {
+ globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
+ }
+ else
+ {
+ ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" );
+
+ // free the original brushes
+ GlobalSceneGraph().traverse( BrushDeleteSelected() );
+
+ merged_path.pop();
+ Node_getTraversable( merged_path.top() )->insert( node );
+ merged_path.push( makeReference( node.get() ) );
+
+ selectPath( merged_path, true );
+
+ globalOutputStream() << "CSG Merge: Succeeded.\n";
+ SceneChangeNotify();
+ }
+}