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 INodeDefManager;
  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() {}
  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 VoxelArea(MinEdge+off, MaxEdge+off);
 179         }
 180
 181         VoxelArea operator-(const v3s16 &off) const
 182         {
 183                 return VoxelArea(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         // Translate index in the X coordinate
 281         void add_x(const v3s16 &extent, u32 &i, s16 a)
 282         {
 283                 i += a;
 284         }
 285         // Translate index in the Y coordinate
 286         void add_y(const v3s16 &extent, u32 &i, s16 a)
 287         {
 288                 i += a * extent.X;
 289         }
 290         // Translate index in the Z coordinate
 291         void add_z(const v3s16 &extent, u32 &i, s16 a)
 292         {
 293                 i += a * extent.X*extent.Y;
 294         }
 295         // Translate index in space
 296         void add_p(const v3s16 &extent, u32 &i, v3s16 a)
 297         {
 298                 i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
 299         }
 300
 301         /*
 302                 Print method for debugging
 303         */
 304         void print(std::ostream &o) const
 305         {
 306                 o << PP(MinEdge) << PP(MaxEdge) << "="
 307                         << m_cache_extent.X << "x" << m_cache_extent.Y << "x" << m_cache_extent.Z
 308                         << "=" << getVolume();
 309         }
 310
 311         // Edges are inclusive
 312         v3s16 MinEdge = v3s16(1,1,1);
 313         v3s16 MaxEdge;
 314 private:
 315         void cacheExtent()
 316         {
 317                 m_cache_extent = MaxEdge - MinEdge + v3s16(1,1,1);
 318         }
 319
 320         v3s16 m_cache_extent = v3s16(0,0,0);
 321 };
 322
 323 // unused
 324 #define VOXELFLAG_UNUSED   (1 << 0)
 325 // no data about that node
 326 #define VOXELFLAG_NO_DATA  (1 << 1)
 327 // Algorithm-dependent
 328 #define VOXELFLAG_CHECKED1 (1 << 2)
 329 // Algorithm-dependent
 330 #define VOXELFLAG_CHECKED2 (1 << 3)
 331 // Algorithm-dependent
 332 #define VOXELFLAG_CHECKED3 (1 << 4)
 333 // Algorithm-dependent
 334 #define VOXELFLAG_CHECKED4 (1 << 5)
 335
 336 enum VoxelPrintMode
 337 {
 338         VOXELPRINT_NOTHING,
 339         VOXELPRINT_MATERIAL,
 340         VOXELPRINT_WATERPRESSURE,
 341         VOXELPRINT_LIGHT_DAY,
 342 };
 343
 344 class VoxelManipulator
 345 {
 346 public:
 347         VoxelManipulator();
 348         virtual ~VoxelManipulator();
 349
 350         /*
 351                 These are a bit slow and shouldn't be used internally.
 352                 Use m_data[m_area.index(p)] instead.
 353         */
 354         MapNode getNode(const v3s16 &p)
 355         {
 356                 VoxelArea voxel_area(p);
 357                 addArea(voxel_area);
 358
 359                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA) {
 360                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 361                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 362                                         <<", index="<<m_area.index(p)
 363                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 364                                         <<" is inexistent"<<std::endl;*/
 365                         throw InvalidPositionException
 366                         ("VoxelManipulator: getNode: inexistent");
 367                 }
 368
 369                 return m_data[m_area.index(p)];
 370         }
 371         MapNode getNodeNoEx(const v3s16 &p)
 372         {
 373                 VoxelArea voxel_area(p);
 374                 addArea(voxel_area);
 375
 376                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA) {
 377                         return MapNode(CONTENT_IGNORE);
 378                 }
 379
 380                 return m_data[m_area.index(p)];
 381         }
 382         MapNode getNodeNoExNoEmerge(const v3s16 &p)
 383         {
 384                 if (!m_area.contains(p))
 385                         return MapNode(CONTENT_IGNORE);
 386                 if (m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
 387                         return MapNode(CONTENT_IGNORE);
 388                 return m_data[m_area.index(p)];
 389         }
 390         // Stuff explodes if non-emerged area is touched with this.
 391         // Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
 392         MapNode & getNodeRefUnsafe(const v3s16 &p)
 393         {
 394                 return m_data[m_area.index(p)];
 395         }
 396
 397         const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
 398         {
 399                 s32 index = m_area.index(p);
 400
 401                 if (m_flags[index] & VOXELFLAG_NO_DATA)
 402                         return ContentIgnoreNode;
 403
 404                 return m_data[index];
 405         }
 406
 407         u8 & getFlagsRefUnsafe(const v3s16 &p)
 408         {
 409                 return m_flags[m_area.index(p)];
 410         }
 411
 412         bool exists(const v3s16 &p)
 413         {
 414                 return m_area.contains(p) &&
 415                         !(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
 416         }
 417
 418         void setNode(const v3s16 &p, const MapNode &n)
 419         {
 420                 VoxelArea voxel_area(p);
 421                 addArea(voxel_area);
 422
 423                 m_data[m_area.index(p)] = n;
 424                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
 425         }
 426         // TODO: Should be removed and replaced with setNode
 427         void setNodeNoRef(const v3s16 &p, const MapNode &n)
 428         {
 429                 setNode(p, n);
 430         }
 431
 432         /*
 433                 Set stuff if available without an emerge.
 434                 Return false if failed.
 435                 This is convenient but slower than playing around directly
 436                 with the m_data table with indices.
 437         */
 438         bool setNodeNoEmerge(const v3s16 &p, MapNode n)
 439         {
 440                 if(!m_area.contains(p))
 441                         return false;
 442                 m_data[m_area.index(p)] = n;
 443                 return true;
 444         }
 445
 446         /*
 447                 Control
 448         */
 449
 450         virtual void clear();
 451
 452         void print(std::ostream &o, INodeDefManager *nodemgr,
 453                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 454
 455         void addArea(const VoxelArea &area);
 456
 457         /*
 458                 Copy data and set flags to 0
 459                 dst_area.getExtent() <= src_area.getExtent()
 460         */
 461         void copyFrom(MapNode *src, const VoxelArea& src_area,
 462                         v3s16 from_pos, v3s16 to_pos, const v3s16 &size);
 463
 464         // Copy data
 465         void copyTo(MapNode *dst, const VoxelArea& dst_area,
 466                         v3s16 dst_pos, v3s16 from_pos, const v3s16 &size);
 467
 468         /*
 469                 Algorithms
 470         */
 471
 472         void clearFlag(u8 flag);
 473
 474         // TODO: Move to voxelalgorithms.h
 475
 476         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 477                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 478
 479         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 480         void spreadLight(enum LightBank bank,
 481                         std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
 482
 483         /*
 484                 Member variables
 485         */
 486
 487         /*
 488                 The area that is stored in m_data.
 489                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 490                 MaxEdge is 1 higher than maximum allowed position
 491         */
 492         VoxelArea m_area;
 493
 494         /*
 495                 nullptr if data size is 0 (extent (0,0,0))
 496                 Data is stored as [z*h*w + y*h + x]
 497         */
 498         MapNode *m_data = nullptr;
 499
 500         /*
 501                 Flags of all nodes
 502         */
 503         u8 *m_flags = nullptr;
 504
 505         static const MapNode ContentIgnoreNode;
 506 };