2 Copyright (C) 1999-2007 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
32 void Brush_Scale( brush_t* b ){
33 for ( face_t* f = b->brush_faces ; f ; f = f->next )
35 for ( int i = 0 ; i < 3 ; i++ )
37 VectorScale( f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i] );
42 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->patchBrush || b->bFiltered ) {
57 for ( f = b->brush_faces ; f ; f = f->next )
60 VectorScale( f->plane.normal, g_qeglobals.d_gridsize, move );
61 for ( i = 0 ; i < 3 ; i++ )
62 VectorSubtract( split.planepts[i], move, split.planepts[i] );
64 Brush_SplitBrushByFace( b, &split, &front, &back );
69 Brush_AddToList( front, &selected_brushes );
74 Sys_UpdateWindows( W_ALL );
81 Returns a new brush that is created by merging brush1 and brush2.
82 May return NULL if brush1 and brush2 do not create a convex brush when merged.
83 The input brushes brush1 and brush2 stay intact.
85 if onlyshape is true then the merge is allowed based on the shape only
86 otherwise the texture/shader references of faces in the same plane have to
90 brush_t *Brush_Merge( brush_t *brush1, brush_t *brush2, int onlyshape ){
93 face_t *face1, *face2, *newface, *f;
95 // check for bounding box overlapp
96 for ( i = 0; i < 3; i++ )
98 if ( brush1->mins[i] > brush2->maxs[i] + ON_EPSILON
99 || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON ) {
100 // never merge if the brushes overlap
106 // check if the new brush would be convex... flipped planes make a brush non-convex
107 for ( face1 = brush1->brush_faces; face1; face1 = face1->next )
109 // don't check the faces of brush 1 and 2 touching each other
110 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
112 if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) {
114 // there may only be ONE shared side
121 // if this face plane is shared
126 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
128 // don't check the faces of brush 1 and 2 touching each other
129 for ( f = brush1->brush_faces; f; f = f->next )
131 if ( Plane_Equal( &face2->plane, &f->plane, true ) ) {
139 if ( Plane_Equal( &face1->plane, &face2->plane, false ) ) {
140 //if the texture/shader references should be the same but are not
141 if ( !onlyshape && stricmp( face1->texdef.GetName(), face2->texdef.GetName() ) != 0 ) {
147 if ( Winding_PlanesConcave( face1->face_winding, face2->face_winding,
148 face1->plane.normal, face2->plane.normal,
149 face1->plane.dist, face2->plane.dist ) ) {
155 newbrush = Brush_Alloc();
157 for ( face1 = brush1->brush_faces; face1; face1 = face1->next )
159 // don't add the faces of brush 1 and 2 touching each other
160 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
162 if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) {
169 // don't add faces with the same plane twice
170 for ( f = newbrush->brush_faces; f; f = f->next )
172 if ( Plane_Equal( &face1->plane, &f->plane, false ) ) {
175 if ( Plane_Equal( &face1->plane, &f->plane, true ) ) {
183 newface = Face_Alloc();
184 newface->texdef = face1->texdef;
185 VectorCopy( face1->planepts[0], newface->planepts[0] );
186 VectorCopy( face1->planepts[1], newface->planepts[1] );
187 VectorCopy( face1->planepts[2], newface->planepts[2] );
188 newface->plane = face1->plane;
189 newface->next = newbrush->brush_faces;
190 newbrush->brush_faces = newface;
193 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
195 // don't add the faces of brush 1 and 2 touching each other
196 for ( face1 = brush1->brush_faces; face1; face1 = face1->next )
198 if ( Plane_Equal( &face2->plane, &face1->plane, true ) ) {
205 // don't add faces with the same plane twice
206 for ( f = newbrush->brush_faces; f; f = f->next )
208 if ( Plane_Equal( &face2->plane, &f->plane, false ) ) {
211 if ( Plane_Equal( &face2->plane, &f->plane, true ) ) {
219 newface = Face_Alloc();
220 newface->texdef = face2->texdef;
221 VectorCopy( face2->planepts[0], newface->planepts[0] );
222 VectorCopy( face2->planepts[1], newface->planepts[1] );
223 VectorCopy( face2->planepts[2], newface->planepts[2] );
224 newface->plane = face2->plane;
225 newface->next = newbrush->brush_faces;
226 newbrush->brush_faces = newface;
228 // link the new brush to an entity
229 Entity_LinkBrush( brush1->owner, newbrush );
230 // build windings for the faces
231 Brush_BuildWindings( newbrush, false );
240 Returns a list with merged brushes.
241 Tries to merge brushes pair wise.
242 The input list is destroyed.
243 Input and output should be a single linked list using .next
246 brush_t *Brush_MergeListPairs( brush_t *brushlist, int onlyshape ){
247 int nummerges, merged;
248 brush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
258 for ( tail = brushlist; tail; tail = tail->next )
266 for ( b1 = brushlist; b1; b1 = brushlist )
269 for ( b2 = b1->next; b2; b2 = b2->next )
271 newbrush = Brush_Merge( b1, b2, onlyshape );
273 tail->next = newbrush;
274 lastb2->next = b2->next;
275 brushlist = brushlist->next;
276 b1->next = b1->prev = NULL;
277 b2->next = b2->prev = NULL;
280 for ( tail = brushlist; tail; tail = tail->next )
292 //if b1 can't be merged with any of the other brushes
294 brushlist = brushlist->next;
296 b1->next = newbrushlist;
300 brushlist = newbrushlist;
309 Tries to merge all brushes in the list into one new brush.
310 The input brush list stays intact.
311 Returns NULL if no merged brush can be created.
312 To create a new brush the brushes in the list may not overlap and
313 the outer faces of the brushes together should make a new convex brush.
315 if onlyshape is true then the merge is allowed based on the shape only
316 otherwise the texture/shader references of faces in the same plane have to
320 brush_t *Brush_MergeList( brush_t *brushlist, int onlyshape ){
321 brush_t *brush1, *brush2, *brush3, *newbrush;
322 face_t *face1, *face2, *face3, *newface, *f;
327 for ( brush1 = brushlist; brush1; brush1 = brush1->next )
329 // check if the new brush would be convex... flipped planes make a brush concave
330 for ( face1 = brush1->brush_faces; face1; face1 = face1->next )
332 // don't check face1 if it touches another brush
333 for ( brush2 = brushlist; brush2; brush2 = brush2->next )
335 if ( brush2 == brush1 ) {
338 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
340 if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) {
348 // if face1 touches another brush
353 for ( brush2 = brush1->next; brush2; brush2 = brush2->next )
355 // don't check the faces of brush 2 touching another brush
356 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
358 for ( brush3 = brushlist; brush3; brush3 = brush3->next )
360 if ( brush3 == brush2 ) {
363 for ( face3 = brush3->brush_faces; face3; face3 = face3->next )
365 if ( Plane_Equal( &face2->plane, &face3->plane, true ) ) {
373 // if face2 touches another brush
378 if ( Plane_Equal( &face1->plane, &face2->plane, false ) ) {
379 //if the texture/shader references should be the same but are not
380 if ( !onlyshape && stricmp( face1->texdef.GetName(), face2->texdef.GetName() ) != 0 ) {
386 if ( Winding_PlanesConcave( face1->face_winding, face2->face_winding,
387 face1->plane.normal, face2->plane.normal,
388 face1->plane.dist, face2->plane.dist ) ) {
396 newbrush = Brush_Alloc();
398 for ( brush1 = brushlist; brush1; brush1 = brush1->next )
400 for ( face1 = brush1->brush_faces; face1; face1 = face1->next )
402 // don't add face1 to the new brush if it touches another brush
403 for ( brush2 = brushlist; brush2; brush2 = brush2->next )
405 if ( brush2 == brush1 ) {
408 for ( face2 = brush2->brush_faces; face2; face2 = face2->next )
410 if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) {
421 // don't add faces with the same plane twice
422 for ( f = newbrush->brush_faces; f; f = f->next )
424 if ( Plane_Equal( &face1->plane, &f->plane, false ) ) {
427 if ( Plane_Equal( &face1->plane, &f->plane, true ) ) {
435 newface = Face_Alloc();
436 newface->texdef = face1->texdef;
437 VectorCopy( face1->planepts[0], newface->planepts[0] );
438 VectorCopy( face1->planepts[1], newface->planepts[1] );
439 VectorCopy( face1->planepts[2], newface->planepts[2] );
440 newface->plane = face1->plane;
441 newface->next = newbrush->brush_faces;
442 newbrush->brush_faces = newface;
445 // link the new brush to an entity
446 Entity_LinkBrush( brushlist->owner, newbrush );
447 // build windings for the faces
448 Brush_BuildWindings( newbrush, false );
457 Returns a list of brushes that remain after B is subtracted from A.
458 May by empty if A is contained inside B.
459 The originals are undisturbed.
462 brush_t *Brush_Subtract( brush_t *a, brush_t *b ){
463 // a - b = out (list)
464 brush_t *front, *back;
465 brush_t *in, *out, *next;
470 for ( f = b->brush_faces; f && in; f = f->next )
472 Brush_SplitBrushByFace( in, f, &front, &back );
476 if ( front ) { // add to list
482 //NOTE: in != a just in case brush b has no faces
483 if ( in && in != a ) {
487 { //didn't really intersect
488 for ( b = out; b; b = next )
491 b->next = b->prev = NULL;
504 void CSG_Subtract( void ){
505 brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext;
506 brush_t fragmentlist;
507 int i, numfragments, numbrushes;
509 Sys_Printf( "Subtracting...\n" );
511 if ( selected_brushes.next == &selected_brushes ) {
512 Sys_Printf( "No brushes selected.\n" );
516 fragmentlist.next = &fragmentlist;
517 fragmentlist.prev = &fragmentlist;
521 for ( b = selected_brushes.next ; b != &selected_brushes ; b = next )
525 if ( b->owner->eclass->fixedsize ) {
526 continue; // can't use texture from a fixed entity, so don't subtract
529 // chop all fragments further up
530 for ( s = fragmentlist.next; s != &fragmentlist; s = snext )
534 for ( i = 0 ; i < 3 ; i++ )
535 if ( b->mins[i] >= s->maxs[i] - ON_EPSILON
536 || b->maxs[i] <= s->mins[i] + ON_EPSILON ) {
540 continue; // definately don't touch
542 fragments = Brush_Subtract( s, b );
543 // if the brushes did not really intersect
544 if ( fragments == s ) {
547 // try to merge fragments
548 fragments = Brush_MergeListPairs( fragments, true );
549 // add the fragments to the list
550 for ( frag = fragments; frag; frag = nextfragment )
552 nextfragment = frag->next;
554 frag->owner = s->owner;
555 Brush_AddToList( frag, &fragmentlist );
557 // free the original brush
561 // chop any active brushes up
562 for ( s = active_brushes.next; s != &active_brushes; s = snext )
566 if ( s->owner->eclass->fixedsize || s->patchBrush || s->bFiltered ) {
570 if ( s->brush_faces->pShader->getFlags() & QER_NOCARVE ) {
574 for ( i = 0 ; i < 3 ; i++ )
575 if ( b->mins[i] >= s->maxs[i] - ON_EPSILON
576 || b->maxs[i] <= s->mins[i] + ON_EPSILON ) {
580 continue; // definately don't touch
583 fragments = Brush_Subtract( s, b );
584 // if the brushes did not really intersect
585 if ( fragments == s ) {
590 // one extra brush chopped up
592 // try to merge fragments
593 fragments = Brush_MergeListPairs( fragments, true );
594 // add the fragments to the list
595 for ( frag = fragments; frag; frag = nextfragment )
597 nextfragment = frag->next;
599 frag->owner = s->owner;
600 Brush_AddToList( frag, &fragmentlist );
602 // free the original brush
607 // move all fragments to the active brush list
608 for ( frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment )
610 nextfragment = frag->next;
612 Brush_RemoveFromList( frag );
613 Brush_AddToList( frag, &active_brushes );
614 Undo_EndBrush( frag );
617 /*if (numfragments == 0)
619 Sys_Printf("Selected brush%s did not intersect with any other brushes.\n",
620 (selected_brushes.next->next == &selected_brushes) ? "":"es");
623 Sys_Printf( "done. (created %d fragment%s out of %d brush%s)\n", numfragments, ( numfragments == 1 ) ? "" : "s",
624 numbrushes, ( numbrushes == 1 ) ? "" : "es" );
625 Sys_UpdateWindows( W_ALL );
633 void CSG_Merge( void ){
634 brush_t *b, *next, *newlist, *newbrush;
635 struct entity_s *owner;
637 Sys_Printf( "Merging...\n" );
639 if ( selected_brushes.next == &selected_brushes ) {
640 Sys_Printf( "No brushes selected.\n" );
644 if ( selected_brushes.next->next == &selected_brushes ) {
645 Sys_Printf( "At least two brushes have to be selected.\n" );
649 owner = selected_brushes.next->owner;
651 for ( b = selected_brushes.next; b != &selected_brushes; b = next )
655 if ( b->owner->eclass->fixedsize ) {
656 // can't use texture from a fixed entity, so don't subtract
657 Sys_Printf( "Cannot add fixed size entities.\n" );
661 if ( b->patchBrush ) {
662 Sys_Printf( "Cannot add patches.\n" );
667 // disable the qer_nocarve for CSG-MERGE operations
669 if ( b->brush_faces->d_texture->bFromShader && ( b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE ) ) {
670 Sys_Printf( "Cannot add brushes using shaders that don't allows CSG operations.\n" );
675 if ( b->owner != owner ) {
676 Sys_Printf( "Cannot add brushes from different entities.\n" );
683 for ( b = selected_brushes.next; b != &selected_brushes; b = next )
687 Brush_RemoveFromList( b );
693 newbrush = Brush_MergeList( newlist, true );
694 // if the new brush would not be convex
696 // add the brushes back into the selection
697 for ( b = newlist; b; b = next )
702 Brush_AddToList( b, &selected_brushes );
704 Sys_Printf( "Cannot add a set of brushes with a concave hull.\n" );
707 // free the original brushes
708 for ( b = newlist; b; b = next )
716 newbrush->bFiltered = FilterBrush( newbrush ); // spog - set filters for the new brush
718 Brush_AddToList( newbrush, &selected_brushes );
720 Sys_Printf( "done.\n" );
721 Sys_UpdateWindows( W_ALL );