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