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(v3s16 p)
 417         {
 418                 return m_data[m_area.index(p)];
 419         }
 420         u8 & getFlagsRefUnsafe(v3s16 p)
 421         {
 422                 return m_flags[m_area.index(p)];
 423         }
 424         bool exists(v3s16 p)
 425         {
 426                 return m_area.contains(p) &&
 427                         !(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
 428         }
 429         MapNode & getNodeRef(v3s16 p)
 430         {
 431                 VoxelArea voxel_area(p);
 432                 addArea(voxel_area);
 433                 if(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA)
 434                 {
 435                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 436                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 437                                         <<", index="<<m_area.index(p)
 438                                         <<", flags="<<(int)getFlagsRefUnsafe(p)
 439                                         <<" is inexistent"<<std::endl;*/
 440                         throw InvalidPositionException
 441                         ("VoxelManipulator: getNode: inexistent");
 442                 }
 443                 return getNodeRefUnsafe(p);
 444         }
 445         void setNode(v3s16 p, const MapNode &n)
 446         {
 447                 VoxelArea voxel_area(p);
 448                 addArea(voxel_area);
 449
 450                 m_data[m_area.index(p)] = n;
 451                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
 452         }
 453         // TODO: Should be removed and replaced with setNode
 454         void setNodeNoRef(v3s16 p, const MapNode &n)
 455         {
 456                 setNode(p, n);
 457         }
 458
 459         /*void setExists(VoxelArea a)
 460         {
 461                 addArea(a);
 462                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 463                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 464                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 465                 {
 466                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_NO_DATA;
 467                 }
 468         }*/
 469
 470         /*MapNode & operator[](v3s16 p)
 471         {
 472                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 473                 if(isValidPosition(p) == false)
 474                         addArea(VoxelArea(p));
 475
 476                 return m_data[m_area.index(p)];
 477         }*/
 478
 479         /*
 480                 Set stuff if available without an emerge.
 481                 Return false if failed.
 482                 This is convenient but slower than playing around directly
 483                 with the m_data table with indices.
 484         */
 485         bool setNodeNoEmerge(v3s16 p, MapNode n)
 486         {
 487                 if(m_area.contains(p) == false)
 488                         return false;
 489                 m_data[m_area.index(p)] = n;
 490                 return true;
 491         }
 492         bool setNodeNoEmerge(s32 i, MapNode n)
 493         {
 494                 if(m_area.contains(i) == false)
 495                         return false;
 496                 m_data[i] = n;
 497                 return true;
 498         }
 499         /*bool setContentNoEmerge(v3s16 p, u8 c)
 500         {
 501                 if(isValidPosition(p) == false)
 502                         return false;
 503                 m_data[m_area.index(p)].d = c;
 504         }*/
 505
 506         /*
 507                 Control
 508         */
 509
 510         virtual void clear();
 511
 512         void print(std::ostream &o, INodeDefManager *nodemgr,
 513                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 514
 515         void addArea(const VoxelArea &area);
 516
 517         /*
 518                 Copy data and set flags to 0
 519                 dst_area.getExtent() <= src_area.getExtent()
 520         */
 521         void copyFrom(MapNode *src, const VoxelArea& src_area,
 522                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 523
 524         // Copy data
 525         void copyTo(MapNode *dst, const VoxelArea& dst_area,
 526                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 527
 528         /*
 529                 Algorithms
 530         */
 531
 532         void clearFlag(u8 flag);
 533
 534         // TODO: Move to voxelalgorithms.h
 535
 536         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 537                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 538         void unspreadLight(enum LightBank bank,
 539                         std::map<v3s16, u8> & from_nodes,
 540                         std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
 541
 542         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 543         void spreadLight(enum LightBank bank,
 544                         std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
 545
 546         /*
 547                 Virtual functions
 548         */
 549
 550         /*
 551                 Member variables
 552         */
 553
 554         /*
 555                 The area that is stored in m_data.
 556                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 557                 MaxEdge is 1 higher than maximum allowed position
 558         */
 559         VoxelArea m_area;
 560
 561         /*
 562                 NULL if data size is 0 (extent (0,0,0))
 563                 Data is stored as [z*h*w + y*h + x]
 564         */
 565         MapNode *m_data;
 566
 567         /*
 568                 Flags of all nodes
 569         */
 570         u8 *m_flags;
 571
 572         //TODO: Use these or remove them
 573         //TODO: Would these make any speed improvement?
 574         //bool m_pressure_route_valid;
 575         //v3s16 m_pressure_route_surface;
 576
 577         /*
 578                 Some settings
 579         */
 580         //bool m_disable_water_climb;
 581
 582 private:
 583 };
 584
 585 #endif
 586