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 ){
55 SplitBrush( brush, planenum, front, back );
57 if ( *front && ( *front )->sides[( *front )->numsides - 1].texinfo == -1 ) {
58 ( *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
70 Returns a list of brushes that remain after B is subtracted from A.
71 May by empty if A is contained inside B.
73 The originals are undisturbed.
76 bspbrush_t *SubtractBrush( bspbrush_t *a, bspbrush_t *b ){ // 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 );
89 if ( front ) { // add to list
99 { // didn't really intersect
100 FreeBrushList( out );
110 Returns a single brush made up by the intersection of the
111 two provided brushes, or NULL if they are disjoint.
113 The originals are undisturbed.
116 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 );
147 Returns true if the two brushes definately do not intersect.
148 There will be false negatives for some non-axial combinations.
151 qboolean BrushesDisjoint( bspbrush_t *a, bspbrush_t *b ){
154 // check bounding boxes
155 for ( i = 0 ; i < 3 ; i++ )
156 if ( a->mins[i] >= b->maxs[i]
157 || a->maxs[i] <= b->mins[i] ) {
159 } // bounding boxes don't overlap
161 // check for opposing planes
162 for ( i = 0 ; i < a->numsides ; i++ )
164 for ( j = 0 ; j < b->numsides ; j++ )
166 if ( a->sides[i].planenum ==
167 ( b->sides[j].planenum ^ 1 ) ) {
168 return true; // opposite planes, so not touching
173 return false; // might intersect
180 Returns a content word for the intersection of two brushes.
181 Some combinations will generate a combination (water + clip),
182 but most will be the stronger of the two contents.
185 int IntersectionContents( int c1, int c2 ){
190 if ( out & CONTENTS_SOLID ) {
191 out = CONTENTS_SOLID;
205 Any planes shared with the box edge will be set to no texinfo
208 bspbrush_t *ClipBrushToBox( bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs ){
210 bspbrush_t *front, *back;
213 for ( j = 0 ; j < 2 ; j++ )
215 if ( brush->maxs[j] > clipmaxs[j] ) {
216 SplitBrush( brush, maxplanenums[j], &front, &back );
225 if ( brush->mins[j] < clipmins[j] ) {
226 SplitBrush( brush, minplanenums[j], &front, &back );
237 // remove any colinear faces
239 for ( i = 0 ; i < brush->numsides ; i++ )
241 p = brush->sides[i].planenum & ~1;
242 if ( p == maxplanenums[0] || p == maxplanenums[1]
243 || p == minplanenums[0] || p == minplanenums[1] ) {
244 brush->sides[i].texinfo = TEXINFO_NODE;
245 brush->sides[i].visible = false;
256 bspbrush_t *MakeBspBrushList( int startbrush, int endbrush,
257 vec3_t clipmins, vec3_t clipmaxs ){
259 bspbrush_t *brushlist, *newbrush;
268 for ( i = 0 ; i < 2 ; i++ )
270 VectorClear( normal );
273 maxplanenums[i] = FindFloatPlane( normal, dist );
275 minplanenums[i] = FindFloatPlane( normal, dist );
282 for ( i = startbrush ; i < endbrush ; i++ )
286 numsides = mb->numsides;
290 // make sure the brush has at least one face showing
292 for ( j = 0 ; j < numsides ; j++ )
293 if ( mb->original_sides[j].visible && mb->original_sides[j].winding ) {
298 continue; // no faces at all
301 // if the brush is outside the clip area, skip it
302 for ( j = 0 ; j < 3 ; j++ )
303 if ( mb->mins[j] >= clipmaxs[j]
304 || mb->maxs[j] <= clipmins[j] ) {
312 // make a copy of the brush
314 newbrush = AllocBrush( mb->numsides );
315 newbrush->original = mb;
316 newbrush->numsides = mb->numsides;
317 memcpy( newbrush->sides, mb->original_sides, numsides * sizeof( side_t ) );
318 for ( j = 0 ; j < numsides ; j++ )
320 if ( newbrush->sides[j].winding ) {
321 newbrush->sides[j].winding = CopyWinding( newbrush->sides[j].winding );
323 if ( newbrush->sides[j].surf & SURF_HINT ) {
324 newbrush->sides[j].visible = true; // hints are always visible
327 VectorCopy( mb->mins, newbrush->mins );
328 VectorCopy( mb->maxs, newbrush->maxs );
331 // carve off anything outside the clip box
333 newbrush = ClipBrushToBox( newbrush, clipmins, clipmaxs );
341 newbrush->next = brushlist;
342 brushlist = newbrush;
350 AddBspBrushListToTail
353 bspbrush_t *AddBrushListToTail( bspbrush_t *list, bspbrush_t *tail ){
354 bspbrush_t *walk, *next;
356 for ( walk = list ; walk ; walk = next )
357 { // add to end of list
371 Builds a new list that doesn't hold the given brush
374 bspbrush_t *CullList( bspbrush_t *list, bspbrush_t *skip1 ){
380 for ( ; list ; list = next )
383 if ( list == skip1 ) {
387 list->next = newlist;
399 void WriteBrushMap( char *name, bspbrush_t *list ){
405 Sys_Printf( "writing %s\n", name );
406 f = fopen( name, "wb" );
408 Error( "Can't write %s\b", name );
411 fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
413 for ( ; list ; list = list->next )
416 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
418 w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
420 fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
421 fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
422 fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
424 fprintf( f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture );
439 Returns true if b1 is allowed to bite b2
442 qboolean BrushGE( bspbrush_t *b1, bspbrush_t *b2 ){
443 // detail brushes never bite structural brushes
444 if ( ( b1->original->contents & CONTENTS_DETAIL )
445 && !( b2->original->contents & CONTENTS_DETAIL ) ) {
448 if ( b1->original->contents & CONTENTS_SOLID ) {
458 Carves any intersecting solid brushes into the minimum number
459 of non-intersecting brushes.
462 bspbrush_t *ChopBrushes( bspbrush_t *head ){
463 bspbrush_t *b1, *b2, *next;
466 bspbrush_t *sub, *sub2;
469 Sys_FPrintf( SYS_VRB, "---- ChopBrushes ----\n" );
470 Sys_FPrintf( SYS_VRB, "original brushes: %i\n", CountBrushList( head ) );
473 if ( startbrush == 0 ) {
474 WriteBrushList( "before.gl", head, false );
484 for ( tail = head ; tail->next ; tail = tail->next )
487 for ( b1 = head ; b1 ; b1 = next )
490 for ( b2 = b1->next ; b2 ; b2 = b2->next )
492 if ( BrushesDisjoint( b1, b2 ) ) {
501 if ( BrushGE( b2, b1 ) ) {
502 sub = SubtractBrush( b1, b2 );
504 continue; // didn't really intersect
506 if ( !sub ) { // b1 is swallowed by b2
507 head = CullList( b1, b1 );
510 c1 = CountBrushList( sub );
513 if ( BrushGE( b1, b2 ) ) {
514 sub2 = SubtractBrush( b2, b1 );
516 continue; // didn't really intersect
518 if ( !sub2 ) { // b2 is swallowed by b1
519 FreeBrushList( sub );
520 head = CullList( b1, b2 );
523 c2 = CountBrushList( sub2 );
526 if ( !sub && !sub2 ) {
527 continue; // neither one can bite
530 // only accept if it didn't fragment
531 // (commening this out allows full fragmentation)
532 if ( c1 > 1 && c2 > 1 ) {
534 FreeBrushList( sub2 );
537 FreeBrushList( sub );
544 FreeBrushList( sub2 );
546 tail = AddBrushListToTail( sub, tail );
547 head = CullList( b1, b1 );
553 FreeBrushList( sub );
555 tail = AddBrushListToTail( sub2, tail );
556 head = CullList( b1, b2 );
561 if ( !b2 ) { // b1 is no longer intersecting anything, so keep it
567 Sys_FPrintf( SYS_VRB, "output brushes: %i\n", CountBrushList( keep ) );
570 WriteBrushList( "after.gl", keep, false );
571 WriteBrushMap( "after.map", keep );
583 bspbrush_t *InitialBrushList( bspbrush_t *list ){
585 bspbrush_t *out, *newb;
588 // only return brushes that have visible faces
590 for ( b = list ; b ; b = b->next )
593 for ( i = 0 ; i < b->numsides ; i++ )
594 if ( b->sides[i].visible ) {
597 if ( i == b->numsides ) {
601 newb = CopyBrush( b );
605 // clear visible, so it must be set by MarkVisibleFaces_r
606 // to be used in the optimized list
607 for ( i = 0 ; i < b->numsides ; i++ )
609 newb->sides[i].original = &b->sides[i];
610 // newb->sides[i].visible = true;
611 b->sides[i].visible = false;
623 bspbrush_t *OptimizedBrushList( bspbrush_t *list ){
625 bspbrush_t *out, *newb;
628 // only return brushes that have visible faces
630 for ( b = list ; b ; b = b->next )
632 for ( i = 0 ; i < b->numsides ; i++ )
633 if ( b->sides[i].visible ) {
636 if ( i == b->numsides ) {
639 newb = CopyBrush( b );
644 // WriteBrushList ("vis.gl", out, true);