src/voxel.h

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