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