3 Copyright (C) 2015 est31 <mtest31@outlook.com>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 #include "util/areastore.h"
21 #include "util/serialize.h"
22 #include "util/container.h"
25 #include <spatialindex/SpatialIndex.h>
26 #include <spatialindex/RTree.h>
27 #include <spatialindex/Point.h>
30 #define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z))
32 #define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \
33 (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d)))
35 #define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \
36 AST_SMALLER_EQ_AS((p), (a)->maxedge))
38 #define AST_CONTAINS_AREA(amine, amaxe, b) \
39 (AST_SMALLER_EQ_AS((amine), (b)->minedge) \
40 && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe)))
42 #define AST_AREAS_OVERLAP(amine, amaxe, b) \
43 (AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \
44 AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) && \
45 AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z))
48 AreaStore
*AreaStore::getOptimalImplementation()
51 return new SpatialAreaStore();
53 return new VectorAreaStore();
57 const Area
*AreaStore::getArea(u32 id
) const
59 AreaMap::const_iterator it
= areas_map
.find(id
);
60 if (it
== areas_map
.end())
65 void AreaStore::serialize(std::ostream
&os
) const
68 // Before 5.1.0-dev: version != 0 throws SerializationError
69 // After 5.1.0-dev: version >= 5 throws SerializationError
70 // Forwards-compatibility is assumed before version 5.
72 writeU8(os
, 0); // Serialisation version
75 writeU16(os
, areas_map
.size());
76 for (const auto &it
: areas_map
) {
77 const Area
&a
= it
.second
;
78 writeV3S16(os
, a
.minedge
);
79 writeV3S16(os
, a
.maxedge
);
80 writeU16(os
, a
.data
.size());
81 os
.write(a
.data
.data(), a
.data
.size());
85 for (const auto &it
: areas_map
)
86 writeU32(os
, it
.second
.id
);
89 void AreaStore::deserialize(std::istream
&is
)
92 // Assume forwards-compatibility before version 5
94 throw SerializationError("Unknown AreaStore "
95 "serialization version!");
97 u16 num_areas
= readU16(is
);
98 std::vector
<Area
> areas
;
99 for (u32 i
= 0; i
< num_areas
; ++i
) {
101 a
.minedge
= readV3S16(is
);
102 a
.maxedge
= readV3S16(is
);
103 u16 data_len
= readU16(is
);
104 char *data
= new char[data_len
];
105 is
.read(data
, data_len
);
106 a
.data
= std::string(data
, data_len
);
107 areas
.emplace_back(a
);
111 bool read_ids
= is
.good(); // EOF for old formats
113 for (auto &area
: areas
) {
115 area
.id
= readU32(is
);
120 void AreaStore::invalidateCache()
122 if (m_cache_enabled
) {
123 m_res_cache
.invalidate();
127 u32
AreaStore::getNextId() const
130 for (const auto &area
: areas_map
) {
131 if (area
.first
> free_id
)
132 return free_id
; // Found gap
134 free_id
= area
.first
+ 1;
140 void AreaStore::setCacheParams(bool enabled
, u8 block_radius
, size_t limit
)
142 m_cache_enabled
= enabled
;
143 m_cacheblock_radius
= MYMAX(block_radius
, 16);
144 m_res_cache
.setLimit(MYMAX(limit
, 20));
148 void AreaStore::cacheMiss(void *data
, const v3s16
&mpos
, std::vector
<Area
*> *dest
)
150 AreaStore
*as
= (AreaStore
*)data
;
151 u8 r
= as
->m_cacheblock_radius
;
153 // get the points at the edges of the mapblock
154 v3s16
minedge(mpos
.X
* r
, mpos
.Y
* r
, mpos
.Z
* r
);
160 as
->getAreasInArea(dest
, minedge
, maxedge
, true);
162 /* infostream << "Cache miss with " << dest->size() << " areas, between ("
163 << minedge.X << ", " << minedge.Y << ", " << minedge.Z
165 << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
166 << ")" << std::endl; // */
169 void AreaStore::getAreasForPos(std::vector
<Area
*> *result
, v3s16 pos
)
171 if (m_cache_enabled
) {
172 v3s16 mblock
= getContainerPos(pos
, m_cacheblock_radius
);
173 const std::vector
<Area
*> *pre_list
= m_res_cache
.lookupCache(mblock
);
175 size_t s_p_l
= pre_list
->size();
176 for (size_t i
= 0; i
< s_p_l
; i
++) {
177 Area
*b
= (*pre_list
)[i
];
178 if (AST_CONTAINS_PT(b
, pos
)) {
179 result
->push_back(b
);
183 return getAreasForPosImpl(result
, pos
);
193 bool VectorAreaStore::insertArea(Area
*a
)
195 if (a
->id
== U32_MAX
)
197 std::pair
<AreaMap::iterator
, bool> res
=
198 areas_map
.insert(std::make_pair(a
->id
, *a
));
202 m_areas
.push_back(&res
.first
->second
);
207 bool VectorAreaStore::removeArea(u32 id
)
209 AreaMap::iterator it
= areas_map
.find(id
);
210 if (it
== areas_map
.end())
212 Area
*a
= &it
->second
;
213 for (std::vector
<Area
*>::iterator v_it
= m_areas
.begin();
214 v_it
!= m_areas
.end(); ++v_it
) {
225 void VectorAreaStore::getAreasForPosImpl(std::vector
<Area
*> *result
, v3s16 pos
)
227 for (Area
*area
: m_areas
) {
228 if (AST_CONTAINS_PT(area
, pos
)) {
229 result
->push_back(area
);
234 void VectorAreaStore::getAreasInArea(std::vector
<Area
*> *result
,
235 v3s16 minedge
, v3s16 maxedge
, bool accept_overlap
)
237 for (Area
*area
: m_areas
) {
238 if (accept_overlap
? AST_AREAS_OVERLAP(minedge
, maxedge
, area
) :
239 AST_CONTAINS_AREA(minedge
, maxedge
, area
)) {
240 result
->push_back(area
);
247 static inline SpatialIndex::Region
get_spatial_region(const v3s16 minedge
,
250 const double p_low
[] = {(double)minedge
.X
,
251 (double)minedge
.Y
, (double)minedge
.Z
};
252 const double p_high
[] = {(double)maxedge
.X
, (double)maxedge
.Y
,
254 return SpatialIndex::Region(p_low
, p_high
, 3);
257 static inline SpatialIndex::Point
get_spatial_point(const v3s16 pos
)
259 const double p
[] = {(double)pos
.X
, (double)pos
.Y
, (double)pos
.Z
};
260 return SpatialIndex::Point(p
, 3);
264 bool SpatialAreaStore::insertArea(Area
*a
)
266 if (a
->id
== U32_MAX
)
268 if (!areas_map
.insert(std::make_pair(a
->id
, *a
)).second
)
271 m_tree
->insertData(0, nullptr, get_spatial_region(a
->minedge
, a
->maxedge
), a
->id
);
276 bool SpatialAreaStore::removeArea(u32 id
)
278 std::map
<u32
, Area
>::iterator itr
= areas_map
.find(id
);
279 if (itr
!= areas_map
.end()) {
280 Area
*a
= &itr
->second
;
281 bool result
= m_tree
->deleteData(get_spatial_region(a
->minedge
,
283 areas_map
.erase(itr
);
291 void SpatialAreaStore::getAreasForPosImpl(std::vector
<Area
*> *result
, v3s16 pos
)
293 VectorResultVisitor
visitor(result
, this);
294 m_tree
->pointLocationQuery(get_spatial_point(pos
), visitor
);
297 void SpatialAreaStore::getAreasInArea(std::vector
<Area
*> *result
,
298 v3s16 minedge
, v3s16 maxedge
, bool accept_overlap
)
300 VectorResultVisitor
visitor(result
, this);
301 if (accept_overlap
) {
302 m_tree
->intersectsWithQuery(get_spatial_region(minedge
, maxedge
),
305 m_tree
->containsWhatQuery(get_spatial_region(minedge
, maxedge
), visitor
);
309 SpatialAreaStore::~SpatialAreaStore()
314 SpatialAreaStore::SpatialAreaStore()
317 SpatialIndex::StorageManager::createNewMemoryStorageManager();
318 SpatialIndex::id_type id
;
319 m_tree
= SpatialIndex::RTree::createNewRTree(
322 100, // Index capacity
323 100, // Leaf capacity
325 SpatialIndex::RTree::RV_RSTAR
,