aboutsummaryrefslogtreecommitdiffstats
path: root/code/bspc/csg.c
diff options
context:
space:
mode:
Diffstat (limited to 'code/bspc/csg.c')
-rwxr-xr-xcode/bspc/csg.c2010
1 files changed, 1005 insertions, 1005 deletions
diff --git a/code/bspc/csg.c b/code/bspc/csg.c
index c141075..fc7c327 100755
--- a/code/bspc/csg.c
+++ b/code/bspc/csg.c
@@ -1,1005 +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
+/*
+===========================================================================
+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
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-16 14:01:03 +0000