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 u32 emerge_time;
  53 extern u32 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                 MinEdge(1,1,1),
  65                 MaxEdge(0,0,0)
  66         {
  67         }
  68         VoxelArea(v3s16 min_edge, v3s16 max_edge):
  69                 MinEdge(min_edge),
  70                 MaxEdge(max_edge)
  71         {
  72         }
  73         VoxelArea(v3s16 p):
  74                 MinEdge(p),
  75                 MaxEdge(p)
  76         {
  77         }
  78
  79         /*
  80                 Modifying methods
  81         */
  82
  83         void addArea(VoxelArea &a)
  84         {
  85                 if(getExtent() == v3s16(0,0,0))
  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         }
  97         void addPoint(v3s16 p)
  98         {
  99                 if(getExtent() == v3s16(0,0,0))
 100                 {
 101                         MinEdge = p;
 102                         MaxEdge = p;
 103                         return;
 104                 }
 105                 if(p.X < MinEdge.X) MinEdge.X = p.X;
 106                 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
 107                 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
 108                 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
 109                 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
 110                 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
 111         }
 112
 113         // Pad with d nodes
 114         void pad(v3s16 d)
 115         {
 116                 MinEdge -= d;
 117                 MaxEdge += d;
 118         }
 119
 120         /*void operator+=(v3s16 off)
 121         {
 122                 MinEdge += off;
 123                 MaxEdge += off;
 124         }
 125
 126         void operator-=(v3s16 off)
 127         {
 128                 MinEdge -= off;
 129                 MaxEdge -= off;
 130         }*/
 131
 132         /*
 133                 const methods
 134         */
 135
 136         v3s16 getExtent() const
 137         {
 138                 return MaxEdge - MinEdge + v3s16(1,1,1);
 139         }
 140         s32 getVolume() const
 141         {
 142                 v3s16 e = getExtent();
 143                 return (s32)e.X * (s32)e.Y * (s32)e.Z;
 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.getExtent() == v3s16(0,0,0))
 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+(v3s16 off) const
 177         {
 178                 return VoxelArea(MinEdge+off, MaxEdge+off);
 179         }
 180
 181         VoxelArea operator-(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));
 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                 v3s16 em = getExtent();
 271                 v3s16 off = MinEdge;
 272                 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
 273                 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
 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                 v3s16 e = getExtent();
 308                 o<<"("<<MinEdge.X
 309                  <<","<<MinEdge.Y
 310                  <<","<<MinEdge.Z
 311                  <<")("<<MaxEdge.X
 312                  <<","<<MaxEdge.Y
 313                  <<","<<MaxEdge.Z
 314                  <<")"
 315                  <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
 316         }
 317
 318         // Edges are inclusive
 319         v3s16 MinEdge;
 320         v3s16 MaxEdge;
 321 };
 322
 323 // Hasn't been copied from source (emerged)
 324 #define VOXELFLAG_NOT_LOADED (1<<0)
 325 // Checked as being inexistent in source
 326 #define VOXELFLAG_INEXISTENT (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 /*: public NodeContainer*/
 345 {
 346 public:
 347         VoxelManipulator();
 348         virtual ~VoxelManipulator();
 349
 350         /*
 351                 Virtuals from NodeContainer
 352         */
 353         /*virtual u16 nodeContainerId() const
 354         {
 355                 return NODECONTAINER_ID_VOXELMANIPULATOR;
 356         }
 357         bool isValidPosition(v3s16 p)
 358         {
 359                 emerge(p);
 360                 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
 361         }*/
 362
 363         /*
 364                 These are a bit slow and shouldn't be used internally.
 365                 Use m_data[m_area.index(p)] instead.
 366         */
 367         MapNode getNode(v3s16 p)
 368         {
 369                 emerge(p);
 370
 371                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 372                 {
 373                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 374                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 375                                         <<", index="<<m_area.index(p)
 376                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 377                                         <<" is inexistent"<<std::endl;*/
 378                         throw InvalidPositionException
 379                         ("VoxelManipulator: getNode: inexistent");
 380                 }
 381
 382                 return m_data[m_area.index(p)];
 383         }
 384         MapNode getNodeNoEx(v3s16 p)
 385         {
 386                 emerge(p);
 387
 388                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 389                 {
 390                         return MapNode(CONTENT_IGNORE);
 391                 }
 392
 393                 return m_data[m_area.index(p)];
 394         }
 395         MapNode getNodeNoExNoEmerge(v3s16 p)
 396         {
 397                 if(m_area.contains(p) == false)
 398                         return MapNode(CONTENT_IGNORE);
 399                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 400                         return MapNode(CONTENT_IGNORE);
 401                 return m_data[m_area.index(p)];
 402         }
 403         // Stuff explodes if non-emerged area is touched with this.
 404         // Emerge first, and check VOXELFLAG_INEXISTENT if appropriate.
 405         MapNode & getNodeRefUnsafe(v3s16 p)
 406         {
 407                 return m_data[m_area.index(p)];
 408         }
 409         u8 & getFlagsRefUnsafe(v3s16 p)
 410         {
 411                 return m_flags[m_area.index(p)];
 412         }
 413         bool exists(v3s16 p)
 414         {
 415                 return m_area.contains(p) &&
 416                         !(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT);
 417         }
 418         MapNode & getNodeRef(v3s16 p)
 419         {
 420                 emerge(p);
 421                 if(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT)
 422                 {
 423                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 424                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 425                                         <<", index="<<m_area.index(p)
 426                                         <<", flags="<<(int)getFlagsRefUnsafe(p)
 427                                         <<" is inexistent"<<std::endl;*/
 428                         throw InvalidPositionException
 429                         ("VoxelManipulator: getNode: inexistent");
 430                 }
 431                 return getNodeRefUnsafe(p);
 432         }
 433         void setNode(v3s16 p, const MapNode &n)
 434         {
 435                 emerge(p);
 436
 437                 m_data[m_area.index(p)] = n;
 438                 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 439                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 440         }
 441         // TODO: Should be removed and replaced with setNode
 442         void setNodeNoRef(v3s16 p, const MapNode &n)
 443         {
 444                 setNode(p, n);
 445         }
 446
 447         /*void setExists(VoxelArea a)
 448         {
 449                 emerge(a);
 450                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 451                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 452                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 453                 {
 454                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
 455                 }
 456         }*/
 457
 458         /*MapNode & operator[](v3s16 p)
 459         {
 460                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 461                 if(isValidPosition(p) == false)
 462                         emerge(VoxelArea(p));
 463
 464                 return m_data[m_area.index(p)];
 465         }*/
 466
 467         /*
 468                 Set stuff if available without an emerge.
 469                 Return false if failed.
 470                 This is convenient but slower than playing around directly
 471                 with the m_data table with indices.
 472         */
 473         bool setNodeNoEmerge(v3s16 p, MapNode n)
 474         {
 475                 if(m_area.contains(p) == false)
 476                         return false;
 477                 m_data[m_area.index(p)] = n;
 478                 return true;
 479         }
 480         bool setNodeNoEmerge(s32 i, MapNode n)
 481         {
 482                 if(m_area.contains(i) == false)
 483                         return false;
 484                 m_data[i] = n;
 485                 return true;
 486         }
 487         /*bool setContentNoEmerge(v3s16 p, u8 c)
 488         {
 489                 if(isValidPosition(p) == false)
 490                         return false;
 491                 m_data[m_area.index(p)].d = c;
 492         }*/
 493
 494         /*
 495                 Control
 496         */
 497
 498         virtual void clear();
 499
 500         void print(std::ostream &o, INodeDefManager *nodemgr,
 501                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 502
 503         void addArea(VoxelArea area);
 504
 505         /*
 506                 Copy data and set flags to 0
 507                 dst_area.getExtent() <= src_area.getExtent()
 508         */
 509         void copyFrom(MapNode *src, VoxelArea src_area,
 510                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 511
 512         // Copy data
 513         void copyTo(MapNode *dst, VoxelArea dst_area,
 514                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 515
 516         /*
 517                 Algorithms
 518         */
 519
 520         void clearFlag(u8 flag);
 521
 522         // TODO: Move to voxelalgorithms.h
 523
 524         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 525                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 526         void unspreadLight(enum LightBank bank,
 527                         std::map<v3s16, u8> & from_nodes,
 528                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 529
 530         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 531         void spreadLight(enum LightBank bank,
 532                         std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
 533
 534         /*
 535                 Virtual functions
 536         */
 537
 538         /*
 539                 Get the contents of the requested area from somewhere.
 540                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 541                 Shall reset VOXELFLAG_NOT_LOADED
 542
 543                 If not found from source, add with VOXELFLAG_INEXISTENT
 544         */
 545         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 546         {
 547                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 548                 addArea(a);
 549                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 550                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 551                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 552                 {
 553                         s32 i = m_area.index(x,y,z);
 554                         // Don't touch nodes that have already been loaded
 555                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 556                                 continue;
 557                         m_flags[i] = VOXELFLAG_INEXISTENT;
 558                 }
 559         }
 560
 561         /*
 562                 Member variables
 563         */
 564
 565         /*
 566                 The area that is stored in m_data.
 567                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 568                 MaxEdge is 1 higher than maximum allowed position
 569         */
 570         VoxelArea m_area;
 571
 572         /*
 573                 NULL if data size is 0 (extent (0,0,0))
 574                 Data is stored as [z*h*w + y*h + x]
 575         */
 576         MapNode *m_data;
 577
 578         /*
 579                 Flags of all nodes
 580         */
 581         u8 *m_flags;
 582
 583         //TODO: Use these or remove them
 584         //TODO: Would these make any speed improvement?
 585         //bool m_pressure_route_valid;
 586         //v3s16 m_pressure_route_surface;
 587
 588         /*
 589                 Some settings
 590         */
 591         //bool m_disable_water_climb;
 592
 593 private:
 594 };
 595
 596 #endif
 597