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         }
 457         bool setNodeNoEmerge(s32 i, MapNode n)
 458         {
 459                 if(m_area.contains(i) == false)
 460                         return false;
 461                 m_data[i] = n;
 462         }
 463         /*bool setContentNoEmerge(v3s16 p, u8 c)
 464         {
 465                 if(isValidPosition(p) == false)
 466                         return false;
 467                 m_data[m_area.index(p)].d = c;
 468         }*/
 469
 470         /*
 471                 Control
 472         */
 473
 474         virtual void clear();
 475
 476         void print(std::ostream &o, VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 477
 478         void addArea(VoxelArea area);
 479
 480         /*
 481                 Copy data and set flags to 0
 482                 dst_area.getExtent() <= src_area.getExtent()
 483         */
 484         void copyFrom(MapNode *src, VoxelArea src_area,
 485                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 486
 487         // Copy data
 488         void copyTo(MapNode *dst, VoxelArea dst_area,
 489                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 490
 491         /*
 492                 Algorithms
 493         */
 494
 495         void clearFlag(u8 flag);
 496
 497         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 498                         core::map<v3s16, bool> & light_sources);
 499         void unspreadLight(enum LightBank bank,
 500                         core::map<v3s16, u8> & from_nodes,
 501                         core::map<v3s16, bool> & light_sources);
 502
 503         void spreadLight(enum LightBank bank, v3s16 p);
 504         void spreadLight(enum LightBank bank,
 505                         core::map<v3s16, bool> & from_nodes);
 506
 507         /*
 508                 Virtual functions
 509         */
 510
 511         /*
 512                 Get the contents of the requested area from somewhere.
 513                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 514                 Shall reset VOXELFLAG_NOT_LOADED
 515
 516                 If not found from source, add with VOXELFLAG_INEXISTENT
 517         */
 518         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 519         {
 520                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 521                 addArea(a);
 522                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 523                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 524                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 525                 {
 526                         s32 i = m_area.index(x,y,z);
 527                         // Don't touch nodes that have already been loaded
 528                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 529                                 continue;
 530                         m_flags[i] = VOXELFLAG_INEXISTENT;
 531                 }
 532         }
 533
 534         /*
 535                 Member variables
 536         */
 537
 538         /*
 539                 The area that is stored in m_data.
 540                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 541                 MaxEdge is 1 higher than maximum allowed position
 542         */
 543         VoxelArea m_area;
 544
 545         /*
 546                 NULL if data size is 0 (extent (0,0,0))
 547                 Data is stored as [z*h*w + y*h + x]
 548         */
 549         MapNode *m_data;
 550
 551         /*
 552                 Flags of all nodes
 553         */
 554         u8 *m_flags;
 555
 556         //TODO: Use these or remove them
 557         //TODO: Would these make any speed improvement?
 558         //bool m_pressure_route_valid;
 559         //v3s16 m_pressure_route_surface;
 560
 561         /*
 562                 Some settings
 563         */
 564         //bool m_disable_water_climb;
 565
 566 private:
 567 };
 568
 569 #endif
 570