src/util/areastore.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2015 est31 <mtest31@outlook.com>
   4
   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.
   9
  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.
  14
  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.
  18 */
  19
  20 #include "util/areastore.h"
  21 #include "util/serialize.h"
  22 #include "util/container.h"
  23
  24 #if USE_SPATIAL
  25         #include <spatialindex/SpatialIndex.h>
  26         #include <spatialindex/RTree.h>
  27         #include <spatialindex/Point.h>
  28 #endif
  29
  30 #define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z))
  31
  32 #define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \
  33         (!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d)))
  34
  35 #define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \
  36         AST_SMALLER_EQ_AS((p), (a)->maxedge))
  37
  38 #define AST_CONTAINS_AREA(amine, amaxe, b)         \
  39         (AST_SMALLER_EQ_AS((amine), (b)->minedge) \
  40         && AST_SMALLER_EQ_AS((b)->maxedge, (amaxe)))
  41
  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))
  46
  47
  48 AreaStore *AreaStore::getOptimalImplementation()
  49 {
  50 #if USE_SPATIAL
  51         return new SpatialAreaStore();
  52 #else
  53         return new VectorAreaStore();
  54 #endif
  55 }
  56
  57 const Area *AreaStore::getArea(u32 id) const
  58 {
  59         AreaMap::const_iterator it = areas_map.find(id);
  60         if (it == areas_map.end())
  61                 return nullptr;
  62         return &it->second;
  63 }
  64
  65 void AreaStore::serialize(std::ostream &os) const
  66 {
  67         // WARNING:
  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.
  71
  72         writeU8(os, 0); // Serialisation version
  73
  74         // TODO: Compression?
  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());
  82         }
  83
  84         // Serialize IDs
  85         for (const auto &it : areas_map)
  86                 writeU32(os, it.second.id);
  87 }
  88
  89 void AreaStore::deserialize(std::istream &is)
  90 {
  91         u8 ver = readU8(is);
  92         // Assume forwards-compatibility before version 5
  93         if (ver >= 5)
  94                 throw SerializationError("Unknown AreaStore "
  95                                 "serialization version!");
  96
  97         u16 num_areas = readU16(is);
  98         std::vector<Area> areas;
  99         areas.reserve(num_areas);
 100         for (u32 i = 0; i < num_areas; ++i) {
 101                 Area a(U32_MAX);
 102                 a.minedge = readV3S16(is);
 103                 a.maxedge = readV3S16(is);
 104                 u16 data_len = readU16(is);
 105                 a.data = std::string(data_len, '\0');
 106                 is.read(&a.data[0], data_len);
 107                 areas.emplace_back(std::move(a));
 108         }
 109
 110         bool read_ids = is.good(); // EOF for old formats
 111
 112         for (auto &area : areas) {
 113                 if (read_ids)
 114                         area.id = readU32(is);
 115                 insertArea(&area);
 116         }
 117 }
 118
 119 void AreaStore::invalidateCache()
 120 {
 121         if (m_cache_enabled) {
 122                 m_res_cache.invalidate();
 123         }
 124 }
 125
 126 u32 AreaStore::getNextId() const
 127 {
 128         u32 free_id = 0;
 129         for (const auto &area : areas_map) {
 130                 if (area.first > free_id)
 131                         return free_id; // Found gap
 132
 133                 free_id = area.first + 1;
 134         }
 135         // End of map
 136         return free_id;
 137 }
 138
 139 void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
 140 {
 141         m_cache_enabled = enabled;
 142         m_cacheblock_radius = MYMAX(block_radius, 16);
 143         m_res_cache.setLimit(MYMAX(limit, 20));
 144         invalidateCache();
 145 }
 146
 147 void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
 148 {
 149         AreaStore *as = (AreaStore *)data;
 150         u8 r = as->m_cacheblock_radius;
 151
 152         // get the points at the edges of the mapblock
 153         v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
 154         v3s16 maxedge(
 155                 minedge.X + r - 1,
 156                 minedge.Y + r - 1,
 157                 minedge.Z + r - 1);
 158
 159         as->getAreasInArea(dest, minedge, maxedge, true);
 160
 161         /* infostream << "Cache miss with " << dest->size() << " areas, between ("
 162                         << minedge.X << ", " << minedge.Y << ", " << minedge.Z
 163                         << ") and ("
 164                         << maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
 165                         << ")" << std::endl; // */
 166 }
 167
 168 void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
 169 {
 170         if (m_cache_enabled) {
 171                 v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
 172                 const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);
 173
 174                 size_t s_p_l = pre_list->size();
 175                 for (size_t i = 0; i < s_p_l; i++) {
 176                         Area *b = (*pre_list)[i];
 177                         if (AST_CONTAINS_PT(b, pos)) {
 178                                 result->push_back(b);
 179                         }
 180                 }
 181         } else {
 182                 return getAreasForPosImpl(result, pos);
 183         }
 184 }
 185
 186
 187 ////
 188 // VectorAreaStore
 189 ////
 190
 191
 192 bool VectorAreaStore::insertArea(Area *a)
 193 {
 194         if (a->id == U32_MAX)
 195                 a->id = getNextId();
 196         std::pair<AreaMap::iterator, bool> res =
 197                         areas_map.insert(std::make_pair(a->id, *a));
 198         if (!res.second)
 199                 // ID is not unique
 200                 return false;
 201         m_areas.push_back(&res.first->second);
 202         invalidateCache();
 203         return true;
 204 }
 205
 206 bool VectorAreaStore::removeArea(u32 id)
 207 {
 208         AreaMap::iterator it = areas_map.find(id);
 209         if (it == areas_map.end())
 210                 return false;
 211         Area *a = &it->second;
 212         for (std::vector<Area *>::iterator v_it = m_areas.begin();
 213                         v_it != m_areas.end(); ++v_it) {
 214                 if (*v_it == a) {
 215                         m_areas.erase(v_it);
 216                         break;
 217                 }
 218         }
 219         areas_map.erase(it);
 220         invalidateCache();
 221         return true;
 222 }
 223
 224 void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 225 {
 226         for (Area *area : m_areas) {
 227                 if (AST_CONTAINS_PT(area, pos)) {
 228                         result->push_back(area);
 229                 }
 230         }
 231 }
 232
 233 void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
 234                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 235 {
 236         for (Area *area : m_areas) {
 237                 if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, area) :
 238                                 AST_CONTAINS_AREA(minedge, maxedge, area)) {
 239                         result->push_back(area);
 240                 }
 241         }
 242 }
 243
 244 #if USE_SPATIAL
 245
 246 static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
 247                 const v3s16 maxedge)
 248 {
 249         const double p_low[] = {(double)minedge.X,
 250                 (double)minedge.Y, (double)minedge.Z};
 251         const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
 252                 (double)maxedge.Z};
 253         return SpatialIndex::Region(p_low, p_high, 3);
 254 }
 255
 256 static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
 257 {
 258         const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
 259         return SpatialIndex::Point(p, 3);
 260 }
 261
 262
 263 bool SpatialAreaStore::insertArea(Area *a)
 264 {
 265         if (a->id == U32_MAX)
 266                 a->id = getNextId();
 267         if (!areas_map.insert(std::make_pair(a->id, *a)).second)
 268                 // ID is not unique
 269                 return false;
 270         m_tree->insertData(0, nullptr, get_spatial_region(a->minedge, a->maxedge), a->id);
 271         invalidateCache();
 272         return true;
 273 }
 274
 275 bool SpatialAreaStore::removeArea(u32 id)
 276 {
 277         std::map<u32, Area>::iterator itr = areas_map.find(id);
 278         if (itr != areas_map.end()) {
 279                 Area *a = &itr->second;
 280                 bool result = m_tree->deleteData(get_spatial_region(a->minedge,
 281                         a->maxedge), id);
 282                 areas_map.erase(itr);
 283                 invalidateCache();
 284                 return result;
 285         } else {
 286                 return false;
 287         }
 288 }
 289
 290 void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
 291 {
 292         VectorResultVisitor visitor(result, this);
 293         m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
 294 }
 295
 296 void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
 297                 v3s16 minedge, v3s16 maxedge, bool accept_overlap)
 298 {
 299         VectorResultVisitor visitor(result, this);
 300         if (accept_overlap) {
 301                 m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
 302                         visitor);
 303         } else {
 304                 m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
 305         }
 306 }
 307
 308 SpatialAreaStore::~SpatialAreaStore()
 309 {
 310         delete m_tree;
 311         delete m_storagemanager;
 312 }
 313
 314 SpatialAreaStore::SpatialAreaStore()
 315 {
 316         m_storagemanager =
 317                 SpatialIndex::StorageManager::createNewMemoryStorageManager();
 318         SpatialIndex::id_type id;
 319         m_tree = SpatialIndex::RTree::createNewRTree(
 320                 *m_storagemanager,
 321                 .7, // Fill factor
 322                 100, // Index capacity
 323                 100, // Leaf capacity
 324                 3, // dimension :)
 325                 SpatialIndex::RTree::RV_RSTAR,
 326                 id);
 327 }
 328
 329 #endif