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