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 <map>
  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(v3s16 min_edge, v3s16 max_edge):
  66                 MinEdge(min_edge),
  67                 MaxEdge(max_edge)
  68         {
  69         }
  70         VoxelArea(v3s16 p):
  71                 MinEdge(p),
  72                 MaxEdge(p)
  73         {
  74         }
  75
  76         /*
  77                 Modifying methods
  78         */
  79
  80         void addArea(const VoxelArea &a)
  81         {
  82                 if (hasEmptyExtent())
  83                 {
  84                         *this = a;
  85                         return;
  86                 }
  87                 if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
  88                 if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
  89                 if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
  90                 if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
  91                 if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
  92                 if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
  93         }
  94         void addPoint(const v3s16 &p)
  95         {
  96                 if(hasEmptyExtent())
  97                 {
  98                         MinEdge = p;
  99                         MaxEdge = p;
 100                         return;
 101                 }
 102                 if(p.X < MinEdge.X) MinEdge.X = p.X;
 103                 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
 104                 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
 105                 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
 106                 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
 107                 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
 108         }
 109
 110         // Pad with d nodes
 111         void pad(const v3s16 &d)
 112         {
 113                 MinEdge -= d;
 114                 MaxEdge += d;
 115         }
 116
 117         /*void operator+=(v3s16 off)
 118         {
 119                 MinEdge += off;
 120                 MaxEdge += off;
 121         }
 122
 123         void operator-=(v3s16 off)
 124         {
 125                 MinEdge -= off;
 126                 MaxEdge -= off;
 127         }*/
 128
 129         /*
 130                 const methods
 131         */
 132
 133         v3s16 getExtent() const
 134         {
 135                 return MaxEdge - MinEdge + v3s16(1,1,1);
 136         }
 137
 138         /* Because MaxEdge and MinEdge are included in the voxel area an empty extent
 139          * is not represented by (0, 0, 0), but instead (-1, -1, -1)
 140          */
 141         bool hasEmptyExtent() const
 142         {
 143                 return MaxEdge - MinEdge == v3s16(-1, -1, -1);
 144         }
 145
 146         s32 getVolume() const
 147         {
 148                 v3s16 e = getExtent();
 149                 return (s32)e.X * (s32)e.Y * (s32)e.Z;
 150         }
 151         bool contains(const VoxelArea &a) const
 152         {
 153                 // No area contains an empty area
 154                 // NOTE: Algorithms depend on this, so do not change.
 155                 if(a.hasEmptyExtent())
 156                         return false;
 157
 158                 return(
 159                         a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
 160                         a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
 161                         a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
 162                 );
 163         }
 164         bool contains(v3s16 p) const
 165         {
 166                 return(
 167                         p.X >= MinEdge.X && p.X <= MaxEdge.X &&
 168                         p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
 169                         p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
 170                 );
 171         }
 172         bool contains(s32 i) const
 173         {
 174                 return (i >= 0 && i < getVolume());
 175         }
 176         bool operator==(const VoxelArea &other) const
 177         {
 178                 return (MinEdge == other.MinEdge
 179                                 && MaxEdge == other.MaxEdge);
 180         }
 181
 182         VoxelArea operator+(v3s16 off) const
 183         {
 184                 return VoxelArea(MinEdge+off, MaxEdge+off);
 185         }
 186
 187         VoxelArea operator-(v3s16 off) const
 188         {
 189                 return VoxelArea(MinEdge-off, MaxEdge-off);
 190         }
 191
 192         /*
 193                 Returns 0-6 non-overlapping areas that can be added to
 194                 a to make up this area.
 195
 196                 a: area inside *this
 197         */
 198         void diff(const VoxelArea &a, std::list<VoxelArea> &result)
 199         {
 200                 /*
 201                         This can result in a maximum of 6 areas
 202                 */
 203
 204                 // If a is an empty area, return the current area as a whole
 205                 if(a.getExtent() == v3s16(0,0,0))
 206                 {
 207                         VoxelArea b = *this;
 208                         if(b.getVolume() != 0)
 209                                 result.push_back(b);
 210                         return;
 211                 }
 212
 213                 assert(contains(a));    // pre-condition
 214
 215                 // Take back area, XY inclusive
 216                 {
 217                         v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
 218                         v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
 219                         VoxelArea b(min, max);
 220                         if(b.getVolume() != 0)
 221                                 result.push_back(b);
 222                 }
 223
 224                 // Take front area, XY inclusive
 225                 {
 226                         v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
 227                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
 228                         VoxelArea b(min, max);
 229                         if(b.getVolume() != 0)
 230                                 result.push_back(b);
 231                 }
 232
 233                 // Take top area, X inclusive
 234                 {
 235                         v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
 236                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
 237                         VoxelArea b(min, max);
 238                         if(b.getVolume() != 0)
 239                                 result.push_back(b);
 240                 }
 241
 242                 // Take bottom area, X inclusive
 243                 {
 244                         v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
 245                         v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
 246                         VoxelArea b(min, max);
 247                         if(b.getVolume() != 0)
 248                                 result.push_back(b);
 249                 }
 250
 251                 // Take left area, non-inclusive
 252                 {
 253                         v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
 254                         v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
 255                         VoxelArea b(min, max);
 256                         if(b.getVolume() != 0)
 257                                 result.push_back(b);
 258                 }
 259
 260                 // Take right area, non-inclusive
 261                 {
 262                         v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
 263                         v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
 264                         VoxelArea b(min, max);
 265                         if(b.getVolume() != 0)
 266                                 result.push_back(b);
 267                 }
 268
 269         }
 270
 271         /*
 272                 Translates position from virtual coordinates to array index
 273         */
 274         s32 index(s16 x, s16 y, s16 z) const
 275         {
 276                 v3s16 em = getExtent();
 277                 v3s16 off = MinEdge;
 278                 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
 279                 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
 280                 return i;
 281         }
 282         s32 index(v3s16 p) const
 283         {
 284                 return index(p.X, p.Y, p.Z);
 285         }
 286
 287         // Translate index in the X coordinate
 288         void add_x(const v3s16 &extent, u32 &i, s16 a)
 289         {
 290                 i += a;
 291         }
 292         // Translate index in the Y coordinate
 293         void add_y(const v3s16 &extent, u32 &i, s16 a)
 294         {
 295                 i += a * extent.X;
 296         }
 297         // Translate index in the Z coordinate
 298         void add_z(const v3s16 &extent, u32 &i, s16 a)
 299         {
 300                 i += a * extent.X*extent.Y;
 301         }
 302         // Translate index in space
 303         void add_p(const v3s16 &extent, u32 &i, v3s16 a)
 304         {
 305                 i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
 306         }
 307
 308         /*
 309                 Print method for debugging
 310         */
 311         void print(std::ostream &o) const
 312         {
 313                 v3s16 e = getExtent();
 314                 o<<"("<<MinEdge.X
 315                  <<","<<MinEdge.Y
 316                  <<","<<MinEdge.Z
 317                  <<")("<<MaxEdge.X
 318                  <<","<<MaxEdge.Y
 319                  <<","<<MaxEdge.Z
 320                  <<")"
 321                  <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
 322         }
 323
 324         // Edges are inclusive
 325         v3s16 MinEdge = v3s16(1,1,1);
 326         v3s16 MaxEdge;
 327 };
 328
 329 // unused
 330 #define VOXELFLAG_UNUSED   (1 << 0)
 331 // no data about that node
 332 #define VOXELFLAG_NO_DATA  (1 << 1)
 333 // Algorithm-dependent
 334 #define VOXELFLAG_CHECKED1 (1 << 2)
 335 // Algorithm-dependent
 336 #define VOXELFLAG_CHECKED2 (1 << 3)
 337 // Algorithm-dependent
 338 #define VOXELFLAG_CHECKED3 (1 << 4)
 339 // Algorithm-dependent
 340 #define VOXELFLAG_CHECKED4 (1 << 5)
 341
 342 enum VoxelPrintMode
 343 {
 344         VOXELPRINT_NOTHING,
 345         VOXELPRINT_MATERIAL,
 346         VOXELPRINT_WATERPRESSURE,
 347         VOXELPRINT_LIGHT_DAY,
 348 };
 349
 350 class VoxelManipulator /*: public NodeContainer*/
 351 {
 352 public:
 353         VoxelManipulator();
 354         virtual ~VoxelManipulator();
 355
 356         /*
 357                 Virtuals from NodeContainer
 358         */
 359         /*virtual u16 nodeContainerId() const
 360         {
 361                 return NODECONTAINER_ID_VOXELMANIPULATOR;
 362         }
 363         bool isValidPosition(v3s16 p)
 364         {
 365                 addArea(p);
 366                 return !(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA);
 367         }*/
 368
 369         /*
 370                 These are a bit slow and shouldn't be used internally.
 371                 Use m_data[m_area.index(p)] instead.
 372         */
 373         MapNode getNode(v3s16 p)
 374         {
 375                 VoxelArea voxel_area(p);
 376                 addArea(voxel_area);
 377
 378                 if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
 379                 {
 380                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 381                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 382                                         <<", index="<<m_area.index(p)
 383                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 384                                         <<" is inexistent"<<std::endl;*/
 385                         throw InvalidPositionException
 386                         ("VoxelManipulator: getNode: inexistent");
 387                 }
 388
 389                 return m_data[m_area.index(p)];
 390         }
 391         MapNode getNodeNoEx(v3s16 p)
 392         {
 393                 VoxelArea voxel_area(p);
 394                 addArea(voxel_area);
 395
 396                 if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
 397                 {
 398                         return MapNode(CONTENT_IGNORE);
 399                 }
 400
 401                 return m_data[m_area.index(p)];
 402         }
 403         MapNode getNodeNoExNoEmerge(v3s16 p)
 404         {
 405                 if(m_area.contains(p) == false)
 406                         return MapNode(CONTENT_IGNORE);
 407                 if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
 408                         return MapNode(CONTENT_IGNORE);
 409                 return m_data[m_area.index(p)];
 410         }
 411         // Stuff explodes if non-emerged area is touched with this.
 412         // Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
 413         MapNode & getNodeRefUnsafe(const v3s16 &p)
 414         {
 415                 return m_data[m_area.index(p)];
 416         }
 417
 418         const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
 419         {
 420                 s32 index = m_area.index(p);
 421
 422                 if (m_flags[index] & VOXELFLAG_NO_DATA)
 423                         return ContentIgnoreNode;
 424
 425                 return m_data[index];
 426         }
 427
 428         u8 & getFlagsRefUnsafe(v3s16 p)
 429         {
 430                 return m_flags[m_area.index(p)];
 431         }
 432         bool exists(v3s16 p)
 433         {
 434                 return m_area.contains(p) &&
 435                         !(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
 436         }
 437         MapNode & getNodeRef(v3s16 p)
 438         {
 439                 VoxelArea voxel_area(p);
 440                 addArea(voxel_area);
 441                 if(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA)
 442                 {
 443                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 444                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 445                                         <<", index="<<m_area.index(p)
 446                                         <<", flags="<<(int)getFlagsRefUnsafe(p)
 447                                         <<" is inexistent"<<std::endl;*/
 448                         throw InvalidPositionException
 449                         ("VoxelManipulator: getNode: inexistent");
 450                 }
 451                 return getNodeRefUnsafe(p);
 452         }
 453         void setNode(v3s16 p, const MapNode &n)
 454         {
 455                 VoxelArea voxel_area(p);
 456                 addArea(voxel_area);
 457
 458                 m_data[m_area.index(p)] = n;
 459                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
 460         }
 461         // TODO: Should be removed and replaced with setNode
 462         void setNodeNoRef(v3s16 p, const MapNode &n)
 463         {
 464                 setNode(p, n);
 465         }
 466
 467         /*void setExists(VoxelArea a)
 468         {
 469                 addArea(a);
 470                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 471                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 472                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 473                 {
 474                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_NO_DATA;
 475                 }
 476         }*/
 477
 478         /*MapNode & operator[](v3s16 p)
 479         {
 480                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 481                 if(isValidPosition(p) == false)
 482                         addArea(VoxelArea(p));
 483
 484                 return m_data[m_area.index(p)];
 485         }*/
 486
 487         /*
 488                 Set stuff if available without an emerge.
 489                 Return false if failed.
 490                 This is convenient but slower than playing around directly
 491                 with the m_data table with indices.
 492         */
 493         bool setNodeNoEmerge(v3s16 p, MapNode n)
 494         {
 495                 if(m_area.contains(p) == false)
 496                         return false;
 497                 m_data[m_area.index(p)] = n;
 498                 return true;
 499         }
 500         bool setNodeNoEmerge(s32 i, MapNode n)
 501         {
 502                 if(m_area.contains(i) == false)
 503                         return false;
 504                 m_data[i] = n;
 505                 return true;
 506         }
 507         /*bool setContentNoEmerge(v3s16 p, u8 c)
 508         {
 509                 if(isValidPosition(p) == false)
 510                         return false;
 511                 m_data[m_area.index(p)].d = c;
 512         }*/
 513
 514         /*
 515                 Control
 516         */
 517
 518         virtual void clear();
 519
 520         void print(std::ostream &o, INodeDefManager *nodemgr,
 521                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 522
 523         void addArea(const VoxelArea &area);
 524
 525         /*
 526                 Copy data and set flags to 0
 527                 dst_area.getExtent() <= src_area.getExtent()
 528         */
 529         void copyFrom(MapNode *src, const VoxelArea& src_area,
 530                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 531
 532         // Copy data
 533         void copyTo(MapNode *dst, const VoxelArea& dst_area,
 534                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 535
 536         /*
 537                 Algorithms
 538         */
 539
 540         void clearFlag(u8 flag);
 541
 542         // TODO: Move to voxelalgorithms.h
 543
 544         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 545                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 546         void unspreadLight(enum LightBank bank,
 547                         std::map<v3s16, u8> & from_nodes,
 548                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 549
 550         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 551         void spreadLight(enum LightBank bank,
 552                         std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
 553
 554         /*
 555                 Virtual functions
 556         */
 557
 558         /*
 559                 Member variables
 560         */
 561
 562         /*
 563                 The area that is stored in m_data.
 564                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 565                 MaxEdge is 1 higher than maximum allowed position
 566         */
 567         VoxelArea m_area;
 568
 569         /*
 570                 nullptr if data size is 0 (extent (0,0,0))
 571                 Data is stored as [z*h*w + y*h + x]
 572         */
 573         MapNode *m_data = nullptr;
 574
 575         /*
 576                 Flags of all nodes
 577         */
 578         u8 *m_flags = nullptr;
 579
 580         static const MapNode ContentIgnoreNode;
 581 };
 582
 583 #endif
 584