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 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 <irrList.h>
  26 #include <iostream>
  27 #include "debug.h"
  28 #include "mapnode.h"
  29
  30 class INodeDefManager;
  31
  32 // For VC++
  33 #undef min
  34 #undef max
  35
  36 /*
  37         A fast voxel manipulator class.
  38
  39         In normal operation, it fetches more map when it is requested.
  40         It can also be used so that all allowed area is fetched at the
  41         start, using ManualMapVoxelManipulator.
  42
  43         Not thread-safe.
  44 */
  45
  46 /*
  47         Debug stuff
  48 */
  49 extern u32 emerge_time;
  50 extern u32 emerge_load_time;
  51
  52 /*
  53         This class resembles aabbox3d<s16> a lot, but has inclusive
  54         edges for saner handling of integer sizes
  55 */
  56 class VoxelArea
  57 {
  58 public:
  59         // Starts as zero sized
  60         VoxelArea():
  61                 MinEdge(1,1,1),
  62                 MaxEdge(0,0,0)
  63         {
  64         }
  65         VoxelArea(v3s16 min_edge, v3s16 max_edge):
  66                 MinEdge(min_edge),
  67                 MaxEdge(max_edge)
  68         {
  69         }
  70         VoxelArea(v3s16 p):
  71                 MinEdge(p),
  72                 MaxEdge(p)
  73         {
  74         }
  75
  76         /*
  77                 Modifying methods
  78         */
  79
  80         void addArea(VoxelArea &a)
  81         {
  82                 if(getExtent() == v3s16(0,0,0))
  83                 {
  84                         *this = a;
  85                         return;
  86                 }
  87                 if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
  88                 if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
  89                 if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
  90                 if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
  91                 if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
  92                 if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
  93         }
  94         void addPoint(v3s16 p)
  95         {
  96                 if(getExtent() == v3s16(0,0,0))
  97                 {
  98                         MinEdge = p;
  99                         MaxEdge = p;
 100                         return;
 101                 }
 102                 if(p.X < MinEdge.X) MinEdge.X = p.X;
 103                 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
 104                 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
 105                 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
 106                 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
 107                 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
 108         }
 109
 110         // Pad with d nodes
 111         void pad(v3s16 d)
 112         {
 113                 MinEdge -= d;
 114                 MaxEdge += d;
 115         }
 116
 117         /*void operator+=(v3s16 off)
 118         {
 119                 MinEdge += off;
 120                 MaxEdge += off;
 121         }
 122
 123         void operator-=(v3s16 off)
 124         {
 125                 MinEdge -= off;
 126                 MaxEdge -= off;
 127         }*/
 128
 129         /*
 130                 const methods
 131         */
 132
 133         v3s16 getExtent() const
 134         {
 135                 return MaxEdge - MinEdge + v3s16(1,1,1);
 136         }
 137         s32 getVolume() const
 138         {
 139                 v3s16 e = getExtent();
 140                 return (s32)e.X * (s32)e.Y * (s32)e.Z;
 141         }
 142         bool contains(const VoxelArea &a) const
 143         {
 144                 // No area contains an empty area
 145                 // NOTE: Algorithms depend on this, so do not change.
 146                 if(a.getExtent() == v3s16(0,0,0))
 147                         return false;
 148
 149                 return(
 150                         a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
 151                         a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
 152                         a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
 153                 );
 154         }
 155         bool contains(v3s16 p) const
 156         {
 157                 return(
 158                         p.X >= MinEdge.X && p.X <= MaxEdge.X &&
 159                         p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
 160                         p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
 161                 );
 162         }
 163         bool contains(s32 i) const
 164         {
 165                 return (i >= 0 && i < getVolume());
 166         }
 167         bool operator==(const VoxelArea &other) const
 168         {
 169                 return (MinEdge == other.MinEdge
 170                                 && MaxEdge == other.MaxEdge);
 171         }
 172
 173         VoxelArea operator+(v3s16 off) const
 174         {
 175                 return VoxelArea(MinEdge+off, MaxEdge+off);
 176         }
 177
 178         VoxelArea operator-(v3s16 off) const
 179         {
 180                 return VoxelArea(MinEdge-off, MaxEdge-off);
 181         }
 182
 183         /*
 184                 Returns 0-6 non-overlapping areas that can be added to
 185                 a to make up this area.
 186
 187                 a: area inside *this
 188         */
 189         void diff(const VoxelArea &a, core::list<VoxelArea> &result)
 190         {
 191                 /*
 192                         This can result in a maximum of 6 areas
 193                 */
 194
 195                 // If a is an empty area, return the current area as a whole
 196                 if(a.getExtent() == v3s16(0,0,0))
 197                 {
 198                         VoxelArea b = *this;
 199                         if(b.getVolume() != 0)
 200                                 result.push_back(b);
 201                         return;
 202                 }
 203
 204                 assert(contains(a));
 205
 206                 // Take back area, XY inclusive
 207                 {
 208                         v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
 209                         v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
 210                         VoxelArea b(min, max);
 211                         if(b.getVolume() != 0)
 212                                 result.push_back(b);
 213                 }
 214
 215                 // Take front area, XY inclusive
 216                 {
 217                         v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
 218                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
 219                         VoxelArea b(min, max);
 220                         if(b.getVolume() != 0)
 221                                 result.push_back(b);
 222                 }
 223
 224                 // Take top area, X inclusive
 225                 {
 226                         v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
 227                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
 228                         VoxelArea b(min, max);
 229                         if(b.getVolume() != 0)
 230                                 result.push_back(b);
 231                 }
 232
 233                 // Take bottom area, X inclusive
 234                 {
 235                         v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
 236                         v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
 237                         VoxelArea b(min, max);
 238                         if(b.getVolume() != 0)
 239                                 result.push_back(b);
 240                 }
 241
 242                 // Take left area, non-inclusive
 243                 {
 244                         v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
 245                         v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
 246                         VoxelArea b(min, max);
 247                         if(b.getVolume() != 0)
 248                                 result.push_back(b);
 249                 }
 250
 251                 // Take right area, non-inclusive
 252                 {
 253                         v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
 254                         v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
 255                         VoxelArea b(min, max);
 256                         if(b.getVolume() != 0)
 257                                 result.push_back(b);
 258                 }
 259
 260         }
 261
 262         /*
 263                 Translates position from virtual coordinates to array index
 264         */
 265         s32 index(s16 x, s16 y, s16 z) const
 266         {
 267                 v3s16 em = getExtent();
 268                 v3s16 off = MinEdge;
 269                 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
 270                 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
 271                 return i;
 272         }
 273         s32 index(v3s16 p) const
 274         {
 275                 return index(p.X, p.Y, p.Z);
 276         }
 277
 278         // Translate index in the X coordinate
 279         void add_x(const v3s16 &extent, u32 &i, s16 a)
 280         {
 281                 i += a;
 282         }
 283         // Translate index in the Y coordinate
 284         void add_y(const v3s16 &extent, u32 &i, s16 a)
 285         {
 286                 i += a * extent.X;
 287         }
 288         // Translate index in the Z coordinate
 289         void add_z(const v3s16 &extent, u32 &i, s16 a)
 290         {
 291                 i += a * extent.X*extent.Y;
 292         }
 293         // Translate index in space
 294         void add_p(const v3s16 &extent, u32 &i, v3s16 a)
 295         {
 296                 i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
 297         }
 298
 299         /*
 300                 Print method for debugging
 301         */
 302         void print(std::ostream &o) const
 303         {
 304                 v3s16 e = getExtent();
 305                 o<<"("<<MinEdge.X
 306                  <<","<<MinEdge.Y
 307                  <<","<<MinEdge.Z
 308                  <<")("<<MaxEdge.X
 309                  <<","<<MaxEdge.Y
 310                  <<","<<MaxEdge.Z
 311                  <<")"
 312                  <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
 313         }
 314
 315         // Edges are inclusive
 316         v3s16 MinEdge;
 317         v3s16 MaxEdge;
 318 };
 319
 320 // Hasn't been copied from source (emerged)
 321 #define VOXELFLAG_NOT_LOADED (1<<0)
 322 // Checked as being inexistent in source
 323 #define VOXELFLAG_INEXISTENT (1<<1)
 324 // Algorithm-dependent
 325 #define VOXELFLAG_CHECKED1 (1<<2)
 326 // Algorithm-dependent
 327 #define VOXELFLAG_CHECKED2 (1<<3)
 328 // Algorithm-dependent
 329 #define VOXELFLAG_CHECKED3 (1<<4)
 330 // Algorithm-dependent
 331 #define VOXELFLAG_CHECKED4 (1<<5)
 332
 333 enum VoxelPrintMode
 334 {
 335         VOXELPRINT_NOTHING,
 336         VOXELPRINT_MATERIAL,
 337         VOXELPRINT_WATERPRESSURE,
 338         VOXELPRINT_LIGHT_DAY,
 339 };
 340
 341 class VoxelManipulator /*: public NodeContainer*/
 342 {
 343 public:
 344         VoxelManipulator();
 345         virtual ~VoxelManipulator();
 346
 347         /*
 348                 Virtuals from NodeContainer
 349         */
 350         /*virtual u16 nodeContainerId() const
 351         {
 352                 return NODECONTAINER_ID_VOXELMANIPULATOR;
 353         }
 354         bool isValidPosition(v3s16 p)
 355         {
 356                 emerge(p);
 357                 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
 358         }*/
 359
 360         /*
 361                 These are a bit slow and shouldn't be used internally.
 362                 Use m_data[m_area.index(p)] instead.
 363         */
 364         MapNode getNode(v3s16 p)
 365         {
 366                 emerge(p);
 367
 368                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 369                 {
 370                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 371                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 372                                         <<", index="<<m_area.index(p)
 373                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 374                                         <<" is inexistent"<<std::endl;*/
 375                         throw InvalidPositionException
 376                         ("VoxelManipulator: getNode: inexistent");
 377                 }
 378
 379                 return m_data[m_area.index(p)];
 380         }
 381         MapNode getNodeNoEx(v3s16 p)
 382         {
 383                 emerge(p);
 384
 385                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 386                 {
 387                         return MapNode(CONTENT_IGNORE);
 388                 }
 389
 390                 return m_data[m_area.index(p)];
 391         }
 392         MapNode getNodeNoExNoEmerge(v3s16 p)
 393         {
 394                 if(m_area.contains(p) == false)
 395                         return MapNode(CONTENT_IGNORE);
 396                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 397                         return MapNode(CONTENT_IGNORE);
 398                 return m_data[m_area.index(p)];
 399         }
 400         // Stuff explodes if non-emerged area is touched with this.
 401         // Emerge first, and check VOXELFLAG_INEXISTENT if appropriate.
 402         MapNode & getNodeRefUnsafe(v3s16 p)
 403         {
 404                 return m_data[m_area.index(p)];
 405         }
 406         u8 & getFlagsRefUnsafe(v3s16 p)
 407         {
 408                 return m_flags[m_area.index(p)];
 409         }
 410         bool exists(v3s16 p)
 411         {
 412                 return m_area.contains(p) &&
 413                         !(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT);
 414         }
 415         MapNode & getNodeRef(v3s16 p)
 416         {
 417                 emerge(p);
 418                 if(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT)
 419                 {
 420                         /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 421                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 422                                         <<", index="<<m_area.index(p)
 423                                         <<", flags="<<(int)getFlagsRefUnsafe(p)
 424                                         <<" is inexistent"<<std::endl;*/
 425                         throw InvalidPositionException
 426                         ("VoxelManipulator: getNode: inexistent");
 427                 }
 428                 return getNodeRefUnsafe(p);
 429         }
 430         void setNode(v3s16 p, const MapNode &n)
 431         {
 432                 emerge(p);
 433
 434                 m_data[m_area.index(p)] = n;
 435                 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 436                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 437         }
 438         // TODO: Should be removed and replaced with setNode
 439         void setNodeNoRef(v3s16 p, const MapNode &n)
 440         {
 441                 setNode(p, n);
 442         }
 443
 444         /*void setExists(VoxelArea a)
 445         {
 446                 emerge(a);
 447                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 448                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 449                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 450                 {
 451                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
 452                 }
 453         }*/
 454
 455         /*MapNode & operator[](v3s16 p)
 456         {
 457                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 458                 if(isValidPosition(p) == false)
 459                         emerge(VoxelArea(p));
 460
 461                 return m_data[m_area.index(p)];
 462         }*/
 463
 464         /*
 465                 Set stuff if available without an emerge.
 466                 Return false if failed.
 467                 This is convenient but slower than playing around directly
 468                 with the m_data table with indices.
 469         */
 470         bool setNodeNoEmerge(v3s16 p, MapNode n)
 471         {
 472                 if(m_area.contains(p) == false)
 473                         return false;
 474                 m_data[m_area.index(p)] = n;
 475                 return true;
 476         }
 477         bool setNodeNoEmerge(s32 i, MapNode n)
 478         {
 479                 if(m_area.contains(i) == false)
 480                         return false;
 481                 m_data[i] = n;
 482                 return true;
 483         }
 484         /*bool setContentNoEmerge(v3s16 p, u8 c)
 485         {
 486                 if(isValidPosition(p) == false)
 487                         return false;
 488                 m_data[m_area.index(p)].d = c;
 489         }*/
 490
 491         /*
 492                 Control
 493         */
 494
 495         virtual void clear();
 496
 497         void print(std::ostream &o, INodeDefManager *nodemgr,
 498                         VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 499
 500         void addArea(VoxelArea area);
 501
 502         /*
 503                 Copy data and set flags to 0
 504                 dst_area.getExtent() <= src_area.getExtent()
 505         */
 506         void copyFrom(MapNode *src, VoxelArea src_area,
 507                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 508
 509         // Copy data
 510         void copyTo(MapNode *dst, VoxelArea dst_area,
 511                         v3s16 dst_pos, v3s16 from_pos, v3s16 size);
 512
 513         /*
 514                 Algorithms
 515         */
 516
 517         void clearFlag(u8 flag);
 518
 519         // TODO: Move to voxelalgorithms.h
 520
 521         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 522                         core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr);
 523         void unspreadLight(enum LightBank bank,
 524                         core::map<v3s16, u8> & from_nodes,
 525                         core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr);
 526
 527         void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
 528         void spreadLight(enum LightBank bank,
 529                         core::map<v3s16, bool> & from_nodes, INodeDefManager *nodemgr);
 530
 531         /*
 532                 Virtual functions
 533         */
 534
 535         /*
 536                 Get the contents of the requested area from somewhere.
 537                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 538                 Shall reset VOXELFLAG_NOT_LOADED
 539
 540                 If not found from source, add with VOXELFLAG_INEXISTENT
 541         */
 542         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 543         {
 544                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 545                 addArea(a);
 546                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 547                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 548                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 549                 {
 550                         s32 i = m_area.index(x,y,z);
 551                         // Don't touch nodes that have already been loaded
 552                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 553                                 continue;
 554                         m_flags[i] = VOXELFLAG_INEXISTENT;
 555                 }
 556         }
 557
 558         /*
 559                 Member variables
 560         */
 561
 562         /*
 563                 The area that is stored in m_data.
 564                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 565                 MaxEdge is 1 higher than maximum allowed position
 566         */
 567         VoxelArea m_area;
 568
 569         /*
 570                 NULL if data size is 0 (extent (0,0,0))
 571                 Data is stored as [z*h*w + y*h + x]
 572         */
 573         MapNode *m_data;
 574
 575         /*
 576                 Flags of all nodes
 577         */
 578         u8 *m_flags;
 579
 580         //TODO: Use these or remove them
 581         //TODO: Would these make any speed improvement?
 582         //bool m_pressure_route_valid;
 583         //v3s16 m_pressure_route_surface;
 584
 585         /*
 586                 Some settings
 587         */
 588         //bool m_disable_water_climb;
 589
 590 private:
 591 };
 592
 593 #endif
 594