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