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         /*
 415                 Virtual functions
 416         */
 417
 418         /*
 419                 Get the contents of the requested area from somewhere.
 420                 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
 421                 Shall reset VOXELFLAG_NOT_LOADED
 422
 423                 If not found from source, add with VOXELFLAG_INEXISTENT
 424         */
 425         virtual void emerge(VoxelArea a, s32 caller_id=-1)
 426         {
 427                 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 428                 addArea(a);
 429                 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
 430                 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
 431                 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
 432                 {
 433                         s32 i = m_area.index(x,y,z);
 434                         // Don't touch nodes that have already been loaded
 435                         if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
 436                                 continue;
 437                         m_flags[i] = VOXELFLAG_INEXISTENT;
 438                 }
 439         }
 440
 441         /*
 442                 Member variables
 443         */
 444
 445         /*
 446                 The area that is stored in m_data.
 447                 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
 448                 MaxEdge is 1 higher than maximum allowed position
 449         */
 450         VoxelArea m_area;
 451
 452         /*
 453                 NULL if data size is 0 (extent (0,0,0))
 454                 Data is stored as [z*h*w + y*h + x]
 455         */
 456         MapNode *m_data;
 457
 458         /*
 459                 Flags of all nodes
 460         */
 461         u8 *m_flags;
 462
 463         //TODO: Use these or remove them
 464         //TODO: Would these make any speed improvement?
 465         //bool m_pressure_route_valid;
 466         //v3s16 m_pressure_route_surface;
 467
 468         /*
 469                 Some settings
 470         */
 471         bool m_disable_water_climb;
 472
 473 private:
 474 };
 475
 476 #endif
 477