/
superblockmap.h
293 lines (249 loc) · 8.7 KB
/
superblockmap.h
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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
/**
* @file superblockmap.h
* BSP Builder SuperBlockmap. @ingroup map
*
* Design is effectively that of a 2-dimensional kd-tree.
*
* Based on glBSP 2.24 (in turn, based on BSP 2.3), which is hosted on
* SourceForge: http://sourceforge.net/projects/glbsp/
*
* @authors Copyright © 2007-2013 Daniel Swanson <danij@dengine.net>
* @authors Copyright © 2000-2007 Andrew Apted <ajapted@gmail.com>
* @authors Copyright © 1998-2000 Colin Reed <cph@moria.org.uk>
* @authors Copyright © 1998-2000 Lee Killough <killough@rsn.hp.com>
*
* @par License
* GPL: http://www.gnu.org/licenses/gpl.html
*
* <small>This program 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 2 of the License, or (at your
* option) any later version. This program 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 this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
* 02110-1301 USA</small>
*/
#ifndef LIBDENG_BSP_SUPERBLOCKMAP
#define LIBDENG_BSP_SUPERBLOCKMAP
#include "dd_def.h"
#include "dd_types.h"
#include "map/p_maptypes.h"
#include <de/Log>
#include <list>
namespace de {
namespace bsp {
class SuperBlock;
#ifdef RIGHT
# undef RIGHT
#endif
#ifdef LEFT
# undef LEFT
#endif
class SuperBlockmap
{
public:
/**
* @param bounds Bounding box in map coordinates for the whole blockmap.
*/
SuperBlockmap(const AABox& bounds);
~SuperBlockmap();
/**
* Retrieve the root SuperBlock.
* @return Root SuperBlock instance.
*/
SuperBlock& root();
/**
* Find the axis-aligned bounding box defined by the vertices of all
* HEdges within this superblockmap. If there are no HEdges linked to
* this then @a bounds will be initialized to the "cleared" state
* (i.e., min[x,y] > max[x,y]).
*
* @return bounds Determined bounds are written here.
*/
AABoxd findHEdgeBounds();
/**
* Empty this SuperBlockmap clearing all HEdges and sub-blocks.
*/
void clear();
operator SuperBlock&() { return root(); }
private:
struct Instance;
Instance* d;
friend class SuperBlock;
};
/**
* Subblocks:
* RIGHT - has the lower coordinates.
* LEFT - has the higher coordinates.
* Division of a block always occurs horizontally:
* e.g. 512x512 -> 256x512 -> 256x256.
*/
class SuperBlock
{
public:
typedef std::list<HEdge*> HEdges;
/// A SuperBlock may be subdivided with two child subblocks which are
/// uniquely identifiable by these associated ids.
enum ChildId
{
RIGHT,
LEFT
};
/// Assert that the specified value is a valid @a childId.
static void inline assertValidChildId(ChildId DENG_DEBUG_ONLY(childId))
{
Q_ASSERT(childId == RIGHT || childId == LEFT);
}
public:
SuperBlock& clear();
/**
* Retrieve the SuperBlockmap which owns this block.
* @return The owning SuperBlockmap instance.
*/
SuperBlockmap& blockmap() const;
/**
* Retrieve the axis-aligned bounding box defined for this superblock
* during instantiation. Note that this is NOT the bounds defined by
* the linked HEdges' vertices (see SuperBlock::findHEdgeBounds()).
*
* @return Axis-aligned bounding box.
*/
const AABox& bounds() const;
/**
* Is this block small enough to be considered a "leaf"? A leaf in this
* context is a block whose dimensions are <= [256, 256] and thus can
* not be subdivided any further.
*/
bool isLeaf() const;
bool hasParent() const;
SuperBlock* parent() const;
/**
* Does this block have a child subblock?
*/
bool hasChild(ChildId childId) const;
/**
* Does this block have a Right child subblock?
*/
inline bool hasRight() const { return hasChild(RIGHT); }
/**
* Does this block have a Left child subblock?
*/
inline bool hasLeft() const { return hasChild(LEFT); }
/**
* Retrieve a child of this subblock. Callers must first determine if a
* child is present using SuperBlock::hasChild() (or similar), attempting
* to call this with no child present results in fatal error.
*
* @param childId Subblock identifier.
* @return Selected subblock.
*/
SuperBlock* child(ChildId childId) const;
/**
* Returns the right sub-block.
* @see SuperBlock::child()
*/
inline SuperBlock* right() const { return child(RIGHT); }
/**
* Returns the left sub-block.
* @see SuperBlock::child()
*/
inline SuperBlock* left() const { return child(LEFT); }
/**
* Perform a depth-first traversal over all child superblocks and
* then ultimately visiting this instance, making a callback for
* each object visited. Iteration ends when all superblocks have
* been visited or @a callback returns a non-zero value.
*
* @param callback Callback function ptr.
* @param parameters Passed to the callback. Default=NULL.
*
* @return @c 0 iff iteration completed wholly.
*/
int traverse(int (C_DECL *callback)(SuperBlock*, void*), void* parameters=NULL);
/**
* Find the axis-aligned bounding box defined by the vertices of all
* HEdges within this superblock. If there are no HEdges linked to
* this then @a bounds will be initialized to the "cleared" state
* (i.e., min[x,y] > max[x,y]).
*
* @param bounds Determined bounds are written here.
*/
void findHEdgeBounds(AABoxd& bounds);
/**
* Retrieve the total number of HEdges linked in this superblock
* (including any within child superblocks).
*
* @param addReal Include the "real" half-edges in the total.
* @param addMini Include the "mini" half-edges in the total.
*
* @return Total HEdge count.
*/
uint hedgeCount(bool addReal, bool addMini) const;
/// Convenience functions for retrieving HEdge totals:
inline uint miniHEdgeCount() const { return hedgeCount(false, true); }
inline uint realHEdgeCount() const { return hedgeCount(true, false); }
inline uint totalHEdgeCount() const { return hedgeCount(true, true); }
/**
* Push (link) the given HEdge onto the FIFO list of half-edges linked
* to this superblock.
*
* @param hedge HEdge instance to add.
* @return SuperBlock instance the HEdge was actually linked to.
*/
SuperBlock& push(HEdge& hedge);
/**
* Pop (unlink) the next HEdge from the FIFO list of half-edges linked
* to this superblock.
*
* @return Previous top-most HEdge instance or @c NULL if empty.
*/
HEdge* pop();
const HEdges& hedges() const;
#ifdef DENG_DEBUG
static void DebugPrint(SuperBlock const& inst)
{
DENG2_FOR_EACH_CONST(SuperBlock::HEdges, it, inst.hedges())
{
HEdge* hedge = *it;
LOG_DEBUG("Build: %s %p sector: %d [%1.1f, %1.1f] -> [%1.1f, %1.1f]")
<< (hedge->lineDef? "NORM" : "MINI")
<< hedge << hedge->sector->origIndex()
<< hedge->v[0]->origin()[VX] << hedge->v[0]->origin()[VY]
<< hedge->v[1]->origin()[VX] << hedge->v[1]->origin()[VY];
}
}
#endif
private:
/**
* SuperBlock objects must be constructed within the context of an
* owning SuperBlockmap. Instantiation outside of this context is not
* permitted. @ref SuperBlockmap
*/
SuperBlock(SuperBlockmap& blockmap);
SuperBlock(SuperBlock& parent, ChildId childId, bool splitVertical);
~SuperBlock();
/**
* Attach a new SuperBlock instance as a child of this.
* @param childId Unique identifier of the child.
* @param splitVertical @c true= Subdivide this block on the y axis
* rather than the x axis.
*/
SuperBlock* addChild(ChildId childId, bool splitVertical);
inline SuperBlock* addRight(bool splitVertical) { return addChild(RIGHT, splitVertical); }
inline SuperBlock* addLeft(bool splitVertical) { return addChild(LEFT, splitVertical); }
private:
struct Instance;
Instance* d;
/**
* SuperBlockmap creates instances of SuperBlock so it needs to use
* the special private constructor that takes an existing superblock
* object reference as a parameter.
*/
friend struct SuperBlockmap::Instance;
};
} // namespace bsp
} // namespace de
#endif // LIBDENG_BSP_SUPERBLOCKMAP