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 & getNodeRef(v3s16 p)
 388         {
 389                 emerge(p);
 390
 391                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 392                 {
 393                         dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 394                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 395                                         <<", index="<<m_area.index(p)
 396                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 397                                         <<" is inexistent"<<std::endl;
 398                         throw InvalidPositionException
 399                         ("VoxelManipulator: getNode: inexistent");
 400                 }
 401
 402                 return m_data[m_area.index(p)];
 403         }
 404         void setNode(v3s16 p, MapNode &n)
 405         {
 406                 emerge(p);
 407
 408                 m_data[m_area.index(p)] = n;
 409                 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 410                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 411         }
 412         void setNodeNoRef(v3s16 p, MapNode n)
 413         {
 414                 setNode(p, n);
 415         }
 416
 417         /*void setExists(VoxelArea a)
 418         {
 419                 emerge(a);
 420                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 421                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 422                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 423                 {
 424                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
 425                 }
 426         }*/
 427
 428         /*MapNode & operator[](v3s16 p)
 429         {
 430                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 431                 if(isValidPosition(p) == false)
 432                         emerge(VoxelArea(p));
 433
 434                 return m_data[m_area.index(p)];
 435         }*/
 436
 437         /*
 438                 Set stuff if available without an emerge.
 439                 Return false if failed.
 440                 This is convenient but slower than playing around directly
 441                 with the m_data table with indices.
 442         */
 443         bool setNodeNoEmerge(v3s16 p, MapNode n)
 444         {
 445                 if(m_area.contains(p) == false)
 446                         return false;
 447                 m_data[m_area.index(p)] = n;
 448         }
 449         bool setNodeNoEmerge(s32 i, MapNode n)
 450         {
 451                 if(m_area.contains(i) == false)
 452                         return false;
 453                 m_data[i] = n;
 454         }
 455         /*bool setContentNoEmerge(v3s16 p, u8 c)
 456         {
 457                 if(isValidPosition(p) == false)
 458                         return false;
 459                 m_data[m_area.index(p)].d = c;
 460         }*/
 461
 462         /*
 463                 Control
 464         */
 465
 466         virtual void clear();
 467
 468         void print(std::ostream &o, VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 469
 470         void addArea(VoxelArea area);
 471
 472         /*
 473                 Copy data and set flags to 0
 474                 dst_area.getExtent() <= src_area.getExtent()
 475         */
 476         void copyFrom(MapNode *src, VoxelArea src_area,
 477                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 478
 479         // Copy data
 480         void copyTo(MapNode *dst, VoxelArea dst_area,
 481                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 482
 483         /*
 484                 Algorithms
 485         */
 486
 487         void clearFlag(u8 flag);
 488
 489         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 490                         core::map<v3s16, bool> & light_sources);
 491         void unspreadLight(enum LightBank bank,
 492                         core::map<v3s16, u8> & from_nodes,
 493                         core::map<v3s16, bool> & light_sources);
 494
 495         void spreadLight(enum LightBank bank, v3s16 p);
 496         void spreadLight(enum LightBank bank,
 497                         core::map<v3s16, bool> & from_nodes);
 498
 499         /*
 500                 Virtual functions
 501         */
 502
 503         /*
 504                 Get the contents of the requested area from somewhere.
 505                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 506                 Shall reset VOXELFLAG_NOT_LOADED
 507
 508                 If not found from source, add with VOXELFLAG_INEXISTENT
 509         */
 510         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 511         {
 512                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 513                 addArea(a);
 514                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 515                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 516                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 517                 {
 518                         s32 i = m_area.index(x,y,z);
 519                         // Don't touch nodes that have already been loaded
 520                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 521                                 continue;
 522                         m_flags[i] = VOXELFLAG_INEXISTENT;
 523                 }
 524         }
 525
 526         /*
 527                 Member variables
 528         */
 529
 530         /*
 531                 The area that is stored in m_data.
 532                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 533                 MaxEdge is 1 higher than maximum allowed position
 534         */
 535         VoxelArea m_area;
 536
 537         /*
 538                 NULL if data size is 0 (extent (0,0,0))
 539                 Data is stored as [z*h*w + y*h + x]
 540         */
 541         MapNode *m_data;
 542
 543         /*
 544                 Flags of all nodes
 545         */
 546         u8 *m_flags;
 547
 548         //TODO: Use these or remove them
 549         //TODO: Would these make any speed improvement?
 550         //bool m_pressure_route_valid;
 551         //v3s16 m_pressure_route_surface;
 552
 553         /*
 554                 Some settings
 555         */
 556         bool m_disable_water_climb;
 557
 558 private:
 559 };
 560
 561 #endif
 562