-/*\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 "qbsp.h"\r
-\r
-/*\r
-\r
-tag all brushes with original contents\r
-brushes may contain multiple contents\r
-there will be no brush overlap after csg phase\r
-\r
-\r
-\r
-\r
-each side has a count of the other sides it splits\r
-\r
-the best split will be the one that minimizes the total split counts\r
-of all remaining sides\r
-\r
-precalc side on plane table\r
-\r
-evaluate split side\r
-{\r
-cost = 0\r
-for all sides\r
- for all sides\r
- get \r
- if side splits side and splitside is on same child\r
- cost++;\r
-}\r
-\r
-\r
- */\r
-\r
-void SplitBrush2 (bspbrush_t *brush, int planenum,\r
- bspbrush_t **front, bspbrush_t **back)\r
-{\r
- SplitBrush (brush, planenum, front, back);\r
-#if 0\r
- if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)\r
- (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1\r
- if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)\r
- (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo; // not -1\r
-#endif\r
-}\r
-\r
-/*\r
-===============\r
-SubtractBrush\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
-\r
-The originals are undisturbed.\r
-===============\r
-*/\r
-bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)\r
-{ // a - b = out (list)\r
- int i;\r
- bspbrush_t *front, *back;\r
- bspbrush_t *out, *in;\r
-\r
- in = a;\r
- out = NULL;\r
- for (i=0 ; i<b->numsides && in ; i++)\r
- {\r
- SplitBrush2 (in, b->sides[i].planenum, &front, &back);\r
- if (in != a)\r
- FreeBrush (in);\r
- if (front)\r
- { // add to list\r
- front->next = out;\r
- out = front;\r
- }\r
- in = back;\r
- }\r
- if (in)\r
- FreeBrush (in);\r
- else\r
- { // didn't really intersect\r
- FreeBrushList (out);\r
- return a;\r
- }\r
- return out;\r
-}\r
-\r
-/*\r
-===============\r
-IntersectBrush\r
-\r
-Returns a single brush made up by the intersection of the\r
-two provided brushes, or NULL if they are disjoint.\r
-\r
-The originals are undisturbed.\r
-===============\r
-*/\r
-bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)\r
-{\r
- int i;\r
- bspbrush_t *front, *back;\r
- bspbrush_t *in;\r
-\r
- in = a;\r
- for (i=0 ; i<b->numsides && in ; i++)\r
- {\r
- SplitBrush2 (in, b->sides[i].planenum, &front, &back);\r
- if (in != a)\r
- FreeBrush (in);\r
- if (front)\r
- FreeBrush (front);\r
- in = back;\r
- }\r
-\r
- if (in == a)\r
- return NULL;\r
-\r
- in->next = NULL;\r
- return in;\r
-}\r
-\r
-\r
-/*\r
-===============\r
-BrushesDisjoint\r
-\r
-Returns true if the two brushes definately do not intersect.\r
-There will be false negatives for some non-axial combinations.\r
-===============\r
-*/\r
-qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)\r
-{\r
- int i, j;\r
-\r
- // check bounding boxes\r
- for (i=0 ; i<3 ; i++)\r
- if (a->mins[i] >= b->maxs[i]\r
- || a->maxs[i] <= b->mins[i])\r
- return true; // bounding boxes don't overlap\r
-\r
- // check for opposing planes\r
- for (i=0 ; i<a->numsides ; i++)\r
- {\r
- for (j=0 ; j<b->numsides ; j++)\r
- {\r
- if (a->sides[i].planenum ==\r
- (b->sides[j].planenum^1) )\r
- return true; // opposite planes, so not touching\r
- }\r
- }\r
-\r
- return false; // might intersect\r
-}\r
-\r
-/*\r
-===============\r
-IntersectionContents\r
-\r
-Returns a content word for the intersection of two brushes.\r
-Some combinations will generate a combination (water + clip),\r
-but most will be the stronger of the two contents.\r
-===============\r
-*/\r
-int IntersectionContents (int c1, int c2)\r
-{\r
- int out;\r
-\r
- out = c1 | c2;\r
-\r
- if (out & CONTENTS_SOLID)\r
- out = CONTENTS_SOLID;\r
-\r
- return out;\r
-}\r
-\r
-\r
-int minplanenums[3];\r
-int maxplanenums[3];\r
-\r
-/*\r
-===============\r
-ClipBrushToBox\r
-\r
-Any planes shared with the box edge will be set to no texinfo\r
-===============\r
-*/\r
-bspbrush_t *ClipBrushToBox (bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)\r
-{\r
- int i, j;\r
- bspbrush_t *front, *back;\r
- int p;\r
-\r
- for (j=0 ; j<2 ; j++)\r
- {\r
- if (brush->maxs[j] > clipmaxs[j])\r
- {\r
- SplitBrush (brush, maxplanenums[j], &front, &back);\r
- if (front)\r
- FreeBrush (front);\r
- brush = back;\r
- if (!brush)\r
- return NULL;\r
- }\r
- if (brush->mins[j] < clipmins[j])\r
- {\r
- SplitBrush (brush, minplanenums[j], &front, &back);\r
- if (back)\r
- FreeBrush (back);\r
- brush = front;\r
- if (!brush)\r
- return NULL;\r
- }\r
- }\r
-\r
- // remove any colinear faces\r
-\r
- for (i=0 ; i<brush->numsides ; i++)\r
- {\r
- p = brush->sides[i].planenum & ~1;\r
- if (p == maxplanenums[0] || p == maxplanenums[1] \r
- || p == minplanenums[0] || p == minplanenums[1])\r
- {\r
- brush->sides[i].texinfo = TEXINFO_NODE;\r
- brush->sides[i].visible = false;\r
- }\r
- }\r
- return brush;\r
-}\r
-\r
-/*\r
-===============\r
-MakeBspBrushList \r
-===============\r
-*/\r
-bspbrush_t *MakeBspBrushList (int startbrush, int endbrush,\r
- vec3_t clipmins, vec3_t clipmaxs)\r
-{\r
- mapbrush_t *mb;\r
- bspbrush_t *brushlist, *newbrush;\r
- int i, j;\r
- int c_faces;\r
- int c_brushes;\r
- int numsides;\r
- int vis;\r
- vec3_t normal;\r
- float dist;\r
-\r
- for (i=0 ; i<2 ; i++)\r
- {\r
- VectorClear (normal);\r
- normal[i] = 1;\r
- dist = clipmaxs[i];\r
- maxplanenums[i] = FindFloatPlane (normal, dist);\r
- dist = clipmins[i];\r
- minplanenums[i] = FindFloatPlane (normal, dist);\r
- }\r
-\r
- brushlist = NULL;\r
- c_faces = 0;\r
- c_brushes = 0;\r
-\r
- for (i=startbrush ; i<endbrush ; i++)\r
- {\r
- mb = &mapbrushes[i];\r
-\r
- numsides = mb->numsides;\r
- if (!numsides)\r
- continue;\r
- // make sure the brush has at least one face showing\r
- vis = 0;\r
- for (j=0 ; j<numsides ; j++)\r
- if (mb->original_sides[j].visible && mb->original_sides[j].winding)\r
- vis++;\r
-#if 0\r
- if (!vis)\r
- continue; // no faces at all\r
-#endif\r
- // if the brush is outside the clip area, skip it\r
- for (j=0 ; j<3 ; j++)\r
- if (mb->mins[j] >= clipmaxs[j]\r
- || mb->maxs[j] <= clipmins[j])\r
- break;\r
- if (j != 3)\r
- continue;\r
-\r
- //\r
- // make a copy of the brush\r
- //\r
- newbrush = AllocBrush (mb->numsides);\r
- newbrush->original = mb;\r
- newbrush->numsides = mb->numsides;\r
- memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));\r
- for (j=0 ; j<numsides ; j++)\r
- {\r
- if (newbrush->sides[j].winding)\r
- newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding);\r
- if (newbrush->sides[j].surf & SURF_HINT)\r
- newbrush->sides[j].visible = true; // hints are always visible\r
- }\r
- VectorCopy (mb->mins, newbrush->mins);\r
- VectorCopy (mb->maxs, newbrush->maxs);\r
-\r
- //\r
- // carve off anything outside the clip box\r
- //\r
- newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);\r
- if (!newbrush)\r
- continue;\r
-\r
- c_faces += vis;\r
- c_brushes++;\r
-\r
- newbrush->next = brushlist;\r
- brushlist = newbrush;\r
- }\r
-\r
- return brushlist;\r
-}\r
-\r
-/*\r
-===============\r
-AddBspBrushListToTail\r
-===============\r
-*/\r
-bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)\r
-{\r
- bspbrush_t *walk, *next;\r
-\r
- for (walk=list ; walk ; walk=next)\r
- { // add to end of list\r
- next = walk->next;\r
- walk->next = NULL;\r
- tail->next = walk;\r
- tail = walk;\r
- }\r
-\r
- return tail;\r
-}\r
-\r
-/*\r
-===========\r
-CullList\r
-\r
-Builds a new list that doesn't hold the given brush\r
-===========\r
-*/\r
-bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1)\r
-{\r
- bspbrush_t *newlist;\r
- bspbrush_t *next;\r
-\r
- newlist = NULL;\r
-\r
- for ( ; list ; list = next)\r
- {\r
- next = list->next;\r
- if (list == skip1)\r
- {\r
- FreeBrush (list);\r
- continue;\r
- }\r
- list->next = newlist;\r
- newlist = list;\r
- }\r
- return newlist;\r
-}\r
-\r
-\r
-/*\r
-==================\r
-WriteBrushMap\r
-==================\r
-*/\r
-void WriteBrushMap (char *name, bspbrush_t *list)\r
-{\r
- FILE *f;\r
- side_t *s;\r
- int i;\r
- winding_t *w;\r
-\r
- Sys_Printf ("writing %s\n", name);\r
- f = fopen (name, "wb");\r
- if (!f)\r
- Error ("Can't write %s\b", name);\r
-\r
- fprintf (f, "{\n\"classname\" \"worldspawn\"\n");\r
-\r
- for ( ; list ; list=list->next )\r
- {\r
- fprintf (f, "{\n");\r
- for (i=0,s=list->sides ; i<list->numsides ; i++,s++)\r
- {\r
- w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);\r
-\r
- fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);\r
- fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);\r
- fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);\r
-\r
- fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);\r
- FreeWinding (w);\r
- }\r
- fprintf (f, "}\n");\r
- }\r
- fprintf (f, "}\n");\r
-\r
- fclose (f);\r
-\r
-}\r
-\r
-/*\r
-==================\r
-BrushGE\r
-\r
-Returns true if b1 is allowed to bite b2\r
-==================\r
-*/\r
-qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)\r
-{\r
- // detail brushes never bite structural brushes\r
- if ( (b1->original->contents & CONTENTS_DETAIL) \r
- && !(b2->original->contents & CONTENTS_DETAIL) )\r
- return false;\r
- if (b1->original->contents & CONTENTS_SOLID)\r
- return true;\r
- return false;\r
-}\r
-\r
-/*\r
-=================\r
-ChopBrushes\r
-\r
-Carves any intersecting solid brushes into the minimum number\r
-of non-intersecting brushes. \r
-=================\r
-*/\r
-bspbrush_t *ChopBrushes (bspbrush_t *head)\r
-{\r
- bspbrush_t *b1, *b2, *next;\r
- bspbrush_t *tail;\r
- bspbrush_t *keep;\r
- bspbrush_t *sub, *sub2;\r
- int c1, c2;\r
-\r
- Sys_FPrintf( SYS_VRB, "---- ChopBrushes ----\n");\r
- Sys_FPrintf( SYS_VRB, "original brushes: %i\n", CountBrushList (head));\r
-\r
-#if 0\r
- if (startbrush == 0)\r
- WriteBrushList ("before.gl", head, false);\r
-#endif\r
- keep = NULL;\r
-\r
-newlist:\r
- // find tail\r
- if (!head)\r
- return NULL;\r
- for (tail=head ; tail->next ; tail=tail->next)\r
- ;\r
-\r
- for (b1=head ; b1 ; b1=next)\r
- {\r
- next = b1->next;\r
- for (b2=b1->next ; b2 ; b2 = b2->next)\r
- {\r
- if (BrushesDisjoint (b1, b2))\r
- continue;\r
-\r
- sub = NULL;\r
- sub2 = NULL;\r
- c1 = 999999;\r
- c2 = 999999;\r
-\r
- if ( BrushGE (b2, b1) )\r
- {\r
- sub = SubtractBrush (b1, b2);\r
- if (sub == b1)\r
- continue; // didn't really intersect\r
- if (!sub)\r
- { // b1 is swallowed by b2\r
- head = CullList (b1, b1);\r
- goto newlist;\r
- }\r
- c1 = CountBrushList (sub);\r
- }\r
-\r
- if ( BrushGE (b1, b2) )\r
- {\r
- sub2 = SubtractBrush (b2, b1);\r
- if (sub2 == b2)\r
- continue; // didn't really intersect\r
- if (!sub2)\r
- { // b2 is swallowed by b1\r
- FreeBrushList (sub);\r
- head = CullList (b1, b2);\r
- goto newlist;\r
- }\r
- c2 = CountBrushList (sub2);\r
- }\r
-\r
- if (!sub && !sub2)\r
- continue; // neither one can bite\r
-\r
- // only accept if it didn't fragment\r
- // (commening this out allows full fragmentation)\r
- if (c1 > 1 && c2 > 1)\r
- {\r
- if (sub2)\r
- FreeBrushList (sub2);\r
- if (sub)\r
- FreeBrushList (sub);\r
- continue;\r
- }\r
-\r
- if (c1 < c2)\r
- {\r
- if (sub2)\r
- FreeBrushList (sub2);\r
- tail = AddBrushListToTail (sub, tail);\r
- head = CullList (b1, b1);\r
- goto newlist;\r
- }\r
- else\r
- {\r
- if (sub)\r
- FreeBrushList (sub);\r
- tail = AddBrushListToTail (sub2, tail);\r
- head = CullList (b1, b2);\r
- goto newlist;\r
- }\r
- }\r
-\r
- if (!b2)\r
- { // b1 is no longer intersecting anything, so keep it\r
- b1->next = keep;\r
- keep = b1;\r
- }\r
- }\r
-\r
- Sys_FPrintf( SYS_VRB, "output brushes: %i\n", CountBrushList (keep));\r
-#if 0\r
- {\r
- WriteBrushList ("after.gl", keep, false);\r
- WriteBrushMap ("after.map", keep);\r
- }\r
-#endif\r
- return keep;\r
-}\r
-\r
-\r
-/*\r
-=================\r
-InitialBrushList\r
-=================\r
-*/\r
-bspbrush_t *InitialBrushList (bspbrush_t *list)\r
-{\r
- bspbrush_t *b;\r
- bspbrush_t *out, *newb;\r
- int i;\r
-\r
- // only return brushes that have visible faces\r
- out = NULL;\r
- for (b=list ; b ; b=b->next)\r
- {\r
-#if 0\r
- for (i=0 ; i<b->numsides ; i++)\r
- if (b->sides[i].visible)\r
- break;\r
- if (i == b->numsides)\r
- continue;\r
-#endif\r
- newb = CopyBrush (b);\r
- newb->next = out;\r
- out = newb;\r
-\r
- // clear visible, so it must be set by MarkVisibleFaces_r\r
- // to be used in the optimized list\r
- for (i=0 ; i<b->numsides ; i++)\r
- {\r
- newb->sides[i].original = &b->sides[i];\r
-// newb->sides[i].visible = true;\r
- b->sides[i].visible = false;\r
- }\r
- }\r
-\r
- return out;\r
-}\r
-\r
-/*\r
-=================\r
-OptimizedBrushList\r
-=================\r
-*/\r
-bspbrush_t *OptimizedBrushList (bspbrush_t *list)\r
-{\r
- bspbrush_t *b;\r
- bspbrush_t *out, *newb;\r
- int i;\r
-\r
- // only return brushes that have visible faces\r
- out = NULL;\r
- for (b=list ; b ; b=b->next)\r
- {\r
- for (i=0 ; i<b->numsides ; i++)\r
- if (b->sides[i].visible)\r
- break;\r
- if (i == b->numsides)\r
- continue;\r
- newb = CopyBrush (b);\r
- newb->next = out;\r
- out = newb;\r
- }\r
-\r
-// WriteBrushList ("vis.gl", out, true);\r
-\r
- return out;\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 "qbsp.h"
+
+/*
+
+tag all brushes with original contents
+brushes may contain multiple contents
+there will be no brush overlap after csg phase
+
+
+
+
+each side has a count of the other sides it splits
+
+the best split will be the one that minimizes the total split counts
+of all remaining sides
+
+precalc side on plane table
+
+evaluate split side
+{
+cost = 0
+for all sides
+ for all sides
+ get
+ if side splits side and splitside is on same child
+ cost++;
+}
+
+
+ */
+
+void SplitBrush2 (bspbrush_t *brush, int planenum,
+ bspbrush_t **front, bspbrush_t **back)
+{
+ SplitBrush (brush, planenum, front, back);
+#if 0
+ if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)
+ (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1
+ if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)
+ (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo; // not -1
+#endif
+}
+
+/*
+===============
+SubtractBrush
+
+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.
+===============
+*/
+bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
+{ // a - b = out (list)
+ int i;
+ bspbrush_t *front, *back;
+ bspbrush_t *out, *in;
+
+ in = a;
+ out = NULL;
+ for (i=0 ; i<b->numsides && in ; i++)
+ {
+ SplitBrush2 (in, b->sides[i].planenum, &front, &back);
+ if (in != a)
+ FreeBrush (in);
+ if (front)
+ { // add to list
+ front->next = out;
+ out = front;
+ }
+ in = back;
+ }
+ if (in)
+ FreeBrush (in);
+ else
+ { // didn't really intersect
+ FreeBrushList (out);
+ return a;
+ }
+ return out;
+}
+
+/*
+===============
+IntersectBrush
+
+Returns a single brush made up by the intersection of the
+two provided brushes, or NULL if they are disjoint.
+
+The originals are undisturbed.
+===============
+*/
+bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)
+{
+ int i;
+ bspbrush_t *front, *back;
+ bspbrush_t *in;
+
+ in = a;
+ for (i=0 ; i<b->numsides && in ; i++)
+ {
+ SplitBrush2 (in, b->sides[i].planenum, &front, &back);
+ if (in != a)
+ FreeBrush (in);
+ if (front)
+ FreeBrush (front);
+ in = back;
+ }
+
+ if (in == a)
+ return NULL;
+
+ in->next = NULL;
+ return in;
+}
+
+
+/*
+===============
+BrushesDisjoint
+
+Returns true if the two brushes definately do not intersect.
+There will be false negatives for some non-axial combinations.
+===============
+*/
+qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)
+{
+ int i, j;
+
+ // check bounding boxes
+ for (i=0 ; i<3 ; i++)
+ if (a->mins[i] >= b->maxs[i]
+ || a->maxs[i] <= b->mins[i])
+ return true; // bounding boxes don't overlap
+
+ // check for opposing planes
+ for (i=0 ; i<a->numsides ; i++)
+ {
+ for (j=0 ; j<b->numsides ; j++)
+ {
+ if (a->sides[i].planenum ==
+ (b->sides[j].planenum^1) )
+ return true; // opposite planes, so not touching
+ }
+ }
+
+ return false; // might intersect
+}
+
+/*
+===============
+IntersectionContents
+
+Returns a content word for the intersection of two brushes.
+Some combinations will generate a combination (water + clip),
+but most will be the stronger of the two contents.
+===============
+*/
+int IntersectionContents (int c1, int c2)
+{
+ int out;
+
+ out = c1 | c2;
+
+ if (out & CONTENTS_SOLID)
+ out = CONTENTS_SOLID;
+
+ return out;
+}
+
+
+int minplanenums[3];
+int maxplanenums[3];
+
+/*
+===============
+ClipBrushToBox
+
+Any planes shared with the box edge will be set to no texinfo
+===============
+*/
+bspbrush_t *ClipBrushToBox (bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)
+{
+ int i, j;
+ bspbrush_t *front, *back;
+ int p;
+
+ for (j=0 ; j<2 ; j++)
+ {
+ if (brush->maxs[j] > clipmaxs[j])
+ {
+ SplitBrush (brush, maxplanenums[j], &front, &back);
+ if (front)
+ FreeBrush (front);
+ brush = back;
+ if (!brush)
+ return NULL;
+ }
+ if (brush->mins[j] < clipmins[j])
+ {
+ SplitBrush (brush, minplanenums[j], &front, &back);
+ if (back)
+ FreeBrush (back);
+ brush = front;
+ if (!brush)
+ return NULL;
+ }
+ }
+
+ // remove any colinear faces
+
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ p = brush->sides[i].planenum & ~1;
+ if (p == maxplanenums[0] || p == maxplanenums[1]
+ || p == minplanenums[0] || p == minplanenums[1])
+ {
+ brush->sides[i].texinfo = TEXINFO_NODE;
+ brush->sides[i].visible = false;
+ }
+ }
+ return brush;
+}
+
+/*
+===============
+MakeBspBrushList
+===============
+*/
+bspbrush_t *MakeBspBrushList (int startbrush, int endbrush,
+ vec3_t clipmins, vec3_t clipmaxs)
+{
+ mapbrush_t *mb;
+ bspbrush_t *brushlist, *newbrush;
+ int i, j;
+ int c_faces;
+ int c_brushes;
+ int numsides;
+ int vis;
+ vec3_t normal;
+ float dist;
+
+ for (i=0 ; i<2 ; i++)
+ {
+ VectorClear (normal);
+ normal[i] = 1;
+ dist = clipmaxs[i];
+ maxplanenums[i] = FindFloatPlane (normal, dist);
+ dist = clipmins[i];
+ minplanenums[i] = FindFloatPlane (normal, dist);
+ }
+
+ brushlist = NULL;
+ c_faces = 0;
+ c_brushes = 0;
+
+ for (i=startbrush ; i<endbrush ; i++)
+ {
+ mb = &mapbrushes[i];
+
+ numsides = mb->numsides;
+ if (!numsides)
+ continue;
+ // make sure the brush has at least one face showing
+ vis = 0;
+ for (j=0 ; j<numsides ; j++)
+ if (mb->original_sides[j].visible && mb->original_sides[j].winding)
+ vis++;
+#if 0
+ if (!vis)
+ continue; // no faces at all
+#endif
+ // if the brush is outside the clip area, skip it
+ for (j=0 ; j<3 ; j++)
+ if (mb->mins[j] >= clipmaxs[j]
+ || mb->maxs[j] <= clipmins[j])
+ break;
+ if (j != 3)
+ continue;
+
+ //
+ // make a copy of the brush
+ //
+ newbrush = AllocBrush (mb->numsides);
+ newbrush->original = mb;
+ newbrush->numsides = mb->numsides;
+ memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));
+ for (j=0 ; j<numsides ; j++)
+ {
+ if (newbrush->sides[j].winding)
+ newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding);
+ if (newbrush->sides[j].surf & SURF_HINT)
+ newbrush->sides[j].visible = true; // hints are always visible
+ }
+ VectorCopy (mb->mins, newbrush->mins);
+ VectorCopy (mb->maxs, newbrush->maxs);
+
+ //
+ // carve off anything outside the clip box
+ //
+ newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
+ if (!newbrush)
+ continue;
+
+ c_faces += vis;
+ c_brushes++;
+
+ newbrush->next = brushlist;
+ brushlist = newbrush;
+ }
+
+ return brushlist;
+}
+
+/*
+===============
+AddBspBrushListToTail
+===============
+*/
+bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)
+{
+ bspbrush_t *walk, *next;
+
+ for (walk=list ; walk ; walk=next)
+ { // add to end of list
+ next = walk->next;
+ walk->next = NULL;
+ tail->next = walk;
+ tail = walk;
+ }
+
+ return tail;
+}
+
+/*
+===========
+CullList
+
+Builds a new list that doesn't hold the given brush
+===========
+*/
+bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1)
+{
+ bspbrush_t *newlist;
+ bspbrush_t *next;
+
+ newlist = NULL;
+
+ for ( ; list ; list = next)
+ {
+ next = list->next;
+ if (list == skip1)
+ {
+ FreeBrush (list);
+ continue;
+ }
+ list->next = newlist;
+ newlist = list;
+ }
+ return newlist;
+}
+
+
+/*
+==================
+WriteBrushMap
+==================
+*/
+void WriteBrushMap (char *name, bspbrush_t *list)
+{
+ FILE *f;
+ side_t *s;
+ int i;
+ winding_t *w;
+
+ Sys_Printf ("writing %s\n", name);
+ f = fopen (name, "wb");
+ if (!f)
+ Error ("Can't write %s\b", name);
+
+ fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
+
+ for ( ; list ; list=list->next )
+ {
+ fprintf (f, "{\n");
+ for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
+ {
+ w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
+
+ fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
+ fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
+ fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
+
+ fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
+ FreeWinding (w);
+ }
+ fprintf (f, "}\n");
+ }
+ fprintf (f, "}\n");
+
+ fclose (f);
+
+}
+
+/*
+==================
+BrushGE
+
+Returns true if b1 is allowed to bite b2
+==================
+*/
+qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
+{
+ // detail brushes never bite structural brushes
+ if ( (b1->original->contents & CONTENTS_DETAIL)
+ && !(b2->original->contents & CONTENTS_DETAIL) )
+ return false;
+ if (b1->original->contents & CONTENTS_SOLID)
+ return true;
+ return false;
+}
+
+/*
+=================
+ChopBrushes
+
+Carves any intersecting solid brushes into the minimum number
+of non-intersecting brushes.
+=================
+*/
+bspbrush_t *ChopBrushes (bspbrush_t *head)
+{
+ bspbrush_t *b1, *b2, *next;
+ bspbrush_t *tail;
+ bspbrush_t *keep;
+ bspbrush_t *sub, *sub2;
+ int c1, c2;
+
+ Sys_FPrintf( SYS_VRB, "---- ChopBrushes ----\n");
+ Sys_FPrintf( SYS_VRB, "original brushes: %i\n", CountBrushList (head));
+
+#if 0
+ if (startbrush == 0)
+ WriteBrushList ("before.gl", head, false);
+#endif
+ keep = NULL;
+
+newlist:
+ // find tail
+ if (!head)
+ return NULL;
+ for (tail=head ; tail->next ; tail=tail->next)
+ ;
+
+ for (b1=head ; b1 ; b1=next)
+ {
+ next = b1->next;
+ for (b2=b1->next ; b2 ; b2 = b2->next)
+ {
+ if (BrushesDisjoint (b1, b2))
+ continue;
+
+ sub = NULL;
+ sub2 = NULL;
+ c1 = 999999;
+ c2 = 999999;
+
+ if ( BrushGE (b2, b1) )
+ {
+ sub = SubtractBrush (b1, b2);
+ if (sub == b1)
+ continue; // didn't really intersect
+ if (!sub)
+ { // b1 is swallowed by b2
+ head = CullList (b1, b1);
+ goto newlist;
+ }
+ c1 = CountBrushList (sub);
+ }
+
+ if ( BrushGE (b1, b2) )
+ {
+ sub2 = SubtractBrush (b2, b1);
+ if (sub2 == b2)
+ continue; // didn't really intersect
+ if (!sub2)
+ { // b2 is swallowed by b1
+ FreeBrushList (sub);
+ head = CullList (b1, b2);
+ goto newlist;
+ }
+ c2 = CountBrushList (sub2);
+ }
+
+ if (!sub && !sub2)
+ continue; // neither one can bite
+
+ // only accept if it didn't fragment
+ // (commening this out allows full fragmentation)
+ if (c1 > 1 && c2 > 1)
+ {
+ if (sub2)
+ FreeBrushList (sub2);
+ if (sub)
+ FreeBrushList (sub);
+ continue;
+ }
+
+ if (c1 < c2)
+ {
+ if (sub2)
+ FreeBrushList (sub2);
+ tail = AddBrushListToTail (sub, tail);
+ head = CullList (b1, b1);
+ goto newlist;
+ }
+ else
+ {
+ if (sub)
+ FreeBrushList (sub);
+ tail = AddBrushListToTail (sub2, tail);
+ head = CullList (b1, b2);
+ goto newlist;
+ }
+ }
+
+ if (!b2)
+ { // b1 is no longer intersecting anything, so keep it
+ b1->next = keep;
+ keep = b1;
+ }
+ }
+
+ Sys_FPrintf( SYS_VRB, "output brushes: %i\n", CountBrushList (keep));
+#if 0
+ {
+ WriteBrushList ("after.gl", keep, false);
+ WriteBrushMap ("after.map", keep);
+ }
+#endif
+ return keep;
+}
+
+
+/*
+=================
+InitialBrushList
+=================
+*/
+bspbrush_t *InitialBrushList (bspbrush_t *list)
+{
+ bspbrush_t *b;
+ bspbrush_t *out, *newb;
+ int i;
+
+ // only return brushes that have visible faces
+ out = NULL;
+ for (b=list ; b ; b=b->next)
+ {
+#if 0
+ for (i=0 ; i<b->numsides ; i++)
+ if (b->sides[i].visible)
+ break;
+ if (i == b->numsides)
+ continue;
+#endif
+ newb = CopyBrush (b);
+ newb->next = out;
+ out = newb;
+
+ // clear visible, so it must be set by MarkVisibleFaces_r
+ // to be used in the optimized list
+ for (i=0 ; i<b->numsides ; i++)
+ {
+ newb->sides[i].original = &b->sides[i];
+// newb->sides[i].visible = true;
+ b->sides[i].visible = false;
+ }
+ }
+
+ return out;
+}
+
+/*
+=================
+OptimizedBrushList
+=================
+*/
+bspbrush_t *OptimizedBrushList (bspbrush_t *list)
+{
+ bspbrush_t *b;
+ bspbrush_t *out, *newb;
+ int i;
+
+ // only return brushes that have visible faces
+ out = NULL;
+ for (b=list ; b ; b=b->next)
+ {
+ for (i=0 ; i<b->numsides ; i++)
+ if (b->sides[i].visible)
+ break;
+ if (i == b->numsides)
+ continue;
+ newb = CopyBrush (b);
+ newb->next = out;
+ out = newb;
+ }
+
+// WriteBrushList ("vis.gl", out, true);
+
+ return out;
+}