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 #define BRUSH_EPSILON 0.1f
35 #define BRUSH_PLANE_NORMAL_EPSILON 0.00001f
36 #define BRUSH_PLANE_DIST_EPSILON 0.01f
38 #define OUTPUT_UPDATE_TIME 500 // update every 500 msec
40 //#define OUTPUT_CHOP_STATS
47 void DisplayRealTimeString( char *string, ... ) {
49 char buf[MAX_STRING_CHARS];
50 static int lastUpdateTime;
53 time = Sys_Milliseconds();
54 if ( time > lastUpdateTime + OUTPUT_UPDATE_TIME ) {
55 va_start( argPtr, string );
56 vsprintf( buf, string, argPtr );
58 common->Printf( buf );
59 lastUpdateTime = time;
64 //===============================================================
68 //===============================================================
72 idBrushSide::idBrushSide
75 idBrushSide::idBrushSide( void ) {
83 idBrushSide::idBrushSide
86 idBrushSide::idBrushSide( const idPlane &plane, int planeNum ) {
89 this->planeNum = planeNum;
95 idBrushSide::~idBrushSide
98 idBrushSide::~idBrushSide( void ) {
109 idBrushSide *idBrushSide::Copy( void ) const {
112 side = new idBrushSide( plane, planeNum );
115 side->winding = winding->Copy();
118 side->winding = NULL;
128 int idBrushSide::Split( const idPlane &splitPlane, idBrushSide **front, idBrushSide **back ) const {
129 idWinding *frontWinding, *backWinding;
133 *front = *back = NULL;
135 winding->Split( splitPlane, 0.0f, &frontWinding, &backWinding );
137 if ( frontWinding ) {
138 (*front) = new idBrushSide( plane, planeNum );
139 (*front)->winding = frontWinding;
140 (*front)->flags = flags;
144 (*back) = new idBrushSide( plane, planeNum );
145 (*back)->winding = backWinding;
146 (*back)->flags = flags;
149 if ( frontWinding && backWinding ) {
150 return PLANESIDE_CROSS;
152 else if ( frontWinding ) {
153 return PLANESIDE_FRONT;
156 return PLANESIDE_BACK;
161 //===============================================================
165 //===============================================================
172 idBrush::idBrush( void ) {
173 contents = flags = 0;
176 windingsValid = false;
185 idBrush::~idBrush( void ) {
186 for ( int i = 0; i < sides.Num(); i++ ) {
193 idBrush::RemoveSidesWithoutWinding
196 bool idBrush::RemoveSidesWithoutWinding( void ) {
199 for ( i = 0; i < sides.Num(); i++ ) {
201 if ( sides[i]->winding ) {
205 sides.RemoveIndex( i );
209 return ( sides.Num() >= 4 );
214 idBrush::CreateWindings
217 bool idBrush::CreateWindings( void ) {
222 for ( i = 0; i < sides.Num(); i++ ) {
225 if ( side->winding ) {
226 delete side->winding;
229 side->winding = new idWinding( side->plane.Normal(), side->plane.Dist() );
231 for ( j = 0; j < sides.Num() && side->winding; j++ ) {
235 // keep the winding if on the clip plane
236 side->winding = side->winding->Clip( -sides[j]->plane, BRUSH_EPSILON, true );
239 if ( side->winding ) {
240 for ( j = 0; j < side->winding->GetNumPoints(); j++ ) {
241 bounds.AddPoint( (*side->winding)[j].ToVec3() );
246 if ( bounds[0][0] > bounds[1][0] ) {
249 for ( i = 0; i < 3; i++ ) {
250 if ( bounds[0][i] < MIN_WORLD_COORD || bounds[1][i] > MAX_WORLD_COORD ) {
255 windingsValid = true;
265 void idBrush::BoundBrush( const idBrush *original ) {
270 assert( windingsValid );
273 for ( i = 0; i < sides.Num(); i++ ) {
282 for ( j = 0; j < w->GetNumPoints(); j++ ) {
283 bounds.AddPoint( (*w)[j].ToVec3() );
287 if ( bounds[0][0] > bounds[1][0] ) {
289 idBrushMap *bm = new idBrushMap( "error_brush", "_original" );
290 bm->WriteBrush( original );
293 common->Error( "idBrush::BoundBrush: brush %d on entity %d without windings", primitiveNum, entityNum );
296 for ( i = 0; i < 3; i++ ) {
297 if ( bounds[0][i] < MIN_WORLD_COORD || bounds[1][i] > MAX_WORLD_COORD ) {
299 idBrushMap *bm = new idBrushMap( "error_brush", "_original" );
300 bm->WriteBrush( original );
303 common->Error( "idBrush::BoundBrush: brush %d on entity %d is unbounded", primitiveNum, entityNum );
313 bool idBrush::FromSides( idList<idBrushSide *> &sideList ) {
316 for ( i = 0; i < sideList.Num(); i++ ) {
317 sides.Append( sideList[i] );
322 return CreateWindings();
330 bool idBrush::FromWinding( const idWinding &w, const idPlane &windingPlane ) {
333 idVec3 normal, axialNormal;
335 sides.Append( new idBrushSide( windingPlane, -1 ) );
336 sides.Append( new idBrushSide( -windingPlane, -1 ) );
339 for ( i = 1; i < 3; i++ ) {
340 if ( idMath::Fabs( windingPlane.Normal()[i] ) > idMath::Fabs( windingPlane.Normal()[bestAxis] ) ) {
344 axialNormal = vec3_origin;
345 if ( windingPlane.Normal()[bestAxis] > 0.0f ) {
346 axialNormal[bestAxis] = 1.0f;
349 axialNormal[bestAxis] = -1.0f;
352 for ( i = 0; i < w.GetNumPoints(); i++ ) {
353 j = (i+1) % w.GetNumPoints();
354 normal = ( w[j].ToVec3() - w[i].ToVec3() ).Cross( axialNormal );
355 if ( normal.Normalize() < 0.5f ) {
358 plane.SetNormal( normal );
359 plane.FitThroughPoint( w[j].ToVec3() );
360 sides.Append( new idBrushSide( plane, -1 ) );
363 if ( sides.Num() < 4 ) {
364 for ( i = 0; i < sides.Num(); i++ ) {
371 sides[0]->winding = w.Copy();
372 windingsValid = true;
383 bool idBrush::FromBounds( const idBounds &bounds ) {
388 for ( axis = 0; axis < 3; axis++ ) {
389 for ( dir = -1; dir <= 1; dir += 2 ) {
390 normal = vec3_origin;
392 plane.SetNormal( normal );
393 plane.SetDist( dir * bounds[(dir == 1)][axis] );
394 sides.Append( new idBrushSide( plane, -1 ) );
398 return CreateWindings();
406 void idBrush::Transform( const idVec3 &origin, const idMat3 &axis ) {
408 bool transformed = false;
410 if ( axis.IsRotated() ) {
411 for ( i = 0; i < sides.Num(); i++ ) {
412 sides[i]->plane.RotateSelf( vec3_origin, axis );
416 if ( origin != vec3_origin ) {
417 for ( i = 0; i < sides.Num(); i++ ) {
418 sides[i]->plane.TranslateSelf( origin );
432 float idBrush::GetVolume( void ) const {
436 float d, area, volume;
438 // grab the first valid point as a corner
440 for ( i = 0; i < sides.Num(); i++ ) {
441 w = sides[i]->winding;
449 corner = (*w)[0].ToVec3();
451 // create tetrahedrons to all other sides
453 for ( ; i < sides.Num(); i++) {
454 w = sides[i]->winding;
458 d = -( corner * sides[i]->plane.Normal() - sides[i]->plane.Dist() );
463 return ( volume * ( 1.0f / 3.0f ) );
471 bool idBrush::Subtract( const idBrush *b, idBrushList &list ) const {
473 idBrush *front, *back;
478 for ( i = 0; i < b->sides.Num() && in; i++ ) {
480 in->Split( b->sides[i]->plane, b->sides[i]->planeNum, &front, &back );
486 list.AddToTail( front );
490 // if didn't really intersect
505 bool idBrush::TryMerge( const idBrush *brush, const idPlaneSet &planeList ) {
506 int i, j, k, l, m, seperatingPlane;
507 const idBrush *brushes[2];
509 const idPlane *plane;
511 // brush bounds should overlap
512 for ( i = 0; i < 3; i++ ) {
513 if ( bounds[0][i] > brush->bounds[1][i] + 0.1f ) {
516 if ( bounds[1][i] < brush->bounds[0][i] - 0.1f ) {
521 // the brushes should share an opposite plane
522 seperatingPlane = -1;
523 for ( i = 0; i < GetNumSides(); i++ ) {
524 for ( j = 0; j < brush->GetNumSides(); j++ ) {
525 if ( GetSide(i)->GetPlaneNum() == (brush->GetSide(j)->GetPlaneNum() ^ 1) ) {
526 // may only have one seperating plane
527 if ( seperatingPlane != -1 ) {
530 seperatingPlane = GetSide(i)->GetPlaneNum();
535 if ( seperatingPlane == -1 ) {
542 for ( i = 0; i < 2; i++ ) {
546 for ( k = 0; k < brushes[i]->GetNumSides(); k++ ) {
548 // if the brush side plane is the seprating plane
549 if ( !( ( brushes[i]->GetSide(k)->GetPlaneNum() ^ seperatingPlane ) >> 1 ) ) {
553 plane = &brushes[i]->GetSide(k)->GetPlane();
555 // all the non seperating brush sides of the other brush should be at the back or on the plane
556 for ( l = 0; l < brushes[j]->GetNumSides(); l++ ) {
558 w = brushes[j]->GetSide(l)->GetWinding();
563 if ( !( ( brushes[j]->GetSide(l)->GetPlaneNum() ^ seperatingPlane ) >> 1 ) ) {
567 for ( m = 0; m < w->GetNumPoints(); m++ ) {
568 if ( plane->Distance( (*w)[m].ToVec3() ) > 0.1f ) {
576 // add any sides from the other brush to this brush
577 for ( i = 0; i < brush->GetNumSides(); i++ ) {
578 for ( j = 0; j < GetNumSides(); j++ ) {
579 if ( !( ( brush->GetSide(i)->GetPlaneNum() ^ GetSide(j)->GetPlaneNum() ) >> 1 ) ) {
583 if ( j < GetNumSides() ) {
584 sides[j]->flags &= brush->GetSide(i)->GetFlags();
587 sides.Append( brush->GetSide(i)->Copy() );
590 // remove any side from this brush that is the opposite of a side of the other brush
591 for ( i = 0; i < GetNumSides(); i++ ) {
592 for ( j = 0; j < brush->GetNumSides(); j++ ) {
593 if ( GetSide(i)->GetPlaneNum() == ( brush->GetSide(j)->GetPlaneNum() ^ 1 ) ) {
597 if ( j < brush->GetNumSides() ) {
599 sides.RemoveIndex(i);
605 contents |= brush->contents;
618 int idBrush::Split( const idPlane &plane, int planeNum, idBrush **front, idBrush **back ) const {
620 idBrushSide *side, *frontSide, *backSide;
621 float dist, maxBack, maxFront, *maxBackWinding, *maxFrontWinding;
624 assert( windingsValid );
633 res = bounds.PlaneSide( plane, -BRUSH_EPSILON );
634 if ( res == PLANESIDE_FRONT ) {
640 if ( res == PLANESIDE_BACK ) {
647 maxBackWinding = (float *) _alloca16( sides.Num() * sizeof(float) );
648 maxFrontWinding = (float *) _alloca16( sides.Num() * sizeof(float) );
650 maxFront = maxBack = 0.0f;
651 for ( i = 0; i < sides.Num(); i++ ) {
660 maxBackWinding[i] = 10.0f;
661 maxFrontWinding[i] = -10.0f;
663 for ( j = 0; j < w->GetNumPoints(); j++ ) {
665 dist = plane.Distance( (*w)[j].ToVec3() );
666 if ( dist > maxFrontWinding[i] ) {
667 maxFrontWinding[i] = dist;
669 if ( dist < maxBackWinding[i] ) {
670 maxBackWinding[i] = dist;
674 if ( maxFrontWinding[i] > maxFront ) {
675 maxFront = maxFrontWinding[i];
677 if ( maxBackWinding[i] < maxBack ) {
678 maxBack = maxBackWinding[i];
682 if ( maxFront < BRUSH_EPSILON ) {
686 return PLANESIDE_BACK;
689 if ( maxBack > -BRUSH_EPSILON ) {
693 return PLANESIDE_FRONT;
696 mid = new idWinding( plane.Normal(), plane.Dist() );
698 for ( i = 0; i < sides.Num() && mid; i++ ) {
699 mid = mid->Clip( -sides[i]->plane, BRUSH_EPSILON, false );
703 if ( mid->IsTiny() ) {
707 else if ( mid->IsHuge() ) {
708 // if the winding is huge then the brush is unbounded
709 common->Warning( "brush %d on entity %d is unbounded"
710 "( %1.2f %1.2f %1.2f )-( %1.2f %1.2f %1.2f )-( %1.2f %1.2f %1.2f )", primitiveNum, entityNum,
711 bounds[0][0], bounds[0][1], bounds[0][2], bounds[1][0], bounds[1][1], bounds[1][2],
712 bounds[1][0]-bounds[0][0], bounds[1][1]-bounds[0][1], bounds[1][2]-bounds[0][2] );
719 if ( maxFront > - maxBack ) {
723 return PLANESIDE_FRONT;
729 return PLANESIDE_BACK;
733 if ( !front && !back ) {
735 return PLANESIDE_CROSS;
738 *front = new idBrush();
739 (*front)->SetContents( contents );
740 (*front)->SetEntityNum( entityNum );
741 (*front)->SetPrimitiveNum( primitiveNum );
742 *back = new idBrush();
743 (*back)->SetContents( contents );
744 (*back)->SetEntityNum( entityNum );
745 (*back)->SetPrimitiveNum( primitiveNum );
747 for ( i = 0; i < sides.Num(); i++ ) {
750 if ( !side->winding ) {
754 // if completely at the front
755 if ( maxBackWinding[i] >= BRUSH_EPSILON ) {
756 (*front)->sides.Append( side->Copy() );
758 // if completely at the back
759 else if ( maxFrontWinding[i] <= -BRUSH_EPSILON ) {
760 (*back)->sides.Append( side->Copy() );
764 side->Split( plane, &frontSide, &backSide );
766 (*front)->sides.Append( frontSide );
768 else if ( maxFrontWinding[i] > -BRUSH_EPSILON ) {
769 // favor an overconstrained brush
771 side->winding = side->winding->Clip( idPlane( plane.Normal(), (plane.Dist() - (BRUSH_EPSILON+0.02f)) ), 0.01f, true );
772 assert( side->winding );
773 (*front)->sides.Append( side );
776 (*back)->sides.Append( backSide );
778 else if ( maxBackWinding[i] < BRUSH_EPSILON ) {
779 // favor an overconstrained brush
781 side->winding = side->winding->Clip( idPlane( -plane.Normal(), -(plane.Dist() + (BRUSH_EPSILON+0.02f)) ), 0.01f, true );
782 assert( side->winding );
783 (*back)->sides.Append( side );
788 side = new idBrushSide( -plane, planeNum^1 );
789 side->winding = mid->Reverse();
790 side->flags |= SFL_SPLIT;
791 (*front)->sides.Append( side );
792 (*front)->windingsValid = true;
793 (*front)->BoundBrush( this );
795 side = new idBrushSide( plane, planeNum );
797 side->flags |= SFL_SPLIT;
798 (*back)->sides.Append( side );
799 (*back)->windingsValid = true;
800 (*back)->BoundBrush( this );
802 return PLANESIDE_CROSS;
807 idBrush::AddBevelsForAxialBox
810 #define BRUSH_BEVEL_EPSILON 0.1f
812 void idBrush::AddBevelsForAxialBox( void ) {
813 int axis, dir, i, j, k, l, order;
814 idBrushSide *side, *newSide;
820 assert( windingsValid );
822 // add the axial planes
824 for ( axis = 0; axis < 3; axis++ ) {
826 for ( dir = -1; dir <= 1; dir += 2, order++ ) {
828 // see if the plane is already present
829 for ( i = 0; i < sides.Num(); i++ ) {
831 if ( sides[i]->plane.Normal()[axis] >= 0.9999f ) {
836 if ( sides[i]->plane.Normal()[axis] <= -0.9999f ) {
842 if ( i >= sides.Num() ) {
843 normal = vec3_origin;
845 plane.SetNormal( normal );
846 plane.SetDist( dir * bounds[(dir == 1)][axis] );
847 newSide = new idBrushSide( plane, -1 );
848 newSide->SetFlag( SFL_BEVEL );
849 sides.Append( newSide );
854 // if the brush is pure axial we're done
855 if ( sides.Num() == 6 ) {
859 // test the non-axial plane edges
860 for ( i = 0; i < sides.Num(); i++ ) {
867 for ( j = 0; j < w->GetNumPoints(); j++) {
868 k = (j+1) % w->GetNumPoints();
869 vec = (*w)[j].ToVec3() - (*w)[k].ToVec3();
870 if ( vec.Normalize() < 0.5f ) {
873 for ( k = 0; k < 3; k++ ) {
874 if ( vec[k] == 1.0f || vec[k] == -1.0f || (vec[k] == 0.0f && vec[(k+1)%3] == 0.0f) ) {
879 continue; // only test non-axial edges
882 // try the six possible slanted axials from this edge
883 for ( axis = 0; axis < 3; axis++ ) {
885 for ( dir = -1; dir <= 1; dir += 2 ) {
888 normal = vec3_origin;
890 normal = vec.Cross( normal );
891 if ( normal.Normalize() < 0.5f ) {
894 plane.SetNormal( normal );
895 plane.FitThroughPoint( (*w)[j].ToVec3() );
897 // if all the points on all the sides are
898 // behind this plane, it is a proper edge bevel
899 for ( k = 0; k < sides.Num(); k++ ) {
901 // if this plane has allready been used, skip it
902 if ( plane.Compare( sides[k]->plane, 0.001f, 0.1f ) ) {
906 w2 = sides[k]->winding;
911 for ( l = 0; l < w2->GetNumPoints(); l++ ) {
912 d = plane.Distance( (*w2)[l].ToVec3() );
913 if ( d > BRUSH_BEVEL_EPSILON ) {
914 break; // point at the front
920 // if some point was at the front
921 if ( l < w2->GetNumPoints() ) {
924 // if no points at the back then the winding is on the bevel plane
925 if ( minBack > -BRUSH_BEVEL_EPSILON ) {
930 if ( k < sides.Num() ) {
931 continue; // wasn't part of the outer hull
935 newSide = new idBrushSide( plane, -1 );
936 newSide->SetFlag( SFL_BEVEL );
937 sides.Append( newSide );
946 idBrush::ExpandForAxialBox
949 void idBrush::ExpandForAxialBox( const idBounds &bounds ) {
954 AddBevelsForAxialBox();
956 for ( i = 0; i < sides.Num(); i++ ) {
959 for ( j = 0; j < 3; j++ ) {
960 if ( side->plane.Normal()[j] > 0.0f ) {
968 side->plane.SetDist( side->plane.Dist() + v * -side->plane.Normal() );
971 if ( !CreateWindings() ) {
972 common->Error( "idBrush::ExpandForAxialBox: brush %d on entity %d imploded", primitiveNum, entityNum );
976 // after expansion at least all non bevel sides should have a winding
977 for ( i = 0; i < sides.Num(); i++ ) {
979 if ( !side->winding ) {
980 if ( !( side->flags & SFL_BEVEL ) ) {
993 idBrush *idBrush::Copy( void ) const {
998 b->entityNum = entityNum;
999 b->primitiveNum = primitiveNum;
1000 b->contents = contents;
1001 b->windingsValid = windingsValid;
1003 for ( i = 0; i < sides.Num(); i++ ) {
1004 b->sides.Append( sides[i]->Copy() );
1010 //===============================================================
1014 //===============================================================
1018 idBrushList::idBrushList
1021 idBrushList::idBrushList( void ) {
1022 numBrushes = numBrushSides = 0;
1028 idBrushList::~idBrushList
1031 idBrushList::~idBrushList( void ) {
1036 idBrushList::GetBounds
1039 idBounds idBrushList::GetBounds( void ) const {
1044 for ( b = Head(); b; b = b->Next() ) {
1045 bounds += b->GetBounds();
1052 idBrushList::AddToTail
1055 void idBrushList::AddToTail( idBrush *brush ) {
1065 numBrushSides += brush->sides.Num();
1070 idBrushList::AddToTail
1073 void idBrushList::AddToTail( idBrushList &list ) {
1074 idBrush *brush, *next;
1076 for ( brush = list.head; brush; brush = next ) {
1087 numBrushSides += brush->sides.Num();
1089 list.head = list.tail = NULL;
1090 list.numBrushes = 0;
1095 idBrushList::AddToFront
1098 void idBrushList::AddToFront( idBrush *brush ) {
1105 numBrushSides += brush->sides.Num();
1110 idBrushList::AddToFront
1113 void idBrushList::AddToFront( idBrushList &list ) {
1114 idBrush *brush, *next;
1116 for ( brush = list.head; brush; brush = next ) {
1124 numBrushSides += brush->sides.Num();
1126 list.head = list.tail = NULL;
1127 list.numBrushes = 0;
1135 void idBrushList::Remove( idBrush *brush ) {
1139 for ( b = head; b; b = b->next ) {
1142 last->next = b->next;
1151 numBrushSides -= brush->sides.Num();
1163 void idBrushList::Delete( idBrush *brush ) {
1167 for ( b = head; b; b = b->next ) {
1170 last->next = b->next;
1179 numBrushSides -= b->sides.Num();
1192 idBrushList *idBrushList::Copy( void ) const {
1196 list = new idBrushList;
1198 for ( brush = head; brush; brush = brush->next ) {
1199 list->AddToTail( brush->Copy() );
1209 void idBrushList::Free( void ) {
1210 idBrush *brush, *next;
1212 for ( brush = head; brush; brush = next ) {
1217 numBrushes = numBrushSides = 0;
1225 void idBrushList::Split( const idPlane &plane, int planeNum, idBrushList &frontList, idBrushList &backList, bool useBrushSavedPlaneSide ) {
1226 idBrush *b, *front, *back;
1231 if ( !useBrushSavedPlaneSide ) {
1232 for ( b = head; b; b = b->next ) {
1233 b->Split( plane, planeNum, &front, &back );
1235 frontList.AddToTail( front );
1238 backList.AddToTail( back );
1244 for ( b = head; b; b = b->next ) {
1245 if ( b->savedPlaneSide & BRUSH_PLANESIDE_BOTH ) {
1246 b->Split( plane, planeNum, &front, &back );
1248 frontList.AddToTail( front );
1251 backList.AddToTail( back );
1254 else if ( b->savedPlaneSide & BRUSH_PLANESIDE_FRONT ) {
1255 frontList.AddToTail( b->Copy() );
1258 backList.AddToTail( b->Copy() );
1268 void idBrushList::Chop( bool (*ChopAllowed)( idBrush *b1, idBrush *b2 ) ) {
1269 idBrush *b1, *b2, *next;
1270 idBrushList sub1, sub2, keep;
1272 idPlaneSet planeList;
1274 #ifdef OUTPUT_CHOP_STATS
1275 common->Printf( "[Brush CSG]\n");
1276 common->Printf( "%6d original brushes\n", this->Num() );
1279 CreatePlaneList( planeList );
1281 for ( b1 = this->Head(); b1; b1 = this->Head() ) {
1283 for ( b2 = b1->next; b2; b2 = next ) {
1287 for ( i = 0; i < 3; i++ ) {
1288 if ( b1->bounds[0][i] >= b2->bounds[1][i] ) {
1291 if ( b1->bounds[1][i] <= b2->bounds[0][i] ) {
1299 for ( i = 0; i < b1->GetNumSides(); i++ ) {
1300 for ( j = 0; j < b2->GetNumSides(); j++ ) {
1301 if ( b1->GetSide(i)->GetPlaneNum() == ( b2->GetSide(j)->GetPlaneNum() ^ 1 ) ) {
1302 // opposite planes, so not touching
1306 if ( j < b2->GetNumSides() ) {
1310 if ( i < b1->GetNumSides() ) {
1320 // if b2 may chop up b1
1321 if ( !ChopAllowed || ChopAllowed( b2, b1 ) ) {
1322 if ( !b1->Subtract( b2, sub1 ) ) {
1323 // didn't really intersect
1326 if ( sub1.IsEmpty() ) {
1327 // b1 is swallowed by b2
1334 // if b1 may chop up b2
1335 if ( !ChopAllowed || ChopAllowed( b1, b2 ) ) {
1336 if ( !b2->Subtract( b1, sub2 ) ) {
1337 // didn't really intersect
1340 if ( sub2.IsEmpty() ) {
1341 // b2 is swallowed by b1
1349 if ( sub1.IsEmpty() && sub2.IsEmpty() ) {
1353 // don't allow too much fragmentation
1354 if ( c1 > 2 && c2 > 2 ) {
1362 this->AddToTail( sub1 );
1368 this->AddToTail( sub2 );
1375 // b1 is no longer intersecting anything, so keep it
1377 keep.AddToTail( b1 );
1378 #ifdef OUTPUT_CHOP_STATS
1379 DisplayRealTimeString( "\r%6d", keep.numBrushes );
1386 #ifdef OUTPUT_CHOP_STATS
1387 common->Printf( "\r%6d output brushes\n", Num() );
1397 void idBrushList::Merge( bool (*MergeAllowed)( idBrush *b1, idBrush *b2 ) ) {
1398 idPlaneSet planeList;
1399 idBrush *b1, *b2, *nextb2;
1402 common->Printf( "[Brush Merge]\n");
1403 common->Printf( "%6d original brushes\n", Num() );
1405 CreatePlaneList( planeList );
1408 for ( b1 = Head(); b1; b1 = b1->next ) {
1410 for ( b2 = Head(); b2; b2 = nextb2 ) {
1411 nextb2 = b2->Next();
1417 if ( MergeAllowed && !MergeAllowed( b1, b2 ) ) {
1421 if ( b1->TryMerge( b2, planeList ) ) {
1423 DisplayRealTimeString( "\r%6d", ++numMerges );
1429 common->Printf( "\r%6d brushes merged\n", numMerges );
1434 idBrushList::SetFlagOnFacingBrushSides
1437 void idBrushList::SetFlagOnFacingBrushSides( const idPlane &plane, int flag ) {
1442 for ( b = head; b; b = b->next ) {
1443 if ( idMath::Fabs( b->GetBounds().PlaneDistance( plane ) ) > 0.1f ) {
1446 for ( i = 0; i < b->GetNumSides(); i++ ) {
1447 w = b->GetSide(i)->GetWinding();
1449 if ( b->GetSide(i)->GetPlane().Compare( plane, BRUSH_PLANE_NORMAL_EPSILON, BRUSH_PLANE_DIST_EPSILON ) ) {
1450 b->GetSide(i)->SetFlag( flag );
1454 if ( w->PlaneSide( plane ) == SIDE_ON ) {
1455 b->GetSide(i)->SetFlag( flag );
1463 idBrushList::CreatePlaneList
1466 void idBrushList::CreatePlaneList( idPlaneSet &planeList ) const {
1471 planeList.Resize( 512, 128 );
1472 for ( b = Head(); b; b = b->Next() ) {
1473 for ( i = 0; i < b->GetNumSides(); i++ ) {
1474 side = b->GetSide( i );
1475 side->SetPlaneNum( planeList.FindPlane( side->GetPlane(), BRUSH_PLANE_NORMAL_EPSILON, BRUSH_PLANE_DIST_EPSILON ) );
1482 idBrushList::CreatePlaneList
1485 void idBrushList::WriteBrushMap( const idStr &fileName, const idStr &ext ) const {
1488 map = new idBrushMap( fileName, ext );
1489 map->WriteBrushList( *this );
1494 //===============================================================
1498 //===============================================================
1502 idBrushMap::idBrushMap
1505 idBrushMap::idBrushMap( const idStr &fileName, const idStr &ext ) {
1509 qpath.StripFileExtension();
1511 qpath.SetFileExtension( "map" );
1513 common->Printf( "writing %s...\n", qpath.c_str() );
1515 fp = fileSystem->OpenFileWrite( qpath, "fs_devpath" );
1517 common->Error( "Couldn't open %s\n", qpath.c_str() );
1521 texture = "textures/washroom/btile01";
1523 fp->WriteFloatString( "Version %1.2f\n", (float) CURRENT_MAP_VERSION );
1524 fp->WriteFloatString( "{\n" );
1525 fp->WriteFloatString( "\"classname\" \"worldspawn\"\n" );
1532 idBrushMap::~idBrushMap
1535 idBrushMap::~idBrushMap( void ) {
1539 fp->WriteFloatString( "}\n" );
1540 fileSystem->CloseFile( fp );
1545 idBrushMap::WriteBrush
1548 void idBrushMap::WriteBrush( const idBrush *brush ) {
1556 fp->WriteFloatString( "// primitive %d\n{\nbrushDef3\n{\n", brushCount++ );
1558 for ( i = 0; i < brush->GetNumSides(); i++ ) {
1559 side = brush->GetSide( i );
1560 fp->WriteFloatString( " ( %f %f %f %f ) ", side->GetPlane()[0], side->GetPlane()[1], side->GetPlane()[2], -side->GetPlane().Dist() );
1561 fp->WriteFloatString( "( ( 0.031250 0 0 ) ( 0 0.031250 0 ) ) %s 0 0 0\n", texture.c_str() );
1564 fp->WriteFloatString( "}\n}\n" );
1569 idBrushMap::WriteBrushList
1572 void idBrushMap::WriteBrushList( const idBrushList &brushList ) {
1579 for ( b = brushList.Head(); b; b = b->Next() ) {