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