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