src/voxelalgorithms.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2013 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 Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser 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 #include "voxelalgorithms.h"
  21 #include "nodedef.h"
  22 #include "mapblock.h"
  23 #include "map.h"
  24
  25 namespace voxalgo
  26 {
  27
  28 void setLight(VoxelManipulator &v, VoxelArea a, u8 light,
  29                 INodeDefManager *ndef)
  30 {
  31         for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
  32         for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
  33         for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
  34         {
  35                 v3s16 p(x,y,z);
  36                 MapNode &n = v.getNodeRefUnsafe(p);
  37                 n.setLight(LIGHTBANK_DAY, light, ndef);
  38                 n.setLight(LIGHTBANK_NIGHT, light, ndef);
  39         }
  40 }
  41
  42 void clearLightAndCollectSources(VoxelManipulator &v, VoxelArea a,
  43                 enum LightBank bank, INodeDefManager *ndef,
  44                 std::set<v3s16> & light_sources,
  45                 std::map<v3s16, u8> & unlight_from)
  46 {
  47         // The full area we shall touch
  48         VoxelArea required_a = a;
  49         required_a.pad(v3s16(0,0,0));
  50         // Make sure we have access to it
  51         v.addArea(a);
  52
  53         for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
  54         for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
  55         for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
  56         {
  57                 v3s16 p(x,y,z);
  58                 MapNode &n = v.getNodeRefUnsafe(p);
  59                 u8 oldlight = n.getLight(bank, ndef);
  60                 n.setLight(bank, 0, ndef);
  61
  62                 // If node sources light, add to list
  63                 u8 source = ndef->get(n).light_source;
  64                 if(source != 0)
  65                         light_sources.insert(p);
  66
  67                 // Collect borders for unlighting
  68                 if((x==a.MinEdge.X || x == a.MaxEdge.X
  69                 || y==a.MinEdge.Y || y == a.MaxEdge.Y
  70                 || z==a.MinEdge.Z || z == a.MaxEdge.Z)
  71                 && oldlight != 0)
  72                 {
  73                         unlight_from[p] = oldlight;
  74                 }
  75         }
  76 }
  77
  78 SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
  79                 bool inexistent_top_provides_sunlight,
  80                 std::set<v3s16> & light_sources,
  81                 INodeDefManager *ndef)
  82 {
  83         // Return values
  84         bool bottom_sunlight_valid = true;
  85
  86         // The full area we shall touch extends one extra at top and bottom
  87         VoxelArea required_a = a;
  88         required_a.pad(v3s16(0,1,0));
  89         // Make sure we have access to it
  90         v.addArea(a);
  91
  92         s16 max_y = a.MaxEdge.Y;
  93         s16 min_y = a.MinEdge.Y;
  94
  95         for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
  96         for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
  97         {
  98                 v3s16 p_overtop(x, max_y+1, z);
  99                 bool overtop_has_sunlight = false;
 100                 // If overtop node does not exist, trust heuristics
 101                 if(!v.exists(p_overtop))
 102                         overtop_has_sunlight = inexistent_top_provides_sunlight;
 103                 else if(v.getNodeRefUnsafe(p_overtop).getContent() == CONTENT_IGNORE)
 104                         overtop_has_sunlight = inexistent_top_provides_sunlight;
 105                 // Otherwise refer to it's light value
 106                 else
 107                         overtop_has_sunlight = (v.getNodeRefUnsafe(p_overtop).getLight(
 108                                         LIGHTBANK_DAY, ndef) == LIGHT_SUN);
 109
 110                 // Copy overtop's sunlight all over the place
 111                 u8 incoming_light = overtop_has_sunlight ? LIGHT_SUN : 0;
 112                 for(s32 y=max_y; y>=min_y; y--)
 113                 {
 114                         v3s16 p(x,y,z);
 115                         MapNode &n = v.getNodeRefUnsafe(p);
 116                         if(incoming_light == 0){
 117                                 // Do nothing
 118                         } else if(incoming_light == LIGHT_SUN &&
 119                                         ndef->get(n).sunlight_propagates){
 120                                 // Do nothing
 121                         } else if(ndef->get(n).sunlight_propagates == false){
 122                                 incoming_light = 0;
 123                         } else {
 124                                 incoming_light = diminish_light(incoming_light);
 125                         }
 126                         u8 old_light = n.getLight(LIGHTBANK_DAY, ndef);
 127
 128                         if(incoming_light > old_light)
 129                                 n.setLight(LIGHTBANK_DAY, incoming_light, ndef);
 130
 131                         if(diminish_light(incoming_light) != 0)
 132                                 light_sources.insert(p);
 133                 }
 134
 135                 // Check validity of sunlight at top of block below if it
 136                 // hasn't already been proven invalid
 137                 if(bottom_sunlight_valid)
 138                 {
 139                         bool sunlight_should_continue_down = (incoming_light == LIGHT_SUN);
 140                         v3s16 p_overbottom(x, min_y-1, z);
 141                         if(!v.exists(p_overbottom) ||
 142                                         v.getNodeRefUnsafe(p_overbottom
 143                                                         ).getContent() == CONTENT_IGNORE){
 144                                 // Is not known, cannot compare
 145                         } else {
 146                                 bool overbottom_has_sunlight = (v.getNodeRefUnsafe(p_overbottom
 147                                                 ).getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN);
 148                                 if(sunlight_should_continue_down != overbottom_has_sunlight){
 149                                         bottom_sunlight_valid = false;
 150                                 }
 151                         }
 152                 }
 153         }
 154
 155         return SunlightPropagateResult(bottom_sunlight_valid);
 156 }
 157
 158 /*!
 159  * A direction.
 160  * 0=X+
 161  * 1=Y+
 162  * 2=Z+
 163  * 3=Z-
 164  * 4=Y-
 165  * 5=X-
 166  * 6=no direction
 167  * Two directions are opposite only if their sum is 5.
 168  */
 169 typedef u8 direction;
 170 /*!
 171  * Relative node position.
 172  * This represents a node's position in its map block.
 173  * All coordinates must be between 0 and 15.
 174  */
 175 typedef v3s16 relative_v3;
 176 /*!
 177  * Position of a map block (block coordinates).
 178  * One block_pos unit is as long as 16 node position units.
 179  */
 180 typedef v3s16 mapblock_v3;
 181
 182 //! Contains information about a node whose light is about to change.
 183 struct ChangingLight {
 184         //! Relative position of the node in its map block.
 185         relative_v3 rel_position;
 186         //! Position of the node's block.
 187         mapblock_v3 block_position;
 188         //! Pointer to the node's block.
 189         MapBlock *block;
 190         /*!
 191          * Direction from the node that caused this node's changing
 192          * to this node.
 193          */
 194         direction source_direction;
 195
 196         ChangingLight() :
 197                 rel_position(),
 198                 block_position(),
 199                 block(NULL),
 200                 source_direction(6)
 201         {}
 202
 203         ChangingLight(relative_v3 rel_pos, mapblock_v3 block_pos,
 204                 MapBlock *b, direction source_dir) :
 205                 rel_position(rel_pos),
 206                 block_position(block_pos),
 207                 block(b),
 208                 source_direction(source_dir)
 209         {}
 210 };
 211
 212 /*!
 213  * A fast, priority queue-like container to contain ChangingLights.
 214  * The ChangingLights are ordered by the given light levels.
 215  * The brightest ChangingLight is returned first.
 216  */
 217 struct LightQueue {
 218         //! For each light level there is a vector.
 219         std::vector<ChangingLight> lights[LIGHT_SUN + 1];
 220         //! Light of the brightest ChangingLight in the queue.
 221         u8 max_light;
 222
 223         /*!
 224          * Creates a LightQueue.
 225          * \param reserve for each light level that many slots are reserved.
 226          */
 227         LightQueue(size_t reserve)
 228         {
 229                 max_light = LIGHT_SUN;
 230                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
 231                         lights[i].reserve(reserve);
 232                 }
 233         }
 234
 235         /*!
 236          * Returns the next brightest ChangingLight and
 237          * removes it from the queue.
 238          * If there were no elements in the queue, the given parameters
 239          * remain unmodified.
 240          * \param light light level of the popped ChangingLight
 241          * \param data the ChangingLight that was popped
 242          * \returns true if there was a ChangingLight in the queue.
 243          */
 244         bool next(u8 &light, ChangingLight &data)
 245         {
 246                 while (lights[max_light].empty()) {
 247                         if (max_light == 0) {
 248                                 return false;
 249                         }
 250                         max_light--;
 251                 }
 252                 light = max_light;
 253                 data = lights[max_light].back();
 254                 lights[max_light].pop_back();
 255                 return true;
 256         }
 257
 258         /*!
 259          * Adds an element to the queue.
 260          * The parameters are the same as in ChangingLight's constructor.
 261          * \param light light level of the ChangingLight
 262          */
 263         inline void push(u8 light, const relative_v3 &rel_pos,
 264                 const mapblock_v3 &block_pos, MapBlock *block,
 265                 direction source_dir)
 266         {
 267                 assert(light <= LIGHT_SUN);
 268                 lights[light].push_back(
 269                         ChangingLight(rel_pos, block_pos, block, source_dir));
 270         }
 271 };
 272
 273 /*!
 274  * This type of light queue is for unlighting.
 275  * A node can be pushed in it only if its raw light is zero.
 276  * This prevents pushing nodes twice into this queue.
 277  * The light of the pushed ChangingLight must be the
 278  * light of the node before unlighting it.
 279  */
 280 typedef LightQueue UnlightQueue;
 281 /*!
 282  * This type of light queue is for spreading lights.
 283  * While spreading lights, all the nodes in it must
 284  * have the same light as the light level the ChangingLights
 285  * were pushed into this queue with. This prevents unnecessary
 286  * re-pushing of the nodes into the queue.
 287  * If a node doesn't let light trough but emits light, it can be added
 288  * too.
 289  */
 290 typedef LightQueue ReLightQueue;
 291
 292 /*!
 293  * neighbor_dirs[i] points towards
 294  * the direction i.
 295  * See the definition of the type "direction"
 296  */
 297 const static v3s16 neighbor_dirs[6] = {
 298         v3s16(1, 0, 0), // right
 299         v3s16(0, 1, 0), // top
 300         v3s16(0, 0, 1), // back
 301         v3s16(0, 0, -1), // front
 302         v3s16(0, -1, 0), // bottom
 303         v3s16(-1, 0, 0), // left
 304 };
 305
 306 /*!
 307  * Transforms the given map block offset by one node towards
 308  * the specified direction.
 309  * \param dir the direction of the transformation
 310  * \param rel_pos the node's relative position in its map block
 311  * \param block_pos position of the node's block
 312  */
 313 bool step_rel_block_pos(direction dir, relative_v3 &rel_pos,
 314         mapblock_v3 &block_pos)
 315 {
 316         switch (dir) {
 317         case 0:
 318                 if (rel_pos.X < MAP_BLOCKSIZE - 1) {
 319                         rel_pos.X++;
 320                 } else {
 321                         rel_pos.X = 0;
 322                         block_pos.X++;
 323                         return true;
 324                 }
 325                 break;
 326         case 1:
 327                 if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
 328                         rel_pos.Y++;
 329                 } else {
 330                         rel_pos.Y = 0;
 331                         block_pos.Y++;
 332                         return true;
 333                 }
 334                 break;
 335         case 2:
 336                 if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
 337                         rel_pos.Z++;
 338                 } else {
 339                         rel_pos.Z = 0;
 340                         block_pos.Z++;
 341                         return true;
 342                 }
 343                 break;
 344         case 3:
 345                 if (rel_pos.Z > 0) {
 346                         rel_pos.Z--;
 347                 } else {
 348                         rel_pos.Z = MAP_BLOCKSIZE - 1;
 349                         block_pos.Z--;
 350                         return true;
 351                 }
 352                 break;
 353         case 4:
 354                 if (rel_pos.Y > 0) {
 355                         rel_pos.Y--;
 356                 } else {
 357                         rel_pos.Y = MAP_BLOCKSIZE - 1;
 358                         block_pos.Y--;
 359                         return true;
 360                 }
 361                 break;
 362         case 5:
 363                 if (rel_pos.X > 0) {
 364                         rel_pos.X--;
 365                 } else {
 366                         rel_pos.X = MAP_BLOCKSIZE - 1;
 367                         block_pos.X--;
 368                         return true;
 369                 }
 370                 break;
 371         }
 372         return false;
 373 }
 374
 375 /*
 376  * Removes all light that is potentially emitted by the specified
 377  * light sources. These nodes will have zero light.
 378  * Returns all nodes whose light became zero but should be re-lighted.
 379  *
 380  * \param bank the light bank in which the procedure operates
 381  * \param from_nodes nodes whose light is removed
 382  * \param light_sources nodes that should be re-lighted
 383  * \param modified_blocks output, all modified map blocks are added to this
 384  */
 385 void unspread_light(Map *map, INodeDefManager *nodemgr, LightBank bank,
 386         UnlightQueue &from_nodes, ReLightQueue &light_sources,
 387         std::map<v3s16, MapBlock*> &modified_blocks)
 388 {
 389         // Stores data popped from from_nodes
 390         u8 current_light;
 391         ChangingLight current;
 392         // Data of the current neighbor
 393         mapblock_v3 neighbor_block_pos;
 394         relative_v3 neighbor_rel_pos;
 395         // A dummy boolean
 396         bool is_valid_position;
 397         // Direction of the brightest neighbor of the node
 398         direction source_dir;
 399         while (from_nodes.next(current_light, current)) {
 400                 // For all nodes that need unlighting
 401
 402                 // There is no brightest neighbor
 403                 source_dir = 6;
 404                 // The current node
 405                 const MapNode &node = current.block->getNodeNoCheck(
 406                         current.rel_position, &is_valid_position);
 407                 const ContentFeatures &f = nodemgr->get(node);
 408                 // If the node emits light, it behaves like it had a
 409                 // brighter neighbor.
 410                 u8 brightest_neighbor_light = f.light_source + 1;
 411                 for (direction i = 0; i < 6; i++) {
 412                         //For each neighbor
 413
 414                         // The node that changed this node has already zero light
 415                         // and it can't give light to this node
 416                         if (current.source_direction + i == 5) {
 417                                 continue;
 418                         }
 419                         // Get the neighbor's position and block
 420                         neighbor_rel_pos = current.rel_position;
 421                         neighbor_block_pos = current.block_position;
 422                         MapBlock *neighbor_block;
 423                         if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
 424                                 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
 425                                 if (neighbor_block == NULL) {
 426                                         current.block->setLightingComplete(bank, i, false);
 427                                         continue;
 428                                 }
 429                         } else {
 430                                 neighbor_block = current.block;
 431                         }
 432                         // Get the neighbor itself
 433                         MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
 434                                 &is_valid_position);
 435                         const ContentFeatures &neighbor_f = nodemgr->get(
 436                                 neighbor.getContent());
 437                         u8 neighbor_light = neighbor.getLightRaw(bank, neighbor_f);
 438                         // If the neighbor has at least as much light as this node, then
 439                         // it won't lose its light, since it should have been added to
 440                         // from_nodes earlier, so its light would be zero.
 441                         if (neighbor_f.light_propagates && neighbor_light < current_light) {
 442                                 // Unlight, but only if the node has light.
 443                                 if (neighbor_light > 0) {
 444                                         neighbor.setLight(bank, 0, neighbor_f);
 445                                         neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
 446                                         from_nodes.push(neighbor_light, neighbor_rel_pos,
 447                                                 neighbor_block_pos, neighbor_block, i);
 448                                         // The current node was modified earlier, so its block
 449                                         // is in modified_blocks.
 450                                         if (current.block != neighbor_block) {
 451                                                 modified_blocks[neighbor_block_pos] = neighbor_block;
 452                                         }
 453                                 }
 454                         } else {
 455                                 // The neighbor can light up this node.
 456                                 if (neighbor_light < neighbor_f.light_source) {
 457                                         neighbor_light = neighbor_f.light_source;
 458                                 }
 459                                 if (brightest_neighbor_light < neighbor_light) {
 460                                         brightest_neighbor_light = neighbor_light;
 461                                         source_dir = i;
 462                                 }
 463                         }
 464                 }
 465                 // If the brightest neighbor is able to light up this node,
 466                 // then add this node to the output nodes.
 467                 if (brightest_neighbor_light > 1 && f.light_propagates) {
 468                         brightest_neighbor_light--;
 469                         light_sources.push(brightest_neighbor_light, current.rel_position,
 470                                 current.block_position, current.block,
 471                                 (source_dir == 6) ? 6 : 5 - source_dir
 472                                 /* with opposite direction*/);
 473                 }
 474         }
 475 }
 476
 477 /*
 478  * Spreads light from the specified starting nodes.
 479  *
 480  * Before calling this procedure, make sure that all ChangingLights
 481  * in light_sources have as much light on the map as they have in
 482  * light_sources (if the queue contains a node multiple times, the brightest
 483  * occurrence counts).
 484  *
 485  * \param bank the light bank in which the procedure operates
 486  * \param light_sources starting nodes
 487  * \param modified_blocks output, all modified map blocks are added to this
 488  */
 489 void spread_light(Map *map, INodeDefManager *nodemgr, LightBank bank,
 490         LightQueue &light_sources,
 491         std::map<v3s16, MapBlock*> &modified_blocks)
 492 {
 493         // The light the current node can provide to its neighbors.
 494         u8 spreading_light;
 495         // The ChangingLight for the current node.
 496         ChangingLight current;
 497         // Position of the current neighbor.
 498         mapblock_v3 neighbor_block_pos;
 499         relative_v3 neighbor_rel_pos;
 500         // A dummy boolean.
 501         bool is_valid_position;
 502         while (light_sources.next(spreading_light, current)) {
 503                 spreading_light--;
 504                 for (direction i = 0; i < 6; i++) {
 505                         // This node can't light up its light source
 506                         if (current.source_direction + i == 5) {
 507                                 continue;
 508                         }
 509                         // Get the neighbor's position and block
 510                         neighbor_rel_pos = current.rel_position;
 511                         neighbor_block_pos = current.block_position;
 512                         MapBlock *neighbor_block;
 513                         if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
 514                                 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
 515                                 if (neighbor_block == NULL) {
 516                                         current.block->setLightingComplete(bank, i, false);
 517                                         continue;
 518                                 }
 519                         } else {
 520                                 neighbor_block = current.block;
 521                         }
 522                         // Get the neighbor itself
 523                         MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
 524                                 &is_valid_position);
 525                         const ContentFeatures &f = nodemgr->get(neighbor.getContent());
 526                         if (f.light_propagates) {
 527                                 // Light up the neighbor, if it has less light than it should.
 528                                 u8 neighbor_light = neighbor.getLightRaw(bank, f);
 529                                 if (neighbor_light < spreading_light) {
 530                                         neighbor.setLight(bank, spreading_light, f);
 531                                         neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
 532                                         light_sources.push(spreading_light, neighbor_rel_pos,
 533                                                 neighbor_block_pos, neighbor_block, i);
 534                                         // The current node was modified earlier, so its block
 535                                         // is in modified_blocks.
 536                                         if (current.block != neighbor_block) {
 537                                                 modified_blocks[neighbor_block_pos] = neighbor_block;
 538                                         }
 539                                 }
 540                         }
 541                 }
 542         }
 543 }
 544
 545 /*!
 546  * Returns true if the node gets sunlight from the
 547  * node above it.
 548  *
 549  * \param pos position of the node.
 550  */
 551 bool is_sunlight_above(Map *map, v3s16 pos, INodeDefManager *ndef)
 552 {
 553         bool sunlight = true;
 554         mapblock_v3 source_block_pos;
 555         relative_v3 source_rel_pos;
 556         getNodeBlockPosWithOffset(pos + v3s16(0, 1, 0), source_block_pos,
 557                 source_rel_pos);
 558         // If the node above has sunlight, this node also can get it.
 559         MapBlock *source_block = map->getBlockNoCreateNoEx(source_block_pos);
 560         if (source_block == NULL) {
 561                 // But if there is no node above, then use heuristics
 562                 MapBlock *node_block = map->getBlockNoCreateNoEx(getNodeBlockPos(pos));
 563                 if (node_block == NULL) {
 564                         sunlight = false;
 565                 } else {
 566                         sunlight = !node_block->getIsUnderground();
 567                 }
 568         } else {
 569                 bool is_valid_position;
 570                 MapNode above = source_block->getNodeNoCheck(source_rel_pos,
 571                         &is_valid_position);
 572                 if (is_valid_position) {
 573                         if (above.getContent() == CONTENT_IGNORE) {
 574                                 // Trust heuristics
 575                                 if (source_block->getIsUnderground()) {
 576                                         sunlight = false;
 577                                 }
 578                         } else if (above.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
 579                                 // If the node above doesn't have sunlight, this
 580                                 // node is in shadow.
 581                                 sunlight = false;
 582                         }
 583                 }
 584         }
 585         return sunlight;
 586 }
 587
 588 static const LightBank banks[] = { LIGHTBANK_DAY, LIGHTBANK_NIGHT };
 589
 590 void update_lighting_nodes(Map *map,
 591         std::vector<std::pair<v3s16, MapNode> > &oldnodes,
 592         std::map<v3s16, MapBlock*> &modified_blocks)
 593 {
 594         INodeDefManager *ndef = map->getNodeDefManager();
 595         // For node getter functions
 596         bool is_valid_position;
 597
 598         // Process each light bank separately
 599         for (s32 i = 0; i < 2; i++) {
 600                 LightBank bank = banks[i];
 601                 UnlightQueue disappearing_lights(256);
 602                 ReLightQueue light_sources(256);
 603                 // Nodes that are brighter than the brightest modified node was
 604                 // won't change, since they didn't get their light from a
 605                 // modified node.
 606                 u8 min_safe_light = 0;
 607                 for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
 608                                 oldnodes.begin(); it < oldnodes.end(); ++it) {
 609                         u8 old_light = it->second.getLight(bank, ndef);
 610                         if (old_light > min_safe_light) {
 611                                 min_safe_light = old_light;
 612                         }
 613                 }
 614                 // If only one node changed, even nodes with the same brightness
 615                 // didn't get their light from the changed node.
 616                 if (oldnodes.size() > 1) {
 617                         min_safe_light++;
 618                 }
 619                 // For each changed node process sunlight and initialize
 620                 for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
 621                                 oldnodes.begin(); it < oldnodes.end(); ++it) {
 622                         // Get position and block of the changed node
 623                         v3s16 p = it->first;
 624                         relative_v3 rel_pos;
 625                         mapblock_v3 block_pos;
 626                         getNodeBlockPosWithOffset(p, block_pos, rel_pos);
 627                         MapBlock *block = map->getBlockNoCreateNoEx(block_pos);
 628                         if (block == NULL || block->isDummy()) {
 629                                 continue;
 630                         }
 631                         // Get the new node
 632                         MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
 633                         if (!is_valid_position) {
 634                                 break;
 635                         }
 636
 637                         // Light of the old node
 638                         u8 old_light = it->second.getLight(bank, ndef);
 639
 640                         // Add the block of the added node to modified_blocks
 641                         modified_blocks[block_pos] = block;
 642
 643                         // Get new light level of the node
 644                         u8 new_light = 0;
 645                         if (ndef->get(n).light_propagates) {
 646                                 if (bank == LIGHTBANK_DAY && ndef->get(n).sunlight_propagates
 647                                         && is_sunlight_above(map, p, ndef)) {
 648                                         new_light = LIGHT_SUN;
 649                                 } else {
 650                                         new_light = ndef->get(n).light_source;
 651                                         for (int i = 0; i < 6; i++) {
 652                                                 v3s16 p2 = p + neighbor_dirs[i];
 653                                                 bool is_valid;
 654                                                 MapNode n2 = map->getNodeNoEx(p2, &is_valid);
 655                                                 if (is_valid) {
 656                                                         u8 spread = n2.getLight(bank, ndef);
 657                                                         // If it is sure that the neighbor won't be
 658                                                         // unlighted, its light can spread to this node.
 659                                                         if (spread > new_light && spread >= min_safe_light) {
 660                                                                 new_light = spread - 1;
 661                                                         }
 662                                                 }
 663                                         }
 664                                 }
 665                         } else {
 666                                 // If this is an opaque node, it still can emit light.
 667                                 new_light = ndef->get(n).light_source;
 668                         }
 669
 670                         if (new_light > 0) {
 671                                 light_sources.push(new_light, rel_pos, block_pos, block, 6);
 672                         }
 673
 674                         if (new_light < old_light) {
 675                                 // The node became opaque or doesn't provide as much
 676                                 // light as the previous one, so it must be unlighted.
 677
 678                                 // Add to unlight queue
 679                                 n.setLight(bank, 0, ndef);
 680                                 block->setNodeNoCheck(rel_pos, n);
 681                                 disappearing_lights.push(old_light, rel_pos, block_pos, block,
 682                                         6);
 683
 684                                 // Remove sunlight, if there was any
 685                                 if (bank == LIGHTBANK_DAY && old_light == LIGHT_SUN) {
 686                                         for (s16 y = p.Y - 1;; y--) {
 687                                                 v3s16 n2pos(p.X, y, p.Z);
 688
 689                                                 MapNode n2;
 690
 691                                                 n2 = map->getNodeNoEx(n2pos, &is_valid_position);
 692                                                 if (!is_valid_position)
 693                                                         break;
 694
 695                                                 // If this node doesn't have sunlight, the nodes below
 696                                                 // it don't have too.
 697                                                 if (n2.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
 698                                                         break;
 699                                                 }
 700                                                 // Remove sunlight and add to unlight queue.
 701                                                 n2.setLight(LIGHTBANK_DAY, 0, ndef);
 702                                                 map->setNode(n2pos, n2);
 703                                                 relative_v3 rel_pos2;
 704                                                 mapblock_v3 block_pos2;
 705                                                 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
 706                                                 MapBlock *block2 = map->getBlockNoCreateNoEx(
 707                                                         block_pos2);
 708                                                 disappearing_lights.push(LIGHT_SUN, rel_pos2,
 709                                                         block_pos2, block2,
 710                                                         4 /* The node above caused the change */);
 711                                         }
 712                                 }
 713                         } else if (new_light > old_light) {
 714                                 // It is sure that the node provides more light than the previous
 715                                 // one, unlighting is not necessary.
 716                                 // Propagate sunlight
 717                                 if (bank == LIGHTBANK_DAY && new_light == LIGHT_SUN) {
 718                                         for (s16 y = p.Y - 1;; y--) {
 719                                                 v3s16 n2pos(p.X, y, p.Z);
 720
 721                                                 MapNode n2;
 722
 723                                                 n2 = map->getNodeNoEx(n2pos, &is_valid_position);
 724                                                 if (!is_valid_position)
 725                                                         break;
 726
 727                                                 // This should not happen, but if the node has sunlight
 728                                                 // then the iteration should stop.
 729                                                 if (n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN) {
 730                                                         break;
 731                                                 }
 732                                                 // If the node terminates sunlight, stop.
 733                                                 if (!ndef->get(n2).sunlight_propagates) {
 734                                                         break;
 735                                                 }
 736                                                 relative_v3 rel_pos2;
 737                                                 mapblock_v3 block_pos2;
 738                                                 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
 739                                                 MapBlock *block2 = map->getBlockNoCreateNoEx(
 740                                                         block_pos2);
 741                                                 // Mark node for lighting.
 742                                                 light_sources.push(LIGHT_SUN, rel_pos2, block_pos2,
 743                                                         block2, 4);
 744                                         }
 745                                 }
 746                         }
 747
 748                 }
 749                 // Remove lights
 750                 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
 751                         modified_blocks);
 752                 // Initialize light values for light spreading.
 753                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
 754                         const std::vector<ChangingLight> &lights = light_sources.lights[i];
 755                         for (std::vector<ChangingLight>::const_iterator it = lights.begin();
 756                                         it < lights.end(); it++) {
 757                                 MapNode n = it->block->getNodeNoCheck(it->rel_position,
 758                                         &is_valid_position);
 759                                 n.setLight(bank, i, ndef);
 760                                 it->block->setNodeNoCheck(it->rel_position, n);
 761                         }
 762                 }
 763                 // Spread lights.
 764                 spread_light(map, ndef, bank, light_sources, modified_blocks);
 765         }
 766 }
 767
 768 /*!
 769  * Borders of a map block in relative node coordinates.
 770  * Compatible with type 'direction'.
 771  */
 772 const VoxelArea block_borders[] = {
 773         VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
 774         VoxelArea(v3s16(0, 15, 0), v3s16(15, 15, 15)), //Y+
 775         VoxelArea(v3s16(0, 0, 15), v3s16(15, 15, 15)), //Z+
 776         VoxelArea(v3s16(0, 0, 0), v3s16(15, 15, 0)),   //Z-
 777         VoxelArea(v3s16(0, 0, 0), v3s16(15, 0, 15)),   //Y-
 778         VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
 779 };
 780
 781 /*!
 782  * Returns true if:
 783  * -the node has unloaded neighbors
 784  * -the node doesn't have light
 785  * -the node's light is the same as the maximum of
 786  * its light source and its brightest neighbor minus one.
 787  * .
 788  */
 789 bool is_light_locally_correct(Map *map, INodeDefManager *ndef, LightBank bank,
 790         v3s16 pos)
 791 {
 792         bool is_valid_position;
 793         MapNode n = map->getNodeNoEx(pos, &is_valid_position);
 794         const ContentFeatures &f = ndef->get(n);
 795         if (f.param_type != CPT_LIGHT) {
 796                 return true;
 797         }
 798         u8 light = n.getLightNoChecks(bank, &f);
 799         assert(f.light_source <= LIGHT_MAX);
 800         u8 brightest_neighbor = f.light_source + 1;
 801         for (direction d = 0; d < 6; ++d) {
 802                 MapNode n2 = map->getNodeNoEx(pos + neighbor_dirs[d],
 803                         &is_valid_position);
 804                 u8 light2 = n2.getLight(bank, ndef);
 805                 if (brightest_neighbor < light2) {
 806                         brightest_neighbor = light2;
 807                 }
 808         }
 809         assert(light <= LIGHT_SUN);
 810         return brightest_neighbor == light + 1;
 811 }
 812
 813 void update_block_border_lighting(Map *map, MapBlock *block,
 814         std::map<v3s16, MapBlock*> &modified_blocks)
 815 {
 816         INodeDefManager *ndef = map->getNodeDefManager();
 817         bool is_valid_position;
 818         for (s32 i = 0; i < 2; i++) {
 819                 LightBank bank = banks[i];
 820                 UnlightQueue disappearing_lights(256);
 821                 ReLightQueue light_sources(256);
 822                 // Get incorrect lights
 823                 for (direction d = 0; d < 6; d++) {
 824                         // For each direction
 825                         // Get neighbor block
 826                         v3s16 otherpos = block->getPos() + neighbor_dirs[d];
 827                         MapBlock *other = map->getBlockNoCreateNoEx(otherpos);
 828                         if (other == NULL) {
 829                                 continue;
 830                         }
 831                         // Only update if lighting was not completed.
 832                         if (block->isLightingComplete(bank, d) &&
 833                                         other->isLightingComplete(bank, 5 - d))
 834                                 continue;
 835                         // Reset flags
 836                         block->setLightingComplete(bank, d, true);
 837                         other->setLightingComplete(bank, 5 - d, true);
 838                         // The two blocks and their connecting surfaces
 839                         MapBlock *blocks[] = {block, other};
 840                         VoxelArea areas[] = {block_borders[d], block_borders[5 - d]};
 841                         // For both blocks
 842                         for (u8 blocknum = 0; blocknum < 2; blocknum++) {
 843                                 MapBlock *b = blocks[blocknum];
 844                                 VoxelArea a = areas[blocknum];
 845                                 // For all nodes
 846                                 for (s32 x = a.MinEdge.X; x <= a.MaxEdge.X; x++)
 847                                 for (s32 z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++)
 848                                 for (s32 y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 849                                         MapNode n = b->getNodeNoCheck(x, y, z,
 850                                                 &is_valid_position);
 851                                         u8 light = n.getLight(bank, ndef);
 852                                         // Sunlight is fixed
 853                                         if (light < LIGHT_SUN) {
 854                                                 // Unlight if not correct
 855                                                 if (!is_light_locally_correct(map, ndef, bank,
 856                                                                 v3s16(x, y, z) + b->getPosRelative())) {
 857                                                         // Initialize for unlighting
 858                                                         n.setLight(bank, 0, ndef);
 859                                                         b->setNodeNoCheck(x, y, z, n);
 860                                                         modified_blocks[b->getPos()]=b;
 861                                                         disappearing_lights.push(light,
 862                                                                 relative_v3(x, y, z), b->getPos(), b,
 863                                                                 6);
 864                                                 }
 865                                         }
 866                                 }
 867                         }
 868                 }
 869                 // Remove lights
 870                 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
 871                         modified_blocks);
 872                 // Initialize light values for light spreading.
 873                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
 874                         const std::vector<ChangingLight> &lights = light_sources.lights[i];
 875                         for (std::vector<ChangingLight>::const_iterator it = lights.begin();
 876                                         it < lights.end(); it++) {
 877                                 MapNode n = it->block->getNodeNoCheck(it->rel_position,
 878                                         &is_valid_position);
 879                                 n.setLight(bank, i, ndef);
 880                                 it->block->setNodeNoCheck(it->rel_position, n);
 881                         }
 882                 }
 883                 // Spread lights.
 884                 spread_light(map, ndef, bank, light_sources, modified_blocks);
 885         }
 886 }
 887
 888 VoxelLineIterator::VoxelLineIterator(
 889         const v3f &start_position,
 890         const v3f &line_vector) :
 891         m_start_position(start_position),
 892         m_line_vector(line_vector),
 893         m_next_intersection_multi(10000.0f, 10000.0f, 10000.0f),
 894         m_intersection_multi_inc(10000.0f, 10000.0f, 10000.0f),
 895         m_step_directions(1.0f, 1.0f, 1.0f)
 896 {
 897         m_current_node_pos = floatToInt(m_start_position, 1);
 898
 899         if (m_line_vector.X > 0) {
 900                 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5) + 1.5
 901                         - m_start_position.X) / m_line_vector.X;
 902                 m_intersection_multi_inc.X = 1 / m_line_vector.X;
 903         } else if (m_line_vector.X < 0) {
 904                 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5)
 905                         - m_start_position.X + 0.5) / m_line_vector.X;
 906                 m_intersection_multi_inc.X = -1 / m_line_vector.X;
 907                 m_step_directions.X = -1;
 908         }
 909
 910         if (m_line_vector.Y > 0) {
 911                 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5) + 1.5
 912                         - m_start_position.Y) / m_line_vector.Y;
 913                 m_intersection_multi_inc.Y = 1 / m_line_vector.Y;
 914         } else if (m_line_vector.Y < 0) {
 915                 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5)
 916                         - m_start_position.Y + 0.5) / m_line_vector.Y;
 917                 m_intersection_multi_inc.Y = -1 / m_line_vector.Y;
 918                 m_step_directions.Y = -1;
 919         }
 920
 921         if (m_line_vector.Z > 0) {
 922                 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5) + 1.5
 923                         - m_start_position.Z) / m_line_vector.Z;
 924                 m_intersection_multi_inc.Z = 1 / m_line_vector.Z;
 925         } else if (m_line_vector.Z < 0) {
 926                 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5)
 927                         - m_start_position.Z + 0.5) / m_line_vector.Z;
 928                 m_intersection_multi_inc.Z = -1 / m_line_vector.Z;
 929                 m_step_directions.Z = -1;
 930         }
 931
 932         m_has_next = (m_next_intersection_multi.X <= 1)
 933                 || (m_next_intersection_multi.Y <= 1)
 934                 || (m_next_intersection_multi.Z <= 1);
 935 }
 936
 937 void VoxelLineIterator::next()
 938 {
 939         if ((m_next_intersection_multi.X < m_next_intersection_multi.Y)
 940                         && (m_next_intersection_multi.X < m_next_intersection_multi.Z)) {
 941                 m_next_intersection_multi.X += m_intersection_multi_inc.X;
 942                 m_current_node_pos.X += m_step_directions.X;
 943         } else if ((m_next_intersection_multi.Y < m_next_intersection_multi.Z)) {
 944                 m_next_intersection_multi.Y += m_intersection_multi_inc.Y;
 945                 m_current_node_pos.Y += m_step_directions.Y;
 946         } else {
 947                 m_next_intersection_multi.Z += m_intersection_multi_inc.Z;
 948                 m_current_node_pos.Z += m_step_directions.Z;
 949         }
 950
 951         m_has_next = (m_next_intersection_multi.X <= 1)
 952                         || (m_next_intersection_multi.Y <= 1)
 953                         || (m_next_intersection_multi.Z <= 1);
 954 }
 955
 956 } // namespace voxalgo
 957