1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
/*
===========================================================================
Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
Doom 3 Source Code is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Doom 3 Source Code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
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.
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.
===========================================================================
*/
#ifndef __BRUSHBSP_H__
#define __BRUSHBSP_H__
#include "idlib/containers/VectorSet.h"
#include "idlib/containers/StrList.h"
#include "idlib/geometry/Winding.h"
#include "idlib/MapFile.h"
#include "tools/compilers/aas/Brush.h"
/*
===============================================================================
BrushBSP
===============================================================================
*/
class idBrushBSP;
class idBrushBSPNode;
class idBrushBSPPortal;
//===============================================================
//
// idBrushBSPPortal
//
//===============================================================
class idBrushBSPPortal {
friend class idBrushBSP;
friend class idBrushBSPNode;
public:
idBrushBSPPortal( void );
~idBrushBSPPortal( void );
void AddToNodes( idBrushBSPNode *front, idBrushBSPNode *back );
void RemoveFromNode( idBrushBSPNode *l );
void Flip( void );
int Split( const idPlane &splitPlane, idBrushBSPPortal **front, idBrushBSPPortal **back );
idWinding * GetWinding( void ) const { return winding; }
const idPlane & GetPlane( void ) const { return plane; }
void SetFaceNum( int num ) { faceNum = num; }
int GetFaceNum( void ) const { return faceNum; }
int GetFlags( void ) const { return flags; }
void SetFlag( int flag ) { flags |= flag; }
void RemoveFlag( int flag ) { flags &= ~flag; }
idBrushBSPPortal * Next( int side ) const { return next[side]; }
idBrushBSPNode * GetNode( int side ) const { return nodes[side]; }
private:
idPlane plane; // portal plane
int planeNum; // number of plane this portal is on
idWinding * winding; // portal winding
idBrushBSPNode * nodes[2]; // nodes this portal seperates
idBrushBSPPortal * next[2]; // next portal in list for both nodes
int flags; // portal flags
int faceNum; // number of the face created for this portal
};
//===============================================================
//
// idBrushBSPNode
//
//===============================================================
#define NODE_VISITED BIT(30)
#define NODE_DONE BIT(31)
class idBrushBSPNode {
friend class idBrushBSP;
friend class idBrushBSPPortal;
public:
idBrushBSPNode( void );
~idBrushBSPNode( void );
void SetContentsFromBrushes( void );
idBounds GetPortalBounds( void );
idBrushBSPNode * GetChild( int index ) const { return children[index]; }
idBrushBSPNode * GetParent( void ) const { return parent; }
void SetContents( int contents ) { this->contents = contents; }
int GetContents( void ) const { return contents; }
const idPlane & GetPlane( void ) const { return plane; }
idBrushBSPPortal * GetPortals( void ) const { return portals; }
void SetAreaNum( int num ) { areaNum = num; }
int GetAreaNum( void ) const { return areaNum; }
int GetFlags( void ) const { return flags; }
void SetFlag( int flag ) { flags |= flag; }
void RemoveFlag( int flag ) { flags &= ~flag; }
bool TestLeafNode( void );
// remove the flag from nodes found by flooding through portals to nodes with the flag set
void RemoveFlagFlood( int flag );
// recurse down the tree and remove the flag from all visited nodes
void RemoveFlagRecurse( int flag );
// first recurse down the tree and flood from there
void RemoveFlagRecurseFlood( int flag );
// returns side of the plane the node is on
int PlaneSide( const idPlane &plane, float epsilon = ON_EPSILON ) const;
// split the leaf node with a plane
bool Split( const idPlane &splitPlane, int splitPlaneNum );
private:
idPlane plane; // split plane if this is not a leaf node
idBrush * volume; // node volume
int contents; // node contents
idBrushList brushList; // list with brushes for this node
idBrushBSPNode * parent; // parent of this node
idBrushBSPNode * children[2]; // both are NULL if this is a leaf node
idBrushBSPPortal * portals; // portals of this node
int flags; // node flags
int areaNum; // number of the area created for this node
int occupied; // true when portal is occupied
};
//===============================================================
//
// idBrushBSP
//
//===============================================================
class idBrushBSP {
public:
idBrushBSP( void );
~idBrushBSP( void );
// build a bsp tree from a set of brushes
void Build( idBrushList brushList, int skipContents,
bool (*ChopAllowed)( idBrush *b1, idBrush *b2 ),
bool (*MergeAllowed)( idBrush *b1, idBrush *b2 ) );
// remove splits in subspaces with the given contents
void PruneTree( int contents );
// portalize the bsp tree
void Portalize( void );
// remove subspaces outside the map not reachable by entities
bool RemoveOutside( const idMapFile *mapFile, int contents, const idStrList &classNames );
// write file with a trace going through a leak
void LeakFile( const idStr &fileName );
// try to merge portals
void MergePortals( int skipContents );
// try to merge the two leaf nodes at either side of the portal
bool TryMergeLeafNodes( idBrushBSPPortal *portal, int side );
void PruneMergedTree_r( idBrushBSPNode *node );
// melt portal windings
void MeltPortals( int skipContents );
// write a map file with a brush for every leaf node that has the given contents
void WriteBrushMap( const idStr &fileName, const idStr &ext, int contents );
// bounds for the whole tree
const idBounds & GetTreeBounds( void ) const { return treeBounds; }
// root node of the tree
idBrushBSPNode * GetRootNode( void ) const { return root; }
private:
idBrushBSPNode * root;
idBrushBSPNode * outside;
idBounds treeBounds;
idPlaneSet portalPlanes;
int numGridCells;
int numSplits;
int numGridCellSplits;
int numPrunedSplits;
int numPortals;
int solidLeafNodes;
int outsideLeafNodes;
int insideLeafNodes;
int numMergedPortals;
int numInsertedPoints;
idVec3 leakOrigin;
int brushMapContents;
idBrushMap * brushMap;
bool (*BrushChopAllowed)( idBrush *b1, idBrush *b2 );
bool (*BrushMergeAllowed)( idBrush *b1, idBrush *b2 );
private:
void RemoveMultipleLeafNodeReferences_r( idBrushBSPNode *node );
void Free_r( idBrushBSPNode *node );
void IncreaseNumSplits( void );
bool IsValidSplitter( const idBrushSide *side );
int BrushSplitterStats( const idBrush *brush, int planeNum, const idPlaneSet &planeList, bool *testedPlanes, struct splitterStats_s &stats );
int FindSplitter( idBrushBSPNode *node, const idPlaneSet &planeList, bool *testedPlanes, struct splitterStats_s &bestStats );
void SetSplitterUsed( idBrushBSPNode *node, int planeNum );
idBrushBSPNode * BuildBrushBSP_r( idBrushBSPNode *node, const idPlaneSet &planeList, bool *testedPlanes, int skipContents );
idBrushBSPNode * ProcessGridCell( idBrushBSPNode *node, int skipContents );
void BuildGrid_r( idList<idBrushBSPNode *> &gridCells, idBrushBSPNode *node );
void PruneTree_r( idBrushBSPNode *node, int contents );
void MakeOutsidePortals( void );
idWinding * BaseWindingForNode( idBrushBSPNode *node );
void MakeNodePortal( idBrushBSPNode *node );
void SplitNodePortals( idBrushBSPNode *node );
void MakeTreePortals_r( idBrushBSPNode *node );
void FloodThroughPortals_r( idBrushBSPNode *node, int contents, int depth );
bool FloodFromOrigin( const idVec3 &origin, int contents );
bool FloodFromEntities( const idMapFile *mapFile, int contents, const idStrList &classNames );
void RemoveOutside_r( idBrushBSPNode *node, int contents );
void SetPortalPlanes_r( idBrushBSPNode *node, idPlaneSet &planeList );
void SetPortalPlanes( void );
void MergePortals_r( idBrushBSPNode *node, int skipContents );
void MergeLeafNodePortals( idBrushBSPNode *node, int skipContents );
void UpdateTreeAfterMerge_r( idBrushBSPNode *node, const idBounds &bounds, idBrushBSPNode *oldNode, idBrushBSPNode *newNode );
void RemoveLeafNodeColinearPoints( idBrushBSPNode *node );
void RemoveColinearPoints_r( idBrushBSPNode *node, int skipContents );
void MeltFlood_r( idBrushBSPNode *node, int skipContents, idBounds &bounds, idVectorSet<idVec3,3> &vertexList );
void MeltLeafNodePortals( idBrushBSPNode *node, int skipContents, idVectorSet<idVec3,3> &vertexList );
void MeltPortals_r( idBrushBSPNode *node, int skipContents, idVectorSet<idVec3,3> &vertexList );
};
#endif /* !__BRUSHBSP_H__ */
|
