src/voxel.h

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