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