src/voxel.h

   1 /*
   2 Minetest
   3 Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.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 #pragma once
  21
  22 #include "irrlichttypes.h"
  23 #include "irr_v3d.h"
  24 #include <iostream>
  25 #include <cassert>
  26 #include "exceptions.h"
  27 #include "mapnode.h"
  28 #include <set>
  29 #include <list>
  30 #include "util/basic_macros.h"
  31
  32 class NodeDefManager;
  33
  34 // For VC++
  35 #undef min
  36 #undef max
  37
  38 /*
  39         A fast voxel manipulator class.
  40
  41         In normal operation, it fetches more map when it is requested.
  42         It can also be used so that all allowed area is fetched at the
  43         start, using ManualMapVoxelManipulator.
  44
  45         Not thread-safe.
  46 */
  47
  48 /*
  49         Debug stuff
  50 */
  51 extern u64 emerge_time;
  52 extern u64 emerge_load_time;
  53
  54 /*
  55         This class resembles aabbox3d<s16> a lot, but has inclusive
  56         edges for saner handling of integer sizes
  57 */
  58 class VoxelArea
  59 {
  60 public:
  61         // Starts as zero sized
  62         VoxelArea() = default;
  63
  64         VoxelArea(const v3s16 &min_edge, const v3s16 &max_edge):
  65                 MinEdge(min_edge),
  66                 MaxEdge(max_edge)
  67         {
  68                 cacheExtent();
  69         }
  70
  71         VoxelArea(const v3s16 &p):
  72                 MinEdge(p),
  73                 MaxEdge(p)
  74         {
  75                 cacheExtent();
  76         }
  77
  78         /*
  79                 Modifying methods
  80         */
  81
  82         void addArea(const VoxelArea &a)
  83         {
  84                 if (hasEmptyExtent())
  85                 {
  86                         *this = a;
  87                         return;
  88                 }
  89                 if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
  90                 if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
  91                 if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
  92                 if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
  93                 if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
  94                 if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
  95                 cacheExtent();
  96         }
  97
  98         void addPoint(const v3s16 &p)
  99         {
 100                 if(hasEmptyExtent())
 101                 {
 102                         MinEdge = p;
 103                         MaxEdge = p;
 104                         cacheExtent();
 105                         return;
 106                 }
 107                 if(p.X < MinEdge.X) MinEdge.X = p.X;
 108                 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
 109                 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
 110                 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
 111                 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
 112                 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
 113                 cacheExtent();
 114         }
 115
 116         // Pad with d nodes
 117         void pad(const v3s16 &d)
 118         {
 119                 MinEdge -= d;
 120                 MaxEdge += d;
 121         }
 122
 123         /*
 124                 const methods
 125         */
 126
 127         const v3s16 &getExtent() const
 128         {
 129                 return m_cache_extent;
 130         }
 131
 132         /* Because MaxEdge and MinEdge are included in the voxel area an empty extent
 133          * is not represented by (0, 0, 0), but instead (-1, -1, -1)
 134          */
 135         bool hasEmptyExtent() const
 136         {
 137                 return MaxEdge - MinEdge == v3s16(-1, -1, -1);
 138         }
 139
 140         s32 getVolume() const
 141         {
 142                 return (s32)m_cache_extent.X * (s32)m_cache_extent.Y * (s32)m_cache_extent.Z;
 143         }
 144
 145         bool contains(const VoxelArea &a) const
 146         {
 147                 // No area contains an empty area
 148                 // NOTE: Algorithms depend on this, so do not change.
 149                 if(a.hasEmptyExtent())
 150                         return false;
 151
 152                 return(
 153                         a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
 154                         a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
 155                         a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
 156                 );
 157         }
 158         bool contains(v3s16 p) const
 159         {
 160                 return(
 161                         p.X >= MinEdge.X && p.X <= MaxEdge.X &&
 162                         p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
 163                         p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
 164                 );
 165         }
 166         bool contains(s32 i) const
 167         {
 168                 return (i >= 0 && i < getVolume());
 169         }
 170         bool operator==(const VoxelArea &other) const
 171         {
 172                 return (MinEdge == other.MinEdge
 173                                 && MaxEdge == other.MaxEdge);
 174         }
 175
 176         VoxelArea operator+(const v3s16 &off) const
 177         {
 178                 return {MinEdge+off, MaxEdge+off};
 179         }
 180
 181         VoxelArea operator-(const v3s16 &off) const
 182         {
 183                 return {MinEdge-off, MaxEdge-off};
 184         }
 185
 186         /*
 187                 Returns 0-6 non-overlapping areas that can be added to
 188                 a to make up this area.
 189
 190                 a: area inside *this
 191         */
 192         void diff(const VoxelArea &a, std::list<VoxelArea> &result)
 193         {
 194                 /*
 195                         This can result in a maximum of 6 areas
 196                 */
 197
 198                 // If a is an empty area, return the current area as a whole
 199                 if(a.getExtent() == v3s16(0,0,0))
 200                 {
 201                         VoxelArea b = *this;
 202                         if(b.getVolume() != 0)
 203                                 result.push_back(b);
 204                         return;
 205                 }
 206
 207                 assert(contains(a));    // pre-condition
 208
 209                 // Take back area, XY inclusive
 210                 {
 211                         v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
 212                         v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
 213                         VoxelArea b(min, max);
 214                         if(b.getVolume() != 0)
 215                                 result.push_back(b);
 216                 }
 217
 218                 // Take front area, XY inclusive
 219                 {
 220                         v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
 221                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
 222                         VoxelArea b(min, max);
 223                         if(b.getVolume() != 0)
 224                                 result.push_back(b);
 225                 }
 226
 227                 // Take top area, X inclusive
 228                 {
 229                         v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
 230                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
 231                         VoxelArea b(min, max);
 232                         if(b.getVolume() != 0)
 233                                 result.push_back(b);
 234                 }
 235
 236                 // Take bottom area, X inclusive
 237                 {
 238                         v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
 239                         v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
 240                         VoxelArea b(min, max);
 241                         if(b.getVolume() != 0)
 242                                 result.push_back(b);
 243                 }
 244
 245                 // Take left area, non-inclusive
 246                 {
 247                         v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
 248                         v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
 249                         VoxelArea b(min, max);
 250                         if(b.getVolume() != 0)
 251                                 result.push_back(b);
 252                 }
 253
 254                 // Take right area, non-inclusive
 255                 {
 256                         v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
 257                         v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
 258                         VoxelArea b(min, max);
 259                         if(b.getVolume() != 0)
 260                                 result.push_back(b);
 261                 }
 262
 263         }
 264
 265         /*
 266                 Translates position from virtual coordinates to array index
 267         */
 268         s32 index(s16 x, s16 y, s16 z) const
 269         {
 270                 s32 i = (s32)(z - MinEdge.Z) * m_cache_extent.Y * m_cache_extent.X
 271                         + (y - MinEdge.Y) * m_cache_extent.X
 272                         + (x - MinEdge.X);
 273                 return i;
 274         }
 275         s32 index(v3s16 p) const
 276         {
 277                 return index(p.X, p.Y, p.Z);
 278         }
 279
 280         /**
 281          * Translate index in the X coordinate
 282          */
 283         static void add_x(const v3s16 &extent, u32 &i, s16 a)
 284         {
 285                 i += a;
 286         }
 287
 288         /**
 289          * Translate index in the Y coordinate
 290          */
 291         static void add_y(const v3s16 &extent, u32 &i, s16 a)
 292         {
 293                 i += a * extent.X;
 294         }
 295
 296         /**
 297          * Translate index in the Z coordinate
 298          */
 299         static void add_z(const v3s16 &extent, u32 &i, s16 a)
 300         {
 301                 i += a * extent.X * extent.Y;
 302         }
 303
 304         /**
 305          * Translate index in space
 306          */
 307         static void add_p(const v3s16 &extent, u32 &i, v3s16 a)
 308         {
 309                 i += a.Z * extent.X * extent.Y + a.Y * extent.X + a.X;
 310         }
 311
 312         /*
 313                 Print method for debugging
 314         */
 315         void print(std::ostream &o) const
 316         {
 317                 o << PP(MinEdge) << PP(MaxEdge) << "="
 318                         << m_cache_extent.X << "x" << m_cache_extent.Y << "x" << m_cache_extent.Z
 319                         << "=" << getVolume();
 320         }
 321
 322         // Edges are inclusive
 323         v3s16 MinEdge = v3s16(1,1,1);
 324         v3s16 MaxEdge;
 325 private:
 326         void cacheExtent()
 327         {
 328                 m_cache_extent = MaxEdge - MinEdge + v3s16(1,1,1);
 329         }
 330
 331         v3s16 m_cache_extent = v3s16(0,0,0);
 332 };
 333
 334 // unused
 335 #define VOXELFLAG_UNUSED   (1 << 0)
 336 // no data about that node
 337 #define VOXELFLAG_NO_DATA  (1 << 1)
 338 // Algorithm-dependent
 339 #define VOXELFLAG_CHECKED1 (1 << 2)
 340 // Algorithm-dependent
 341 #define VOXELFLAG_CHECKED2 (1 << 3)
 342 // Algorithm-dependent
 343 #define VOXELFLAG_CHECKED3 (1 << 4)
 344 // Algorithm-dependent
 345 #define VOXELFLAG_CHECKED4 (1 << 5)
 346
 347 enum VoxelPrintMode
 348 {
 349         VOXELPRINT_NOTHING,
 350         VOXELPRINT_MATERIAL,
 351         VOXELPRINT_WATERPRESSURE,
 352         VOXELPRINT_LIGHT_DAY,
 353 };
 354
 355 class VoxelManipulator
 356 {
 357 public:
 358         VoxelManipulator() = default;
 359         virtual ~VoxelManipulator();
 360
 361         /*
 362                 These are a bit slow and shouldn't be used internally.
 363                 Use m_data[m_area.index(p)] instead.
 364         */
 365         MapNode getNode(const v3s16 &p)
 366         {
 367                 VoxelArea voxel_area(p);
 368                 addArea(voxel_area);
 369
 370                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA) {
 371                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 372                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 373                                         <<", index="<<m_area.index(p)
 374                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 375                                         <<" is inexistent"<<std::endl;*/
 376                         throw InvalidPositionException
 377                         ("VoxelManipulator: getNode: inexistent");
 378                 }
 379
 380                 return m_data[m_area.index(p)];
 381         }
 382         MapNode getNodeNoEx(const v3s16 &p)
 383         {
 384                 VoxelArea voxel_area(p);
 385                 addArea(voxel_area);
 386
 387                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA) {
 388                         return {CONTENT_IGNORE};
 389                 }
 390
 391                 return m_data[m_area.index(p)];
 392         }
 393         MapNode getNodeNoExNoEmerge(const v3s16 &p)
 394         {
 395                 if (!m_area.contains(p))
 396                         return {CONTENT_IGNORE};
 397                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
 398                         return {CONTENT_IGNORE};
 399                 return m_data[m_area.index(p)];
 400         }
 401         // Stuff explodes if non-emerged area is touched with this.
 402         // Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
 403         MapNode & getNodeRefUnsafe(const v3s16 &p)
 404         {
 405                 return m_data[m_area.index(p)];
 406         }
 407
 408         const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
 409         {
 410                 s32 index = m_area.index(p);
 411
 412                 if (m_flags[index] & VOXELFLAG_NO_DATA)
 413                         return ContentIgnoreNode;
 414
 415                 return m_data[index];
 416         }
 417
 418         u8 & getFlagsRefUnsafe(const v3s16 &p)
 419         {
 420                 return m_flags[m_area.index(p)];
 421         }
 422
 423         bool exists(const v3s16 &p)
 424         {
 425                 return m_area.contains(p) &&
 426                         !(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
 427         }
 428
 429         void setNode(const v3s16 &p, const MapNode &n)
 430         {
 431                 VoxelArea voxel_area(p);
 432                 addArea(voxel_area);
 433
 434                 m_data[m_area.index(p)] = n;
 435                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
 436         }
 437         // TODO: Should be removed and replaced with setNode
 438         void setNodeNoRef(const v3s16 &p, const MapNode &n)
 439         {
 440                 setNode(p, n);
 441         }
 442
 443         /*
 444                 Set stuff if available without an emerge.
 445                 Return false if failed.
 446                 This is convenient but slower than playing around directly
 447                 with the m_data table with indices.
 448         */
 449         bool setNodeNoEmerge(const v3s16 &p, MapNode n)
 450         {
 451                 if(!m_area.contains(p))
 452                         return false;
 453                 m_data[m_area.index(p)] = n;
 454                 return true;
 455         }
 456
 457         /*
 458                 Control
 459         */
 460
 461         virtual void clear();
 462
 463         void print(std::ostream &o, const NodeDefManager *nodemgr,
 464                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 465
 466         void addArea(const VoxelArea &area);
 467
 468         /*
 469                 Copy data and set flags to 0
 470                 dst_area.getExtent() <= src_area.getExtent()
 471         */
 472         void copyFrom(MapNode *src, const VoxelArea& src_area,
 473                         v3s16 from_pos, v3s16 to_pos, const v3s16 &size);
 474
 475         // Copy data
 476         void copyTo(MapNode *dst, const VoxelArea& dst_area,
 477                         v3s16 dst_pos, v3s16 from_pos, const v3s16 &size);
 478
 479         /*
 480                 Algorithms
 481         */
 482
 483         void clearFlag(u8 flag);
 484
 485         /*
 486                 Member variables
 487         */
 488
 489         /*
 490                 The area that is stored in m_data.
 491                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 492                 MaxEdge is 1 higher than maximum allowed position
 493         */
 494         VoxelArea m_area;
 495
 496         /*
 497                 nullptr if data size is 0 (extent (0,0,0))
 498                 Data is stored as [z*h*w + y*h + x]
 499         */
 500         MapNode *m_data = nullptr;
 501
 502         /*
 503                 Flags of all nodes
 504         */
 505         u8 *m_flags = nullptr;
 506
 507         static const MapNode ContentIgnoreNode;
 508 };