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