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 /*!
  29  * A direction.
  30  * 0=X+
  31  * 1=Y+
  32  * 2=Z+
  33  * 3=Z-
  34  * 4=Y-
  35  * 5=X-
  36  * 6=no direction
  37  * Two directions are opposite only if their sum is 5.
  38  */
  39 typedef u8 direction;
  40 /*!
  41  * Relative node position.
  42  * This represents a node's position in its map block.
  43  * All coordinates must be between 0 and 15.
  44  */
  45 typedef v3s16 relative_v3;
  46 /*!
  47  * Position of a map block (block coordinates).
  48  * One block_pos unit is as long as 16 node position units.
  49  */
  50 typedef v3s16 mapblock_v3;
  51
  52 //! Contains information about a node whose light is about to change.
  53 struct ChangingLight {
  54         //! Relative position of the node in its map block.
  55         relative_v3 rel_position;
  56         //! Position of the node's block.
  57         mapblock_v3 block_position;
  58         //! Pointer to the node's block.
  59         MapBlock *block = NULL;
  60         /*!
  61          * Direction from the node that caused this node's changing
  62          * to this node.
  63          */
  64         direction source_direction = 6;
  65
  66         ChangingLight() = default;
  67
  68         ChangingLight(const relative_v3 &rel_pos, const mapblock_v3 &block_pos,
  69                 MapBlock *b, direction source_dir) :
  70                 rel_position(rel_pos),
  71                 block_position(block_pos),
  72                 block(b),
  73                 source_direction(source_dir)
  74         {}
  75 };
  76
  77 /*!
  78  * A fast, priority queue-like container to contain ChangingLights.
  79  * The ChangingLights are ordered by the given light levels.
  80  * The brightest ChangingLight is returned first.
  81  */
  82 struct LightQueue {
  83         //! For each light level there is a vector.
  84         std::vector<ChangingLight> lights[LIGHT_SUN + 1];
  85         //! Light of the brightest ChangingLight in the queue.
  86         u8 max_light;
  87
  88         /*!
  89          * Creates a LightQueue.
  90          * \param reserve for each light level that many slots are reserved.
  91          */
  92         LightQueue(size_t reserve)
  93         {
  94                 max_light = LIGHT_SUN;
  95                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
  96                         lights[i].reserve(reserve);
  97                 }
  98         }
  99
 100         /*!
 101          * Returns the next brightest ChangingLight and
 102          * removes it from the queue.
 103          * If there were no elements in the queue, the given parameters
 104          * remain unmodified.
 105          * \param light light level of the popped ChangingLight
 106          * \param data the ChangingLight that was popped
 107          * \returns true if there was a ChangingLight in the queue.
 108          */
 109         bool next(u8 &light, ChangingLight &data)
 110         {
 111                 while (lights[max_light].empty()) {
 112                         if (max_light == 0) {
 113                                 return false;
 114                         }
 115                         max_light--;
 116                 }
 117                 light = max_light;
 118                 data = lights[max_light].back();
 119                 lights[max_light].pop_back();
 120                 return true;
 121         }
 122
 123         /*!
 124          * Adds an element to the queue.
 125          * The parameters are the same as in ChangingLight's constructor.
 126          * \param light light level of the ChangingLight
 127          */
 128         inline void push(u8 light, const relative_v3 &rel_pos,
 129                 const mapblock_v3 &block_pos, MapBlock *block,
 130                 direction source_dir)
 131         {
 132                 assert(light <= LIGHT_SUN);
 133                 lights[light].emplace_back(rel_pos, block_pos, block, source_dir);
 134         }
 135 };
 136
 137 /*!
 138  * This type of light queue is for unlighting.
 139  * A node can be pushed in it only if its raw light is zero.
 140  * This prevents pushing nodes twice into this queue.
 141  * The light of the pushed ChangingLight must be the
 142  * light of the node before unlighting it.
 143  */
 144 typedef LightQueue UnlightQueue;
 145 /*!
 146  * This type of light queue is for spreading lights.
 147  * While spreading lights, all the nodes in it must
 148  * have the same light as the light level the ChangingLights
 149  * were pushed into this queue with. This prevents unnecessary
 150  * re-pushing of the nodes into the queue.
 151  * If a node doesn't let light trough but emits light, it can be added
 152  * too.
 153  */
 154 typedef LightQueue ReLightQueue;
 155
 156 /*!
 157  * neighbor_dirs[i] points towards
 158  * the direction i.
 159  * See the definition of the type "direction"
 160  */
 161 const static v3s16 neighbor_dirs[6] = {
 162         v3s16(1, 0, 0), // right
 163         v3s16(0, 1, 0), // top
 164         v3s16(0, 0, 1), // back
 165         v3s16(0, 0, -1), // front
 166         v3s16(0, -1, 0), // bottom
 167         v3s16(-1, 0, 0), // left
 168 };
 169
 170 /*!
 171  * Transforms the given map block offset by one node towards
 172  * the specified direction.
 173  * \param dir the direction of the transformation
 174  * \param rel_pos the node's relative position in its map block
 175  * \param block_pos position of the node's block
 176  */
 177 bool step_rel_block_pos(direction dir, relative_v3 &rel_pos,
 178         mapblock_v3 &block_pos)
 179 {
 180         switch (dir) {
 181         case 0:
 182                 if (rel_pos.X < MAP_BLOCKSIZE - 1) {
 183                         rel_pos.X++;
 184                 } else {
 185                         rel_pos.X = 0;
 186                         block_pos.X++;
 187                         return true;
 188                 }
 189                 break;
 190         case 1:
 191                 if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
 192                         rel_pos.Y++;
 193                 } else {
 194                         rel_pos.Y = 0;
 195                         block_pos.Y++;
 196                         return true;
 197                 }
 198                 break;
 199         case 2:
 200                 if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
 201                         rel_pos.Z++;
 202                 } else {
 203                         rel_pos.Z = 0;
 204                         block_pos.Z++;
 205                         return true;
 206                 }
 207                 break;
 208         case 3:
 209                 if (rel_pos.Z > 0) {
 210                         rel_pos.Z--;
 211                 } else {
 212                         rel_pos.Z = MAP_BLOCKSIZE - 1;
 213                         block_pos.Z--;
 214                         return true;
 215                 }
 216                 break;
 217         case 4:
 218                 if (rel_pos.Y > 0) {
 219                         rel_pos.Y--;
 220                 } else {
 221                         rel_pos.Y = MAP_BLOCKSIZE - 1;
 222                         block_pos.Y--;
 223                         return true;
 224                 }
 225                 break;
 226         case 5:
 227                 if (rel_pos.X > 0) {
 228                         rel_pos.X--;
 229                 } else {
 230                         rel_pos.X = MAP_BLOCKSIZE - 1;
 231                         block_pos.X--;
 232                         return true;
 233                 }
 234                 break;
 235         }
 236         return false;
 237 }
 238
 239 /*
 240  * Removes all light that is potentially emitted by the specified
 241  * light sources. These nodes will have zero light.
 242  * Returns all nodes whose light became zero but should be re-lighted.
 243  *
 244  * \param bank the light bank in which the procedure operates
 245  * \param from_nodes nodes whose light is removed
 246  * \param light_sources nodes that should be re-lighted
 247  * \param modified_blocks output, all modified map blocks are added to this
 248  */
 249 void unspread_light(Map *map, const NodeDefManager *nodemgr, LightBank bank,
 250         UnlightQueue &from_nodes, ReLightQueue &light_sources,
 251         std::map<v3s16, MapBlock*> &modified_blocks)
 252 {
 253         // Stores data popped from from_nodes
 254         u8 current_light;
 255         ChangingLight current;
 256         // Data of the current neighbor
 257         mapblock_v3 neighbor_block_pos;
 258         relative_v3 neighbor_rel_pos;
 259         // A dummy boolean
 260         bool is_valid_position;
 261         // Direction of the brightest neighbor of the node
 262         direction source_dir;
 263         while (from_nodes.next(current_light, current)) {
 264                 // For all nodes that need unlighting
 265
 266                 // There is no brightest neighbor
 267                 source_dir = 6;
 268                 // The current node
 269                 const MapNode &node = current.block->getNodeNoCheck(
 270                         current.rel_position, &is_valid_position);
 271                 const ContentFeatures &f = nodemgr->get(node);
 272                 // If the node emits light, it behaves like it had a
 273                 // brighter neighbor.
 274                 u8 brightest_neighbor_light = f.light_source + 1;
 275                 for (direction i = 0; i < 6; i++) {
 276                         //For each neighbor
 277
 278                         // The node that changed this node has already zero light
 279                         // and it can't give light to this node
 280                         if (current.source_direction + i == 5) {
 281                                 continue;
 282                         }
 283                         // Get the neighbor's position and block
 284                         neighbor_rel_pos = current.rel_position;
 285                         neighbor_block_pos = current.block_position;
 286                         MapBlock *neighbor_block;
 287                         if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
 288                                 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
 289                                 if (neighbor_block == NULL) {
 290                                         current.block->setLightingComplete(bank, i, false);
 291                                         continue;
 292                                 }
 293                         } else {
 294                                 neighbor_block = current.block;
 295                         }
 296                         // Get the neighbor itself
 297                         MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
 298                                 &is_valid_position);
 299                         const ContentFeatures &neighbor_f = nodemgr->get(
 300                                 neighbor.getContent());
 301                         u8 neighbor_light = neighbor.getLightRaw(bank, neighbor_f);
 302                         // If the neighbor has at least as much light as this node, then
 303                         // it won't lose its light, since it should have been added to
 304                         // from_nodes earlier, so its light would be zero.
 305                         if (neighbor_f.light_propagates && neighbor_light < current_light) {
 306                                 // Unlight, but only if the node has light.
 307                                 if (neighbor_light > 0) {
 308                                         neighbor.setLight(bank, 0, neighbor_f);
 309                                         neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
 310                                         from_nodes.push(neighbor_light, neighbor_rel_pos,
 311                                                 neighbor_block_pos, neighbor_block, i);
 312                                         // The current node was modified earlier, so its block
 313                                         // is in modified_blocks.
 314                                         if (current.block != neighbor_block) {
 315                                                 modified_blocks[neighbor_block_pos] = neighbor_block;
 316                                         }
 317                                 }
 318                         } else {
 319                                 // The neighbor can light up this node.
 320                                 if (neighbor_light < neighbor_f.light_source) {
 321                                         neighbor_light = neighbor_f.light_source;
 322                                 }
 323                                 if (brightest_neighbor_light < neighbor_light) {
 324                                         brightest_neighbor_light = neighbor_light;
 325                                         source_dir = i;
 326                                 }
 327                         }
 328                 }
 329                 // If the brightest neighbor is able to light up this node,
 330                 // then add this node to the output nodes.
 331                 if (brightest_neighbor_light > 1 && f.light_propagates) {
 332                         brightest_neighbor_light--;
 333                         light_sources.push(brightest_neighbor_light, current.rel_position,
 334                                 current.block_position, current.block,
 335                                 (source_dir == 6) ? 6 : 5 - source_dir
 336                                 /* with opposite direction*/);
 337                 }
 338         }
 339 }
 340
 341 /*
 342  * Spreads light from the specified starting nodes.
 343  *
 344  * Before calling this procedure, make sure that all ChangingLights
 345  * in light_sources have as much light on the map as they have in
 346  * light_sources (if the queue contains a node multiple times, the brightest
 347  * occurrence counts).
 348  *
 349  * \param bank the light bank in which the procedure operates
 350  * \param light_sources starting nodes
 351  * \param modified_blocks output, all modified map blocks are added to this
 352  */
 353 void spread_light(Map *map, const NodeDefManager *nodemgr, LightBank bank,
 354         LightQueue &light_sources,
 355         std::map<v3s16, MapBlock*> &modified_blocks)
 356 {
 357         // The light the current node can provide to its neighbors.
 358         u8 spreading_light;
 359         // The ChangingLight for the current node.
 360         ChangingLight current;
 361         // Position of the current neighbor.
 362         mapblock_v3 neighbor_block_pos;
 363         relative_v3 neighbor_rel_pos;
 364         // A dummy boolean.
 365         bool is_valid_position;
 366         while (light_sources.next(spreading_light, current)) {
 367                 spreading_light--;
 368                 for (direction i = 0; i < 6; i++) {
 369                         // This node can't light up its light source
 370                         if (current.source_direction + i == 5) {
 371                                 continue;
 372                         }
 373                         // Get the neighbor's position and block
 374                         neighbor_rel_pos = current.rel_position;
 375                         neighbor_block_pos = current.block_position;
 376                         MapBlock *neighbor_block;
 377                         if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
 378                                 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
 379                                 if (neighbor_block == NULL) {
 380                                         current.block->setLightingComplete(bank, i, false);
 381                                         continue;
 382                                 }
 383                         } else {
 384                                 neighbor_block = current.block;
 385                         }
 386                         // Get the neighbor itself
 387                         MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
 388                                 &is_valid_position);
 389                         const ContentFeatures &f = nodemgr->get(neighbor.getContent());
 390                         if (f.light_propagates) {
 391                                 // Light up the neighbor, if it has less light than it should.
 392                                 u8 neighbor_light = neighbor.getLightRaw(bank, f);
 393                                 if (neighbor_light < spreading_light) {
 394                                         neighbor.setLight(bank, spreading_light, f);
 395                                         neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
 396                                         light_sources.push(spreading_light, neighbor_rel_pos,
 397                                                 neighbor_block_pos, neighbor_block, i);
 398                                         // The current node was modified earlier, so its block
 399                                         // is in modified_blocks.
 400                                         if (current.block != neighbor_block) {
 401                                                 modified_blocks[neighbor_block_pos] = neighbor_block;
 402                                         }
 403                                 }
 404                         }
 405                 }
 406         }
 407 }
 408
 409 struct SunlightPropagationUnit{
 410         v2s16 relative_pos;
 411         bool is_sunlit;
 412
 413         SunlightPropagationUnit(v2s16 relpos, bool sunlit):
 414                 relative_pos(relpos),
 415                 is_sunlit(sunlit)
 416         {}
 417 };
 418
 419 struct SunlightPropagationData{
 420         std::vector<SunlightPropagationUnit> data;
 421         v3s16 target_block;
 422 };
 423
 424 /*!
 425  * Returns true if the node gets sunlight from the
 426  * node above it.
 427  *
 428  * \param pos position of the node.
 429  */
 430 bool is_sunlight_above(Map *map, v3s16 pos, const NodeDefManager *ndef)
 431 {
 432         bool sunlight = true;
 433         mapblock_v3 source_block_pos;
 434         relative_v3 source_rel_pos;
 435         getNodeBlockPosWithOffset(pos + v3s16(0, 1, 0), source_block_pos,
 436                 source_rel_pos);
 437         // If the node above has sunlight, this node also can get it.
 438         MapBlock *source_block = map->getBlockNoCreateNoEx(source_block_pos);
 439         if (source_block == NULL) {
 440                 // But if there is no node above, then use heuristics
 441                 MapBlock *node_block = map->getBlockNoCreateNoEx(getNodeBlockPos(pos));
 442                 if (node_block == NULL) {
 443                         sunlight = false;
 444                 } else {
 445                         sunlight = !node_block->getIsUnderground();
 446                 }
 447         } else {
 448                 bool is_valid_position;
 449                 MapNode above = source_block->getNodeNoCheck(source_rel_pos,
 450                         &is_valid_position);
 451                 if (is_valid_position) {
 452                         if (above.getContent() == CONTENT_IGNORE) {
 453                                 // Trust heuristics
 454                                 if (source_block->getIsUnderground()) {
 455                                         sunlight = false;
 456                                 }
 457                         } else if (above.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
 458                                 // If the node above doesn't have sunlight, this
 459                                 // node is in shadow.
 460                                 sunlight = false;
 461                         }
 462                 }
 463         }
 464         return sunlight;
 465 }
 466
 467 static const LightBank banks[] = { LIGHTBANK_DAY, LIGHTBANK_NIGHT };
 468
 469 void update_lighting_nodes(Map *map,
 470         std::vector<std::pair<v3s16, MapNode> > &oldnodes,
 471         std::map<v3s16, MapBlock*> &modified_blocks)
 472 {
 473         const NodeDefManager *ndef = map->getNodeDefManager();
 474         // For node getter functions
 475         bool is_valid_position;
 476
 477         // Process each light bank separately
 478         for (LightBank bank : banks) {
 479                 UnlightQueue disappearing_lights(256);
 480                 ReLightQueue light_sources(256);
 481                 // Nodes that are brighter than the brightest modified node was
 482                 // won't change, since they didn't get their light from a
 483                 // modified node.
 484                 u8 min_safe_light = 0;
 485                 for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
 486                                 oldnodes.begin(); it < oldnodes.end(); ++it) {
 487                         u8 old_light = it->second.getLight(bank, ndef);
 488                         if (old_light > min_safe_light) {
 489                                 min_safe_light = old_light;
 490                         }
 491                 }
 492                 // If only one node changed, even nodes with the same brightness
 493                 // didn't get their light from the changed node.
 494                 if (oldnodes.size() > 1) {
 495                         min_safe_light++;
 496                 }
 497                 // For each changed node process sunlight and initialize
 498                 for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
 499                                 oldnodes.begin(); it < oldnodes.end(); ++it) {
 500                         // Get position and block of the changed node
 501                         v3s16 p = it->first;
 502                         relative_v3 rel_pos;
 503                         mapblock_v3 block_pos;
 504                         getNodeBlockPosWithOffset(p, block_pos, rel_pos);
 505                         MapBlock *block = map->getBlockNoCreateNoEx(block_pos);
 506                         if (block == NULL || block->isDummy()) {
 507                                 continue;
 508                         }
 509                         // Get the new node
 510                         MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
 511                         if (!is_valid_position) {
 512                                 break;
 513                         }
 514
 515                         // Light of the old node
 516                         u8 old_light = it->second.getLight(bank, ndef);
 517
 518                         // Add the block of the added node to modified_blocks
 519                         modified_blocks[block_pos] = block;
 520
 521                         // Get new light level of the node
 522                         u8 new_light = 0;
 523                         if (ndef->get(n).light_propagates) {
 524                                 if (bank == LIGHTBANK_DAY && ndef->get(n).sunlight_propagates
 525                                         && is_sunlight_above(map, p, ndef)) {
 526                                         new_light = LIGHT_SUN;
 527                                 } else {
 528                                         new_light = ndef->get(n).light_source;
 529                                         for (const v3s16 &neighbor_dir : neighbor_dirs) {
 530                                                 v3s16 p2 = p + neighbor_dir;
 531                                                 bool is_valid;
 532                                                 MapNode n2 = map->getNode(p2, &is_valid);
 533                                                 if (is_valid) {
 534                                                         u8 spread = n2.getLight(bank, ndef);
 535                                                         // If it is sure that the neighbor won't be
 536                                                         // unlighted, its light can spread to this node.
 537                                                         if (spread > new_light && spread >= min_safe_light) {
 538                                                                 new_light = spread - 1;
 539                                                         }
 540                                                 }
 541                                         }
 542                                 }
 543                         } else {
 544                                 // If this is an opaque node, it still can emit light.
 545                                 new_light = ndef->get(n).light_source;
 546                         }
 547
 548                         if (new_light > 0) {
 549                                 light_sources.push(new_light, rel_pos, block_pos, block, 6);
 550                         }
 551
 552                         if (new_light < old_light) {
 553                                 // The node became opaque or doesn't provide as much
 554                                 // light as the previous one, so it must be unlighted.
 555
 556                                 // Add to unlight queue
 557                                 n.setLight(bank, 0, ndef);
 558                                 block->setNodeNoCheck(rel_pos, n);
 559                                 disappearing_lights.push(old_light, rel_pos, block_pos, block,
 560                                         6);
 561
 562                                 // Remove sunlight, if there was any
 563                                 if (bank == LIGHTBANK_DAY && old_light == LIGHT_SUN) {
 564                                         for (s16 y = p.Y - 1;; y--) {
 565                                                 v3s16 n2pos(p.X, y, p.Z);
 566
 567                                                 MapNode n2;
 568
 569                                                 n2 = map->getNode(n2pos, &is_valid_position);
 570                                                 if (!is_valid_position)
 571                                                         break;
 572
 573                                                 // If this node doesn't have sunlight, the nodes below
 574                                                 // it don't have too.
 575                                                 if (n2.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
 576                                                         break;
 577                                                 }
 578                                                 // Remove sunlight and add to unlight queue.
 579                                                 n2.setLight(LIGHTBANK_DAY, 0, ndef);
 580                                                 map->setNode(n2pos, n2);
 581                                                 relative_v3 rel_pos2;
 582                                                 mapblock_v3 block_pos2;
 583                                                 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
 584                                                 MapBlock *block2 = map->getBlockNoCreateNoEx(
 585                                                         block_pos2);
 586                                                 disappearing_lights.push(LIGHT_SUN, rel_pos2,
 587                                                         block_pos2, block2,
 588                                                         4 /* The node above caused the change */);
 589                                         }
 590                                 }
 591                         } else if (new_light > old_light) {
 592                                 // It is sure that the node provides more light than the previous
 593                                 // one, unlighting is not necessary.
 594                                 // Propagate sunlight
 595                                 if (bank == LIGHTBANK_DAY && new_light == LIGHT_SUN) {
 596                                         for (s16 y = p.Y - 1;; y--) {
 597                                                 v3s16 n2pos(p.X, y, p.Z);
 598
 599                                                 MapNode n2;
 600
 601                                                 n2 = map->getNode(n2pos, &is_valid_position);
 602                                                 if (!is_valid_position)
 603                                                         break;
 604
 605                                                 // This should not happen, but if the node has sunlight
 606                                                 // then the iteration should stop.
 607                                                 if (n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN) {
 608                                                         break;
 609                                                 }
 610                                                 // If the node terminates sunlight, stop.
 611                                                 if (!ndef->get(n2).sunlight_propagates) {
 612                                                         break;
 613                                                 }
 614                                                 relative_v3 rel_pos2;
 615                                                 mapblock_v3 block_pos2;
 616                                                 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
 617                                                 MapBlock *block2 = map->getBlockNoCreateNoEx(
 618                                                         block_pos2);
 619                                                 // Mark node for lighting.
 620                                                 light_sources.push(LIGHT_SUN, rel_pos2, block_pos2,
 621                                                         block2, 4);
 622                                         }
 623                                 }
 624                         }
 625
 626                 }
 627                 // Remove lights
 628                 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
 629                         modified_blocks);
 630                 // Initialize light values for light spreading.
 631                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
 632                         const std::vector<ChangingLight> &lights = light_sources.lights[i];
 633                         for (std::vector<ChangingLight>::const_iterator it = lights.begin();
 634                                         it < lights.end(); ++it) {
 635                                 MapNode n = it->block->getNodeNoCheck(it->rel_position,
 636                                         &is_valid_position);
 637                                 n.setLight(bank, i, ndef);
 638                                 it->block->setNodeNoCheck(it->rel_position, n);
 639                         }
 640                 }
 641                 // Spread lights.
 642                 spread_light(map, ndef, bank, light_sources, modified_blocks);
 643         }
 644 }
 645
 646 /*!
 647  * Borders of a map block in relative node coordinates.
 648  * Compatible with type 'direction'.
 649  */
 650 const VoxelArea block_borders[] = {
 651         VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
 652         VoxelArea(v3s16(0, 15, 0), v3s16(15, 15, 15)), //Y+
 653         VoxelArea(v3s16(0, 0, 15), v3s16(15, 15, 15)), //Z+
 654         VoxelArea(v3s16(0, 0, 0), v3s16(15, 15, 0)),   //Z-
 655         VoxelArea(v3s16(0, 0, 0), v3s16(15, 0, 15)),   //Y-
 656         VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
 657 };
 658
 659 /*!
 660  * Returns true if:
 661  * -the node has unloaded neighbors
 662  * -the node doesn't have light
 663  * -the node's light is the same as the maximum of
 664  * its light source and its brightest neighbor minus one.
 665  * .
 666  */
 667 bool is_light_locally_correct(Map *map, const NodeDefManager *ndef,
 668         LightBank bank, v3s16 pos)
 669 {
 670         bool is_valid_position;
 671         MapNode n = map->getNode(pos, &is_valid_position);
 672         const ContentFeatures &f = ndef->get(n);
 673         if (f.param_type != CPT_LIGHT) {
 674                 return true;
 675         }
 676         u8 light = n.getLightNoChecks(bank, &f);
 677         assert(f.light_source <= LIGHT_MAX);
 678         u8 brightest_neighbor = f.light_source + 1;
 679         for (const v3s16 &neighbor_dir : neighbor_dirs) {
 680                 MapNode n2 = map->getNode(pos + neighbor_dir,
 681                         &is_valid_position);
 682                 u8 light2 = n2.getLight(bank, ndef);
 683                 if (brightest_neighbor < light2) {
 684                         brightest_neighbor = light2;
 685                 }
 686         }
 687         assert(light <= LIGHT_SUN);
 688         return brightest_neighbor == light + 1;
 689 }
 690
 691 void update_block_border_lighting(Map *map, MapBlock *block,
 692         std::map<v3s16, MapBlock*> &modified_blocks)
 693 {
 694         const NodeDefManager *ndef = map->getNodeDefManager();
 695         bool is_valid_position;
 696         for (LightBank bank : banks) {
 697                 // Since invalid light is not common, do not allocate
 698                 // memory if not needed.
 699                 UnlightQueue disappearing_lights(0);
 700                 ReLightQueue light_sources(0);
 701                 // Get incorrect lights
 702                 for (direction d = 0; d < 6; d++) {
 703                         // For each direction
 704                         // Get neighbor block
 705                         v3s16 otherpos = block->getPos() + neighbor_dirs[d];
 706                         MapBlock *other = map->getBlockNoCreateNoEx(otherpos);
 707                         if (other == NULL) {
 708                                 continue;
 709                         }
 710                         // Only update if lighting was not completed.
 711                         if (block->isLightingComplete(bank, d) &&
 712                                         other->isLightingComplete(bank, 5 - d))
 713                                 continue;
 714                         // Reset flags
 715                         block->setLightingComplete(bank, d, true);
 716                         other->setLightingComplete(bank, 5 - d, true);
 717                         // The two blocks and their connecting surfaces
 718                         MapBlock *blocks[] = {block, other};
 719                         VoxelArea areas[] = {block_borders[d], block_borders[5 - d]};
 720                         // For both blocks
 721                         for (u8 blocknum = 0; blocknum < 2; blocknum++) {
 722                                 MapBlock *b = blocks[blocknum];
 723                                 VoxelArea a = areas[blocknum];
 724                                 // For all nodes
 725                                 for (s32 x = a.MinEdge.X; x <= a.MaxEdge.X; x++)
 726                                 for (s32 z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++)
 727                                 for (s32 y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 728                                         MapNode n = b->getNodeNoCheck(x, y, z,
 729                                                 &is_valid_position);
 730                                         u8 light = n.getLight(bank, ndef);
 731                                         // Sunlight is fixed
 732                                         if (light < LIGHT_SUN) {
 733                                                 // Unlight if not correct
 734                                                 if (!is_light_locally_correct(map, ndef, bank,
 735                                                                 v3s16(x, y, z) + b->getPosRelative())) {
 736                                                         // Initialize for unlighting
 737                                                         n.setLight(bank, 0, ndef);
 738                                                         b->setNodeNoCheck(x, y, z, n);
 739                                                         modified_blocks[b->getPos()]=b;
 740                                                         disappearing_lights.push(light,
 741                                                                 relative_v3(x, y, z), b->getPos(), b,
 742                                                                 6);
 743                                                 }
 744                                         }
 745                                 }
 746                         }
 747                 }
 748                 // Remove lights
 749                 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
 750                         modified_blocks);
 751                 // Initialize light values for light spreading.
 752                 for (u8 i = 0; i <= LIGHT_SUN; i++) {
 753                         const std::vector<ChangingLight> &lights = light_sources.lights[i];
 754                         for (std::vector<ChangingLight>::const_iterator it = lights.begin();
 755                                         it < lights.end(); ++it) {
 756                                 MapNode n = it->block->getNodeNoCheck(it->rel_position,
 757                                         &is_valid_position);
 758                                 n.setLight(bank, i, ndef);
 759                                 it->block->setNodeNoCheck(it->rel_position, n);
 760                         }
 761                 }
 762                 // Spread lights.
 763                 spread_light(map, ndef, bank, light_sources, modified_blocks);
 764         }
 765 }
 766
 767 /*!
 768  * Resets the lighting of the given VoxelManipulator to
 769  * complete darkness and full sunlight.
 770  * Operates in one map sector.
 771  *
 772  * \param offset contains the least x and z node coordinates
 773  * of the map sector.
 774  * \param light incoming sunlight, light[x][z] is true if there
 775  * is sunlight above the voxel manipulator at the given x-z coordinates.
 776  * The array's indices are relative node coordinates in the sector.
 777  * After the procedure returns, this contains outgoing light at
 778  * the bottom of the voxel manipulator.
 779  */
 780 void fill_with_sunlight(MMVManip *vm, const NodeDefManager *ndef, v2s16 offset,
 781         bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
 782 {
 783         // Distance in array between two nodes on top of each other.
 784         s16 ystride = vm->m_area.getExtent().X;
 785         // Cache the ignore node.
 786         MapNode ignore = MapNode(CONTENT_IGNORE);
 787         // For each column of nodes:
 788         for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
 789         for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
 790                 // Position of the column on the map.
 791                 v2s16 realpos = offset + v2s16(x, z);
 792                 // Array indices in the voxel manipulator
 793                 s32 maxindex = vm->m_area.index(realpos.X, vm->m_area.MaxEdge.Y,
 794                         realpos.Y);
 795                 s32 minindex = vm->m_area.index(realpos.X, vm->m_area.MinEdge.Y,
 796                         realpos.Y);
 797                 // True if the current node has sunlight.
 798                 bool lig = light[z][x];
 799                 // For each node, downwards:
 800                 for (s32 i = maxindex; i >= minindex; i -= ystride) {
 801                         MapNode *n;
 802                         if (vm->m_flags[i] & VOXELFLAG_NO_DATA)
 803                                 n = &ignore;
 804                         else
 805                                 n = &vm->m_data[i];
 806                         // Ignore IGNORE nodes, these are not generated yet.
 807                         if(n->getContent() == CONTENT_IGNORE)
 808                                 continue;
 809                         const ContentFeatures &f = ndef->get(n->getContent());
 810                         if (lig && !f.sunlight_propagates)
 811                                 // Sunlight is stopped.
 812                                 lig = false;
 813                         // Reset light
 814                         n->setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
 815                         n->setLight(LIGHTBANK_NIGHT, 0, f);
 816                 }
 817                 // Output outgoing light.
 818                 light[z][x] = lig;
 819         }
 820 }
 821
 822 /*!
 823  * Returns incoming sunlight for one map block.
 824  * If block above is not found, it is loaded.
 825  *
 826  * \param pos position of the map block that gets the sunlight.
 827  * \param light incoming sunlight, light[z][x] is true if there
 828  * is sunlight above the block at the given z-x relative
 829  * node coordinates.
 830  */
 831 void is_sunlight_above_block(ServerMap *map, mapblock_v3 pos,
 832         const NodeDefManager *ndef, bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
 833 {
 834         mapblock_v3 source_block_pos = pos + v3s16(0, 1, 0);
 835         // Get or load source block.
 836         // It might take a while to load, but correcting incorrect
 837         // sunlight may be even slower.
 838         MapBlock *source_block = map->emergeBlock(source_block_pos, false);
 839         // Trust only generated blocks.
 840         if (source_block == NULL || source_block->isDummy()
 841                         || !source_block->isGenerated()) {
 842                 // But if there is no block above, then use heuristics
 843                 bool sunlight = true;
 844                 MapBlock *node_block = map->getBlockNoCreateNoEx(pos);
 845                 if (node_block == NULL)
 846                         // This should not happen.
 847                         sunlight = false;
 848                 else
 849                         sunlight = !node_block->getIsUnderground();
 850                 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
 851                 for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
 852                         light[z][x] = sunlight;
 853         } else {
 854                 // Dummy boolean, the position is valid.
 855                 bool is_valid_position;
 856                 // For each column:
 857                 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
 858                 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
 859                         // Get the bottom block.
 860                         MapNode above = source_block->getNodeNoCheck(x, 0, z,
 861                                 &is_valid_position);
 862                         light[z][x] = above.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN;
 863                 }
 864         }
 865 }
 866
 867 /*!
 868  * Propagates sunlight down in a given map block.
 869  *
 870  * \param data contains incoming sunlight and shadow and
 871  * the coordinates of the target block.
 872  * \param unlight propagated shadow is inserted here
 873  * \param relight propagated sunlight is inserted here
 874  *
 875  * \returns true if the block was modified, false otherwise.
 876  */
 877 bool propagate_block_sunlight(Map *map, const NodeDefManager *ndef,
 878         SunlightPropagationData *data, UnlightQueue *unlight, ReLightQueue *relight)
 879 {
 880         bool modified = false;
 881         // Get the block.
 882         MapBlock *block = map->getBlockNoCreateNoEx(data->target_block);
 883         if (block == NULL || block->isDummy()) {
 884                 // The work is done if the block does not contain data.
 885                 data->data.clear();
 886                 return false;
 887         }
 888         // Dummy boolean
 889         bool is_valid;
 890         // For each changing column of nodes:
 891         size_t index;
 892         for (index = 0; index < data->data.size(); index++) {
 893                 SunlightPropagationUnit it = data->data[index];
 894                 // Relative position of the currently inspected node.
 895                 relative_v3 current_pos(it.relative_pos.X, MAP_BLOCKSIZE - 1,
 896                         it.relative_pos.Y);
 897                 if (it.is_sunlit) {
 898                         // Propagate sunlight.
 899                         // For each node downwards:
 900                         for (; current_pos.Y >= 0; current_pos.Y--) {
 901                                 MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
 902                                 const ContentFeatures &f = ndef->get(n);
 903                                 if (n.getLightRaw(LIGHTBANK_DAY, f) < LIGHT_SUN
 904                                                 && f.sunlight_propagates) {
 905                                         // This node gets sunlight.
 906                                         n.setLight(LIGHTBANK_DAY, LIGHT_SUN, f);
 907                                         block->setNodeNoCheck(current_pos, n);
 908                                         modified = true;
 909                                         relight->push(LIGHT_SUN, current_pos, data->target_block,
 910                                                 block, 4);
 911                                 } else {
 912                                         // Light already valid, propagation stopped.
 913                                         break;
 914                                 }
 915                         }
 916                 } else {
 917                         // Propagate shadow.
 918                         // For each node downwards:
 919                         for (; current_pos.Y >= 0; current_pos.Y--) {
 920                                 MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
 921                                 const ContentFeatures &f = ndef->get(n);
 922                                 if (n.getLightRaw(LIGHTBANK_DAY, f) == LIGHT_SUN) {
 923                                         // The sunlight is no longer valid.
 924                                         n.setLight(LIGHTBANK_DAY, 0, f);
 925                                         block->setNodeNoCheck(current_pos, n);
 926                                         modified = true;
 927                                         unlight->push(LIGHT_SUN, current_pos, data->target_block,
 928                                                 block, 4);
 929                                 } else {
 930                                         // Reached shadow, propagation stopped.
 931                                         break;
 932                                 }
 933                         }
 934                 }
 935                 if (current_pos.Y >= 0) {
 936                         // Propagation stopped, remove from data.
 937                         data->data[index] = data->data.back();
 938                         data->data.pop_back();
 939                         index--;
 940                 }
 941         }
 942         return modified;
 943 }
 944
 945 /*!
 946  * Borders of a map block in relative node coordinates.
 947  * The areas do not overlap.
 948  * Compatible with type 'direction'.
 949  */
 950 const VoxelArea block_pad[] = {
 951         VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
 952         VoxelArea(v3s16(1, 15, 0), v3s16(14, 15, 15)), //Y+
 953         VoxelArea(v3s16(1, 1, 15), v3s16(14, 14, 15)), //Z+
 954         VoxelArea(v3s16(1, 1, 0), v3s16(14, 14, 0)),   //Z-
 955         VoxelArea(v3s16(1, 0, 0), v3s16(14, 0, 15)),   //Y-
 956         VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
 957 };
 958
 959 /*!
 960  * The common part of bulk light updates - it is always executed.
 961  * The procedure takes the nodes that should be unlit, and the
 962  * full modified area.
 963  *
 964  * The procedure handles the correction of all lighting except
 965  * direct sunlight spreading.
 966  *
 967  * \param minblock least coordinates of the changed area in block
 968  * coordinates
 969  * \param maxblock greatest coordinates of the changed area in block
 970  * coordinates
 971  * \param unlight the first queue is for day light, the second is for
 972  * night light. Contains all nodes on the borders that need to be unlit.
 973  * \param relight the first queue is for day light, the second is for
 974  * night light. Contains nodes that were not modified, but got sunlight
 975  * because the changes.
 976  * \param modified_blocks the procedure adds all modified blocks to
 977  * this map
 978  */
 979 void finish_bulk_light_update(Map *map, mapblock_v3 minblock,
 980         mapblock_v3 maxblock, UnlightQueue unlight[2], ReLightQueue relight[2],
 981         std::map<v3s16, MapBlock*> *modified_blocks)
 982 {
 983         const NodeDefManager *ndef = map->getNodeDefManager();
 984         // dummy boolean
 985         bool is_valid;
 986
 987         // --- STEP 1: Do unlighting
 988
 989         for (size_t bank = 0; bank < 2; bank++) {
 990                 LightBank b = banks[bank];
 991                 unspread_light(map, ndef, b, unlight[bank], relight[bank],
 992                         *modified_blocks);
 993         }
 994
 995         // --- STEP 2: Get all newly inserted light sources
 996
 997         // For each block:
 998         v3s16 blockpos;
 999         v3s16 relpos;
1000         for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
1001         for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
1002         for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
1003                 MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
1004                 if (!block || block->isDummy())
1005                         // Skip not existing blocks
1006                         continue;
1007                 // For each node in the block:
1008                 for (relpos.X = 0; relpos.X < MAP_BLOCKSIZE; relpos.X++)
1009                 for (relpos.Z = 0; relpos.Z < MAP_BLOCKSIZE; relpos.Z++)
1010                 for (relpos.Y = 0; relpos.Y < MAP_BLOCKSIZE; relpos.Y++) {
1011                         MapNode node = block->getNodeNoCheck(relpos.X, relpos.Y, relpos.Z, &is_valid);
1012                         const ContentFeatures &f = ndef->get(node);
1013
1014                         // For each light bank
1015                         for (size_t b = 0; b < 2; b++) {
1016                                 LightBank bank = banks[b];
1017                                 u8 light = f.param_type == CPT_LIGHT ?
1018                                         node.getLightNoChecks(bank, &f):
1019                                         f.light_source;
1020                                 if (light > 1)
1021                                         relight[b].push(light, relpos, blockpos, block, 6);
1022                         } // end of banks
1023                 } // end of nodes
1024         } // end of blocks
1025
1026         // --- STEP 3: do light spreading
1027
1028         // For each light bank:
1029         for (size_t b = 0; b < 2; b++) {
1030                 LightBank bank = banks[b];
1031                 // Sunlight is already initialized.
1032                 u8 maxlight = (b == 0) ? LIGHT_MAX : LIGHT_SUN;
1033                 // Initialize light values for light spreading.
1034                 for (u8 i = 0; i <= maxlight; i++) {
1035                         const std::vector<ChangingLight> &lights = relight[b].lights[i];
1036                         for (std::vector<ChangingLight>::const_iterator it = lights.begin();
1037                                         it < lights.end(); ++it) {
1038                                 MapNode n = it->block->getNodeNoCheck(it->rel_position,
1039                                         &is_valid);
1040                                 n.setLight(bank, i, ndef);
1041                                 it->block->setNodeNoCheck(it->rel_position, n);
1042                         }
1043                 }
1044                 // Spread lights.
1045                 spread_light(map, ndef, bank, relight[b], *modified_blocks);
1046         }
1047 }
1048
1049 void blit_back_with_light(ServerMap *map, MMVManip *vm,
1050         std::map<v3s16, MapBlock*> *modified_blocks)
1051 {
1052         const NodeDefManager *ndef = map->getNodeDefManager();
1053         mapblock_v3 minblock = getNodeBlockPos(vm->m_area.MinEdge);
1054         mapblock_v3 maxblock = getNodeBlockPos(vm->m_area.MaxEdge);
1055         // First queue is for day light, second is for night light.
1056         UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
1057         ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
1058         // Will hold sunlight data.
1059         bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
1060         SunlightPropagationData data;
1061         // Dummy boolean.
1062         bool is_valid;
1063
1064         // --- STEP 1: reset everything to sunlight
1065
1066         // For each map block:
1067         for (s16 x = minblock.X; x <= maxblock.X; x++)
1068         for (s16 z = minblock.Z; z <= maxblock.Z; z++) {
1069                 // Extract sunlight above.
1070                 is_sunlight_above_block(map, v3s16(x, maxblock.Y, z), ndef, lights);
1071                 v2s16 offset(x, z);
1072                 offset *= MAP_BLOCKSIZE;
1073                 // Reset the voxel manipulator.
1074                 fill_with_sunlight(vm, ndef, offset, lights);
1075                 // Copy sunlight data
1076                 data.target_block = v3s16(x, minblock.Y - 1, z);
1077                 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1078                 for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
1079                         data.data.emplace_back(v2s16(x, z), lights[z][x]);
1080                 // Propagate sunlight and shadow below the voxel manipulator.
1081                 while (!data.data.empty()) {
1082                         if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
1083                                         &relight[0]))
1084                                 (*modified_blocks)[data.target_block] =
1085                                         map->getBlockNoCreateNoEx(data.target_block);
1086                         // Step downwards.
1087                         data.target_block.Y--;
1088                 }
1089         }
1090
1091         // --- STEP 2: Get nodes from borders to unlight
1092         v3s16 blockpos;
1093         v3s16 relpos;
1094
1095         // In case there are unloaded holes in the voxel manipulator
1096         // unlight each block.
1097         // For each block:
1098         for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
1099         for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
1100         for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
1101                 MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
1102                 if (!block || block->isDummy())
1103                         // Skip not existing blocks.
1104                         continue;
1105                 v3s16 offset = block->getPosRelative();
1106                 // For each border of the block:
1107                 for (const VoxelArea &a : block_pad) {
1108                         // For each node of the border:
1109                         for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
1110                         for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
1111                         for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {
1112
1113                                 // Get old and new node
1114                                 MapNode oldnode = block->getNodeNoCheck(relpos, &is_valid);
1115                                 const ContentFeatures &oldf = ndef->get(oldnode);
1116                                 MapNode newnode = vm->getNodeNoExNoEmerge(relpos + offset);
1117                                 const ContentFeatures &newf = oldnode == newnode ? oldf :
1118                                         ndef->get(newnode);
1119
1120                                 // For each light bank
1121                                 for (size_t b = 0; b < 2; b++) {
1122                                         LightBank bank = banks[b];
1123                                         u8 oldlight = oldf.param_type == CPT_LIGHT ?
1124                                                 oldnode.getLightNoChecks(bank, &oldf):
1125                                                 LIGHT_SUN; // no light information, force unlighting
1126                                         u8 newlight = newf.param_type == CPT_LIGHT ?
1127                                                 newnode.getLightNoChecks(bank, &newf):
1128                                                 newf.light_source;
1129                                         // If the new node is dimmer, unlight.
1130                                         if (oldlight > newlight) {
1131                                                 unlight[b].push(
1132                                                         oldlight, relpos, blockpos, block, 6);
1133                                         }
1134                                 } // end of banks
1135                         } // end of nodes
1136                 } // end of borders
1137         } // end of blocks
1138
1139         // --- STEP 3: All information extracted, overwrite
1140
1141         vm->blitBackAll(modified_blocks, true);
1142
1143         // --- STEP 4: Finish light update
1144
1145         finish_bulk_light_update(map, minblock, maxblock, unlight, relight,
1146                 modified_blocks);
1147 }
1148
1149 /*!
1150  * Resets the lighting of the given map block to
1151  * complete darkness and full sunlight.
1152  *
1153  * \param light incoming sunlight, light[x][z] is true if there
1154  * is sunlight above the map block at the given x-z coordinates.
1155  * The array's indices are relative node coordinates in the block.
1156  * After the procedure returns, this contains outgoing light at
1157  * the bottom of the map block.
1158  */
1159 void fill_with_sunlight(MapBlock *block, const NodeDefManager *ndef,
1160         bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
1161 {
1162         if (block->isDummy())
1163                 return;
1164         // dummy boolean
1165         bool is_valid;
1166         // For each column of nodes:
1167         for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1168         for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
1169                 // True if the current node has sunlight.
1170                 bool lig = light[z][x];
1171                 // For each node, downwards:
1172                 for (s16 y = MAP_BLOCKSIZE - 1; y >= 0; y--) {
1173                         MapNode n = block->getNodeNoCheck(x, y, z, &is_valid);
1174                         // Ignore IGNORE nodes, these are not generated yet.
1175                         if (n.getContent() == CONTENT_IGNORE)
1176                                 continue;
1177                         const ContentFeatures &f = ndef->get(n.getContent());
1178                         if (lig && !f.sunlight_propagates) {
1179                                 // Sunlight is stopped.
1180                                 lig = false;
1181                         }
1182                         // Reset light
1183                         n.setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
1184                         n.setLight(LIGHTBANK_NIGHT, 0, f);
1185                         block->setNodeNoCheck(x, y, z, n);
1186                 }
1187                 // Output outgoing light.
1188                 light[z][x] = lig;
1189         }
1190 }
1191
1192 void repair_block_light(ServerMap *map, MapBlock *block,
1193         std::map<v3s16, MapBlock*> *modified_blocks)
1194 {
1195         if (!block || block->isDummy())
1196                 return;
1197         const NodeDefManager *ndef = map->getNodeDefManager();
1198         // First queue is for day light, second is for night light.
1199         UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
1200         ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
1201         // Will hold sunlight data.
1202         bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
1203         SunlightPropagationData data;
1204         // Dummy boolean.
1205         bool is_valid;
1206
1207         // --- STEP 1: reset everything to sunlight
1208
1209         mapblock_v3 blockpos = block->getPos();
1210         (*modified_blocks)[blockpos] = block;
1211         // For each map block:
1212         // Extract sunlight above.
1213         is_sunlight_above_block(map, blockpos, ndef, lights);
1214         // Reset the voxel manipulator.
1215         fill_with_sunlight(block, ndef, lights);
1216         // Copy sunlight data
1217         data.target_block = v3s16(blockpos.X, blockpos.Y - 1, blockpos.Z);
1218         for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
1219         for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
1220                 data.data.emplace_back(v2s16(x, z), lights[z][x]);
1221         }
1222         // Propagate sunlight and shadow below the voxel manipulator.
1223         while (!data.data.empty()) {
1224                 if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
1225                                 &relight[0]))
1226                         (*modified_blocks)[data.target_block] =
1227                                 map->getBlockNoCreateNoEx(data.target_block);
1228                 // Step downwards.
1229                 data.target_block.Y--;
1230         }
1231
1232         // --- STEP 2: Get nodes from borders to unlight
1233
1234         // For each border of the block:
1235         for (const VoxelArea &a : block_pad) {
1236                 v3s16 relpos;
1237                 // For each node of the border:
1238                 for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
1239                 for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
1240                 for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {
1241
1242                         // Get node
1243                         MapNode node = block->getNodeNoCheck(relpos, &is_valid);
1244                         const ContentFeatures &f = ndef->get(node);
1245                         // For each light bank
1246                         for (size_t b = 0; b < 2; b++) {
1247                                 LightBank bank = banks[b];
1248                                 u8 light = f.param_type == CPT_LIGHT ?
1249                                         node.getLightNoChecks(bank, &f):
1250                                         f.light_source;
1251                                 // If the new node is dimmer than sunlight, unlight.
1252                                 // (if it has maximal light, it is pointless to remove
1253                                 // surrounding light, as it can only become brighter)
1254                                 if (LIGHT_SUN > light) {
1255                                         unlight[b].push(
1256                                                 LIGHT_SUN, relpos, blockpos, block, 6);
1257                                 }
1258                         } // end of banks
1259                 } // end of nodes
1260         } // end of borders
1261
1262         // STEP 3: Remove and spread light
1263
1264         finish_bulk_light_update(map, blockpos, blockpos, unlight, relight,
1265                 modified_blocks);
1266 }
1267
1268 VoxelLineIterator::VoxelLineIterator(const v3f &start_position, const v3f &line_vector) :
1269         m_start_position(start_position),
1270         m_line_vector(line_vector)
1271 {
1272         m_current_node_pos = floatToInt(m_start_position, 1);
1273         m_start_node_pos = m_current_node_pos;
1274         m_last_index = getIndex(floatToInt(start_position + line_vector, 1));
1275
1276         if (m_line_vector.X > 0) {
1277                 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5) + 1.5
1278                         - m_start_position.X) / m_line_vector.X;
1279                 m_intersection_multi_inc.X = 1 / m_line_vector.X;
1280         } else if (m_line_vector.X < 0) {
1281                 m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5)
1282                         - m_start_position.X + 0.5) / m_line_vector.X;
1283                 m_intersection_multi_inc.X = -1 / m_line_vector.X;
1284                 m_step_directions.X = -1;
1285         }
1286
1287         if (m_line_vector.Y > 0) {
1288                 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5) + 1.5
1289                         - m_start_position.Y) / m_line_vector.Y;
1290                 m_intersection_multi_inc.Y = 1 / m_line_vector.Y;
1291         } else if (m_line_vector.Y < 0) {
1292                 m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5)
1293                         - m_start_position.Y + 0.5) / m_line_vector.Y;
1294                 m_intersection_multi_inc.Y = -1 / m_line_vector.Y;
1295                 m_step_directions.Y = -1;
1296         }
1297
1298         if (m_line_vector.Z > 0) {
1299                 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5) + 1.5
1300                         - m_start_position.Z) / m_line_vector.Z;
1301                 m_intersection_multi_inc.Z = 1 / m_line_vector.Z;
1302         } else if (m_line_vector.Z < 0) {
1303                 m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5)
1304                         - m_start_position.Z + 0.5) / m_line_vector.Z;
1305                 m_intersection_multi_inc.Z = -1 / m_line_vector.Z;
1306                 m_step_directions.Z = -1;
1307         }
1308 }
1309
1310 void VoxelLineIterator::next()
1311 {
1312         m_current_index++;
1313         if ((m_next_intersection_multi.X < m_next_intersection_multi.Y)
1314                         && (m_next_intersection_multi.X < m_next_intersection_multi.Z)) {
1315                 m_next_intersection_multi.X += m_intersection_multi_inc.X;
1316                 m_current_node_pos.X += m_step_directions.X;
1317         } else if ((m_next_intersection_multi.Y < m_next_intersection_multi.Z)) {
1318                 m_next_intersection_multi.Y += m_intersection_multi_inc.Y;
1319                 m_current_node_pos.Y += m_step_directions.Y;
1320         } else {
1321                 m_next_intersection_multi.Z += m_intersection_multi_inc.Z;
1322                 m_current_node_pos.Z += m_step_directions.Z;
1323         }
1324 }
1325
1326 s16 VoxelLineIterator::getIndex(v3s16 voxel){
1327         return
1328                 abs(voxel.X - m_start_node_pos.X) +
1329                 abs(voxel.Y - m_start_node_pos.Y) +
1330                 abs(voxel.Z - m_start_node_pos.Z);
1331 }
1332
1333 } // namespace voxalgo
1334