-/*\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-2007 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 "stdafx.h"
+#include "winding.h"
+#include "filters.h"
+
+/*
+=============
+CSG_MakeHollow
+=============
+*/
+
+void Brush_Scale(brush_t* b)
+{
+ for (face_t* f = b->brush_faces ; f ; f=f->next)
+ {
+ for (int i=0 ; i<3 ; i++)
+ {
+ VectorScale (f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i]);
+ }
+ }
+}
+
+void CSG_MakeHollow (void)
+{
+ brush_t *b, *front, *back, *next;
+ face_t *f;
+ face_t split;
+ vec3_t move;
+ int i;
+
+ for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
+ {
+ next = b->next;
+
+ if (b->owner->eclass->fixedsize || b->patchBrush || b->bFiltered)
+ continue;
+
+ for (f = b->brush_faces ; f ; f=f->next)
+ {
+ split = *f;
+ VectorScale (f->plane.normal, g_qeglobals.d_gridsize, move);
+ for (i=0 ; i<3 ; i++)
+ VectorSubtract (split.planepts[i], move, split.planepts[i]);
+
+ Brush_SplitBrushByFace (b, &split, &front, &back);
+ if (back)
+ Brush_Free (back);
+ if (front)
+ Brush_AddToList (front, &selected_brushes);
+ }
+ Brush_Free (b);
+ }
+ Sys_UpdateWindows (W_ALL);
+}
+
+/*
+=============
+Brush_Merge
+
+ Returns a new brush that is created by merging brush1 and brush2.
+ May return NULL if brush1 and brush2 do not create a convex brush when merged.
+ The input brushes brush1 and brush2 stay intact.
+
+ if onlyshape is true then the merge is allowed based on the shape only
+ otherwise the texture/shader references of faces in the same plane have to
+ be the same as well.
+=============
+*/
+brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)
+{
+ int i, shared;
+ brush_t *newbrush;
+ face_t *face1, *face2, *newface, *f;
+
+ // check for bounding box overlapp
+ for (i = 0; i < 3; i++)
+ {
+ if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
+ || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)
+ {
+ // never merge if the brushes overlap
+ return NULL;
+ }
+ }
+ //
+ shared = 0;
+ // check if the new brush would be convex... flipped planes make a brush non-convex
+ for (face1 = brush1->brush_faces; face1; face1 = face1->next)
+ {
+ // don't check the faces of brush 1 and 2 touching each other
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ if (Plane_Equal(&face1->plane, &face2->plane, true))
+ {
+ shared++;
+ // there may only be ONE shared side
+ if (shared > 1)
+ return NULL;
+ break;
+ }
+ }
+ // if this face plane is shared
+ if (face2) continue;
+ //
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ // don't check the faces of brush 1 and 2 touching each other
+ for (f = brush1->brush_faces; f; f = f->next)
+ {
+ if (Plane_Equal(&face2->plane, &f->plane, true)) break;
+ }
+ if (f)
+ continue;
+ //
+ if (Plane_Equal(&face1->plane, &face2->plane, false))
+ {
+ //if the texture/shader references should be the same but are not
+ if (!onlyshape && stricmp(face1->texdef.GetName(), face2->texdef.GetName()) != 0) return NULL;
+ continue;
+ }
+ //
+ if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
+ face1->plane.normal, face2->plane.normal,
+ face1->plane.dist, face2->plane.dist))
+ {
+ return NULL;
+ } //end if
+ } //end for
+ } //end for
+ //
+ newbrush = Brush_Alloc();
+ //
+ for (face1 = brush1->brush_faces; face1; face1 = face1->next)
+ {
+ // don't add the faces of brush 1 and 2 touching each other
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ if (Plane_Equal(&face1->plane, &face2->plane, true))
+ break;
+ }
+ if (face2)
+ continue;
+ // don't add faces with the same plane twice
+ for (f = newbrush->brush_faces; f; f = f->next)
+ {
+ if (Plane_Equal(&face1->plane, &f->plane, false))
+ break;
+ if (Plane_Equal(&face1->plane, &f->plane, true))
+ break;
+ }
+ if (f)
+ continue;
+ //
+ newface = Face_Alloc();
+ newface->texdef = face1->texdef;
+ VectorCopy(face1->planepts[0], newface->planepts[0]);
+ VectorCopy(face1->planepts[1], newface->planepts[1]);
+ VectorCopy(face1->planepts[2], newface->planepts[2]);
+ newface->plane = face1->plane;
+ newface->next = newbrush->brush_faces;
+ newbrush->brush_faces = newface;
+ }
+ //
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ // don't add the faces of brush 1 and 2 touching each other
+ for (face1 = brush1->brush_faces; face1; face1 = face1->next)
+ {
+ if (Plane_Equal(&face2->plane, &face1->plane, true))
+ break;
+ }
+ if (face1)
+ continue;
+ // don't add faces with the same plane twice
+ for (f = newbrush->brush_faces; f; f = f->next)
+ {
+ if (Plane_Equal(&face2->plane, &f->plane, false))
+ break;
+ if (Plane_Equal(&face2->plane, &f->plane, true))
+ break;
+ }
+ if (f)
+ continue;
+ //
+ newface = Face_Alloc();
+ newface->texdef = face2->texdef;
+ VectorCopy(face2->planepts[0], newface->planepts[0]);
+ VectorCopy(face2->planepts[1], newface->planepts[1]);
+ VectorCopy(face2->planepts[2], newface->planepts[2]);
+ newface->plane = face2->plane;
+ newface->next = newbrush->brush_faces;
+ newbrush->brush_faces = newface;
+ }
+ // link the new brush to an entity
+ Entity_LinkBrush (brush1->owner, newbrush);
+ // build windings for the faces
+ Brush_BuildWindings( newbrush, false);
+
+ return newbrush;
+}
+
+/*
+=============
+Brush_MergeListPairs
+
+ Returns a list with merged brushes.
+ Tries to merge brushes pair wise.
+ The input list is destroyed.
+ Input and output should be a single linked list using .next
+=============
+*/
+brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)
+{
+ int nummerges, merged;
+ brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
+ brush_t *lastb2;
+
+ if (!brushlist) return NULL;
+
+ nummerges = 0;
+ do
+ {
+ for (tail = brushlist; tail; tail = tail->next)
+ {
+ if (!tail->next) break;
+ }
+ merged = 0;
+ newbrushlist = NULL;
+ for (b1 = brushlist; b1; b1 = brushlist)
+ {
+ lastb2 = b1;
+ for (b2 = b1->next; b2; b2 = b2->next)
+ {
+ newbrush = Brush_Merge(b1, b2, onlyshape);
+ if (newbrush)
+ {
+ tail->next = newbrush;
+ lastb2->next = b2->next;
+ brushlist = brushlist->next;
+ b1->next = b1->prev = NULL;
+ b2->next = b2->prev = NULL;
+ Brush_Free(b1);
+ Brush_Free(b2);
+ for (tail = brushlist; tail; tail = tail->next)
+ {
+ if (!tail->next) break;
+ } //end for
+ merged++;
+ nummerges++;
+ break;
+ }
+ lastb2 = b2;
+ }
+ //if b1 can't be merged with any of the other brushes
+ if (!b2)
+ {
+ brushlist = brushlist->next;
+ //keep b1
+ b1->next = newbrushlist;
+ newbrushlist = b1;
+ }
+ }
+ brushlist = newbrushlist;
+ } while(merged);
+ return newbrushlist;
+}
+
+/*
+=============
+Brush_MergeList
+
+ Tries to merge all brushes in the list into one new brush.
+ The input brush list stays intact.
+ Returns NULL if no merged brush can be created.
+ To create a new brush the brushes in the list may not overlap and
+ the outer faces of the brushes together should make a new convex brush.
+
+ if onlyshape is true then the merge is allowed based on the shape only
+ otherwise the texture/shader references of faces in the same plane have to
+ be the same as well.
+=============
+*/
+brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)
+{
+ brush_t *brush1, *brush2, *brush3, *newbrush;
+ face_t *face1, *face2, *face3, *newface, *f;
+
+ if (!brushlist) return NULL;
+ for (brush1 = brushlist; brush1; brush1 = brush1->next)
+ {
+ // check if the new brush would be convex... flipped planes make a brush concave
+ for (face1 = brush1->brush_faces; face1; face1 = face1->next)
+ {
+ // don't check face1 if it touches another brush
+ for (brush2 = brushlist; brush2; brush2 = brush2->next)
+ {
+ if (brush2 == brush1) continue;
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ if (Plane_Equal(&face1->plane, &face2->plane, true))
+ {
+ break;
+ }
+ }
+ if (face2) break;
+ }
+ // if face1 touches another brush
+ if (brush2) continue;
+ //
+ for (brush2 = brush1->next; brush2; brush2 = brush2->next)
+ {
+ // don't check the faces of brush 2 touching another brush
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ for (brush3 = brushlist; brush3; brush3 = brush3->next)
+ {
+ if (brush3 == brush2) continue;
+ for (face3 = brush3->brush_faces; face3; face3 = face3->next)
+ {
+ if (Plane_Equal(&face2->plane, &face3->plane, true)) break;
+ }
+ if (face3) break;
+ }
+ // if face2 touches another brush
+ if (brush3) continue;
+ //
+ if (Plane_Equal(&face1->plane, &face2->plane, false))
+ {
+ //if the texture/shader references should be the same but are not
+ if (!onlyshape && stricmp(face1->texdef.GetName(), face2->texdef.GetName()) != 0) return NULL;
+ continue;
+ }
+ //
+ if (Winding_PlanesConcave(face1->face_winding, face2->face_winding,
+ face1->plane.normal, face2->plane.normal,
+ face1->plane.dist, face2->plane.dist))
+ {
+ return NULL;
+ }
+ }
+ }
+ }
+ }
+ //
+ newbrush = Brush_Alloc();
+ //
+ for (brush1 = brushlist; brush1; brush1 = brush1->next)
+ {
+ for (face1 = brush1->brush_faces; face1; face1 = face1->next)
+ {
+ // don't add face1 to the new brush if it touches another brush
+ for (brush2 = brushlist; brush2; brush2 = brush2->next)
+ {
+ if (brush2 == brush1) continue;
+ for (face2 = brush2->brush_faces; face2; face2 = face2->next)
+ {
+ if (Plane_Equal(&face1->plane, &face2->plane, true))
+ {
+ break;
+ }
+ }
+ if (face2) break;
+ }
+ if (brush2) continue;
+ // don't add faces with the same plane twice
+ for (f = newbrush->brush_faces; f; f = f->next)
+ {
+ if (Plane_Equal(&face1->plane, &f->plane, false))
+ break;
+ if (Plane_Equal(&face1->plane, &f->plane, true))
+ break;
+ }
+ if (f)
+ continue;
+ //
+ newface = Face_Alloc();
+ newface->texdef = face1->texdef;
+ VectorCopy(face1->planepts[0], newface->planepts[0]);
+ VectorCopy(face1->planepts[1], newface->planepts[1]);
+ VectorCopy(face1->planepts[2], newface->planepts[2]);
+ newface->plane = face1->plane;
+ newface->next = newbrush->brush_faces;
+ newbrush->brush_faces = newface;
+ }
+ }
+ // link the new brush to an entity
+ Entity_LinkBrush (brushlist->owner, newbrush);
+ // build windings for the faces
+ Brush_BuildWindings( newbrush, false);
+
+ return newbrush;
+}
+
+/*
+=============
+Brush_Subtract
+
+ Returns a list of brushes that remain after B is subtracted from A.
+ May by empty if A is contained inside B.
+ The originals are undisturbed.
+=============
+*/
+brush_t *Brush_Subtract(brush_t *a, brush_t *b)
+{
+ // a - b = out (list)
+ brush_t *front, *back;
+ brush_t *in, *out, *next;
+ face_t *f;
+
+ in = a;
+ out = NULL;
+ for (f = b->brush_faces; f && in; f = f->next)
+ {
+ Brush_SplitBrushByFace(in, f, &front, &back);
+ if (in != a) Brush_Free(in);
+ if (front)
+ { // add to list
+ front->next = out;
+ out = front;
+ }
+ in = back;
+ }
+ //NOTE: in != a just in case brush b has no faces
+ if (in && in != a)
+ {
+ Brush_Free(in);
+ }
+ else
+ { //didn't really intersect
+ for (b = out; b; b = next)
+ {
+ next = b->next;
+ b->next = b->prev = NULL;
+ Brush_Free(b);
+ }
+ return a;
+ }
+ return out;
+}
+
+/*
+=============
+CSG_Subtract
+=============
+*/
+void CSG_Subtract (void)
+{
+ brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
+ brush_t fragmentlist;
+ int i, numfragments, numbrushes;
+
+ Sys_Printf ("Subtracting...\n");
+
+ if (selected_brushes.next == &selected_brushes)
+ {
+ Sys_Printf("No brushes selected.\n");
+ return;
+ }
+
+ fragmentlist.next = &fragmentlist;
+ fragmentlist.prev = &fragmentlist;
+
+ numfragments = 0;
+ numbrushes = 0;
+ for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
+ {
+ next = b->next;
+
+ if (b->owner->eclass->fixedsize)
+ continue; // can't use texture from a fixed entity, so don't subtract
+
+ // chop all fragments further up
+ for (s = fragmentlist.next; s != &fragmentlist; s = snext)
+ {
+ snext = s->next;
+
+ for (i=0 ; i<3 ; i++)
+ if (b->mins[i] >= s->maxs[i] - ON_EPSILON
+ || b->maxs[i] <= s->mins[i] + ON_EPSILON)
+ break;
+ if (i != 3)
+ continue; // definately don't touch
+ fragments = Brush_Subtract(s, b);
+ // if the brushes did not really intersect
+ if (fragments == s)
+ continue;
+ // try to merge fragments
+ fragments = Brush_MergeListPairs(fragments, true);
+ // add the fragments to the list
+ for (frag = fragments; frag; frag = nextfragment)
+ {
+ nextfragment = frag->next;
+ frag->next = NULL;
+ frag->owner = s->owner;
+ Brush_AddToList(frag, &fragmentlist);
+ }
+ // free the original brush
+ Brush_Free(s);
+ }
+
+ // chop any active brushes up
+ for (s = active_brushes.next; s != &active_brushes; s = snext)
+ {
+ snext = s->next;
+
+ if (s->owner->eclass->fixedsize || s->patchBrush || s->bFiltered)
+ continue;
+
+ if (s->brush_faces->pShader->getFlags() & QER_NOCARVE)
+ {
+ continue;
+ }
+
+ for (i=0 ; i<3 ; i++)
+ if (b->mins[i] >= s->maxs[i] - ON_EPSILON
+ || b->maxs[i] <= s->mins[i] + ON_EPSILON)
+ break;
+ if (i != 3)
+ continue; // definately don't touch
+
+ fragments = Brush_Subtract(s, b);
+ // if the brushes did not really intersect
+ if (fragments == s)
+ continue;
+ //
+ Undo_AddBrush(s);
+ // one extra brush chopped up
+ numbrushes++;
+ // try to merge fragments
+ fragments = Brush_MergeListPairs(fragments, true);
+ // add the fragments to the list
+ for (frag = fragments; frag; frag = nextfragment)
+ {
+ nextfragment = frag->next;
+ frag->next = NULL;
+ frag->owner = s->owner;
+ Brush_AddToList(frag, &fragmentlist);
+ }
+ // free the original brush
+ Brush_Free(s);
+ }
+ }
+
+ // move all fragments to the active brush list
+ for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)
+ {
+ nextfragment = frag->next;
+ numfragments++;
+ Brush_RemoveFromList(frag);
+ Brush_AddToList(frag, &active_brushes);
+ Undo_EndBrush(frag);
+ }
+
+ /*if (numfragments == 0)
+ {
+ Sys_Printf("Selected brush%s did not intersect with any other brushes.\n",
+ (selected_brushes.next->next == &selected_brushes) ? "":"es");
+ return;
+ }*/
+ Sys_Printf("done. (created %d fragment%s out of %d brush%s)\n", numfragments, (numfragments == 1)?"":"s",
+ numbrushes, (numbrushes == 1)?"":"es");
+ Sys_UpdateWindows(W_ALL);
+}
+
+/*
+=============
+CSG_Merge
+=============
+*/
+void CSG_Merge(void)
+{
+ brush_t *b, *next, *newlist, *newbrush;
+ struct entity_s *owner;
+
+ Sys_Printf ("Merging...\n");
+
+ if (selected_brushes.next == &selected_brushes)
+ {
+ Sys_Printf("No brushes selected.\n");
+ return;
+ }
+
+ if (selected_brushes.next->next == &selected_brushes)
+ {
+ Sys_Printf("At least two brushes have to be selected.\n");
+ return;
+ }
+
+ owner = selected_brushes.next->owner;
+
+ for (b = selected_brushes.next; b != &selected_brushes; b = next)
+ {
+ next = b->next;
+
+ if (b->owner->eclass->fixedsize)
+ {
+ // can't use texture from a fixed entity, so don't subtract
+ Sys_Printf("Cannot add fixed size entities.\n");
+ return;
+ }
+
+ if (b->patchBrush)
+ {
+ Sys_Printf("Cannot add patches.\n");
+ return;
+ }
+
+ // TTimo: cleanup
+ // disable the qer_nocarve for CSG-MERGE operations
+#if 0
+ if (b->brush_faces->d_texture->bFromShader && (b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE))
+ {
+ Sys_Printf("Cannot add brushes using shaders that don't allows CSG operations.\n");
+ return;
+ }
+#endif
+
+ if (b->owner != owner)
+ {
+ Sys_Printf("Cannot add brushes from different entities.\n");
+ return;
+ }
+
+ }
+
+ newlist = NULL;
+ for (b = selected_brushes.next; b != &selected_brushes; b = next)
+ {
+ next = b->next;
+
+ Brush_RemoveFromList(b);
+ b->next = newlist;
+ b->prev = NULL;
+ newlist = b;
+ }
+
+ newbrush = Brush_MergeList(newlist, true);
+ // if the new brush would not be convex
+ if (!newbrush)
+ {
+ // add the brushes back into the selection
+ for (b = newlist; b; b = next)
+ {
+ next = b->next;
+ b->next = NULL;
+ b->prev = NULL;
+ Brush_AddToList(b, &selected_brushes);
+ }
+ Sys_Printf("Cannot add a set of brushes with a concave hull.\n");
+ return;
+ }
+ // free the original brushes
+ for (b = newlist; b; b = next)
+ {
+ next = b->next;
+ b->next = NULL;
+ b->prev = NULL;
+ Brush_Free(b);
+ }
+
+ newbrush->bFiltered = FilterBrush(newbrush); // spog - set filters for the new brush
+
+ Brush_AddToList(newbrush, &selected_brushes);
+
+ Sys_Printf ("done.\n");
+ Sys_UpdateWindows (W_ALL);
+}