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 operator==(const VoxelArea &other) const
 156         {
 157                 return (MinEdge == other.MinEdge
 158                                 && MaxEdge == other.MaxEdge);
 159         }
 160
 161         VoxelArea operator+(v3s16 off) const
 162         {
 163                 return VoxelArea(MinEdge+off, MaxEdge+off);
 164         }
 165
 166         VoxelArea operator-(v3s16 off) const
 167         {
 168                 return VoxelArea(MinEdge-off, MaxEdge-off);
 169         }
 170
 171         /*
 172                 Returns 0-6 non-overlapping areas that can be added to
 173                 a to make up this area.
 174
 175                 a: area inside *this
 176         */
 177         void diff(const VoxelArea &a, core::list<VoxelArea> &result)
 178         {
 179                 /*
 180                         This can result in a maximum of 6 areas
 181                 */
 182
 183                 // If a is an empty area, return the current area as a whole
 184                 if(a.getExtent() == v3s16(0,0,0))
 185                 {
 186                         VoxelArea b = *this;
 187                         if(b.getVolume() != 0)
 188                                 result.push_back(b);
 189                         return;
 190                 }
 191
 192                 assert(contains(a));
 193
 194                 // Take back area, XY inclusive
 195                 {
 196                         v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
 197                         v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
 198                         VoxelArea b(min, max);
 199                         if(b.getVolume() != 0)
 200                                 result.push_back(b);
 201                 }
 202
 203                 // Take front area, XY inclusive
 204                 {
 205                         v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
 206                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
 207                         VoxelArea b(min, max);
 208                         if(b.getVolume() != 0)
 209                                 result.push_back(b);
 210                 }
 211
 212                 // Take top area, X inclusive
 213                 {
 214                         v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
 215                         v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
 216                         VoxelArea b(min, max);
 217                         if(b.getVolume() != 0)
 218                                 result.push_back(b);
 219                 }
 220
 221                 // Take bottom area, X inclusive
 222                 {
 223                         v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
 224                         v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
 225                         VoxelArea b(min, max);
 226                         if(b.getVolume() != 0)
 227                                 result.push_back(b);
 228                 }
 229
 230                 // Take left area, non-inclusive
 231                 {
 232                         v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
 233                         v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
 234                         VoxelArea b(min, max);
 235                         if(b.getVolume() != 0)
 236                                 result.push_back(b);
 237                 }
 238
 239                 // Take right area, non-inclusive
 240                 {
 241                         v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
 242                         v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
 243                         VoxelArea b(min, max);
 244                         if(b.getVolume() != 0)
 245                                 result.push_back(b);
 246                 }
 247
 248         }
 249
 250         /*
 251                 Translates position from virtual coordinates to array index
 252         */
 253         s32 index(s16 x, s16 y, s16 z) const
 254         {
 255                 v3s16 em = getExtent();
 256                 v3s16 off = MinEdge;
 257                 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
 258                 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
 259                 return i;
 260         }
 261         s32 index(v3s16 p) const
 262         {
 263                 return index(p.X, p.Y, p.Z);
 264         }
 265
 266         void print(std::ostream &o) const
 267         {
 268                 v3s16 e = getExtent();
 269                 o<<"("<<MinEdge.X
 270                  <<","<<MinEdge.Y
 271                  <<","<<MinEdge.Z
 272                  <<")("<<MaxEdge.X
 273                  <<","<<MaxEdge.Y
 274                  <<","<<MaxEdge.Z
 275                  <<")"
 276                  <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
 277         }
 278
 279         // Edges are inclusive
 280         v3s16 MinEdge;
 281         v3s16 MaxEdge;
 282 };
 283
 284 // Hasn't been copied from source (emerged)
 285 #define VOXELFLAG_NOT_LOADED (1<<0)
 286 // Checked as being inexistent in source
 287 #define VOXELFLAG_INEXISTENT (1<<1)
 288 // Algorithm-dependent
 289 // flowWater: "visited"
 290 #define VOXELFLAG_CHECKED (1<<2)
 291 // Algorithm-dependent
 292 // getWaterPressure: "visited"
 293 #define VOXELFLAG_CHECKED2 (1<<3)
 294 // Algorithm-dependent
 295 // spreadWaterPressure: "visited"
 296 #define VOXELFLAG_CHECKED3 (1<<4)
 297 // Algorithm-dependent
 298 // water: "pressure check route node"
 299 #define VOXELFLAG_CHECKED4 (1<<5)
 300
 301 enum VoxelPrintMode
 302 {
 303         VOXELPRINT_NOTHING,
 304         VOXELPRINT_MATERIAL,
 305         VOXELPRINT_WATERPRESSURE,
 306 };
 307
 308 class VoxelManipulator /*: public NodeContainer*/
 309 {
 310 public:
 311         VoxelManipulator();
 312         virtual ~VoxelManipulator();
 313
 314         /*
 315                 Virtuals from NodeContainer
 316         */
 317         /*virtual u16 nodeContainerId() const
 318         {
 319                 return NODECONTAINER_ID_VOXELMANIPULATOR;
 320         }
 321         bool isValidPosition(v3s16 p)
 322         {
 323                 emerge(p);
 324                 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
 325         }*/
 326
 327         /*
 328                 These are a bit slow and shouldn't be used internally.
 329                 Use m_data[m_area.index(p)] instead.
 330         */
 331         MapNode getNode(v3s16 p)
 332         {
 333                 emerge(p);
 334
 335                 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
 336                 {
 337                         dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 338                                         <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 339                                         <<", index="<<m_area.index(p)
 340                                         <<", flags="<<(int)m_flags[m_area.index(p)]
 341                                         <<" is inexistent"<<std::endl;
 342                         throw InvalidPositionException
 343                         ("VoxelManipulator: getNode: inexistent");
 344                 }
 345
 346                 return m_data[m_area.index(p)];
 347         }
 348         void setNode(v3s16 p, MapNode &n)
 349         {
 350                 emerge(p);
 351
 352                 m_data[m_area.index(p)] = n;
 353                 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 354                 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 355         }
 356         void setNodeNoRef(v3s16 p, MapNode n)
 357         {
 358                 setNode(p, n);
 359         }
 360
 361         /*void setExists(VoxelArea a)
 362         {
 363                 emerge(a);
 364                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 365                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 366                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 367                 {
 368                         m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
 369                 }
 370         }*/
 371
 372         /*MapNode & operator[](v3s16 p)
 373         {
 374                 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 375                 if(isValidPosition(p) == false)
 376                         emerge(VoxelArea(p));
 377
 378                 return m_data[m_area.index(p)];
 379         }*/
 380
 381         /*
 382                 Control
 383         */
 384
 385         virtual void clear();
 386
 387         void print(std::ostream &o, VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 388
 389         void addArea(VoxelArea area);
 390
 391         /*
 392                 Copy data and set flags to 0
 393                 dst_area.getExtent() <= src_area.getExtent()
 394         */
 395         void copyFrom(MapNode *src, VoxelArea src_area,
 396                         v3s16 from_pos, v3s16 to_pos, v3s16 size);
 397
 398         /*
 399                 Algorithms
 400         */
 401
 402         void clearFlag(u8 flag);
 403
 404         void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 405                         core::map<v3s16, bool> & light_sources);
 406         void unspreadLight(enum LightBank bank,
 407                         core::map<v3s16, u8> & from_nodes,
 408                         core::map<v3s16, bool> & light_sources);
 409
 410         void spreadLight(enum LightBank bank, v3s16 p);
 411         void spreadLight(enum LightBank bank,
 412                         core::map<v3s16, bool> & from_nodes);
 413
 414 #if 0
 415         // VOXELFLAG_CHECKED2s must usually be cleared before calling
 416         // -1: dead end, 0-255: pressure
 417         // highest_y: Highest found water y is stored here.
 418         //            Must be initialized to -32768
 419         int getWaterPressure(v3s16 p, s16 &highest_y, int recur_count);
 420
 421         /*
 422                 VOXELFLAG_CHECKED3s must usually be cleared before calling.
 423
 424                 active_nodes: surface-touching air nodes with flow-causing
 425                 pressure. set-like dummy map container.
 426
 427                 Spreads pressure pr at node p to request_area or as far as
 428                 there is invalid pressure.
 429         */
 430         void spreadWaterPressure(v3s16 p, int pr,
 431                         VoxelArea request_area,
 432                         core::map<v3s16, u8> &active_nodes,
 433                         int recur_count);
 434
 435         /*
 436                 VOXELFLAG_CHECKED3s must usually be cleared before calling.
 437         */
 438         void updateAreaWaterPressure(VoxelArea a,
 439                         core::map<v3s16, u8> &active_nodes,
 440                         bool checked3_is_clear=false);
 441
 442         /*
 443                 Returns true if moved something
 444         */
 445         bool flowWater(v3s16 removed_pos,
 446                         core::map<v3s16, u8> &active_nodes,
 447                         int recursion_depth=0,
 448                         bool debugprint=false,
 449                         u32 stoptime=0
 450         );
 451
 452         /*
 453                 To flow some water, call this with the target node in
 454                 active_nodes
 455                 TODO: Make the active_nodes map to contain some vectors
 456                       that are properly sorted according to water flow order.
 457                           The current order makes water flow strangely if the
 458                           first one is always taken.
 459                           No, active_nodes should preserve the order stuff is
 460                           added to it, in addition to adhering the water flow
 461                           order.
 462         */
 463         void flowWater(core::map<v3s16, u8> &active_nodes,
 464                         int recursion_depth=0,
 465                         bool debugprint=false,
 466                         u32 timelimit=50
 467         );
 468 #endif
 469
 470         /*
 471                 Virtual functions
 472         */
 473
 474         /*
 475                 Get the contents of the requested area from somewhere.
 476                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 477                 Shall reset VOXELFLAG_NOT_LOADED
 478
 479                 If not found from source, add with VOXELFLAG_INEXISTENT
 480         */
 481         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 482         {
 483                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 484                 addArea(a);
 485                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 486                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 487                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 488                 {
 489                         s32 i = m_area.index(x,y,z);
 490                         // Don't touch nodes that have already been loaded
 491                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 492                                 continue;
 493                         m_flags[i] = VOXELFLAG_INEXISTENT;
 494                 }
 495         }
 496
 497         /*
 498                 Member variables
 499         */
 500
 501         /*
 502                 The area that is stored in m_data.
 503                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 504                 MaxEdge is 1 higher than maximum allowed position
 505         */
 506         VoxelArea m_area;
 507
 508         /*
 509                 NULL if data size is 0 (extent (0,0,0))
 510                 Data is stored as [z*h*w + y*h + x]
 511         */
 512         MapNode *m_data;
 513
 514         /*
 515                 Flags of all nodes
 516         */
 517         u8 *m_flags;
 518
 519         //TODO: Use these or remove them
 520         //TODO: Would these make any speed improvement?
 521         //bool m_pressure_route_valid;
 522         //v3s16 m_pressure_route_surface;
 523
 524         /*
 525                 Some settings
 526         */
 527         bool m_disable_water_climb;
 528
 529 private:
 530 };
 531
 532 #endif
 533