src/voxelalgorithms.cpp

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