diff options
Diffstat (limited to 'code/bspc/csg.c')
| -rwxr-xr-x | code/bspc/csg.c | 1005 |
1 files changed, 1005 insertions, 0 deletions
diff --git a/code/bspc/csg.c b/code/bspc/csg.c new file mode 100755 index 0000000..c141075 --- /dev/null +++ b/code/bspc/csg.c @@ -0,0 +1,1005 @@ +/*
+===========================================================================
+Copyright (C) 1999-2005 Id Software, Inc.
+
+This file is part of Quake III Arena source code.
+
+Quake III Arena source code 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.
+
+Quake III Arena source code 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 Foobar; 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
+
+*/
+
+int minplanenums[3];
+int maxplanenums[3];
+
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void CheckBSPBrush(bspbrush_t *brush)
+{
+ int i, j;
+ plane_t *plane1, *plane2;
+
+ //check if the brush is convex... flipped planes make a brush non-convex
+ for (i = 0; i < brush->numsides; i++)
+ {
+ for (j = 0; j < brush->numsides; j++)
+ {
+ if (i == j) continue;
+ plane1 = &mapplanes[brush->sides[i].planenum];
+ plane2 = &mapplanes[brush->sides[j].planenum];
+ //
+ if (WindingsNonConvex(brush->sides[i].winding,
+ brush->sides[j].winding,
+ plane1->normal, plane2->normal,
+ plane1->dist, plane2->dist))
+ {
+ Log_Print("non convex brush");
+ break;
+ } //end if
+ } //end for
+ } //end for
+ BoundBrush(brush);
+ //check for out of bound brushes
+ for (i = 0; i < 3; i++)
+ {
+ if (brush->mins[i] < -MAX_MAP_BOUNDS || brush->maxs[i] > MAX_MAP_BOUNDS)
+ {
+ Log_Print("brush: bounds out of range\n");
+ Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
+ break;
+ } //end if
+ if (brush->mins[i] > MAX_MAP_BOUNDS || brush->maxs[i] < -MAX_MAP_BOUNDS)
+ {
+ Log_Print("brush: no visible sides on brush\n");
+ Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
+ break;
+ } //end if
+ } //end for
+} //end of the function CheckBSPBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void BSPBrushWindings(bspbrush_t *brush)
+{
+ int i, j;
+ winding_t *w;
+ plane_t *plane;
+
+ for (i = 0; i < brush->numsides; i++)
+ {
+ plane = &mapplanes[brush->sides[i].planenum];
+ w = BaseWindingForPlane(plane->normal, plane->dist);
+ for (j = 0; j < brush->numsides && w; j++)
+ {
+ if (i == j) continue;
+ plane = &mapplanes[brush->sides[j].planenum^1];
+ ChopWindingInPlace(&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
+ } //end for
+ brush->sides[i].winding = w;
+ } //end for
+} //end of the function BSPBrushWindings
+//===========================================================================
+// NOTE: can't keep brush->original intact
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *TryMergeBrushes(bspbrush_t *brush1, bspbrush_t *brush2)
+{
+ int i, j, k, n, shared;
+ side_t *side1, *side2, *cs;
+ plane_t *plane1, *plane2;
+ bspbrush_t *newbrush;
+
+ //check for bounding box overlapp
+ for (i = 0; i < 3; i++)
+ {
+ if (brush1->mins[i] > brush2->maxs[i] + 2
+ || brush1->maxs[i] < brush2->mins[i] - 2)
+ {
+ return NULL;
+ } //end if
+ } //end for
+ //
+ shared = 0;
+ //check if the brush is convex... flipped planes make a brush non-convex
+ for (i = 0; i < brush1->numsides; i++)
+ {
+ side1 = &brush1->sides[i];
+ //don't check the "shared" sides
+ for (k = 0; k < brush2->numsides; k++)
+ {
+ side2 = &brush2->sides[k];
+ if (side1->planenum == (side2->planenum^1))
+ {
+ shared++;
+ //there may only be ONE shared side
+ if (shared > 1) return NULL;
+ break;
+ } //end if
+ } //end for
+ if (k < brush2->numsides) continue;
+ //
+ for (j = 0; j < brush2->numsides; j++)
+ {
+ side2 = &brush2->sides[j];
+ //don't check the "shared" sides
+ for (n = 0; n < brush1->numsides; n++)
+ {
+ side1 = &brush1->sides[n];
+ if (side1->planenum == (side2->planenum^1)) break;
+ } //end for
+ if (n < brush1->numsides) continue;
+ //
+ side1 = &brush1->sides[i];
+ //if the side is in the same plane
+ //*
+ if (side1->planenum == side2->planenum)
+ {
+ if (side1->texinfo != TEXINFO_NODE &&
+ side2->texinfo != TEXINFO_NODE &&
+ side1->texinfo != side2->texinfo) return NULL;
+ continue;
+ } //end if
+ //
+ plane1 = &mapplanes[side1->planenum];
+ plane2 = &mapplanes[side2->planenum];
+ //
+ if (WindingsNonConvex(side1->winding, side2->winding,
+ plane1->normal, plane2->normal,
+ plane1->dist, plane2->dist))
+ {
+ return NULL;
+ } //end if
+ } //end for
+ } //end for
+ newbrush = AllocBrush(brush1->numsides + brush2->numsides);
+ newbrush->original = brush1->original;
+ newbrush->numsides = 0;
+ //newbrush->side = brush1->side; //brush contents
+ //fix texinfos for sides lying in the same plane
+ for (i = 0; i < brush1->numsides; i++)
+ {
+ side1 = &brush1->sides[i];
+ //
+ for (n = 0; n < brush2->numsides; n++)
+ {
+ side2 = &brush2->sides[n];
+ //if both sides are in the same plane get the texinfo right
+ if (side1->planenum == side2->planenum)
+ {
+ if (side1->texinfo == TEXINFO_NODE) side1->texinfo = side2->texinfo;
+ if (side2->texinfo == TEXINFO_NODE) side2->texinfo = side1->texinfo;
+ } //end if
+ } //end for
+ } //end for
+ //
+ for (i = 0; i < brush1->numsides; i++)
+ {
+ side1 = &brush1->sides[i];
+ //don't add the "shared" sides
+ for (n = 0; n < brush2->numsides; n++)
+ {
+ side2 = &brush2->sides[n];
+ if (side1->planenum == (side2->planenum ^ 1)) break;
+ } //end for
+ if (n < brush2->numsides) continue;
+ //
+ for (n = 0; n < newbrush->numsides; n++)
+ {
+ cs = &newbrush->sides[n];
+ if (cs->planenum == side1->planenum)
+ {
+ Log_Print("brush duplicate plane\n");
+ break;
+ } //end if
+ } //end if
+ if (n < newbrush->numsides) continue;
+ //add this side
+ cs = &newbrush->sides[newbrush->numsides];
+ newbrush->numsides++;
+ *cs = *side1;
+ } //end for
+ for (j = 0; j < brush2->numsides; j++)
+ {
+ side2 = &brush2->sides[j];
+ for (n = 0; n < brush1->numsides; n++)
+ {
+ side1 = &brush1->sides[n];
+ //if the side is in the same plane
+ if (side2->planenum == side1->planenum) break;
+ //don't add the "shared" sides
+ if (side2->planenum == (side1->planenum ^ 1)) break;
+ } //end for
+ if (n < brush1->numsides) continue;
+ //
+ for (n = 0; n < newbrush->numsides; n++)
+ {
+ cs = &newbrush->sides[n];
+ if (cs->planenum == side2->planenum)
+ {
+ Log_Print("brush duplicate plane\n");
+ break;
+ } //end if
+ } //end if
+ if (n < newbrush->numsides) continue;
+ //add this side
+ cs = &newbrush->sides[newbrush->numsides];
+ newbrush->numsides++;
+ *cs = *side2;
+ } //end for
+ BSPBrushWindings(newbrush);
+ BoundBrush(newbrush);
+ CheckBSPBrush(newbrush);
+ return newbrush;
+} //end of the function TryMergeBrushes
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *MergeBrushes(bspbrush_t *brushlist)
+{
+ int nummerges, merged;
+ bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
+ bspbrush_t *lastb2;
+
+ if (!brushlist) return NULL;
+
+ qprintf("%5d brushes merged", nummerges = 0);
+ do
+ {
+ for (tail = brushlist; tail; tail = tail->next)
+ {
+ if (!tail->next) break;
+ } //end for
+ merged = 0;
+ newbrushlist = NULL;
+ for (b1 = brushlist; b1; b1 = brushlist)
+ {
+ lastb2 = b1;
+ for (b2 = b1->next; b2; b2 = b2->next)
+ {
+ //if the brushes don't have the same contents
+ if (b1->original->contents != b2->original->contents ||
+ b1->original->expansionbbox != b2->original->expansionbbox) newbrush = NULL;
+ else newbrush = TryMergeBrushes(b1, b2);
+ if (newbrush)
+ {
+ tail->next = newbrush;
+ lastb2->next = b2->next;
+ brushlist = brushlist->next;
+ FreeBrush(b1);
+ FreeBrush(b2);
+ for (tail = brushlist; tail; tail = tail->next)
+ {
+ if (!tail->next) break;
+ } //end for
+ merged++;
+ qprintf("\r%5d", nummerges++);
+ break;
+ } //end if
+ lastb2 = b2;
+ } //end for
+ //if b1 can't be merged with any of the other brushes
+ if (!b2)
+ {
+ brushlist = brushlist->next;
+ //keep b1
+ b1->next = newbrushlist;
+ newbrushlist = b1;
+ } //end else
+ } //end for
+ brushlist = newbrushlist;
+ } while(merged);
+ qprintf("\n");
+ return newbrushlist;
+} //end of the function MergeBrushes
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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
+} //end of the function SplitBrush2
+//===========================================================================
+// 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.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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;
+ } //end if
+ in = back;
+ } //end for
+ if (in)
+ {
+ FreeBrush (in);
+ } //end if
+ else
+ { // didn't really intersect
+ FreeBrushList (out);
+ return a;
+ } //end else
+ return out;
+} //end of the function SubtractBrush
+//===========================================================================
+// Returns a single brush made up by the intersection of the
+// two provided brushes, or NULL if they are disjoint.
+//
+// The originals are undisturbed.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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;
+ } //end for
+
+ if (in == a) return NULL;
+
+ in->next = NULL;
+ return in;
+} //end of the function IntersectBrush
+//===========================================================================
+// Returns true if the two brushes definately do not intersect.
+// There will be false negatives for some non-axial combinations.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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
+} //end of the function BrushesDisjoint
+//===========================================================================
+// 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.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int IntersectionContents (int c1, int c2)
+{
+ int out;
+
+ out = c1 | c2;
+
+ if (out & CONTENTS_SOLID) out = CONTENTS_SOLID;
+
+ return out;
+} //end of the function IntersectionContents
+//===========================================================================
+// Any planes shared with the box edge will be set to no texinfo
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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].flags &= ~SFL_VISIBLE;
+ }
+ }
+ return brush;
+} //end of the function ClipBrushToBox
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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].flags & SFL_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].flags |= SFL_VISIBLE; // 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;
+} //end of the function MakeBspBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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;
+ } //end for
+ return tail;
+} //end of the function AddBrushListToTail
+//===========================================================================
+// Builds a new list that doesn't hold the given brush
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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;
+} //end of the function CullList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+/*
+void WriteBrushMap(char *name, bspbrush_t *list)
+{
+ FILE *f;
+ side_t *s;
+ int i;
+ winding_t *w;
+
+ Log_Print("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);
+} //end of the function WriteBrushMap
+*/
+//===========================================================================
+// Returns true if b1 is allowed to bite b2
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
+{
+#ifdef ME
+ if (create_aas)
+ {
+ if (b1->original->expansionbbox != b2->original->expansionbbox)
+ {
+ return false;
+ } //end if
+ //never have something else bite a ladder brush
+ //never have a ladder brush bite something else
+ if ( (b1->original->contents & CONTENTS_LADDER)
+ && !(b2->original->contents & CONTENTS_LADDER))
+ {
+ return false;
+ } //end if
+ } //end if
+#endif //ME
+ // detail brushes never bite structural brushes
+ if ( (b1->original->contents & CONTENTS_DETAIL)
+ && !(b2->original->contents & CONTENTS_DETAIL) )
+ {
+ return false;
+ } //end if
+ if (b1->original->contents & CONTENTS_SOLID)
+ {
+ return true;
+ } //end if
+ return false;
+} //end of the function BrushGE
+//===========================================================================
+// Carves any intersecting solid brushes into the minimum number
+// of non-intersecting brushes.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *ChopBrushes (bspbrush_t *head)
+{
+ bspbrush_t *b1, *b2, *next;
+ bspbrush_t *tail;
+ bspbrush_t *keep;
+ bspbrush_t *sub, *sub2;
+ int c1, c2;
+ int num_csg_iterations;
+
+ Log_Print("-------- Brush CSG ---------\n");
+ Log_Print("%6d original brushes\n", CountBrushList (head));
+
+ num_csg_iterations = 0;
+ qprintf("%6d output brushes", num_csg_iterations);
+
+#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;
+
+ //if the conversion is cancelled
+ if (cancelconversion)
+ {
+ b1->next = keep;
+ keep = b1;
+ continue;
+ } //end if
+
+ 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
+ } //end if
+ 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
+ // (commenting 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;
+ } //end if
+ else
+ {
+ if (sub) FreeBrushList (sub);
+ tail = AddBrushListToTail (sub2, tail);
+ head = CullList (b1, b2);
+ goto newlist;
+ } //end else
+ } //end for
+
+ if (!b2)
+ { // b1 is no longer intersecting anything, so keep it
+ b1->next = keep;
+ keep = b1;
+ } //end if
+ num_csg_iterations++;
+ qprintf("\r%6d", num_csg_iterations);
+ } //end for
+
+ if (cancelconversion) return keep;
+ //
+ qprintf("\n");
+ Log_Write("%6d output brushes\r\n", num_csg_iterations);
+
+#if 0
+ {
+ WriteBrushList ("after.gl", keep, false);
+ WriteBrushMap ("after.map", keep);
+ }
+#endif
+
+ return keep;
+} //end of the function ChopBrushes
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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].flags & SFL_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].flags &= ~SFL_VISIBLE;
+ }
+ }
+
+ return out;
+} //end of the function InitialBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+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].flags & SFL_VISIBLE)
+ break;
+ if (i == b->numsides)
+ continue;
+ newb = CopyBrush (b);
+ newb->next = out;
+ out = newb;
+ } //end for
+
+// WriteBrushList ("vis.gl", out, true);
+ return out;
+} //end of the function OptimizeBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+tree_t *ProcessWorldBrushes(int brush_start, int brush_end)
+{
+ bspbrush_t *brushes;
+ tree_t *tree;
+ node_t *node;
+ vec3_t mins, maxs;
+
+ //take the whole world
+ mins[0] = map_mins[0] - 8;
+ mins[1] = map_mins[1] - 8;
+ mins[2] = map_mins[2] - 8;
+
+ maxs[0] = map_maxs[0] + 8;
+ maxs[1] = map_maxs[1] + 8;
+ maxs[2] = map_maxs[2] + 8;
+
+ //reset the brush bsp
+ ResetBrushBSP();
+
+ // the makelist and chopbrushes could be cached between the passes...
+
+ //create a list with brushes that are within the given mins/maxs
+ //some brushes will be cut and only the part that falls within the
+ //mins/maxs will be in the bush list
+ brushes = MakeBspBrushList(brush_start, brush_end, mins, maxs);
+ //
+
+ if (!brushes)
+ {
+ node = AllocNode ();
+ node->planenum = PLANENUM_LEAF;
+ node->contents = CONTENTS_SOLID;
+
+ tree = Tree_Alloc();
+ tree->headnode = node;
+ VectorCopy(mins, tree->mins);
+ VectorCopy(maxs, tree->maxs);
+ } //end if
+ else
+ {
+ //Carves any intersecting solid brushes into the minimum number
+ //of non-intersecting brushes.
+ if (!nocsg)
+ {
+ brushes = ChopBrushes(brushes);
+ /*
+ if (create_aas)
+ {
+ brushes = MergeBrushes(brushes);
+ } //end if*/
+ } //end if
+ //if the conversion is cancelled
+ if (cancelconversion)
+ {
+ FreeBrushList(brushes);
+ return NULL;
+ } //end if
+ //create the actual bsp tree
+ tree = BrushBSP(brushes, mins, maxs);
+ } //end else
+ //return the tree
+ return tree;
+} //end of the function ProcessWorldBrushes
|