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 General Public License as published by
   7 the Free Software Foundation; either version 2 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 General Public License for more details.
  14
  15 You should have received a copy of the GNU 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 "common_irrlicht.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 };
 337
 338 class VoxelManipulator /*: public NodeContainer*/
 339 {
 340 public:
 341         VoxelManipulator();
 342         virtual ~VoxelManipulator();
 343
 344         /*
 345                 Virtuals from NodeContainer
 346         */
 347         /*virtual u16 nodeContainerId() const
 348         {
 349                 return NODECONTAINER_ID_VOXELMANIPULATOR;
 350         }
 351         bool isValidPosition(v3s16 p)
 352         {
 353                 emerge(p);
 354                 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
 355         }*/
 356
 357         /*
 358                 These are a bit slow and shouldn't be used internally.
 359                 Use m_data[m_area.index(p)] instead.
 360         */
 361         MapNode getNode(v3s16 p)
 362         {
 363                 emerge(p);
 364
 365                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 366                 {
 367                         dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 368                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 369                                         <<", index="<<m_area.index(p)
 370                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 371                                         <<" is inexistent"<<std::endl;
 372                         throw InvalidPositionException
 373                         ("VoxelManipulator: getNode: inexistent");
 374                 }
 375
 376                 return m_data[m_area.index(p)];
 377         }
 378         MapNode getNodeNoEx(v3s16 p)
 379         {
 380                 emerge(p);
 381
 382                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 383                 {
 384                         return MapNode(CONTENT_IGNORE);
 385                 }
 386
 387                 return m_data[m_area.index(p)];
 388         }
 389         MapNode getNodeNoExNoEmerge(v3s16 p)
 390         {
 391                 if(m_area.contains(p) == false)
 392                         return MapNode(CONTENT_IGNORE);
 393                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 394                         return MapNode(CONTENT_IGNORE);
 395                 return m_data[m_area.index(p)];
 396         }
 397         MapNode & getNodeRef(v3s16 p)
 398         {
 399                 emerge(p);
 400
 401                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 402                 {
 403                         dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 404                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 405                                         <<", index="<<m_area.index(p)
 406                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 407                                         <<" is inexistent"<<std::endl;
 408                         throw InvalidPositionException
 409                         ("VoxelManipulator: getNode: inexistent");
 410                 }
 411
 412                 return m_data[m_area.index(p)];
 413         }
 414         void setNode(v3s16 p, MapNode &n)
 415         {
 416                 emerge(p);
 417
 418                 m_data[m_area.index(p)] = n;
 419                 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 420                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 421         }
 422         void setNodeNoRef(v3s16 p, MapNode n)
 423         {
 424                 setNode(p, n);
 425         }
 426
 427         /*void setExists(VoxelArea a)
 428         {
 429                 emerge(a);
 430                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 431                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 432                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 433                 {
 434                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
 435                 }
 436         }*/
 437
 438         /*MapNode & operator[](v3s16 p)
 439         {
 440                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 441                 if(isValidPosition(p) == false)
 442                         emerge(VoxelArea(p));
 443
 444                 return m_data[m_area.index(p)];
 445         }*/
 446
 447         /*
 448                 Set stuff if available without an emerge.
 449                 Return false if failed.
 450                 This is convenient but slower than playing around directly
 451                 with the m_data table with indices.
 452         */
 453         bool setNodeNoEmerge(v3s16 p, MapNode n)
 454         {
 455                 if(m_area.contains(p) == false)
 456                         return false;
 457                 m_data[m_area.index(p)] = n;
 458                 return true;
 459         }
 460         bool setNodeNoEmerge(s32 i, MapNode n)
 461         {
 462                 if(m_area.contains(i) == false)
 463                         return false;
 464                 m_data[i] = n;
 465                 return true;
 466         }
 467         /*bool setContentNoEmerge(v3s16 p, u8 c)
 468         {
 469                 if(isValidPosition(p) == false)
 470                         return false;
 471                 m_data[m_area.index(p)].d = c;
 472         }*/
 473
 474         /*
 475                 Control
 476         */
 477
 478         virtual void clear();
 479
 480         void print(std::ostream &o, INodeDefManager *nodemgr,
 481                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 482
 483         void addArea(VoxelArea area);
 484
 485         /*
 486                 Copy data and set flags to 0
 487                 dst_area.getExtent() <= src_area.getExtent()
 488         */
 489         void copyFrom(MapNode *src, VoxelArea src_area,
 490                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 491
 492         // Copy data
 493         void copyTo(MapNode *dst, VoxelArea dst_area,
 494                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 495
 496         /*
 497                 Algorithms
 498         */
 499
 500         void clearFlag(u8 flag);
 501
 502         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 503                         core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr);
 504         void unspreadLight(enum LightBank bank,
 505                         core::map<v3s16, u8> & from_nodes,
 506                         core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr);
 507
 508         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 509         void spreadLight(enum LightBank bank,
 510                         core::map<v3s16, bool> & from_nodes, INodeDefManager *nodemgr);
 511
 512         /*
 513                 Virtual functions
 514         */
 515
 516         /*
 517                 Get the contents of the requested area from somewhere.
 518                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 519                 Shall reset VOXELFLAG_NOT_LOADED
 520
 521                 If not found from source, add with VOXELFLAG_INEXISTENT
 522         */
 523         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 524         {
 525                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 526                 addArea(a);
 527                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 528                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 529                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 530                 {
 531                         s32 i = m_area.index(x,y,z);
 532                         // Don't touch nodes that have already been loaded
 533                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 534                                 continue;
 535                         m_flags[i] = VOXELFLAG_INEXISTENT;
 536                 }
 537         }
 538
 539         /*
 540                 Member variables
 541         */
 542
 543         /*
 544                 The area that is stored in m_data.
 545                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 546                 MaxEdge is 1 higher than maximum allowed position
 547         */
 548         VoxelArea m_area;
 549
 550         /*
 551                 NULL if data size is 0 (extent (0,0,0))
 552                 Data is stored as [z*h*w + y*h + x]
 553         */
 554         MapNode *m_data;
 555
 556         /*
 557                 Flags of all nodes
 558         */
 559         u8 *m_flags;
 560
 561         //TODO: Use these or remove them
 562         //TODO: Would these make any speed improvement?
 563         //bool m_pressure_route_valid;
 564         //v3s16 m_pressure_route_surface;
 565
 566         /*
 567                 Some settings
 568         */
 569         //bool m_disable_water_climb;
 570
 571 private:
 572 };
 573
 574 #endif
 575