2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
26 ===========================================================================
29 #include "../../idlib/precompiled.h"
34 const float PLANE_EPSILON = 0.0001f;
41 void CSG_MakeHollow (void)
43 brush_t *b, *front, *back, *next;
49 for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
53 if (b->owner->eclass->fixedsize || b->pPatch || b->hiddenBrush || b->modelHandle > 0)
56 for ( f = b->brush_faces; f; f = f->next ) {
58 VectorScale (f->plane, g_qeglobals.d_gridsize, move);
60 VectorSubtract (split.planepts[i], move, split.planepts[i]);
62 Brush_SplitBrushByFace (b, &split, &front, &back);
66 Brush_AddToList (front, &selected_brushes);
70 Sys_UpdateWindows (W_ALL);
77 Returns a new brush that is created by merging brush1 and brush2.
78 May return NULL if brush1 and brush2 do not create a convex brush when merged.
79 The input brushes brush1 and brush2 stay intact.
81 if onlyshape is true then the merge is allowed based on the shape only
82 otherwise the texture/shader references of faces in the same plane have to
86 brush_t *Brush_Merge(brush_t *brush1, brush_t *brush2, int onlyshape)
90 face_t *face1, *face2, *newface, *f;
92 // check for bounding box overlapp
93 for (i = 0; i < 3; i++)
95 if (brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
96 || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON)
98 // never merge if the brushes overlap
104 // check if the new brush would be convex... flipped planes make a brush non-convex
105 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
107 // don't check the faces of brush 1 and 2 touching each other
108 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
110 if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) )
113 // there may only be ONE shared side
119 // if this face plane is shared
122 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
124 // don't check the faces of brush 1 and 2 touching each other
125 for ( f = brush1->brush_faces; f; f = f->next ) {
126 if ( face2->plane.Compare( -f->plane, PLANE_EPSILON ) ) {
134 if ( face1->plane.Compare( face2->plane, PLANE_EPSILON ) )
136 //if the texture/shader references should be the same but are not
137 if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0)
142 if ( face1->face_winding->PlanesConcave( *face2->face_winding,
143 face1->plane.Normal(), face2->plane.Normal(), -face1->plane[3], -face2->plane[3]))
150 newbrush = Brush_Alloc();
152 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
154 // don't add the faces of brush 1 and 2 touching each other
155 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
157 if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
163 // don't add faces with the same plane twice
164 for (f = newbrush->brush_faces; f; f = f->next)
166 if ( face1->plane.Compare( f->plane, PLANE_EPSILON ) )
168 if ( face1->plane.Compare( -f->plane, PLANE_EPSILON ) )
175 newface = Face_Alloc();
176 newface->texdef = face1->texdef;
177 VectorCopy(face1->planepts[0], newface->planepts[0]);
178 VectorCopy(face1->planepts[1], newface->planepts[1]);
179 VectorCopy(face1->planepts[2], newface->planepts[2]);
180 newface->plane = face1->plane;
181 newface->next = newbrush->brush_faces;
182 newbrush->brush_faces = newface;
185 for (face2 = brush2->brush_faces; face2; face2 = face2->next) {
186 // don't add the faces of brush 1 and 2 touching each other
187 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
189 if ( face2->plane.Compare( -face1->plane, PLANE_EPSILON ) ) {
195 // don't add faces with the same plane twice
196 for (f = newbrush->brush_faces; f; f = f->next)
198 if ( face2->plane.Compare( f->plane, PLANE_EPSILON ) )
200 if ( face2->plane.Compare( -f->plane, PLANE_EPSILON ) )
207 newface = Face_Alloc();
208 newface->texdef = face2->texdef;
209 VectorCopy(face2->planepts[0], newface->planepts[0]);
210 VectorCopy(face2->planepts[1], newface->planepts[1]);
211 VectorCopy(face2->planepts[2], newface->planepts[2]);
212 newface->plane = face2->plane;
213 newface->next = newbrush->brush_faces;
214 newbrush->brush_faces = newface;
216 // link the new brush to an entity
217 Entity_LinkBrush (brush1->owner, newbrush);
218 // build windings for the faces
219 Brush_BuildWindings( newbrush, false);
227 Returns a list with merged brushes.
228 Tries to merge brushes pair wise.
229 The input list is destroyed.
230 Input and output should be a single linked list using .next
233 brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape)
235 int nummerges, merged;
236 brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
239 if (!brushlist) return NULL;
244 for (tail = brushlist; tail; tail = tail->next)
246 if (!tail->next) break;
250 for (b1 = brushlist; b1; b1 = brushlist)
253 for (b2 = b1->next; b2; b2 = b2->next)
255 newbrush = Brush_Merge(b1, b2, onlyshape);
258 tail->next = newbrush;
259 lastb2->next = b2->next;
260 brushlist = brushlist->next;
261 b1->next = b1->prev = NULL;
262 b2->next = b2->prev = NULL;
265 for (tail = brushlist; tail; tail = tail->next)
267 if (!tail->next) break;
275 //if b1 can't be merged with any of the other brushes
278 brushlist = brushlist->next;
280 b1->next = newbrushlist;
284 brushlist = newbrushlist;
293 Tries to merge all brushes in the list into one new brush.
294 The input brush list stays intact.
295 Returns NULL if no merged brush can be created.
296 To create a new brush the brushes in the list may not overlap and
297 the outer faces of the brushes together should make a new convex brush.
299 if onlyshape is true then the merge is allowed based on the shape only
300 otherwise the texture/shader references of faces in the same plane have to
304 brush_t *Brush_MergeList(brush_t *brushlist, int onlyshape)
306 brush_t *brush1, *brush2, *brush3, *newbrush;
307 face_t *face1, *face2, *face3, *newface, *f;
309 if (!brushlist) return NULL;
310 for (brush1 = brushlist; brush1; brush1 = brush1->next)
312 // check if the new brush would be convex... flipped planes make a brush concave
313 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
315 // don't check face1 if it touches another brush
316 for (brush2 = brushlist; brush2; brush2 = brush2->next)
318 if (brush2 == brush1) continue;
319 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
321 if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
328 // if face1 touches another brush
332 for (brush2 = brush1->next; brush2; brush2 = brush2->next)
334 // don't check the faces of brush 2 touching another brush
335 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
337 for (brush3 = brushlist; brush3; brush3 = brush3->next)
339 if (brush3 == brush2) continue;
340 for (face3 = brush3->brush_faces; face3; face3 = face3->next)
342 if ( face2->plane.Compare( -face3->plane, PLANE_EPSILON ) )
348 // if face2 touches another brush
352 if ( face1->plane.Compare( face2->plane, PLANE_EPSILON ) )
354 //if the texture/shader references should be the same but are not
355 if (!onlyshape && stricmp(face1->texdef.name, face2->texdef.name) != 0)
360 if ( face1->face_winding->PlanesConcave( *face2->face_winding,
361 face1->plane.Normal(), face2->plane.Normal(), -face1->plane[3], -face2->plane[3]))
370 newbrush = Brush_Alloc();
372 for (brush1 = brushlist; brush1; brush1 = brush1->next)
374 for (face1 = brush1->brush_faces; face1; face1 = face1->next)
376 // don't add face1 to the new brush if it touches another brush
377 for (brush2 = brushlist; brush2; brush2 = brush2->next)
379 if (brush2 == brush1) continue;
380 for (face2 = brush2->brush_faces; face2; face2 = face2->next)
382 if ( face1->plane.Compare( -face2->plane, PLANE_EPSILON ) ) {
391 // don't add faces with the same plane twice
392 for (f = newbrush->brush_faces; f; f = f->next)
394 if ( face1->plane.Compare( f->plane, PLANE_EPSILON ) )
396 if ( face1->plane.Compare( -f->plane, PLANE_EPSILON ) )
402 newface = Face_Alloc();
403 newface->texdef = face1->texdef;
404 VectorCopy(face1->planepts[0], newface->planepts[0]);
405 VectorCopy(face1->planepts[1], newface->planepts[1]);
406 VectorCopy(face1->planepts[2], newface->planepts[2]);
407 newface->plane = face1->plane;
408 newface->next = newbrush->brush_faces;
409 newbrush->brush_faces = newface;
412 // link the new brush to an entity
413 Entity_LinkBrush (brushlist->owner, newbrush);
414 // build windings for the faces
415 Brush_BuildWindings( newbrush, false);
423 Returns a list of brushes that remain after B is subtracted from A.
424 May by empty if A is contained inside B.
425 The originals are undisturbed.
428 brush_t *Brush_Subtract(brush_t *a, brush_t *b)
430 // a - b = out (list)
431 brush_t *front, *back;
432 brush_t *in, *out, *next;
437 for (f = b->brush_faces; f && in; f = f->next)
439 Brush_SplitBrushByFace(in, f, &front, &back);
440 if (in != a) Brush_Free(in);
448 //NOTE: in != a just in case brush b has no faces
454 { //didn't really intersect
455 for (b = out; b; b = next)
458 b->next = b->prev = NULL;
471 void CSG_Subtract (void)
473 brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
474 brush_t fragmentlist;
475 int i, numfragments, numbrushes;
477 Sys_Status ("Subtracting...\n");
479 if (selected_brushes.next == &selected_brushes)
481 Sys_Status("No brushes selected.\n");
485 fragmentlist.next = &fragmentlist;
486 fragmentlist.prev = &fragmentlist;
490 for (b = selected_brushes.next ; b != &selected_brushes ; b=next)
494 if (b->owner->eclass->fixedsize || b->modelHandle > 0)
495 continue; // can't use texture from a fixed entity, so don't subtract
497 // chop all fragments further up
498 for (s = fragmentlist.next; s != &fragmentlist; s = snext)
502 for (i=0 ; i<3 ; i++)
503 if (b->mins[i] >= s->maxs[i] - ON_EPSILON
504 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
507 continue; // definately don't touch
508 fragments = Brush_Subtract(s, b);
509 // if the brushes did not really intersect
512 // try to merge fragments
513 fragments = Brush_MergeListPairs(fragments, true);
514 // add the fragments to the list
515 for (frag = fragments; frag; frag = nextfragment)
517 nextfragment = frag->next;
519 frag->owner = s->owner;
520 Brush_AddToList(frag, &fragmentlist);
522 // free the original brush
526 // chop any active brushes up
527 for (s = active_brushes.next; s != &active_brushes; s = snext)
531 if (s->owner->eclass->fixedsize || s->pPatch || s->hiddenBrush || s->modelHandle > 0)
534 //face_t *pFace = s->brush_faces;
535 if ( s->brush_faces->d_texture && ( s->brush_faces->d_texture->GetContentFlags()& CONTENTS_NOCSG ) )
540 for (i=0 ; i<3 ; i++)
541 if (b->mins[i] >= s->maxs[i] - ON_EPSILON
542 || b->maxs[i] <= s->mins[i] + ON_EPSILON)
545 continue; // definately don't touch
547 fragments = Brush_Subtract(s, b);
548 // if the brushes did not really intersect
553 // one extra brush chopped up
555 // try to merge fragments
556 fragments = Brush_MergeListPairs(fragments, true);
557 // add the fragments to the list
558 for (frag = fragments; frag; frag = nextfragment)
560 nextfragment = frag->next;
562 frag->owner = s->owner;
563 Brush_AddToList(frag, &fragmentlist);
565 // free the original brush
570 // move all fragments to the active brush list
571 for (frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment)
573 nextfragment = frag->next;
575 Brush_RemoveFromList(frag);
576 Brush_AddToList(frag, &active_brushes);
580 if (numfragments == 0)
582 common->Printf("Selected brush%s did not intersect with any other brushes.\n",
583 (selected_brushes.next->next == &selected_brushes) ? "":"es");
587 common->Printf(" (created %d fragment%s out of %d brush%s)\n", numfragments, (numfragments == 1)?"":"s",
588 numbrushes, (numbrushes == 1)?"":"es");
589 Sys_UpdateWindows(W_ALL);
599 brush_t *b, *next, *newlist, *newbrush;
600 struct entity_s *owner;
602 Sys_Status("Merging...\n");
604 if (selected_brushes.next == &selected_brushes)
606 Sys_Status("No brushes selected.\n");
610 if (selected_brushes.next->next == &selected_brushes)
612 Sys_Status("At least two brushes have to be selected.\n");
616 owner = selected_brushes.next->owner;
618 for (b = selected_brushes.next; b != &selected_brushes; b = next)
622 if (b->owner->eclass->fixedsize || b->modelHandle > 0)
624 // can't use texture from a fixed entity, so don't subtract
625 Sys_Status("Cannot add fixed size entities.\n");
631 Sys_Status("Cannot add patches.\n");
635 if ( b->brush_faces->d_texture && ( b->brush_faces->d_texture->GetContentFlags() & CONTENTS_NOCSG ) )
637 Sys_Status("Cannot add brushes using shaders that don't allows CSG operations.\n");
641 if (b->owner != owner)
643 Sys_Status("Cannot add brushes from different entities.\n");
650 for (b = selected_brushes.next; b != &selected_brushes; b = next)
654 Brush_RemoveFromList(b);
660 newbrush = Brush_MergeList(newlist, true);
661 // if the new brush would not be convex
664 // add the brushes back into the selection
665 for (b = newlist; b; b = next)
670 Brush_AddToList(b, &selected_brushes);
672 Sys_Status("Cannot add a set of brushes with a concave hull.\n");
675 // free the original brushes
676 for (b = newlist; b; b = next)
683 Brush_AddToList(newbrush, &selected_brushes);
685 Sys_Status ("done.\n");
686 Sys_UpdateWindows (W_ALL);