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