2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
26 tag all brushes with original contents
27 brushes may contain multiple contents
28 there will be no brush overlap after csg phase
33 each side has a count of the other sides it splits
35 the best split will be the one that minimizes the total split counts
36 of all remaining sides
38 precalc side on plane table
46 if side splits side and splitside is on same child
53 void SplitBrush2 (bspbrush_t *brush, int planenum,
54 bspbrush_t **front, bspbrush_t **back)
56 SplitBrush (brush, planenum, front, back);
58 if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)
59 (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1
60 if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)
61 (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo; // not -1
69 Returns a list of brushes that remain after B is subtracted from A.
70 May by empty if A is contained inside B.
72 The originals are undisturbed.
75 bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
76 { // a - b = out (list)
78 bspbrush_t *front, *back;
83 for (i=0 ; i<b->numsides && in ; i++)
85 SplitBrush2 (in, b->sides[i].planenum, &front, &back);
98 { // didn't really intersect
109 Returns a single brush made up by the intersection of the
110 two provided brushes, or NULL if they are disjoint.
112 The originals are undisturbed.
115 bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)
118 bspbrush_t *front, *back;
122 for (i=0 ; i<b->numsides && in ; i++)
124 SplitBrush2 (in, b->sides[i].planenum, &front, &back);
144 Returns true if the two brushes definately do not intersect.
145 There will be false negatives for some non-axial combinations.
148 qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)
152 // check bounding boxes
153 for (i=0 ; i<3 ; i++)
154 if (a->mins[i] >= b->maxs[i]
155 || a->maxs[i] <= b->mins[i])
156 return true; // bounding boxes don't overlap
158 // check for opposing planes
159 for (i=0 ; i<a->numsides ; i++)
161 for (j=0 ; j<b->numsides ; j++)
163 if (a->sides[i].planenum ==
164 (b->sides[j].planenum^1) )
165 return true; // opposite planes, so not touching
169 return false; // might intersect
176 Returns a content word for the intersection of two brushes.
177 Some combinations will generate a combination (water + clip),
178 but most will be the stronger of the two contents.
181 int IntersectionContents (int c1, int c2)
187 if (out & CONTENTS_SOLID)
188 out = CONTENTS_SOLID;
201 Any planes shared with the box edge will be set to no texinfo
204 bspbrush_t *ClipBrushToBox (bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)
207 bspbrush_t *front, *back;
210 for (j=0 ; j<2 ; j++)
212 if (brush->maxs[j] > clipmaxs[j])
214 SplitBrush (brush, maxplanenums[j], &front, &back);
221 if (brush->mins[j] < clipmins[j])
223 SplitBrush (brush, minplanenums[j], &front, &back);
232 // remove any colinear faces
234 for (i=0 ; i<brush->numsides ; i++)
236 p = brush->sides[i].planenum & ~1;
237 if (p == maxplanenums[0] || p == maxplanenums[1]
238 || p == minplanenums[0] || p == minplanenums[1])
240 brush->sides[i].texinfo = TEXINFO_NODE;
241 brush->sides[i].visible = false;
252 bspbrush_t *MakeBspBrushList (int startbrush, int endbrush,
253 vec3_t clipmins, vec3_t clipmaxs)
256 bspbrush_t *brushlist, *newbrush;
265 for (i=0 ; i<2 ; i++)
267 VectorClear (normal);
270 maxplanenums[i] = FindFloatPlane (normal, dist);
272 minplanenums[i] = FindFloatPlane (normal, dist);
279 for (i=startbrush ; i<endbrush ; i++)
283 numsides = mb->numsides;
286 // make sure the brush has at least one face showing
288 for (j=0 ; j<numsides ; j++)
289 if (mb->original_sides[j].visible && mb->original_sides[j].winding)
293 continue; // no faces at all
295 // if the brush is outside the clip area, skip it
296 for (j=0 ; j<3 ; j++)
297 if (mb->mins[j] >= clipmaxs[j]
298 || mb->maxs[j] <= clipmins[j])
304 // make a copy of the brush
306 newbrush = AllocBrush (mb->numsides);
307 newbrush->original = mb;
308 newbrush->numsides = mb->numsides;
309 memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));
310 for (j=0 ; j<numsides ; j++)
312 if (newbrush->sides[j].winding)
313 newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding);
314 if (newbrush->sides[j].surf & SURF_HINT)
315 newbrush->sides[j].visible = true; // hints are always visible
317 VectorCopy (mb->mins, newbrush->mins);
318 VectorCopy (mb->maxs, newbrush->maxs);
321 // carve off anything outside the clip box
323 newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
330 newbrush->next = brushlist;
331 brushlist = newbrush;
339 AddBspBrushListToTail
342 bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)
344 bspbrush_t *walk, *next;
346 for (walk=list ; walk ; walk=next)
347 { // add to end of list
361 Builds a new list that doesn't hold the given brush
364 bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1)
371 for ( ; list ; list = next)
379 list->next = newlist;
391 void WriteBrushMap (char *name, bspbrush_t *list)
398 Sys_Printf ("writing %s\n", name);
399 f = fopen (name, "wb");
401 Error ("Can't write %s\b", name);
403 fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
405 for ( ; list ; list=list->next )
408 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
410 w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
412 fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
413 fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
414 fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
416 fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
431 Returns true if b1 is allowed to bite b2
434 qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
436 // detail brushes never bite structural brushes
437 if ( (b1->original->contents & CONTENTS_DETAIL)
438 && !(b2->original->contents & CONTENTS_DETAIL) )
440 if (b1->original->contents & CONTENTS_SOLID)
449 Carves any intersecting solid brushes into the minimum number
450 of non-intersecting brushes.
453 bspbrush_t *ChopBrushes (bspbrush_t *head)
455 bspbrush_t *b1, *b2, *next;
458 bspbrush_t *sub, *sub2;
461 Sys_FPrintf( SYS_VRB, "---- ChopBrushes ----\n");
462 Sys_FPrintf( SYS_VRB, "original brushes: %i\n", CountBrushList (head));
466 WriteBrushList ("before.gl", head, false);
474 for (tail=head ; tail->next ; tail=tail->next)
477 for (b1=head ; b1 ; b1=next)
480 for (b2=b1->next ; b2 ; b2 = b2->next)
482 if (BrushesDisjoint (b1, b2))
490 if ( BrushGE (b2, b1) )
492 sub = SubtractBrush (b1, b2);
494 continue; // didn't really intersect
496 { // b1 is swallowed by b2
497 head = CullList (b1, b1);
500 c1 = CountBrushList (sub);
503 if ( BrushGE (b1, b2) )
505 sub2 = SubtractBrush (b2, b1);
507 continue; // didn't really intersect
509 { // b2 is swallowed by b1
511 head = CullList (b1, b2);
514 c2 = CountBrushList (sub2);
518 continue; // neither one can bite
520 // only accept if it didn't fragment
521 // (commening this out allows full fragmentation)
522 if (c1 > 1 && c2 > 1)
525 FreeBrushList (sub2);
534 FreeBrushList (sub2);
535 tail = AddBrushListToTail (sub, tail);
536 head = CullList (b1, b1);
543 tail = AddBrushListToTail (sub2, tail);
544 head = CullList (b1, b2);
550 { // b1 is no longer intersecting anything, so keep it
556 Sys_FPrintf( SYS_VRB, "output brushes: %i\n", CountBrushList (keep));
559 WriteBrushList ("after.gl", keep, false);
560 WriteBrushMap ("after.map", keep);
572 bspbrush_t *InitialBrushList (bspbrush_t *list)
575 bspbrush_t *out, *newb;
578 // only return brushes that have visible faces
580 for (b=list ; b ; b=b->next)
583 for (i=0 ; i<b->numsides ; i++)
584 if (b->sides[i].visible)
586 if (i == b->numsides)
589 newb = CopyBrush (b);
593 // clear visible, so it must be set by MarkVisibleFaces_r
594 // to be used in the optimized list
595 for (i=0 ; i<b->numsides ; i++)
597 newb->sides[i].original = &b->sides[i];
598 // newb->sides[i].visible = true;
599 b->sides[i].visible = false;
611 bspbrush_t *OptimizedBrushList (bspbrush_t *list)
614 bspbrush_t *out, *newb;
617 // only return brushes that have visible faces
619 for (b=list ; b ; b=b->next)
621 for (i=0 ; i<b->numsides ; i++)
622 if (b->sides[i].visible)
624 if (i == b->numsides)
626 newb = CopyBrush (b);
631 // WriteBrushList ("vis.gl", out, true);